ecc-formulas.tex 7.41 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{url}

\author{Niels Möller}
\title{Notes on ECC formulas}

\begin{document}

\maketitle

\section{Weierstrass curve}

Consider only the special case
\begin{equation*}
Niels Möller's avatar
Niels Möller committed
17
  y^2 = x^3 - 3x + b \pmod{p}
Niels Möller's avatar
Niels Möller committed
18
19
20
21
22
23
24
25
26
27
28
\end{equation*}
See \url{http://www.hyperelliptic.org/EFD/g1p/auto-shortw.html}.

Affine formulas for duplication, $(x_2, y_2) = 2(x_1, y_1)$:
\begin{align*}
  t &=  (2y)^{-1} 3 (x_1^2 - 1) \\
  x_2 &= t^2 - 2 x_1 \\
  y_2 &= (x_1 - x_2) * t - y_1
\end{align*}
Affine formulas for addition, $(x_3, y_3) = (x_1, y_1) + (x_2,
y_2)$:
Niels Möller's avatar
Niels Möller committed
29
\begin{align*}
Niels Möller's avatar
Niels Möller committed
30
31
32
  t &= (x_2 - x_1)^{-1} (y_2 - y_1) \\
  x_3 &= t^2 - x_1 - x_2 \\
  y_3 &= (x_1 - x_3) t - y_1
Niels Möller's avatar
Niels Möller committed
33
\end{align*}
Niels Möller's avatar
Niels Möller committed
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

\section{Montgomery curve}

Consider the special case
\begin{equation*}
  y^2 = x^3 + b x^2 + x  
\end{equation*}
See \url{http://www.hyperelliptic.org/EFD/g1p/auto-montgom.html}.

Affine formulas for duplication, $(x_2, y_2) = 2(x_1, y_1)$:
\begin{align*}
  t &= (2 y_1)^{-1} (3 x_1^2 + 2b x_1 + 1) \\
  x_2 &= t^2 - b - 2 x_1 \\
  y_2 &= (3 x_1 + b) t - t^3 - y_1 \\
  &= (3 x_1 + b - t^2) t - y_1 \\
  &= (x_1 - x_2) t - y_1
\end{align*}
So the computation is very similar to the Weierstraß case, differing
only in the formula for $t$, and the $b$ term in $x_2$.

Affine formulas for addition, $(x_3, y_3) = (x_1, y_1) + (x_2,
y_2)$:
\begin{align*}
  t &= (x_2 - x_1)^{-1} (y_2 - y_1) \\
  x_3 &= t^2 - b - x_1 - x_2 \\
  y_3 &= (2 x_1 + x_2 + b) t - t^3 - y_1 \\
  &= (2 x_1 + x_2 + b - t^2) t - y_1 \\
  &= (x_1 - x_3) t - y_1
\end{align*}
Again, very similar to the Weierstraß formulas, with only an
additional $b$ term in the formula for $x_3$.

\section{Edwards curve}

For an Edwards curve, we consider the special case
\begin{equation*}
  x^2 + y^2 = 1 + d x^2 y^2
\end{equation*}
See \url{http://cr.yp.to/papers.html#newelliptic}.

Affine formulas for addition, $(x_3, y_3) = (x_1, y_1) + (x_2,
y_2)$:
\begin{align*}
  t &= d x_1 x_2 y_1 y_2 \\
  x_3 &= (1 + t)^{-1} (x_1 y_2 + y_1 x_2) \\
  y_3 &= (1 - t)^{-1} (y_1 y_2 - x_1 x_2)
\end{align*}
With homogeneous coordinates $(X_1, Y_1, Z_1)$ etc., D.~J.~Bernstein
suggests the formulas
\begin{align*}
  A &= Z_1 Z_2 \\
  B &= A^2 \\
  C &= X_1 X_2 \\
  D &= Y_1 Y_2 \\
  E &= d C D \\
  F &= B - E \\
  G &= B + E \\
  X_3 &= A F [(X_1 + Y_1)(X_2 + Y_2) - C - D] \\
  Y_3 &= A G (D - C) \\
  Z_3 &= F G
\end{align*}
This works also for doubling, but a more efficient variant is
\begin{align*}
  B &= (X_1 + Y_1)^2 \\
  C &= X_1^2 \\
  D &= Y_1^2 \\
  E &= C + D \\
  H &= Z_1^2 \\
  J &= E - 2H \\
  X_3 &= (B - E) J \\
  Y_3 &= E (C - D) \\
  Z_3 &= E J
\end{align*}

Niels Möller's avatar
Niels Möller committed
108
109
110
111
112
\section{EdDSA}

The EdDSA paper (\url{http://ed25519.cr.yp.to/ed25519-20110926.pdf})
suggests using the twisted Edwards curve,
\begin{equation*}
113
  -x^2 + y^2 = 1 + d' x^2 y^2 \pmod{p}
Niels Möller's avatar
Niels Möller committed
114
\end{equation*}
115
(For this we use the same $d' = -d = (121665/121666) \bmod p$).
Niels Möller's avatar
Niels Möller committed
116
117
Assuming -1 has a square root modulo $p$, a point $(x, y)$ lies on
this curve if and only if $(\sqrt{-1} x, p)$ lies of the non-twisted
118
Edwards curve. The point addition formulas for the twisted Edwards
Niels Möller's avatar
Niels Möller committed
119
120
curve are
\begin{align*}
121
  t &= d' x_1 x_2 y_1 y_2 \\
Niels Möller's avatar
Niels Möller committed
122
123
124
  x_3 &= (1 + t)^{-1} (x_1 y_2 + y_1 x_2) \\
  y_3 &= (1 - t)^{-1} (y_1 y_2 + x_1 x_2)
\end{align*}
125
126
127
128
129
130
131
or in terms of $d$ rather than $d'$, signs are switched as
\begin{align*}
  t &= d x_1 x_2 y_1 y_2 \\
  x_3 &= (1 - t)^{-1} (x_1 y_2 + y_1 x_2) \\
  y_3 &= (1 + t)^{-1} (y_1 y_2 + x_1 x_2)
\end{align*}

Niels Möller's avatar
Niels Möller committed
132
133
134
135
136
137
138
For the other formulas, it should be fine to just switch the sign of
terms involving $x_1 x_2$ or $x_1^2$. The paper suggests further
optimizations: For precomputed points, use the representation $(x-y,
x+y, dxy)$. And for temporary points, maintain an additional redundant
coordinate $T$, with $Z T = X Y$ (see
\url{http://eprint.iacr.org/2008/522.pdf}).

139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
According to djb, the formulas in Section 3.1 are the once to use,
because they are complete. See
\url{http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#addition-add-2008-hwcd},
\begin{align*}
  A &= x_1 x_2 \\
  B &= y_1 y_2 \\
  C &= t_1 d' t_2 \\
  D &= z_1 z_2 \\
  E &= (x_1+y_1) (x_2+y_2)-A-B \\
  F &= D-C \\
  G &= D+C \\
  H &= B-a A \\
  x_3 &= E*F \\
  y_3 &= G*H \\
  t_3 &= E*H \\
  z_3 &= F*G
\end{align*}

In our notation $a = -1$, and the $d'$ above is $-d$.

Niels Möller's avatar
Niels Möller committed
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
\section{Curve25519}

Curve25519 is defined as the Montgomery curve
\begin{equation*}
  y^2 = x^3 + b x^2 + x \pmod p
\end{equation*}
with $b = 486662$ and $p = 2^{255} -19$. It is equivalent to the
Edwards curve
\begin{equation*}
  u^2 + v^2 = 1 + d u^2 v^2 \pmod p
\end{equation*}
with $d = (121665/121666) \bmod p$. The equivalence is given by
mapping $P = (x,y)$ to $P' = (u, v)$, as follows.
\begin{itemize}
\item $P = \infty$ corresponds to $P' = (0, 1)$
\item $P = (0, 0)$ corresponds to $P' = (0, -1)$
\item Otherwise, for all other points on the curve. First note that $x
  \neq -1$ (since then the right hand side is a not a quadratic
  residue), and that $y \neq 0$ (since $y = 0$ and $x \neq 0$ implies
  that $x^2 + bx + 1 = 0$, or $(x + b/2)^2 = (b/2)^2 - 1$, which also
  isn't a quadratic residue). The correspondence is then given by
  \begin{align*}
181
    u &= \sqrt{b+2} \, x / y \\
Niels Möller's avatar
Niels Möller committed
182
183
184
185
186
187
188
    v &= (x-1) / (x+1)
  \end{align*}
\end{itemize}

The inverse transformation is
\begin{align*}
  x &= (1+v) / (1-v) \\
189
  y &= \sqrt{b+2} \, x / u 
Niels Möller's avatar
Niels Möller committed
190
191
192
193
194
195
196
197
\end{align*}
If the Edwards coordinates are represented using homogeneous
coordinates, $u = U/W$ and $v = V/W$, then
\begin{align*}
  x &= \frac{W+V}{W-V} \\
  y &= \sqrt{b} \frac{(W+V) W}{(W-V) U} 
\end{align*}
so we need to invert the value $(W-V) U$.
198

Niels Möller's avatar
Niels Möller committed
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
\subsection{Transforms for the twisted Edwards Curve}

If we use the twisted Edwards curve instead, let $\alpha = \sqrt{-1}
\pmod{p}$. Then we work with coordinates $(u', v)$, where $u' = \alpha
u$. The transform from Montgomery form $(x, y)$ is then
\begin{align*}
  u &= (\alpha \sqrt{b+2}) \, x / y\\
  v &= (x-1) / (x+1)
\end{align*}
And the inverse transform is similarly
\begin{align*}
  x &= (1+v) / (1-v) \\
  y &= (\alpha \sqrt{b+2}) \, x / u 
\end{align*}
so it's just a change of the transform constant, effectively using
$\sqrt{-(b+2)}$ instead.

\subsection{Coordinates outside of the base field}

218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
The curve25519 function is defined with an input point represented by
the $x$-coordinate only, and is specified as allowing any value. The
corresponding $y$ coordinate is given by 
\begin{equation*}
  y = \sqrt{x^3 + b x^2 + x} \pmod p
\end{equation*}
whenever this square root exists. But what if it doesn't? Then we work
with the curve over the extended field $F_{p^2}$. Let $n$ by any
non-square, then $(x^3 + b x^2 + x) n$ is a square, and we get the
$y = y' / \sqrt{n}$ with
\begin{equation*}
  y' = \sqrt{(x^3 + b x^2 + x) n}
\end{equation*}
It happens that for all multiples of such a point, this same factor is
tacked on to all the $y$-coordinates, while all the $x$-coordinates
remain in the base field $F_p$. It's the ``twist'' curve $y'^2 / n =
x^3 + bx^2 + x$. On the corresponding Edwards curve, we
get $u = \sqrt{n} u'$ with
\begin{equation*}
  u' = \sqrt{b+2} \, x / y'
\end{equation*}
and the addition formula
\begin{align*}
  t &= d n u'_1 u'_2 v_1 v_2 \\
  u'_3 &= (1+t)^{-1}(u'_1v_2 + v_1 u'_2) \\
  v_3 &= (1-t)^{-1}(v_1 v_2 - n u'_1 u'_2)
\end{align*}
It seems a bit tricky to handle both types of point in a single
function without speed penalty, due to the conditional factor of $n$
in the formula for $v_3$.
Niels Möller's avatar
Niels Möller committed
248
249
250
251
252
253
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: