Public-Key Cryptography · Authentication

ElGamalDigital Signature Scheme

Sign a message with your private key, let anyone verify it with your public key. Learn it, compute it, and test yourself — all here.

The core idea

What does a digital signature do?

A digital signature proves who sent a message and that it wasn't tampered with. It is the mirror image of encryption: you sign with your private key, and anyone can verify with your public key.

ElGamal signatures (Taher ElGamal, 1985) are built on the same hard problem as Diffie–Hellman: the discrete logarithm problem. The scheme is the ancestor of the modern DSA standard.

Private key — sign with this

Secret. Only the owner can produce a valid signature.

Public key — verify with this

(p, g, y)

Published. Anyone can check a signature, nobody can forge one.

Encryption vs. signing — don't confuse them

	Encryption	Signature
Goal	secrecy	authenticity + integrity
Sender uses	recipient's public key	own private key
Receiver uses	own private key	sender's public key
Output	ciphertext	signature (r, s)

In signing, the message itself is usually sent in the clear — the signature travels alongside it as a proof of origin.

Why it's secure — the discrete log trapdoor

Given g, p and y = gˣ mod p, it is easy to compute y but believed infeasible to recover the exponent x (the discrete logarithm) when p is large. Without x, an attacker cannot construct the value s that makes the verification equation balance.

Key vocabulary

p — a large prime; all arithmetic is modulo p.
g — a generator (primitive root) modulo p.
x — the private key, a secret integer with 1 < x < p−1.
y — the public key, y = gˣ mod p.
k — the ephemeral key: a fresh random number per signature, with gcd(k, p−1) = 1.
(r, s) — the signature pair attached to the message m.

The lifecycle at a glance

1 · Key generation — pick p, g, secret x → publish y = gˣ mod p.
2 · Sign — pick fresh k → compute r = gᵏ mod p and s = (m − x·r)·k⁻¹ mod (p−1).
3 · Send — transmit message m together with signature (r, s).
4 · Verify — accept iff gᵐ ≡ yʳ · rˢ (mod p).

Formulas & theory

Everything you must memorise

Step 1 — Key generation

choose prime p and generator g (1 < g < p)g should be a primitive root modulo p.

choose private key x, 1 < x < p − 1Kept secret.

public key y = g^x mod pPublished as the triple (p, g, y).

Step 2 — Signing message m

choose random k with gcd(k, p − 1) = 1The ephemeral key — must be fresh and secret for every signature.

r = g^k mod pFirst component of the signature.

s = (m − x·r) · k⁻¹ mod (p − 1)k⁻¹ is the inverse of k modulo (p−1). If s = 0, pick a new k. Signature = (r, s).

Step 3 — Verification

accept ⟺ g^m ≡ y^r · r^s (mod p)Also requires 0 < r < p and 0 < s < p−1.

Why verification works

From the signing equation, s·k ≡ m − x·r (mod p−1), so m ≡ x·r + k·s (mod p−1). By Fermat's little theorem, exponents of g can be taken modulo p−1, therefore:

g^m = g^{x·r + k·s} = (g^x)^r · (g^k)^s = y^r · r^s (mod p)The two sides match exactly for a genuine signature.

Quick-reference table

Symbol	Role	Computed as	Secret?
p, g	domain params	chosen	public
x	private key	chosen	secret
y	public key	gˣ mod p	public
k	ephemeral key	random, gcd(k,p−1)=1	secret
r	signature part 1	gᵏ mod p	public
s	signature part 2	(m−x·r)·k⁻¹ mod(p−1)	public

Critical pitfalls (exam favourites)

The signing exponent arithmetic is modulo (p − 1), but r, y, g operations are modulo p. Mixing these up is the #1 error.
Never reuse k. Two signatures with the same k let an attacker solve for the private key x.
k must be coprime to p − 1, otherwise k⁻¹ mod (p−1) doesn't exist.

Live signature calculator

Type values — sign and verify recompute instantly

p (prime)

g (generator)

x (private key)

m (message / hash)

k — ephemeral key, gcd(k, p−1) = 1

A full worked example

Small numbers so you can follow every step by hand

Sign the message m = 7 with prime p = 23, generator g = 5, private key x = 6, and ephemeral key k = 3.

📄

Message

m = 7

🖋️sign with x, k

🔏

Signature

(r, s) = (10, 19)

🔍verify with y

✅

Result

17 = 17 ✓

Key generation

① Domain parameters

p = 23, g = 5 (a primitive root mod 23)

② Private key

x = 6

③ Public key

y = gˣ mod p = 5⁶ mod 23 = 8

5²=2, 5⁴=4, 5⁶ = 4·2 = 8 (mod 23). Publish (p, g, y) = (23, 5, 8).

Signing

④ Pick ephemeral k

k = 3, gcd(3, 22) = 1 ✓

p − 1 = 22, and 3 is coprime to 22, so k is valid.

⑤ Compute r

r = gᵏ mod p = 5³ mod 23 = 125 mod 23 = 10

⑥ Inverse of k mod (p−1)

k⁻¹ = 3⁻¹ mod 22 = 15

Check: 3 × 15 = 45 = 44 + 1 ≡ 1 (mod 22) ✓

⑦ Compute s

s = (m − x·r)·k⁻¹ mod (p−1)
= (7 − 6·10)·15 mod 22 = (−53)·15 mod 22

−53 ≡ 13 (mod 22), then 13 × 15 = 195 ≡ 19 (mod 22). So s = 19.

Public key

(p, g, y) = (23, 5, 8)

Signature on m=7

(r, s) = (10, 19)

Verification

⑧ Left side

v₁ = gᵐ mod p = 5⁷ mod 23 = 17

⑨ Right side

v₂ = yʳ · rˢ mod p = 8¹⁰ · 10¹⁹ mod 23 = 3 · 21 = 63 mod 23 = 17

⑩ Compare

v₁ = v₂ = 17 → signature VALID ✓

Both sides match, so the verifier accepts the signature as authentic.

Try changing any single value (say m = 8) in the Calculator tab — verification will fail, showing how the signature binds to the exact message.

Test yourself

6 questions · instant feedback · explanations

Score

0 / 6

Answer the questions to see how you're doing.