Re: [Hipsec] HIT construction for ECC HIs

[Robert Moskowitz <[e-mail]>]

More on this from the

On 04/14/2010 10:03 AM, Robert Moskowitz wrote:
> This may only be applied to Diet HIP, but ECC public keys have some 
> interesting properties:
>
> The Private key is a uniformly distributed random number. From:
>
> draft-mcgrew-fundamental-ecc-02.txt, sec 5.3.1:
>
> The private key z is an integer between 1 and q - 1, inclusive,
> generated uniformly at random. (See Appendix B regarding random
> integers.) The public key is the group element
> Y = alpha^z. Each public key is associated with a particular
> particular parameter set as per Section 3.3.
>
>
> Thus the private key is uniformly distributed from the set:
>
> { 1, 2, .... , q-1 }
>
> Further a subset of the bits of the PK are uniformly distributed.
>
> Thus it is conceivable that the HIT for an ECC HI is just 96 bits 
> selected from the HI. To put it within the ORCHID context, it could be 
> a simple XOR with the HIP ECC context.
>
> Comments?

 From the IRTF cfrg list:

============================

Don't have a proof, but here's a couple of thoughts:

I actually wondered about the same question a few years ago and ran an 
experiment: I generated a few thousand public keys and ran the NIST 
randomness tests on them. Based on those tests, at least, the bits in 
the public keys did indeed look pretty random.

Actually, here's a proof sketch:
-- ECC public key has the form (x,y), where x,y in GF(2^n) satisfy the 
curve equations
-- Since the curve equations are quadratic in y, the standard compact 
form of a public key is (x,b), where b is a single bit that indicates 
which of the two possible y values (see, e.g., [1])
-- A random public key is generated as a random element of a cyclic 
group of order p~=2^n
-- So the entropy of the public key is approximately n bits, in a 
representation with n+1 bits
-- So the public key distribution has to be close to uniform, for some 
definition of "close" (e.g., in terms of Kullback-Liebler divergence)

[1] <http://csrc.nist.gov/rng/>
[1] <http://www.hpl.hp.com/techreports/98/HPL-98-94R1.pdf>

===========================================