Cryptography and Computer Security

« nazaj

Cryptography and computer security - Tutorial 15.12.2020

---

Discrete logarithm problem

• Input: $a, b, p$
• Output: $x \in \mathbb{Z}_{p-1}$ such that $a^x \equiv b \pmod{p}$

Baby-step/giant-step algorithm (Shanks’s algorithm)

1. Let $H$ be an empty hash map.
2. Set $m := \lceil \sqrt{r} \rceil$, where $r$ is (a multiple of) the order of $a$ in $\mathbb{Z}_p^*$ (in general, $r = p-1$). $O(\log^2 p)$
3. For $i = 0, 1, \dots, m-1$ do $H[a^{mi} \bmod{p}] := i$. $O(\sqrt{p} \log^2 p)$
4. For $j = 0, 1, \dots, m-1$ do: $O(\sqrt{p})$ steps, total $O(\sqrt{p} \log^2 p)$
   1. Set $c := ba^{-j} \bmod{p}$. $O(\log^2 p)$
   2. If $c \in H$ then return $m H[c] + j$. $O(\log p)$

Pohlig-Hellman algorithm

1. Write $p-1 = \prod_{i=1}^t q_i^{e_i}$, where $q_i$ ($1 \le i \le t$) are prime numbers.
2. For $i = 1, 2, \dots, t$:
   1. Compute $a_i := a^{(p-1)/q_i} \bmod{p}$.
   2. Set $c_{i0} := 1$ and $k_{i0} := 0$.
   3. For $j = 1, 2, \dots, e_i$ do:
      1. Compute $c_{ij} := c_{i,j-1} a^{-k_{i,j-1}} \bmod{p}$.
      2. Compute $k_{ij} := q_i^{j-1} \log_{a_i} (b c_{ij})^{(p-1)/q_i^j}$ in $\mathbb{Z}_p$ using the baby-step/giant-step algorithm with order $q_i$.
   4. Compute $x_i := \sum_{j=1}^{e_i} k_{ij}$.
3. Solve the system $x \equiv x_i \pmod{q_i^{e_i}}$ ($1 \le i \le t$) by CRT and return $x$.

Index calculus algorithm

1. Choose a factor base $(q_i)_{i=1}^t$ consisting of $-1 \bmod{p}$ and small primes.
2. Find the logarithm table $(f_i)_{i=1}^t$ for the factor base, i.e., $a^{f_i} \equiv q_i \pmod{p}$ ($1 \le i \le t$).
3. Choose $x \stackrel{R}{\in} \mathbb{Z}_{p-1}$.
4. Compute $c := b^x \bmod{p}$.
5. Attempt to find $(e_i)_{i=1}^t$ such that $c \equiv \prod_{i=1}^t q_i^{e_i} \pmod{p}$ (on failure go to 3).
6. Compute $g := \gcd(p-1, x)$ and $m := {p-1 \over g}$.
7. Compute $y := \left(\sum_{i=1}^t e_i f_i \right) x^{-1} \bmod{m}$.
8. For $j = 0, 1, \dots, g-1$ do:
   1. Compute $z := y + jm$.
   2. If $a^z \equiv b \pmod{p}$ then return $z$.

---

Exercise 1

Determine the time and space complexities of the exhaustive search and the baby-step/giant-step algorithm for computing the discrete logarithm.

---

• $x = \log_a b$ in $\mathbb{Z}_p^*$, $p$ prime
• $a^x \equiv b \pmod{p}$
• $x \in \mathbb{Z}_{p-1}$

Exhaustive search:

• time complexity: $O(p \log^2 p)$
• space complexity: $O(\log p)$

Baby-step/giant-step:

• time complexity: $O(\sqrt{p} \log^2 p)$
• space complexity: $O(\sqrt{p} \log p)$

---

Exercise 2

Find $\log_{47} 191$ in $\mathbb{Z}^*_{829}$ using the baby-step/giant-step algorithm.

---

Computation

---

Exercise 3

Find $\log_2 181$ in $\mathbb{Z}^*_{197}$ using the Pohlig-Hellman algorithm. Then, compute $\log_{11} 2020$ in $\mathbb{Z}^*_{15121}$.

---

• $p = 197$
• $p-1 = 196 = 2^2 \cdot 7^2$
• $a = 2$

• $b = 181$

• $q_1 = 2$
  • $a_1 = 2^{98} \bmod{197} = 196$
  • $c_{11} = 1$
  • $\log_{196} 181^{98} = \log_{196} 1 = 0$
  • $k_{11} = 0$
  • $c_{12} = 1$
  • $\log_{196} 181^{49} = \log_{196} 196 = 1$
  • $k_{12} = 2$
  • $x_1 = 2$
  • $x \equiv 2 \pmod{4}$
• $q_2 = 7$
  • $a_2 = 2^{28} \bmod{197} = 104$
  • $c_{21} = 1$
  • $\log_{104} 181^{28} = \log_{104} 164 = 4$
  • $k_{21} = 4$
  • $c_{22} = 2^{-4} \bmod{197} = 37$
  • $\log_{104} (181 \cdot 37)^4 = \log_{104} 1 = 0$
  • $k_{22} = 0$
  • $x_2 = 4$
  • $x \equiv 4 \pmod{49}$
• $x = 102$

Computation

---

Exercise 4

Find $\log_5 4389733$ and $\log_5 1234567$ in $\mathbb{Z}^*_{9330887}$ using the index calculus method.

---

Computation

---

Exercise 5

Find $\log_{47} 191$ in $\mathbb{Z}^*_p$ for

\[\begin{aligned} p \in \{&{} 100000000003, 10000000000000000051, 1000000000000000000117, \\ &{} 10000000000000000000000343, 10000000000000000000000000331\}. \end{aligned}\]

Compare the running times of the baby-step/giant-step, Pohlig-Hellman and index calculus algorithms.

---

• Baby-step/giant-step
• Pohlig-Hellman
• Index calculus

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.