2023鹏城杯密码全WP

2023鹏城杯，Crypto四题Writeup。

赛后才AK，一天四道题，上了一周班还是周末的比赛，精力不足了-

题目有一定挑战性，不过也只是有挑战性，大部分都是已知的漏洞拼凑一下弄成很长的代码然后再卡一下界的那种题，时间几乎都花在调试代码上，可以看得出出题人为了把题目上难度已经很努力了（x

WP也有在山石网科安全技术研究院上同步推送，您可以认为我博客这是做了转发+细化（

SecretShare·

题目：SecretShare.zip

审了半天，原来是做MT19937的随机数预测，泄露的X已经暴露了624 * 32以上的随机比特，调RandCrack预测最后的X，然后解线性方程可分解N，最后做RSA解密即可

参考代码：

from randcrack import RandCrack
import libnum

with open('./output.txt', 'r') as f:
  data = f.read().split('\n')[:-1]
X = []
R = []
for i in range(len(data)):
  tmp = [Integer(_) for _ in data[i].split(' ')]
  X += [tmp[0]]
  R += [tmp[1]]
R += [158171468736013100218170873274656605219228738469715092751861925345310881653082508445746109167302799236685145510095499361526242392251594397820661050281094210672424887670015189702781308615421102937559185479455827148241690888934661637911906309379701856488858180027365752169466863585611322838180758159364570481257]
p = 667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029   
c = 9658009093151541277762773618550582280013680172161026781649630205505443184765264518709081169475689440555639354980432557616120809346519461077355134139495745998317849357705381020225760061125236265304057301286196004542729553944161451832173970613915423841610378207266606500956362098150141825329354727367056070349148059780287916811442861961254066733726576151134458892613951223277692935141880749737598416235307087782001086096114978527447987308876878393763055893556123029990282534497668077854186604106027698257663251502775547705641708624619340185646943640576690633662704397191379303254341343433077302686466850600522990402912
N = 11790604055677230214731474049594783873473779547159534481643303694816346271798870343160061559787963631020684982858033776446193418629055210874285696446209220404060653230407249409973790191858423402504530660556839353260629987853933304089439885784684686555554108157760445567974629355878575105480273451284714281430590737346099023372211403461861104391534461524711472734572409128196536805998116015230502045333769525693468193385557827209520108839913096017750428926467123493650506193757937746017474062985480713594474378324234033232933140389879312722642144536418253323908290256009510135710208223393009237664704631175216240376891
n = 21

randomness = []
for i in range(n-1):
  for j in range(1024 // 32):
    randomness += [(X[i] >> (32*j)) & 0xffffffff]
rc = RandCrack()
for r in randomness[:624]:
  rc.submit(r)
for i in range(len(randomness) - 624):
  rc.predict_getrandbits(32)

X += [rc.predict_getrandbits(1024)]

M = matrix(GF(p), n, n)
for i in range(n):
  for j in range(n):
    M[i, j] = pow(X[j], i, p)
w = vector(GF(p), R)
v = w * M^(-1)
P = Integer(v[0])

Q = N // P
flag = libnum.n2s(int(pow(c, Integer(65537).inverse_mod((P-1)*(Q-1)), N)))
print(flag)

# b'flag{2f43430b-3c31-03ee-0a92-5b24826c015c}'

当时其实有想过能不能用N里面的secret因子代进去做消元，不过消元的复杂度还是太高了，以后找到更好的消元方法再试试（留坑

Neltharion_and_Arthas·

题目：Neltharion_and_Arthas.zip

题目有两个子问题，首先看第一个是在encrypt1用CTR模式和相同的密钥key1加密了gift1和flag1

引用一下CTF wiki上的图，CTR其实就是在用counter和key1做加密得到一堆的OTP，然后用这个OTP和明文做异或得到密文，这里的counter已经是128位，和AES的块大小一致，所以并没有上图中的Nonce

题目中用了相同的密钥加密两个消息，所以在CTR中产生的OTP也一样，flag1知道了前面6个字母，所以可以把这6个字母与enc_flag前6字节做异或，恢复出前6字节的OTP，再与enc_gift1异或得到gift1的前6字节，结果为I am D

所以盲猜gift1和gift2一样是一个英文句子，然后根据题目名字的Neltharion搜到D应该是Deathwing，然后搜到完整句子（以为人均魔兽玩家是吧-）

gift1 = b'I am Deathwing, the destroyer, the end of all things! Inevitable. Indomitable.'

最后用gift1和enc_gift1异或得到完整的OTP，再与enc_flag异或实现解密

参考代码：

cf1 = bytes.fromhex('c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df')
cg1 = bytes.fromhex('bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca')
flag6 = b'2023: '
m6 = ''
for i in range(6):
    ki = flag6[i] ^ cf1[i]
    m6 += chr(ki ^ cg1[i])
print(m6)

# https://www.reddit.com/r/wow/comments/855dxm/so_what_are_your_favorite_deathwing_quotes/
gift = b'I am Deathwing'
gift = b'I am Deathwing, the destroyer, the end of all things! Inevitable. Indomitable.'
m = ''
for i in range(len(cf1)):
    ki = gift[i] ^ cg1[i]
    m += chr(ki ^ cf1[i])
print(gift.decode())
print(m)

# 2023: flag{4ff732dd2b7445fd

PS：如果没猜到gift1的话应该也可以通过枚举flag1里面的十六进制猜gift1里面字母的组合，不过复杂度会高很多

第二个问题稍微麻烦点，用的是CBC模式，知道前半部分gift2，知道缺了4个字节的key2，知道gift2的密文的最后一块和倒数第二块的一半，求作为IV的flag2

首先根据CBC的加密流程可以推出一种根据后一块的明密文推出上一块密文的方法

$$C_{i-1} = \text{Dec}(K, C_i) \oplus M_i$$

当然这个方法需要密钥key2和最后一块明文，但这里明文最后一块和key2有关，所以可以通过枚举key2的4个字节，判断解出的倒数第二块密文是否符合enc_gift2的格式，来恢复key2（枚举的时候记得明文要加padding）。

拿到key2后只需要

$$\text{IV} = \text{Dec}(K, C_0) \oplus M_0$$

即可恢复flag2

不过题目没给字母表，完整爆破string.printable需要一个小时…

参考代码：

from Crypto.Cipher import AES
from Crypto.Util import *
import binascii
import hashlib
import string
import itertools
import libnum
from tqdm import tqdm

def decBlock(key, c):
    assert len(c) == 16
    aes = AES.new(key, AES.MODE_ECB)
    return aes.decrypt(c)

def xor(a, b):
    return libnum.n2s(libnum.s2n(a) ^ libnum.s2n(b))

clast = bytes.fromhex('918096cfa3b76d6622914395c7e28eef')
keyx = 'tn*-ix6L*tCa*}i*'
keyx = keyx.replace('*', '%s')
key_len = len(keyx)
for xxxx in tqdm(itertools.product(string.printable, repeat=4), total=100**4):
    key = keyx % xxxx
    h = binascii.unhexlify(hashlib.sha256(key.encode()).hexdigest())[:11]
    msg = b'I tell you this, for when my days have come to an end , you, shall be King.' + h
    #padding = bytes((key_len - len(msg) % key_len) * '&', encoding='utf-8')
    msg += b'&&&&&&&&&&'
    m = []
    for i in range(0, len(msg), 16):
        m += [msg[i: i+16]]
    c = clast
    c = xor(decBlock(key.encode(), c), m[-1])
    # '**5**c***74***********fee046b4d2'
    if not 'fee046b4d2' in c.hex():
        continue
    print(key, c.hex(), h)
# 5643132/100000000

key2 = b'tn5-ix6L#tCaG}i6'
h = binascii.unhexlify(hashlib.sha256(key2).hexdigest())[:11]
msg = b'I tell you this, for when my days have come to an end , you, shall be King.' + h
msg += b'&&&&&&&&&&'
m = []
for i in range(0, len(msg), 16):
    m += [msg[i: i+16]]
#m = m[::-1]
c = bytes.fromhex('918096cfa3b76d6622914395c7e28eef')
for i in range(len(m)):
    c = xor(decBlock(key2, c), m[-(i+1)])
flag2 = c
print(flag2)
# b'a3eae82b4c491e0e'

最后把两段拼起来做成uuid格式即是flag

flag = '2023: flag{4ff732dd-2b74-45fd-a3ea-e82b4c491e0e}'

LeakyRSA·

题目：LeakyRSA.zip

知道$p \oplus q$的高leakBits = 262位比特，分解n = p * q，其中p和q是nbits = 512位。

首先不妨令nbits是$\eta$，然后假设知道$p$和$q$的高$\eta - \ell$位的话，即可以根据

$$p = 2^\ell p_h + p_l \\ q = 2^\ell q_h + q_l$$

来把$p$和$q$拆分成高低两部分，然后用来表示$n$：

$$\begin{aligned} n &= p q \\ &= (2^\ell p_h + p_l) (q = 2^\ell q_h + q_l) \\ &= 2^{2\ell} p_h q_h + 2^\ell (p_h q_l + q_h p_l) + p_l q_l \end{aligned}$$

前面的$2^{2\ell} p_h q_h$是我们可知的高位，其中的低$2 \ell$比特是$0$

剩下的$2^\ell (p_h q_l + q_h p_l) + p_l q_l$是低位，规模大概是$\eta + \ell$，加上加法产生的进位$\varepsilon$

由于低位影响不了高位，所以$2^{2\ell} p_h q_h$的高位$\eta - \ell - \varepsilon$比特会与$n$的高$\eta - \ell - \varepsilon$比特相等，于是便可通过枚举$p$的高位，用leak计算出$q$的高位，从高位比特到低位比特枚举，然后用以上特性做剪枝

最后知道$p$的高位后就是典型的RSA知道p高位攻击，Coppersmith解之

不过解的过程中会有一些问题，一个是如果$\varepsilon$设得太小的话在前面的几步枚举会出错，所以可以先选择一个大的$\varepsilon$，让算法进入到正确分支得出一堆（高位相同的）结果后，再用这个结果的高位和小的$\varepsilon$去缩小结果的范围

另一个问题是，题目的Coppersmith界卡得很死，用SageMath的small_roots去解的话，需要设置一个小的epsilon和恰当的beta，还要等很长的时间

参考代码：

n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923
c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691
leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321
nbits=512
leakBits = 262

import itertools
def hack(i, pi, e=2):
  if i == leakBits:
    print(pi)
    return [pi]
  res = []
  for bi in itertools.product((0, 1)):
    pj = pi * 2 + bi[0]
    qj = (leak >> (leakBits - i - 1)) ^^ pj
    nj = pj * 2^(nbits-i-1) * qj * 2^(nbits-i-1)
    k = nbits - (i+1)
    r = nbits + k + e
    test1 = n >> r
    test2 = nj >> r
    if test1 == test2:
      res += hack(i+1, pj, e)
  return res

# ph = hack(1, 0b1, e=8)
# print(ph)

ph = 0b10000010000111000101010101100001111010110001001111000001111111000110011011011011101001111010101110110011001111010011000100111100101000000011000101001101100001100001001010001111101100001011001000101111110011010010000010011111011110100000111110001010101
ph = hack(ph.nbits(), ph)
print(ph)

#  [3766446804604751716700603557468056141781372537302833297927481351664361621596419, 3766446804604751716700603557468056141781372537302833297927481351664361621596420, 3766446804604751716700603557468056141781372537302833297927481351664361621596421]

做完ph = hack(1, 0b1, e=8)可以得到以上的ph = 0b1000001...，然后缩小范围后只有三个结果，最后用这三个结果去做CopperSmith

参考代码：

def solve(n, ph, pl=1, pbits=512):
  hbits = ph.nbits()
  print(hbits)
  lbits = pl.nbits()
  PR.<x> = PolynomialRing(Zmod(n))
  f = ph * 2^(pbits-hbits) + x * 2^lbits + pl
  f = f.monic()
  roots = f.small_roots(X=2^(pbits-hbits-lbits+1), beta=0.47, epsilon=0.008)
  if roots:        
    pm = Integer(roots[0])
    p = ph * 2^(pbits-hbits) + pm * 2^lbits + pl
    if n % p == 0:
      q = n // p
      return p, q
  return None

n = 73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923

from tqdm import tqdm
phs = [3766446804604751716700603557468056141781372537302833297927481351664361621596419, 3766446804604751716700603557468056141781372537302833297927481351664361621596420, 3766446804604751716700603557468056141781372537302833297927481351664361621596421]
for ph in phs:
  res = solve(n, Integer(ph))
  if res != None:
    print(res)

p, q = (6814449132912466352143200200256605077873329465758477832056090562012411200107156482645933890997787435093806046493913273252717701817613907418845774345791241, 10833217580503000698385694268032196544400600307706228180481286239545614448110770843300361411809086269809006469621399256214887200838529724133384063799751203)
assert p * q == n

import libnum
c = 71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691
flag = libnum.n2s(int(pow(c, Integer(65537).inverse_mod((p-1)*(q-1)), n)))
print(flag)

# b'flag{6eb67115-38b1-4e75-b3fc-de3a9697e565}'

colorful_matrix·

题目：colorful_matrix.zip

这题赛后出的，比赛中被HNP绕进去了，没有发现AES的密钥是key1，根本就不需要key2，大坑啊（

分析题目，如果不是出题人的失误的话，题目应该是有两个子问题。

一个是AGCD（Approximate GCD）问题，即知道$n_i = p q_i + m_i$求$p$，其中$m_i$是$256$比特，$q_i$是$1024$比特，$p$是$768$比特，有5组式子

首先整理多组式子

$$q_0 n_i = p q_i q_0 + m_i q_0 \\ q_i n_0 = p q_i q_0 + m_0 q_i$$

两式相减即可得$q_0 n_i - q_i n_0 = m_i q_0 + m_0 q_i$，其中$n_i$和$n_0$是已知量，$m_i q_0 + m_0 q_i$是一个偏小的量，所以构造格（其中$C = 2^{256}$，和$m_i$同规模）

$$M = \begin{bmatrix} C & n_1 & n_2 & n_3 & n_4 \\ & -n_0 & & & \\ & & -n_0 & & \\ & & & -n_0 & \\ & & & & -n_0 \\ \end{bmatrix}$$

然后可得

$$\begin{aligned} vM &= (q_0, q_1, \cdots, q_4) \cdot M = w \\ &= (C q_0, m_1 q_0 + m_0 q_1, \cdots, m_4 q_0 + m_0 q_4) \end{aligned}$$

粗略估算$\|w\| \approx 2^{256 + 1024} < 2^{\frac{256 + 4 \cdot (768+1024)}{5}} \approx \sigma(\mathcal{L}(M))$，所以LLL解$w$，然后计算$v = w M^{-1}$即可恢复所有$q_i$，然后由于$m_i$是一个误差，所以$p = \lfloor\frac{n_i}{q_i}\rfloor$即可恢复$p$，最后$m_i = n_i - p q_i$可恢复$m_i$

其中$p$的前32字节就是key1

import libnum
ns = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970, 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852, 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406, 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918, 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848]

M = matrix(ZZ, 5, 5)
for i in range(1, 5):
  M[0, i] = ns[i]
  M[i, i] = -ns[0]
M[0, 0] = 2^256
L = M.LLL()
w = L[0]
v = w * M^(-1)
q = [Integer(abs(_)) for _ in v]

q0 = q[0]
p = ns[0] // q0
assert is_prime(p)
print(p)
m = [ns[i] - p * q[i] for i in range(5)]
key1 = libnum.n2s(int(p))[:32]
print(key1)

# 293423658885957174953198318664231534672400520068303593221989900395768107225130267646792968959460384248015583618158947268381852534151783869878808621629530642974652628810907251607210136313789978156955302211733219987661815438401343683
# b'0b5e732a48fc8c6f5ac6366212d2bc59'

然后看第二个子问题是一个变种的HNP问题，令$T_1 = 2^{528}$，$T_2 = 2^{400}$，问题为

$$T_1 b^\text{h}_i + T_2 B_i + b^\text{l}_i \equiv A_i x \pmod p$$

其中$b^\text{h}_i$是$238$比特，$B_i$是$128$比特，$b^\text{l}_i$是$400$比特，$A_i$是$512$比特，$p$是上面问题解出的$p$，有$766$比特，知道37组求$x$

这个问题和2022高校密码数学挑战赛赛题二的Level3几乎一摸一样。首先整理下式子消去$x$

$$A_0(T_1 b^\text{h}_i + T_2 B_i + b^\text{l}_i) \equiv A_0 A_i x \pmod p \\ A_i(T_1 b^\text{h}_0 + T_2 B_0 + b^\text{l}_0) \equiv A_0 A_i x \pmod p \\ A_0(T_1 b^\text{h}_i + T_2 B_i + b^\text{l}_i) \equiv A_i(T_1 b^\text{h}_0 + T_2 B_0 + b^\text{l}_0) \pmod p$$

然后把$b^\text{l}_i$挪到等号一边，整理出

$$T_1 b^\text{h}_i + T_2 B_i + b^\text{l}_i \equiv A_0^{-1} A_i(T_1 b^\text{h}_0 + T_2 B_0 + b^\text{l}_0) \pmod p \\ b^\text{l}_i \equiv T_1 A_0^{-1} A_i b^\text{h}_0 + T_2 A_0^{-1} A_i B_0 + A_0^{-1} A_i b^\text{l}_0 - T_1 b^\text{h}_i - T_2 B_i \pmod p \\ b^\text{l}_i \equiv T_2 A_0^{-1} (A_i B_0 - A_0 B_i) + T_1 A_0^{-1} A_i b^\text{h}_0 + A_0^{-1} A_i b^\text{l}_0 - T_1 b^\text{h}_i \pmod p \\$$

令

$$\begin{aligned} D_i &\equiv T_2 A_0^{-1} (A_i B_0 - A_0 B_i) \pmod p \\ E_i &\equiv T_1 A_0^{-1} A_i \pmod p \\ F_i &\equiv A_0^{-1} A_i \pmod p \end{aligned}$$

即可得36组

$$D_i + E_i b^\text{h}_0 + F_i b^\text{l}_0 - T_1 b^\text{h}_i - k_i p = b^\text{l}_i$$

然后用这个式子构造格基，令$G = 2^{238}$即$b^\text{h}_i$的大小，令$H = 2^{400}$即$b^\text{l}_i$的大小：

$$M = \begin{bmatrix} -p & & & & & & & & & \\ -T_1 & G & & & & & & & & \\ & & -p & & & & & & & \\ & & -T_1 & G & & & & & & \\ & & & & \ddots & & & & & \\ & & & & & -p & & & & \\ & & & & & -T_1 & G & & & \\ F_1 & & F_2 & & \cdots & F_{n-1} & & 1 & & \\ E_1 & & E_2 & & \cdots & E_{n-1} & & & G & \\ D_1 & & D_2 & & \cdots & D_{n-1} & & & & H \\ \end{bmatrix}_{(2n+1)*(2n+1)}$$

然后令

$$v = (k_1, b^\text{h}_1, k_2, b^\text{h}_2, \cdots, k_0, b^\text{h}_0, 1) \\ w = (b^\text{l}_1, Gb^\text{h}_1, b^\text{l}_2, Gb^\text{h}_2, \cdots, b^\text{l}_0, Gb^\text{h}_0, H)$$

即得$vM = w$，粗略估算一下

$$\|w\| \approx 2^{400} \\ \sigma(\mathcal{L}(M)) \approx 2^{\frac{(766+238)(n-1) + 238 + 400}{2n + 1}}$$

所以只要$400 < \frac{(766+238)(n-1) + 238 + 400}{2n + 1}$即$n \ge 4 > \frac{760}{204}$即可，界好像有点松？不过可能这个格基比较特殊，最后我实验测出来要$n \ge 16$才行

反正最后有$\|w\| < \sigma(\mathcal{L}(M))$，然后LLL解出所有的$b^\text{l}_i$和$b^\text{h}_i$，然后计算$x \equiv A_i^{-1}(T_1 b^\text{h}_i + T_2 B_i + b^\text{l}_i) \pmod p$，即可恢复$x$

其中$x$的前32字节就是key2，但因为非预期所以其实并不需要key2。

import libnum

p = 293423658885957174953198318664231534672400520068303593221989900395768107225130267646792968959460384248015583618158947268381852534151783869878808621629530642974652628810907251607210136313789978156955302211733219987661815438401343683
A = [12789809461864875489953273982997537541385904671489556544122095227619591140533414669794423644619127980362623481580128258914287474542792728686579090501397390, 10463950513938701625808784986819665844287315724639315128677227520960105897990256530542006653611594269012930935073966767351788182657861624733138283749460454, 5253244650607533810967862436125419800679723144526973463211784033045021824966560017919956773745212139142517766154626849426827164032731516615725539069585525, 5644589184984504085855423002268477365020278981591337230721358313393863912025011466727192648804002734561676112555123877764178690726130713927642577324443238, 4231732567865883627242742552738439372803539125622706171540910152922080004603138662537022248675968288205781990968838888633816697065257733344028576518431020, 2483388920404524165854675814798022834892112957478917588986471421083048888193527751575039626887367465858751417977246719312923814782809309525841102293919541, 3252353812256192711411255830105475125944842449239880454539397067913664088094160819193268643401968970009466652179043139341471403913410402646923633696154454, 11575010486066232687430367040977113580882826853104996856464797182632266635060724100357205810604915010810884387573114266349621457564659060272935537811111850, 116107444921917032985259963199427176510900273385517435613848456370557161312731449337837406563733552524777525870560544042690403987311424820755256727586807, 5859050133610438843641532306693688255014116940390205022708310454673159702673207152462501010791971695002865650407033762568636006764435795015869726867643634, 5954075553161305677556950650395792531753502207483036473422070018485916621872566706504374038792527687442272405589975343003802956899043321092006127828986114, 4571747544457157571652286537158051402285727327066029382085461714597609990601683125994983291866807816649968826930652068427193317966970789937746419206862747, 7166507561570980603812241332170524724051295937096000768984168029904561160020043035660087151672164814332446644696618077835020463308343415953131944864257266, 4852042788460566411381271873349329096978244586097817622748766708426751073559942708861852208085367014057217116211249133109246735634468823924185525972777655, 11962941918999276757181090570698839032103646409734781047194175833198626142790676141060052011581957980660140931408560130449153056874213033784715711461403345, 10324508881746579337486319574059121005227580732153432145860775835052420139026016902518605634385512021513380467928195663920843022679549517463264144660593354, 13276257094435850052122403884510025189232513948002582716865201271569293297601525601586036713056700716929820641888489806178376555435219630186396004003438962, 6525051273399089095687950615197786094425890004112675057642687348101531212837185750558500720306108976630502328600886080197626115513445112562084719104488315, 12922888505610354933000354792496863801007995464403098763485264334670452387681468617068312646367483171083114539083453125614861357751571161533921864394641576, 9489726784141062031514945333087338495823600723655465328127755755022980083351477888038160719541864899912899592065620071698977397662002448273876711116012763, 10630316198843195148937849513165933809121991192035364160395429088101265852052098101114542104327663563661384303617672183366879116750889320604308038959012109, 12675564142993964272844760955973914547747654087592111324261755301551267959231076883765863344473167582531968290671984039948163579495803204811731286282708940, 11847724105274460405216443356582445218232627275228120716891711887600046501095390733716854871561352002320819466803698088448952127166615410820121973485089326, 5131676593756685549522564504727003861447389891839469018437277330988047271086971907217360711863971849879439418231726349935396008040776952541710218842744018, 8049060452950901277510497437779182190254362319091882684392717180429468875432078713802857488901441344429723298843967365750616860588029426099852763482179470, 2365060249260571713545479629411006471094806409182638354076861269679377537605360223984548798658469783472746989448405310909017645138161178501458084966625559, 7467521246204465304438401242342633361751371318557249418344587207503257890765643838557008735305668588521988487342275527781708126255070883848829062790678347, 5841608816993144092409175658260479687582056537041472535819914412630519543198558564258699185557903902095773598614097026740427138629173672250387442834578787, 3935779917509948624841228665498558015416911059417306651751360048412619176423173794541812556512582747588138532941031730797102738268660078594473168666677171, 1459083415233950534805962555425717865938763752937036513111696179351002303817986848490146888626704327653287774806488952733813718461674376764427084478395399, 6426876689549337938550615491086475536072547585103523407263007393570982327518298678278232288342601754164640081474537962710401178482959474762541185760732929, 5241364650650467046722868257809607948071188801137204831449976666385482519613365369974704486723941517654753205012497273820309153659423928739972270634209996, 6387483223002092292686097811446217867743566298067033295601210265979889577756648605354064672061975949925472022416479935990178719227937307079186916383092053, 170562164015232424518655058158727202269056868720093972639058422975773575660534168774299548952867348396798580779605954510297102765330549642318362861226163, 10004133230245713370426176448219282796530473722412487408402635996842671302539458739305597027107498342509248085998067976408732789438099488867425813748783724, 12325342879747412722323355648741345730921040452129462974449188258885453690169624888480720109964630270938743431623479816739889661554987977051169401841580388, 641543989928732942291347866597230552820621633110802944556141221591498546555080480758772801043509130524233886009444044150447511986129019395067102094826363]
B = [108715652691370707411987210267535348806, 131676833696101475747102644851662113271, 122436706338521558335484593966234623745, 255864866572301552398412638474857375629, 81098761191414480003681301866161112100, 322322463176364397336266169283851913620, 198167679309202772183020662350938553923, 326360662842236388778385468938922853242, 241812832858991643670485138860832357660, 69768236619183466076110136290750715548, 32383134960394164339076842474280712870, 147747232748027508904245311745435517130, 25327826075608705748116808975774398964, 65295332681674581261444632606267440749, 236756211690281667988216748814564193312, 106435149910135092172124474857722935730, 270727089812520941022075406571244846193, 206881193220261276126028739930244917728, 131961838897694897398340205404861333362, 219211823942216355573832791993673934321, 150960424777134558142309786444952807101, 51112048255939343109218372373173385772, 182065623911902509203036774197184164110, 168420344895532090057957641972492853410, 301808673225362418769168353084541667053, 132272458662433671393247350648662880688, 495672626901999558635736361346563007, 182444159345379042372018248514964944782, 144584137563407779776361378564517880036, 338518705859818740467225748906995999694, 205885429741815676881969528495365151019, 233897982464483450790005953366237992668, 279307677123402840425362992920185630901, 133493426228159673166382443820069696429, 316624110847744871475435405969944304329, 187931604382397525131117897387179435812, 220019728924915067987393012581921164417]
def matrix_overview(BB):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            if BB[ii, jj] == 0:
                a += ' '
            else:
                a += 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)

n = 37
T1 = 2^528
T2 = 2^400
G = 2^238
H = 2^400
M = matrix(ZZ, 2*n+1, 2*n+1)
for i in range(n-1):
  Di = T2 * A[-1].inverse_mod(p) * (A[i] * B[-1] - A[-1] * B[i]) % p
  Ei = T1 * A[-1].inverse_mod(p) * A[i] % p
  Fi = A[-1].inverse_mod(p) * A[i] % p
  M[2*i, 2*i] = - p
  M[2*i+1, 2*i] = - T1
  M[2*i+1, 2*i+1] = G
  M[-1, 2*i] = Di
  M[-2, 2*i] = Ei
  M[-3, 2*i] = Fi
M[-3, -3] = 1
M[-2, -2] = G
M[-1, -1] = H
matrix_overview(M)
L = M.LLL()
l = L[0]
x0 = (T1*abs(l[2*0+1])//G + T2*B[0] + abs(l[2*0])) * A[0].inverse_mod(p) % p
x1 = (T1*abs(l[2*1+1])//G + T2*B[1] + abs(l[2*1])) * A[1].inverse_mod(p) % p
assert x0 == x1
x = x0
key2 = libnum.n2s(int(x))[:32]
print(key2)

# b'71daf933d8f03cd24fd8596fcf6468b3'

解出两个密钥后就是做AES解密，但是不知道IV，其实CBC模式的话不用IV可以恢复除第一个块以外的明文，但这里第一块也含flag所以没用

最终漏洞还是MT19937的随机数预测，ms和A中泄露了624 * 32以上的随机比特，调RandCrack预测可得iv，然后用key正常解密即可

m = [12610761596859615338377507505797807887151476346999744775108821558273890028891, 13117413857353092802818150671891243460783640002008674612123855586624653019593, 53615229752684072838720322357723519016612611217408795609204017594168753460173, 114925727157331362271459397249756452108949510154527632590097998028667381400721, 111107324092431692605535663730265818421299427508885792571022132823006030649517]
A = [12789809461864875489953273982997537541385904671489556544122095227619591140533414669794423644619127980362623481580128258914287474542792728686579090501397390, 10463950513938701625808784986819665844287315724639315128677227520960105897990256530542006653611594269012930935073966767351788182657861624733138283749460454, 5253244650607533810967862436125419800679723144526973463211784033045021824966560017919956773745212139142517766154626849426827164032731516615725539069585525, 5644589184984504085855423002268477365020278981591337230721358313393863912025011466727192648804002734561676112555123877764178690726130713927642577324443238, 4231732567865883627242742552738439372803539125622706171540910152922080004603138662537022248675968288205781990968838888633816697065257733344028576518431020, 2483388920404524165854675814798022834892112957478917588986471421083048888193527751575039626887367465858751417977246719312923814782809309525841102293919541, 3252353812256192711411255830105475125944842449239880454539397067913664088094160819193268643401968970009466652179043139341471403913410402646923633696154454, 11575010486066232687430367040977113580882826853104996856464797182632266635060724100357205810604915010810884387573114266349621457564659060272935537811111850, 116107444921917032985259963199427176510900273385517435613848456370557161312731449337837406563733552524777525870560544042690403987311424820755256727586807, 5859050133610438843641532306693688255014116940390205022708310454673159702673207152462501010791971695002865650407033762568636006764435795015869726867643634, 5954075553161305677556950650395792531753502207483036473422070018485916621872566706504374038792527687442272405589975343003802956899043321092006127828986114, 4571747544457157571652286537158051402285727327066029382085461714597609990601683125994983291866807816649968826930652068427193317966970789937746419206862747, 7166507561570980603812241332170524724051295937096000768984168029904561160020043035660087151672164814332446644696618077835020463308343415953131944864257266, 4852042788460566411381271873349329096978244586097817622748766708426751073559942708861852208085367014057217116211249133109246735634468823924185525972777655, 11962941918999276757181090570698839032103646409734781047194175833198626142790676141060052011581957980660140931408560130449153056874213033784715711461403345, 10324508881746579337486319574059121005227580732153432145860775835052420139026016902518605634385512021513380467928195663920843022679549517463264144660593354, 13276257094435850052122403884510025189232513948002582716865201271569293297601525601586036713056700716929820641888489806178376555435219630186396004003438962, 6525051273399089095687950615197786094425890004112675057642687348101531212837185750558500720306108976630502328600886080197626115513445112562084719104488315, 12922888505610354933000354792496863801007995464403098763485264334670452387681468617068312646367483171083114539083453125614861357751571161533921864394641576, 9489726784141062031514945333087338495823600723655465328127755755022980083351477888038160719541864899912899592065620071698977397662002448273876711116012763, 10630316198843195148937849513165933809121991192035364160395429088101265852052098101114542104327663563661384303617672183366879116750889320604308038959012109, 12675564142993964272844760955973914547747654087592111324261755301551267959231076883765863344473167582531968290671984039948163579495803204811731286282708940, 11847724105274460405216443356582445218232627275228120716891711887600046501095390733716854871561352002320819466803698088448952127166615410820121973485089326, 5131676593756685549522564504727003861447389891839469018437277330988047271086971907217360711863971849879439418231726349935396008040776952541710218842744018, 8049060452950901277510497437779182190254362319091882684392717180429468875432078713802857488901441344429723298843967365750616860588029426099852763482179470, 2365060249260571713545479629411006471094806409182638354076861269679377537605360223984548798658469783472746989448405310909017645138161178501458084966625559, 7467521246204465304438401242342633361751371318557249418344587207503257890765643838557008735305668588521988487342275527781708126255070883848829062790678347, 5841608816993144092409175658260479687582056537041472535819914412630519543198558564258699185557903902095773598614097026740427138629173672250387442834578787, 3935779917509948624841228665498558015416911059417306651751360048412619176423173794541812556512582747588138532941031730797102738268660078594473168666677171, 1459083415233950534805962555425717865938763752937036513111696179351002303817986848490146888626704327653287774806488952733813718461674376764427084478395399, 6426876689549337938550615491086475536072547585103523407263007393570982327518298678278232288342601754164640081474537962710401178482959474762541185760732929, 5241364650650467046722868257809607948071188801137204831449976666385482519613365369974704486723941517654753205012497273820309153659423928739972270634209996, 6387483223002092292686097811446217867743566298067033295601210265979889577756648605354064672061975949925472022416479935990178719227937307079186916383092053, 170562164015232424518655058158727202269056868720093972639058422975773575660534168774299548952867348396798580779605954510297102765330549642318362861226163, 10004133230245713370426176448219282796530473722412487408402635996842671302539458739305597027107498342509248085998067976408732789438099488867425813748783724, 12325342879747412722323355648741345730921040452129462974449188258885453690169624888480720109964630270938743431623479816739889661554987977051169401841580388, 641543989928732942291347866597230552820621633110802944556141221591498546555080480758772801043509130524233886009444044150447511986129019395067102094826363]

from Crypto.Util.number import *
from Crypto.Cipher import AES
from randcrack import RandCrack
import libnum
key1 = b'0b5e732a48fc8c6f5ac6366212d2bc59'
key2 = b'71daf933d8f03cd24fd8596fcf6468b3'
enc = b'cTmkMb\xfc\x05|\x1d\xc7\x13\xbaSe\xe0\xbd\xc0\xd9\xa3\x8cwo\x82yN[B&\x80\xd7KPwQ`\x9c\xbf<y\x8e\x8a\x97e\xa074\xb2'

rc = RandCrack()
randomness = []
for mi in m:
  for j in range(256 // 32):
    randomness += [(mi >> (32*j)) & 0xffffffff]
for ai in A:
  for j in range(512 // 32):
    randomness += [(ai >> (32*j)) & 0xffffffff]
for r in randomness[:624]:
  rc.submit(r)
for i in range(624, len(randomness)):
  assert randomness[i] == rc.predict_getrandbits(32)

def xor(a, b):
    return bytes([a[i%len(a)] ^ b[i%len(b)] for i in range(max(len(a), len(b)))])
# key = xor(key1,key2)
key = key1

iv = long_to_bytes(rc.predict_getrandbits(128))
aes = AES.new(key,AES.MODE_CBC,iv)
print(aes.decrypt(enc))

# b'flag{86baa4ed-5ec7-11ee-ae14-ac1203ab14da}\x06\x06\x06\x06\x06\x06'