1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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)
|
