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

["Dan Harkins" <[e-mail]>]

  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.