离散对数——Discrete Logorithm

2024-12-10

离散对数问题，Discrete Logorithm Problem，简称DLP，是非对称密码学所依赖的极为重要的数学难题之一。
经典DLP问题描述：
给定 $g^x \equiv c (mod p) （g,x < p）$，由 $(g,x)$ 计算 $c$ 很容易（快速幂取模），但由 $(g,c)$ 计算 $x$ 是困难的。

即使是BSGS等攻击方法，依然必须涉及“爆破”一步，即在x的可能范围内逐个数值尝试是否能让等式成立。

离散数学（广义上）DLP问题描述：设循环群 $G_p$ 的阶为 $n$。
给定群内的任意元素 $A \in G_p$ 及 $x < n$，计算 $C = x \cdot A$ 很容易，但给定 $C$、$A$，求解 $x$ 是困难的。
这里x代表A执行二元运算的次数，对于经典DLP，其为模p环下的乘法运算；对于ECDLP，其为椭圆曲线上的加法运算。

给定$C,x$，可以计算 $A = x^{-1} \cdot C$，此时 $x^{-1}$ 应理解为 $x$ 在 $Zmod(n)$ 下的逆元。

由DLP问题衍生出的 Diffle-Hellman 密钥交换：
假设Alice和Bob希望在一个不安全的环境下进行密钥交换。他们协商密钥交换在 $G_p$ 上进行，选定生成元 $G$ 并公开。
Alice和Bob分别产生一个私钥 $d_A$ 和 $d_B$，分别计算 $A = d_A \cdot G$ 与 $B = d_B \cdot G$，将 $A$、$B$ 发送给对方并公开。
随后，他们再分别使用私钥和对方发送的密钥计算 $AB = d_A \cdot B = d_B \cdot A$。在阿贝尔群上其正确性显然。
此时双方就已经完成了密钥交换，共享密钥就是AB。外人即使知道了 $(G_p,G,A,B)$，亦很难从中获得$d_A$或$d_B$，进而保证了共享密钥 $AB$ 的安全性。

攻击方法概览

暴力攻击，在n较小时，攻击者可以枚举所有的 $x \in (0,n)$ 逐个校验。
BSGS(Baby-step Giant-step，大步小步法，~~又名“亦步亦趋”~~)，通过制造碰撞来“用空间换时间”。

大步小步法的空间复杂度与时间复杂度均为 $O(\sqrt n)$。暴力攻击的二者显然分别为 $O(1)$ 及 $O(n)$。

Pohlig-Hellman攻击
Pollard's kangaroo algorithm
Pollard's rho algorithm

上述是较为通用的解法，对于部分 $G_p$ 存在特有的攻击方法，比如ECDLP下的Smart's Attack、MOV Attack等。

另外，有一些循环群可能求解 $G_p$ 上的离散对数问题并不困难，比如 $Zmod(p)$ 上的加法运算可以快速求解。

细讲

以下内容干货（纸面资料）过多，~~小心噎着~~

BSGS —— 亦步亦趋

BSGS本质是在试着制造碰撞，利用散列表查找复杂度为常量的优势，以空间换时间。
具体操作方法如下：设待求解 $C = x \cdot G$ 中的x，
记 $T = \sqrt n$，$R = G \cdot T^{-1}$；制备一个散列表集合 $S = {i \cdot G}，i \in [0,C)$
随后遍历 $j \in [0,C)$，若 $C + j \cdot R \in S$ ，则说明碰撞成功，得到 $x = jT + i$。
显然遍历中一定会存在一次碰撞。

“大步小步”的命名之源：

如上式，$i$ 每增加1，$x$ 增加1，所谓一“小步”；$j$ 每增加1， $x$ 增加 $\sqrt n$ ，所谓一“大步”。

这种攻击思想在轮加密/类轮加密的攻击（含哈希碰撞）中也有较多应用，思路即为将密钥拆为两部分，将中间值进行碰撞。

~~为了便于理解，~~给出一段示意BSGS求解 $GF_p$ 下DLP问题的代码

def dlog(p:int,c:int) -> int:
    g = 2 #假设目标是求解pow(2,x,p)==c中的p
    t = int(pow(p,1/2))
    r = pow(2,-t,p)

    dc = {}
    for i in range(t):
        dc[g] = i
        g = (g * 2) % p
    
    for j in range(t):
        if c in dc: #找到碰撞
            return dc[c] + j * t
        c = (c * r) % p

    return None

Pohlig-Hellman —— 韩信点“兵”

Pohlig-Hellman 利用了群论中的拉格朗日定理和中国剩余定理。
其攻击对象是阶的小因子之积过小的循环群，在这些群上，可以求解(部分)阶比较小的子群的离散对数问题；
对这些结果应用中国剩余定理，即可获得原群上离散对数问题的结果。

群中的拉格朗日定理：如果 $G_P$ 是 $G$ 的一个子群，则 $ord(G_P)$ 一定整除 $ord(G)$。

攻击成立的两个场景：
- 目标群的阶的全部因子都很小，a.k.a.“光滑数”(smooth-number)；
- 目标运算数计数 $x$ 小于目标群的阶的小因子之积（实际上第一种情况可以看作是第二种情况的特例）。

实现上，我们令 $n = $ $\prod_{i=1}^m{p_i^{e_i}}$。对于每个因子 $f = p_i^{e_i}$，考虑 $C^{'} = f \cdot C$，$G^{'} = f \cdot G$。
此时 $C^{'}$ 在群中的阶为 $\frac{n}{f}x$，$G^{'}$ 的阶则为 $\frac{n}{f}$。
根据拉格朗日定理，此时以 $G^{'}$ 为生成元的子群的阶只有 $f$，且 $C^{'}$ 亦在这个群上，故可以在这个低阶子群上求解DLP。
依此法求解的 $\{x_i\}$ 满足 $x_i \equiv x (mod p_i^{e_i})$。

对于第一种情况，显然 ${p_i^{e_i}}$ 互素，故将所有等式联立至CRT中，求出通解 $x^{'} = x_0 + kn'$，令 $k=0$ 即可获得 $x$。
对于第二种情况，假设存在 $x < r$，则可以升序求解模 $p_i^{e_i}$ 下的DLP，只需要求解出的 $\prod_{i=1}^m{p_i^{e_i}} > r$ ，即可令CRT求解出的 $x^{'}$ 模数大于 $r$，进而获得 $x$。

还是直接上代码：

def ph_attack(p:int,c:int,intact: bool = True) -> int: #仍旧是pow(2,x,p) == c
    g = 2
    
    #约定，factor(x)返回一个list，每个元素是形如(prime,factor)的tuple
    #约定，预置了discrete_log(a,g)返回int，作用为给定(g,a)，求解群中满足a = x * g的x，其可以采用暴力攻击、BSGS等方法进行
    #约定，函数crt(r,m)可以对给定两个等长的列表，且m各元素互质时，求CRT问题的基础解(k=0)
    rls = []
    mls = []

    n = p - 1 #Zmod(p)的阶

    #对于第一种情况的攻击，即不知道x的额外信息，完全攻击每个子群
    if intact:
        for pm,exp in factor(n):
            cur = pow(pm,exp)
            fc = n // cur
            temp_g = pow(g,fc,p)
            temp_c = pow(c,fc,p)
            mls.append(cur)
            rls.append(discrete_log(temp_c,temp_g))

    #对于第二种情况的攻击，攻击部分子群，其实只需要记录已经求解的模数之积，伺机break
    else:
        Sentinel = pow(2,32) #x的上界
        mul = 1
        for pm,exp in factor(n):
            cur = pow(pm,exp)
            fc = n // cur
            temp_g = pow(g,fc,p)
            temp_c = pow(c,fc,p)
            mls.append(cur)
            rls.append(discrete_log(temp_c,temp_g))
            mul *= cur
            if mul > Sentinel:
                break

    return crt(rls,mls)

因此，为使任意场景实例化的DLP问题抵抗Pohlig-Hellman攻击，该群的阶或应没有小因子（最好阶自身就是大质数），或其小因子极少且乘积极小。

对于 $Zmod(p)$ 上的离散对数问题，一般会要求p是质数的同时，$\frac{p-1}{2}$ 为质数（或没有小因子）。

$p$ 是质数时，其阶 $\phi(p) = p-1$，显然此时 $2$ 是其阶的一个因子，令其阶的另一个因子是质数，同时约束 $x>2$，即可确保其最大限度地抵抗Pohlig-Hellman攻击。

只要一个群的阶不是质数，那么Pohlig-Hellman总能通过转而攻击子群，降低求解该群上DLP问题的复杂度。

sagemath中内置了求解离散对数相关的工具：

#sage
p = 7
E = EllipticCurve(Zmod(p),[0,2])
A = E.random_point()
G = E.gens()[0]

#经典调用方法，discrete_log是一个通用化的函数，第一参数为结果，第二参数为底，内置方法就是Pohlig-Hellman和BSGS

#指定operation相当于约定了特定的运算（对于EllipticCurve默认为'+'，对于Zmod(p)默认为'*'）
print(discrete_log(A,G,operation='+')) 

#还可以指定bounds=(a,b)来引导sage来利用上述Pohlig-Hellman攻击中的第二种情况
print(discrete_log(A,G,operation='+',bounds=(0,5))) #假设x的上界为5