人工智能网络安全挑战赛 WriteUp

Crypto#

CardSeed#

题目：

1
from random import *
2
import base64
3

4
key_number=randrange(999999)
5
flag=b'flag{}'
6
enc=list(base64.b64encode(flag))
7
seed(key_number)
8
shuffle(enc)
9
print(bytes(enc))
10
#b'mwCBYZmOByyj1mN2NxjYTYYQhWTLUN3ys2iTQFOIMjZZt2Qh3CiZO9z1'

题目目标是还原shuffle前的顺序，加密流程如下：

对flag做base64编码
将编码结果转成列表
使用随机种子key_number初始化随机数生成器
使用shuffle(enc)打乱base64字符顺序
输出打乱后的字节串

关键点在于key_number = randrange(999999)，因此随机种子的范围很小，最多只有 999999 种可能，可以直接爆破。因此可以对每个可能的seed：

创建长度相同的下标数组perm = list(range(len(ct)))
使用当前seed复现shuffle：

1
r = Random(key)
2
r.shuffle(perm)

利用这个置换关系恢复原始顺序：假设原始列表是original，下标数组是perm = [0, 1, 2, ...]；对perm执行同样的shuffle后，得到的perm[i]表示密文第i个字符，来自原文第perm[i]个位置，也就是ct[i] = original[perm[i]]，所以恢复时应当为original[perm[i]] = ct[i]
得到候选base64后，尝试解码
检查解码结果是否满足flag格式：flag.startswith(b'flag{') and flag.endswith(b'}')

exp.py：

1
from tqdm import trange
2
from random import Random
3
from base64 import b64decode
4

5
ct = b'mwCBYZmOByyj1mN2NxjYTYYQhWTLUN3ys2iTQFOIMjZZt2Qh3CiZO9z1'
6
n = len(ct)
7
for key in trange(999999):
8
    perm = list(range(n))
9
    r = Random(key)
10
    r.shuffle(perm)
11
    original = [0] * n
12
    for i, p in enumerate(perm):
13
        original[p] = ct[i]
14
    b64 = bytes(original)
15
    flag = b64decode(b64, validate=True)
16
    if flag.startswith(b'flag{') and flag.endswith(b'}'):
17
        print("[+] seed =", key)
18
        print("[+] base64 =", b64)
19
        print("[+] flag =", flag.decode())
20
        break
21
#  61%|██████▏   | 614033/999999 [00:10<00:06, 60656.04it/s]
22
# [+] seed = 614033
23
# [+] base64 = b'ZmxhZ3s2OWQyN2I3OC1iNzYyLTQwNmUtOTYyZC1jMjFhZmQ2YjBiYTB9'
24
# [+] flag = flag{69d27b78-b762-406e-962d-c21afd6b0ba0}

Drift#

题目：

1
#!/usr/bin/env python3
2
import time
3

4
if not hasattr(time, "clock"):
5
    time.clock = time.time
6

7
from Crypto.Util.number import bytes_to_long, getPrime, isPrime
8
from os import urandom
9
from random import SystemRandom
10

11

12
FLAG = b"flag{????????????????????????????????????????}"
13

14
NBITS = 1024
15
PBITS = NBITS // 2
16
K_BOUND = 96
17
ERR_BITS = 150
18
E = 65537
19

20
rnd = SystemRandom()
21

22

23
def prime_pair():
24
    while True:
25
        p = getPrime(PBITS)
26
        q = getPrime(PBITS)
27
        if p < q:
28
            p, q = q, p
29
        # The released instance uses balanced primes that are not Fermat-close.
30
        if (p - q).bit_length() > 500:
31
            return p, q
32

33

34
p, q = prime_pair()
35
N = p * q
36
phi = (p - 1) * (q - 1)
37

38
k = rnd.randrange(2, K_BOUND + 1)
39
x = rnd.getrandbits(ERR_BITS)
40
a = k * phi + x
41

42
m = bytes_to_long(FLAG + urandom(4))
43
c = pow(m, E, N)
44

45
print(f"N = {N}")
46
print(f"a = {a}")
47
print(f"e = {E}")
48
print(f"c = {c}")

题目是一个 RSA 变形题。加密逻辑如下：

1
p, q = 512-bit primes
2
N = p * q
3
phi = (p - 1) * (q - 1)
4

5
k = random integer in [2, 96]
6
x = random 150-bit integer
7
a = k * phi + x
8

9
c = pow(m, 65537, N)

题目额外泄露了a，虽然a不是phi(N)的精确倍数，但它距离k * phi(N)只有一个 150-bit 的误差x。对于 1024-bit RSA 来说，这个误差太小，可以恢复p + q的高位，进而使用 Coppersmith 分解 N。我们设s = p + q，则

\varphi(N) = (p - 1)(q - 1) = N - p - q + 1 = N - s + 1

题目给出a = k * phi(N) + x，代入可得a = k(N - s + 1) + x。整理得到

k(N + 1) - a = k * s - x

记T = k(N + 1) - a，由于x < 2 ** 150，所以

\frac{T}{k} = s - \frac{x}{k}

也就是说可以得到s = p + q的一个非常精确的近似值。另一方面，因为phi(N) < N，且x远小于N，所以(k - 1)N < a < kN，因此可以直接恢复k = ceil(a / N)，本题计算得到k = 73。

随后计算：

s_0\approx p+q,d_0\approx \sqrt{(s_0^2-4N)},p_0=\frac{s_0+d_0}{2}

得到素因子p的近似值p0。由于误差只有约 150 bit，而N是 1024 bit，因此可以使用 Coppersmith 的已知高位攻击。

exp.py：

1
# SageMath 10.9
2
from sage.all import *
3
from math import isqrt
4
from Crypto.Util.number import long_to_bytes
5

6
N = 70348019346920225151438034957813493231231443364520695925697367812678267378897050570635325016789186427527627744652884686026189881979099100944176495081442955265380095121863635075531798834758389879382247088008659295375722841294856190557973505558251155261597518040032088590658055177065503199735664745204227888427
7
a = 5135405412325176436054976551920385005879895365610010802575907850325513518659484691656378726225610609209516825359660582079911861384474234368924884140945334509348765532424795469299266204346679735260094698493166169498311851100406909115273444255675286398694437571854269388837080201134630664629766706561917803344448
8
e = 65537
9
c = 9296542098018873044394759012765434299706576522096444493793810655415889697390132144995221239973859793936851932724715286107374874365336744786504435027863156982156088795593491345064398970849862482621588067098936463958310420017844272981803060478440169438214656457237359921285809149413605955223168775277392730747
10
k = (a + N - 1) // N
11
T = k * (N + 1) - a
12
s0 = (T + k // 2) // k
13
D0 = s0 * s0 - 4 * N
14
d0 = ZZ(isqrt(int(D0)))
15
p0 = (s0 + d0) // 2
16
PR.<x> = PolynomialRing(Zmod(N))
17
f = p0 + x
18
roots = f.small_roots(X=2**160, beta=0.4, epsilon=0.02)
19
p = int(p0 + roots[0])
20
q = N // p
21
phi = (p - 1) * (q - 1)
22
d = inverse_mod(e, phi)
23
m = pow(c, d, N)
24
flag = long_to_bytes(m).decode()
25
print(flag)
26
# flag{rsa_exponent_transforms_need_error_bounds}

LuckyRand#

题目：

1
from Crypto.Util.number import *
2
from Crypto.Cipher import AES
3
from random import *
4

5
iv = long_to_bytes(getrandbits(128))
6

7
flag = ?
8
flag = flag + b'\x00' * (16 - (len(flag) % 16))
9

10
res = [long_to_bytes(getrandbits(128)) for _ in range(160)]
11
for i in range(len(res)):
12
    if len(res[i])!= 16:
13
        res[i] = b'\x00' * (16 - len(res[i])) + res[i]
14

15
plaintext = flag + b''.join(i for i in res)
16
key = long_to_bytes(getrandbits(128))
17
aes = AES.new(key, AES.MODE_CBC, iv)
18
cipher = aes.encrypt(plaintext)
19

20
print(key)
21
print(cipher)
22

23
'''
24
b'\xd0\xa2\x10\x8bH!\x0b\x80\xec\xe2lDo\xf1\xb00'
25
b'\xf8{\x90\xc2B\x80\xa6\xb5\x12\x9e\x99s\xa6\xf3\x12D,\x9b\x9b\xe4\xa0\x1c\xe1\xb1\x03\xfb!\xc1\xe0\x80l\x94#1\xc2\xa7b\xc5:g\xe5\xdf*\xca\x0b\xe9\xda\x9d\xfa\x1d\xc1\xb9\x1en\xc1\x8e1].\xcb\xad\xb4\x8cC\x16C\x01\x118\x87+\xe6L\xd7\xd6\x8b\nw\xba@q8\x1e\x15?[B\xb7>t\xeb\xadpE\xa8\x04mL#\x89\xc7\xd3\xac~D\xa4=j\xb8\xb0J\r?\xc9\xe4J7U,\x9d2\xb1\xe1L\x86\xe6\xf4-\x9bS!\xd3\xe0\xc6\xdd\x8b\xb2pj\xe7:>{\xf7\xfa\x0fI\xb5,\xeeS\xbfc?\xe1\x1b\t?\xa3?\xae\x19-\xb6\xf3\x94\x13*\x02d\xb4\xe0\x98\x91@y\n\x1av\'WOb\xec\xed/\x99\xb1\xab\xa6\xd2OU\xa4\xbf`w@\x9e\xab\xae\xecYbf\xe7\x86\xa1\xc6\x1c;X\xd4\x97!\xaf\xe0\xc1\xc4\xa74k\xf1\x9f8Ol\x07x\x88\x10\xe0\xa2\xc6u\xb9\xf6\xa7\x0cs~\xbe\xf0H*\xc6\xe4\xcbN\x8d\xf1\xc7Frc5\xf7\xc3\x91M7M\xec\xbe\xd81iO\xb5/\xe9\xd2\x17\xe0$\x97S<\xb2\x9e\xd5\xd3\xb13m(~=\xa3\xfd\xc9\t\xa1Ry\x18\xd2\x1b\x19\xb2\xb6\x07\x97?\x9a_q\x0f\x86f\xe5\xac\r\x03\xe9NY\x823\x0f\x01\xf3\x14`\xafB\xa54\xef\x8e\xa1\xcc\xa7I\xb2\x1c|\xed\xbeOn[\xa8G\x96\x96d\n\xebCX\x8d\x92\x93\x13\x9c\x00-\x9c8G\xa0\x8b\x03\xaf&\x8e\xf45\'\xad\xae\xc7L\xcc\xd7\x83\x87\xc31\xa5\x83\xdf\xf5\xf4Md\x9c\x14\x9b77\xcb\xde}\x87}\x94\xdb\xd8\xca\xf8(\xaf~e\x85\x9cm}EG \xca\xd0\x83\xb3\x9by4j?H\xfc\x10#\x8e\xab\xe4pr\x16pw\xf1\xec\xa4\xfd\xbbo\x19,$\xc2/\x95%yL"\x17\x890\xdc\xdf\x04zv\x12\x9c:}\xfe\xfc\x84\xc1\xc8\x02\x96\xa3\xc9\xb9\x7f\xc90\x11P<\\\xaa\xfe_V\'\x92\xe6\xb3\x15S\xad64R\x87*\xc14\xa9\xae\xc6\xd6t\xab\x1d$\xcf:\xf4\xa7#6\xe7\x94\xdf\xcb\xe9\xb4@\xaa\xd3Y\x88Sl\xa9\x0f\xe1\x0fh\x02\x8a\x91\xf8:\xacDrT\xa2\xa4\x97_\xda9\xdaP\xaaf\xe7\xc4\x0f`F`\x874\xd2\xee\xc3#|\xe8\xb8\xac\xd2\x00\xc6J\x8e\xd5!\xe4I\xa4\xe9B\xfc\x97\xa6\xa2\xe43\x16Cp\x86\xb90\x16\xb4\xc0\xa94yo\xcfc\x95\x89\xca\xd9\xe37#\x9a\xd9d\xb1=\x13\xfc\xfcZ\xfd^\xaa\xd5\x12\x8d\xce\x05R\x8b\xc9\xd2\xfaZ\xf4\xea\x91o<\x14\xae%\x1d\xcfJ\x12dW\xa5p\x15\x00\xfc\x10f\xfc6\xc6\xaa/\xdc\xd2\xe9\xa0f\xb6\xc1\x86\xd3~N\xac\x9d\x87TdH\x7fE3\x95\xc37N#\xb7\x00A\xbf\xe6\xe6\xbc\xbf\xf3K\xbe\xe6\xea\xbf\xb1d\x92\xb9\xba\xe2\x0f\xd3<\x0b\xeb\x98\x97Q\x06]\xe1\xe4K\x89*\xba\x8a\xe4~\xbf\'Tu\xba\xdajF\xae\x8b\x1c{\x14\xa3\xc2\xff\xcc3j\xee\xed|\xa9\xa4\xb4\xfcU\xb5\xbf\x81\xcb1I\x80\xa9\x88\r\xe0\x06\x81z\x16\x0f\xdc\x80^\x94\x18\x1bLd\xe5\x0e\xc9\xe8m\xaa\xdf\xadJ\x03u*\x0f\xcf>\xb2;TOq^\xbc\xb4f(\xedIa8%sA\xc1\x92F\x8d/\xe6\xb2\x18\xa0\x0b\rD\x06\x8b\xd24_M?\x1d\x95\xa1yb\x8f\xec\x82\xe5\x12\xe7Wq\x1a\xd1\x158/\x17\x180\xae@\x869\x96f%!E\x0f\xee7\xcaFF\x9a-1$\x16\xd9\x17l|\xff0\xd3\xe8\xac\x19\x80\x95u\x9c{\x14i}f\xdbk\xf6\xfb\xa5\xa3^+\xa7\xc3<\xe9-\xa3A\x03N\xa3+\xc8\x15WC\xaa\x92\xefz\x01\xd6gq4\x12\xeb\xfe^-Ejg\xf7\\\xe9\x82\xde\x91\x1cD\x91nz\xc7\xf1\xcd\x01\xc7\xf0\xcbo\xda\xd8o\xacZ\x11\xd4\xc9\t\x14A\x00\xb0!\xa1\x9e\x1b\xc3\xca\xed\xf1^M\xd6\xa8\xe7\xf4\xe3\x0cCZ\x93\xa8{\x98\x85a\x82\xe4\xb8\x1c59\xeaE\xc4\xf6\x04Ui\x84lPV\x98\xc9\xce\x02o\x07\xe6\xb6\xdc>a+\x13\x14\xe0\xb6\xa0\xb0\xc88\xd9~\x05k\xd1E+\x8d\xe0o\xed\x15\x89\xd5\xa2\xc2\xe0\xb3\xe0]\xf3\xb2\xaa_W\xa4s\xf6`$\xa9\x9da\x13\xc9e\r\xd3\x97\xedB\xe5\xd6\x1cB\x15\xc2_\x117\x9fE\x8a\xc7<\x8a\xb9\x96\xc8$\x80\xe2\xab\x14K\x9aJ\xa1\t\xf7=\xc5\x8f{.Ml\x83\xa58\x1e\xf9\xa4\xafw\x00\xed\xd0\xb6\r\xd2\x9f\xf7h\xf3\x82,X\xfc\t\'\xdf\xd6H\x82\xda\xe3\xb8\xa2*\xf2\x81\xe8\xfb $\xb4c\nU?\x95\x06\x10\xb7\xf6\xc3i|\x86\x88\xcagO\x9d\x7f\xf0s\x91AD\x0eRA\x1d\x915\xed\xab3\xfd.|\xceb|\x99AqP\xcf7\xe3\x9d\n%t\xc3\xd9\x11\x87\xc2\x8eD]V\x0b\xd59"\x0f\xdc\x19\x19\xed\xbc\xba\x83\xd5\x1d\xe0\xa3\xfc\x9b\xd5a\xb0\xe2C\x90\x0c\xe8q\xca&nd\x13\x03\x1dg9\x13\xe8\x8a@\xfb\x8c\xce\xe6Q\xe5\x06W\x19\xc0\xdeP0Z\x96\xe7\x85\xe5MaT}\x0e\xc0c\x08y\xf7\xf8\xff9\xea\x91H\x1f\xa0TC\xa4\xdf\x04\x07\x89l\x8dk\x91\n{\xd1;e\t=\x1f\xafAy\x17\x88ip\xd4F\x1d\xa3\x1a}\'\xfb\x1e\x05\xf9\x02gHK\x9a\xeeMx\xf0\xbc_\xf0\xb2\x8c\xd3\xb4\xc3\xd9\xa3\xb4\x85\xeeL)\xbe\x01\xee\xb2vP@P\x9c\x83\xbfp\xbe\xc3\xfa[\xb8kh?\xb2\xa3\xfbO\x8fJ\x8e\xc6\xbcG|x\xcb\xe3\x10\x14\x8b\xabC\xd4\xc3\x15:\xa7Jptk6\xa2\xc4\xb2b\x84&\xfe\xe7\xf2r\x89\xcf1\x9c\n\xec\xba\xfbG\x94X5*\x0e\xec\x8c\xdc\xb9\x8b\xc3\xe6Z\x91\x857\x1a\xd0\x1e\xdf{,\x9e\x06\x99\x1c\xe8$\x90\xdc\x10l\t\x02\xf8q"\xfa\x8a\xf8\x7f\x80\x14\xcc\xcd\xf0\xca\x16\x8fD\xd1|\xd1?\xaa\xf1+\x0bx\x9a\xa7G>M\x18\xa6\x08e\xd5\xe7KK\xfdk\xbc(\\et\xeb\xb0/\x19\xa3\xf09I\xc2\x0b\x99\xb8\xb0\x14\xa5\xf6\n\xd4\xa7#\xb6\x9a\xb4\x04\xcd\xc0\x96\x14~\x9f\x9aO\xf6F8\xbfx\x16\n\xfd`k\xe0U\xe9\xdc\xf8\xb5\xa8\x01Sc\x89\xa3\xea\xd8N\x83@\xaf\r0U\x96>\x03m\x81\xb5\xcb%3Lx\xd0p\xb3}\x13\xf1;\xef\xd4\xc5\x9b\xf2\xdc`\x88\x92\xb6\xe1\xd6\xd3J\xa4\xf4TBu\xf3W\'\xe54\x10?@\nN\x9b\xc0\xcb|\xb5\xea\xacY\x11?=~$o\xc5\x93^\xba(\x1as\x12\xed\xb7\xe25\xc8F\xcbV\xe10~\xc6tC\xadR\x19o\xb9yF\xda\x06\xda\x83}\xf6Kah"\xc2\xc9\xe1\\]6R\x11\xccn\xbe\xa1Mv\xe5).j^\xf2w\xbc\xcd\x8b\xbf`\x0f\xccuF\xaf\xac\xef\x04]\xd9\xc2-\x85\x1d<:?\x8f\x1b\x83,\xd2\xca\xb3\xb4\xf8B\x06W[u\xc1<H\x16\x198q\xf1}\x8a\xe8i\x87\x0b\xcf\xd7\x9f\x81\x8fY\xe4EQ\xa8\xd3\xcd\xed@\xc8!\xd1\x85\x95\x14\xfd4\t{\xcdw\xb5b%\xb3\x93\x9e\x0733v^\xa6\xa8\x9a\x9bD\xe1\xac\n\x97\x04v\xdb[X\x94\xf5e\x9a\x04,\x07<\x03\xda\x01\xd9\x83v\xe3\x10\x1eK\xc1\x85\x19T\xeb\xe6D\xf3\x82T\xc4\xa9\xdb\xf6E\xec,\xc2\xbb:J\xeb5\xd3\x14|\x96\xac9\xca\xf8\x94d5\xa1\xde(\x8b\xf6\x01\xa3:\xfdf\xa9\xec\xea\xdc\xda\x97~\x90\xb6P6\x99\xff\xe9\xb92\xfc%\xa9\xce\x99\xe2)\x10\\B\xdf6h\xde\x06\xe8\xe2\xd1\xce\xcfd!$\x17\x80\xd4C\xdbQy\x1f\xb9\x9eW\x1c\x1e\xa2\xed\xfdF\xc7_\xc0\xd0\xcd\x9b2_.>Tb\x89\x18\xbb\x91>\xc8\xe6\xb7\x1e\x83$\xceJpf\xca\xf6H\x03w8V\x89\xd7{\x1f\x80&E/K2\xe5\xd5\x80w\xb5d\xbb\xea0\x16\xc0\x042\xfbk\x1a\x0f8=\x16\xa3`\xae\xeb\x13\x1b\xa6\xb0\xccq\xbaL(j\x1aS\x97\xb7\x11At\x86G\xf1E\xfe\xf40i\xb3\x01\x812\xcd\x96r\xb2\x90r\xa1\x17#\xa6 \x1db\xf2\xaa&\xa7\xc8SN\x1a:9\xd0\x1d\xf9(\xb2\xe6\xfb\xc1\x1c\xf4\x98`"\xa2f\xbd\x00o\x93S\x11!\x83\xca\xd3\x01\xc7\xfcak\x1aK\xc3\xba\xa8\xfbuC\x94\xd7\x14\x13y({\xf5\x8aT\x15\xafLd\xe1T\xbb\xd7>[\x9bE\xf6a7\xed\x9b\x10\xbd@j3\xc3\xd7\xba\xbf\'R\xeb\x00\xb7\xe0f\xb2,\x11\xf3_^\x80\xd7?\xe8\xbd\xf0\xfa\x08\xca1\xa4\xad\x15\xd8\xa8>\xe9f\x00\xb9\xcdd\xcd:K?)#\x8b\xc3)I\x95\xbe\x9cZ5\x18H\x99\xd8EFJ\xe4G-\xd1\x88j\n0H\x13L\xb8ra_4\xc8\xcdP3\xa5V\xbe\xd0\xa9\xfd\xa3\xf7\x05\t\xea\x08\xea\xc3uR4\xca\x16s<\xd1v.\x14\x05\xc8\x9fH\x1b\xd9\x8dY\xeas\x97\x98\x80\x01\xf87\xd6\xbe\xda7\xc4\xfe\x97\x98\xb7\xdb\x1bC\x0b\x9d\n\x91P"U\xcf\xa5Z\xb4/-:^\r\xa4\x10\x10\x83,\xaf\xeav\xbb\x99\xe4\x9a\x16\xcc\xbe\xa6\x06\xa3\xb6\\J\xa7\x84 M<p;\x03\xb2\x02\xfb\x15\x80\xf1\xc86\x89\xe7\xbdO\xeb\x08\x0c\t\xc6\xf7\'\xbbCO\x7f\\-\n\xfd\x97\xaf pP5\xb0\xd4\xb4m\x94m\x9a \x94\xf3\xdb\x84\xae\x85\x172uB2k\x038\x84\xe2\x86\xe5\x8f*u(h3\xc4\xaa\xae0\xd4S\xd2\xd8k[\x80\xe8\x85\x1a\x80\xf6\xab\xdbz~\xd8|\xc7\xf3\xe5\xaf\xee$\xbf@\xc8\x81\xa9\x93-\xee\x03\xdfU)\x0f(\n.\xd7Q\x98~)\x13\xf6\x86\x8d\xd8\xd6\x1d\xea\xcblg\x97\xed9T\xf9\xc4Y\xfe~)\xd9\x05?\x8c\xa7m\xf6\xa7\xaa\xbf\x8f\xc3\xd7\xf0y\xa2!\xf2\xa0\xa8\x92sT\xefiL8\xf4\xc7I\xd2M\x1c\xadg5K\x1d\xe3\xfa\xe2\xa3\x10\x9f\xaf\xc3\x06AI\xc7&\x1f#\x9al\x81n\x8b\xb2!\xc27\x07\xc0\xee\x05\xba\xb8&\xa2\xecQ\\Vc\xd9\xd0\xbdf\x8aAi\xc1\xb7\xb0cc\x17\xf1=\xcf\xfbc\xd3\xe6\xf3^\xd16\x11\x9d)\xa1;\xd8\x88\xe8\xe6\xf4{z\x98\xcb\x03\x1a\x03)[\x92\xa8\xce\xac\xd1\x8e\xf7n\xd3\xc1\xd6\xd4\x81CSZ\x9d\xae\x85\xfcW\x1e\x06*\x9f%~>n*\xf2\x9bj\xef\xc8\xa2\x1e\xea\x87\x1b\xc6\x14\x9e\xe4\xa1Gd\xe7D\x15\x02\x9b\xf1\xbe\x13%,\xa7\xe8VR\xa6\xca\x05\xed\x13\x97\xd6\x9c\xb3\xccoO\t\x85\x94\xe5l\x08g\xeb\xc9Pq&\xea\x92a\xaa8[0\xf0\xcb@\x9f\x95\xfe\x02\xda\x0f+O\x15\x15\xf2L[z\x98\xe9'
26
'''

这题的漏洞点不在 AES，而在随机数生成器。脚本中所有随机值都来自random.getrandbits(128)，一眼 MT19937，只要泄露足够多连续输出，就可以恢复内部状态。题目中随机数调用顺序如下：

1
getrandbits(128)  -> IV
2
getrandbits(128) * 160 -> 160 个随机明文块
3
getrandbits(128)  -> AES key

每次getrandbits(128)会消耗 4 个 32-bit MT19937 输出。所以按 32-bit 输出编号，有：

1
output 0..3     -> IV
2
output 4..643   -> 160 个随机明文块
3
output 644..647 -> key

因为题目直接打印了AES key，所以可以先解 AES-CBC，恢复出除第 0 块外的全部明文块。这样就可以得到 160 个随机明文块，再加上已知key，总共得到outputs 4..647，也就是 644 个连续 32-bit MT19937 输出。这些输出足够反推出更早的 outputs 0..3，从而恢复 IV，再解出第 0 个明文块。

AES-CBC 明文恢复#

AES-CBC 解密关系为D(C_i) = P_i xor C_{i-1}，因此：

1
P_i = D(C_i) xor C_{i-1}, i >= 1

只有第 0 块需要 IV：P_0 = D(C_0) xor IV。

题目给出了key，所以可以对整个密文做 AES-ECB 解密，得到每个块的 D(C_i)。密文长度为 2608 字节即2608 / 16 = 163 blocks。后面固定拼接了 160 个随机块，所以 flag 补零后占163 - 160 = 3 blocks也就是 48 字节，可直接恢复第 2、3 个 flag 块，剩下的问题是恢复第 0 块，而第 0 块需要 IV。

Python getrandbits(128) 的字节顺序#

Python 的getrandbits(128)可以看作由 4 个 32-bit MT 输出组成：

1
x = out0 + (out1 << 32) + (out2 << 64) + (out3 << 96)

但是long_to_bytes(x)是大端字节序，所以最终 16 字节块表现为：

1
out3 || out2 || out1 || out0

因此从一个 16 字节随机块中解析 MT 输出时，需要反过来取：

1
def block_to_mt_outputs(block):
2
    words = [
3
        int.from_bytes(block[i:i + 4], "big")
4
        for i in range(0, 16, 4)
5
    ]
6
    return words[::-1]

这样就能从 160 个随机明文块和 key 中得到连续的 MT 输出：

1
outputs 4..647

MT19937 状态恢复#

MT19937 的输出经过temper操作。若已知输出值，可以通过untemper还原 raw state word。temper过程为：

1
y ^= y >> 11
2
y ^= (y << 7) & 0x9d2c5680
3
y ^= (y << 15) & 0xefc60000
4
y ^= y >> 18

写出对应的逆操作untemper后，就可以从输出恢复 raw state。

记 raw state 序列为X[i]，因为我们知道outputs 4..647，untemper 后得到X[4]..X[647]，MT19937 的 twist 递推关系为：

1
X[i + 624] = X[i + 397] xor mix(X[i], X[i + 1])

其中：

1
mix(a, b) = (((a & 0x80000000) | (b & 0x7fffffff)) >> 1) ^ mag01[b & 1]

mix(a, b)只依赖a的最高 bit 和b的低 31 bit。

反推 X[1], X[2], X[3]#

我们已知X[4]..X[647]，利用递推关系：

1
X[i + 624] = X[i + 397] xor mix(X[i], X[i + 1])

取i = 3：

1
X[627] = X[400] xor mix(X[3], X[4])

因为X[627]、X[400]、X[4]都已知，所以可以恢复X[3]的最高 bit。再取i = 2：

1
X[626] = X[399] xor mix(X[2], X[3])

因为X[626]、X[399]已知，并且刚才知道了X[3]的最高 bit，所以可以恢复X[3]的低 31 bit，同时恢复 X[2] 的最高 bit。

继续取i = 1和i = 0，可以恢复X[1]，X[2]，X[3]，X[0]的最高 bit，到这里还缺 X[0] 的低 31 bit。

关键一步：用 i = -1 恢复 X[0] 的低 31 bit#

这是本题最容易漏掉的地方。继续使用同一个递推关系：

1
X[i + 624] = X[i + 397] xor mix(X[i], X[i + 1])

取i = -1，等价于：

1
X[623] = X[396] xor mix(X[-1], X[0])

这里X[623]和X[396]已知，所以：

1
mix(X[-1], X[0]) = X[623] xor X[396]

虽然X[-1]本身未知，但mix(X[-1], X[0])只依赖X[-1]的最高 bit 和X[0]的低 31 bit，因此可以直接枚举X[-1]的最高 bit，反推出X[0]的低 31 bit。再结合前面已经恢复的 X[0] 最高 bit，就可以完整恢复X[0]，于是X[0]..X[3]全部恢复，对它们重新temper，就能得到outputs 0..3，也就是完整 IV。

exp.py：

1
from Crypto.Cipher import AES
2

3
MASK = 0xffffffff
4
MATRIX_A = 0x9908b0df
5
UPPER = 0x80000000
6
LOWER = 0x7fffffff
7

8
def xor_bytes(a, b):
9
    return bytes(x ^ y for x, y in zip(a, b))
10

11
def temper(x):
12
    y = x & MASK
13
    y ^= y >> 11
14
    y ^= (y << 7) & 0x9d2c5680
15
    y ^= (y << 15) & 0xefc60000
16
    y ^= y >> 18
17
    return y & MASK
18

19
def unright(y, shift):
20
    x = 0
21
    for i in range(31, -1, -1):
22
        bit = (y >> i) & 1
23
        if i + shift < 32:
24
            bit ^= (x >> (i + shift)) & 1
25
        x |= bit << i
26
    return x & MASK
27

28
def unleft(y, shift, mask):
29
    x = 0
30
    for i in range(32):
31
        bit = (y >> i) & 1
32
        if i - shift >= 0 and ((mask >> i) & 1):
33
            bit ^= (x >> (i - shift)) & 1
34
        x |= bit << i
35
    return x & MASK
36

37
def untemper(y):
38
    y = unright(y, 18)
39
    y = unleft(y, 15, 0xefc60000)
40
    y = unleft(y, 7, 0x9d2c5680)
41
    y = unright(y, 11)
42
    return y & MASK
43

44
def mix(a, b):
45
    y = (a & UPPER) | (b & LOWER)
46
    return ((y >> 1) ^ (MATRIX_A if y & 1 else 0)) & MASK
47

48
def inv_mix_from_z(z):
49
    """
50
    z = mix(a, b)
51
    mix 只依赖：
52
    - a 的最高 bit
53
    - b 的低 31 bit
54
    返回：
55
    - a 的最高 bit
56
    - b 的低 31 bit
57
    """
58
    z &= MASK
59
    for lsb in (0, 1):
60
        y = ((z ^ (MATRIX_A if lsb else 0)) << 1) & MASK
61
        y |= lsb
62
        yield y & UPPER, y & LOWER
63

64
def inv_mix_get_prev_upper(z, b):
65
    """
66
    z = mix(a, b)，b 已知。
67
    反推出 a 的最高 bit。
68
    """
69
    z &= MASK
70
    b &= MASK
71
    y = ((z ^ (MATRIX_A if (b & 1) else 0)) << 1) & MASK
72
    y |= b & 1
73
    assert (y & LOWER) == (b & LOWER)
74
    return y & UPPER
75

76
def block_to_mt_outputs(block):
77
    """
78
    Python getrandbits(128) 的 4 个 32-bit 输出顺序是：
79
        out0 + (out1 << 32) + (out2 << 64) + (out3 << 96)
80
    long_to_bytes 是大端，所以字节块为：
81
        out3 || out2 || out1 || out0
82
    """
83
    words = [
84
        int.from_bytes(block[i:i + 4], "big")
85
        for i in range(0, 16, 4)
86
    ]
87
    return words[::-1]
88

89
key = b'\xd0\xa2\x10\x8bH!\x0b\x80\xec\xe2lDo\xf1\xb00'
90
cipher = b'\xf8{\x90\xc2B\x80\xa6\xb5\x12\x9e\x99s\xa6\xf3\x12D,\x9b\x9b\xe4\xa0\x1c\xe1\xb1\x03\xfb!\xc1\xe0\x80l\x94#1\xc2\xa7b\xc5:g\xe5\xdf*\xca\x0b\xe9\xda\x9d\xfa\x1d\xc1\xb9\x1en\xc1\x8e1].\xcb\xad\xb4\x8cC\x16C\x01\x118\x87+\xe6L\xd7\xd6\x8b\nw\xba@q8\x1e\x15?[B\xb7>t\xeb\xadpE\xa8\x04mL#\x89\xc7\xd3\xac~D\xa4=j\xb8\xb0J\r?\xc9\xe4J7U,\x9d2\xb1\xe1L\x86\xe6\xf4-\x9bS!\xd3\xe0\xc6\xdd\x8b\xb2pj\xe7:>{\xf7\xfa\x0fI\xb5,\xeeS\xbfc?\xe1\x1b\t?\xa3?\xae\x19-\xb6\xf3\x94\x13*\x02d\xb4\xe0\x98\x91@y\n\x1av\'WOb\xec\xed/\x99\xb1\xab\xa6\xd2OU\xa4\xbf`w@\x9e\xab\xae\xecYbf\xe7\x86\xa1\xc6\x1c;X\xd4\x97!\xaf\xe0\xc1\xc4\xa74k\xf1\x9f8Ol\x07x\x88\x10\xe0\xa2\xc6u\xb9\xf6\xa7\x0cs~\xbe\xf0H*\xc6\xe4\xcbN\x8d\xf1\xc7Frc5\xf7\xc3\x91M7M\xec\xbe\xd81iO\xb5/\xe9\xd2\x17\xe0$\x97S<\xb2\x9e\xd5\xd3\xb13m(~=\xa3\xfd\xc9\t\xa1Ry\x18\xd2\x1b\x19\xb2\xb6\x07\x97?\x9a_q\x0f\x86f\xe5\xac\r\x03\xe9NY\x823\x0f\x01\xf3\x14`\xafB\xa54\xef\x8e\xa1\xcc\xa7I\xb2\x1c|\xed\xbeOn[\xa8G\x96\x96d\n\xebCX\x8d\x92\x93\x13\x9c\x00-\x9c8G\xa0\x8b\x03\xaf&\x8e\xf45\'\xad\xae\xc7L\xcc\xd7\x83\x87\xc31\xa5\x83\xdf\xf5\xf4Md\x9c\x14\x9b77\xcb\xde}\x87}\x94\xdb\xd8\xca\xf8(\xaf~e\x85\x9cm}EG \xca\xd0\x83\xb3\x9by4j?H\xfc\x10#\x8e\xab\xe4pr\x16pw\xf1\xec\xa4\xfd\xbbo\x19,$\xc2/\x95%yL"\x17\x890\xdc\xdf\x04zv\x12\x9c:}\xfe\xfc\x84\xc1\xc8\x02\x96\xa3\xc9\xb9\x7f\xc90\x11P<\\\xaa\xfe_V\'\x92\xe6\xb3\x15S\xad64R\x87*\xc14\xa9\xae\xc6\xd6t\xab\x1d$\xcf:\xf4\xa7#6\xe7\x94\xdf\xcb\xe9\xb4@\xaa\xd3Y\x88Sl\xa9\x0f\xe1\x0fh\x02\x8a\x91\xf8:\xacDrT\xa2\xa4\x97_\xda9\xdaP\xaaf\xe7\xc4\x0f`F`\x874\xd2\xee\xc3#|\xe8\xb8\xac\xd2\x00\xc6J\x8e\xd5!\xe4I\xa4\xe9B\xfc\x97\xa6\xa2\xe43\x16Cp\x86\xb90\x16\xb4\xc0\xa94yo\xcfc\x95\x89\xca\xd9\xe37#\x9a\xd9d\xb1=\x13\xfc\xfcZ\xfd^\xaa\xd5\x12\x8d\xce\x05R\x8b\xc9\xd2\xfaZ\xf4\xea\x91o<\x14\xae%\x1d\xcfJ\x12dW\xa5p\x15\x00\xfc\x10f\xfc6\xc6\xaa/\xdc\xd2\xe9\xa0f\xb6\xc1\x86\xd3~N\xac\x9d\x87TdH\x7fE3\x95\xc37N#\xb7\x00A\xbf\xe6\xe6\xbc\xbf\xf3K\xbe\xe6\xea\xbf\xb1d\x92\xb9\xba\xe2\x0f\xd3<\x0b\xeb\x98\x97Q\x06]\xe1\xe4K\x89*\xba\x8a\xe4~\xbf\'Tu\xba\xdajF\xae\x8b\x1c{\x14\xa3\xc2\xff\xcc3j\xee\xed|\xa9\xa4\xb4\xfcU\xb5\xbf\x81\xcb1I\x80\xa9\x88\r\xe0\x06\x81z\x16\x0f\xdc\x80^\x94\x18\x1bLd\xe5\x0e\xc9\xe8m\xaa\xdf\xadJ\x03u*\x0f\xcf>\xb2;TOq^\xbc\xb4f(\xedIa8%sA\xc1\x92F\x8d/\xe6\xb2\x18\xa0\x0b\rD\x06\x8b\xd24_M?\x1d\x95\xa1yb\x8f\xec\x82\xe5\x12\xe7Wq\x1a\xd1\x158/\x17\x180\xae@\x869\x96f%!E\x0f\xee7\xcaFF\x9a-1$\x16\xd9\x17l|\xff0\xd3\xe8\xac\x19\x80\x95u\x9c{\x14i}f\xdbk\xf6\xfb\xa5\xa3^+\xa7\xc3<\xe9-\xa3A\x03N\xa3+\xc8\x15WC\xaa\x92\xefz\x01\xd6gq4\x12\xeb\xfe^-Ejg\xf7\\\xe9\x82\xde\x91\x1cD\x91nz\xc7\xf1\xcd\x01\xc7\xf0\xcbo\xda\xd8o\xacZ\x11\xd4\xc9\t\x14A\x00\xb0!\xa1\x9e\x1b\xc3\xca\xed\xf1^M\xd6\xa8\xe7\xf4\xe3\x0cCZ\x93\xa8{\x98\x85a\x82\xe4\xb8\x1c59\xeaE\xc4\xf6\x04Ui\x84lPV\x98\xc9\xce\x02o\x07\xe6\xb6\xdc>a+\x13\x14\xe0\xb6\xa0\xb0\xc88\xd9~\x05k\xd1E+\x8d\xe0o\xed\x15\x89\xd5\xa2\xc2\xe0\xb3\xe0]\xf3\xb2\xaa_W\xa4s\xf6`$\xa9\x9da\x13\xc9e\r\xd3\x97\xedB\xe5\xd6\x1cB\x15\xc2_\x117\x9fE\x8a\xc7<\x8a\xb9\x96\xc8$\x80\xe2\xab\x14K\x9aJ\xa1\t\xf7=\xc5\x8f{.Ml\x83\xa58\x1e\xf9\xa4\xafw\x00\xed\xd0\xb6\r\xd2\x9f\xf7h\xf3\x82,X\xfc\t\'\xdf\xd6H\x82\xda\xe3\xb8\xa2*\xf2\x81\xe8\xfb $\xb4c\nU?\x95\x06\x10\xb7\xf6\xc3i|\x86\x88\xcagO\x9d\x7f\xf0s\x91AD\x0eRA\x1d\x915\xed\xab3\xfd.|\xceb|\x99AqP\xcf7\xe3\x9d\n%t\xc3\xd9\x11\x87\xc2\x8eD]V\x0b\xd59"\x0f\xdc\x19\x19\xed\xbc\xba\x83\xd5\x1d\xe0\xa3\xfc\x9b\xd5a\xb0\xe2C\x90\x0c\xe8q\xca&nd\x13\x03\x1dg9\x13\xe8\x8a@\xfb\x8c\xce\xe6Q\xe5\x06W\x19\xc0\xdeP0Z\x96\xe7\x85\xe5MaT}\x0e\xc0c\x08y\xf7\xf8\xff9\xea\x91H\x1f\xa0TC\xa4\xdf\x04\x07\x89l\x8dk\x91\n{\xd1;e\t=\x1f\xafAy\x17\x88ip\xd4F\x1d\xa3\x1a}\'\xfb\x1e\x05\xf9\x02gHK\x9a\xeeMx\xf0\xbc_\xf0\xb2\x8c\xd3\xb4\xc3\xd9\xa3\xb4\x85\xeeL)\xbe\x01\xee\xb2vP@P\x9c\x83\xbfp\xbe\xc3\xfa[\xb8kh?\xb2\xa3\xfbO\x8fJ\x8e\xc6\xbcG|x\xcb\xe3\x10\x14\x8b\xabC\xd4\xc3\x15:\xa7Jptk6\xa2\xc4\xb2b\x84&\xfe\xe7\xf2r\x89\xcf1\x9c\n\xec\xba\xfbG\x94X5*\x0e\xec\x8c\xdc\xb9\x8b\xc3\xe6Z\x91\x857\x1a\xd0\x1e\xdf{,\x9e\x06\x99\x1c\xe8$\x90\xdc\x10l\t\x02\xf8q"\xfa\x8a\xf8\x7f\x80\x14\xcc\xcd\xf0\xca\x16\x8fD\xd1|\xd1?\xaa\xf1+\x0bx\x9a\xa7G>M\x18\xa6\x08e\xd5\xe7KK\xfdk\xbc(\\et\xeb\xb0/\x19\xa3\xf09I\xc2\x0b\x99\xb8\xb0\x14\xa5\xf6\n\xd4\xa7#\xb6\x9a\xb4\x04\xcd\xc0\x96\x14~\x9f\x9aO\xf6F8\xbfx\x16\n\xfd`k\xe0U\xe9\xdc\xf8\xb5\xa8\x01Sc\x89\xa3\xea\xd8N\x83@\xaf\r0U\x96>\x03m\x81\xb5\xcb%3Lx\xd0p\xb3}\x13\xf1;\xef\xd4\xc5\x9b\xf2\xdc`\x88\x92\xb6\xe1\xd6\xd3J\xa4\xf4TBu\xf3W\'\xe54\x10?@\nN\x9b\xc0\xcb|\xb5\xea\xacY\x11?=~$o\xc5\x93^\xba(\x1as\x12\xed\xb7\xe25\xc8F\xcbV\xe10~\xc6tC\xadR\x19o\xb9yF\xda\x06\xda\x83}\xf6Kah"\xc2\xc9\xe1\\]6R\x11\xccn\xbe\xa1Mv\xe5).j^\xf2w\xbc\xcd\x8b\xbf`\x0f\xccuF\xaf\xac\xef\x04]\xd9\xc2-\x85\x1d<:?\x8f\x1b\x83,\xd2\xca\xb3\xb4\xf8B\x06W[u\xc1<H\x16\x198q\xf1}\x8a\xe8i\x87\x0b\xcf\xd7\x9f\x81\x8fY\xe4EQ\xa8\xd3\xcd\xed@\xc8!\xd1\x85\x95\x14\xfd4\t{\xcdw\xb5b%\xb3\x93\x9e\x0733v^\xa6\xa8\x9a\x9bD\xe1\xac\n\x97\x04v\xdb[X\x94\xf5e\x9a\x04,\x07<\x03\xda\x01\xd9\x83v\xe3\x10\x1eK\xc1\x85\x19T\xeb\xe6D\xf3\x82T\xc4\xa9\xdb\xf6E\xec,\xc2\xbb:J\xeb5\xd3\x14|\x96\xac9\xca\xf8\x94d5\xa1\xde(\x8b\xf6\x01\xa3:\xfdf\xa9\xec\xea\xdc\xda\x97~\x90\xb6P6\x99\xff\xe9\xb92\xfc%\xa9\xce\x99\xe2)\x10\\B\xdf6h\xde\x06\xe8\xe2\xd1\xce\xcfd!$\x17\x80\xd4C\xdbQy\x1f\xb9\x9eW\x1c\x1e\xa2\xed\xfdF\xc7_\xc0\xd0\xcd\x9b2_.>Tb\x89\x18\xbb\x91>\xc8\xe6\xb7\x1e\x83$\xceJpf\xca\xf6H\x03w8V\x89\xd7{\x1f\x80&E/K2\xe5\xd5\x80w\xb5d\xbb\xea0\x16\xc0\x042\xfbk\x1a\x0f8=\x16\xa3`\xae\xeb\x13\x1b\xa6\xb0\xccq\xbaL(j\x1aS\x97\xb7\x11At\x86G\xf1E\xfe\xf40i\xb3\x01\x812\xcd\x96r\xb2\x90r\xa1\x17#\xa6 \x1db\xf2\xaa&\xa7\xc8SN\x1a:9\xd0\x1d\xf9(\xb2\xe6\xfb\xc1\x1c\xf4\x98`"\xa2f\xbd\x00o\x93S\x11!\x83\xca\xd3\x01\xc7\xfcak\x1aK\xc3\xba\xa8\xfbuC\x94\xd7\x14\x13y({\xf5\x8aT\x15\xafLd\xe1T\xbb\xd7>[\x9bE\xf6a7\xed\x9b\x10\xbd@j3\xc3\xd7\xba\xbf\'R\xeb\x00\xb7\xe0f\xb2,\x11\xf3_^\x80\xd7?\xe8\xbd\xf0\xfa\x08\xca1\xa4\xad\x15\xd8\xa8>\xe9f\x00\xb9\xcdd\xcd:K?)#\x8b\xc3)I\x95\xbe\x9cZ5\x18H\x99\xd8EFJ\xe4G-\xd1\x88j\n0H\x13L\xb8ra_4\xc8\xcdP3\xa5V\xbe\xd0\xa9\xfd\xa3\xf7\x05\t\xea\x08\xea\xc3uR4\xca\x16s<\xd1v.\x14\x05\xc8\x9fH\x1b\xd9\x8dY\xeas\x97\x98\x80\x01\xf87\xd6\xbe\xda7\xc4\xfe\x97\x98\xb7\xdb\x1bC\x0b\x9d\n\x91P"U\xcf\xa5Z\xb4/-:^\r\xa4\x10\x10\x83,\xaf\xeav\xbb\x99\xe4\x9a\x16\xcc\xbe\xa6\x06\xa3\xb6\\J\xa7\x84 M<p;\x03\xb2\x02\xfb\x15\x80\xf1\xc86\x89\xe7\xbdO\xeb\x08\x0c\t\xc6\xf7\'\xbbCO\x7f\\-\n\xfd\x97\xaf pP5\xb0\xd4\xb4m\x94m\x9a \x94\xf3\xdb\x84\xae\x85\x172uB2k\x038\x84\xe2\x86\xe5\x8f*u(h3\xc4\xaa\xae0\xd4S\xd2\xd8k[\x80\xe8\x85\x1a\x80\xf6\xab\xdbz~\xd8|\xc7\xf3\xe5\xaf\xee$\xbf@\xc8\x81\xa9\x93-\xee\x03\xdfU)\x0f(\n.\xd7Q\x98~)\x13\xf6\x86\x8d\xd8\xd6\x1d\xea\xcblg\x97\xed9T\xf9\xc4Y\xfe~)\xd9\x05?\x8c\xa7m\xf6\xa7\xaa\xbf\x8f\xc3\xd7\xf0y\xa2!\xf2\xa0\xa8\x92sT\xefiL8\xf4\xc7I\xd2M\x1c\xadg5K\x1d\xe3\xfa\xe2\xa3\x10\x9f\xaf\xc3\x06AI\xc7&\x1f#\x9al\x81n\x8b\xb2!\xc27\x07\xc0\xee\x05\xba\xb8&\xa2\xecQ\\Vc\xd9\xd0\xbdf\x8aAi\xc1\xb7\xb0cc\x17\xf1=\xcf\xfbc\xd3\xe6\xf3^\xd16\x11\x9d)\xa1;\xd8\x88\xe8\xe6\xf4{z\x98\xcb\x03\x1a\x03)[\x92\xa8\xce\xac\xd1\x8e\xf7n\xd3\xc1\xd6\xd4\x81CSZ\x9d\xae\x85\xfcW\x1e\x06*\x9f%~>n*\xf2\x9bj\xef\xc8\xa2\x1e\xea\x87\x1b\xc6\x14\x9e\xe4\xa1Gd\xe7D\x15\x02\x9b\xf1\xbe\x13%,\xa7\xe8VR\xa6\xca\x05\xed\x13\x97\xd6\x9c\xb3\xccoO\t\x85\x94\xe5l\x08g\xeb\xc9Pq&\xea\x92a\xaa8[0\xf0\xcb@\x9f\x95\xfe\x02\xda\x0f+O\x15\x15\xf2L[z\x98\xe9'
91
print("[+] cipher length =", len(cipher))
92
print("[+] blocks =", len(cipher) // 16)
93
aes = AES.new(key, AES.MODE_ECB)
94
dec = aes.decrypt(cipher)
95
cblocks = [cipher[i:i + 16] for i in range(0, len(cipher), 16)]
96
dblocks = [dec[i:i + 16] for i in range(0, len(dec), 16)]
97
# CBC: P_i = D(C_i) xor C_{i-1}, i >= 1
98
pblocks = [None]
99
for i in range(1, len(cblocks)):
100
    pblocks.append(xor_bytes(dblocks[i], cblocks[i - 1]))
101
flag_blocks = len(cblocks) - 160
102
print("[+] flag padded blocks =", flag_blocks)
103
assert flag_blocks == 3
104
print("[+] known P1 =", pblocks[1])
105
print("[+] known P2 =", pblocks[2])
106
# 已知随机明文块 P[3:]，以及 key，全部都是 getrandbits(128) 结果
107
known_outputs = []
108
for block in pblocks[3:] + [key]:
109
    known_outputs.extend(block_to_mt_outputs(block))
110
# outputs 4..647，共 644 个
111
assert len(known_outputs) == 644
112
known_raw = [untemper(x) for x in known_outputs]
113
# 记 raw 序列为 X[i]
114
# 已知 X[4..623] 和 X[624..647]
115
X = {}
116
for i in range(4, 624):
117
    X[i] = known_raw[i - 4]
118
for i in range(624, 648):
119
    X[i] = known_raw[i - 4]
120
# 先利用 i = 3, 2, 1, 0 反推 X[3], X[2], X[1], X[0] 的最高 bit
121
# X[i + 624] = X[i + 397] ^ mix(X[i], X[i + 1])
122
# i = 3:
123
# X[627] ^ X[400] = mix(X[3], X[4])
124
up3 = inv_mix_get_prev_upper(X[627] ^ X[400], X[4])
125
solutions = []
126
# i = 2:
127
for up2, low3 in inv_mix_from_z(X[626] ^ X[399]):
128
    x3 = up3 | low3
129
    if mix(x3, X[4]) != (X[627] ^ X[400]):
130
        continue
131

132
    # i = 1:
133
    for up1, low2 in inv_mix_from_z(X[625] ^ X[398]):
134
        x2 = up2 | low2
135
        if mix(x2, x3) != (X[626] ^ X[399]):
136
            continue
137
        # i = 0:
138
        for up0, low1 in inv_mix_from_z(X[624] ^ X[397]):
139
            x1 = up1 | low1
140
            if mix(x1, x2) != (X[625] ^ X[398]):
141
                continue
142
            # 此时只能得到 X[0] 的最高 bit
143
            if mix(up0, x1) != (X[624] ^ X[397]):
144
                continue
145
            solutions.append((up0, x1, x2, x3))
146
assert len(solutions) == 1
147
up0, X[1], X[2], X[3] = solutions[0]
148
# 关键补刀：
149
# 取 i = -1:
150
# X[623] = X[396] ^ mix(X[-1], X[0])
151
# 虽然 X[-1] 不知道，但是 mix 只需要 X[-1] 的最高 bit，
152
# 所以可以反推出 X[0] 的低 31 bit。
153
z = X[623] ^ X[396]
154
x0_candidates = []
155
for prev_upper, low0 in inv_mix_from_z(z):
156
    x0 = up0 | low0
157
    if mix(prev_upper, x0) == z:
158
        x0_candidates.append(x0)
159
assert len(x0_candidates) == 1
160
X[0] = x0_candidates[0]
161
print("[+] raw X0 =", hex(X[0]))
162
print("[+] raw X1 =", hex(X[1]))
163
print("[+] raw X2 =", hex(X[2]))
164
print("[+] raw X3 =", hex(X[3]))
165
out0 = temper(X[0])
166
out1 = temper(X[1])
167
out2 = temper(X[2])
168
out3 = temper(X[3])
169
# IV bytes = out3 || out2 || out1 || out0
170
iv = (
171
    out3.to_bytes(4, "big")
172
    + out2.to_bytes(4, "big")
173
    + out1.to_bytes(4, "big")
174
    + out0.to_bytes(4, "big")
175
)
176
print("[+] recovered IV =", iv.hex())
177
# CBC 第 0 块：
178
p0 = xor_bytes(dblocks[0], iv)
179
flag = (p0 + pblocks[1] + pblocks[2]).rstrip(b"\x00")
180
print("[+] P0 =", p0)
181
print("[+] flag =", flag.decode())
182

183
"""
184
[+] key = d0a2108b48210b80ece26c446ff1b030
185
[+] cipher length = 2608
186
[+] blocks = 163
187
[+] flag padded blocks = 3
188
[+] known P1 = b'58-4587-8d34-ccf'
189
[+] known P2 = b'fbe81eb16}\x00\x00\x00\x00\x00\x00'
190
[+] raw X0 = 0x53f2cef1
191
[+] raw X1 = 0xfa626130
192
[+] raw X2 = 0xbc38e3cd
193
[+] raw X3 = 0xfae3445
194
[+] recovered IV = 5a0f97802b0f2e926bff2183adb4cfc5
195
[+] P0 = b'flag{75b24dd7-e7'
196
[+] flag = flag{75b24dd7-e758-4587-8d34-ccffbe81eb16}
197
"""

ps：MT19937 还是不太熟练了，直接纯 GPT 神力了，简单看看叭就。

RsaComb#

题目：

1
import hashlib
2
import random
3
from math import gcd
4

5
from Crypto.Util.number import bytes_to_long, getPrime, inverse
6
from sage.all import Permutations
7
from secret import flag
8

9

10
p = getPrime(1024)
11
q = getPrime(1024)
12
n = p * q
13
phi = (p - 1) * (q - 1)
14

15
while True:
16
    d = random.getrandbits(512)
17
    if gcd(d, phi) == 1 and 36 * pow(d, 4) < n and d.bit_length() > 401:
18
        break
19

20
e = inverse(d, phi)
21

22
m = bytes_to_long(flag)
23
assert m.bit_length() < 512
24

25
print("simple rsa, but this time you can not get my e!")
26
print(f"n = {n}")
27
print(f"c = {pow(m, e, n)}")
28
print(f"e = {str(e).encode()[:4]}")
29

30
print("\na gift_e for you")
31
gift_e = getPrime(224)
32
gift_d = inverse(gift_e, phi)
33
print(f"gift_e = {pow(e, gift_d, n)}")
34

35
print("\nHow to use ? enjoy the magic_problem")
36
def cycle_lengths(perm):
37
    values = list(perm)
38
    visited = [False] * len(values)
39
    lengths = []
40
    for start in range(len(values)):
41
        if visited[start]:
42
            continue
43
        current = start
44
        length = 0
45
        while not visited[current]:
46
            visited[current] = True
47
            length += 1
48
            current = values[current] - 1
49
        lengths.append(length)
50
    return lengths
51

52

53
def good_magic_perm(perm):
54
    lengths = cycle_lengths(perm)
55
    if any(length % 3 == 0 for length in lengths):
56
        return False
57

58
    even_counts = {}
59
    for length in lengths:
60
        if length % 2 == 0:
61
            even_counts[length] = even_counts.get(length, 0) + 1
62
    return any(count % 2 == 1 for count in even_counts.values())
63

64

65
Gift = Permutations(256).random_element()
66
while not good_magic_perm(Gift):
67
    Gift = Permutations(256).random_element()
68
print(Gift ** 3)
69
print([
70
    x ^ y
71
    for x, y in zip(
72
        hashlib.sha3_512(b"RsaCombV2|" + str(Gift).encode()).digest(),
73
        str(gift_e).encode()[::-1],
74
    )
75
])

题目分为两部分，RSA 部分是常规的 Wiener 攻击，能恢复完整e就可以轻松解决。但是题目并没有给出实际的e，而是给出了一个str(e)的前 4 字节以及一个所谓的gift_e。脚本令gift_d = inverse(gift_e, phi)，然后输出pow(e, gift_d, n)。记输出的大数为Egift，则：

Egift\equiv e^{gift\_d}\pmod{n}

由于

gift\_e * gift\_d \equiv1 \pmod{\varphi(n)}

因此

Egift^{gift\_e} \equiv e\pmod{n}

所以问题转化为恢复真正的 224-bit 素数gift_e。

gift_e被 permutation 部分隐藏。题目随机生成Gift，并保证Gift 的所有循环长度都不被 3 整除，然后输出Gift ** 3。对于一个长度为L的循环，如果gcd(3, L) = 1，则三次幂在该循环上可逆。设输出的置换为

1
H = Gift ** 3

在每个循环上计算inv3 = 3^{-1} mod L，就有Gift = H ** inv3。因此可以从H唯一恢复Gift，当然也可以无脑点，题目给出的限制条件会使Gift唯一，用sage中Permutation类的nth_roots()函数恢复Gift也行：

1
H = Permutation([...])
2
Gift = list(H.nth_roots(3))

exp里就直接用 GPT 写的函数恢复了。

恢复Gift后计算sha3_512(b"RsaCombV2|" + str(Gift).encode()).digest()，再与题目给出的 64 字节数组异或，可以得到str(gift_e).encode()[::-1][:64]，即gift_e十进制表示末尾 64 位的逆序。因为gift_e是 224-bit 素数，其十进制长度只有 67 或 68 位，所以只需爆破前 3 或 4 位，并用 bit_length、素性测试以及e的已知前缀 b’2543’ 过滤即可。

exp.py：

1
from Crypto.Util.number import isPrime, long_to_bytes
2
from hashlib import sha3_512
3

4
def recover_perm_from_cube(H):
5
    """
6
    H = Gift^3.
7
    置换用 1-based image list 表示。
8
    因为 Gift 的所有循环长度都不被 3 整除，
9
    所以每个循环上都可以取 3 的逆元恢复 Gift。
10
    """
11
    N = len(H)
12
    seen = [False] * (N + 1)
13
    G = [0] * (N + 1)
14
    for start in range(1, N + 1):
15
        if seen[start]:
16
            continue
17
        cyc = []
18
        x = start
19
        while not seen[x]:
20
            seen[x] = True
21
            cyc.append(x)
22
            x = H[x - 1]
23
        L = len(cyc)
24
        if L % 3 == 0:
25
            raise ValueError("cycle length divisible by 3")
26
        inv3 = pow(3, -1, L)
27
        for i, x in enumerate(cyc):
28
            G[x] = cyc[(i + inv3) % L]
29
    return G[1:]
30

31
class ContinuedFraction():
32
    def __init__(self, numerator, denominator):
33
        self.numberlist = []
34
        self.fractionlist = []
35
        self.GenerateNumberList(numerator, denominator)
36
        self.GenerateFractionList()
37

38
    def GenerateNumberList(self, numerator, denominator):
39
        # 生成简单连分数
40
        while numerator != 1:
41
            quotient = numerator // denominator
42
            remainder = numerator % denominator
43
            self.numberlist.append(quotient)
44
            numerator = denominator
45
            denominator = remainder
46

47
    def GenerateFractionList(self):
48
        self.fractionlist.append([self.numberlist[0], 1])
49
        for i in range(1, len(self.numberlist)):
50
            numerator = self.numberlist[i]
51
            denominator = 1
52
            for j in range(i):
53
                temp = numerator
54
                numerator = denominator + numerator * self.numberlist[i - j - 1]
55
                denominator = temp
56
            self.fractionlist.append([numerator, denominator])
57

58
n = 9255291751880445288870572522017487995584547663979234757693816085089020430119070002490425642734801619061183697679452633025322885628563224649552057886740933431539713859273280725866094649013473047535287674756844637587560806590241273403262474304542761149791407330973745320333684963310642261989069497321640633957185440704852760659717784163571987947083199371979083092012735288122276098719485385522641892728932368890653395195165081416222768880612865608600539794582810313366333262478928323220756117152405217842150085039666615287931956139986386333375843396284682353530902981549442348179929347669127887005117616573029837793989
59
c = 96735618756237464828737083120351317336039496897799663455927664178900841302474361876086224679902179097035065900519532923991173317254409155919432371926821159016182429742643096731534714099320158748412816395265447120709775146713474760415269564165188026932403099271266589505572068084417654623993463808489836781983820824599382127597746670823695131445541507061924797452463084477246937821139153368695192543745077708914325452912022241535496340068382553788602652721139339813247578162057108332165436681363076372463838197612298480736237684077667300689294301698822851084969278330076056205773185307120795521950835577328304215059
60
e_prefix = '2543'
61
Egift = 9027267807000258739919159451695219324195629947118106243835644105059507908448938424473860161636471689503683187832151597955211023188904124254767092931849312068084428919037453749958277779097008482680609955950431774164274891590265394849245859917231882598389887574495620591576018315340194784915821008329345875155163785060210259939655173196305145727638495782354653405408141018883657042671400657549748935779645589878437972678147553536674490540328154626005034561000001338650665925708206881974354981161860630339220731717967031600307823293625596584602649115272748539003484466153279634696354975835875051492632382213523667951679
62
H = [12, 104, 35, 246, 223, 15, 119, 170, 221, 56, 115, 210, 175, 70, 141, 46, 60, 190, 131, 55, 196, 94, 116, 73, 162, 92, 174, 107, 29, 39, 180, 80, 84, 197, 160, 105, 75, 1, 93, 106, 199, 53, 204, 244, 108, 18, 145, 195, 77, 103, 44, 157, 4, 127, 25, 50, 150, 235, 36, 222, 153, 179, 38, 67, 47, 234, 192, 144, 34, 239, 125, 113, 181, 240, 182, 40, 218, 19, 41, 151, 99, 207, 242, 189, 54, 126, 147, 166, 130, 186, 154, 62, 9, 215, 89, 178, 216, 133, 173, 250, 252, 148, 121, 5, 183, 231, 161, 97, 109, 205, 203, 184, 23, 58, 226, 76, 122, 255, 238, 63, 98, 91, 69, 159, 6, 158, 83, 168, 220, 249, 87, 251, 59, 3, 74, 27, 21, 237, 17, 213, 26, 134, 224, 100, 42, 201, 164, 211, 114, 81, 163, 194, 137, 118, 65, 51, 2, 191, 37, 88, 200, 16, 185, 20, 95, 45, 124, 253, 24, 71, 138, 214, 120, 28, 172, 248, 128, 187, 112, 72, 132, 31, 177, 13, 135, 86, 48, 167, 228, 136, 140, 188, 32, 43, 198, 30, 111, 129, 256, 33, 247, 142, 202, 208, 152, 79, 78, 230, 10, 232, 61, 171, 64, 14, 8, 243, 149, 219, 22, 236, 7, 49, 96, 212, 85, 193, 66, 57, 101, 117, 241, 169, 229, 11, 217, 90, 68, 52, 165, 206, 110, 146, 139, 82, 123, 233, 156, 143, 245, 155, 209, 102, 176, 254, 225, 227]
63
xor_list = [56, 209, 107, 183, 193, 204, 10, 115, 135, 14, 92, 57, 2, 104, 250, 14, 26, 4, 169, 97, 169, 220, 8, 218, 29, 162, 220, 81, 156, 144, 213, 215, 3, 90, 144, 47, 4, 130, 164, 7, 152, 200, 24, 167, 184, 112, 25, 49, 225, 86, 118, 119, 248, 210, 179, 138, 208, 86, 252, 219, 10, 14, 230, 237]
64
Gift = recover_perm_from_cube(H)
65
recovered_reversed = bytes(a ^ b for a, b in zip(xor_list, sha3_512(b"RsaCombV2|" + str(Gift).encode()).digest()))
66
suffix64 = recovered_reversed[::-1].decode()
67
e = None
68
for total_len in (67, 68):
69
    prefix_len = total_len - 64
70
    for prefix in range(10 ** (prefix_len - 1), 10 ** prefix_len):
71
        gift_e = int(str(prefix) + suffix64)
72
        if gift_e.bit_length() != 224:
73
            continue
74
        if not isPrime(gift_e):
75
            continue
76
        e = pow(Egift, gift_e, n)
77
        if str(e).startswith(e_prefix):
78
            print(f"{e = }")
79
            break
80
res = ContinuedFraction(e, n)
81
for k, d in res.fractionlist:
82
    # 判断哪一个是我们所需的d
83
    if k < 20:
84
        continue
85
    elif (e * d - 1) % k == 0:
86
        break
87
m = pow(c, d, n)
88
print(long_to_bytes(m).decode())
89
# e = 2543227115950034359259431921883754022830582292637401733235553030107364098712291832536697560659257095503796373251636092489593903580286003571024803135820294126652369366117829278404230050461613381458005675777410020965908830867154128395524705917496214312199741087602226327069432869310599070868046223970919841169490420588910058122702285070986368342692724998833326184467966153744596198639879887813334912449669725862474145497854971275908053178144122420191018708749076313368778942124532153015306743156373566078442925099963498648299779952200871168436841913010888725601154109260208842197396130728533932791175590162330730746525
90
# flag{rsa_comb_v2_cube_root}

持续更新中~

Crypto#

CardSeed#

Drift#

LuckyRand#

AES-CBC 明文恢复#

Python getrandbits(128) 的字节顺序#

MT19937 状态恢复#

反推 X[1], X[2], X[3]#

关键一步：用 i = -1 恢复 X[0] 的低 31 bit#

RsaComb#