数论与群论密码学-10-针对离散对数密码系统的攻击

对于前文讨论的基于离散对数问题的密码系统,都有猜想认为破解他们等价于求解 DLP。因此本章我们讨论解决 DLP 的算法。

读者应当明白,本文的重点是通过分析离散对数算法/攻击,从而讨论其对基于离散对数的密码,尤其是对于密钥选择的影响。因此为了节约篇幅,各算法的部分细节我们将略去不表,而读者应将注意力放在使得各种攻击实际上可行的,不良的密钥选取方法上。

时间复杂度分析

\(n = \big| \mathbb{F}_p^\times \big| = p-1\),且 对于 \(b\in\mathbb{F}_p^\times\)\(ord(b) = n\)。那么构造以 \(b\) 为底的对数表需要进行 \(n \times time(mult)=n(\log_2p)^2\) 次,或者说 \(\Theta(p \log_2^2 p)\) 次位运算。

空间复杂度分析

存储 \(n\) 个群元素约需要 \(\Theta(p \log p)\) 比特。

虽然并不是明显可见,存储对数表所耗空间是大得惊人的。这里给出一个算是蛮精确的估计。若设 \(s_p\) 为对数表的比特大小, \(r\)\(p\) 的比特位数,则有

\[n_{r-1} < s_p < n_r\]

其中 \(n_r = (r-1)2^r\) 为存储所有比特位数小于等于 \(r\) 的数所需的空间。显然,因为有 \(2^{k-1}\)\(k\) 比特数,而存储它们需要 \(2^{k-1}k\) 位空间。

于是根据归纳法我们可以证明

\[ n_r = \sum_{k=1}^{r} k2^{k-1} = (r-1)2^r + 1 \]


因此若有 \(y\),其阶小得多,记 \(ord(y) =: k\),于是有 \(y \in <b^\frac{n}{k}>\),那么我们只需要构造以 \(b^{n/k}\) 为底,大小为 \(k\) 的对数表便可解决 DLP。这个主意被部分地用在了 SPH 攻击中。

对数表攻击的变种:穷举

为了求 \(DL_b(y)\),逐次计算 \(b^0, b^1, b^2, \cdots\) 直到得到 \(y\)

该方法只需要存储 \(b, b^n, b^{n+1}, n\),而缺点为每次攻击时都需要重新计算。

而时间上与对数表方法一致。

方法 1a: 大步小步算法(Baby Step, Giant Step, BSGS)

BSGS 方法观察到了这样的事实:为了找到满足 \(b^x = y\) 的数 \(x\),其中有 \(ord(b) = n\),我们可以将 \(x\) 重写为 \(i m + j\),其中 \(m = \lceil \sqrt{n} \rceil\), \(0 \le i, j < m\)。于是有 \[ \begin{aligned} b^x &= y\\ b^{im + j} &= y\\ b^j &= y(b^{-m})^i \end{aligned} \] 并找到满足该关系的 \(i, j\)。具体寻找 \(i, j\) 的方法略去不表,但作为对比,我们给出这样的事实:该方法仅需构造大小为 \(\sqrt{n}\) 的对数表,并在此过程中需要进行 \(\sqrt{n}\) 次乘法运算。

方法 2: SPH 攻击

\(b \in G\)\(y \in <b>\)

\(n=ord(b)\) 是 "B-平滑"(B-smooth)的,即 \(n\) 的素因数都很小:

\[ n = \prod_{i=1}^s p_i^{\alpha_i}, \text{ 其中 $p_i \le B$, $B$ 为一足够小的数} \]

此时该方法是可行的:若我们能对 \(n\) 进行因式分解,该攻击仅需构造大小不超过 \(B\) 的对数表。

该攻击的方法如下:

\(x=DL_b(y), n = ord(b)\)

  1. 为了求 \(x\),我们仅需对于 \(i = 1,\cdots,s\) 分别求 \(x \pmod{p_i^{\alpha_i}}\),随后根据 CRT 求得 \(x\).

  2. 对于上述每一个 \(i\),记 \(p = p_i\), \(\alpha = \alpha_i\),可以使用以下给出的高效算法求得 \(x \pmod{p^\alpha}\)

    1. 构造以 \(c = b^{n/p}\) 的对数表。注意该表的大小为 \(p\).

    2. \(x \pmod{p^\alpha}\)\(p\)-展开,即求满足 \[x \equiv x_0P^0 + x_1P^1 + \cdots + x_{\alpha-1}p^{\alpha-1} \pmod{p^\alpha}\]\(x_0, \cdots, x_{\alpha-1}\),其中 \(0 \le x_i < p\)。依据以下递归公式: \[ \begin{array}{ll} y_0 = y, &x_0 = DL_c(y^{n/p})\\ y_i = y_{i-1} / b^{x_{i-1}p^{i-1}}, &x_i = DL_c(y_i^{n/p^{i+1}}) \end{array} \] 注意到 \(y_i^{n/p^{i}}\) 确实存在于第一步构造的对数表里。

因此对于任何离散对数密码系统,都应该避免选择其阶对于某个较小的数 B 来说是 B-平滑的 的数。最好的选择是阶为某个足够大的素数的数。

对于 \(p = 37, b = 2, y = 28\),在 \(\mathbb{F}_p^\times\) 中求 \(x = DL_b(y)\)\(\mathbb{F}_{37}^\times\) 中的 \(DL_2(28)\)

解:因式分解 \[ \begin{aligned} n &= ord(2) = 36\\ &= 2^2 \cdot 3^2\\ &= P_1^{\alpha_1}P_2^{\alpha_2} \end{aligned} \]

于是有 \[ \begin{aligned} P_1 = 2, P_2 = 3\\ \alpha_1 = 2, \alpha_2 = 2 \end{aligned} \]

首先记 \(P = P_1 = 2\),此时求 \(x \bmod 2^2\) \[ \begin{aligned} c_1 = 2^\frac{36}{2} &\equiv -1 \pmod{37}\\ &\equiv 36 \pmod{37} \end{aligned} \]

因此循环子群 \(<c_1>\)\(\{1, 36\}\),且幂表为 \[ \begin{array}{ll} 0 & 1\\ \hline 1 & 36 \end{array} \] 因此对数表为 \[ \begin{array}{ll} 1 & 36\\ \hline 0 & 1 \end{array} \]

为了求 \(x \bmod 4\),记

\[x \equiv 2^0x_0 + 2^1x_1 \pmod 4\]

\[ \begin{array}{lll} y_0 = y = 28 & \begin{aligned} x_0 &= DL_c(28^\frac{36}{P^1})\\ &= 0 \end{aligned} & 28^\frac{36}{2} \equiv 1 \pmod{37} \\\hline \begin{aligned} y_1 &= y_0 / b^{x_0P^0}\\ &= y_0 = 28 \end{aligned} & \begin{aligned} x_1 &= DL_c(28^{36 / P^2})\\ &= 1 \end{aligned} & \begin{aligned} 28^\frac{26}{4} &\equiv -1 \pmod{37}\\ &\equiv 36 \pmod{37} \end{aligned} \end{array} \]

因此有 \(x \equiv x_0 + 2x_1 \pmod 4 \equiv 2 \pmod 4\).

类似地,记 \(P = P_2 = 3\),此时求 \(x \bmod 3^2\) \[ c_2 = 2^\frac{36}{3} \equiv 26 \pmod{37} \]

因此循环子群 \(<c_2>\)\(\{1, 26, 10\}\),且幂表为 \[ \begin{array}{ll} 0 & 1 & 2\\ \hline 1 & 26 & 10 \end{array} \] 因此对数表为 \[ \begin{array}{ll} 1 & 10& 26\\ \hline 0 & 2 & 1 \end{array} \]

为了求 \(x \bmod 9\),记

\[x \equiv 3^0x_0 + 3^1x_1 \pmod 9\]

\[ \begin{array}{lll} y_0 = y = 28 & \begin{aligned} x_0 &= DL_c(28^\frac{36}{P^1})\\ &= 1 \end{aligned} & 28^\frac{36}{3} \equiv 26 \pmod{27} \\\hline \begin{aligned} y_1 &= y_0 / b^{x_0P^0}\\ &= y_0 = 28 / 2^{1 \cdot 1} = 14 \end{aligned} & \begin{aligned} x_1 &= DL_c((28 / 2^1)^{36 / P^2})\\ &= 2 \end{aligned} & \begin{aligned} 14^4 &\equiv 10 \pmod{27}\\ &\equiv 36 \pmod{37} \end{aligned} \end{array} \]

因此有 \(x \equiv x_0 + 3x_1 \pmod 9 \equiv 7 \pmod 9\).

因此 \[ \begin{aligned} x &\equiv 2 \pmod 4\\ x &\equiv 7 \pmod 9 \end{aligned} \stackrel{CRT}{\implies} x \equiv -2 \pmod{37} \equiv 34 \pmod{37} \]

所以在 \(\mathbb{F}_{37}^\times\)\(DL_2(28) = 24\).

方法3: 指数计算法(Index Calculus)

该方法基于在 \(\mathbb{Z}\)(或 \(\mathbb{F}_p^\times[x]\),即 \(\mathbb{F}_p^\times\) 上的多项式)中 找到一组合适的“因数基”(factor basis) \(\mathfrak{B}\). 其利用了 \(\mathbb{F}_p^\times\) 是通过在 \(\mathbb{Z}\) 上的模运算构造出来的(\(\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}\))。类似地,也可以从 \(\mathbb{F}_p[x]\) 中构造出有限域。

我们以 \(\mathbb{Z}\) 为例,若能得到一组 factor basis \(\mathfrak{B}\),则可通过以下步骤完成攻击:
1. 对于每个 \(b\in\mathfrak{B}\),求 \(x(b) = DL_g(b)\).
2. 找到这么一个 \(t\in\mathbb{Z}\) 使得 \(yg^t\)\(\mathfrak{B}\)-平滑 的,即有满足以下关系的可算函数 \(e(b)\): \[ yg^t = \prod_{b\in\mathfrak{B}} b^{e(b)} \] 3. 求解以下线性离散对数方程: \[ x = DL_g(y) \equiv \sum_{b\in\mathfrak{B}} x(b)e(b) - z \pmod n \]

注意,\(\mathfrak{B}\) 的选择十分微妙。若 \(\mathfrak{B}\) 过小,第三步的方程是实际上不可解的。而若 \(\mathfrak{B}\) 过大,第一步的耗时又使得其计算不可行。合适的基目前仅在 \(G = \mathbb{F}_p^\times\) 中已知存在,而我们并不知晓在后文将讨论的基于椭圆曲线的密码系统中所使用的 \(G = E(\mathbb{F}_p^\times)\) 中是否也存在(更勿论如何找出)这样的基。

例如,若 \(G = \mathbb{F}_p^\times\),其中 \(p\) 为素数,确定 \(B << p\), 并取 \[\mathfrak{B} = \{\text{素数 } p \le B\}\]

\(G = \mathbb{F}_q^\times\),其中 \(q = p^n\), \(p\) 为素数,确定 \(M < n\),并取 \[\mathfrak{B} = \{ p(x) \in \mathbb{F}_p[x] : deg(p) \le M, p(x) \text{ 不可约}\}\]

\(G = \mathbb{F}_p^\times\),那么该方法给出的是一个次指数时间复杂度的算法:

\[Time(\text{解 $DLP$}) = L_p(\frac{1}{2}, c)\]

其中 \(c > 0\), 且

\[L_p(r, c) = \Theta(e^{c(\log p)^r(\log \log p)^{1-r}})\]

因此我们需要注意到,在基于 \(G = \mathbb{F}_q^\times\) 的离散对数密码系统中我们选择的密钥大小 \(n\)(同理 \(q\))比基于 \(G = E(\mathbb{F}_q)\) 的应该大很多才能保证同样程度的安全。

Pollard's \(\lambda\)\(\rho\) 方法

\(\lambda\) 方法讨论了利用通过随机分布产生的生日问题对离散对数的攻击。该方法因其生成的两条伪随机数序列相交时的场景类似于希腊字母 \(\lambda\) 而得名。由于 \(\lambda\) 方法有时也指一种平行运算版本的 \(\rho\) 方法,因此 Pollard 更喜欢称此方法为袋鼠方法。我们掠过具体的算法,因为类似的 \(\rho\) 算法更为有趣。

在同一篇论文中提出的 \(\rho\) 方法也基于“随机游走”:构造一个函数 \(f = f_y : G \to G\),其中 \(y_k = f^k(y_0)\) 符合递归关系 \(y_k = g^{x_k}y^{z_k}, k = 1, 2, \cdots\)。可以证明,其中有 \(y_{k+t_i} = y_k\),因此有关系 \[ (x_k - x_{k+t_i}) \equiv x(z_k+t_i - z_k ) \pmod n \]

\(x\) 可依据此关系求得。

其中由于数列 \(y_k\) 在某点后循环在图像上类似希腊字母 \(\rho\),该算法因此而得名。

时间复杂度:\(\Theta(\sqrt{n})\) 次乘法运算,其中对循环的判断由于使用了龟兔赛跑算法,因此可以实现 \(\Theta(1)\) 的空间复杂度。