From a3fb911ea645a5d4d0a624e1bcf4c788044dab85 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Niels=20M=C3=B6ller?= Date: Thu, 2 Oct 2014 15:55:41 +0200 Subject: [PATCH] Notes on EdDSA decompression. --- misc/ecc-formulas.tex | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) diff --git a/misc/ecc-formulas.tex b/misc/ecc-formulas.tex index d696ca50..6c61982d 100644 --- a/misc/ecc-formulas.tex +++ b/misc/ecc-formulas.tex @@ -181,7 +181,8 @@ 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$). +(For this we use $d' = -d$, with $d = (121665/121666) \bmod p$, where +$d$ is the same as in the curve25519 equivalence described below). 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 @@ -225,6 +226,18 @@ because they are complete. See In our notation $a = -1$, and the $d'$ above is $-d$. +\subsection{Decompression} + +For EdDSA, points are represented by the $y$ coordinate and only the +low bit, or ``sign'' bit, of the $x$ coordinate. Then $x^2$ can be +computed as +\begin{align*} + x^2 &= (1-y^2) (d y^2 - 1)^{-1} \\ + &= 121666 (1-y^2) (121665 y^2 - 121666)^{-1} +\end{align*} +We then get $x$ from a square root, and we can use a trick of djb's to +avoid the inversion. + \section{Curve25519} Curve25519 is defined as the Montgomery curve -- 2.47.2