ecc-formulas.tex

\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*}
  y^2 = x^3 - 3x + b \pmod{p}
\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)$:
\begin{align*}
  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
\end{align*}

\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*}

\section{EdDSA}

The EdDSA paper (\url{http://ed25519.cr.yp.to/ed25519-20110926.pdf})
suggests using the twisted Edwards curve,
\begin{equation*}
  -x^2 + y^2 = 1 + d' x^2 y^2 \pmod{p}
\end{equation*}
(For this we use the same $d' = -d = (121665/121666) \bmod p$).
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
Edwards curve. The point addition formulas for the twisted Edwards
curve are
\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*}
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*}

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}).

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

\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*}
    u &= \sqrt{b+2} \, x / y \\
    v &= (x-1) / (x+1)
  \end{align*}
\end{itemize}

The inverse transformation is
\begin{align*}
  x &= (1+v) / (1-v) \\
  y &= \sqrt{b+2} \, x / u 
\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$.

\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}

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$.
\end{document}

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