Re: [Cfrg] uniform random distribution in ECDH public key

"Scott Fluhrer (sfluhrer)" <> Tue, 14 August 2012 18:14 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 1E7EC21F8793 for <>; Tue, 14 Aug 2012 11:14:44 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -10.599
X-Spam-Status: No, score=-10.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id xNa+a4eWYlW2 for <>; Tue, 14 Aug 2012 11:14:43 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id 5995F21F878B for <>; Tue, 14 Aug 2012 11:14:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple;;; l=1476; q=dns/txt; s=iport; t=1344968083; x=1346177683; h=from:to:subject:date:message-id:references:in-reply-to: content-transfer-encoding:mime-version; bh=Kl0yFL8WSOFZUIPAgQNUEhGgbIdvCqhR4sm2vZm4E7U=; b=lwgFiqfwflMf0bn12cCL7oCHNy5ZOPTvgGA2T/AUuSRiRgk0gi8Zg4ya gcI+BOS3VlQEHk0+zFyz+6uO2e0PfQEezaI3iZ/RjUm0QTAEEU3KBmPi0 Mhwy/lNWFNXYEFAsCg6iqjKO83QiCyyqC5vF0B9/2qVX+zxmZlIJMXnZO 0=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-AV: E=Sophos;i="4.77,768,1336348800"; d="scan'208";a="111524951"
Received: from ([]) by with ESMTP; 14 Aug 2012 18:14:42 +0000
Received: from ( []) by (8.14.5/8.14.5) with ESMTP id q7EIEgvE022728 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Tue, 14 Aug 2012 18:14:42 GMT
Received: from ([]) by ([]) with mapi id 14.02.0298.004; Tue, 14 Aug 2012 13:14:42 -0500
From: "Scott Fluhrer (sfluhrer)" <>
To: Robert Moskowitz <>, "" <>
Thread-Topic: [Cfrg] uniform random distribution in ECDH public key
Thread-Index: AQHNekb9jeMcpOeb9EuiRpkm0AlB15dZm7Kw
Date: Tue, 14 Aug 2012 18:14:41 +0000
Message-ID: <>
References: <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
x-originating-ip: []
x-tm-as-product-ver: SMEX-
x-tm-as-result: No--32.925400-8.000000-31
x-tm-as-user-approved-sender: No
x-tm-as-user-blocked-sender: No
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: Re: [Cfrg] uniform random distribution in ECDH public key
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 14 Aug 2012 18:14:44 -0000

No, the value g^j (or jG, if we prefer the more traditional additive notation for elliptic curves) is not uniform; it is a 512 bit value (for P256), and corresponds to a point on the curve (that is, it is a pair of 256 bit values that together are a solution to a specific cubic equation).  There are approximately 2^256 possible values for this 512 bit value, and so there are a large number of 512 bit public values which are not possible.

-----Original Message-----
From: [] On Behalf Of Robert Moskowitz
Sent: Tuesday, August 14, 2012 2:02 PM
Subject: [Cfrg] uniform random distribution in ECDH public key

I understand from RFC 6090 and 5869 that the secret key produced from an 
ECDH exchange is not uniformly randomly distributed and that is why we 
have the 'Extract' phase in HKDF.  Got that.

This question is about the public key, g^j:

I understand that like j, it must be a point on the curve, thus if the 
curve is p-256, both j and g^j are 256 bits long.  But is g^j uniformly 
randomly distributed like j is suppose to be?

Side question:  I am still unclear on the length of the exchanged secret 
(g^j)^k, is it 256 bits (for p-256) or larger (perhaps 512 bits)?

Thank you for helping me get all this straight.

Cfrg mailing list