ecc-formulas.tex 10.2 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

\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$.

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
\subsection{Montgomery ladder}

It's possible to do operations on a Montgomery curve in terms of the
$x$ coordinate only. Or, with homogeneous coordinates, use $X$ and $Z$
with $x = X/Z$.

For doubling,
\begin{align*}
  x' &= (x^2 - z^2)^2 = (x-z)^2 (x+z)^2 \\
  t &= (x+z)^2 - (x-z)^2 \\
  z' &= 4 xz (x^2 + bzx + z^2) = t \left((x+z)^2 + b't\right)
\end{align*}
with $b' = (b-2)/4$.

Addition is a bit trickier. If we have $x$ and $z$ for points $Q_1$,
$Q_2$ and $Q_3$, with $Q_3 = Q_1 +  Q_3$, and $x_1, z_1 \neq 0$, we
get the coordinates for $Q_2 + Q_3$ as
\begin{align*}
  x' &= 4 (x_2 x_3 - z_2 z_3)^2 z_1 = \left((x_2 - z_2)(x_3 + z_3) +
    (x_2 + z_2)(x_3 - z_3)\right)^2 z_1 \\
  z' &= 4 (x_2 z_3 - z_2 x_3)^2 x_1 = \left((x_2 - z_2)(x_3 + z_3) -
    (x_2 + z_2)(x_3 - z_3)\right)^2 x_1
\end{align*}
Note that the doubling formula is symmetric in $Q_2$ and $Q_3$. Which
is consistent with negating of $Q_1$, which really is the negatiion of
the $y$-coordinate, which doesn't appear in the formula.

This can be used for a binary ``Montgomery ladder'' to compute $n Q$
for any $n$. If we have the points $Q$, $n Q$, and $(n+1) Q$, we can
compute the three points
\begin{align*}
  (2n) Q &= 2 (nQ) && \text{doubling} \\
  (2n+1) Q &= (nQ) + (n+1)Q && \text{addition} \\
  (2n+2) Q &= 2((n+1) Q) && \text{doubling}
\end{align*}

The following algorithm is suggested by dj (see
\url{http://www.ietf.org/mail-archive/web/cfrg/current/msg05004.html}.
\begin{verbatim}
   x2,z2,x3,z3 = 1,0,x1,1
   for i in reversed(range(255)):
     bit = 1 & (n >> i)
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
     x3,z3 = ((x2*x3-z2*z3)^2,x1*(x2*z3-z2*x3)^2)
     x2,z2 = ((x2^2-z2^2)^2,4*x2*z2*(x2^2+A*x2*z2+z2^2))
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
   return x2*z2^(p-2)
\end{verbatim}
It's not too hard to decipher this. The update for $x_2, z_2$ is the
doubling. The update for $x_3, z_3$ is an addition.

If the bit is zero, we get $x_2', z_2'$ representing $Q_2' = 2 Q_2$,
and $x_3', z_3'$ representing $Q_3' = Q_2 + Q_3 = 2 Q_2 + Q_1$.

What if the bit is set? For the doubling, we get it applied to $Q_3$
instead, so we get $x_3', z_3'$ representing $Q_3' = 2 Q_3 = 2 Q_2 + 2
Q_1$. For the add, the initial swap flips the sign of one of the
intermediate values, but the end result is the same, so we get $x_2',
z_2'$ representing $Q_2' = Q_2 + Q_3 = 2 Q_2 + Q_1$, as desired.

Note that the initial conditional swap doesn't have to be a full swap;
if that's convenient in the implementation, a conditional assignment
should be sufficient to get the duplication formula appplied to the
right point. It looks like, in all cases, one will start by computing
$x_2 \pm z_2$ and $x_3 \pm z_3$, so maybe one can apply conditional
assignment to these values instead.

Niels Möller's avatar
Niels Möller committed
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
\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
177
178
179
180
181
\section{EdDSA}

The EdDSA paper (\url{http://ed25519.cr.yp.to/ed25519-20110926.pdf})
suggests using the twisted Edwards curve,
\begin{equation*}
182
  -x^2 + y^2 = 1 + d' x^2 y^2 \pmod{p}
Niels Möller's avatar
Niels Möller committed
183
\end{equation*}
184
(For this we use the same $d' = -d = (121665/121666) \bmod p$).
Niels Möller's avatar
Niels Möller committed
185
186
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
187
Edwards curve. The point addition formulas for the twisted Edwards
Niels Möller's avatar
Niels Möller committed
188
189
curve are
\begin{align*}
190
  t &= d' x_1 x_2 y_1 y_2 \\
Niels Möller's avatar
Niels Möller committed
191
192
193
  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*}
194
195
196
197
198
199
200
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
201
202
203
204
205
206
207
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}).

208
209
According to djb, the formulas in Section 3.1 are the once to use,
because they are complete. See
210
\url{http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#addition-add-2008-hwcd-3},
211
\begin{align*}
212
213
214
215
216
217
218
219
220
221
222
223
  A &= (y_1 - x_1)(y_2 - x_2) \\
  B &= (y_1 + x_1)(y_2 + x_2) \\
  C &= 2 t_1 d' t_2 \\
  D &= 2 z_1 z_2 \\
  E &= B - A \\
  F &= D - C \\
  G &= D + C \\
  H &= B + A \\
  x_3 &= E F \\
  y_3 &= G H \\
  t_3 &= E H \\
  z_3 &= F G
224
225
226
227
\end{align*}

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

Niels Möller's avatar
Niels Möller committed
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
\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*}
250
    u &= \sqrt{b+2} \, x / y \\
Niels Möller's avatar
Niels Möller committed
251
252
253
254
255
256
257
    v &= (x-1) / (x+1)
  \end{align*}
\end{itemize}

The inverse transformation is
\begin{align*}
  x &= (1+v) / (1-v) \\
258
  y &= \sqrt{b+2} \, x / u 
Niels Möller's avatar
Niels Möller committed
259
260
261
262
263
264
265
266
\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$.
267

Niels Möller's avatar
Niels Möller committed
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
\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}

287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
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
317
318
319
320
321
322
\end{document}

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