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