楚慧杯(原题杯)抽象lcg

DASCTF(2024楚慧杯原题杯)的一道抽象lcg做题过程

一些吐槽

为什么翻遍全网都没有这道题wp，对于真菜的我，手搓有点难泵

做题过程

from Crypto.Util.number import *
from random import *
from secret import flag

LENGTH = 512
RATIO = 0.02024
M = 2**LENGTH
a, b, seed = getPrime(LENGTH), getPrime(LENGTH), getPrime(LENGTH)
SEED = seed


x = []
for i in range(64):
    seed = (a*seed + b) % M
    x.append("".join([bin(seed)[2:].zfill(LENGTH)[i] if uniform(0,1) < RATIO else "*" for i in range(LENGTH)]))


print("c =", bytes_to_long(flag) ^ SEED)
print("a =",a)
print("b =",b)
print("x =",x)

尝试模拟一个类似情

from Crypto.Util.number import *
from random import *
a = 7048435472566573813031570507837890091364947084306630050544242220147807292350445564322172244244726206563452305566866223414437853917448623276909090327076693
b = 9204853069421046007176344891235245198607052139715825810823076231566533652655127030214860066312526149219510111657539481375881111759200483396551737326166933
f=b'flag{yoxi_nidi_liangmin}'
m=bytes_to_long(f)
M=2**512
seed=8656702749867102422219200570484898209691959687594188444284921871713214793286935518322058853234901407306874127174670521978953484935737586264798208150365287
RATIO=0.6
Seed=seed
print(seed)
x=[]
for i in range(3):
    seed = (a * seed + b) % M
    print(seed)
    x.append("".join([bin(seed)[2:].zfill(512)[i] if uniform(0,1) < RATIO else "*" for i in range(512)]))
print(seed)
print(x)
c=m^Seed
print(c)

我把显示数据百分比调高了一点，因为测试如果太低就是出现错误结果。这行代码加密逻辑跟原题一样。过程也很简洁

我们使用z3约束。由于是才学的z3有的，写的时候也有些问题，比如定义

BitVec向量在转换的时候会出现类型错误。这是改进后的解开上述脚本的代码

from z3 import *


num = [[BitVec(f'num[{i},{j}]', 512) for j in range(1)] for i in range(3)]
a = 
b = 
M = 2**512


A = []
s=Solver()



seed = []


for i in range(3):
    for j in range(512):
        if A[i][j] == '0':
            s.add(Extract(511-j, 511-j, num[i][0]) == 0)
        elif A[i][j] == '1':
            s.add(Extract(511-j, 511-j, num[i][0]) == 1)



for i in range(2):
    s.add(num[i+1][0] == (a * num[i][0] + b) % M)


if s.check() == sat:
    model = s.model()
    Seed=model[num[0][0]]

接下来看一下题目本身

64此Lcg递推，得到64个被大部分隐藏的二进制位我们需要求到第一个被递归的再反推出SEED。解密过程看起来还算简单但是，计算也需要时间我的脚本大概算了半个小时。
补充

Extract这一部分是定义起始和结束位置

from z3 import *


num = [BitVec(f'num[{i}]', 512) for i in range(64)]#有点像二维数组，是重点得理解一下,512这里是num[i]一个的大小。我们定义j


a = 7048435472566573813031570507837890091364947084306630050544242220147807292350445564322172244244726206563452305566866223414437853917448623276909090327076693
b = 9204853069421046007176344891235245198607052139715825810823076231566533652655127030214860066312526149219510111657539481375881111759200483396551737326166933
M = 2**512
c = 168815802663712138791999335515513916578434659976069633486645257813364375941625207868153496481655635421252190634818222465004994343266249958687663356753760620029589052494330932123212
A=[]

s=Solver()

seed = []

for i in range(64):
    for j in range(512):
        if A[i][j] == '0':
            s.add(Extract(511-j, 511-j, num[i]) == 0)
        elif A[i][j] == '1':
            s.add(Extract(511-j, 511-j, num[i]) == 1)#定义替换位置


for i in range(63):
    s.add(num[i+1] == (a * num[i] + b) % M)

if s.check() == sat:

    model = s.model()
    Seed=model[num[0]]
    print(Seed)
然后
'''
3109110488358343346016940967694590460203057088734099480714916540569545873216239855284197469883314735576988812243170940490083088872700634135415701390964362
'''
a_1 = pow(a, -1, M)
seed = (a_1 * (Seed - b)) % M
m = c ^ seed
print(long_to_bytes(m))
'''
b'DASCTF{0n\x85\xb8\xffU_know_th3_polynomial_0F_D47a_you_can_m@ke_Use_of_Leak_bits!}'
'''