# 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}+486662{x}^{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

Authors | Name | Date | Link |
---|---|---|---|

Daniel J Bernstein, Chitchanok Chuengsatiansup, Tanja Lange | “Curve41417: Karatsuba revisited” | 2014 | |

Daniel J Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang | “High-speed high-security signatures” | 2011 | |

Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson | “Twisted Edwards Curves Revisited” | 2008 | |

Daniel J Bernstein, Peter Birkner, Marc Joye, Tanja Lange, Christiane Peters | “Twisted Edwards Curves” | 2008 |

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}+{\mathrm{14DEF9DEA2F79CD65812631A5CF5D3ED}}_{16}\\ d=& -\frac{121665}{121666}\\ B=& (9,{\mathrm{20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9}}_{16})\end{array}$### Key pair generation

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

$\begin{array}{rl}{h}_{i}=& H\left(k\right)\hspace{0.17em}\forall 0\le i<2b\\ a=& {2}^{b-2}+\sum _{3\le i\le b-3}{2}^{i}{h}_{i}\\ A=& aB\end{array}$- The private key is given as $(a,{h}_{i})$
- 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({h}_{b},\dots ,{h}_{2b-1},M)\\ R=& rB\\ S=& \left(r+H(\underset{\xaf}{R},\underset{\xaf}{A},\underset{\xaf}{M})a\right)\phantom{\rule{10px}{0ex}}\mathrm{mod}l\\ \Rightarrow & (\underset{\xaf}{R},\underset{\xaf}{S})\end{array}$### Verifying

Accept $(\underset{\xaf}{R},\underset{\xaf}{S})$ if and only if

$8SB\stackrel{?}{=}8R+8H(\underset{\xaf}{R},\underset{\xaf}{A},\underset{\xaf}{M})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.

## Notes & resources

- An informal cheatsheet for Curve25519 and Ed25519
- My cheatsheet “Elliptic Curves, birational equivalence and EdDSA” featuring
- theoretical background
- additional test vectors
- sage and python source snippets

- A tool to simplify work with byte arrays
- A commented version of ed25519.py with example output
- Sagemath worksheets