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

[Trevor Perrin]

On Mon, Jan 30, 2017 at 1:48 PM, Mike Hamburg <mike at shiftleft.org> wrote:
>
> On Jan 30, 2017, at 12:41 PM, Antonio Sanso <asanso at adobe.com> wrote:
>
> On Nov 7, 2016, at 12:51 AM, Trevor Perrin <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?
[...]
>
> 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.

I'll describe the same thing, but maybe this is simpler wording:

For X25519, just add a point of low order (i.e. order=2, 4, or 8) onto
an X25519 public key.  Because X25519 private keys are multiples of
the cofactor (8), the added point won't change DH results.

I.e. for public key A, some private key b, and low-order point L:

b(A+L) = bA + bL = bA


Trevor