Ed25519 Signature Algorithm: A Detailed Explanation

Introduction

Ed25519 is a modern, high-security, and efficient digital signature algorithm based on Edwards-curve Digital Signature Algorithm (EdDSA), using the twisted Edwards curve Curve25519. It is widely used due to its fast signing, fast verification, and resistance to side-channel attacks.

Key Components

• Curve25519: An elliptic curve defined over a finite field.

• SHA-512: A cryptographic hash function used for hashing keys and messages.

• Clamping: A process that ensures certain properties of private keys to improve security.

Key Generation

Ed25519 generates a key pair (public key, private key) as follows:

1. Generate a 32-byte random seed: Let this be $sk$.

2. Derive a 64-byte private key:

   • Compute the SHA-512 hash of $sk$: $h=\text{SHA-512}(sk)$

   • Split $h$ into two 32-byte halves: ($h_L$, $h_R$)

   • Modify $h_L$ (clamping):

     • Set the first 3 bits to zero: Ensures small subgroup attacks are avoided.
     • Set the second-most significant bit: Ensures group order is prime.

3. Compute the public key:

   • Interpret $h_L$ as an integer and multiply it by the generator point G: $P=h_L\cdot G$
   • The point P on the curve is actually represented as X and Y coordinates (32 bytes each). Many times, the Y cordinate is discarded and public key is just the X coordinate.

Signature Generation

Given a message $M$, and the two halves $h_L\text{ and }{h}_R$ derived from private key, the signature is computed as follows:

1. Compute the nonce:

   • Compute: r $r=\text{SHA-512}(h_R||M)\mathrm{mod}q$
   • Compute the nonce point R: $R=r\cdot G$
   • Here also, only X coordinate of R is considered toverify.

2. Compute the challenge hash:

   • Concatenate $R$, $P$, and $M$: $k=\text{SHA-512}(R||P||M)\mathrm{mod}q$

3. Compute the final signature value:

   • Compute: $S=(r+k\cdot h_L)\mathrm{mod}q$
   • The signature is concatenated R and S, i.e. (R, S). Its length is 64 bytes toverify .

Signature Verification

Given a public key $P$, a message $M$, and a signature $(R,S)$, the verification process is:

1. Compute the challenge hash:

   • Compute k: $k=\text{SHA-512}(R||P||M)\mathrm{mod}q$

2. Verify the signature equation:

   • Check if: $S\cdot G=R+k\cdot P$
   • If true, the signature is valid; otherwise, it is invalid.
   • Why does this work?$\begin{array}{rl}S\cdot G& =(r+k\cdot sk)\cdot G\\ & \\ & =r\cdot G+k\cdot sk\cdot G\\ & \\ & =R+k\cdot P\end{array}$

Security Features

• Fast & Efficient: Uses small, constant-time operations, making it resistant to timing attacks.

• Collision Resistance: Uses SHA-512 to hash inputs.

• No Side-Channel Leaks: Protects against branch prediction & cache timing attacks.

• Deterministic Signatures: Prevents nonce reuse attacks.