1 files changed, 77 insertions, 0 deletions
diff --git a/spec/dir-spec/converting-to-ed25519.md b/spec/dir-spec/converting-to-ed25519.md
new file mode 100644
index 0000000..57f9d1d
--- /dev/null
+++ b/spec/dir-spec/converting-to-ed25519.md
@@ -0,0 +1,77 @@
+<a id="dir-spec.txt-C"></a>
+
+# 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
+
+```text
+         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
+
+```text
+         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)