25Mar1-MTArchive

25年3月专题1 MT19937

0.Introduction

最近不知为何，发现MT19937出现地越来越多了，那就写一个Blog记录一下这些题目吧！

其实自己在Explort MT19937中，已经在2月更新了相关内容，就是在知道任意19968个bit时，可以构造 $19968\times19968$ 的矩阵，然后解线性方程组就OK了。当然，构造矩阵时，需要确保你的MT19937比特获取过程同步，也就是需要更改 getRows 函数中获取内容。这个代码是记录的 $1250$ 组 getrandbits(16) 的结果。（其实 $1248$ 组就OK了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
Dall=list(map(int,open('data3.txt','r').readlines()))
from Crypto.Util.number import *
from random import *
from tqdm import *
n=1250
D=Dall[:n]
rng=Random()
def getRows(rng):
    #这一部分根据题目实际编写，必须和题目实际比特获取顺序和方式完全一致，且确保比特数大于19937，并且请注意zfill。
    row=[]
    for i in range(n):
        row+=list(map(int, (bin(rng.getrandbits(16))[2:].zfill(16))))
    return row
M=[]
for i in tqdm_notebook(range(19968)):#这一部分为固定套路
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    rng.setstate((3,tuple(state+[624]),None)) #这个setstate也是固定格式，已于2025.1.21测试
    M.append(getRows(rng))
M=Matrix(GF(2),M)
y=[]
for i in range(n):
    y+=list(map(int, (bin(D[i])[2:].zfill(16))))
y=vector(GF(2),y)
s=M.solve_left(y)
#print(s)
G=[]
for i in range(624):
    C=0
    for j in range(32):
        C<<=1
        C|=int(s[32*i+j])
    G.append(C)
import random
RNG1 = random.Random()
for i in range(624):
    G[i]=int(G[i])
RNG1.setstate((int(3),tuple(G+[int(624)]),None))

print([RNG1.getrandbits(16) for _ in range(75)])
print(D[:75])

1.[TPCTF]RandomlizedRandom

先看看题目：

1
2
3
4
5
6
7
8
# FROM python:3
import random
with open("flag.txt","rb") as f:
    flag=f.read()
for i in range(2**64):
    print(random.getrandbits(32)+flag[random.getrandbits(32)%len(flag)])
    input()

交互次数很多，并且就是简单的 getrandbits(32)，很明显的MT特征。

但这边是 getrandbits(32)+flag[getrandbits(32)%len(flag)]，也就是说，这边 getrandbits(32) 的结果是带误差的，其误差就是flag的值。但由于flag每个字符不超过 $127$，因此可以认为得到的所有 $32$ 位数字中，其高 $8$ bit 是准确的。

我们可以先收集一波数据。这边为了保险，收集了 $10000$ 个。但其实用不了那么多。

1
2
3
4
5
6
7
8
from pwn import *
from tqdm import *
sh=remote('1.95.57.127',3001)
with open('datarecv002.txt','w') as f:
    for i in tqdm_notebook(range(10000)):
        x=int(sh.recvline(keepends=False))
        f.write(str(x)+'\n')
        sh.sendline(b'A')

接着构造矩阵，由于题目中给出的数字是先取一个，再丢一个的，因此我们这边也要按照题目的过程来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from random import *
n=4992
def getRows(rng):
    #这一部分根据题目实际编写，必须和题目实际比特获取顺序和方式完全一致，且确保比特数大于19937，并且请注意zfill。
    row=[]
    for i in range(n):
        row+=list(map(int, (bin(rng.getrandbits(32)>>24)[2:].zfill(8))))
        _=rng.getrandbits(32)
    return row
M=[]
for i in tqdm_notebook(range(19968)):#这一部分为固定套路
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    rng.setstate((3,tuple(state+[624]),None)) #这个setstate也是固定格式，已于2025.1.21测试
    M.append(getRows(rng))
M=Matrix(GF(2),M)
save(M,'matrix308')

构造矩阵后，就是处理数据然后设置state了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
D=open('datarecv001.txt','r').readlines()
for i in range(10000):
    D[i]=int(D[i])
n=4992
M=load('matrix308.sobj')
y=[]
for i in range(n):
    y+=list(map(int, (bin(D[i]>>24)[2:].zfill(8))))
y=vector(GF(2),y)
s=M.solve_left(y)
G=[]
for i in range(624):
    C=0
    for j in range(32):
        C<<=1
        C|=int(s[32*i+j])
    G.append(C)
import random
RNG1 = random.Random()
for i in range(624):
    G[i]=int(G[i])
RNG1.setstate((int(3),tuple(G+[int(624)]),None))

当然，这边还需要简单爆破一下flag的长度，最后发现是 $29$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
A=[]
B=[]
F=[]
for i in range(10000):
    a=RNG1.getrandbits(32)
    b=RNG1.getrandbits(32)
    f=D[i]-a
    A.append(a)
    B.append(b)
    F.append(f)
def check(L):
    arr=[0]*L
    for i in range(10000):
        cur=arr[B[i]%L]
        if(cur-F[i] and cur):
            return 0
        elif(not cur):
            arr[B[i]%L]=F[i]
    return 1
for i in range(23,99):
    if(check(i)):
        print(i)
def make(L):
    arr=[0]*L
    for i in range(10000):
            arr[B[i]%L]=F[i]
    return bytes(arr)
print(make(29))
#b'TPCTF{Ez_MTI9937_pr3d1cTi0n}\n'

2.[SUCTF2025]SUPoly

题目看着很简单，并且鸡块Blog中也已经有了WP，这边复现一下！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from hashlib import md5
from secret import flag
import signal

PR.<x> = PolynomialRing(Zmod(0xfffffffffffffffffffffffffffffffe))
SUPOLY = PR.random_element(10)
gift = []
for i in range(bytes_to_long(b"SU")):
    f = PR.random_element(10)
    gift.append([int((f*SUPOLY)(j)) & 0xff for j in range(10)])
print("🎁 :", gift)

signal.alarm(10)
if(md5(str(SUPOLY.list()).encode()).hexdigest() == input("Show me :)")):
    print("🚩 :", flag)
else:
    print("🏳️ :", "flag")

这个题在获取Flag后时间只有10秒，提供了 $21333$ 组数据。多项式使用的模数为 $2^{128}-2$。

这边解题的漏洞就是：Sagemath中，random_element 函数是通过 randrange() 获取的，这基本等价于getrandbits()取模，这就会导致在模 $2^{32k}-1$ 下，其生成的数值与MT19937中 getrandbits(32*k) 生成的数值一致，虽然在这个过程中可能会加上模数，但这边模数为 $2^{128}-2$，产生取模的概率可以忽略不计。因此也就是说，多项式 $s$ 和 $f$ 的所有系数均可以看作 MT19937 生成的原始数据。

题目最终会给出 $f_i\times s$ 取 $0\sim9$ 的函数值。不过考虑到数据组数为 $21333$，并且 $f\times s$ 会导致常数项产生变化。但题目中的模数取的是 $2^{128}-2$，就是因为模 $2$ 之后，$(f_is(0))$ 的最后一比特是会暴露的。因此我们就只需要考察 $(f_is)(0)$ 对 $2$ 取模的结果就OK。如果 $s$ 的常数项是奇数，那么就可能暴露 $f_i$ 的常数项的最低比特。$21333>19937$，所以数据是足够的了。

不过由于题目只有10秒时间，我们就需要预先构造矩阵，然后再考虑求逆。

这边需要一个小细节：构造的时候，最好使用np.array构造，因为我们这边所有的数字都是 $(0,1)$，所以uint8 就够了，这样一个值只占 $1$ 字节。否则一个值要占 $28$ 字节。(但这么做还是没啥用，因为你造矩阵时，内存还是会炸，但至少不会给你炸到两倍内存。)

好家伙，要是CTF再出这种卡16G+内存的题的话，研二就换64G内存的电脑了。

$\mathsf{14min,16.6GB}$，但测了官方wp，其消耗为 $\mathsf{12min,8.8GB}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from random import *
from tqdm import*
import numpy as np
def getRows(rng):
    row=np.zeros(21333,dtype='uint8')
    rng.getrandbits(128*11)
    for i in range(21333):
        _a=rng.getrandbits(128*10)
        row[i]=(rng.getrandbits(128)&1)
    return row
M=[]
rng=Random()
for i in tqdm_notebook(range(19968)):#这一部分为固定套路，具体原因已经写在注释中了
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
    for j in range(624): 
        state[j] = int(temp[32*j:32*j+32],2)
    rng.setstate((3,tuple(state+[624]),None)) #这个setstate也是固定格式，已于2025.1.21测试
    M.append(getRows(rng))
M=Matrix(GF(2),M)
save(M,'mat111')
save(M[[0]+list(range(32,19968)),:19937]**-1,'Minv')

这边，M.rank() 为 $19937$，符合预期。但我们后面要对它进行逆向，因此我们要找一个方阵对其求逆。

经过测试，对于这个 $19968\times21333$ 的矩阵而言，取 $19968\times19937$ 的子矩阵，其rank仍然是 $19937$。但取前 $19937$ 行，其rank为 $19906$，取后 $19937$ 行，其 rank 为$19936$。因此最终取第一行和最后 $19936$ 行，才能够构成 $19937\times19937$ 的矩阵。

注意到之前解方程用的是 solve_left，因此可以在这边给他来个转置，然后再对这个子矩阵求逆，后面拿到数据后，就可以右乘向量了。

拿到 $M^{-1}$ 之后，就可以接收数据，解方程，构建状态了。注意到我们这边 $19968$ 个数值取的是 $0$ 和 $32\sim19967$，因此 $(M^{-1})^T\vec v$ 得到的第一个分量的下标为 $0$，第二个分量的下标为 $32$，因此中间还需要填充 $31$ 个 $0$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Minv=load('Minv.sobj').T
from pwn import *
from hashlib import md5
sh=remote('node6.anna.nssctf.cn',21966)
sh.recvuntil(b':')
D=eval(sh.recvline())
v=[D[i][0]&1 for i in range(21333)]

if(1 in v):
    v = vector(GF(2), v[:19937])
    v=Minv*v
    v=list(v)
    v=[v[0]]+[0]*31+v[1:]
    vstr = "".join(list(map(str, v)))
    state = []
    for i in range(624):
        state.append(int(vstr[32*i:32*i+32],2))
    RNG1 = random.Random()
    RNG1.setstate((3,tuple(state+[624]),None))
    s = [RNG1.getrandbits(128) for i in range(11)][::-1]
    sh.recvuntil(b"Show me :)")
    sh.sendline(str(md5(str(s).encode()).hexdigest()).encode())
    print(sh.recvall(timeout=7))
else:
    print('fail')
sh.close()
#b'\xf0\x9f\x9a\xa9 : NSSCTF{f614f081-ddec-4579-88e2-fdc29183bdc3}\n'

3.[CATCTF]Random_game

又是很短的题目：

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
from secret import flag
from random import *
gift = b"".join(long_to_bytes((pow(getrandbits(4), 2*i, 17) & 0xf) ^ getrandbits(8), 1) for i in range(4567))
m = list(flag)
for i in range(2024):
    shuffle(m)
print("gift =", bytes_to_long(gift))
print("c = '" +  "".join(list(map(chr,m))) + "'")

题目只给出了gift和c，并且这个上面出现了 getrandbits，那肯定还是要从 MT 去思考。

由于题目每次给出的内容是：
$$
r_4^{2i}\mod 17 \mod 16 \oplus r_8
$$
因此，$r_8$ 的高 $4$ 位是保持住了，那么我们就直接得到了 $4\times4567=18268$ 个内部状态，但貌似还不够。。。

不过我们可以发现这边的模数是 $17$，而 $a^{16}\equiv 1 \pmod {17}$，因为每 $8$ 轮，$r_8$ 异或的值就一定为 $1$，那么轮数（从 $0$ 计数）是 $8$ 的倍数的轮次，我们可以知道低 $4$ 位，这又是 $2284$ 个比特。那么我们就一共得到了 $20552$ 个状态了。

这似乎是一件很美妙的事情，结果。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import long_to_bytes
from random import *
D=long_to_bytes(gift)
y=[]
for i in range(4567):
    x=D[i]
    if(i%8==0):
        y+=list(map(int, (bin(x^^1)[2:].zfill(8))))
    else:
        y+=list(map(int, (bin(x>>4)[2:].zfill(4))))
y=vector(GF(2),y)
s=M.solve_left(y)
G=[]
for i in range(624):
    C=0
    for j in range(32):
        C<<=1
        C|=int(s[32*i+j])
    G.append(C)
RNG1 = Random()
for i in range(624):
    G[i]=int(G[i])
RNG1.setstate((int(3),tuple(G+[int(624)]),None))
#ValueError: matrix equation has no solutions

什么鬼？我都是按照流程来的，为啥没解？！！！

简单思考了一下发现：因为 getrandbits(4) 的结果可能是 $0$，$0^{16}\equiv 0\pmod {17}$，而我前面错误地将其认为是 $1$ 了，笑死。

那如果干脆把这一位丢掉呢？那就还知道 $3\times 571=19981$ 位，也算勉强够，那就把这位去了重新构造矩阵吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from tqdm import *
from random import *
def getRows(rng):
    row=[]
    for i in range(4567):
        x=rng.getrandbits(4)
        x=rng.getrandbits(8)
        if(i%8==0):
            row+=list(map(int, (bin(x>>1)[2:].zfill(7))))
        else:
            row+=list(map(int, (bin(x>>4)[2:].zfill(4))))
    return row
rng=Random()
M=[]
for i in tqdm_notebook(range(19968)):#这一部分为固定套路
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    rng.setstate((3,tuple(state+[624]),None)) #这个setstate也是固定格式，已于2025.1.21测试
    M.append(getRows(rng))
M=Matrix(GF(2),M)
save(M,'catrandom3')

得到新的矩阵后，然后重新走流程就OK了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
M=load('catrandom3.sobj')
gift=
c=
from Crypto.Util.number import long_to_bytes
from random import *
D=long_to_bytes(gift)
y=[]
for i in range(4567):
    x=D[i]
    if(i%8==0):
        y+=list(map(int, (bin(x>>1)[2:].zfill(7))))
    else:
        y+=list(map(int, (bin(x>>4)[2:].zfill(4))))
y=vector(GF(2),y)
s=M.solve_left(y)
G=[]
for i in range(624):
    C=0
    for j in range(32):
        C<<=1
        C|=int(s[32*i+j])
    G.append(C)
RNG1 = Random()
for i in range(624):
    G[i]=int(G[i])
RNG1.setstate((int(3),tuple(G+[int(624)]),None))
for i in range(4567):
    RNG1.getrandbits(4)
    RNG1.getrandbits(8)
x = [i for i in range(len(c))]
for i in range(2024):
    RNG1.shuffle(x)
s=[None]*len(c)
for i in range(len(c)):
    s[x[i]]=c[i]
print(''.join(s))
#catctf{_Shuf|fl3_s|hUFf1e_UnsHUff|L3_unsH|ufF1E_}

又回顾了一下wp，wp是利用了更多组数据：因为 $x^8\equiv ±1\pmod {17}$，因此当轮数是 $4$ 的倍数时，这一轮我们可以知道 $7$ 个位！所以最后我们实际能知道的位数是还能够更多。

4.[N1CTF_junior]BabyAES

还是看看题先：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Cipher import AES
from random import randbytes
import os


pad = lambda x: x+randbytes(16-len(x)%16)
cipher = AES.new(os.urandom(16), AES.MODE_CBC, iv=randbytes(16))

for ROUND in range(128):
    msg = pad(bytes.fromhex(input("msg: ")))
    cts = [cipher.encrypt(msg), randbytes(len(msg))]
    decision = os.urandom(1)[0]&1
    print("ct:", cts[decision].hex())
    assert input("[+] ") == str(decision)
from uuid import uuid4
FLAG = "flag{"+str(uuid4())+"}"
print(f"Congrats! 🚩 {FLAG}")

代码仍然很短。题目要求你连续 $128$ 轮猜测，每次输入一个明文 $m$，问你输出结果是 $m$ 对应的密文还是随机字符串。

测了一下这边的 randbytes，看来和 getrandbits 的结果是一样的。不过关注顺序可以发现 randbytes 得到的字符串的数据是倒着来的。 而 os.urandom 不会影响 randbytes 的生成顺序（因为不是random包中的内容）。

1

有了这个信息后，我们就可以进行解题了：注意到题目中的这句话：

1
cts = [cipher.encrypt(msg), randbytes(len(msg))]

因此我们第一次可以发一个很长很长的字符串，然后猜 $1$ ，这个有一半的概率成功。如果这成功了，那么我们就得到了非常多的state。

那这个字符串发多长呢？因为一个 bytes 是 8 位，也就是 getrandbits(32) 的四分之一。使用 getrandbits(32) 需要 $624$ 个 state。那么这边就是 $2496$ 个字节长度。但需要注意的是，题目中会有一个pad成 $16$ 的倍数的长度，这会影响输出结果，因此也需要考虑进去。因此我们可以发送 $2480$ 字节，加上 $16$ 字节填充，那最后就是 $2496$ 字节了。

如果上一个步骤成功了。考虑到 MT19937 输出比特数最好为 32 的倍数，因此后面 $127$ 轮我们可以一次发送 $4$ 字节，然后服务器会用 randbytes 填充 $12$ 字节凑够 $16$ 字节，这也刚好是 $4$ 个 32bit-state 的状态。当然，如果我们一次发 $4$ 字节，cts=[cipher.encrypt(msg), randbytes(len(msg))] 还会调用一次randbytes，因此我们还要再计算 $16$ 字节，也就是 $4$ 个状态的值。

最终本地测试代码如下，这边 mttools 还是我之前在 Explore MT19937 中第二章最后写的模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from pwn import *
from random import *
from mttools import *
sh=process(['python3','localtest.py'])
sh.recvuntil(b'msg:')
sh.sendline(b'00'*2480)
sh.recvuntil(b'ct:')
recv=sh.recvline(keepends=False).strip()
print(recv)
print(len(recv)//2)
sh.sendline(b'1')
F=MT19937()
D=[]
for i in range(624):
	di=recv[i*8:i*8+8]
	di=(int(di[6:8],16)<<24)+(int(di[4:6],16)<<16)+(int(di[2:4],16)<<8)+(int(di[0:2],16))
	D.append(di)
F.setstate(D)
from tqdm import *
for T in tqdm(range(127)):
	sh.recvuntil(b'msg:')
	sh.sendline(b'00'*4)
	test=[F.getstate()for i in range(7)][3:]
	#print(test)
	sh.recvuntil(b'ct:')
	D=[]
	recv=sh.recvline(keepends=False).strip()
	for i in range(4):
		di=recv[i*8:i*8+8]
		di=(int(di[6:8],16)<<24)+(int(di[4:6],16)<<16)+(int(di[2:4],16)<<8)+(int(di[0:2],16))
		D.append(di)
	#print(D)
	if(D==test):
		sh.sendline(b'1')
	else:
		sh.sendline(b'0')
print(sh.recvall(timeout=6))
#b'[+] Congrats! \xf0\x9f\x9a\xa9 flag{71e3453c-5edb-4ef2-bb51-6c9a5f3b782b}\n'

当然据说maple3142大佬在github上给出了[板子](maple3142/gf2bv: Solving linear systems over GF(2) by manipulating bitvectors (github.com))。这个小工具可以预测连续的 getrandbits(X) ，不过需要安装一些依赖库。好在这玩意可以在 2GB 的服务器上流畅运行（占用内存仅 $\mathsf{250MB}$），不用构造矩阵。但不知为何，貌似很多时候预测会有无解的情况（实际有解），因此最好让他多运行几次。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import random, time
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from time import perf_counter
from contextlib import contextmanager
from pwn import *
def RUN():
    try:
        sh=process(['python3','localtest.py'])
        sh.recvuntil(b'msg:')
        sh.sendline(b'00'*2480)
        sh.recvuntil(b'ct:')
        recv=sh.recvline(keepends=False).strip()
        #sh.recvuntil(b'] ')
        sh.sendline(b'1')
        def mt19937(bs, out):
            print(out)
            lin = LinearSystem([32] * 624)
            mt = lin.gens()
            rng = MT19937(mt)
            zeros = [rng.getrandbits(bs) ^ int(o) for o in out] + [mt[0] ^ int(0x80000000)]
            sol = lin.solve_one(zeros)
            #print(sol)
            rng = MT19937(sol)
            pyrand = rng.to_python_random()
            return pyrand
        D=[]
        for i in range(624):
        	di=recv[i*8:i*8+8]
        	di=(int(di[6:8],16)<<24)+(int(di[4:6],16)<<16)+(int(di[2:4],16)<<8)+(int(di[0:2],16))
        	D.append(di)
        rng10=mt19937(32,D[:])
        
        for i in range(624):
            assert (rng10.getrandbits(32)==D[i])
        print('assert pass')
        
        for T in range(127):
            sh.recvuntil(b'msg:')
            sh.sendline(b'00'*4)
            test=[rng10.getrandbits(32) for _ in range(7)][3:]
            sh.recvuntil(b'ct:')
            D=[]
            recv=sh.recvline(keepends=False).strip()
            for i in range(4):
                di=recv[i*8:i*8+8]
                di=(int(di[6:8],16)<<24)+(int(di[4:6],16)<<16)+(int(di[2:4],16)<<8)+(int(di[0:2],16))
                D.append(di)
            print(f'{T=}')
            print(f'{D=}')
            print(f'{test=}')
            if(D==test):
                sh.sendline(b'1')
            else:
                sh.sendline(b'0')
        print(sh.recvall(timeout=6))
        return 1
    except:
        sh.close()
        return 0
while not(RUN()):
    pass
#b'[+] Congrats! \xf0\x9f\x9a\xa9 flag{ad75507a-c187-4675-8498-f465d5532b7d}\n'

当然这边还有一些其他的工具：比如ExtendMT19937Predictor（功能更多，可预测randint,randrange，但state只能设置成 $32$ 比特的倍数）和MT19937Predictor-master（可以预测 getrandbits(X)，$X$ 为任意值，其原理也是构造矩阵）。。

5.[NSSr3] MT

这是两个题目，一起看！

5x01 MT-N

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from secret import flag
from random import *

def N(k):
    return getrandbits(1) & 0 if k == 0 else getrandbits(k)

gift = []
for i in range(100000):
    gift.append(N(N(N(1))))

key = getrandbits(500)
c = bytes_to_long(flag)^key

with open("output.txt", "w") as f:
    f.write(f"gift = {gift}\n")
    f.write(f"c = {long_to_bytes(c)}")

题目给出了 $100,000$ 组 N(N(N(1))) 的结果，而函数 $N$ 就是调用一次 getrandbits(1) 。由于 $N$ 时三层嵌套，而只要有一层的结果为 $0$，则最终的结果为 $0$，只有三次 getrandbits(1) 都是 $1$，最终结果才会返回 $1$。

测试一下，发现 $1$ 的个数确实接近 $1/8$ 总数。

1
2
sum(gift)
#12602

那么就按套路上exp（$\mathsf{9min,5.9GB}$）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
gift=
c=
import random
from tqdm import *
n=100000
def getRows(rng):
    #这一部分根据题目实际编写，必须和题目实际比特获取顺序和方式完全一致，且确保比特数大于19937，并且请注意zfill。
    row=[]
    s=0
    for i in range(n):
        a1=rng.getrandbits(1)
        a2=rng.getrandbits(1)
        a3=rng.getrandbits(1)
        if(gift[i]):
            s+=1
            row+=list(map(int, (bin(a1)[2:].zfill(1))))
            row+=list(map(int, (bin(a2)[2:].zfill(1))))
            row+=list(map(int, (bin(a3)[2:].zfill(1))))
        if(s>=7000):
            break
    return row
M=[]
rng=random.Random()
for i in tqdm_notebook(range(19968)):#这一部分为固定套路
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    rng.setstate((3,tuple(state+[624]),None)) #这个setstate也是固定格式，已于2025.1.21测试
    M.append(getRows(rng))
M=Matrix(GF(2),M)
y=[]
tot=0
for i in range(n):
    if(gift[i]):
        y+=[1,1,1]
        tot+=1
    if(tot>=7000):
        break
y=vector(GF(2),y)
s=M.solve_left(y)
#print(s)
G=[]
for i in range(624):
    C=0
    for j in range(32):
        C<<=1
        C|=int(s[32*i+j])
    G.append(C)
import random
RNG1 = random.Random()
for i in range(624):
    G[i]=int(G[i])
RNG1.setstate((int(3),tuple(G+[int(624)]),None))
from Crypto.Util.number import *
for i in range(300000):
    RNG1.getrandbits(1)
K=RNG1.getrandbits(500)
C=bytes_to_long(c)
print(long_to_bytes(C^^K))

5x02 MT-SS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from secret import flag
from random import *

def SS(k):
    return getrandbits(1) & 0 if k == 0 else getrandbits(k)

gift = []
for i in range(50000):
    gift.append(SS(SS(5)))

key = getrandbits(500)
c = bytes_to_long(flag)^key

with open("output.txt", "w") as f:
    f.write(f"gift = {gift}\n")
    f.write(f"c = {long_to_bytes(c)}")
#NSSCTF{1st_year_2nd_year_And_now_is_3rd_not_4th_Do_U_know_why?}

很显然这个 SS 就是上个题的 N。但这边是两次嵌套 SS，第一次调用得到 getrandbits(5)，这是一个 $0\sim31$ 的数字。第二次调用 getrandbits() 相当于取的位数为随机值。。

需要注意的是： getrandbits() 产生的是 $0\sim2^x-1$ 的值，也就是如果某个 getrandbits() 返回了一个 $n$ bit 的数，我们只知道参数值一定大于等于 $n$，但具体值我们却不知道。由于这边 getrandbits() 的参数均不超过 $32$，因此每次调用只消耗一个内部的 $32$ 位 state。

虽然我们不清楚每一轮外侧 getrandbits() 的参数，但该参数一定在 $0\sim 31$ 中。因此看到 $31$ 比特的数值，就说明参数是 $31$，这样我们就可以一次得到 $5+31=36$ 个准确的比特。测了一下，应该够用。

1
2
3
4
5
6
s=0
for i in range(len(gift)):
    s+=(gift[i]>=0x40000000)
s
#794
#794*36=28584

然后就是用上面的套路解题了。。。 （$\mathsf{9min,9GB}$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
gift=
c=
import random
from tqdm import *
n=50000
def getRows(rng):
    #这一部分根据题目实际编写，必须和题目实际比特获取顺序和方式完全一致，且确保比特数大于19937，并且请注意zfill。
    row=[]
    for i in range(n):
        a=rng.getrandbits(5)
        b=rng.getrandbits(31)
        if(gift[i]&0x40000000):
            row+=list(map(int, (bin(31)[2:].zfill(5))))
            row+=list(map(int, (bin(b)[2:].zfill(31))))
    return row
M=[]
rng=random.Random()
for i in tqdm_notebook(range(19968)):#这一部分为固定套路
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    rng.setstate((3,tuple(state+[624]),None)) #这个setstate也是固定格式，已于2025.1.21测试
    M.append(getRows(rng))
M=Matrix(GF(2),M)
y=[]
tot=0
for i in range(n):
    if(gift[i]&0x40000000):
        y+=list(map(int, (bin(31)[2:].zfill(5))))
        y+=list(map(int, (bin(gift[i])[2:].zfill(31))))
        tot+=1
y=vector(GF(2),y)
s=M.solve_left(y)
#print(s)
G=[]
for i in range(624):
    C=0
    for j in range(32):
        C<<=1
        C|=int(s[32*i+j])
    G.append(C)
import random
RNG1 = random.Random()
for i in range(624):
    G[i]=int(G[i])
RNG1.setstate((int(3),tuple(G+[int(624)]),None))
from Crypto.Util.number import *
for i in range(50000):
    RNG1.getrandbits(5)
    RNG1.getrandbits(31)
K=RNG1.getrandbits(500)
C=bytes_to_long(c)
print(long_to_bytes(C^^K))
#b'NSSCTF{Bec4us3_0f_LinearXD!!}'

6.[强网拟态2024]notiv

瞄一眼题目（注：题目非核心部分与原题略有改动，比如取消了proof_of_work，并改了一下flag的形式，但不影响题目原本难度和解题做法）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
# !/usr/bin/env python
from hashlib import sha256
import socketserver
import os
import sys
import random
import signal
import string
from hashlib import sha256
from mypad import *
from datetime import *
from Crypto.Cipher import AES
from random import *
from Crypto.Util.number import *


class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def close(self):
        self.request.close()

    def handle(self):
        try:
            signal.alarm(120)
            count = 0
            for _ in range(50):
                seed(os.urandom(8))
                key = pad_x923(b"")
                print(key.hex())
                chal = hex(getrandbits(64*3))[2:].zfill(16*3)
                print(str(datetime.now()),chal)
                for i in range(200):
                    iv = long_to_bytes(getrandbits(128)).rjust(16, b"\00")
                    cipher = AES.new(key, AES.MODE_CBC, iv)
                    test = self.recv(b":> ").decode()
                    tb = bytes.fromhex(test)
                    ret = cipher.encrypt(pad_x923(tb))
                    if len(ret) > 16:
                        self.send(b"forbid")
                        continue
                    self.send((iv+ret).hex().encode())

                s = self.recv(b">> ").decode()
                print('s=',s)
                iv = bytes.fromhex(s[:32])
                print('iv=',iv)
                ans = bytes.fromhex(s[32:])
                print('ans=',ans)
                cipher = AES.new(key, AES.MODE_CBC, iv)
                att = cipher.decrypt(ans)
                print('attpad=',att)
                att = unpad_x923(att)
                print('att=',att,'chalEncode=',chal.encode())
                if att == chal.encode():
                    count += 1
            self.send(b"you got %d score" % count)
            if count >= 20:
                FLAG="flag{Success at "+str(datetime.now())+"}"
                FLAG=FLAG.replace(' ','-')
                self.send(b"cong!your flag is "+FLAG.encode())
            else:
                self.send(b"sorry,plz try again")
        except:
            self.send(b"something wrong! plz try again!")
            self.close()


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '127.0.0.1', 60717
    print(f'running on {HOST}:{PORT}')
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

其中：

1
2
3
4
5
from Crypto.Random import get_random_bytes

pad_x923=lambda x,block_size=16:x+get_random_bytes((block_size-(len(x)%block_size)-1))+bytes([(block_size-len(x)%block_size)])
unpad_x923=lambda x,block_size=16:x[:-((x[-1]-1)%block_size)-1]

注：get_random_bytyes 调用的是 os.urandom，不可预测。

题目拿到第一眼：getrandbits(128)，这妥妥的MT随机数预测，200次机会，说明156次就可以预测后面的随机数了。然后发现，题目要求是构造一个给定的 48 字节的串的密文（这个可以求出来，因为这个串是 getrandbits(64*3) 生成的，前向反推一次就行）。

但在题目中，每次只能对至多 15 字节内容进行加密，且加密填充方式为：填充 $n-1$ 个随机字符，然后再放入 1 字节填充长度来保证分组。当明文长度为 48 时，意味着密文长度为 64（因为要填充一整组）。且题目使用了 CBC 模式，也就是前一组密文和后一组明文异或后才是真正的加密内容，即：$IV=C_0$，$C_i=E(C_{i-1}\oplus M_i),i=1,2,3,4$。

经过分析后，我们可以大致地得到这些事实：

  1. 由于填充的随机性，因此，必须构造 15 字节的密文，这样才能保证 填充后字符串的确定性（只会填充一个\x01）
  2. 使用的IV是可以预测的，可以从这个地方出发考虑。
  3. 构造密文时，IV是可指定的，因此 $C_1$ 可以直接构造。同时，对 $C_4$ 的要求是：保证最后四个比特为 $0$ 就行，对应 $1/16$ 的概率。
  4. 因此本题重点是主要考虑 $C_2$ 和 $C_3$，且要保证能达到约 40 percent 的构造成功率。

设 $\mathrm{chal}=H_1,H_2,H_3,H_4$，其中可以假设 $H_4$ 为全零（根据第三条后半部分）。考虑直接构造：由于 $C_2=E_K(H_2\oplus C_1)$。而在之前选择明文的过程中：$C_2=E_K(M_2\oplus IV_2)$，因此，我们构造出来的 $M_2$ 应该为 $M_2=IV_2\oplus C_1\oplus H_2$。因此我们需要保证 $M_2$ 的最后一字节的十六进制为 $\mathtt{01H}$，这个概率为 $1/256$。

而同理，$M_3$ 也是 $1/256$ 的概率构造。那这样成功率算下来就是 $1/65536$，故期望得分为：
$$
E(\mathrm{Point})=\frac{50\times200}{65536}=0.1526
$$
也就是平均尝试六次，才只能得 $1$ 分。

借鉴的MaPl大哥的EXP，其中，mttool见本人博客中2021年7月的Explore MT19937文章。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
from pwn import *
from tqdm import *
from mttool import *

# 记录所有AES加解密对
AES_P, AES_C = [], []

def turn(sh, data: bytes):
	assert len(data) == 15
	sh.recvuntil(b':> ')
	sh.sendline(data.hex().encode())
	ret = sh.recvline().decode().strip()
	iv = bytes.fromhex(ret[:32])
	ciph = bytes.fromhex(ret[32:])
	AES_P.append(xor(data + b"\1", iv))
	AES_C.append(ciph)
	return iv, ciph

def getrandbits(F, bits):
	assert bits % 8 == 0
	state = [F.getstate() for _ in range(bits//32)][::-1]
	return b"".join(w.to_bytes(4, "big") for w in state)

def skip_state(F, state_count):
	for _ in range(state_count):
		F.getstate()

def xor(a, b):
    return bytes(a[i] ^ b[i] for i in range(min(len(a), len(b))))

sh = remote('127.0.0.1', 60717)

for i in range(50):
	AES_P, AES_C = [], []
	# 恢复随机数状态
	D = []
	F = MT19937()
	for _ in range(624//4):
		my_plain = b"0"*15 + b"\x01"
		iv, ciph = turn(sh, my_plain[:15])
		for j in [12, 8, 4, 0]:
			D.append(int.from_bytes(iv[j:j+4], 'big'))
	F.setstate(D)
	F.invtwist()
	F.invtwist()

	# 得到 chal
	skip_state(F, 624-6)
	chal = getrandbits(F, 24*8).hex().encode()
	print(f"chal: {chal}")
	P1 = chal[:16]
	P2 = chal[16:32]
	P3 = chal[32:]

	# 将随机数置为当前状态
	skip_state(F, 624)

	# 搜索加解密对，构造C2
	times = 200 - 624//4
	solve = []
	next_iv = getrandbits(F, 128)
	
	while times > 2:
		for P, C in zip(AES_P, AES_C):
			if (C[-1] ^ P2[-1] ^ next_iv[-1]) == 1:
				payload = xor(P2, next_iv)
				payload = xor(C, payload)
				assert payload[-1] == 1
				iv, ciph = turn(sh, payload[:15])
				assert iv == next_iv
				next_iv = getrandbits(F, 128)
				IV, C1, C2 = xor(P, P1), C, ciph
				if (C2[-1] ^ P3[-1] ^ next_iv[-1]) == 1: # 从已有结果构造 C3 (低概率)
					payload = xor(P3, next_iv)
					payload = xor(C2, payload)
					iv, ciph = turn(sh, payload[:15])
					assert iv == next_iv
					next_iv = getrandbits(F, 128)
					times -= 1
					C3 = ciph
					for P, C in zip(AES_P, AES_C): # 筛选出最后一组填充
						if (P[-1] ^ C3[-1]) % 16 == 0 and (C[-1] ^ next_iv[-1]) == 1:
							C4 = Cs
							print(f"[+] get solve:")
							print(f"\tIV: {IV.hex()}")
							print(f"\tC1: {C1.hex()}")
							print(f"\tC2: {C2.hex()}")
							print(f"\tC3: {C3.hex()}")
							print(f"\tC4: {C4.hex()}")
							solve.append((IV, C1, C2, C3, C4))
				break
		else:
			turn(sh, b"0"*15)
			next_iv = getrandbits(F, 128)
		times -= 1

	# context.log_level = "debug" 
	while times:
		turn(sh, b"0"*15)
		times -= 1

	sh.recvuntil(b'>> ')
	if solve:
		sh.sendline(b"".join(solve[0]).hex().encode())
	else:
		sh.send(b"00"*32)
print(sh.readline())

因为这个算法只求一个 $C_2$，然后对这个 $C_2$ 根据当前的IV去求 $C_3$，这样来的话概率当然会很低了。看了wp之后发现， wp的思路是存储所有满足条件的 $C_2$ 及其对应的 $C_1,IV$，然后对每个 $C_2$ 去用当前IV猜 $C_3$。由于一开始 $C_2$ 的数量少，因此如果没有找到合适的 $C_3$，则再获取一组可行的 $C_2$ 。

测了一下，一次运行大概可以获取 $19$ 个 $C_2$，尝试次数为 $19\times9=171$ 次。获取可行的 $C_3$ 的概率为 $1/256$，因此当获得 $19$ 个可行的 $C_2$ 后，就有很大的概率获取一个 $C_3$。

至于当前IV？IV是在获取 $156$ 组数据之后就可以预测出来，因此可以先进行测试，如果没有 $C_2$ 或者根据当前的 $C_2$ 找不到可行的 $C_3$，就可以再找一组 $C_2$。再本地进行枚举，找不到合适的就不交，不会浪费查询次数。

至于 $C_4$ ，可以认为 $H_4$ 为全 $0$，因此 $C_4$ 可以根据 $C_3$ 构造出来，概率为 $1/16$。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
from pwn import *
from tqdm import *
from Crypto.Util.number import *
from mttool import *

sh=remote('127.0.0.1',60717)
def sendMyMsg(msg):
	msghex=msg.hex()
	print(len(msghex),msghex)
	sh.recvuntil(b':> ')
	sh.sendline(msghex.encode())
	recvline=sh.recvline(keepends=False)
	recvline=recvline.strip()
	print(recvline)
	assert(len(recvline)==64)
	iv,ciph=recvline[:32],recvline[32:]
	iv,ciph=int(iv,16),int(ciph,16)
	plain=iv^ciph
	state4=[]
	iv00=iv
	for i in range(4):
		state4.append(iv&0xffffffff)
		iv>>=32
	return plain,ciph,state4,iv00
from tqdm import *
for o in tqdm(range(50)):
	V,M,C,D=[],[],[],[]#IV,realencmsg,cipher,32bitdata(iv)
	for i in range(156): #获取156组数据，624个state预测后续数值
		recvline=sendMyMsg(bytes([0]*15))
		M.append(recvline[0])
		C.append(recvline[1])
		D=D+recvline[2]
		V.append(recvline[3])
	F=MT19937()
	F.setstate(D)
	F.invtwist()
	F.invtwist()
	Ha=[F.getstate() for _ in range(624)]
	Ha=Ha[-6:]
	H=sum([Ha[i]<<(32*i) for i in range(6)]) #获取chal
	H=(hex(H)[2:].zfill(48))
	print(H)
	H1,H2,H3=[bytes_to_long(H[16*i:16*i+16].encode()) for i in range(3)]
	F.setstate(D)
	Fv=[sum([F.getstate()<<(32*_) for _ in range(4)]) for __ in range(44)] #获取后续IV
	V=V+Fv
	assert len(V)==200
	C0,C1,C2,C3,C4=0,0,0,0,0 #C0就是IV
	possC2=[]
	possC1ind=[]
	T=156
	while(T<200):
		print(possC2)
		ivT=V[T]
		foundC3=0
		for i in range(len(possC2)):#根据已有的 C2 去找 C3,如果找到了，就结束这一部分了
			X=ivT^possC2[i]^H3
			if(X%256==1): #只有构造出来的X满足末字节是01才可以
				msgX=(hex(X)[2:]).zfill(32)
				msgX=(hex(X)[2:]).zfill(32)
				msgX=bytes.fromhex(msgX) #如果明文X符合条件，就找发过去，获取这组C3并准备结束
				print(msgX)
				print('C3')
				recvline=sendMyMsg(msgX[:-1])
				T+=1
				C3=recvline[1]
				C2=possC2[i]
				C1=C[possC1ind[i]]
				C0=V[possC1ind[i]]^H1^1
				foundC3=1
				break
		if(foundC3): #找到C3立刻退出这个循环
			break
        #如果没有找到C3，那就寻找对应的 C2
		foundC2=0
		for i in range(len(C)):
			X=ivT^C[i]^H2 #通过所有的C[i]，构造可能的C2，这边的C[i]会被用作C1，因为C1构造很简单。
			if(X%256==1):
				msgX=(hex(X)[2:]).zfill(32)
				msgX=bytes.fromhex(msgX)
				print(msgX)
				recvline=sendMyMsg(msgX[:-1]) #如果明文X符合条件，就找发过去，获取这组C2
				T+=1
				possC2.append(recvline[1])
				C.append(recvline[1])
				possC1ind.append(i)
				foundC2=1
				break
		if(foundC2): #找到C2就看下一组数据
			continue
		else:
			recvline=sendMyMsg(bytes([0]*15)) #找不到C2，就再发一组00000...001过去凑数
			T+=1
			M.append(recvline[0])
			C.append(recvline[1])
	if(C0*C1*C2*C3):#如果C0,C1,C2,C3都找到了，就通过H4(H4=0) 去构造C4
		while(T<200):
			X=V[T]^C3^0 #这个异或H4=0可以不写，但为了明显起见，还是写出来
			if(X%16==1):
				X^=(X&0xf0)
				msgX='{:032X}'.format(X)
				msgX=bytes.fromhex(msgX)
				assert len(msgX)==16
				recvline=sendMyMsg(msgX[:-1])
				C4=recvline[1]
				T+=1
				break
			else:
				T+=1
				recvline=sendMyMsg(msgX[:-1])
				M.append(recvline[0])
				C.append(recvline[1])
		while(T<200):
			T+=1
			recvline=sendMyMsg(msgX[:-1])
			M.append(recvline[0])
			C.append(recvline[1])
		s=''
		for i in [C0,C1,C2,C3,C4]:
			s+='{:032X}'.format(i)
		print(s)
		sh.sendline(s.encode())
	else:#如果没有找到符合条件的数据，也要把次数用完，然后发一组全0跳掉这组数据。
		while(T<200):
			T+=1
			recvline=sendMyMsg(msgX[:-1])
			M.append(recvline[0])
			C.append(recvline[1])
		sh.sendline(bytes([48]*96))
sh.interactive()

运行结果，最后运行时间为 $41$ 秒，符合题目两分钟的限时。

4

7.[强网杯2024]ECRandom_Game

7x01 题目代码

既然看了这么多了，那就来个大的！这题目可真TM长。。。当时直接放弃了。。。结果现在回来看，因为刷了CryptoHack和系统地重新整理了一下MT的知识，当然更重要地是有了WP，感觉。好像也就那样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
from flag import M, q, a, b, select
import hashlib
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Cipher import AES
import sys
import ecdsa
from Crypto.Util.Padding import pad, unpad
from ecdsa.ellipticcurve import CurveFp,Point
from math import ceil
import os
import random
import string

flag = b'qwb{kLeMjJw_HBPtoHsVhnnxZdvtGjomivNDUI_vMRhZHrfKlCZ6HlGAeXRV_gQ8i117nGhzEMr0Zk_YTl1wftSskpX4JLnryE9Mhl96cPTWorGCl_R6nD33bcx1AYflag_leak}'
assert len(flag) == 136

BANNER = '''
 GGGGG   OOOOO   DDDDD   DDDDD    GGGGG    AAA    MM    MM EEEEEEE 
GG      OO   OO  DD   D  DD   D  GG       AAAAA   MMM  MMM EE      
GG  GGG OO   OO  DD   D  DD   D  GG  GGG  A   A   MM MM MM EEEEE   
GG   GG OO   OO  DD   D  DD   D  GG   GG  AAAAA   MM    MM EE      
GGGGGGG  OOOOO   DDDDD   DDDDD   GGGGGGG  A   A   MM    MM EEEEEEE 
 '''

NNN = []
def die(*args):
    pr(*args)
    quit()

def pr(*args):
    s = " ".join(map(str, args))
    sys.stdout.write(s + "\n")
    sys.stdout.flush()

def sc():
    return sys.stdin.buffer.readline()

def Rng(k):
    ran = random.getrandbits(k)
    NNN.append(ran)
    return ran


def ADD(num):
    NUM = 0
    for i in range(num):
        NUM += Rng(32)
    return NUM

def secure_choice(sequence):
    if not sequence:
        return None
    randbelow = 0
    for i, x in enumerate(sequence):
        randbelow += 1
        if os.urandom(1)[0] < (1 << 8) * randbelow // len(sequence):
            return x

def xDBLADD(P, Q, PQ, q, a, b):
    (X1, Z1), (X2, Z2), (X3, Z3) = PQ, P, Q
    X4 = (X2**2 - a * Z2**2) ** 2 - 8 * b * X2 * Z2**3
    Z4 = 4 * (X2 * Z2 * (X2**2 + a * Z2**2) + b * Z2**4)
    X5 = Z1 * ((X2 * X3 - a * Z2 * Z3) ** 2 - 4 * b * Z2 * Z3 * (X2 * Z3 + X3 * Z2))
    Z5 = X1 * (X2 * Z3 - X3 * Z2) ** 2
    X4, Z4, X5, Z5 = (c % q for c in (X4, Z4, X5, Z5))
    return (X4, Z4), (X5, Z5)

def xMUL(P, k, q, a, b):
    Q, R = (1, 0), P
    for i in reversed(range(k.bit_length() + 1)):
        if k >> i & 1:
            R, Q = Q, R
        Q, R = xDBLADD(Q, R, P, q, a, b)
        if k >> i & 1:
            R, Q = Q, R
    return Q

def shout(x, d, q, a, b):
    P = (x,1)
    Q = xMUL(P, d, q, a, b)
    return Q[0] * pow(Q[1], -1, q) % q

def generate_random_string(length):
    characters = string.ascii_letters + string.digits
    random_string = ''.join(secure_choice(characters) for i in range(length))
    return random_string

class ECCDu():
    def __init__(self,curve,G):
        self.state = getRandomNBitInteger(512)
        self.Curve = curve
        self.g = G

        self.num = Rng(32)
        d = 65537
        self.Q = self.num*self.g
        self.P = d * self.Q

    def ingetkey(self):
        t = int((self.state * self.Q).x())
        self.updade()
        return t%(2**250)

    def updade(self):
        self.state = int((self.state * self.P).x())

    def Random_key(self, n:int):
        out = 0
        number = ceil(n/250)
        for i in range(number):
            out = (out<<250) + self.ingetkey()
        return out % (2**n)

def proof_of_work():
    random.seed(os.urandom(8))
    proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
    _hexdigest = sha256(proof.encode()).hexdigest()
    pr(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
    pr('Give me XXXX: ')
    x = sc().rstrip(b'\n')
    if len(x) != 4 or sha256(x + proof[4:].encode()).hexdigest() != _hexdigest:
        return False
    return True


def main():
    pr(BANNER)
    pr('WELCOME TO THIS SIMPLE GAME!!!')
    ASSERT = 1#( proof_of_work() ) #Simplified for local test.
    if not ASSERT:
        die("Not right proof of work")

    pr('Now we will start our formal GAME!!!')
    pr('===== First 1💪: =====')
    pr('Enter an integer as the parameter p for Curve: y^2 = x^3+12x+17 (mod p) and 250<p.bit_length()')
    p1 = int(sc())
    if not 250<=p1.bit_length():
        die('Wrong length!')
    curve = CurveFp(p1, 12, 17,1)
    pr(curve)
    pr('Please Enter a random_point G:')
    G_t = sc().split(b' ')
    Gx,Gy = int(G_t[0]),int(G_t[1])
    if not curve.contains_point(Gx,Gy):
        die('This point is outside the curve')
    G = Point(curve,Gx,Gy)

    for i in range(500):
        ECDU = ECCDu(curve,G)
        m  = 'My secret is a random saying of phrase,As below :' + generate_random_string(119)
        Number = ECDU.Random_key(1344)
        c = Number^bytes_to_long(m.encode())
        pr(f'c = {c}')
        pr(f'P = {int(ECDU.P.x()), int(ECDU.P.y())}')
        pr(f'Q = {int(ECDU.Q.x()), int(ECDU.Q.y())}')

        pr('Enter m:')
        m_en = sc().rstrip(b'\n')
        if m_en != m.encode():
            die('This is not the right m,Please try again')
        else:
            pr('Right m!!!')
    pr('Bingo!')
    new_state,new_state1 = ADD(136),ADD(50)
    
    random.seed(new_state)

    pr('===== Second 2💪: =====')
    curve1 = CurveFp(q,a,b,1)
    pr(f'{int(curve1.p()),int(curve1.a()),int(curve1.b())}')

    pr("Enter a number that does not exceed 1500")
    number = int(sc())

    pr(f'You only have {number} chances to try')
    success = 0
    for i in range(number):
        Gx = secure_choice(select)
        R = Rng(25)
        pr('Gx = ',Gx)
        pr('Px = ',shout(Gx, R, q, a, b))
        R_n = int(sc().rstrip(b'\n'))
        if R_n != R:
            pr(f'Wrong number!!!,Here is your right number {R}')
        else:
            pr('GGood!')
            success += 1

    if int(success)/int(number) <= 0.262:
        die('Please Try more...')

    random.seed(new_state)
    iv_num = ADD(2000)

    iv = hashlib.sha256(str(iv_num).encode()).digest()[:16]
    key = hashlib.sha256(str(new_state1).encode()).digest()[:16]
    Aes = AES.new(key,AES.MODE_CBC, iv)
    C = Aes.encrypt(pad(flag,16))

    key_n, iv_n = int(sc()), int(sc())
    iv1 = hashlib.sha256(str(iv_n).encode()).digest()[:16]
    key1 = hashlib.sha256(str(key_n).encode()).digest()[:16]
    Aes_verify = AES.new(key1,AES.MODE_CBC, iv1)
    C_verify = unpad(Aes_verify.decrypt(C),16)

    if C_verify == flag:
        pr('Congratulations🎇🎇🎇!!!!')
        pr('Here is your flag😊：', M)
    else:
        pr('Maybe you could get the right flag!')

if __name__ == '__main__':
    main()

大致看了一下，题目貌似分为三个部分，那就一个一个看！

7x02 Part 1

先看看第一部分：这一部分首先要你输入一个超过 $250$ 位的素数 $p$ ，用于顶i有椭圆曲线 $y^2=x^3+12x+17$。然后让你给出曲线上面的一个点 $G$ 并带有判断 $G$ 是否在线上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
pr('Now we will start our formal GAME!!!')
pr('===== First 1💪: =====')
pr('Enter an integer as the parameter p for Curve: y^2 = x^3+12x+17 (mod p) and 250<p.bit_length()')
p1 = int(sc())
if not 250<=p1.bit_length():
    die('Wrong length!')
curve = CurveFp(p1, 12, 17,1)
pr(curve)
pr('Please Enter a random_point G:')
G_t = sc().split(b' ')
Gx,Gy = int(G_t[0]),int(G_t[1])
if not curve.contains_point(Gx,Gy):
    die('This point is outside the curve')
G = Point(curve,Gx,Gy)

for i in range(500):
    ECDU = ECCDu(curve,G)
    m  = 'My secret is a random saying of phrase,As below :' + generate_random_string(119)
    Number = ECDU.Random_key(1344)
    c = Number^bytes_to_long(m.encode())
    pr(f'c = {c}')
    pr(f'P = {int(ECDU.P.x()), int(ECDU.P.y())}')
    pr(f'Q = {int(ECDU.Q.x()), int(ECDU.Q.y())}')

    pr('Enter m:')
    m_en = sc().rstrip(b'\n')
    if m_en != m.encode():
        die('This is not the right m,Please try again')
    else:
        pr('Right m!!!')
pr('Bingo!')
new_state,new_state1 = ADD(136),ADD(50)

random.seed(new_state)

然后需要进行 $500$ 轮：每一轮给出一个 $c$， 然后 $Q=r_{32}G$，$P=65537Q$。并且经过测试， secure_choice、generate_random_string 和 getRandomNBitInteger 都不会改变 getrandbits 的值。

1
2
3
4
5
6
7
8
9
10
11
12
def secure_choice(sequence):
    if not sequence:
        return None
    randbelow = 0
    for i, x in enumerate(sequence):
        randbelow += 1
        if os.urandom(1)[0] < (1 << 8) * randbelow // len(sequence):
            return x
def generate_random_string(length):
    characters = string.ascii_letters + string.digits
    random_string = ''.join(secure_choice(characters) for i in range(length))
    return random_string

但是他这个 ECCDU 的生成方式非常诡异，感觉这个似乎不是很好预测。但为啥他这个是 $P=dQ=65537Q$ 呢，这么明显的 $P,Q$ 关系有啥意义吗？盲猜这个 $d$ 大概率是某个私钥被泄露了。

查了一下，这玩意虽然不是私钥泄露，但属于后门一类的东西。ECCDU 实际上是 DUAL ECC 随机数生成器。当知道了 $P,Q$ 之间的离散对数关系之后，只需要很简单的操作就可以恢复密钥：在这个题目中是这样的：

1.设置初始状态 $s_0$。
2.计算 $t=(s_0Q)_x$
3.计算 $s_1=(s_0P)_x$
4.返回 $t \mod 2^{250}$ 的值

那么，如果我们知道了第一次输出的内容。那就可以求出 $t\mod 2^{250}$ 的值。并且如果丢掉的位数少的话，$t$ 的实际值是可以枚举的。假如我们枚举到了正确的 $t$。那么有：E.lift_x(t) 可执行，那我们就得到了 $s_0Q$ 横坐标的真实值。又因为我们知道 $P=dQ$那么 $s_1$ 就可以通过下面的式子得到，其截断值就是 $t_1$ 的值。
$$
s_1=(s_0P)_x=(s_0dP)_x
$$

然而，在原题中，我们得到的比特是数是 $1344$（也就是 $168$字节），已知的长度为 $49$ 字节，未知的长度为 $119$ 字节。那么划分一下：$6$ 个随机数中， $t_0,t_1,t_2$ 我们分别知道 $94,250,48$ 位。那么我们就可以通过 $t_1$ 的完整值，枚举 $s_1$，进而结合 $t_2$ 的高位拿到 $t_2$ 的完整值，那么后面的数值也就都能求出来了（当然我为了保险，只判断高 $46$ 位）。。

下面就是找一个素数 $p$ 使得 $y^2=x^3+12x+17$ 上有光滑点了。这里自己找了下，可以选 

1
2
3
4
p=10966580842619877820066146550592605243948059864235950049184301493326519904217
n=10966580842619877820066146550592605243884930330463142198655617377280752484140 
order = 2**2 · 5 · 7 · 31 · 103 · 127 · 65537
#65537 * 5 * 103 * 127

那么第一部分的solution 就这么完成了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
p=10966580842619877820066146550592605243948059864235950049184301493326519904217
n=10966580842619877820066146550592605243884930330463142198655617377280752484140
order=65537 * 127 * 103 * 5
E=EllipticCurve(GF(p),[12,17])
Gx=9902877122724401288649251020980593854891741191216834612223927570106136389588
Gy=5145046550562502488367834786527673957133862042253512817925201451928791986047
G=E(Gx,Gy)
assert n%order==0
sh.sendline(str(p).encode())
sh.recvuntil(b':')
sh.sendline(f'{Gx} {Gy}'.encode())

msg=b'My secret is a random saying of phrase,As below :'
vmsg=bytes_to_long(msg)<<952

from tqdm import *
R32s=[]
for i in tqdm(range(500)):
    sh.recvuntil(b'c =')
    c=eval(sh.recvline())
    sh.recvuntil(b'P =')
    P=eval('E '+sh.recvline().strip().decode())
    sh.recvuntil(b'Q =')
    Q=eval('E'+sh.recvline().strip().decode())
    R32s.append(discrete_log(Q,G,operation='+'))
    ctmp=c^vmsg
    tarr=[0]*6
    for i in range(6):
        tarr[5-i]=ctmp%(2**250)
        ctmp>>=250
    tarr[3]=tarr[4]=tarr[5]=0
    tarr[2]=tarr[2]>>(204)<<(204)
    # print(tarr)
    # print(R32)
    # print(c)
    # print(P)
    # print(Q)
    for i in range(16):
        try:
            s1=Integer((i<<250)|tarr[1])
            sQ=E.lift_x(s1)
            s2=Integer((65537*sQ)[0])
            t2all=Integer((s2*Q)[0])
            t2=t2all%(2**250)
            if(((t2>>204)<<204)==tarr[2]):
                print('found:',i)
                break
        except:
            pass
    else:
        print('not found')
    # sh.interactive()
    s0=s2
    for i in [2,3,4,5]:
        ti=(s0*Q)[0]
        s0=Integer((s0*P)[0])
        tarr[i]=Integer(ti)%2**250
    # print(tarr)
    t1344=0
    for i in range(6):
        t1344<<=250
        t1344|=tarr[i]
    msgans=(long_to_bytes(c^t1344))
    sh.sendline(msgans)
print(R32s)

在第一部分结束后，系统会设置 new_state 和 new_state1。分别是 $136$ 个 getrandbits(32) 和 $50$ 个 getrandbits(32) 的结果。如果回顾MT19937的源码的话，可以发现每个状态 $r_{i+624}$ 只和 $r_{i},r_{i+1},r_{i+397}$ 三个数字有关。 虽然我们只有 $500$ 个状态，也就是 $r_{0\sim499}$，并且 $r_{500\sim623}$ 是未知的，而 $r_{624\sim 726}$ 我们是可以知道的，因为这一部分只和 $r_{0\sim499}$ 有关。 这里 new_state 与 $r_{500\sim 635}$ 有关，而 new_state1 与 $r_{636\sim685}$ 有关。因此我们可以得到 new_state1，也就是最后的解密密钥。

7x03 Part 2

假设我们已经获得了 new_state1，下面来看看第二部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
pr('===== Second 2💪: =====')
curve1 = CurveFp(q,a,b,1)
pr(f'{int(curve1.p()),int(curve1.a()),int(curve1.b())}')

pr("Enter a number that does not exceed 1500")
number = int(sc())

pr(f'You only have {number} chances to try')
success = 0
for i in range(number):
    Gx = secure_choice(select)
    R = Rng(25)
    pr('Gx = ',Gx)
    pr('Px = ',shout(Gx, R, q, a, b))
    R_n = int(sc().rstrip(b'\n'))
    if R_n != R:
        pr(f'Wrong number!!!,Here is your right number {R}')
    else:
        pr('GGood!')
        success += 1

if int(success)/int(number) <= 0.262:
    die('Please Try more...')

第二轮一开始会给你 $q,a,b$ 三个值，其中 $q$ 是 $64$ 位素数，你有至多 $1500$ 次机会，如果做过CryptoHack可以知道，这边的 shout 是根据点 $P$ 的横坐标求出 $dP$ 的横坐标。由于这边的 $d$ 是 getrandbits(25) 产生的，且 $q$ 比较小，因此求ECDLP是相对容易的。如果不放心复杂度，可以自己写个BSGS，计算量也就 $13$ 位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def xDBLADD(P, Q, PQ, q, a, b):
    (X1, Z1), (X2, Z2), (X3, Z3) = PQ, P, Q
    X4 = (X2**2 - a * Z2**2) ** 2 - 8 * b * X2 * Z2**3
    Z4 = 4 * (X2 * Z2 * (X2**2 + a * Z2**2) + b * Z2**4)
    X5 = Z1 * ((X2 * X3 - a * Z2 * Z3) ** 2 - 4 * b * Z2 * Z3 * (X2 * Z3 + X3 * Z2))
    Z5 = X1 * (X2 * Z3 - X3 * Z2) ** 2
    X4, Z4, X5, Z5 = (c % q for c in (X4, Z4, X5, Z5))
    return (X4, Z4), (X5, Z5)

def xMUL(P, k, q, a, b):
    Q, R = (1, 0), P
    for i in reversed(range(k.bit_length() + 1)):
        if k >> i & 1:
            R, Q = Q, R
        Q, R = xDBLADD(Q, R, P, q, a, b)
        if k >> i & 1:
            R, Q = Q, R
    return Q

def shout(x, d, q, a, b):
    P = (x,1)
    Q = xMUL(P, d, q, a, b)
    return Q[0] * pow(Q[1], -1, q) % q

计算得到：$\dfrac{624\times32}{25}=798.72$，也就是我们只需要 $799$ 组随机数，就可以预测后面的数值了。那么我们后面可以有 $700$ 组正确预测，正确概率也达到了 $0.4669$，远大于 $0.262$，因此这一部分也就这么过了。

但这样还是会有问题：这样构造出的矩阵尺寸为 $19968\times19975$，但其秩只有 $16808$，因为这里面很多比特是线性相关的。经过测试，貌似到 $1250$ 组的时候，矩阵的秩才达到 $19937$，预测才能够百分百成功。

因此，可以选择发送 $1266$ 组数据，前 $342$ （$1266\times0.27=341.82$）组正常BSGS（大约十分钟），后面瞎猜，这样也能够满足成功率的要求。。

这边还有个很坑的点：题目中 $q,a,b=18446744073709550537,12,19$ 为固定值。但给的 $x$ 坐标不一定在原曲线上，因此需要在 $\mathbb F_{q^2}$ 上定义曲线，模数 $q$ 的二次非剩余为 $-3$。

那么这一部分就这么下来了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
sh.recvuntil(b'(')
q,a,b=eval('('+sh.recvline().decode())
print(q,a,b)
sh.recvline()

nSample=1266
sh.sendline(str(nSample).encode())
sh.recvline()
import mttools
F=mttools.MT19937()
F.setstate(R32s[:500]+[0]*124)
newstate1=0
for i in range(12):
    F.getstate()
newstate1=sum([F.getstate() for _ in range(50)])

# with open('debugclient','w') as fffp:
#     fffp.write(str(newstate1)+'\n')
#     fffp.write(str(R32s))


def ecBSGS(G,H):
    D=dict()
    P=E(0)
    G2=G*5793
    for i in range(5793):
        D[P]=i
        P+=G2
    Htmp=H
    for i in range(5793):
        u=D.get(Htmp,None)
        if(u):
            return u*5793+i
        Htmp-=G
    return -1

Fq2=GF((q,2),name='sq3i',modulus=[3,0,1])
E=EllipticCurve(GF(q*q),[a,b])
D=[]
realSample=int(1+0.27*nSample)

for i in tqdm(range(realSample)):
    sh.recvuntil(b'=')
    Gx=int(sh.recvline())
    sh.recvuntil(b'=')
    Px=int(sh.recvline())
    G=E.lift_x(ZZ(Gx))
    P=E.lift_x(ZZ(Px))
    d=ecBSGS(G,P)
    if(d+1):
        sh.sendline(str(d).encode())
        D.append(int(d))
    else:
        P=-P
        d=ecBSGS(G,P)
        if(d+1):
            sh.sendline(str(d).encode())
            D.append(int(d))
        else:
            print('fail')
            exit(0)
for i in tqdm(range(realSample,nSample)):
    sh.recvuntil(b'=')
    Gx=int(sh.recvline())
    sh.recvuntil(b'=')
    Px=int(sh.recvline())
    sh.sendline(b'99999999999999')
    sh.recvuntil(b'right number')
    v=sh.recvline(keepends=False)
    D.append(int(v))
print(len(D))

不过鸡块博客中提到，这边系统没有判断输入是否大于 $1500$，因此发 $2000$ 过去也没啥事，$1300$ 组拿数据，$700$ 组预测。可以省去了BSGS的时间。

7x04 Part 3

最后这一部分，随机数生成器又冲洗你设置成了new_state，然后 iv 就是 $2000$ 个 getrandbits(32) 的和，密钥就是 new_state1，传过去就行了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
random.seed(new_state)
iv_num = ADD(2000)

iv = hashlib.sha256(str(iv_num).encode()).digest()[:16]
key = hashlib.sha256(str(new_state1).encode()).digest()[:16]
Aes = AES.new(key,AES.MODE_CBC, iv)
C = Aes.encrypt(pad(flag,16))

key_n, iv_n = int(sc()), int(sc())
iv1 = hashlib.sha256(str(iv_n).encode()).digest()[:16]
key1 = hashlib.sha256(str(key_n).encode()).digest()[:16]
Aes_verify = AES.new(key1,AES.MODE_CBC, iv1)
C_verify = unpad(Aes_verify.decrypt(C),16)

if C_verify == flag:
    pr('Congratulations🎇🎇🎇!!!!')
    pr('Here is your flag😊：', M)
else:
    pr('Maybe you could get the right flag!')

这边EXP就很简单了，可以直接用gf2bv做（$\mathsf{34s,373MB}$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
def gf2bv_mt19937(bs, out):
    lin = LinearSystem([32] * 624)
    mt = lin.gens()

    rng = MT19937(mt)
    zeros = [rng.getrandbits(bs) ^ int(o) for o in out] + [mt[0] ^ int(0x80000000)]
    sol = lin.solve_one(zeros)

    rng = MT19937(sol)
    pyrand = rng.to_python_random()
    return pyrand
rng2=gf2bv_mt19937(25,D)
A32=[rng2.getrandbits(32) for i in range(2000)]
A=sum(A32)
sh.sendline(str(newstate1).encode())
sh.sendline(str(A).encode())
print(sh.recvall(timeout=6))

当然，构造矩阵也是可以的（$\mathsf{112s,6.9GB}$）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import random
def getRows(rng):
    row=[]
    for i in range(nSample):
        row+=list(map(int, (bin(rng.getrandbits(25))[2:].zfill(25))))
    return row
rng=random.Random()
M=[]
for i in tqdm(range(19968)):#这一部分为固定套路，具体原因已经写在注释中了
    state = [0]*624
    temp = "0"*i + "1"*1 + "0"*(19968-1-i)
    for j in range(624):
        state[j] = int(temp[32*j:32*j+32],2)
    rng.setstate((3,tuple(state+[624]),None)) #这个setstate也是固定格式，已于2025.1.21测试
    M.append(getRows(rng))
M=Matrix(GF(2),M)
print("r(M)=",M.rank())
y=[]
for i in range(nSample):
    y+=list(map(int, (bin(D[i])[2:].zfill(25))))
y=vector(GF(2),y)
s=M.solve_left(y)
G=[]
for i in range(624):
    C=0
    for j in range(32):
        C<<=1
        C|=int(s[32*i+j])
    G.append(C)
RNG1 = random.Random()
for i in range(624):
    G[i]=int(G[i])
RNG1.setstate((int(3),tuple(G+[int(624)]),None))
A32=[RNG1.getrandbits(32) for i in range(2000)]
A=sum(A32)

sh.sendline(str(newstate1).encode())
sh.sendline(str(A).encode())
print(sh.recvall(timeout=6))

7x05 完整exp

那么最终完整的exp就是这些了（直接调了我两天半才调出来。。。）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#python 3
from pwn import *
from Crypto.Util.number import *
from hashlib import *
from sage.all import *
context.log_level='debug'
def getyanzhengma(s16,s64):
    table='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'
    for ch1 in table:
        for ch2 in table:
            for ch3 in table:
                for ch4 in table:
                    if(sha256((ch1+ch2+ch3+ch4+s16).encode()).hexdigest()==s64):
                        return ch1+ch2+ch3+ch4
    return 'aaaa'
# sh=process(['python3','task37.py'])
sh=remote("node7.anna.nssctf.cn",23842)
sh.recvuntil(b'+')
recv=sh.recvline().decode().strip().split('==')
s16=recv[0][:-2]
s64=recv[1][1:-1]
print(s16,s64)
yanzhengma=getyanzhengma(s16,s64)
sh.sendline(yanzhengma.encode())
for i in range(3):
    sh.recvline()


p=10966580842619877820066146550592605243948059864235950049184301493326519904217
n=10966580842619877820066146550592605243884930330463142198655617377280752484140
order=65537 * 127 * 103 * 5
E=EllipticCurve(GF(p),[12,17])
Gx=9902877122724401288649251020980593854891741191216834612223927570106136389588
Gy=5145046550562502488367834786527673957133862042253512817925201451928791986047
G=E(Gx,Gy)
assert n%order==0
sh.sendline(str(p).encode())
sh.recvuntil(b':')
sh.sendline(f'{Gx} {Gy}'.encode())

msg=b'My secret is a random saying of phrase,As below :'
vmsg=bytes_to_long(msg)<<952

from tqdm import *
R32s=[]
for i in tqdm(range(500)):
    sh.recvuntil(b'c =')
    c=eval(sh.recvline())
    sh.recvuntil(b'P =')
    P=eval('E '+sh.recvline().strip().decode())
    sh.recvuntil(b'Q =')
    Q=eval('E'+sh.recvline().strip().decode())
    R32s.append(int(discrete_log(Q,G,operation='+')))
    ctmp=c^vmsg
    tarr=[0]*6
    for i in range(6):
        tarr[5-i]=ctmp%(2**250)
        ctmp>>=250
    tarr[3]=tarr[4]=tarr[5]=0
    tarr[2]=tarr[2]>>(204)<<(204)
    for i in range(32):
        try:
            s1=Integer((i<<250)|tarr[1])
            sQ=E.lift_x(s1)
            s2=Integer((65537*sQ)[0])
            t2all=Integer((s2*Q)[0])
            t2=t2all%(2**250)
            if(((t2>>204)<<204)==tarr[2]):
                #print('found:',i)
                break
        except:
            pass
    else:
        print('not found')
    # sh.interactive()
    s0=s2
    for i in [2,3,4,5]:
        ti=(s0*Q)[0]
        s0=Integer((s0*P)[0])
        tarr[i]=Integer(ti)%2**250
    # print(tarr)
    t1344=0
    for i in range(6):
        t1344<<=250
        t1344|=tarr[i]
    msgans=(long_to_bytes(c^t1344))
    sh.sendline(msgans)
print(len(R32s))

sh.recvuntil(b'(')
q,a,b=eval('('+sh.recvline().decode())
print(q,a,b)
sh.recvline()

nSample=1266
sh.sendline(str(nSample).encode())
sh.recvline()
import mttools
F=mttools.MT19937()
F.setstate(R32s[:500]+[0]*124)
newstate1=0
for i in range(12):
    F.getstate()
newstate1=sum([F.getstate() for _ in range(50)])

def ecBSGS(G,H):
    D=dict()
    P=E(0)
    G2=G*5793
    for i in range(5793):
        D[P]=i
        P+=G2
    Htmp=H
    for i in range(5793):
        u=D.get(Htmp,None)
        if(u):
            return u*5793+i
        Htmp-=G
    return -1

Fq2=GF((q,2),name='sq3i',modulus=[3,0,1])
E=EllipticCurve(GF(q*q),[a,b])
D=[]
realSample=int(1+0.27*nSample)

for i in tqdm(range(realSample)):
    sh.recvuntil(b'=')
    Gx=int(sh.recvline())
    sh.recvuntil(b'=')
    Px=int(sh.recvline())
    G=E.lift_x(ZZ(Gx))
    P=E.lift_x(ZZ(Px))
    d=ecBSGS(G,P)
    if(d+1):
        sh.sendline(str(d).encode())
        D.append(int(d))
    else:
        P=-P
        d=ecBSGS(G,P)
        if(d+1):
            sh.sendline(str(d).encode())
            D.append(int(d))
        else:
            print('fail')
            exit(0)
for i in tqdm(range(realSample,nSample)):
    sh.recvuntil(b'=')
    Gx=int(sh.recvline())
    sh.recvuntil(b'=')
    Px=int(sh.recvline())
    sh.sendline(b'99999999999999')
    sh.recvuntil(b'right number')
    v=sh.recvline(keepends=False)
    D.append(int(v))
print(len(D))

#=========IF YOU DO NOT HAVE GF2BV, REPLACE THE CODE BELOW TO THE LAST CODE BLOCK IN 7x04 CHAPTER.
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
def gf2bv_mt19937(bs, out):
    lin = LinearSystem([32] * 624)
    mt = lin.gens()

    rng = MT19937(mt)
    zeros = [rng.getrandbits(bs) ^ int(o) for o in out] + [mt[0] ^ int(0x80000000)]
    sol = lin.solve_one(zeros)

    rng = MT19937(sol)
    pyrand = rng.to_python_random()
    return pyrand
rng2=gf2bv_mt19937(25,D)
A32=[rng2.getrandbits(32) for i in range(2000)]
A=sum(A32)

sh.sendline(str(newstate1).encode())
sh.sendline(str(A).encode())
print(sh.recvall(timeout=6))

最终运行结果如下：

2

7x09 和去年11月对比？

相比较于去年 11 月，寒假从CryptoHack那边知道了 $X,Z$ 的表示，以及值用 $X$ 坐标计算倍点的方式。然后中途做了些题，知道了 getrandbits(X) 的完整解法（X不一定为 $32$ 的倍数）。当然，也从本题中，知道了DUAL EC随机数发生器的后门。因为当时不知道这些，加上这个题sol比较少，所以直接放弃了。没想到 $20$ 个星期后，积累了一些知识，竟然还做出来了。。

9.总结

貌似MT19937的题型的解法相对比较固定，基本就是建矩阵然后解state，并且也有很多工具能够直接一把梭。。。

rec:当你发现某个题型出题思路和解题思路相对比较固定的时候，那就说明你变强了。

翻了眼QQ空间，今天是 3 月 21 日。（因为最近忙导师项目和CISCN所以这篇blog原计划是 3 月 10 日前后发布的，还是拖到了现在才发布）。2021 年 3 月 21 日下午 4 点，我做出了 Am4 师傅给我发的 x1c 考核题，感觉那似乎还是昨天，但实际上已经 4 年了。。。

5

还有三个月就研二了，感觉半年来，自己CTF水平确实也是有所提升的，看后面三个月会不会还有啥继续进步吧。。。。。。

1
Nep{LOoK_aT_th3_sT4R-Lo0k_h0w_tH3y_5h1N3_fOr_Y0u}
CTFSeason4
#ExpLog
25Mar1-MTArchive
http://example.com/2025/03/21/25Mar1-MTArchive/
作者
huangx607087
发布于
2025年3月21日
许可协议