« nazaj
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:
- Alice produces a signature $\sigma$ of $m$.
- Alice encrypts $m | \sigma$ to produce a ciphertext $c$ and sends it to Bob.
- Bob decrypts the ciphertext $c$ to obtain the message $m’$ and signature $\sigma’$.
- 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$