BSGS | xXxYOLOxXx

Baby Step Giant Step – 小步大步算法

用于求解形如 $a^x ≡ b \mod n$ 的问题( $gcd(a, n) = 1, x < n$ )
将x转为 $i*m - j$ 的形式
$a^x ≡ b \mod n$
$a^{(i*m - j)} ≡ b \mod n$
$a^{(i*m)} ≡ b*a^j \mod n$
对于右边，j遍历[0, m-1]，计算结果进行存储
对于左边，i遍历[0, $\frac{n}{m}$ ]，计算结果在右边的存储中进行搜索

计算时间复杂度为O( $\frac{n}{m}+m$ )
当 $\frac{n}{m} = m$ 时
即 $m = \sqrt{n}$ 时
计算时间复杂度最小，为O( $2\sqrt{n}$ )

例如：[网鼎杯2020青龙组] you_raise_me_up
m, c, n已知来求flag

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
import random

n = 2 ** 512
m = random.randint(2, n-1) | 1
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)

# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

sage中可使用的离散对数求解函数：

discrete_log
discrete_log_rho
discrete_log_lambda
bsgs

但是这里使用bsgs会直接使python执行进程退出，只能使用discrete_log

n = 2 ** 512
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
flag = discrete_log(c, mod(m,n))
print(long_to_bytes(flag))

而之前的digits_missing中只能使用bsgs，使用discrete_log的效率太低

p = 8652390958861741435444627047576503554063739935043923776101303146382894597047179400211376204501335462644199685775560596374016398617315983998885273252232383
q = 11398271496284943396462023942239673376393494680988625153067750611899511451472208462647358820098737289431021205366418955146690406049973272066743297095335701
n = p * q
m = 119734924542618020546820838777476635357941645923563189966789686819064058863592
c = 56409941327407928550531590953236316964802997285515886345082618240072551829663483576336544664403443682438280485868042844696756568731554243773790500024504963753053241086872006291605136092928526547169334420024477141471212559780737725850766070778466019859345735742281733141983853509548060639633435609434590536531
F = IntegerModRing(n)
flag = bsgs(F(m), F(c), (0, 2**32))
print(flag)

查阅相关资料之后再，对比来看：

bsgs算法虽然时间复杂度为O( $2\sqrt{n}$ )，但是可以借助已知条件来限定flag值的范围，从而极大地提高了该函数的效率
而discrete_log函数基于的算法为：Pohlig-Hellman and Baby step giant step. Pohlig-Hellman算法与(n-1)的因数分解相关，对于易分解的(n-1)，使用该函数的效果更佳

另外也有扩展BSGS的情况( $gcd(a, n) > 1$ )