前言

这个比赛感觉多多少少有点惊吓到我了，开赛差不多三个小时，结果零解，吓死。

题目

fl@g

task

from Crypto.Util.number import *
from sympy import *
from tqdm import *
from itertools import *
from math import factorial
import string

table = string.ascii_letters + string.digits + "@?!*"

def myprime():
    num = 0
    for i in tqdm(permutations(table) , total=factorial(len(table))):
        temp = "".join(list(i))
        if("flag" in temp or "FLAG" in temp or "f14G" in temp or "7!@9" in temp or "🚩" in temp):
            num += 1
    return nextprime(num)

m = bytes_to_long(flag)
n = myprime()*getPrime(300)
c = pow(m,65537,n)

print("n =",n)
print("c =",c)

'''
n = 10179374723747373757354331803486491859701644330006662145185130847839571647703918266478112837755004588085165750997749893646933873398734236153637724985137304539453062753420396973717
c = 1388132475577742501308652898326761622837921103707698682051295277382930035244575886211234081534946870195081797116999020335515058810721612290772127889245497723680133813796299680596
'''

思路
首先分析代码，

permutations(table) , total=factorial(len(table))

对table的66个字符进行全排列，然后统计里面有"flag"，"FLAG"，"f14G"，"7!@9"，"🚩"的次数，如果你直接用这个函数算，也可以算出来，就是有点慢()。
题目里面说了是组合数学，就是高中的排列组合。
首先🚩就是个整活的，说以实际上就四个。
首先四个每个里面都是四个字符，当作一个整体，那么就是63个，进行全排列，就是63!，一共四个，所以乘4，
然后想到里面会有两个两个同时出现的情况，所以也要减去，那么就是减去60！，一共四组，注意有重复字母的不可能同时出现，
最后想三个重复的情况，只有一组，就是57!*3，但是上一组已经减过头了，所以要加上一组补上去，那么就出来了

exp

from Crypto.Util.number import *
from sympy import *
from tqdm import *
from itertools import *
from math import factorial
import string

table = string.ascii_letters + string.digits + "@?!*"
n = 10179374723747373757354331803486491859701644330006662145185130847839571647703918266478112837755004588085165750997749893646933873398734236153637724985137304539453062753420396973717
c = 1388132475577742501308652898326761622837921103707698682051295277382930035244575886211234081534946870195081797116999020335515058810721612290772127889245497723680133813796299680596

print(len(table))
x=factorial(63)*4-factorial(60)*4+factorial(57)
print(x)
print(nextprime(x))
p=7930399977709836210408886944838540258627004066353629452237535203485317857280000000000083
q=n//p
d=inverse(65537,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

easy_random(复现)

task

import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

flag = b'WKCTF{}'
pad_flag = pad(flag,16)
key = random.randbytes(16)
cipher = AES.new(key,AES.MODE_ECB)
print(cipher.encrypt(pad_flag))
# b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'
with open('random.txt','w') as f:
    for i in range(2496):
        f.write(str(random.getrandbits(8))+'\n')

赛时思路

看到random.getrandbits(8)就联想到了MT19937算法，这一点没有想错，然后和一个师傅讨论尝试了一下午，我们俩的思路是基于MT19937去预测key，后面发现key是random.randbytes(16)，字节形式，所以改为预测seed，代码是我敲的，多多少少有定痛苦。
因为MT19937去预测32位，所以我们想到每四个为一组，转成16进制进行倒序拼接，下面是代码

# 打开文件并读取所有行
with open('random.txt', 'r') as file:
    lines = file.readlines()

# 将每一行存储为元组
tuples = tuple(line.strip() for line in lines)

# 打印元组以验证
#print(tuples)

grouped_tuples = [tuples[i:i + 4] for i in range(0, len(tuples), 4)]

#print(grouped_tuples)

hex_grouped_tuples = [[hex(int(item)).replace('0x', '') for item in group] for group in grouped_tuples]

# 打印转换后的结果以验证
print(hex_grouped_tuples)
print('---------------')

reversed_hex_grouped_tuples = [list(reversed(group)) for group in hex_grouped_tuples]

# 打印转换后的结果以验证
print(reversed_hex_grouped_tuples)

print('---------------')

combined_hex_strings = [''.join(group) for group in reversed_hex_grouped_tuples]

# 打印转换后的结果以验证
print(combined_hex_strings)

print('---------------')

decimal_values = [int(hex_string, 16) for hex_string in combined_hex_strings]

# 打印转换后的结果以验证
print(decimal_values)

生成完以后，卧槽，感觉稳了，这个时候还没发现字节的锅，我们用github的extend_mt19937_predictor项目直接进行预测

from extend_mt19937_predictor import ExtendMT19937Predictor

randoms=[]

def prenumber(list):
    predictor = ExtendMT19937Predictor()
    for i in range(624):  # 2496 / 4 = 624
        predictor.setrandbits(list[i], 32)
    for i in range(624):
        predictor.backtrack_getrandbits(32)
    x = predictor.backtrack_getrandbits(16)
    return x

发现不对，然后16，32，64，128位的都尝试了一下，都不对，崩溃了老铁，然后发现了字节这个玩意，同时挖了他的源码，生成的长度是n*8，就是128位，这个时候采用恢复seed的脚本

from gmpy2 import invert

def _int32(x):
    return int(0xFFFFFFFF & x)

def invert_right(res,shift):
    tmp = res
    for i in range(32//shift):
        res = tmp^res>>shift
    return _int32(res)

def recoverseed(last):
    n = 1<<32
    inv = invert(1812433253,n)
    for i in range(623,0,-1):
        last = ((last-i)*inv)%n
        last = invert_right(last,30)
    return last

randoms=[]
x=[]
for seed in randoms:
   print(recoverseed(seed))
   x.append(recoverseed(seed))

print(x)

发现还是不对，心态崩了。

正确的方法

原理应该是https://www.anquanke.com/post/id/205861#h3-9的2020 pwnhub CoinFlip2这道题目的exp，恢复state的板子是https://github.com/NonupleBroken/ExtendMT19937Predictor ，也可以用https://github.com/JuliaPoo/MT19937-Symbolic-Execution-and-Solver 直接梭哈，原理等研究明白了单独发出来。

exp

import sys
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
sys.path.append('./MT19937-Symbolic-Execution-and-Solver/source')
from MT19937 import MT19937, MT19937_symbolic

c = b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'

f = open('random.txt','r')
rand = f.read().split('\n')[:-1]
rand = [int(i) for i in rand]

# Clone rng's current state
rng_clone = MT19937(state_from_data=(rand, 8))

# Reverse state by 4
rng_clone.reverse_states(4)
reverse_states = [rng_clone() for i in range(4)]
# 先生成的32比特放在低位
k = reverse_states[0] + reverse_states[1]*2**32 + reverse_states[2]*2**64 + reverse_states[3]*2**96
key = k.to_bytes(16, 'little')
cipher = AES.new(key,AES.MODE_ECB)
print(unpad(cipher.decrypt(c),16).decode())

from sage.all import *
from random import Random
from tqdm import *

prng = Random()
length = 19968

def myState():
    state = [0]*624
    i = 0
    while i < length:
        ind = i // 32
        expont = i % 32
        state[ind] = 1 << (31 - expont)
        s = (3,tuple(state + [0]),None)
        yield s
        state[ind] = 0
        i += 1

def getRow():
    rng = Random()
    gs = myState()
    for i in range(length):
        s = next(gs)
        rng.setstate(s)
        data=[]
        for i in range(length // 8):
            data.extend(list(bin(rng.getrandbits(8))[2:].zfill(8)))
        data = [int(i) for i in data] # 只有1行，还是length长度
        row = vector(GF(2),data)
        yield row

def buildBox():
    b = matrix(GF(2),length,length)
    rg = getRow()
    for i in tqdm(range(length)):
        b[i] = next(rg)
    return b # length * length

def test():
    prng = Random()
    originState = prng.getstate()
    # 这里都是用的MSB,如果采用不同的二进制位(如LSB)最后的矩阵T 也会不同
    leak = []
    for i in range(length // 8):
        leak.extend(list(bin(prng.getrandbits(8))[2:].zfill(8)))
    leak = [int(i) for i in leak]
    leak = vector(GF(2),leak) # leak 长度为 length
    T = buildBox()
    with open("Matirx","w") as f:
        for i in trange(T.nrows()):
            for j in range(T.ncols()):
                f.write(str(T[i,j])+'n')
    x = T.solve_left(leak)
    x = ''.join([str(i) for i in x.list()])
    state = []
    for i in range(624):
        tmp = int(x[i*32:(i+1)*32],2)
        state.append(tmp)
    prng.setstate(originState)
    prng.getrandbits(8)
    originState = [x for x in prng.getstate()[1][:-1]]
    print(originState[1:] == state[1:])
#     print(state)
    return state,T

def buildMatrix():
    with open("Matrix","r") as f:
        data = [int(x) for x in f.read().split('n')]
    m = matrix(GF(2),length,length,data)
    return m

# X = Z*(T^-1)
def recoverState(T,leak):
    x = T.solve_left(leak)
    x = ''.join([str(i) for i in x.list()])
    state = []
    for i in range(624):
        tmp = int(x[i * 32:(i + 1) * 32], 2)
        state.append(tmp)
    return state

# 根据题型2,还原state,有两种可能,这时候可以用暴破
def backfirst(state):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    tmp = state[623] ^ state[396]
    if tmp & high == high:
        tmp ^= mask
        tmp <<= 1
        tmp |= 1
    else:
        tmp <<= 1
    return (1 << 32 - 1) | tmp & low, tmp & low

def main():
    _, T = test()
    print('构建完成')
    print("T完成")
    prng = Random()
    originState = prng.getstate()
    # 题目给的数据
    leak = []

    leak1 = [int(j) for j in "".join([bin(i)[2:].zfill(8) for i in leak[:19968 // 8]])]
    leak1 = matrix(GF(2), leak1)
    # 恢复state
    state = recoverState(T,leak1)
    print("state恢复完成")
    # 两种可能
    guess1, guess2 = backfirst(state)
    print(f"两种可能分别为{guess1}, {guess2}")
    state[0] = guess1
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    if True:
        print("尝试第一种可能")
        prng.setstate((3, tuple(s + [0]), None))
        now =  [prng.getrandbits(8) for i in range(2496)]
        if now == leak:
            print("第一个可能尝试成功")
            print(f"state = {state}")
            return
    state[0] = guess2
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    if True:
        print("尝试第二种可能")
        prng.setstate((3, tuple(s + [0]), None))
        now =  [prng.getrandbits(8) for i in range(2496)]
        if now == leak:
            print("第二个可能尝试成功")
            print(f"state = {state}")
            return
main()

from random import Random
prng = Random()
state = []

prng.setstate((3, tuple(state + [0]), None))
D = [prng.getrandbits(32) for _ in range(624)]
print(D)

from Crypto.Cipher import AES
from extend_mt19937_predictor import ExtendMT19937Predictor

predictor = ExtendMT19937Predictor()

D = []

for _ in range(624):
    predictor.setrandbits(D[_], 32)

for i in range(624):
    predictor.backtrack_getrandbits(32)

key = predictor.backtrack_getrandbits(16 * 8).to_bytes(16, 'little')
cipher = AES.new(key,AES.MODE_ECB)
c =  b'a\x93\xdc\xc3\x90\x0cK\xfa\xfb\x1c\x05$y\x16:\xfc\xf3+\xf8+%\xfe\xf9\x86\xa3\x17i+ab\xca\xb6\xcd\r\xa5\x94\xeaVM\xdeo\xa7\xdf\xa9D\n\x02\xa3'
flag = cipher.decrypt(c)
print(flag)
# WKCTF{3f2af637b773613c18d27694f20d98fd}

Meet me in the summer(复现)

task

from random import choice, randint
from Crypto.Util.number import isPrime, sieve_base as primes, getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import md5

flag = b'WKCTF{}'
flag = pad(flag,16)
def myPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

def encrypt(key, message):
    return pow(65537, message, key)

p = myPrime(512)
q = getPrime(512)
N = p * q
m = [getPrime(512) for i in range(1024)]
enc = [encrypt(N, _) for _ in m]

a = [randint(1,2 ** 50) for i in range(70)]
b = [randint(1,2 ** 50) for i in range(50)]
secret = randint(2**119, 2**120)

ra = 1
rb = 1
for i in range(120):
    if(i < 70):
        if (secret >> i) & 1:
            ra *= a[i]
            ra %= p
    else:
        if (secret >> i) & 1:
            rb *= b[i-70]
            rb %= q

key = md5(str(secret).encode()).hexdigest()[16:].encode()
cipher = AES.new(key,AES.MODE_ECB)

with open("output.txt","w") as f:
    f.write(f'c = {cipher.encrypt(flag).hex()}\n')
    f.write(f'm = {m}\n')
    f.write(f'enc = {enc}\n')
    f.write(f'a = {a}\n')
    f.write(f'b = {b}\n')
    f.write(f'ra = {ra}\n')
    f.write(f'rb = {rb}\n')

思路
1.先用背包去恢复N
enc_i=65537^ (m_i) mod N
我们可以找a1,a2,a3,···,an,使得a1m1+a2m2+···+an mn=0
那么这就构造出一个格，再找到第二组a，就可以对两组求公因数得到N

f = open("output.txt",'r').readlines()
m = eval(f[1].strip().split("=")[-1])
enc = eval(f[2].strip().split("=")[-1])

m = m[:100]
enc = enc[:100]
# 感觉不需要全部数据，随便取点数据试试能不能出

n = len(m)
Ge = Matrix(ZZ,n,n+1)
K = 2^200
for i in range(n):
    Ge[i,i] = 1
    Ge[i,-1] = K*m[i]

L = Ge.LLL()
xx = product([ZZ(y) ^ x for x, y in zip(L[0][:-1], enc)])
yy = product([ZZ(y) ^ x for x, y in zip(L[1][:-1], enc)])
N = gcd(xx.numer() - xx.denom(), yy.numer() - yy.denom())
print(N)

2.求出N后，p-1光滑，套脚本直接出pq

import gmpy2 

N = 3365950545896839807600753681439061096312578337873460615427103468443333055935222147455641892341798604350037357999848711970084367398055755047567367304166808830853176966914407772226194410114093800191521813038405295729046243670270181161836427221727870133145321390846488824416000038564306005700271206427983462394735137
def smooth(N):
    a = 2
    n = 2
    while True:
        a = pow(a, n, N)
        res = gmpy2.gcd(a - 1, N)
        if res != 1 and res != N:
            return res
        n += 1

p = smooth(N)
q = N // p
print(f"p = {p}")
print(f"q = {q}")
"""
p = 266239931579101788237217833822346198682539336616234011732898866661722928035386747695230192006141430294833011494452114878744414084025005167432139516382471637567
q = 12642545864299817932696528548195775137854645688987690739317393212595731628016420449974358672452504599152386464349500792607469701592216257829464295238775711

"""

3.下面要处理secret，，将之看作两段，前七十位可以构造格出来，后五十位mimt可以出来，这个题目的名字就是这样来的

a = []
ra =
p =
g = 5
tmp = discrete_log(mod(ra,p),mod(g,p))

n = len(a)
A = [discrete_log(mod(a[i],p),mod(g,p)) for i in range(n)]

d = n / log(max(A), 2)
print(CDF(d))

Ge = Matrix(ZZ,n+2,n+2)
for i in range(n):
    Ge[i,i] = 2
    Ge[i,-1] = A[i]
    Ge[-1,i] = 1

Ge[-2,-2] = 1
Ge[-2,-1] = p - 1
Ge[-1,-1] = tmp
Ge[-1,-2] = 1
Ge[:,-1] *= 2^200

for line in Ge.BKZ(block_size = 26):
    if line[-1] == 0:
        t = ""
        for i in line[:-2]:
            if i == 1:
                t += "0"        # or 1
            if i == -1:
                t += "1"        # or 0 这两个来回换一下即可
    if len(t) == 70:
        print(t[::-1])
        break
        # 1100100011000011000001010101000010111110000001000010101010100100011011

from tqdm import *
from Crypto.Util.number import *

q = 12642545864299817932696528548195775137854645688987690739317393212595731628016420449974358672452504599152386464349500792607469701592216257829464295238775711
rb =
b = []

dict = {}
for tmp in trange(2**24,2**25):
    t1 = 1
    for i in range(25):
        if (tmp >> i) & 1:
            t1 *= b[i]
            t1 %= q
    dict[t1] = tmp

for tmp in trange(2**24,2**25):
    t2 = 1
    for i in range(25):
        if (tmp >> i) & 1:
            t2 *= b[i + 25]
            t2 %= q
    t = rb * inverse(t2,q) % q
    if t in dict.keys():
        print(f"低25位是:{bin(dict[t])[2:]}")
        print(f"高25位是:{bin(tmp)[2:]}")
        break
        # 1011111010011011011100010
        # 1100010001001011111001111
        # 11000100010010111110011111011111010011011011100010

4.AES解密

from Crypto.Cipher import AES
from hashlib import md5

high = "11000100010010111110011111011111010011011011100010"
low = "1100100011000011000001010101000010111110000001000010101010100100011011"
secret = int(high + low,2)
print(secret)

c = "dc6ba0123102f13a60ec4488d917a53a3c9b61372f39b977e93027fcb735eac38ceea2c0a7d5d6baf3570eea05200ce0"
key = md5(str(secret).encode()).hexdigest()[16:].encode()
cipher = AES.new(key,AES.MODE_ECB)
flag = cipher.decrypt(bytes.fromhex(c))

print(flag)
# WKCTF{Hell0_CTFer_Th1s_the_5ignin_fl4g.}

总结

第三题感觉好难，搞明白了再写一遍，MT19937应该会再去发一个。