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

David Jacobson <> Thu, 23 August 2012 05:17 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 469B021F8470 for <>; Wed, 22 Aug 2012 22:17:44 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.74
X-Spam-Status: No, score=-0.74 tagged_above=-999 required=5 tests=[BAYES_20=-0.74]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 6PFD605VO08V for <>; Wed, 22 Aug 2012 22:17:43 -0700 (PDT)
Received: from ( []) by (Postfix) with SMTP id 719BC21F8471 for <>; Wed, 22 Aug 2012 22:17:42 -0700 (PDT)
Received: from [] by with NNFMP; 23 Aug 2012 05:17:39 -0000
Received: from [] by with NNFMP; 23 Aug 2012 05:17:39 -0000
Received: from [] by with NNFMP; 23 Aug 2012 05:17:39 -0000
Received: from [] by with NNFMP; 23 Aug 2012 05:17:39 -0000
Received: (qmail 60069 invoked from network); 23 Aug 2012 05:17:39 -0000
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024;; h=DKIM-Signature:X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=icGVbA9mCf7OfJfl5l5hLw+cLpR9hyWPtf1SSqzCtup+0E1j7ccPVc2m2i1iAOKwsisFZ8xvQjBJg5oCkdsOf6rmmZNXAiSnq8aXeZz9c+C9NESHFcCy/M7TRTbDtJ/RjZHpHDC1mL6KI4e6T/deJZ3Al1VH3WbP67+UXNNI1nM= ;
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=s1024; t=1345699059; bh=57BnRH57dpPT3Oc1DxayLYUiANp7JWcn7WLZivYNaWU=; h=X-Yahoo-Newman-Property:X-YMail-OSG:X-Yahoo-SMTP:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:Subject:References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=6ngj7xcijRLaNr4m6xikBQpJcH1dwfP60RMju9kL+IcCKNG0tX+KjBX0d72/KG1HdCWSu4zEhitnpOmROMNk6lm+1y5ZpuWV+AJY5YzjV4aoni56P/YOtWdjz3romZO74OniQ4Lspye/lGjY1ts7zCFDszyld8w03E+q5jeJ5vI=
X-Yahoo-Newman-Property: ymail-3
X-YMail-OSG: evCRO00VM1nfQBf1kDA4L9OkwRV_v1eoW9m2PctAv0.LZV1 ZWxr9fiWIxOj1yDPIrEJBoy95fWYwdVEMak5zGgiCfPyUa8sXeGJisTozKIF ii57mtA0hb58pWzcCTkk4VTH3aLmpzJ2N.n40KNgqbEdzmpCqU2nY5ey52mC FjDkyQBCOAaLiPhU1EVHBlAAMJmjDrXvSICYicYLtamq.2g4Kc74QU9zcwb4 cooMjZIHSnEjKz2ov3n29Obp.8dr_yHaGjdGsfUw_ayL4lE4MZEjMmGTxJxj JNbSUt7TcF8kOPeKmpiQofxbqEirFdBU4vzlWsKAff0LY_Pbw3DDJEhsPKFi KD12N1.g1C9X2T1SwAJtlMsNK_uOUvhUJyujwUyWKnmenH7W8X_NsjeZlm07 bzDawDhS6zVCUGGdJBHh9sS0s2Z9DgCreC8Q3czYs2rzMFqiNHdUCCLPp68K yiTeUUbBqHQ--
X-Yahoo-SMTP: nOrmCa6swBAE50FabWnlVFUpgFVJ9Gbi__8U5mpvhtQq7tTV1g--
Received: from [] (dmjacobson@ with plain) by with SMTP; 22 Aug 2012 22:17:39 -0700 PDT
Message-ID: <>
Date: Wed, 22 Aug 2012 22:17:37 -0700
From: David Jacobson <>
User-Agent: Mozilla/5.0 (X11; Linux i686; rv:14.0) Gecko/20120714 Thunderbird/14.0
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
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: Thu, 23 Aug 2012 05:17:44 -0000

On 08/14/2012 11:23 AM, Dan Harkins wrote:
>    Hi Bob,
> On Tue, August 14, 2012 11:01 am, Robert Moskowitz wrote:
>> 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?
>    No, it's not. It's it's a special pair (x,y) that satisfy the equation
> of the
> curve:  y^2 = x^3 + ax + b. Not all pairs will satisfy that equation. I
> believe about half of them will and about half won't.
>    For x to be random, each number between 0 and p would have equal
> probability. But that's not the case since about half won't.
>> 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)?
>    The result of an ECDH is an element in the group so it's also an (x,y)
> pair but the secret that you use in your KDF is the x coordinate of that
> result. The y coordinate is discarded.
>    regards,
>    Dan.
> _______________________________________________
> Cfrg mailing list
So now that we are into tutorial mode on this, I'd like to ask a 
question.  Standard procedure for Diffie-Hellman key exchange is to 
construct the session key from the X-coordinate by hashing.  Now suppose 
that I'm using the NIST P-256 curve and the symmetric encryption 
functions is AES-256.

The number of possible shared key values is the order of the curve - 1 
(point at infinity isn't used), which is extremely close to 2^256.    
These points come in pairs, if there is a point at an X value, there are 
2, one at Y and the other -Y.  So essentially all X values occur with 
probability  very close to 2/2^256, which means that the X-coordinate 
after the DH procedure can be thought of as a source with 255 bits of  
min-entropy.  If we hash the X coordinate with SHA-256, we actually lose 
a little bit of entropy, since some X values will collide and produce 
some session key with probability higher than 2/2^256, lowering the 

So what is the advantage of the hash operation?

Thank you,

     --David Jacobson