# EdDSA and Ed25519

**EdDSA** (Edwards-curve Digital Signature Algorithm) is a modern and secure digital signature algorithm based on performance-optimized elliptic curves, such as the 255-bit curve [**Curve25519**](https://en.wikipedia.org/wiki/Curve25519) and the 448-bit curve [**Curve448-Goldilocks**](https://en.wikipedia.org/wiki/Curve448). The EdDSA signatures use the **Edwards form** of the elliptic curves (for performance reasons), respectively `edwards25519` and `edwards448`. The **EdDSA** algorithm is based on the [**Schnorr signature algorithm**](https://en.wikipedia.org/wiki/Schnorr_signature) and relies on the difficulty of the **ECDLP problem**.

The **EdDSA** signature algorithm and its variants **Ed25519** and **Ed448** are technically described in the [RFC 8032](https://tools.ietf.org/html/rfc8032).

## EdDSA Key Generation

**Ed25519** and **Ed448** use small **private keys** (32 or 57 bytes respectively), small **public keys** (32 or 57 bytes) and **small signatures** (64 or 114 bytes) with **high security level** at the same time (128-bit or 224-bit respectively).

Assume the elliptic curve for the EdDSA algorithm comes with a generator point **G** and a subgroup order ***q*** for the EC points, generated from **G**.

The **EdDSA key-pair** consists of:

* **private key** (integer): ***privKey***
* **public key** (EC point): ***pubKey*** = ***privKey*** \* **G**

The **private key** is generated from a **random integer**, known as ***seed*** (which should have similar bit length, like the curve order). The ***seed*** is first hashed, then the last few bits, corresponding to the curve **cofactor** (8 for Ed25519 and 4 for X448) are cleared, then the highest bit is cleared and the second highest bit is set. These transformations guarantee that the private key will always belong to the same subgroup of EC points on the curve and that the private keys will always have similar bit length (to protect from timing-based side-channel attacks). For **Ed25519** the private key is 32 bytes. For **Ed448** the private key is 57 bytes.

The public key ***pubKey*** is a point on the elliptic curve, calculated by the EC point multiplication: ***pubKey*** = ***privKey*** \* **G** (the private key, multiplied by the generator point **G** for the curve). The public key is encoded as **compressed** EC point: the **y**-coordinate, combined with the lowest bit (the parity) of the **x**-coordinate. For **Ed25519** the public key is 32 bytes. For **Ed448** the public key is 57 bytes.

## EdDSA Sign

The **EdDSA signing** algorithm ([RFC 8032](https://tools.ietf.org/html/rfc8032#page-13)) takes as input a text message ***msg*** + the signer's EdDSA **private key** ***privKey*** and produces as output a pair of integers {***R***, ***s***}. EdDSA signing works as follows (with minor simplifications):

`EdDSA_sign(msg, privKey) --> { R, s }`

1. Calculate ***pubKey*** = ***privKey*** \* **G**
2. Deterministically generate a secret integer ***r*** = hash(hash(***privKey***) + ***msg***) mod ***q*** (this is a bit simplified)
3. Calculate the public key point behind ***r*** by multiplying it by the curve generator: ***R*** = ***r*** \* **G**
4. Calculate ***h*** = hash(***R*** + ***pubKey*** + ***msg***) mod ***q***
5. Calculate ***s*** = (***r*** + ***h*** \* ***privKey***) mod ***q***
6. Return the **signature** { ***R***, ***s*** }

The produced **digital signature** is 64 bytes (32 + 32 bytes) for **Ed25519** and 114 bytes (57 + 57 bytes) for **Ed448**. It holds a compressed point ***R*** + the integer ***s*** (confirming that the signer knows the ***msg*** and the ***privKey***).

## EdDSA Verify Signature

The **EdDSA signature verification** algorithm ([RFC 8032](https://tools.ietf.org/html/rfc8032#page-13)) takes as input a text message ***msg*** + the signer's EdDSA **public key** ***pubKey*** + the EdDSA signature {***R***, ***s***} and produces as output a boolean value (valid or invalid signature). EdDSA verification works as follows (with minor simplifications):

`EdDSA_signature_verify(msg, pubKey, signature { R, s } ) --> valid / invalid`

1. Calculate ***h*** = hash(***R*** + ***pubKey*** + ***msg***) mod ***q***
2. Calculate ***P1*** = ***s*** \* **G**
3. Calculate ***P2*** = ***R*** + ***h*** \* ***pubKey***
4. Return ***P1*** == ***P2***

## How Does it Work? <a href="#how-does-it-work" id="how-does-it-work"></a>

During the verification the point ***P1*** is calculated as: ***P1*** = ***s*** \* **G**.

During the signing ***s*** = (***r*** + ***h*** \* ***privKey***) mod ***q***. Now replace ***s*** in the above equation:

* ***P1*** = ***s*** \* **G =** (***r*** + ***h*** \* ***privKey***) mod ***q*** \* **G** = ***r*** \* **G** + ***h*** \* ***privKey*** \* **G** = ***R*** + ***h*** \* ***pubKey***

The above is exactly the other point ***P2***. If these points ***P1*** and ***P2*** are the same EC point, this proves that the point ***P1***, calculated by the private key matches the point ***P2***, created by its corresponding public key.

## ECDSA vs EdDSA

If we compare the signing and verification for EdDSA, we shall find that **EdDSA is simpler than ECDSA**, easier to understand and to implement. Both signature algorithms have **similar security strength** for curves with similar key lengths. For the most popular curves (liked `edwards25519` and `edwards448`) the **EdDSA algorithm is slightly faster than ECDSA**, but this highly depends on the curves used and on the certain implementation. Unlike ECDSA the EdDSA signatures do not provide a way to **recover the signer's public key** from the signature and the message. Generally, it is considered that EdDSA is recommended for most modern apps.