« nazaj
Cryptography and computer security - Tutorial 17.11.2020
Attacks on RSA
Exercise 1
Show that, given $\phi(n)$, one can factorize $n$. Factorize $n = 187$ if you know $\phi(n) = 160$.
\[\begin{aligned}
n &= pq \\
\phi(n) &= (p-1)(q-1) = pq - p - q + 1 \\
q &= {n \over p} \\
\phi(n) &= n - p - {n \over p} + 1 \\
p \phi(n) &= np - p^2 - n + p \\
0 &= p^2 - (n - \phi(n) + 1) p + n \\
p, q &= {n - \phi(n) + 1 \pm \sqrt{(n - \phi(n) + 1)^2 - 4n} \over 2} \\[1ex]
p, q &= {187 - 160 + 1 \pm \sqrt{(187 - 160 + 1)^2 - 4 \cdot 187} \over 2} \\
&= {28 \pm \sqrt{784 - 748} \over 2} = 14 \pm 3 = 11, 17
\end{aligned}\]
Exercise 2 - Coppersmith’s attack on a small exponent
Suppose Alice sends the same message $m$ in encrypted form to three people. Each time, she used the same public exponent $e = 3$, but different moduli $n_i$ ($i = 1, 2, 3$). Show how an attacker can retrieve the message $m$ only from the public data (i.e., the moduli $n_i$, the public exponent $e$, and the encryptions $c_i = m^e \bmod{n_i}$ for $i = 1, 2, 3$).
Find the message $m$ if $e = 3$, $n_1 = 55$, $n_2 = 391$, $n_3 = 1189$ and $c_1 = 6$, $c_2 = 105$, $c_3 = 1148$.
\[\begin{aligned}
c_1 &\equiv m^3 \pmod{n_1} \\
c_2 &\equiv m^3 \pmod{n_2} \\
c_3 &\equiv m^3 \pmod{n_3} \\
\end{aligned}\]
- We find $x := m^3 \bmod{n_1 n_2 n_3}$ by CRT (assuming $n_1, n_2, n_3$ are coprime).
- If they are not coprime, we can factorize them and find the private keys.
\[\begin{aligned}
0 \le m &< n_1 \\
0 \le m &< n_2 \\
0 \le m &< n_3 \\
0 \le m^3 &< n_1 n_2 n_3
\end{aligned}\]
- Therefore, $x = m^3$.
- $m = \sqrt[3]{x}$
- Example
Exercise 3 - common modulus attack
Show how the plaintext can be recovered when the same message $m$ is encrypted with two relatively prime public exponents $e_1$ and $e_2$ and the same modulus $n$.
Find the message $m$ if $n = 55$, $e_1 = 3$, $e_2 = 7$ and $c_1 = 8$, $c_2 = 18$.
\[\begin{aligned}
c_1 &\equiv m^{e_1} \pmod{n} \\
c_2 &\equiv m^{e_2} \pmod{n} \\
e_1 &\bot e_2 \\
c_1^a c_2^b &\equiv m^{a e_1 + b e_2} \pmod{n}
\end{aligned}\]
- We use the Extended Euclidean algorithm to compute $a, b$ such that $a e_1 + b e_2 = 1$.
- We can then compute $m = c_1^a c_2^b \bmod{n}$.
- Example
Exercise 4
Suppose that the RSA public key $(n, e) = (2491, 1595)$ has been used to encrypt each individual character in a message $m$ (using their ASCII codes), giving the following ciphertext:
\[c = (111, 2474, 1302, 1302, 1587, 395, 224, 313, 1587, 1047, 1302, 1341, 980) .\]
Determine the original message $m$ without factoring $n$.