Cryptography and computer security - Tutorial 15.12.2020

--- tags: vaje, kirv, discrete logarithm hackmd: https://hackmd.io/eF6k1BOHTLK_y5NjUIvDPQ plugins: mathjax --- # 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](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/BabyStepGiantStep.ipynb) --- ### 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](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/PohligHellman.ipynb) --- ### Exercise 4 Find $\log_5 4389733$ and $\log_5 1234567$ in $\mathbb{Z}^*_{9330887}$ using the index calculus method. ---- [Computation](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/IndexCalculus.ipynb) --- ### 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](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/BabyStepGiantStep.ipynb#Running-time-comparison) * [Pohlig-Hellman](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/PohligHellman.ipynb#Running-time-comparison) * [Index calculus](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/IndexCalculus.ipynb#Running-time-comparison)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.