Cryptography and computer security - Tutorial 22.12.2020

Digital signatures

"Textbook" RSA signature

• Key generation: same as for RSA encryption
• Signing: \(\sigma = m^d \bmod{n}\)
• Verifying: \(m \stackrel{?}{\equiv} \sigma^e \pmod{n}\)

ElGamal signature

• Key generation:

  • Choose a large prime \(p\) and \(\alpha \in \mathbb{Z}_p^*\) such that \(\langle \alpha \rangle = \mathbb{Z}_p^*\)
  • Choose the private key \(a \stackrel{R}{\in} \mathbb{Z}_{p-1} \setminus \lbrace 0 \rbrace\)
  • Compute \(\beta = \alpha^a \bmod{p}\)
  • Publish \((p, \alpha, \beta)\) as the public key

• Signing \(m \in \mathbb{Z}_{p-1}\):

  • Choose \(k \stackrel{R}{\in} \mathbb{Z}_{p-1} \setminus \lbrace 0 \rbrace\)
  • Compute \(\gamma = \alpha^k \bmod{p}\) and \(\delta = (m - a \gamma) k^{-1} \bmod{(p-1)}\)
  • If \(\gamma \equiv 0 \pmod{p-1}\) or \(\delta = 0\), start over by choosing a new \(k\)
  • The signature is \(\sigma = (\gamma, \delta)\)

• Verifying a signature \(\sigma = (\gamma, \delta) \in \mathbb{Z}_p^*\)\({}\times \mathbb{Z}_{p-1}\) of a message \(m \in \mathbb{Z}_{p-1}\):

  • Check that \(\alpha^m \equiv \beta^\gamma \gamma^\delta \pmod{p}\)

DSA signature

• Key generation:

  • Choose a 1024-bit prime \(p\) and \(\alpha \in \mathbb{Z}_p^*\) of order \(q\) a 160-bit prime
  • Choose the private key \(a \stackrel{R}{\in} \mathbb{Z}_q \setminus \lbrace 0 \rbrace\)
  • Compute \(\beta = \alpha^a \bmod{p}\)
  • Publish \((p, q, \alpha, \beta)\) as the public key

• Signing \(m \in \mathbb{Z}_q\):

  • Choose \(k \stackrel{R}{\in} \mathbb{Z}_q \setminus \lbrace 0 \rbrace\)
  • Compute \(\gamma = (\alpha^k \bmod{p}) \bmod{q}\) and \(\delta = (m + a \gamma) k^{-1} \bmod{q}\)
  • If \(\gamma = 0\) or \(\delta = 0\), start over by choosing a new \(k\)
  • The signature is \(\sigma = (\gamma, \delta)\)

• Verifying a signature \(\sigma = (\gamma, \delta) \in (\mathbb{Z}_q)^*\) of a message \(m \in \mathbb{Z}_q\):

  • Verify that \(\gamma, \delta \ne 0\)
  • Compute \(\theta = \delta^{-1} \bmod{q}\)
  • Check that \(((\alpha^m \beta^\gamma)^\theta \bmod{p}) \bmod{q} = \gamma\)

Attacks on digital signatures

• Universal forgery: an adversary can forge a valid signature \(\sigma\) for any given message \(m\).
• Selective forgery: an adversary can forge a valid signature \(\sigma\) for a message \(m\) chosen by a challenger.
• Existential forgery: an adversary can forge a valid message-signature pair \((m, \sigma)\) which had not been previously produced by a legitimate signer.

Attack models

• Key-only attack: the adversary only has access to the public key.
• Known-message attack: the adversary has access to a number of valid message-signature pairs \((m_i, \sigma_i)\).
• Chosen-message attack: the attacker can obtain valid signatures \(\sigma_i\) for messages \(m_i\) of his own choice.

Exercise 1

Show that the textbook RSA signature scheme is existentially forgeable under a key-only attack and a known-message attack, and universally forgeable under a chosen-message attack. Describe the easiest way to prevent these attacks.

• Existential forgery under a key-only attack:
  • the adversary knows \(n, e\)
  • cho ose \(\sigma \in \mathbb{Z}_n\)
  • compute \(m = \sigma^e \bmod{n}\)
• Existential forgery under a known-message attack:
  • the adversary knows \(n, e\) and some \((m_i, \sigma_i)\)
  • \(m = m_1 m_2 \bmod{n}\)
  • \(\sigma = \sigma_1 \sigma_2 \bmod{n}\)
• Universal forgery under a chosen-message attack:
  • we want to obtain a signature for a message \(m\)
  • find \(m_1, m_2 \ne m\) such that \(m_1 m_2 \equiv m \pmod{n}\)
  • obtain signatures \(\sigma_1\), \(\sigma_2\) of \(m_1\), \(m_2\)
  • compute \(\sigma = \sigma_1 \sigma_2 \bmod{n}\)

Exercise 2 - the reblocking problem

Suppose that Alice wants to send Bob a signed and encrypted message \(m\). She will use RSA for both signing and encrypting. She first uses her private key \((n_A, d_A)\) to obtain the signature \(s = m^{d_A} \bmod{n_A}\), and then uses Bob's public key \((n_B, e_B)\) to obtain the ciphertext \(c = s^{e_B} \bmod{n_B}\). She sends \(c\) to Bob, who then decrypts it with his private key \((n_B, d_B)\) to obtain \(s' = c^{d_B} \bmod{n_B}\), and finally recovers the message \(m' = s'^{e_A} \bmod{n_A}\) using Alice's public key \((n_A, e_A)\).

Assuming that \(m\) has been chosen uniformly at random from \(\mathbb{Z}_{n_A}\), what is the probability that \(m \ne m'\) - i.e., that Bob does not decrypt the message correctly? Compute the probability for \(n_A = 62894113\) and \(n_B = 55465219\). How could this problem be mitigated?

\[ \begin{aligned} m' &= s'^{e_A} \bmod{n_A} \\ &= (c^{d_B} \bmod{n_B})^{e_A} \bmod{n_A} \\ &= ((s^{e_B} \bmod{n_B})^{d_B} \bmod{n_B})^{e_A} \bmod{n_A} \\ &= (((m^{d_A} \bmod{n_A})^{e_B} \bmod{n_B})^{d_B} \bmod{n_B})^{e_A} \bmod{n_A} \\ &= ((m^{d_A} \bmod{n_A}) \bmod{n_B})^{e_A} \bmod{n_A} \end{aligned} \]

• If \(n_A < n_B\), everything will be OK.
• If \(n_A > n_B\): \(m' \ne m\) with probability \(1 - \frac{n_B}{n_A}\).

Revised protocol:

1. Alice produces a signature \(\sigma\) of \(m\).
2. Alice encrypts \(m \| \sigma\) to produce a ciphertext \(c\) and sends it to Bob.
3. Bob decrypts the ciphertext \(c\) to obtain the message \(m'\) and signature \(\sigma'\).
4. Bob verifies that \(\sigma'\) is Alice's signature of \(m'\).

Exercise 3

Describe why the value \(\gamma \bmod{p-1}\) in the ElGamal signature scheme should not be \(0\).

• If \(\gamma \equiv 0 \pmod{p-1}\), then the private key is not used in signing.
• If \(\delta = 0\), then we can compute \(a = m\gamma^{-1} \bmod{p-1}\).

Exercise 4

Compare the ElGamal and DSA signature schemes. Does the difference in efficiency affect the security of DSA?

Assume \(p\) is a 1024-bit prime, \(q\) is 160-bit prime.

• ElGamal signature:

  • signature length: \(2048\) bits
  • signing: \(O(\log^3 p) \approx 1024^3\)
  • verifying: \(3 \cdot O(\log^3 p) \approx 3 \cdot 1024^3\)

• DSA signature:

  • signature length: \(320\) bits
  • signing: \(O(\log^3 p) \approx 1024^3\)
  • verifying: \(3 \cdot O(\log^3 p) \approx 3 \cdot 1024^3\)

• Index calculus on \(p\) is about as efficient as doing baby-step/giant-step algorithm in a subgroup of order \(q\)