密码学专题| 六、基于数学难解问题假设的单向函数

前文介绍了如果使用单向函数构造伪随机数发生器，进而构建计算安全的密码学算法。但是目前没有任何一个被严格证实的单向函数。但是基于近世代数可以构造一系列单向函数的候选数学难解问题。我们假设这些难解问题是多项式时间不可解的，并且构建了一系列实际在用的密码学算法。

群论

定义一个集合 G 和集合中的一个二元映射 + ,满足如下条件则成为一个群：

1. 封闭性： \(\forall a, b \in G, a+b \in G \)
2. 单位元存在： \(\exists e \in G, \forall a \in G, e+a = a+e = a \)
3. 存在逆元： \(\forall g \in G, \exists h \in G, g+h = h+g =e 记 h=g^{-1} \)
4. 结合律： \( \forall a,b,c \in G, (a+b)+c = a+(b+c) \)

如何满足如下条件成为阿贝尔群（交换群）：

5. 交换率： \(\forall a, b \in G, a+b = b + a \)

有限元素的群称为有限群，群的大小（也就是群元素的个数）为群的阶 |G|。

集合 {0,1,…N-1} 和膜 N 的加法构成了群 \(Z_N\)。 膜 N 的可逆元素和 膜 N 的乘法构成了交换群 \(Z_N^*\) 。特别地，集合 {1,2,…p-1} 和膜 p 的乘法构成了交换群 \(Z_p\) （其实是一个域）。

群有如下性质：

1. 消去率： 结合律： \( \forall a,b,c \in G, ab=bc \Rightarrow a=c \)
2. 对有限群 G ，在 \(\forall g \in G, g^{|G|} = e\)
3. 对一个 |G| > 1 的有限群，令 e > 0 且 \( \text{gcm}(e, |G| ) = 1 \) 。定义 \( f_e: G \rightarrow G, f_e(g) = g^e \)。则 \(f_e 是一个双射，即逆映射 f_d = f_e^{-1} 存在。且 f_d 和 f_e 互为逆 \)

考虑群 \(Z_N^*\) 有如下性质：

1. 群 \(Z_N^*\) 的大小 \( \phi(N) \) 称为欧拉函数。由算数基本定理，记 \(N = \prod p_i^{e_i} \)，则 \( \phi(N) = \prod p_i^{e_i-1}(p_i-1)\)。特别地，如果 N= pq，\(\phi(N) = (p-1)(q-1)\)；如果 N=p,\(\phi(p) = p-1\)
2. \(\exists e > 0 且 \text{gcm}(e, \phi(N)) = 1\) 则 \(f_e\) 是一个双射，它的逆为 \(f_e^{-1} = f_d \), \( d = e^{-1} \mod \phi(N) \)

群同构和中国剩余定理

可以定义两个群是指是等价的，也就是群同构:

对于两个群 \( (G, +_G ) 和 （H, +_H) \)，存在 f: G->H 满足如下条件时，构成群同构，写成 \(G \backsimeq H \)：

1. f 是一个双射。
2. \( \forall g_1, g_2 \in G, f(g_1 +_G g_2 ) = f(g_1) +_H f(g_2)\)

\(Z_N 和 Z_N^*\) 直接存在如下关系，也就是中国剩余定理（CRT)：

设 N = pq，且 gcm(p,q) = 1。\( Z_N \backsimeq Z_p \times Z_q, Z_N^* \backsimeq Z_p^* \times Z_q^* \) 则映射 \( f: N \rightarrow P \times Q , f(x) = ( [x \mod p], [x \mod q] )\)

由于存在这种等价关系，因此可以等价地将膜 N 的复杂运算降为膜 p 和 q 的小规模运算。

循环群

循环群是一种使用单个生成元 g 生成的群 \( \langle g \rangle \)。假设 \( \langle g \rangle \) 是一个 m 阶的循环群。那么对于生成元 g 有： \[ \langle g \rangle = \lbrace g^0, g^1 … g^{m-1} \rbrace \]

定义元素 g 的阶 ord(g) 是使得 \(g^l = 1 \) 的最小的 l = ord(g)。有如下性质：

1. 如果 \(x = y \mod l\) 则 \(g^x = g^y\)
2. 如果 m 有限，则 \( i | m \)
3. 如果 m 是一个素数，那么 \( \langle g \rangle \)中除了单位元之外的每一个元素都是生成元。
4. 如果 p 是一个素数，那么 \(Z_p^* \) 是一个循环群。

大整数分解难题和 RSA 难题

大整数分解问题描述为如下实验：

1. 随机生成 n bit 素数 \(p,q = Gen(1^n)\)，并验证 p，q 是素数。
2. 给一个线性多项式运行时间的敌手 A 输入 N=pq，A 输出 \(p’,q’\)
3. 如果 \(p’ q’ = N\) 则定义\(\text{Adv}_{A,\Pi_N} = 1\)

如果 \(Pr[\text{Adv}_{A,\Pi_N} = 1] \le negl(n)\) 那么我们认为在多项式时间内进行大数分解是困难的。

实验需要讨论如何构造 n 比特定长的素数？方案是首先生成 n-1 位的随机数 \(r’ = \lbrace 0,1 \rbrace^{n-1} \) ，而后构造数 r = 1 || r’。对数字 r 进行素性判定。如果 r 是素数，那么输出 r ，否则继续上述循环。

由于素数有稠密性质，上述循环进行最多 \( t = \frac{n^2}{c} \)次，无法找到素数的概率是可忽略的。其中 c 是一个常数。那么如何高效的寻找素数呢？一个典型的方法是 Miller-Rabin 素性判定算法。在这里不再赘述。

RSA 算法基于 RSA 问题，如果 N=pq，那么由于 p 和 q 分解困难，因此 \(\phi(N) \) 的计算是困难的。有如下 RSA 实验：

1. 运行 \( (p,q) \leftarrow GenRSA(1^n) \) ,选取 e 满足 \( gcd(e, \phi(N)) = 1 \)，以及 \( d = e^{-1} \mod \phi(N) \)，输出 (N, e, d)
2. 选择 \( y \leftarrow Z_n^* \)
3. 给多项式时间敌手 A 输入 (N, e, y)，A 输出 \(x \leftarrow Z_n^*\)
4. 当且仅当 \( x^e = y \mod N \) 时候 \(Adv_{A,\Pi}^{RSA} = 1\)

这个问题是困难的，也就是说： \[ Pr[Adv_{A,\Pi}^{RSA} = 1] \le negl(N) \]

目前大数分解有一些非多项式时间的算法，包括：

1. Pollard 的 p-1 方案。
2. Pollard 的 rho 方案，时间复杂度约为 \( O(N^{\frac{1}{4}} \cdot polylog(N) ) \)
3. 二次筛法。其复杂度是 \( O(2^{O(n)}) \) 亚指数的。
4. 通用数域筛法，平均复杂度为 \( 2^{ O(n^{ \frac{1}{3}} \cdot (\log(n))^{\frac{2}{3}} )}\)

离散对数难题和 Diffie-Hellman 难题

离散对数难题定义如下：

1. 运行 \((G,q,g) \leftarrow Gen(1^n) \)，其中 G 是一个素数 q 阶循环群，生成元是 g 。（ ||q|| = n)。
2. 选择 \(h \leftarrow G \)
3. 对一个多项式时间敌手 A 输入 G,q,g,h 。输出 \(x \in Z_q\)
4. 当且仅当 \(g^x = h\) ，则 \(Adv_{A,\Pi}^{DLOG} = 1\)

如果这个敌手在多项式时间计算出 x 的可能性可忽略，则认为是一个难题： \[ Pr[Adv_{A,\Pi}^{DLOG} = 1] \le negl(n) \]

Diffie-Hellman 难题是在 DLOG 难题之上引申而出的，对于 (G,q,g) 来说，计算 x,y 分别使得 \(g^x = h_1, g^y = h_2\) 是困难的。那么计算 \( g^{x \cdot y}\) 也是困难的。

已知 \(Z_p^* \) 是一个循环群，群的阶是 p-1。但是我们可以从 \( Z_p^* \) 出发，构造一个素数 q 阶的子群，并且可以很容易判断其中任何一个非单位元都是生成元 g 。方式是使用二次剩余子群。

二次剩余是对于\( \forall x \leftarrow Z_p, x^2 = y \mod Z_p \)。这些 y 构成了一个 \(Z_p^*\) 的子群。其群的阶是 \(q = \frac{p-1}{2}\)。这样我们找到了一个构造阶为 p 的循环子群的方案：

1. 首先寻找一个 n+1 bit 强素数 p = 2q+1，其中 q 也是一个素数。
2. 计算 q = (p-1)/2
3. 对于任意 \( x \in Z_p^*, x \ne \pm 1 \mod p \)，计算 \( g = x^2 \mod p\)
4. 以 g 作为单位元，循环 q-1 次，构造出阶为 q 的 \(Z_p^* \) 的一个子群。
5. 返回 G,q,g

目前离散对数难题有一些非多项式时间的算法，目前认为渐进最优化的算法可以在 \(O(\sqrt{q} \cdot ploylog(q))\) 时间内解决。