---
tags: vaje, kirv, rsa, crt
hackmd: https://hackmd.io/8aTp--1SQmWQ_lHgkzCaug
plugins: mathjax
---
# Cryptography and computer security - Tutorial 10.11.2020

---

## RSA

* Rivest, Shamir, Adleman
* <i>$p, q \in \mathbb{P}$</i> distinct (at least 512 bits)
* <i>$n = pq$</i>
* <i>$ed \equiv 1 \pmod{\phi(n)}$</i>
* <i>$\phi(n) = (p-1) (q-1)$</i>

- private key: <i>$(n, d)$</i>
- public key: <i>$(n, e)$</i>
- <i>$\mathcal{P} = \mathcal{C} = \mathbb{Z}_n$</i>
- <i>$E_{(n, e)}(x) = x^e \bmod{n}$</i>
- <i>$D_{(n, d)}(y) = y^d \bmod{n}$</i>

+ <i>$D_{(n, d)}(E_{(n, e)}(x)) \equiv x^{ed} \equiv x \pmod{n}$</i>

---

### Exercise 1

Suppose <i>$p = 11$</i>, <i>$q = 17$</i> and <i>$e = 3$</i>. Compute <i>$d$</i> and encrypt the plaintext <i>$m = 107$</i>. Then, decrypt the resulting ciphertext.

----

* <i>$n = pq = 187$</i>
* <i>$\phi(n) = (p-1)(q-1) = 160$</i>

| $k$ | $a$ | $s$ |
| --- | --- | --- |
| | 160 | 0 |
| | 3 | 1 |
| 53 | 1 | -53 |

* <i>$d = 107$</i>

- Encryption of <i>$m = 107$</i>:
+ <i>$c = m^e \bmod{n} = 107^3 \bmod{187}$</i>
+ <i>$107^2 \bmod{187} = 80^2 \bmod{187} = 6400 \bmod{187} = 42$</i>
+ | bit | square | multiply |
| --- | ------ | -------- |
| 1 | $1$ | $107$ |
| 1 | $42$ | $6$ |
+ <i>$c = 6$</i>

- Decryption of <i>$c = 6$</i>:
+ <i>$m = c^d \bmod{n} = 6^{107} \bmod{187}$</i>
+ <i>$107 = 64 + 32 + 8 + 2 + 1 = 1101011_2$</i>
+ | bit | square | multiply |
| --- | ------ | -------- |
| 1 | $1$ | $6$ |
| 1 | $36$ | $29$ |
| 0 | $93$
| 1 | $47$ | $95$ |
| 0 | $49$
| 1 | $157$ | $7$ |
| 1 | $49$ | $107$ |
+ <i>$m = 107$</i>

---

### Exercise 2

Find <i>$\sqrt[7]{2}$</i> in <i>$\mathbb{Z}_{187}^*$</i>.

----

* <i>$x \equiv \sqrt[7]{2} \pmod{187}$</i>
* <i>$x^7 \equiv 2 \pmod{187}$</i>
* <i>$x^{\phi(187)} \equiv 1 \pmod{187}$</i>
* <i>$x^{160} \equiv 1 \pmod{187}$</i>
* <i>$7 \cdot 23 \equiv 161 \equiv 1 \pmod{\phi(187)}$</i> (obtained by EEA)
* <i>$x = 2^{23} \bmod{187} = 162$</i>

---

## 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 <i>$n_1, n_2, \dots, n_k$</i> are mutually coprime, then there is a unique solution for <i>$x$</i> modulo <i>$n_1 n_2 \cdots n_k$</i>.

---

### Exercise 3

Find a number <i>$x$</i> such that its remainder is <i>$2$</i> when dividing by <i>$3$</i>, <i>$3$</i> when dividing by <i>$5$</i>, and <i>$2$</i> when dividing by <i>$7$</i>.

----

$$
\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 <i>$p$</i> be a prime, and <i>$a$</i> and <i>$b$</i> be arbitrary integers.

1. Show that <i>$p \; | \; {p \choose i}$</i> for <i>$1 \le i \le p-1$</i>.
2. Show that <i>$(a + b)^p \equiv a^p + b^p \pmod{p}$</i>.
3. Show that <i>$a^p \equiv a \pmod{p}$</i>.

----

1. * <i>${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}$</i>
* all values in the denominator are coprime with <i>$p$</i>
* therefore <i>$p \; | \; {p \choose i}$</i>

2. <i>$(a + b)^p \equiv \sum_{i=0}^p {p \choose i} a^i b^{p-i} \equiv a^p + b^p \pmod{p}$</i>

3. <i>$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}$</i>