menu gh0st
BSGS和PH
261 浏览 | 2021-03-16 | 阅读时间: 约 2 分钟 | 分类: CRYPTO学习 | 标签: CRYPTO
请注意,本文编写于 264 天前,最后修改于 221 天前,其中某些信息可能已经过时。

Baby-step giant-step

这一方法通常被称为小步大步法,这一方法使用了中间相遇攻击的思想。

我们可以令 x=im+j,其中 m=⌈√n⌉ ,那么整数 i 和 j 都在 0 到 m 的范围内。

因此:y = gx = g im+j

也就是: y (g  -m  ) = g

那么我们就可以枚举所有的 j 并进行计算,并将其存储到一个集合 S 中,然后我们再次枚举 i,计算 y (g -m ) i ,一旦我们发现计算的结果在集合 S 中,则说明我们得到了一个碰撞,进而得到了 i 和 j。

这显然是一个时间与空间的折中的方式,我们将一个 O(n)的时间复杂度,O(1)空间复杂度的算法转换为了一个O(√n) 的时间复杂度和O(√n)的空间复杂度的算法。

其中

  • 每一次 j 的增加表示 “baby-step”,一次乘上 g。
  • 每一次 i 的增加表示 “giant-step”,一次乘上 g−m
def bsgs(g, y, p):
    m = int(ceil(sqrt(p - 1)))
    S = {pow(g, j, p): j for j in range(m)}
    gs = pow(g, p - 1 - m, p)
    for i in range(m):
        if y in S:
            return i * m + S[y]
        y = y * gs % p
    return None
#在sagemath中使用
R = GF(941)
y = R(390)
g = R(627)
x = discrete_log(y, g)  # 347
assert g**x == y

# 另一种方法
x = y.log(g)  # 347
assert g**x == y

pohlig-hellman

前面我们介绍了BSGS算法,但是BSGS算法时间复杂度很大,在实际操作中可能因为不高效而无法求解,这里引出Pohlig-Hellman算法。

Pohlig-Hellman算法一开始是用来解决离散对数问题,后来也有用在ECC上,这里我们讲讲Pohlig-Hellman算法是怎么用在离散对数上吧。

首先,Pohlig-Hellman算法有一个前提条件:p是素数且p-1存在较小的质因子。P.S.我们以下的运算mod p 省略。

我们已知

ord(g) = N = q_1^{e_1}*q_2^{e_2}*...*q_t^{e_t}

这时候,假如我们有更高效的算法求出x mod q1e1 ,x mod q2e2 ,... ,x mod qiei 这些式子的值的话就可以用CRT求解x mod N ,我们知道CRT速度是非常快的。

现在我们设有ri = x mod qiei ,这里我们把Qi = qiei ,这里我们知道 x = ki*Qi + ri,而对于g,我们知道g的阶是N,有gN = 1,所以

y^{N/Q_i} = (g^x)^{N/Q_i} = g^{k_i*N}*g^{r_i*N/Q_i} = (g^{N/Q_i})^{r_i}

左边的yN/Qi可以计算,右边的(gN/Qi)也是知道的(把Qi一个个带进去运算即可),这样子原来的问题就转化成新的离散对数问题,这个离散对数问题的解就是ri,而在这个新的离散对数问题中,(gN/Qi)的阶不是p-1或N,而是Qi,也就是qiei,这和原来的N相比降低了很多——从N降到了质因子的ei次幂。所以我们的算法模型很清楚了:解出上述 i个新的离散对数问题,得到 r1,r2,⋯,ri,最后利用 CRT 将结果合并起来。

进一步优化:上面存在一种特殊情况,即当N是一个很小质数的某次方,那么上面的优化就等于啥也没做,复杂度还是很高,但是前面得到的新的离散对数问题是:(gN/Qi)ri = yN/Qi,这里底数的阶是Qi = qiei,也就是一个质数的幂,这里我们把x写成q进制的形式:

x = x_0+x_1*q^2+...+x_{e-1}*q^{e-1} where 0<=x_i<q

这里我们按照上面的思路可以得到:

y^{q^{e-1}} = (g^x)^{q^{e-1}} = g^{(x_0+x_1*q+x_2*q^2+...)q^{e-1}}=g^{x_0q^{e-1}}*g^{q^e(x_1+x_2q+...)} = g^{x_0q^{e-1}} = (g^{q^{e-1}})^{x_0}

左边的yqe-1和右边的(gqe-1)x0都可以求出来,于是求x0又转化成一个新的离散对数问题,而这个底数(gqe-1)的阶是q,所以相对效率会高很多,同样的,x1,x2...等等都可以算出来,就是把上面式子的1改成i即可。

SageMath 里面的 discrete_log 就是利用 Pohlig-Hellman 和大步小步算法实现的。只需要调用 discrete_log 即可。

#在sagemath中使用,同上面的代码
R = GF(941)
y = R(390)
g = R(627)
x = discrete_log(y, g)  # 347
assert g**x == y

发表评论

email
web

全部评论 (共 1 条评论)

    2021-03-16 21:05
    数学公式部分插件弄不来,建议复制用md打开食用