密码学-06-针对离散对数的攻击

许多公钥密码系统都依赖于离散对数计算十分困难的特性，离散对数越难计算，那么密码系统就越安全。离散对数的安全性跟它所基于的群关系非常大，通常来说群的阶越高，计算离散对数越困难。但是除了阶的大小，群本身的结构也会影响离散对数的安全性。

为了安全性，离散对数通常定义在模乘法群上，其中为质数。针对离散对数密码系统的攻击，表示找到一种高效的算法，求解使其满足，其中为的生成元，。本文我们讲解的攻击方法都基于这个群。

暴力破解法

将穷举 1 到，直到找到一个数使成立。由于，因此这种算法的复杂度为。

看起来是一个可以接受的复杂度，但是在密码学中一般会取一个很大的数字，因此我们一般用的二进制位数来衡量复杂度，假如有个二进制位，那么复杂度为，这就是一个指数级的复杂度了。因此暴力破解法是个很低效的办法。对于大于 100 位的数就已经很难解了，对于大于上千位的数，暴力破解法消耗的时间甚至超过了太阳的寿命，因此认为不可解。

大步小步法

大步小步法（Baby-Step Giant-Step）是对暴力破解法的一个改进，是算法如下：

计算。
假设，其中，。
因此有，有。
对于在范围内的每个，计算，并且存储起来。
计算的值。
将从到循环，计算，每计算一次，就查找第 4 步中有没有相等的。如果找到，则退出循环，离散对数的解为。

该算法的时间复杂度和空间复杂度为，也即。虽然比暴力算法快很多，但是当足够大时，该算法也不可解。

算法中对循环一次相当于走了一小步，对循环一次相当于一大步，大步小步法因此而得名。

Pohlig-Hellman 算法

前面两种算法对群的阶没有要求，适用于任何群，但是效率不高，对于阶太大的群不适用。密码学家 Pohlig 与 Hellman 在 1978 年发明一种算法，可以用于破解群的阶为光滑数的离散对数，这个算法以两位作者的名字命名为 Pohlig-Hellman 算法。

在理解这个算法之前，先要理解什么是光滑数（Smooth Integer）。

光滑数

在数论中，如果一个数的所有质因数都小于等于 B，就称这个数为B-光滑数（B-Smooth Integer）。例如，因此是一个 7-光滑数。

需要注意的是，一个数被称作是B-光滑数，并不需要 B 是这个数的质因数，只需要 B 大于或等于这个数的每一个质因数就行。例如上面的 15750 也可以被叫做 8-光滑数、9-光滑数、11-光滑数，等等。

算法思想

设群的阶为，根据群的性质可知，设其质因数分解为如下形式：

对如下等式：

我们将两边同时求次幂得到：

交换一下右边的指数得到：

设，，则有：

因为的阶为，所以上述等式是在一个阶的子群上求离散对数，满足等式的解都模同余，设其中一个解为，则解可以表示为：

对于的每个都做如上操作，可以得到如下方程组：

利用中国剩余定理，可以求得满足上诉线性方程组的解，方程组的每个解都模所有的乘积同余，也即模同余，设其某一个解为，则通解可以表示如下：

通过这种方式我们就求得了的解。

在求解时可以利用大步小步法，时间复杂度为，但是如果太大，算法效率还是不够高。

好在对于阶为一个质数的幂的情况，有一个效率很高的算法。为了简化符号，令，。将做进制展开：

其中任意满足。只要想办法求出每个，我们就可以得到。

令

其中。当时，令

由此我们可以看到满足一个递推的关系：

下面我们对求次幂：

$其中为一个整数$

最终我们得到如下等式

其中的阶为。因此通过上述等式求相当于在一个阶的群上求解离散对数，利用大步小步法，其时间复杂度为。求出所有的复杂度为，这比之前的复杂度要好太多。另外由于计算涉及到升幂操作，可以利用逐次平方，其复杂度为。

对于的每个因子都用上诉算法求解，最终 Pohlig-Hellman 的算法复杂度为

从这个复杂度可以看出，只要的阶是一个 B 足够小的 B-光滑数，使用 Pohlig-Hellman 算法求解离散对数问题将会变得非常简单。

防范针对离散对数的攻击

要使离散对数是安全的，首先要保证的阶足够大。其次，根据 Pohlig-Hellman 算法，的阶还需要至少有一个很大的质因数，也就是在上面的描述中，中至少有一个数非常大。从群论的角度讲，需要有一个阶非常大的子群。

的阶为，假设它有一个非常大的质因数，设，为一个整数，且根据质数的性质，一定为偶数，这样可以表示为。在设计离散对数的时候，需要精心挑选，计算，使得落入阶为的子群中。这样根据和，求离散对数才会很困难。有时候为了方便，我们选择的生成元甚至不是的生成元，而是阶子群的生成元。

安全质数

对于这种形式的质数，当时，称为安全质数（Safe Prime），也就是质数可以写成的形式，其中也为质数，也被称为Sophie Germain 质数（Sophie Germain prime）。

使用安全质数的群，其子群结构非常简单，其子群的阶只可能为：、、、或者，其中实际上为本身的阶。阶子群的生成元只有一个，就是，因为。因此，只要随机从选一个数，其要么是阶子群的生成元，要么是阶子群的生成元。在实际工程应用中，通常选择作为生成元，这会使计算变得很简单。求解离散对数将会是在阶子群或者阶子群上求解，如果是在阶子群上求解，攻击者最多只能知道的值，能泄露的信息非常少，不足以求解离散对数。

因此使用非常大的安全质数（通常大于1024比特位）将会使离散对数变得十分安全。

参考文献
[1] Baby-step giant-step: https://en.wikipedia.org/wiki/Baby-step_giant-step
[2] An Improved Algorithm for Computing Logarithms over GP(p) and Its Cryptographic Significance: https://ee.stanford.edu/~hellman/publications/28.pdf
[3] Smooth number: https://en.wikipedia.org/wiki/Smooth_number
[4] The Pohlig-Hellman Algorithm: http://anh.cs.luc.edu/331/notes/PohligHellmanp_k2p.pdf
[5] Safe and Sophie Germain primes: https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes
[6] How to Backdoor Diffie-Hellman: https://eprint.iacr.org/2016/644.pdf