数论部分

质数与模算术

整数集合 $\mathbb{Z}$, $a,b,c \in \mathbb{Z}$。
$a$ 整除 $b$: $a \mid b$ 如果 $\exists c, ac=b$ (否则 $a \nmid b$). $b$ 是 $a$ 的倍数。如果 $a \notin {1,b}$，那么 $a$ 是 $b$ 的因子。
$p > 1$ 是质数（素数），如果其没有因子；否则，是合数。
$\forall a,b$, $\exists$ 商 $q$, 余数 $r$: $a=qb+r$, 且 $0\le r < b$。
最大公因子 $\gcd(a,b)$ 是最大的整数 $c$ 使得 $c\mid a$ 且 $c\mid b$。 $\gcd(0,b)=b$, $\gcd(0,0)$未定义。
$a$ 和 $b$ 是互质，如果 $\gcd(a,b)=1$。
余数 $r= [a\bmod N] = a - b\lfloor a/b\rfloor $ 并且 $r<N$. $N$ 称为模。
$\mathbb{Z}_N = {0,1,\dots,N-1} = {a \bmod N | a \in \mathbb{Z}}$.
$a$ 是模 $N$ 下可逆的$\iff \gcd(a,N) = 1$。如果 $ab \equiv 1 \pmod N$，那么 $b=a^{-1}$是模 $N$ 下 $a$ 的乘法逆。
欧几里德算法（辗转相除法）： $\gcd(a,b) = \gcd(b, [a \bmod b]).$
- $\gcd(12, 27)$
- 扩展欧几里德算法：给定 $a,N$，寻找 $X,Y$ 使得 $Xa+YN = \gcd(a,N)$ （贝祖定理）
  - 例子，求11 (mod 17)下的逆元，$a = 11$，$N = 17$，$Xa + YN = r$
```
               r     X    Y  m
               17    0    1
               11    1    0  1
                6   -1    1  1
                5    2   -1  1
                1   -3    2   
```
- 求余然后相加/乘
  - 计算 $193028 \cdot 190301 \bmod 100$
- 消去律：如果 $\gcd(a,N)=1$ 且 $ab \equiv ac \pmod N$，那么 $b \equiv c \pmod N$.
  - $a=3, c=10, b=2, N=24$

欧拉函数$\phi$

欧拉phi函数：$\phi(N) \overset{\text{def}}{=} |\mathbb{Z}_N^*|$. 注：整数乘法群的阶
- 算法基本定理：$N = \prod_ip_i^{e_i}$ , ${p_i}$ 是不同的质数， $\phi(N) = \prod_ip_i^{e_i-1}(p_i-1)$。
- 例题：$N=pq$ 其中 $p,q$ 是不同质数。$\phi(N)=?$ $\phi(12)=?$ $\phi(30)=?$
- 欧拉定理与费马小定理：$a \in \mathbb{Z}_N^*$. $a^{\phi (N)} \equiv 1 \pmod N$. 注：前面证明过
- 如果 $p$ 是质数并且 $a \in {1,\dotsc,p-1}$，那么 $a^{p-1} \equiv 1 \pmod p$. 注：因为质数$p$乘法群的阶为$p-1$
- 例题：$3^{43} \bmod 49 = ?$

整数分解是一个难问题

分解 $N=pq$. $p,q$ 长度相同为 $n$.
- 尝试分解: $\mathcal{O}(\sqrt{N}\cdot \mathsf{polylog}(N))$.
- Pollard’s $p-1$ 方法: 当 $p-1$ 具有小质数因子时有效。
- Pollard’s rho 方法: $\mathcal{O}(N^{1/4}\cdot \mathsf{polylog}(N))$.
- 二次筛法 [Carl Pomerance]: 亚指数时间 $\mathcal{O}(\exp(\sqrt{n\cdot \log n}))$.
- 已知最优算法为通用数域筛法 [Pollard]：$\mathcal{O}(\exp(n^{1/3}\cdot(\log n)^{2/3}))$.

RSA问题是一个难问题

思路：分解难 $\implies$ 对于 $N=pq$, 找到 $p,q$ 难 $\implies$ 计算 $\phi(N)=(p-1)(q-1)$ 难

$\implies$ 无法模 $\phi(N)$ 计算

$\implies$ 计算 $e^{-1} \bmod \phi(N)$ 难

**这里存在一段空白**

$\implies$ RSA 问题难：给定 $y \in \mathbb{Z}^*_N$, 计算 $y^{-e}$ modulo $N$.

RSA共模攻击

共模攻击使用相同的模数 $N$.
- 情况1：多个用户带有自己的密钥。每个用户可以以自己的 $e,d$ 计算 $\phi(N)$ ，然后找到其他人的 $d$.
- 情况2：用两个公钥为同一个消息加密。
  - 假设 $\gcd(e_1,e_2)=1$, $c_1 \equiv m^{e_1}$ and $c_2 \equiv m^{e_2} \pmod N$. $\exists X,Y$ 使得 $Xe_1 + Ye_2 = 1$ （贝祖定理）.
  - $ c_1^X\cdot c_2^Y \equiv m^{Xe_1}m^{Ye_2} \equiv m^1 \pmod N. $
  - $N = 15, e_{1} = 3, e_{2} = 5, c_{1} = 8, c_{2} = 2, m = ?$

群论

$\mathbb{Z}_N^*$ 群

$ \mathbb{Z}_N^* \overset{\text{def}}{=} {a \in {1,\dotsc,N-1 } | \gcd(a,N) = 1} $
- 群是一个集合 $\mathbb{G}$ 带有一个二元操作 $\circ$:
  - 闭包： $\forall g,h \in \mathbb{G}$, $g \circ h \in \mathbb{G}$.
  - 单位元： $\exists$ 单位元 $e\in \mathbb{G}$ 使得 $\forall g\in \mathbb{G}, e \circ g = g = g \circ e$.
  - 逆元： $\forall g \in G$, $\exists; h \in \mathbb{G}$ 使得 $g \circ h =e = h \circ g$. $h$ 是 $g$ 的逆元.
  - 结合律：$\forall g_1,g_2,g_3 \in \mathbb{G}$, $(g_1\circ g_2)\circ g_3 = g_1 \circ (g_2 \circ g_3)$.
- $\mathbb{G}$ with $\circ$ 是阿贝尔群，如果有交换律：$\forall g,h \in \mathbb{G}, g\circ h = h\circ g$.
- 逆元的存在意味着消去律
- 当 $\mathbb{G}$ 是有限群，$| \mathbb{G}|$ 是群的阶。
- 问题： $\mathbb{Z}N^$ 是乘法下的群吗？ $\mathbb{Z}N$ 在乘法下呢？ $\mathbb{Z}{15}^ = ?$ $\mathbb{Z}{13}^* = ?$

群指数（群的阶数）

$ g^m \overset{\text{def}}{=} \underbrace{g\circ g\circ \cdots \circ g}_{m; \text{times}}. $
- 欧拉定理：$\mathbb{G}$ 是有限群。那么， $\forall g \in \mathbb{G}, g^{|\mathbb{G}|}=1$.
- 注：课上证明，将群中每个元素与 $g$ 相乘后连乘等于群中元素连乘。
- 例子：计算 $3 \in \mathbb{Z}_{7}^*$ 的所有幂。
- 费马小定理：$\forall g \in \mathbb{G}$ and $i$, $g^i \equiv g^{[i \bmod {|\mathbb{G}|}]}$.
- 注：这是欧拉定理的推论。
- 例子：计算 $3^{78} \in \mathbb{Z}_{7}^*$

基于群指数的排列

指数函数 $f_e;:$ $\mathbb{Z}^_N \to \mathbb{Z}^_N$ by $f_e(x) =[x^e \bmod N]$.
- 对指数函数求逆：$y$ 的 $e$ 次方根: $x^e \equiv y$, $x \equiv y^{1/e}$.
- 推论：如果 $\gcd(e,\phi(N))=1$，那么 $f_e$ 是排列。
- 证明：令 $d = [e^{-1} \bmod \phi(N)]$，那么 $f_d$ 是 $f_e$ 的逆函数。$y \equiv x^{e};\quad f_{d}(y) \equiv y^d \equiv x^{ed} \equiv x$.
- 例题：在 $\mathbb{Z}^*{10}$ 中, $e = 3,\ d = ?,\ f{e}(3) = ?,\ f_{d}(f_{e}(3)) = ?,\ 9^{\frac{1}{3}} = ?$
- 问题：如果对于某些特别的$N$无法计算 $\phi(N)$ ，那么会如何？如果不能分解 $N$ 呢?

循环群与生成元

$\mathbb{G}$ 是一个群并且一个元素 $g \in \mathbb{G}$通过运算生成一个子群 $ \langle g \rangle \overset{\text{def}}{=} { g^0,g^1,\dotsc,} = { g^0,g^1,\dotsc, g^{i-1}}$。
- $g$ 的阶是最小的正整数 $i$ 令 $g^i=1$。
- $\mathbb{G}$ 是一个循环群（cyclic group）如果 $\exists;g$ 有阶 $m = |\mathbb{G}|$. $\langle g \rangle = \mathbb{G}$, $g$ 是 $\mathbb{G}$ 的生成元。注：循环群中存在一个元素通过指数运算可生成整个群中每个元素。
- 例题：乘法下的$\mathbb{Z}_6^$, $\mathbb{Z}_7^$,或 $\mathbb{Z}_8^*$ 是循环群吗? 找到生成元。

离散对数难题

如果 $\mathbb{G}$ 是阶为 $q$ 的循环群，那么 $\exists$ 生成元 $g \in \mathbb{G}$ 使得 ${ g^0,g^1,\dotsc,g^{q-1}} = \mathbb{G}$。
- $\forall h \in \mathbb{G}$, $\exists$ 唯一的 $x \in \mathbb{Z}_q$ 使得 $g^x = h$。
- $x= \log_gh$ 是以$g$为底$h$的离散对数（discrete logarithm）。
- 如果 $g^{x’}=h$, 那么 $\log_gh = [x’ \bmod q]$。
- $\log_g1=0$ 并且 $\log_g(h_1\cdot h_2) = [(\log_gh_1+\log_gh_2) \bmod q]$。

离散对数算法

给定一个生成元 $g \in \mathbb{G}$ 并且 $y \in \langle g \rangle$，求 $x$ 使得 $g^x=y$.
- 蛮力： $\mathcal{O}(q)$, $q = \mathsf{ord}(g)$ 是 $\langle g\rangle$ 的阶。
- Baby-step/giant-step [Shanks]: $\mathcal{O}(\sqrt{q}\cdot \mathsf{polylog}(q))$.
- Pohlig-Hellman算法：当 $q$ 有较小因子。
- Index calculus 法: $\mathcal{O}(\exp{(\sqrt{n\cdot \log n})})$.
- 已知最好的算法是通用数域筛法：$\mathcal{O}(\exp(n^{1/3}\cdot(\log n)^{2/3}))$.
- 椭圆曲线群 vs. $\mathbb{Z}_p^$: 在保证安全性相同的同时，更高效。(1024-bit $\mathbb{Z}_p^$ 和 132-bit 椭圆曲线都需要 $2^{66}$ 步来破解。)

质数阶群

定理：如果 $\mathbb{G}$ 是质数阶，那么 $\mathbb{G}$ 是循环群。除单位元外，所有 $g \in \mathbb{G}$ 是生成元。
- 根据拉格朗日定理，任意元素的阶都等于群的阶。
- 拉格朗日定理：子群阶可以整除群阶。$\langle g \rangle$ 是 $\mathbb{G}$ 子群，并且 $|\langle g \rangle| \mid |\mathbb{G}|$。
  - 思路：由一个子群可以派生覆盖了整个群的若干子集，这些子集的阶与子群相同，并且这些子集彼此不相交。
  - 设群$\mathbb{G}$的子群$H$，陪集（coset）$gH$（$g$和$H$中每个元素$h$运算构成的集合）和子群$H$的阶相同。
  - 子群的任意两个陪集$g_1H$和$g_2H$。
    - 或者相同，如果$g_1^{-1}g_2 \in H$。$g_1(g_1^{-1}g_2 )h \in g_1H$，$g_2h \in g_1H$。
    - 或者没有交集，如果$g_1^{-1}g_2 \notin H$。采用反证法，如果有交集，则$g_1h_1 = g_2h_2$，$g_1^{-1}g_2 = h_1h_2^{-1} \in H$，矛盾。
  - 因此，群可以划分为任意子群的若干不相交陪集，每个陪集阶相同，群的阶就是子群的整数倍。
  - 推荐参考：https://brilliant.org/wiki/lagranges-theorem/
- 离散对数问题在质数阶群上是最难的。
- 在质数阶群上找一个生成元很简单。
- 任何非零指数在以质数阶为模下都可逆。
- DDH问题是难题的必要条件是 $\mathsf{DH}_g(h_1,h_2)$ 与群中随机元素之间是不可区分的。在质数阶群上这基本成立。

DH秘钥交换protocol

$\widehat{\mathsf{KE}}^{\mathsf{eav}}_{\mathcal{A},\Pi}$ 表示一个实验，其中如果 $b=0$ ，敌手被给予 $\hat{k} \gets \mathbb{G}$。
- 定理：如果DDH问题与$\mathcal{G}$相关是难的，那么DH 密钥交换协议 $\Pi$ 在出现窃听者时是安全的 (对应改动的实验 $\widehat{\mathsf{KE}}^{\mathsf{eav}}_{\mathcal{A},\Pi}$)。
- 不安全性：在主动的敌手，中间人，攻击下是不安全的 (Man-In-The-Middle)。敌手在中间与双方分别通信，通信双方无法发现在与敌手通信，敌手可以与双方分别协商出密钥。

证明如下：

$\Pr \left[ \widehat{\mathsf{KE}}^{\mathsf{eav}}{\mathcal{A},\Pi} =1\right] $ $= \frac{1}{2}\cdot \Pr\left[ \widehat{\mathsf{KE}}^{\mathsf{eav}}{\mathcal{A},\Pi} =1 | b=1\right] + \frac{1}{2}\cdot \Pr\left[ \widehat{\mathsf{KE}}^{\mathsf{eav}}_{\mathcal{A},\Pi} =1 | b=0\right] $
- 如果 $b=1$, 那么给真密钥；否则给随机的 $g^z$.
- $= \frac{1}{2}\cdot \Pr\left[ \mathcal{A}(g^x,g^y,g^{xy})=1 \right] + \frac{1}{2}\cdot \Pr\left[ \mathcal{A}(g^x,g^y,g^z)=0 \right] $
- $= \frac{1}{2}\cdot \Pr\left[ \mathcal{A}(g^x,g^y,g^{xy})=1 \right] + \frac{1}{2}\cdot (1-\Pr\left[ \mathcal{A}(g^x,g^y,g^z)=1 \right]) $
- $= \frac{1}{2} + \frac{1}{2}\cdot \left( \Pr\left[ \mathcal{A}(g^x,g^y,g^{xy})=1 \right] - \Pr\left[ \mathcal{A}(g^x,g^y,g^z)=1 \right] \right) $
- $ \le \frac{1}{2} + \frac{1}{2}\cdot \mathsf{negl}(n) %\left| \Pr\left[ \mathcal{A}(g^x,g^y,g^{xy})=1 \right] - \Pr\left[ \mathcal{A}(g^x,g^y,g^z)=1 \right] \right| $

密码学中数论知识的总结

数论部分

质数与模算术

欧拉函数$\phi$

整数分解是一个难问题

RSA问题是一个难问题

RSA共模攻击

群论

$\mathbb{Z}_N^*$ 群

群指数（群的阶数）

基于群指数的排列

循环群与生成元

离散对数难题

离散对数算法

质数阶群

DH秘钥交换protocol

CATALOG

FEATURED TAGS