2023 强网杯 discrete_log

题目 > 2023 DLP BSGS

发布时间 : 2023-12-21 16:08

字数:862 阅读 :

题目源码
分析
1. 同余式转化
  1. 第一步
  2. 第二步
2. BSGS
  1. 大步
  2. 小步
解题

题目源码

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)

p = 173383907346370188246634353442514171630882212643019826706575120637048836061602034776136960080336351252616860522273644431927909101923807914940397420063587913080793842100264484222211278105783220210128152062330954876427406484701993115395306434064667136148361558851998019806319799444970703714594938822660931343299
g = 5
c = 105956730578629949992232286714779776923846577007389446302378719229216496867835280661431342821159505656015790792811649783966417989318584221840008436316642333656736724414761508478750342102083967959048112859470526771487533503436337125728018422740023680376681927932966058904269005466550073181194896860353202252854

分析

离散对数问题，flag填充到128长度，但是flag长度未知

比赛的时候以为给的假flag是flag的高位，赛后得知flag里面的长度是12，可能是根据爆破难度来推测长度的，因为用到了bsgs法，相当于爆6位的[0-9a-f]，再长一点就很难爆破了

得知flag长度后，我们把同余式转化成 \(c \equiv g^{flag} \mod{p}\) 的形式，方便最后进行bsgs

同余式转化

第一步

将flag头尾和padding先移到c那边，得到c1，因为padding+'}'的长度是111，此时有 \(c_1 \equiv (g^{flag})^{2^{111 \times 8}} \mod{p}\)（这里以及后面说的flag都是指flag花括号里的内容）

flag_pattern = bytes_to_long(pad(b"flag{" + b"\x00" * 12 + b"}", 128))
c1 = c * pow(g, -flag_pattern, p) % p

第二步

令 \(g_1 = g^{2^{111 \times 8}}\)，有 \(c_1 \equiv g_1^{flag} \mod{p}\)

g1 = pow(g, 2**(111*8), p)

这里还有一种做法，就是把 \(2^{111 \times 8}\) 也移到c那边，因为这个 \(p\ \%\ 4 = 3\)，可以用到Rabin里的思想

assert p % 4 == 3
for _ in range(111*8):
    c1 = pow(c1, (p+1)//4, p)

这样，就有 \(c_1 \equiv g^{flag} \mod{p}\)，也就是说后面的步骤直接用g = 5

但是经过尝试，发现用g和用g1的爆破速度基本一样，所以不如直接用g1

BSGS

根据大步小步法，因为flag长度是12，令 \(flag = im + j\)，其中 \(m = 2^{6 \times 8}\)，\(0 < i < m\)，\(0 < j < m\)

因为 \(c_1 \equiv g_1^{flag} \equiv g_1^{im + j} \mod{p}\)，有 \(c_1 (g_1^{-m})^i \equiv g_1^j \mod{p}\)

大步

左边先乘c1，然后每次乘上n次的\(g_1^{-m}\)（这里写n次是因为flag的字符只有[0-9a-f]，遍历的时候存在“跳跃”，所以n不一定为1）

遍历完所有结果存进字典dic中

g1m_inv = pow(g1, -2**(6*8), p)
left = c1
for i in tqdm(range(len(flag))):
    left = left * pow(g1m_inv, bflag[i+1] - bflag[i], p) % p
    dic[left] = i

小步

右边每次乘上n次的\(g_1\)

每次乘完得到的值判断是否在dic中，如果存在，即left = right，说明找到了正确的i、j

right = 1
for j in tqdm(range(len(flag))):
    right = right * pow(g1, bflag[j+1] - bflag[j], p) % p
    if right in dic.keys():
        i = dic[right]
        print(i, j)

解题

from Crypto.Util.number import *
import itertools
from Crypto.Util.Padding import pad
from tqdm import tqdm

p = 173383907346370188246634353442514171630882212643019826706575120637048836061602034776136960080336351252616860522273644431927909101923807914940397420063587913080793842100264484222211278105783220210128152062330954876427406484701993115395306434064667136148361558851998019806319799444970703714594938822660931343299
g = 5
c = 105956730578629949992232286714779776923846577007389446302378719229216496867835280661431342821159505656015790792811649783966417989318584221840008436316642333656736724414761508478750342102083967959048112859470526771487533503436337125728018422740023680376681927932966058904269005466550073181194896860353202252854

flag_pattern = bytes_to_long(pad(b"flag{" + b"\x00" * 12 + b"}", 128))
c1 = c * pow(g, -flag_pattern, p) % p
g1 = pow(g, 2**(111*8), p)

dic = {}

flag = list(itertools.product("0123456789abcdef", repeat=6))
bflag = [0] + [bytes_to_long("".join(_).encode()) for _ in flag]

g1m_inv = pow(g1, -2**(6*8), p)
left = c1
for i in tqdm(range(len(flag))):
    left = left * pow(g1m_inv, bflag[i+1] - bflag[i], p) % p
    dic[left] = i

right = 1
for j in tqdm(range(len(flag))):
    right = right * pow(g1, bflag[j+1] - bflag[j], p) % p
    if right in dic.keys():
        i = dic[right]
        print(i, j)  # 6416384 8246879
        print("".join(flag[i] + flag[j]))  # 61e8007dd65f

"""
100%|██████████| 16777216/16777216 [01:48<00:00, 154175.60it/s]
 49%|████▉     | 8244395/16777216 [00:52<00:54, 155872.85it/s]6416384 8246879
61e8007dd65f
100%|██████████| 16777216/16777216 [01:47<00:00, 156349.35it/s]
"""

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 skatexu@qq.com