ecc-formulas.tex 7.41 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 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 committed Aug 27, 2014 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*}  Niels Möller committed Aug 28, 2014 113  -x^2 + y^2 = 1 + d' x^2 y^2 \pmod{p}  Niels Möller committed Aug 27, 2014 114 \end{equation*}  Niels Möller committed Aug 28, 2014 115 (For this we use the same $d' = -d = (121665/121666) \bmod p$).  Niels Möller committed Aug 27, 2014 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  Niels Möller committed Aug 28, 2014 118 Edwards curve. The point addition formulas for the twisted Edwards  Niels Möller committed Aug 27, 2014 119 120 curve are \begin{align*}  Niels Möller committed Aug 28, 2014 121  t &= d' x_1 x_2 y_1 y_2 \\  Niels Möller committed Aug 27, 2014 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*}  Niels Möller committed Aug 28, 2014 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 committed Aug 27, 2014 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}).  Niels Möller committed Aug 28, 2014 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 committed Jul 11, 2014 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*}  Niels Möller committed Aug 02, 2014 181  u &= \sqrt{b+2} \, x / y \\  Niels Möller committed Jul 11, 2014 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) \\  Niels Möller committed Aug 23, 2014 189  y &= \sqrt{b+2} \, x / u  Niels Möller committed Jul 11, 2014 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$.  Niels Möller committed Aug 23, 2014 198   Niels Möller committed Aug 27, 2014 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}  Niels Möller committed Aug 23, 2014 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 committed Jul 11, 2014 248 249 250 251 252 253 \end{document} %%% Local Variables: %%% mode: latex %%% TeX-master: t %%% End: