BSGS

BSGS 算法介绍

大步小步算法利用的是中间相遇的思想，使得计算复杂度从暴力枚举 $O(n)$ 降为 $O(\sqrt{n})$。

考虑离散对数问题 $g^x\equiv c\bmod q$，$x\in [0, q-1]$。我们设 $m=\lceil \sqrt{q}\rceil$，并记 $x=Am+B$，那么$A,B<m$。从而离散对数问题即：

$\begin{aligned}g^{Am+B}=c\\ g^{Am}=c\cdot g^{-B} \end{aligned}$

现在将 $A$ 所有可能的值遍历一遍，预计算出所有的 $g^{Am}$，通过哈希表存储。随后再遍历 $B$ 的所有可能值计算 $c\cdot g^{-B}$，并用哈希查找这个值是否以及存储在表中。如果有则 $Am+B$ 即为所求。

强网杯2023 dlp

这里举一道利用中间相遇思想的例子。题目源码：

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
flag = 'flag{d3b07b0d416ebb}'

assert len(flag) <= 45
assert flag.startswith('flag{')
assert flag.endswith('}')

m = bytes_to_long(pad(flag.encode(), 128))

p = 0xf6e82946a9e7657cebcd14018a314a33c48b80552169f3069923d49c301f8dbfc6a1ca82902fc99a9e8aff92cef927e8695baeba694ad79b309af3b6a190514cb6bfa98bbda651f9dc8f80d8490a47e8b7b22ba32dd5f24fd7ee058b4f6659726b9ac50c8a7f97c3c4a48f830bc2767a15c16fe28a9b9f4ca3949ab6eb2e53c3
g = 5

assert m < (p - 1)

c = pow(g, m, p)

with open('out.txt', 'w') as f:
    print(f"{p = }", file=f)
    print(f"{g = }", file=f)
    print(f"{c = }", file=f)

这里 flag 的长度就没说得很清楚，让人以为有40多个字符，而实际上只有18个，并且内容全都是十六进制字符。至于做法就是将内容分成两部分，再利用中间相遇的思想。

注意到 $m$ 是 flag 经过 pad后转过来的，所以 $m$ 可以写成：$m=Ax+By+d$，这里 $x$ 是flag内容的前面一半，y是后面一半。所以离散对数问题就是：

$g^{Ax+By+d}\equiv c\bmod q$

记 $c^′=c\cdot g^{-d},u=g^A,v=g^{-B}$，那么：

$u^x=c^′v^y$

随后遍历 $y$，存储 $c^′v^y$，再遍历 $x$ 可以求出 $m$。

exp:

需要注意的是，计算快速幂gmpy2的powmod比python自带的pow效率更高。

import string
from itertools import product 
from gmpy2 import *

p = 173383907346370188246634353442514171630882212643019826706575120637048836061602034776136960080336351252616860522273644431927909101923807914940397420063587913080793842100264484222211278105783220210128152062330954876427406484701993115395306434064667136148361558851998019806319799444970703714594938822660931343299
g = 5
c = 105956730578629949992232286714779776923846577007389446302378719229216496867835280661431342821159505656015790792811649783966417989318584221840008436316642333656736724414761508478750342102083967959048112859470526771487533503436337125728018422740023680376681927932966058904269005466550073181194896860353202252854

half_len = 6
flag_length = len('flag{}') + half_len * 2
d = b'}' + long_to_bytes(128 - flag_length) * (128 - flag_length)
b = 256 ** (len(d) + half_len)
a = bytes_to_long(b'flag{') * 256 ** (len(d) + half_len * 2)
u = pow(g, b, p)
v = pow(g, -256 ** len(d), p)
d = bytes_to_long(d)
c_ = (c * pow(g, -a, p) * pow(g, -d, p)) % p

lowercase_hex_chars = string.hexdigits[:16]
combination = [bytes_to_long(''.join(chars).encode()) for chars in product(lowercase_hex_chars, repeat=6)]

from tqdm import tqdm
ans = {}
for y in tqdm(combination):
    key = (c_ * powmod(v, y, p)) % p
    ans[key] = y

100%|████████████████████████████████████████████████████████████████████| 16777216/16777216 [05:28<00:00, 51001.90it/s]

for x in tqdm(combination):
    temp = powmod(u, x, p)
    if temp in ans:
        print(b'flag{' + long_to_bytes(x) + long_to_bytes(ans[temp]) + b'}')
        
 38%|██████████████████████████▍                                          | 6425972/16777216 [01:59<03:14, 53116.21it/s]
b'flag{61e8007dd65f}'
 49%|█████████████████████████████████▌                                   | 8161868/16777216 [02:32<02:40, 53597.89it/s]