Ed25519 is a public-key digital signature cryptosystem proposed in 2011 by the team lead by Daniel J. Bernstein. It is a particular variant of EdDSA (Digital Signature Algorithm on twisted Edwards curves).
Ed25519 is quite fast due to a particular choice of the curve and avoids common pitfalls of previous elliptic curve-based cryptosystems, such as ECDSA, in particular boosting resistance to side-channel attacks. However, due to some peculiarities in Ed25519 construction, it’s not always easy to use it correctly for applications besides digital signatures, which are becoming increasingly popular with the advent of cryptocurrencies and popularization of applied cryptography in general.
Ed25519 uses an eponymous elliptic curve. For the sake of this discussion, it’s not necessary to have a deep understanding how elliptic curves are organized. It suffices to say that the curve consists of points, which form a finite abelian group. As per group definition, it is possible to operate on two group points resulting in a group point, and to multiply group by scalars (integers modulo a certain number), again resulting in a point.
A + B.A by the scalar x will be denoted as [x]A.The group has a distinguished identity point O, which plays a similar role
to zero in integer modulo groups: adding O to any point A results in A.
The Ed25519 elliptic curve has 8ℓ points, where the prime
ℓ = 2252 + 27742317777372353535851937790883648493
So, unlike some other elliptic curves (say, secp256k1 used in Bitcoin and Ethereum cryptocurrencies),
the elliptic curve is not a prime-order group itself. As per
basis theorem for finite abelian groups,
we can extract a prime-order subgroup by selecting a basepoint B
with order ℓ and using it as the group generator:
G = { O, B, [2]B, [3]B, … [ℓ - 1]B };
([ℓ]B = O by definition). For this reason, we will assume in further discussion that scalars
are integers modulo ℓ, rather than 8ℓ.
As some other signature schemes based on elliptic curves, Ed25519 is essentially the non-interactive version
of a proof of knowledge of a discrete logarithm.
In the original interactive form of the protocol, one proves that he knows
a scalar a corresponding to a certain group element A = [a]B
without revealing any information about a. The protocol goes as follows:
r.R := [r]B.h.s := r + h*a.[s]B == R + [h]A.Turns out that this protocol is complete (if the prover knows a, the verifier will be convinced
by the proof), sound (the prover cannot produce the necessary output if he doesn’t know a)
and zero-knowledge (the verifier doesn’t learn anything about a he didn’t know before the protocol
was initiated).
To convert this protocol into a digital signature scheme, we apply
the Fiat – Shamir heuristic:
the verifier is replaced with a cryptographic hash function Hash, which, when the verifier’s output
is requested, hashes all data sent so far by the prover together with the message M being signed.
In other words, h := Hash(R ‖ M), where ‖ denotes concatenation of bytes.
If the cryptographic hash function models
a random oracle,
the resulting scheme (known as Schnorr signature scheme)
is secure.
The Schnorr scheme for elliptic curves looks as follows:
B,
in which the discrete logarithm problem (finding scalar a given point [a]B)
is believed to be hard.a as the secret (aka signing) key.
Use A = [a]B as the public (verifying) key.r. Compute R := [r]B,
h := Hash(R ‖ M), and finally s := r + h*a. Output (R, s).A and signature (R, s),
verify [s]B == R + [Hash(R ‖ M)]A.