Baby-step giant-step (BSGS)

条件

$$当n较小时，在群阶n的平方根级别时间内求解g^x=h，适用于阶n小于等于2^{40}$$

原理 中间相遇攻击

$$设G使一个n阶循环群，生成元为g，已知h=g^x，求x$$

$$记x=i\cdot m+j，其中m=\lceil \sqrt n \rceil,则方程变为：$$

$$g^{i \cdot m+j}=h \qquad \Rightarrow \qquad g^j=h\cdot (g^{-m})^i$$

  • $$Baby step:计算所有g^j$$
  • $$Giant step:计算所有h\cdot (g^{-m})^i$$

$$若LHS=RHS，即可得到x=im+j$$

算法实现

1.sagemath bsgs函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
p = 
g = Mod(, p)
h = Mod(, p)
n = p - 1   #群阶

x = bsgs(g, h, (0, n))   # Sage 内置 bsgs 函数，返回一个解
print(x)  # 输出 4258
p =
a, b = 
E = EllipticCurve(GF(p), [a, b])
G = E(,)
Q = E(,)
n = G.order()   #阶

# 导入 Sage 内置的 bsgs 函数
from sage.groups.generic import bsgs
d = bsgs(G, Q, (0, n))
print(d)

2.手动实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def bsgs_ec(G, Q, n):
    """
    BSGS for elliptic curve additive group.
    G: base point (order n)
    Q: target point (Q = x*G)
    returns x (0 <= x < n)
    """
    m = ceil(sqrt(n))
    # Baby steps
    baby = {}
    current = G * 0  # 无穷远点 O
    for j in range(m):
        if current not in baby:   # 避免重复（理论上不会有，因为阶足够大）
            baby[current] = j
        current = current + G     # (j+1)G
    # Giant steps: compute factor = -m*G
    factor = -m * G
    current = Q
    for i in range(m + 1):
        if current in baby:
            j = baby[current]
            return i * m + j
        current = current + factor
    return None  # not found (should not happen)

Pllard’s rho 算法

条件

用于求离散对数问题的概率算法，与BSGS相比，空间复杂度极低，适用于在有限内存环境中处理大规模群，常用于在阶为2^40到2^60范围内。

核心思想：生日悖论与循环检测

生日悖论

典：一间教室内，至少需要多少人才能使至少有两人生日相同的概率超过50%

答：23

数学推导：

$$记N=365，随机选择k个人，他们的生日两两不同的概率是：$$

$$P(B)=\Pi_{i=0}^{k-1} (1-\frac{i}{N})$$

$$当x很小时，1-x \rightarrow e^{-x}代入：$$

$$P(B) \rightarrow e^{-\Pi _{i=0}^{k-1} \frac{i}{N}}=e^{-\frac{k(k-1)}{2N}}$$

目标：

$$P(A)>0.5 \Leftrightarrow P(B) <0.5$$

$$\Leftrightarrow \qquad \frac{k(k-1)}{2N} < ln2$$

$$\Leftrightarrow \qquad k<\sqrt {2N\cdot ln2} \approx 22.5$$

推广：

$$从一个大小为N的集合中随机选取一些元素，期望碰撞次数为\sqrt {\frac{\pi N}{2}}$$

循环检测

$$在一个有限集合上迭代一个确定性函数f:S \rightarrow S,从任意起点x_0出$$

$$序列x_0,x_1=f(x_0),x2=f(x_1),…必然进入一个循环$$

经典算法：Floyd判圈算法，Brent算法

Pohlig-Hellman算法

简介

Pohlig-Hellman算法是一种求解离散对数问题的算法，适用于群的阶为光滑数，将原始的大规模DLP问题分解为一系列小阶子群上的DLP，再通过CPT算出最终解

原理

$$对于循环群G：阶为n，生成元为g，n=\Pi_{i=1}^k p_i^{e_i}$$

$$已知h \equiv g^x \pmod n，求x$$

$$对于每个素数幂p^e，求解x \pmod {p^e}$$

  1. $$我们先求出x \pmod p$$

$$令g_0=g^{\frac{n}{p}},h_0=h^{\frac {n}{p}}，那么g_0^p=g^n=1_G，即有g_0的阶为p$$

$$而h_0=(g^x)^{\frac{n}{p}}=(g^{\frac{n}{p}})^x=g_0^x，因此在阶为p的子群上，可以用BSGS或Pollard’s rho求解x \pmod p,记为x_0$$

  1. $$提升到x \pmod {p^e$$

考虑亨泽尔提升或逐次逼近

逐次递推逼近：

$$假设已知x_j \pmod {p^j},目标：确定x_{j+1} \pmod {p^{j+1}}$$

$$令x=x_j+t \cdot p^j,其中未知数t \in [0,p)，已知：$$

$$g^{x_j+t \cdot p^j}=h \Rightarrow g^{t \cdot p^j}=h \cdot g^{-x_j}$$

$$令g_j=g^{p^j},注意到g_j的阶为\frac{n}{gcd(p_j,n)}=p^{e-j},RHS=h \cdot g^{-x_j}$$

$$需要解： g_j^t=h_j$$

$$此时，等式两边的元素都属于一个阶为p^{e-j}的循环子群，由于t \in [0,p)，实际上可以将问题约化到p的子群上：$$

  • $$计算g_j’=g_j^{p^{e-j-1}},其阶为p，计算h_j’=h_j^{p^{e-j-1}}$$
  • $$则(g_j’)^t=h_j’,这是一个阶为p的子群上的DLP，可解到t$$

$$于是得到了x_{j+1}=x_j+t \cdot p^j，逐次递推逼近即可得到x \pmod {p^e}$$

  1. CRT

$$对每个素数幂p_i^{e_i} 求出x_i \pmod {p_i^{e_i}},然后中国剩余定理：$$

$$x \equiv \Sigma_{i=1}^k x_i \cdot M_i \cdot M_i^{-1} \pmod n \qquad 其中M_i=\frac{n}{p_i^{ei}},M_i^{-1} \pmod {p_i^{e_i}}$$

代码实现

1.离散对数求解 discrete_log

1
2
3
4
5
6
p = 
g = 
h = 
x = discrete_log(h, g, ord= ,operation='+/*')
#h 目标值；g 生成元；ord 阶（可无）；operation 运算类型
print(x)

2.有限域GF(p)上的离散对数 GF(p).multiplicative_generator()

1
2
3
4
5
F = GF(p)
g = F.multiplicative_generator()   # 原根
h = 
x = g.log(h)                       # 或 h.log(g)
print(x)

3.椭圆曲线上的离散对数

1
2
3
4
5
E = EllipticCurve(GF(p), [a,b])
P = E(,)     # 生成元
Q = E(,)     # 已知倍点
x = discrete_log(Q, P, ord=P.order(), operation='+')
print(x)