crypto-snippets/ed25519
Edwards-curve Digital Signature Algorithm
\(\gdef\system{\mathsf{Sig}}\) \(\gdef\systemprefix{}\) \(\gdef\keygen{\mathsf{\systemprefix{}KGen}}\) \(\gdef\sign{\mathsf{\systemprefix{}Sign}}\) \(\gdef\verify{\mathsf{\systemprefix{}Verify}}\) \(\gdef\hash{\mathsf{Hash}}\) \(\gdef\msgspace{\mathcal{M}}\) \(\gdef\group{\mathbb{G}}\) \(\gdef\generator{G}\) \(\gdef\modulo{q}\)
EdDSA is based on Schnorr Signature Scheme but produces deterministic signatures, i.e., for the same secret key and message, it produces the same signature every time. It is an instantiation of the EdDSA signature scheme using the Edwards25519 curve, which is a twisted Edwards curve based on Curve25519.
\(\keygen(1^n) \to (pk, sk)\)
- Random scalar \(x\)
- \(h := \hash(x)\)
- \(k_{sign} := h[:32]\)
- \(Y := k_{sign} \cdot \generator{}\)
- Output \((pk := Y, sk := x)\)
\(\sign(sk, m) \to \sigma\)
- \(h := \hash(x)\)
- \(k_{sign} := h[:32]\)
- \(k_{nonce} := h[32:]\)
- \(r := \hash(h[32:] \| m)\)
- \(R := r \generator\)
- \(s=r+(\hash(R \| Y \| m)) \cdot k_{sign}\)
- Output \(\sigma := (R, s)\)
\(\verify(pk, m, \sigma) \to \{0,1\}\)
- Parse \((R,s) := \sigma \quad Y:= pk\)
- \(S \gets \hash(R \|Y \| m)\)
- \(v_1 := s \generator{}\)
- \(v_2 := R + Y \cdot S\)
- Ouput \(v_1 \stackrel{?}{=} v_2\)
Last modified June 13, 2025, 4:56 a.m.