2025-N1CTF-junior-wp-crypto

N1 junior，启动！

CheckIn

题目

import os
from Crypto.Util.number import *
from secret import FLAG

p, q = getPrime(512), getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537

r = bytes_to_long(b'n1junior2025')
gift = ((2025 * p + r * r) * p % phi) >> 750

msg = bytes_to_long(FLAG)
ct = pow(msg, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")
print(f"gift = {gift}")

'''
n = 127060392619341060272126983366487069092712215979664340339428955285201267724168574813227106020122399594060458777939446978632526348867806863618885370221957087197582864380885199290793062293120324984868138488667017882272415668310242448870352699380394381756621677031459335310964085476227148301120850021800822495119
e = 65537
ct = 18305235107479382231970252522433686185039231184629854177334609960907102735540326234277108553640185845164498239822263821349544015918443334769445559622730315115384134147808359107914969010678607157349844717217781801237935737980608575612421610972048739840839726108493286994232100086338529591086935374295281642738
gift = 8312456126096895497368692810699639462746223116345115761188530231045483000989605820
'''

题目在给出RSA公钥的基础上，额外给出了一个gift：

$gift = ((2025p + r^2)p\;\%\;\phi) >> 750$

其中r = bytes_to_long(b'n1junior2025')。

思路

由于$r$并不大，所以$(2025p + r^2)p$的数量级主要是由$2025p^2$决定的，可以看出这一项也只是比$\phi$略大，所以在小范围内爆破$k$，那么在$k$正确的情况下有：

$(gift << 750) \approx (2025p + r^2)p + k\phi$

把$\phi$写开：

$(gift << 750) \approx (2025p + r^2)p + k(p-1)(q-1)$

这个时候两边同时乘$p$，就可以得到一个关于$p$的单变量方程：

$(gift << 750)p \approx (2025p + r^2)p^2 + k(p-1)(n-p)$

在RealField下可以解出$p$的高位，然后就可以copper了。

exp

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

n = 127060392619341060272126983366487069092712215979664340339428955285201267724168574813227106020122399594060458777939446978632526348867806863618885370221957087197582864380885199290793062293120324984868138488667017882272415668310242448870352699380394381756621677031459335310964085476227148301120850021800822495119
e = 65537
ct = 18305235107479382231970252522433686185039231184629854177334609960907102735540326234277108553640185845164498239822263821349544015918443334769445559622730315115384134147808359107914969010678607157349844717217781801237935737980608575612421610972048739840839726108493286994232100086338529591086935374295281642738
gift = 8312456126096895497368692810699639462746223116345115761188530231045483000989605820

r = bytes_to_long(b'n1junior2025')
G = gift << 750
PR.<x> = PolynomialRing(RealField(1000))
for i in trange(2200, 5000):
    f = (2025*x + r*r)*x^2 - i*(x-1)*(n-x) - x*G
    res = f.roots()
    res = int(res[-1][0]) >> 230 << 230
    P.<y> = PolynomialRing(Zmod(n))
    g = res + y
    ress = g.small_roots(X=2^230, beta=0.499, epsilon=0.04)
    if(ress != []):
        print(i, ress)
        p = int(int(ress[0]) + res)
        break

q = n // p
print(long_to_bytes(int(pow(ct, inverse(e, (p-1)*(q-1)), n))))

#flag{ec6f23afd0b7453bb8224146b6aad196}

BabyAES

题目

from Crypto.Cipher import AES
from random import randbytes
import os

FLAG = "flag{REDACTED}"
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)
print(f"Congrats! 🚩 {FLAG}")

题目一共128轮挑战，每一轮挑战可以输入一段msg，然后靶机会返回一个密文，需要判断出这个密文是未知密钥的AES加密msg得到的，还是randbytes得到的。连续通过128轮就可以得到flag。

思路

前些天接触mt接触的有点多，所以这题看到randbytes的一瞬间就知道这题的做法了。首先第一轮发一段足够长的msg过去(长度大于19968bits)，然后盲猜第一轮发回来的是randbytes，这个时候就可以实现随机数预测了。一个小细节是pad里也会调用randbytes，所以之后每轮的预测要把这个也算上。

exp

from Crypto.Util.number import *
from extend_mt19937_predictor import ExtendMT19937Predictor
from pwn import *
from tqdm import trange
from os import urandom

context.log_level = "critical"
sh = remote("39.106.16.204", 46046)

sh.recvuntil(b"msg: ")
sh.sendline(urandom(19968//8-16).hex().encode())
sh.recvuntil(b"ct:")
res = bytes_to_long(bytes.fromhex(sh.recvline().strip().decode())[::-1])
sh.recvuntil(b"[+] ")
sh.sendline(b"1")


predictor = ExtendMT19937Predictor()
for _ in range(624):
    x = res & 0xffffffff
    res >>= 32
    predictor.setrandbits(x, 32)

for i in trange(127):
    sh.recvuntil(b"msg: ")
    predictor.predict_getrandbits(16*8)
    temp = predictor.predict_getrandbits(19968)
    sh.sendline(urandom(19968//8-16).hex().encode())
    sh.recvuntil(b"ct:")
    res = bytes_to_long(bytes.fromhex(sh.recvline().strip().decode())[::-1])
    sh.recvuntil(b"[+] ")

    if(res == temp):
        sh.sendline(b"1")
    else:
        sh.sendline(b"0")
print(sh.recvline())

#flag{AES_15_S4f3_3n0ugh_but_MT19937_n07}

▪️

题目

from Crypto.Util.number import *
from random import *
from secret import flag
    
def gen_pubkey(n, k, l):
    L = (matrix(Permutations(n).random_element())*vector([i for i in range(n)])).list()[:3*l]
    gen_col1 = lambda x: [x^(i+1) for i in range(l)]+[0]*(k-l)
    gen_col2 = lambda x: [x^(i+1) for i in range(k)]
    
    G = matrix(F,[gen_col1(Integer(randint(1,p-1))) if i in L else gen_col2(Integer(randint(1,p-1))) for i in range(n)]).T
    S = random_matrix(F,k,k)
    
    pubkey = S*G
    privkey = L,G
    
    return (pubkey,privkey)

def encrypt(pubkey, L, message):
    x = random_matrix(F,1,k)
    e = [0 for i in range(n)]
    for i in range(20):
        s = randint(0,n-1)
        if s not in L:
            e[s] = randint(1,p-1)
    
    c = x*pubkey+message*matrix(F,[1 for i in range(n)])+matrix(F,e)
    return c
    
p = 8605605879820394929871171704526267558076275882769290613301265383544615884789835912139373711919931926389028123698181386695814578808144200282148287377501923
F = GF(p)

m = bytes_to_long(flag)
n, k, l = 128, 84, 12

pubkey, privkey = gen_pubkey(n,k,l)
c = encrypt(pubkey,privkey[0],m)
    
save(pubkey.list(),'P.sobj')
save(c.list(),'c.sobj')

题目基于编码，首先生成了一组如下的公私钥：

$pk:\quad SG$ $sk:\quad L, G$

其中：

$L$是一个长36的向量，元素由0-127的其中36个组成，并且打乱了顺序
$G$是84x128的矩阵，有点类似GRS码的生成矩阵，但是区别在于他是从一次幂开始的，而且其中有36列只到12次幂，这36列的位置由$L$决定
$S$是84x84的随机矩阵

之后对flag进行加密，加密方式为：

生成一个长$k$的随机向量$x$
生成一个长$n$的向量$e$，其中error数量大约为14个左右
按如下方式计算密文：
$c = xSG + mt + e$
其中t=matrix(F,[1 for i in range(n)])

给出$pk$和$c$，要求出$m$。

思路

从编码的角度我没有想出什么思路，所以我是从公钥$pk=SG$入手的，为了表示方便，后面我把$pk$这个矩阵乘积看作一个整体，记为$A$。

那么整个加密过程就是：

$c = xA_{k,n} + mt + e$

$A$是我们知道的，所以我们也当然可以求出他的右核，而对于$A$右核中的任意一条向量$y$来说，都有：

$Ay = 0$

而$A$的右核理论上有$n-k$条向量，将这些向量$y_i$都代入加密的式子中就会得到44个新的方程：

$cy_i = mty_i + ey_i \quad,\quad i \in \{1,2,\cdots,44\}$

如果把$m$看作一个变量，$e$看作$n$个变量的话，我们相当于可以获得关于$n+1$个变量的$n-k$个方程，对于题目数据来说，也就是44个方程，129个变量。这相当于是要解一个下面形式的矩阵方程：

$L_{44, 129}x_{129, 1} = R_{44, 1}$

这当然是求不出唯一解的，但是要注意到，对于$e$来说，他不是单纯的128个变量，他仅仅只有14个左右非零的位置，而为零的那些位置对于方程的结果是不影响的，所以从这个角度来说我们可以：

从上面的$L$中先取第一列（对应$m$），之后再从1-128随机抽取43列
如果这43列中恰好包含了$e$中所有非零项，就可以解矩阵方程得到$m$的值了
假设非零项就是14个，那么这样抽取的成功概率为：
$p = \frac{C(128-14,43-14)}{C(128,43)}$
这个概率本身也还比较可观，大约是25bit的复杂度，并且实际上概率远高于这个理论概率，因为$L$并不算个随机矩阵，他的系数比较稀疏

然后实际上发现似乎根本就不用抽，直接解这个理论上无穷多组解的矩阵方程都能把$m$解出来，这可能和$G,e$的结构有某种关系。

exp

题目：

from Crypto.Util.number import *

c = load("c.sobj")
pk = load("P.sobj")

p = 8605605879820394929871171704526267558076275882769290613301265383544615884789835912139373711919931926389028123698181386695814578808144200282148287377501923
F = GF(p)
n, k, l = 128, 84, 12

pk = Matrix(F, k, n, pk)
c = vector(F, c)

RKer = pk.right_kernel().basis()
M = vector(F, [1 for i in range(n)])

L = Matrix(F, n+1, n+1)
R = vector(F, n+1)
for i in range(1, len(RKer)):
    L[i, 0] = M*RKer[i]
    L[i, 1:] = RKer[i]
    R[i] = c*RKer[i]
L = L[1:len(RKer), :]
R = R[1:len(RKer)]
print(L.dimensions())

print(L.solve_right(R))

print(long_to_bytes(int(198974677777462684626999345470421547778964861711348410486818775486703757252837980982397)))

#flag{Us3_sQu@r3_coD3_4nD_h4ck_Th3_L}

QuantumVM

题目

from Crypto.Util.number import *
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
from Crypto.Cipher import AES
import os, random
FLAG = "flag{REDACTED}"

SIM = AerSimulator()
class QuantumVM:
    def __init__(self):
        self.qc = QuantumCircuit(256)
        for i in range(128):
            self.qc.h(i)
    
    def exec(self, code):
        ip = 0
        param = random.sample(range(128,256), 128)
        while ip<len(code):
            op = code[ip]; ip += 1
            num = code[ip]; ip += 1
            match op:
                case 0: self.qc.x(num)
                case 1: self.qc.y(num)
                case 2: self.qc.z(num)
                case 3: self.qc.cx(num, param[num])
                case _: ValueError("Invalid Operation :(")
        for i in range(128): 
            if random.randint(0,1): self.qc.x(i)
            else: self.qc.x(param[i])
        self.qc.measure_all()
        return int(SIM.run(self.qc,shots=1,memory=True).result().get_memory()[0],2)

key = os.urandom(32)
for _ in range(150):
    qvm = QuantumVM()
    code = bytes.fromhex(input("Quantum Code > "))
    print("⚙️", bytes_to_long(key)^qvm.exec(code))
print("🚩", AES.new(key, AES.MODE_ECB).encrypt(FLAG.encode()).hex())

题目基于量子计算，交互过程是：

连接上靶机后，靶机生成一个长32的随机字节串，用作AES的key
之后进行150轮交互，每一次交互都可以输入一段code交给QuantumVM执行，靶机会将执行的结果与key异或并发送回来
150轮交互结束之后，靶机发送AES加密的flag

QuantumVM实际上是模拟了量子电路对于量子比特的操作，他的全流程有：

生成有256个量子比特的量子电路
将前128个量子比特通过$H$门
之后进入可以自己操作的部分，可以选择$X,Y,Z,CNOT$门用

在自己能操作的部分结束后，靶机会按如下方式将其中128个量子比特通过$X$门：

1
2
3

for i in range(128): 
    if random.randint(0,1): self.qc.x(i)
    else: self.qc.x(param[i])

最后对这个量子电路进行一次测量，即得到一次256个量子比特的观测值并返回

预备知识

在这之前我对量子计算一点也不了解，所以正好趁此机会学了一点点，这个题主要会用到量子计算的下面一些基础知识。

量子比特(qubit)

量子比特是量子计算的基本单位，他有如下两个计算基本状态：

$\left|{0}\right\rangle$ $\left|{1}\right\rangle$

而在量子比特没有被观测的时候，他的状态可以用如下形式表示：

$\left|\psi\right\rangle = \alpha\left|{0}\right\rangle + \beta\left|{1}\right\rangle$

这个状态的含义是：

$\alpha,\beta$都是复数，并且满足$|\alpha|^2+|\beta|^2=1$
如果对这个量子比特进行观测，那么他有$|\alpha|^2$的概率是0，$|\beta|^2$的概率是1
在对这个量子比特进行观测之后，这个量子比特会改变自己的状态
$\alpha,\beta$的具体值是没有办法知道的

而实际上，这个表示形式也代表着，量子比特可以表示为一个三维单位球上的一个特定点，这个三维单位球也叫做布洛赫球，如图：

为什么是这样可以参考：1.1 量子计算历史及量子比特 - 知乎

量子门

题目涉及到五种量子门：$H,X,Y,Z,CNOT$，其中前四个是单qubit量子门，$CNOT$是复qubit量子门。

为了清楚表示出每种门的作用，不妨把量子比特写成一个向量：

$\left|\psi\right\rangle = \left(\matrix{ \alpha\\ \beta }\right)$

那么几个门的作用分别就相当于左乘如下矩阵：

$X = \left(\matrix{ 0&1\\ 1&0 }\right)$ $Y = \left(\matrix{ 0&-i\\ i&0 }\right)$ $Z = \left(\matrix{ 1&0\\ 0&-1 }\right)$ $H = \frac{1}{\sqrt{2}} \left(\matrix{ 1&1\\ 1&-1 }\right)$

而直白点解释的话，几个门的主要作用是：

$X$：量子非门，就是翻转该量子比特
$Y$：进行相位转移和比特翻转
$Z$：转变相位
$H$：制造叠加态，并且满足$H^2 = I$

而对于$CNOT$门，它的作用可以描述为由第一个量子比特来控制第二个量子比特的翻转。如果第一量子比特是$\left|{0}\right\rangle$，第二量子比特就不翻转，否则翻转。也就是：

$\left|{00}\right\rangle \rightarrow \left|{00}\right\rangle$ $\left|{01}\right\rangle \rightarrow \left|{01}\right\rangle$ $\left|{10}\right\rangle \rightarrow \left|{11}\right\rangle$ $\left|{11}\right\rangle \rightarrow \left|{10}\right\rangle$

简易量子电路

这里主要需要介绍一下Bell states，由一个$H$门和一个$CNOT$门组成的电路，其输出就是种Bell states，这表现为两个量子比特一定相同，这也代表着这两个量子比特通过这个电路发生了纠缠。

思路

首先我们知道，题目将前128qubit通过$H$门制备了叠加态，也就是前128qubit是如下形式：

$\left|\psi\right\rangle = \alpha\left|{0}\right\rangle + \beta\left|{1}\right\rangle$

而后128qubit通过程序测试可以发现他们是$\left|{0}\right\rangle$，所以我们要在这样的基础上，想办法利用这个QuantumVM得到我们需要的结果。

我们需要注意到的是在执行完code后一定会发生的翻转：

1
2
3

for i in range(128): 
    if random.randint(0,1): self.qc.x(i)
    else: self.qc.x(param[i])

param是后128qubit索引的一个随机置换，因此这个翻转其实细看之下很不随机：

他一定会翻转正好128次
i和param[i]其中有且仅有一个会翻转

第一点会让人联想到之前SEETF与汉明重量有关的一道Neutrality：

Crypto趣题-流密码 | 糖醋小鸡块的blog

具体来说，如果我们能够想办法控制量子电路输出比特串的汉明重量，那么我们可以用类似的思路去做BKZ从而找到key。

而第二点则是提供了一个信息——这些量子比特之间存在成对的绑定关系，这也就提供了一个控制汉明重量的方法。由于前128个qubit是通过了$H$门的，所以我们利用刚才提到的会输出Bell states的简易量子电路，就可以让后128个qubit完全复制前128个qubit的状态，具体来说我们的code就选择为：

code = []
for i in range(128):
    code.append(3)
    code.append(i)
code = bytes(code).hex().encode()

这样，在发生最后的翻转之前，量子电路的256个qubit可以看成是128对，因为i的状态复制给了param[i]。而最后的翻转则使得这128对状态恰好相反了，也就是每一对都一定是下面状态的其中一种：

$\left|{10}\right\rangle , \left|{01}\right\rangle$

因此最终的输出汉明重量一定是128，之后就用SEETF的做法去做同态映射，然后BKZ就可以找到key了。

exp

code = []
for i in range(128):
    code.append(3)
    code.append(i)
code = bytes(code).hex().encode()

from Crypto.Util.number import *
from Crypto.Cipher import AES
from tqdm import *
from pwn import *

sh = remote("39.106.16.204", 20010)

c = []
for i in trange(150):
    sh.recvuntil(b"Quantum Code > ")
    sh.sendline(code)
    sh.recvuntil(b"\xe2\x9a\x99\xef\xb8\x8f ")
    c.append(int(sh.recvline()))

sh.recvuntil(b"\xf0\x9f\x9a\xa9 ")
enc = bytes.fromhex(sh.recvline().strip().decode())

C = []
m, n = 32*8, 150
for i in range(len(c)):
    temp = bin(c[i])[2:].zfill(m)
    vec = []
    for j in temp:
        if(j == "0"):
            vec.append(1)
        else:
            vec.append(-1)
    C.append(vec)

C = Matrix(ZZ,C).T
L = block_matrix(
    [
        [C,identity_matrix(m)]
    ]
)
L[:,:n] *= 2^20

res = L.BKZ(block_size=14)[0]
m = res[n:]
flag1 = ""
flag2 = ""
for i in m:
    if(i == 1):
        flag1 += "0"
        flag2 += "1"
    else:
        flag1 += "1"
        flag2 += "0"


key1 = long_to_bytes(int(flag1,2))
key2 = long_to_bytes(int(flag2,2))
print(AES.new(key1, AES.MODE_ECB).decrypt(enc))
print(AES.new(key2, AES.MODE_ECB).decrypt(enc))


#flag{Ent4ngled_5tat3_Leak_M5ggg}