Pollard ρ for DLP：思考与推导

openSource
约 16 分钟阅读

阅读量:2次
DLP
目标：从问题设定出发，系统推导 Pollard ρ 随机游走算法用于离散对数（DLP）的正确性、复杂度与工程化细节；给出改进（r-adding、negation/自同构加速、并行化）与伪代码。默认在素数阶循环群 $G=\langle g\rangle$ 上讨论，$|G|=n$ 为素数；一般情形见§1.3。

1. 设定与不变式

1.1 离散对数问题（DLP）

给定生成元 $g\in G$ 与 $y\in G$，求 $x\in\{0,\dots,n-1\}$ 使
$$g^x=y.$$

1.2 表示与不变式

算法维护三元组 $(a_k,b_k,X_k)$ 满足
$$X_k = g^{a_k} y^{b_k}, \qquad a_k,b_k\in\mathbb{Z}_n.$$
这是核心不变式；从 $(a_0,b_0,X_0)=(0,0,1)$ 或任意合法种子出发，迭代时确保该式始终成立。

1.3 群阶非素时

若 $|G|=N$ 非素，典型做法是工作在素数阶子群 $\langle g\rangle$（阶 $n\mid N$ 为素），或将结果在各素因子模上解后用 CRT 合并。下文默认 $n$ 素，以保证 $(b_j-b_i)$ 的可逆性（见 §2.2）。

2. 随机游走与碰撞方程

2.1 r-分区迭代（通用形式）

取一个近似均匀的分区函数 $\Pi:G\to\{1,\dots,r\}$（例如哈希若干比特），并预生成 $r$ 组更新常数
$$C_i=(\alpha_i,\beta_i),\quad 1\le i\le r,$$
定义迭代：若 $\Pi(X_k)=i$，则
$$(a_{k+1},b_{k+1},X_{k+1})=(a_k+\alpha_i,\ b_k+\beta_i,\ X_k\cdot g^{\alpha_i} y^{\beta_i})\ (\bmod n),$$
显然保持不变式。经典三分法是 $r=3$ 且三类更新分别是乘以 $g$、平方、乘以 $y$；上式是其推广（Teske 的 r-adding 走法）。

2.2 碰撞推出对数

若存在 $i\ne j$ 使 $X_i=X_j$，由不变式得
$$g^{a_i} y^{b_i} = g^{a_j} y^{b_j} \Rightarrow g^{a_i-a_j}=y^{b_j-b_i}=g^{x(b_j-b_i)}.$$
于是
$$x \equiv (a_i-a_j)\cdot(b_j-b_i)^{-1} \pmod n,$$
其中逆元在 $\mathbb{Z}_n$ 中计算；当 $n$ 为素时，$b_j\ne b_i$ 的概率为 $1-\tfrac{1}{n}$ 近似 1。若出现 $b_j\equiv b_i$，可更换迭代函数或重启。

2.3 ρ 形状与生日悖论

将迭代视作对大小为 $n$ 的集合的"近似随机映射"。随机映射理论与生日悖论给出首次碰撞的期望步数
$$\mathbb{E}[T_\text{coll}]\approx \sqrt{\tfrac{\pi n}{2}}.$$
轨迹分解为"尾长" $\mu$ 与"环长" $\lambda$（ρ 的圆环部分），其期望均约为 $\sqrt{\tfrac{\pi n}{8}}$。这就是名称"ρ"的来源。

随机映射假设是启发式（迭代函数需"混合良好"）；选择合适的 $r$、分区与更新常数可避免短周期/退化。

3. 复杂度与常数因子

  • 时间：期望群运算次数 $\approx \sqrt{\tfrac{\pi n}{2}}$。对椭圆曲线阶 $n\approx 2^{256}$，常数因子随实现细节（分区、negation、梯形法等）有 10%–30% 的浮动。
  • 空间：原始 ρ 常数空间（$O(1)$），使用判圈或"显著点"（distinguished points, DP）并行化时需存少量检查点。

4. 判圈与并行

4.1 判圈（单机）

  • Floyd 乌龟–兔子：维护 $X_k$ 与 $X_{2k}$；当相等时得到碰撞索引（但未必给出两个不同 $(a,b)$，需回溯）。
  • Brent 法：分块指数增长，减少比较次数，实践中略快。

4.2 显著点与 van Oorschot–Wiener 并行

选一判定谓词 $D(X)$（如"高 $t$ 位为 0"），满足 $\Pr[D]=2^{-t}$。各工作进程从不同种子独立游走，遇到显著点即上报三元组 $(a,b,X)$。当两条链汇聚到同一显著点，即得碰撞并解出 $x$。

  • 并行加速：理想情况下 $M$ 个进程的期望总工作量 $\approx \sqrt{\tfrac{\pi n}{2M}}$。
  • 存储/通信：期望链长 $2^t$，内存保存 $\tilde O(\sqrt{n/M})$ 个显著点即可。

5. 重要改进与工程细节

5.1 r-adding 走法（Teske）

  • 取 $r\in[8,32]$（经验值），预表 $T[i]=g^{\alpha_i}y^{\beta_i}$。
  • 步进：$X\leftarrow X\cdot T[\Pi(X)]$；$a\leftarrow a+\alpha_{\Pi(X)}$, $b\leftarrow b+\beta_{\Pi(X)}$。
  • 好处：更好的混合与更少退化周期；常数因子改善（5%–30%）。

5.2 Negation 与自同构加速（ECC）

在椭圆曲线群上，利用 $\nu(P)= -P$ 的阶 2 自同构，将状态空间按 $\{P, -P\}$ 归类，可期望减少搜索空间一半，时间常数改善 $\approx\sqrt{2}$ 倍。更一般地，若有阶 $t$ 的自同构群 $H$，速度可提升 $\sqrt{t}$。

5.3 规避退化与"空耗"

  • 避免"平方"过多导致短环；r-adding 中用随机 $(\alpha_i,\beta_i)$。
  • 发生 $b_j\equiv b_i$ 或循环很短时，改变哈希/常数并重启。
  • 非素阶：先投影到素数阶子群，否则方程不能解或得到 $x$ 仅模某因子。

6. 形式化推导：期望碰撞时间

将迭代视作 $S$ 上大小 $|S|=n$ 的随机函数 $f:S\to S$。前 $t$ 步皆互异的概率为
$$\Pr[\text{no collision up to }t]=\prod_{k=0}^{t-1}\left(1-\frac{k}{n}\right) \approx \exp\left(-\frac{t(t-1)}{2n}\right),$$
因此首次碰撞时间 $T$ 的分布近似满足
$$\Pr[T>t]\approx \exp\left(-\tfrac{t^2}{2n}\right),\qquad \mathbb{E}[T] = \int_0^{\infty}\Pr[T>t]\,dt \approx \sqrt{\tfrac{\pi n}{2}}.$$
这与生日悖论给出的 $2^{n/2}$ 级别一致。

7. 伪代码（两种常用变体）

7.1 Floyd 判圈（r-adding 版本）

input: G, g, y, n (prime), r, partition Π, table T[i]=(α_i, β_i, g^{α_i} y^{β_i})

function state(x, a, b):
    i = Π(x)
    new_x = x * T[i].val  # group operation
    new_a = (a + T[i].α) % n
    new_b = (b + T[i].β) % n
    return (new_x, new_a, new_b)

# Initialize
x, a, b = 1, 0, 0  # starting point: g^0 y^0 = 1
X, A, B = state(x, a, b)  # hare: one extra step

while True:
    # Tortoise: 1 step
    x, a, b = state(x, a, b)
    
    # Hare: 2 steps  
    X, A, B = state(X, A, B)
    X, A, B = state(X, A, B)
    
    if x == X:  # collision detected
        if (B - b) % n == 0:
            # Degenerate case, restart with new parameters
            continue
        xlog = ((a - A) * mod_inverse(B - b, n)) % n
        return xlog

7.2 显著点并行（van Oorschot–Wiener）

# Worker process
def worker(seed):
    x, a, b = seed
    while True:
        x, a, b = state(x, a, b)
        if is_distinguished(x):  # e.g., low t bits are zero
            send_to_server(x, a, b)
            x, a, b = generate_new_seed()  # restart with new seed

# Server process  
def server():
    seen = {}
    while True:
        receive (x, a, b) from worker
        if x in seen:
            (a_prev, b_prev) = seen[x]
            if (b - b_prev) % n != 0:
                xlog = ((a_prev - a) * mod_inverse(b - b_prev, n)) % n
                return xlog
        else:
            seen[x] = (a, b)

8. 与其他算法的比较

  • BSGS：时间 $\Theta(\sqrt{n})$、空间 $\Theta(\sqrt{n})$。若内存紧张，ρ 优势明显；若内存充足且需确定时间上界，BSGS 更稳定。
  • Pohlig–Hellman：当 $n$ 有小素因子时更快；常与 ρ 结合，先拆分到各素因子模上。
  • Index Calculus/NFS-DL：仅对 $\mathbb{F}_p^\times$（及其扩域）适用；椭圆曲线无已知子指数级算法，故 ECC 更短密钥达同等安全。

9. 实用参数与小抄

  • r-adding：$r\in[8,32]$，$(\alpha_i,\beta_i)$ 随机独立；$\Pi$ 用哈希高/低若干比特。
  • DP：选择 $t$ 使得链长 $\approx 2^t$ 与网络/存储平衡（常取 $t\in[16,24]$）。
  • ECC negation：归约到商群 $E/\langle\pm1\rangle$，理想速度提升 $\sqrt{2}$。
  • 期望步数：$\sqrt{\tfrac{\pi n}{2}}$；并行 $M$ 核约为 $\sqrt{\tfrac{\pi n}{2M}}$。

添加新评论