[curves] Climbing the elliptic learning curve (was: Re: Finalizing XEdDSA)

[Mike Hamburg]

> On Jan 30, 2017, at 12:41 PM, Antonio Sanso <asanso at adobe.com> wrote:
> 
> Thanks a lot Trevor,
> 
> this was a great write up.
> One more question
> 
> On Nov 7, 2016, at 12:51 AM, Trevor Perrin <trevp at trevp.net <mailto:trevp at trevp.net>> wrote:
> 
>> However, cofactor>1 can still have subtle and unexpected effects, e.g.
>> see security considerations about "equivalent" public keys in RFC
>> 7748, which is relevant to the cofactor multiplication "cV" in
>> VXEdDSA, or including DH public keys into "AD" in Signal's (recently
>> published) X3DH [3].
> 
> may you shed some more light about this?
> What is the algorithm to find and “equivalent” public key?
> 
> regards
> 
> antonio

There are two degrees of freedom in making X25519 public keys equivalent.

First, the standard specifies that public keys must be treated the same as if they were reduced modulo p = 2^255-19.  That means that if x is a public key computed by the standard algorithm, then x+p is an equivalent public key, and x+2p is too if that fits in 32 bytes.  The same is true for p=2^448-2^224-1, except that for this prime, x+p is too large to write down in 56 bytes for almost every x.

Second, two x’s are equivalent if they differ by a c-torsion point.  This is because the X25519 Diffie-Hellman key exchange algorithm is computing c*secret*P, which is the same as c*secret*(P+T) for points T such that c*T is the identity.  Another way to describe these equivalent keys is that they’re the x-coordinates of points Q such that c*Q = c*P.  Such keys can be found in SAGE by computing

[P.xy()[0] for P in (c*E.lift_x(x)).division_points(c)]

where the cofactor c is 8 for X25519 and 4 for X448.  One of these points will always be 1/x modulo p.  There are surely somewhat-less-nice formulas for the rest of them.

Of course, these two classes can be combined, so that P.xy()[0] + p is also an equivalent public key.

Cheers,
— Mike
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170130/3bafe34b/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3571 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170130/3bafe34b/attachment.bin>