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

2020-05-30 cryptography 密码学 单项函数

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

群论

定义一个集合 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) \)

如何满足如下条件成为阿贝尔群(交换群):

  1. 交换率: \(\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))\) 时间内解决。

本人保留对侵权者及其全家发动因果律武器的权利

版权提醒

如无特殊申明,本站所有文章均是本人原创。转载请务必附上原文链接:https://www.laytonchen.com/post/crypto/crypto-math/

如有其它需要,请邮件联系!版权所有,违者必究!