How does RSA signing and verification work, and how does it relate to RSA encryption/decryption?
RSA signing uses the private key ($s = m^d \mod N$), verification uses the public key ($m' = s^e \mod N$, check if $m' = m$). It's the same math as encryption/decryption but with the roles of e and d reversed.
* Signing is "decrypt-then-verify" run backwards: private d creates the signature, public e checks it — the mirror image of encrypt/decrypt. *
Signing (Alice signs message m): $$s \equiv m^d \mod N$$
- Uses Alice's private key $d$
- Only Alice can create the signature (she alone knows $d$)
Verification (Bob verifies signature s): $$m' \equiv s^e \mod N$$
- Uses Alice's public key $(e, N)$
- Check: does $m' = m$? If yes → valid signature
The mathematical symmetry:
- Encryption: $c = m^e \mod N$ (public key) → Decryption: $m = c^d \mod N$ (private key)
- Signing: $s = m^d \mod N$ (private key) → Verification: $m = s^e \mod N$ (public key)
- Same operations, reversed order of exponents
In practice (hash-then-sign):
- Compute hash: $h = H(m)$
- Sign the hash: $s = h^d \mod N$
- Send both $(m, s)$
- Verifier computes $h' = H(m)$ and checks if $s^e \equiv h' \mod N$
Important: Use separate key pairs for signing and encryption! Using the same key for both creates security vulnerabilities.
Go deeper:
Digital signature (Wikipedia) — the general sign/verify model and its security goals.- RSA — signing (Wikipedia) — why raw RSA signatures need hashing and PSS padding.