« nazaj
Cryptography and computer security - Tutorial 10.11.2020
RSA
Exercise 1
Suppose $p = 11$, $q = 17$ and $e = 3$. Compute $d$ and encrypt the plaintext $m = 107$. Then, decrypt the resulting ciphertext.
- $n = pq = 187$
- $\phi(n) = (p-1)(q-1) = 160$
| $k$ |
$a$ |
$s$ |
| |
160 |
0 |
| |
3 |
1 |
| 53 |
1 |
-53 |
-
$d = 107$
- Encryption of $m = 107$:
- $c = m^e \bmod{n} = 107^3 \bmod{187}$
- $107^2 \bmod{187} = 80^2 \bmod{187} = 6400 \bmod{187} = 42$
-
| bit |
square |
multiply |
| 1 |
$1$ |
$107$ |
| 1 |
$42$ |
$6$ |
- $c = 6$
- Decryption of $c = 6$:
- $m = c^d \bmod{n} = 6^{107} \bmod{187}$
- $107 = 64 + 32 + 8 + 2 + 1 = 1101011_2$
-
| bit |
square |
multiply |
| 1 |
$1$ |
$6$ |
| 1 |
$36$ |
$29$ |
| 0 |
$93$ |
|
| 1 |
$47$ |
$95$ |
| 0 |
$49$ |
|
| 1 |
$157$ |
$7$ |
| 1 |
$49$ |
$107$ |
- $m = 107$
Exercise 2
Find $\sqrt[7]{2}$ in $\mathbb{Z}_{187}^*$.
- $x \equiv \sqrt[7]{2} \pmod{187}$
- $x^7 \equiv 2 \pmod{187}$
- $x^{\phi(187)} \equiv 1 \pmod{187}$
- $x^{160} \equiv 1 \pmod{187}$
- $7 \cdot 23 \equiv 161 \equiv 1 \pmod{\phi(187)}$ (obtained by EEA)
- $x = 2^{23} \bmod{187} = 162$
Chinese remainder theorem
\[\begin{aligned}
x &\equiv a_1 \pmod{n_1} \\
x &\equiv a_2 \pmod{n_2} \\
&\dots \\
x &\equiv a_k \pmod{n_k}
\end{aligned}\]
If $n_1, n_2, \dots, n_k$ are mutually coprime, then there is a unique solution for $x$ modulo $n_1 n_2 \cdots n_k$.
Exercise 3
Find a number $x$ such that its remainder is $2$ when dividing by $3$, $3$ when dividing by $5$, and $2$ when dividing by $7$.
\[\begin{aligned}
x &\equiv 2 \pmod{3} \\
x &\equiv 3 \pmod{5} \\
x &\equiv 2 \pmod{7}
\end{aligned}\]
\[\begin{aligned}
x &= 2 + 3a & (a \in \mathbb{Z}) \\
2 + 3a &\equiv 3 \pmod{5} \\
3a &\equiv 1 \pmod{5} \\
a &\equiv 2 \pmod{5} \\
a &= 2 + 5b & (b \in \mathbb{Z}) \\
x &= 2 + 3(2 + 5b) = 8 + 3 \cdot 5b & (b \in \mathbb{Z}) \\
8 + 15b &\equiv 2 \pmod{7} \\
1 + b &\equiv 2 \pmod{7} \\
b &\equiv 1 \pmod{7} \\
b &= 1 + 7c & (c \in \mathbb{Z}) \\
x &= 8 + 3 \cdot 5 \cdot (1 + 7c) = 23 + 3 \cdot 5 \cdot 7c & (c \in \mathbb{Z}) \\
x &\equiv 23 \pmod{3 \cdot 5 \cdot 7}
\end{aligned}\]
Exercise 4
Let $p$ be a prime, and $a$ and $b$ be arbitrary integers.
- Show that $p \; | \; {p \choose i}$ for $1 \le i \le p-1$.
- Show that $(a + b)^p \equiv a^p + b^p \pmod{p}$.
- Show that $a^p \equiv a \pmod{p}$.
-
- ${p \choose i} = {p! \over i! (p-i)!} = {p \cdot (p-1) \cdots 1 \over i \cdot (i-1) \cdots 1 \ \cdot \ (p-i) \cdot (p-i-1) \cdots 1}$
- all values in the denominator are coprime with $p$
- therefore $p \; | \; {p \choose i}$
-
$(a + b)^p \equiv \sum_{i=0}^p {p \choose i} a^i b^{p-i} \equiv a^p + b^p \pmod{p}$
- $a^p \equiv ((a-1) + 1)^p \equiv (a-1)^p + 1^p \equiv 1^p + 1^p + \dots + 1^p \equiv 1 + 1 + \dots + 1 \equiv a \pmod{p}$