EdDSA

Summary

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

An EdDSA signature scheme is a choice

of finite field F q over odd prime power q ,

of elliptic curve E ( F q ) over F q ,

of base point B ∈ E ( F q ) with order ℓ and cofactor 2 c so that the order of the curve is # E ( F q ) = 2 c ℓ , and

of target-collision-resistant hash function H with 2 b -bit outputs, where 2 b − 1 > q so that elements of F q and curve points in E ( F q ) can be represented by strings of 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—for example, Pollard's rho algorithm for logarithms is expected to take approximately ℓ π / 4 curve additions before it can compute a discrete logarithm, so ℓ must be large enough for this to be infeasible, and is typically taken to exceed 2²⁰⁰.

Within an EdDSA signature scheme,

Public key

An EdDSA public key is a curve point A ∈ E ( F q ) , encoded in b bits.

Signature

An EdDSA signature on a message M by public key A is the pair ( R , S ) , encoded in 2 b bits, of a curve point R ∈ E ( F q ) and an integer 0 < S < ℓ satisfying the verification equation

Private key

An EdDSA private key is a b -bit string k which should be chosen uniformly at random. The corresponding public key is A = s B , where s = H 0 , … , b − 1 ( k ) is the least significant b bits of H ( k ) interpreted as an integer in little-endian. The signature on a message M is ( R , S ) where R = r B for r = H b , … , 2 b − 1 ( k , M ) , and This clearly satisfies the verification equation:

Ed25519

Ed25519 is the EdDSA signature scheme where

q = 2 255 − 19 ,

E ( F q ) is the Twisted Edwards curve

B is the unique point in E ( F q ) whose y coordinate is 4 / 5 and whose x coordinate is positive, and

H is SHA-512, with b = 256 .

The curve E ( F q ) is birationally equivalent to the Montgomery curve known as Curve25519. The equivalence is

Performance

The Bernstein team has optimized Ed25519 for the x86-64 Nehalem/Westmere processor family. Verification can be performed in batches of 64 signatures for even greater throughput. Ed25519 is intended to provide attack resistance comparable to quality 128-bit symmetric ciphers. Public keys are 256 bits in length and signatures are twice that size.

Secure coding

As security features, Ed25519 does not use branch operations and array indexing steps that depend on secret data, so as to defeat many side channel attacks.

Like other discrete-log-based signature schemes, EdDSA uses a secret value called a nonce unique to each signature. In the signature schemes DSA and ECDSA, this nonce is traditionally generated randomly for each signature—and if the random number generator is ever broken and predictable when making a signature, the signature can leak the private key, as happened with the Sony PlayStation 3 firmware update signing key. In contrast, EdDSA chooses the nonce deterministically as the hash of the private key and the message. Thus, once a private key is generated, EdDSA has no further need for a random number generator in order to make signatures, and there is no danger that a broken random number generator used to make a signature will reveal the private key.

Software

Notable uses of Ed25519 include OpenSSH, GnuPG and various alternatives, and the signify tool by OpenBSD.

SUPERCOP reference implementation (C language with inline assembler)

A slow but concise alternate implementation, does not include side-channel attack protection (Python)

NaCl

CryptoNote cryptocurrency protocol

wolfSSL

Libsodium

I2Pd has its own implementation of EdDSA

Minisign and Minisign Miscellanea for macOS

Virgil PKI uses ed25519 keys by default