ecc-formulas.tex 10.2 KB
 Niels Möller committed Jul 11, 2014 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 committed Aug 24, 2014 17  y^2 = x^3 - 3x + b \pmod{p}  Niels Möller committed Jul 11, 2014 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 committed Aug 27, 2014 29 \begin{align*}  Niels Möller committed Jul 11, 2014 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 committed Aug 27, 2014 33 \end{align*}  Niels Möller committed Jul 11, 2014 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$.  Niels Möller committed Sep 06, 2014 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 committed Jul 11, 2014 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 committed Aug 27, 2014 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*}  Niels Möller committed Aug 28, 2014 182  -x^2 + y^2 = 1 + d' x^2 y^2 \pmod{p}  Niels Möller committed Aug 27, 2014 183 \end{equation*}  Niels Möller committed Aug 28, 2014 184 (For this we use the same $d' = -d = (121665/121666) \bmod p$).  Niels Möller committed Aug 27, 2014 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  Niels Möller committed Aug 28, 2014 187 Edwards curve. The point addition formulas for the twisted Edwards  Niels Möller committed Aug 27, 2014 188 189 curve are \begin{align*}  Niels Möller committed Aug 28, 2014 190  t &= d' x_1 x_2 y_1 y_2 \\  Niels Möller committed Aug 27, 2014 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*}  Niels Möller committed Aug 28, 2014 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 committed Aug 27, 2014 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}).  Niels Möller committed Aug 28, 2014 208 209 According to djb, the formulas in Section 3.1 are the once to use, because they are complete. See  Niels Möller committed Aug 28, 2014 210 \url{http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#addition-add-2008-hwcd-3},  Niels Möller committed Aug 28, 2014 211 \begin{align*}  Niels Möller committed Aug 28, 2014 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  Niels Möller committed Aug 28, 2014 224 225 226 227 \end{align*} In our notation $a = -1$, and the $d'$ above is $-d$.  Niels Möller committed Jul 11, 2014 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*}  Niels Möller committed Aug 02, 2014 250  u &= \sqrt{b+2} \, x / y \\  Niels Möller committed Jul 11, 2014 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) \\  Niels Möller committed Aug 23, 2014 258  y &= \sqrt{b+2} \, x / u  Niels Möller committed Jul 11, 2014 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$.  Niels Möller committed Aug 23, 2014 267   Niels Möller committed Aug 27, 2014 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}  Niels Möller committed Aug 23, 2014 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 committed Jul 11, 2014 317 318 319 320 321 322 \end{document} %%% Local Variables: %%% mode: latex %%% TeX-master: t %%% End: