密码学算法 - BSGS 算法二 | Alice and Bobの神秘小屋

上一章我们介绍了 BSGS（Baby-Step Giant-Step）算法的基本原理和实现方法，帮助大家快速求解离散对数问题。接下来，我们将继续深入探讨 BSGS 算法的另一种应用。除了在离散对数问题中，BSGS 算法也可以用于求解 ECC（Elliptic Curve Cryptography）中的离散对数问题，这在现代密码学中具有重要的实际意义。

欢迎来到《密码学核心算法实战》的 BSGS 算法二专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。

ECC中的BSGS算法 🌟

在 ECC 中，离散对数问题的形式是：给定一个椭圆曲线 $E$ 上的点 $P$ 和 $Q$，找到一个整数 $k$ 使得 $Q = kP$。这个问题被称为椭圆曲线离散对数问题（ECDLP），是 ECC 加密算法安全性的基础。而 BSGS 算法可以用来求解 ECDLP，从而在某些情况下破解 ECC 加密。

ECC中的BSGS算法的原理 😵

既然有前一章的铺垫，那么原理就直接简单讲解了。

求解 $x$ 使得 $Q = xP$，我们可以将 $x$ 表示为 $x = i \cdot m - j$，其中 $m = \lceil \sqrt{n} \rceil$，$i \in [0, m)$ （大步），$j \in [0, m)$ （小步）。这样我们可以将 ECDLP 转化为以下形式：

$i \cdot mP = Q + jP$

小步（Baby Step）：计算 $Q + jP$，对于 $j \in [0, m)$，将结果存入哈希表（键为点的坐标，值为 $j$）。每次都是加 $P$，所以叫做小步。

大步（Giant Step）：计算 $mP$，对于 $i \in [0, m)$，计算 $i \cdot mP$，检查是否在哈希表中存在对应的点，如果存在，则可以得到 $x = i \cdot m - j$。每次都是加 $mP$，所以叫做大步。

ECC中的BSGS算法的实现 🙃

import math

class EllipticCurve:
    def __init__(self, a, b, p):
        self.a = a
        self.b = b
        self.p = p

    # 求逆元 (Fermat's little theorem)
    def inverse(self, val):
        return pow(val, self.p - 2, self.p)

    # 点加运算 P + Q
    def add(self, P, Q):
        if P is None: return Q
        if Q is None: return P

        x1, y1 = P
        x2, y2 = Q

        if x1 == x2 and (y1 + y2) % self.p == 0:
            return None # 也就是无穷远点 O

        if P == Q:
            # 斜率 k = (3x^2 + a) / 2y
            lam = (3 * x1 * x1 + self.a) * self.inverse(2 * y1) % self.p
        else:
            if x1 == x2: return None # 垂直切线
            # 斜率 k = (y2 - y1) / (x2 - x1)
            lam = (y2 - y1) * self.inverse(x2 - x1) % self.p

        x3 = (lam * lam - x1 - x2) % self.p
        y3 = (lam * (x1 - x3) - y1) % self.p
        return (x3, y3)

    # 标量乘法 k * P (Double-and-Add 算法)
    def multiply(self, k, P):
        res = None
        current = P
        while k > 0:
            if k % 2 == 1:
                res = self.add(res, current)
            current = self.add(current, current)
            k //= 2
        return res

def bsgs_ecc(curve, P, Q, order):
    """
    ECC 上的 BSGS 算法
    求解 x 使得 Q = xP
    原理: x = i * m - j => i * mP = Q + jP
    :param curve: 椭圆曲线对象
    :param P: 基点 (Generator)
    :param Q: 目标点 (Public Key)
    :param order: 群的阶 n (或者一个足够大的数)
    :return: 离散对数 x
    """

    # 1. 计算步长 m = ceil(sqrt(n))
    m = math.ceil(math.sqrt(order))

    # 2. 小步 (Baby Step)
    # 计算 Q + jP，其中 j ∈ [0, m)
    # 我们构建一个哈希表: { Point: j }

    step_dict = dict()
    current_point = Q # 初始值为 Q + 0P

    for j in range(m):
        # 将点作为 key 存入 (注意点需要是可哈希的类型，元组是可以的)
        if current_point not in step_dict:
             step_dict[current_point] = j
        # 下一步：Q + (j+1)P = (Q + jP) + P
        current_point = curve.add(current_point, P)

    # 3. 大步 (Giant Step)
    # 计算 i * (mP)，其中 i ∈ [1, m] (通常遍历到 m+1 保证覆盖)

    # 先算出 mP
    mP = curve.multiply(m, P)

    current_giant = mP # 初始值为 1 * mP

    for i in range(1, m + 1):
        # 检查 i * mP 是否在 Baby Steps 中
        if current_giant in step_dict:
            j = step_dict[current_giant]

            # 找到碰撞：i * mP = Q + jP
            # Q = i * mP - jP = (i * m - j) P
            x = i * m - j
            return x

        # 下一步：(i+1)mP = imP + mP
        current_giant = curve.add(current_giant, mP)

    return None

SageMath 偷懒 🤓👆

有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻
有的，兄弟有的，这样的算法在 SageMath 中早就已经被封装好了🤫，我们直接调用就行了：

from sage.all import discrete_log
# 1. 定义椭圆曲线 E: y² = x³ + ax + b mod p
p = p
E = EllipticCurve(GF(p), [a, b])  # 格式：EllipticCurve(有限域, [a, b])，对应 y²=x³+ax+b

# 2. 定义基点 P 和公钥 Q
P = E(x_p, y_p)  # 基点 
Q = E(x_q, y_q)  # 公钥 
n = P.order()

# 3. 求解离散对数：找 x 使得 x*P = Q（底层用BSGS/Pollard's Rho等算法，更加完善）
private_key = discrete_log(Q, P, n, operation='+')
print(f"私钥 x = {private_key}")

怎么样，是不是非常简单？🤣👉🤡

上一章：密码学算法 - BSGS一算法 👈
下一章：密码学算法 - AMM 算法 👈
回到开始：关于我 👈

相关链接：
加解密模式分析 - ECC 加密算法 👈