Skip to content
doubtly

1 answer

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):

  1. Choose two large primes \(p\) and \(q\); compute \(n = p\,q\) and \(\phi(n) = (p-1)(q-1)\).
  2. Choose \(e\) with \(1 < e < \phi(n)\) and \(\gcd(e, \phi(n)) = 1\).
  3. Compute \(d\) such that \(e\,d \equiv 1 \pmod{\phi(n)}\).
  4. Public key \(= (e, n)\), private key \(= (d, n)\).

2. Signing (sender A):

  1. Compute the message digest \(h = H(M)\) using a hash function (e.g. SHA-256).
  2. Sign it with the private key: \(S = h^{d} \bmod n\).
  3. Send \((M, S)\) to receiver B.

3. Verification (receiver B):

  1. Compute \(h_1 = H(M)\) from the received message.
  2. Recover \(h_2 = S^{e} \bmod n\) using A's public key.
  3. 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\)).

Doubtly · 16 May 2024 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.