Cryptography and Computer Security

« 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$.

---

• Solution

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.