> On Jan 30, 2017, at 12:41 PM, Antonio Sanso <asa...@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 <tr...@trevp.net > <mailto:tr...@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
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves
