Subject: [Hipsec] HIT construction for ECC HIs

From: Robert Moskowitz <[email-masked]>
Date: Wed, 14 Apr 2010 10:03:16 -0400

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?

Oh, this ASSuMEs that the EC private key was indeed uniformly randomly 
selected from the possible private keys...

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 14 Apr 2010 11:10:08 -0400

More on this from the

> a simple XOR with the HIP ECC context.

 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>

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