Converting a curve25519 public key to an ed25519 public key

Given an X25519 key, that is, an affine point (u,v) on the Montgomery curve defined by

bv^2 = u(u^2 + au +1)

where

         a = 486662
         b = 1

and comprised of the compressed form (i.e. consisting of only the u-coordinate), we can retrieve the y-coordinate of the affine point (x,y) on the twisted Edwards form of the curve defined by

-x^2 + y^2 = 1 + d x^2 y^2

where

d = - 121665/121666

by computing

y = (u-1)/(u+1).

and then we can apply the usual curve25519 twisted Edwards point decompression algorithm to find an x-coordinate of an affine twisted Edwards point to check signatures with. Signing keys for ed25519 are compressed curve points in twisted Edwards form (so a y-coordinate and the sign of the x-coordinate), and X25519 keys are compressed curve points in Montgomery form (i.e. a u-coordinate).

However, note that compressed point in Montgomery form neglects to encode what the sign of the corresponding twisted Edwards x-coordinate would be. Thus, we need the sign of the x-coordinate to do this operation; otherwise, we'll have two possible x-coordinates that might have correspond to the ed25519 public key.

To get the sign, the easiest way is to take the corresponding private key, feed it to the ed25519 public key generation algorithm, and see what the sign is.

[Recomputing the sign bit from the private key every time sounds rather strange and inefficient to me… —isis]

Note that in addition to its coordinates, an expanded Ed25519 private key also has a 32-byte random value, "prefix", used to compute internal r values in the signature. For security, this prefix value should be derived deterministically from the curve25519 key. The Tor implementation derives it as SHA512(private_key | STR)[0..32], where STR is the nul-terminated string:

"Derive high part of ed25519 key from curve25519 key\0"

On the client side, where there is no access to the curve25519 private keys, one may use the curve25519 public key's Montgomery u-coordinate to recover the Montgomery v-coordinate by computing the right-hand side of the Montgomery curve equation:

bv^2 = u(u^2 + au +1)

where

         a = 486662
         b = 1

Then, knowing the intended sign of the Edwards x-coordinate, one may recover said x-coordinate by computing:

x = (u/v) * sqrt(-a - 2)