# EdDSA notes

## Background

In 2014/2015 I implemented Ed25519-SHA-512 for a commercial software. I want to share notes with you, I took during the implementation. It might help you to implement EdDSA/Curve25519 yourself.

## Software using Curve25519

See the wonderful list by ianix.com.

## Terminology

EdDSA
A digital signature scheme (DSA) using Edwards curves (Ed). The specific curve and hash algorithm to use is unspecified.
Curve25519
The Montgomery curve $y^2 = x^3 + 486662x^2 + x$
Ed25519
EdDSA using the Twisted Edwards curve $-{x}^{2}+{y}^{2}=1-\frac{121665}{121666}{x}^{2}{y}^{2}$ which is birationally equivalent to Curve25519
Ed25519-SHA-512
Ed25519 with the hash algorithm SHA-512

## Relevant papers

Daniel J Bernstein, Chitchanok Chuengsatiansup, Tanja Lange “Curve41417: Karatsuba revisited” 2014 PDF
Daniel J Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang “High-speed high-security signatures” 2011 PDF
Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson “Twisted Edwards Curves Revisited” 2008 PDF
Daniel J Bernstein, Peter Birkner, Marc Joye, Tanja Lange, Christiane Peters “Twisted Edwards Curves” 2008 PDF

The 2014 paper is not relevant for EdDSA, but listed here, because EdDSA is mostly implemented because of its performance. This paper introduces an even faster Curve41417 (formerly known as Curve3617).

## The protocol itself

This digital signature scheme is defined in the 2011 paper.

### DSA parameters

$\begin{array}{rl}b=& 256\\ H=& \text{SHA-512 with 2b-bit output}\\ q=& {2}^{255}-19\\ l=& {2}^{252}+{14DEF9DEA2F79CD65812631A5CF5D3ED}_{16}\\ d=& -\frac{121665}{121666}\\ B=& \left(9,{20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9}_{16}\right)\end{array}$

### Key pair generation

Given $b$ random bytes $k$, we initialize:

$\begin{array}{rl}{h}_{i}=& H\left(k\right) \forall 0\le i<2b\\ a=& {2}^{b-2}+\sum _{3\le i\le b-3}{2}^{i}{h}_{i}\\ A=& aB\end{array}$
1. The private key is given as $\left(a,{h}_{i}\right)$
2. The public key is given as $\left(A\right)$

### Signing

Given a message $M$ as sequence of bytes. Let underline denote the little-endian $b$-bit encoding of a point meaning that index $0$ contains the LSB of the y-coordinate and index $b-1$ contains the MSB of y, but set the highest bit if and only if the lower bit of x is set.

$\begin{array}{rl}r=& H\left({h}_{b},\dots ,{h}_{2b-1},M\right)\\ R=& rB\\ S=& \left(r+H\left(\underset{¯}{R},\underset{¯}{A},\underset{¯}{M}\right)a\right)\phantom{\rule{10px}{0ex}}\mathrm{mod}l\\ ⇒& \left(\underset{¯}{R},\underset{¯}{S}\right)\end{array}$

### Verifying

Accept $\left(\underset{¯}{R},\underset{¯}{S}\right)$ if and only if

$8SB\stackrel{?}{=}8R+8H\left(\underset{¯}{R},\underset{¯}{A},\underset{¯}{M}\right)A$

### Remark

If you are still wondering about the steps, this Ed25519 article by Brian Warner should give you a good start for your implementation.