Discrete logarithm problem

发现自己只是知道离散对数很难求，而且自己拿这玩意也没办法，专门来学一下带老婆问题

基本定义

生成元

​ 在一个群 G 中，如果 g 是 G 的生成元，即所有 G 中的所有元素都可以被表示成 $y = g^x$ ，此时的 x 我们称为 y 在 G 中的对数

阶

​ 设 $m\geq 1$ ， $gcd(a,m)=1$ ，使得 $a^d=1\pmod{m}$ 成立的最小正整数 d 称为 a 对模 m 的指数或者阶，我们一般将其记为 $\delta_m(a)$

​ 另：满足 $a^d=1\pmod{m}$ 的d一定满足 $d\mid\varphi(m)$

原根

​ 当 $\delta_m(a)=\varphi(m)$ 时，称 a 是模 m 的原根，简称 m 的原根

​ 只有 $m=2,4,p^\alpha,2p^\alpha （p为奇素数，\alpha为正整数）$ 时，模 m 的剩余系存在原根（充要条件）

离散对数

暴力枚举

万物皆可暴力

1
2
3
4
def ForceDLP(A,B,P):
    for i in range(P):
        if pow(A,i,P)==B:
            return int(i)

Baby-step giant-step

又称北上广深算法 带老婆去了北上广深（bushi

已知 $y = g^x$ ，我们不妨假设 $x=i\cdot m+j$ ，$m = \sqrt{x}$ ，这样 $m^2>n$ ，则这时候一定在[0,m]内存在一组(i,j)满足 $x=i\cdot m+j$

具体做法就是：因为 $y = g^x=g^{i\cdot m+j}$ ， 则 $y\cdot (g^{-m})^i=g^j$ ，所以我们首先枚举所有的j并存在一个盒子里，接着枚举i，如果能找到相同的结果，这说明我们得到了(i,j)

据说

  • 每一次 j 的增加表示 “baby-step”，一次乘上 $g$
  • 每一次 i 的增加表示 “giant-step”，一次乘上 $g^{-m}$
1
2
3
4
5
6
7
8
9
10
11
def BSGS(g, y, p):
    m = int(sqrt(p))
    if not is_square(p):
        m += 1
    S = {pow(g, j, p): j for j in range(m)}
    gs = pow(g, inverse(m, p), p)
    for i in range(m):
        if y in S:
            return i * m + S[y]
        y = y * gs % p
    return None

Pohlig-Hellman Algorithm

​ 这种方法适用于当p-1是个光滑数，因为p是个质数，所以 $\varphi(p)=p-1$ ，根据唯一分解定理，我们可以假设 $p-1 =q_1^{e_1}\cdot q_2^{e_2}\cdot q_3^{e_3}\cdots q_n^{e_n}$ ，我们首先分解 $p-1$ 得到因子列表listq，接着计算每一个因子对应的 $g^{\frac{p-1}{q^e}}$ 与 $h^{\frac{p-1}{q^e}}$ ，此时我们就可以较轻松地计算出满足 $({g^{\frac{p-1}{q^e}}})^x=h^{\frac{p-1}{q^e}}\pmod{p}$ 的x'，而此时的x'也满足 $x’ =x\pmod{p^e}$ ，那么我们可以通过许多的因子来得到许多的x'，最后通过CRT即可找到我们最终要求的x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Crypto.Util.number import *
from gmpy2 import *
import time

# g^x = h (mod p)
def PohligHellmanDLP(g,h,p):
    Lq=pollard_rho_Factor(p-1)
    assert reduce(lambda x,y: x*y, Lq) == p-1
    print(Lq)
    Lg=[pow(g,(p-1)//i,p) for i in Lq]
    Lh=[pow(h,(p-1)//i,p) for i in Lq]
    length=len(Lq)
    La=[]
    for i in range(length):
        La.append(ForceDLP(Lg[i],Lh[i],p))
    X=CRT(Lq,La)
    if pow(g,X,p)==h:
        print("Found x! x =",X)
        return X
    else:
        print("Error!")

p=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
g=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
h=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
start_time=time.time()
x = PohligHellmanDLP(g,h,p)
print(x)
print("it takes",time.time()-start_time,"seconds",)