EdDSA

The following is a simplified description of EdDSA, ignoring details of encoding integers and curve points as bit strings; the full details are in the papers and RFC.[4][2][1]

An EdDSA signature scheme is a choice:[4]^: 1–2[2]^: 5–6[1]^: 5–7

• of finite field ${\displaystyle \mathbb {F} _{q}}$ over odd prime power ${\displaystyle q}$;
• of elliptic curve ${\displaystyle E}$ over ${\displaystyle \mathbb {F} _{q}}$ whose group ${\displaystyle E(\mathbb {F} _{q})}$ of ${\displaystyle \mathbb {F} _{q}}$-rational points has order ${\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }$, where ${\displaystyle \ell }$ is a large prime and ${\displaystyle 2^{c}}$ is called the cofactor;
• of base point ${\displaystyle B\in E(\mathbb {F} _{q})}$ with order ${\displaystyle \ell }$; and
• of cryptographic hash function ${\displaystyle H}$ with ${\displaystyle 2b}$-bit outputs, where ${\displaystyle 2^{b-1}>q}$ so that elements of ${\displaystyle \mathbb {F} _{q}}$ and curve points in ${\displaystyle E(\mathbb {F} _{q})}$ can be represented by strings of ${\displaystyle b}$ bits.

These parameters are common to all users of the EdDSA signature scheme. The security of the EdDSA signature scheme depends critically on the choices of parameters, except for the arbitrary choice of base point—for example, Pollard's rho algorithm for logarithms is expected to take approximately ${\displaystyle {\sqrt {\ell \pi /4}}}$ curve additions before it can compute a discrete logarithm,[5] so ${\displaystyle \ell }$ must be large enough for this to be infeasible, and is typically taken to exceed 2²⁰⁰.[6] The choice of ${\displaystyle \ell }$ is limited by the choice of ${\displaystyle q}$, since by Hasse's theorem, ${\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }$ cannot differ from ${\displaystyle q+1}$ by more than ${\displaystyle 2{\sqrt {q}}}$. The hash function ${\displaystyle H}$ is normally modelled as a random oracle in formal analyses of EdDSA's security.

Within an EdDSA signature scheme,

Public key

An EdDSA public key is a curve point ${\displaystyle A\in E(\mathbb {F} _{q})}$, encoded in ${\displaystyle b}$ bits.

Signature

An EdDSA signature on a message ${\displaystyle M}$ by public key ${\displaystyle A}$ is the pair ${\displaystyle (R,S)}$, encoded in ${\displaystyle 2b}$ bits, of a curve point ${\displaystyle R\in E(\mathbb {F} _{q})}$ and an integer ${\displaystyle 0<S<\ell }$ satisfying the following verification equation. ${\displaystyle \parallel }$ denotes concatenation.

$${\displaystyle 2^{c}SB=2^{c}R+2^{c}H(R\parallel A\parallel M)A}$$

Private key

An EdDSA private key is a ${\displaystyle b}$-bit string ${\displaystyle k}$ which should be chosen uniformly at random. The corresponding public key is ${\displaystyle A=sB}$, where ${\displaystyle s=H_{0,\dots ,b-1}(k)}$ is the least significant ${\displaystyle b}$ bits of ${\displaystyle H(k)}$ interpreted as an integer in little-endian. The signature on a message ${\displaystyle M}$ is ${\displaystyle (R,S)}$ where ${\displaystyle R=rB}$ for ${\displaystyle r=H(H_{b,\dots ,2b-1}(k)\parallel M)}$, and

$${\displaystyle S\equiv r+H(R\parallel A\parallel M)s{\pmod {\ell }}.}$$

This satisfies the verification equation:

$${\displaystyle {\begin{aligned}2^{c}SB&=2^{c}(r+H(R\parallel A\parallel M)s)B\\&=2^{c}rB+2^{c}H(R\parallel A\parallel M)sB\\&=2^{c}R+2^{c}H(R\parallel A\parallel M)A.\end{aligned}}}$$

Ed25519 is the EdDSA signature scheme using SHA-512 (SHA-2) and Curve25519[2] where

• ${\displaystyle q=2^{255}-19,}$
• ${\displaystyle E/\mathbb {F} _{q}}$ is the twisted Edwards curve

$${\displaystyle -x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},}$$

• ${\displaystyle \ell =2^{252}+27742317777372353535851937790883648493}$ and ${\displaystyle c=3}$
• ${\displaystyle B}$ is the unique point in ${\displaystyle E(\mathbb {F} _{q})}$ whose ${\displaystyle y}$ coordinate is ${\displaystyle 4/5}$ and whose ${\displaystyle x}$ coordinate is positive.
  "positive" is defined in terms of bit-encoding:
  • "positive" coordinates are even coordinates (least significant bit is cleared)
  • "negative" coordinates are odd coordinates (least significant bit is set)
• ${\displaystyle H}$ is SHA-512, with ${\displaystyle b=256}$.

The curve ${\displaystyle E(\mathbb {F} _{q})}$ is birationally equivalent to the Montgomery curve known as Curve25519. The equivalence is[2][7]

$${\displaystyle x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.}$$

Ed448 is the EdDSA signature scheme using SHAKE256 and Curve448 defined in RFC 8032. It has also been approved in the final version the FIPS 186-5 standard.[13]

• Public-key cryptography

• Ed25519 home page