Cryptography and computer security - Tutorial 17.11.2020

--- tags: vaje, kirv, rsa, attacks hackmd: https://hackmd.io/0_WDCb5fRVOvbs0XETLfOA plugins: mathjax --- # 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](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/Coppersmith.ipynb) --- ### 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](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/CommonModulus.ipynb) --- ### 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](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/RSA-ECB.ipynb)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.