Ed25519 Quirks

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.

Basic Definitions

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.

• We will refer the group operation as addition and denote it as such: A + B.
• Multiplication of a point 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

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:

([ℓ]B = O by definition). For this reason, we will assume in further discussion that scalars are integers modulo ℓ, rather than 8ℓ.

Schnorr Signature Scheme

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:

1. Prover: Choose a random scalar r.
2. Prover → Verifier: Send R := [r]B.
3. Verifier → Prover: Choose and send a random scalar h.
4. Prover → Verifier: Compute and send s := r + h*a.
5. Verifier: Verify that [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:

• Public parameters: A prime-order group on an elliptic curve with the basepoint B, in which the discrete logarithm problem (finding scalar a given point [a]B) is believed to be hard.
• Key generation: Select random scalar a as the secret (aka signing) key. Use A = [a]B as the public (verifying) key.
• Signing: Select random scalar r. Compute R := [r]B, h := Hash(R ‖ M), and finally s := r + h*a. Output (R, s).
• Verification: Given the public key A and signature (R, s), verify [s]B == R + [Hash(R ‖ M)]A.