Pohlig-Hellman攻击

在ECC中，Pohlig-Hellman攻击可以用来降低特定情况下的离散对数问题的求解难度。

我们知道想要破解ECC最大的难题是ECDLP，即椭圆曲线离散对数问题

假设我们已经知道了椭圆曲线上的基点G和公钥Q，想要从Q=kG中求解私钥k目前没有找到比朴素算法更优的解决方案

我在学习这块内容的时候突然有了个疑惑（之前完全没意识到，好奇怪），就是为什么椭圆曲线加密使用的是Q = kG，却被称作离散对数问题？对数在哪？这不就是看起来很普通的乘法吗？

那我们就先跳出椭圆曲线，先来研究有限域乘法群

$设在\color{blue}有限域\mathbb{F}_P^{*}$，定义运算*为模p乘法，在该有限域中存在生成元g，使得$h=g^k\mod{p}$，离散对数就是已知h和g求解k的过程。这样显然k的表达式会出现对数，且由于运算进行在有限群中，所以称为离散对数

上面$h=g^k\mod{p}$，显然可以写为$h = g*g*g+....\mod{p}$的形式

那是不是与我们标量乘法$Q=G+G+G+....$有点相似呢

这里的G也是群的生成元，k一样表示有多少个G参与运算，所以我们把Q=kG也认为是离散对数问题。

那我们知道了这俩玩意极为相似，我们还是继续研究有限域乘法群吧

p是质数，那有限域的阶p-1是个合数对吧（应该不会有人取p为2或3吧…）

那p-1就可以有若干个因数，我们可以把p-1写为：$p-1 = q_1^{e_1}q_2^{e_2}q_3^{e3}....q_n^{e_n}$

好那我们已经把p-1给分解了，分解的结果已知

把$h=g^k\mod{p}$两边同时做$\frac{(p-1)}{q_i^{e_i}}$次幂

得到$h^{\frac{(p-1)}{q_i^{e_i}}} = g^{k\frac{(p-1)}{q_i^{e_i}}}$

用$h_i和g_i来方便表示：h_i = g_i^k$

那我们又要想了，g是有限域的生成元，它的阶为p-1($g^{p-1}\equiv1 \mod{p}$)

那$g_i$的阶应当是$q_i^{e_i}$，也就是说假如原本g经过k次幂才能得到$h_i$的值，把g换成$g_i$的化，k次幂可能很多是多余的（k可能大于$q_i^{e_i}$,这样子话k次幂其实就等价于$k\mod{q_i^{e_i}}$次幂）

所以我们就有关系式：

$$k\equiv k_i \mod{q_i^{e_i}}$$

到这里顿时柳暗花明了，这不是中国剩余定理吗

好那我问你,$k_i$怎解，现在$h_i和g_i$都很好求，这不是还是离散对数问题吗？拿不到$k_i$的值啊！

但是，我们评估离散对数问题的复杂程度，有公式$T≈exp(c⋅(logp)^{1/3}⋅(loglog\ p)^{2/3})$

倘若我们的p,即$q_i^{e_i}$变的很小，时间复杂度也会很小

于是我们终于进入了正题：

当有限域乘法群的阶n可以分解成若干个小因数时，可以利用Pohlig-Hellman攻击降低离散对数的求解难度

而我们上述的分析过程，其实就是Pohlig-Hellman算法

总结一下，步骤就是：

1. 分解目标群的阶 n=p-1 为素因子幂乘积：$n=q_1^{e_1}q_2^{e_2}q_3^{e3}....q_n^{e_n}$
2. 对每个素因子幂$q_i^{e_i}$:
   • 计算群元素的 $n/q_i^{e_i}$ 倍
   • 求解子群上的离散对数 $k_i$（模 $q_i^{e_i}$）
3. 通过**中国剩余定理（CRT）**合并所有 $k_i$，得到原离散对数 k（模 n）

这一步骤于ECC中的Q=KG一样适用，只不过这里的n会变为椭圆曲线上所有点的个数，可以使用sage来方便的计算。

等我把sage用明白，会在这里贴一个完整的脚本

另外本文重点讲的是Pohlig-Hellman算法的原理，更细的步骤比如怎么求$k_i$会包括在脚本里