Cryptography and computer security - Tutorial 10.11.2020

RSA

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

• private key: \((n, d)\)
• public key: \((n, e)\)
• \(\mathcal{P} = \mathcal{C} = \mathbb{Z}_n\)
• \(E_{(n, e)}(x) = x^e \bmod{n}\)
• \(D_{(n, d)}(y) = y^d \bmod{n}\)

• \(D_{(n, d)}(E_{(n, e)}(x)) \equiv x^{ed} \equiv x \pmod{n}\)

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\)

• \(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.

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

1. • \({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}\)

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

3. \(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}\)