Answer: In the RSA digital signature scheme the sender signs (a hash of) the message with his private key, \(S = H(M)^d \bmod n\), and anyone verifies it with the sender's public key by checking \(S^e \bmod n = H(M)\). This gives authentication, integrity and non-repudiation.
Digital signature: an electronic value attached to a message that proves who sent it and that it has not been altered on the way.
1. Key generation (by sender A):
- Choose two large primes \(p\) and \(q\); compute \(n = p\,q\) and \(\phi(n) = (p-1)(q-1)\).
- Choose \(e\) with \(1 < e < \phi(n)\) and \(\gcd(e, \phi(n)) = 1\).
- Compute \(d\) such that \(e\,d \equiv 1 \pmod{\phi(n)}\).
- Public key \(= (e, n)\), private key \(= (d, n)\).
2. Signing (sender A):
- Compute the message digest \(h = H(M)\) using a hash function (e.g. SHA-256).
- Sign it with the private key: \(S = h^{d} \bmod n\).
- Send \((M, S)\) to receiver B.
3. Verification (receiver B):
- Compute \(h_1 = H(M)\) from the received message.
- Recover \(h_2 = S^{e} \bmod n\) using A's public key.
- If \(h_1 = h_2\), the signature is valid: the message came from A and was not modified. Otherwise reject it.
Diagram (in words): Sender side: Message → Hash → Digest → "Encrypt with A's private key" → Signature; Message + Signature are sent. Receiver side: Message → Hash → Digest 1; Signature → "Decrypt with A's public key" → Digest 2; Compare Digest 1 and Digest 2 → accept / reject.
Small numerical example (hash value taken as 5): \(p = 5,\ q = 11,\ n = 55,\ \phi(n) = 40,\ e = 3,\ d = 27\) (since \(3\times27 = 81 \equiv 1 \pmod{40}\)).
Sign: \(S = 5^{27} \bmod 55 = 25\).
Verify: \(S^{e} \bmod n = 25^{3} \bmod 55 = 15625 \bmod 55 = 5\) (since \(55\times284 = 15620\)), which equals the hash value 5, so the signature is valid.
Security: forging a signature needs \(d\), which requires factoring the large \(n\) into \(p\) and \(q\); this is infeasible for 2048-bit keys. Signing the hash (not the whole message) keeps the signature short and fast.
Services provided: authentication of the sender, integrity of the message and non-repudiation (A cannot later deny signing, because only A has \(d\)).