2025-8-wp-crypto

8月比赛不少，但是基本都是很散的打着玩，没有很完整的打过某场比赛，所以就干脆一块儿放在这篇里了。

观安杯

这个好像是前几天的比赛，赛后有师傅给我看了看题，感觉还都蛮有趣的就写个wp。

baby_crypto

题目

import os
flag = os.getenv("FLAG", "flag{fake_flag}")
NUM = 113
state0, state1 = map(int, input().split(','))
MAX_STATE = 2**64 - 1
state0 &= MAX_STATE
state1 &= MAX_STATE
def generate_random():
    global state0, state1
    s1, s0 = state0, state1
    state0 = s0
    s1 ^= (s1 << 23) & MAX_STATE
    s1 &= MAX_STATE
    s1 ^= (s1 >> 17) & MAX_STATE
    s1 &= MAX_STATE
    s1 ^= s0
    s1 &= MAX_STATE
    s1 ^= (s0 >> 26) & MAX_STATE
    s1 &= MAX_STATE
    state1 = s1
    return state0

total = 0
for i in range(NUM):
    total += generate_random()

print("Total:", total)
if total >= 167 * 10 ** 19:
    print("Good Boy! Flag:", flag)
else:
    print("Bad Boy! Try again!")

题目需要输入两个state，之后基于这两个state的迭代产生113个随机数，如果这些随机数的和大于$167 \cdot 10 ^ {19}$就可以拿到flag。

思路

generate_random()函数里的操作只有^和&，因此是$GF(2)$下线性的，所以将初始的两个state拼起来看成长为128的向量$\mathbf{s}_0$时，可以得到每一轮迭代其实是：

$s_{i+1} = L_{128, 128}\mathbf{s}_i$

而由具体迭代的形式可以看出递推矩阵$L$的分块结构是：

$L = \left(\begin{matrix} O & I \\ L_1 & L_2 \\ \end{matrix}\right)$

其中$L_1,L_2$均把generate_random()当作黑盒去生成明密文对，就可以解线性方程求解出来。

得到$L$之后，我们相当于是要找一个$\mathbf{s}_0$，使得下列向量前半段对应的整数和越大越好：

$\mathbf{s}_1 = L\mathbf{s}_0 \\ \mathbf{s}_2 = L^2\mathbf{s}_0 \\ \cdots \\ \mathbf{s}_{113} = L^{113}\mathbf{s}_0 \\$

这里用贪心的思想，可以让$\mathbf{s}_i$的最高位都是1，然后在解空间里简单搜索一下，发现确实可以找到一组符合要求的解。

exp

MAX_STATE = 2**64 - 1
def generate_random_genM(state0, state1):
    s1, s0 = state0, state1
    state0 = s0
    s1 ^^= (s1 << 23) & MAX_STATE
    s1 &= MAX_STATE
    s1 ^^= (s1 >> 17) & MAX_STATE
    s1 &= MAX_STATE
    s1 ^^= s0
    s1 &= MAX_STATE
    s1 ^^= (s0 >> 26) & MAX_STATE
    s1 &= MAX_STATE
    state1 = s1
    return state1

def generate_random(state0, state1, nums):
    for _ in range(nums):
        s1, s0 = state0, state1
        state0 = s0
        s1 ^^= (s1 << 23) & MAX_STATE
        s1 &= MAX_STATE
        s1 ^^= (s1 >> 17) & MAX_STATE
        s1 &= MAX_STATE
        s1 ^^= s0
        s1 &= MAX_STATE
        s1 ^^= (s0 >> 26) & MAX_STATE
        s1 &= MAX_STATE
        state1 = s1
    return state0

from tqdm import *
NUMS = 113

L = []
R = []
for i in range(256):
    state0, state1 = randint(0, 2^64-1), randint(0, 2^64-1)
    L.append(list(map(int, bin(state0)[2:].zfill(64))) + list(map(int, bin(state1)[2:].zfill(64))))
    R.append(list(map(int, bin(generate_random_genM(state0, state1))[2:].zfill(64))))

L = Matrix(GF(2), L).T
R = Matrix(GF(2), R).T
K = L.solve_left(R)

K1, K2 = K[:, :64], K[:,64:]
K = block_matrix(GF(2), [
    [0, 1],
    [K1, K2],
])

state0, state1 = 12345, 67890
v = list(map(int, bin(state0)[2:].zfill(64))) + list(map(int, bin(state1)[2:].zfill(64)))
v = vector(GF(2), v)
res = K*v
print(int("".join(list(map(str, res[:64]))), 2), int("".join(list(map(str, res[64:]))), 2))

L = []
R = []
for _ in range(NUMS):
    L.append((K^_)[0])
    R.append(1)
L = Matrix(GF(2), L)
R = vector(GF(2), R)

res = L.solve_right(R)
Ker = Matrix(GF(2), L.right_kernel().basis())

from itertools import *

for _ in tqdm(product(range(2), repeat=Ker.nrows()), total=int(2^Ker.nrows())):
    tt = sum([i*j for i, j in zip(_, Ker)])
    ttt = tt + res
    S1, S2 = int("".join(list(map(str, ttt[:64]))), 2), int("".join(list(map(str, ttt[64:]))), 2)

    aa = 0
    for _ in range(1, NUMS+1):
        aa += generate_random(S1, S2, _)
    
    if(aa > 167 * 10 ** 19):
        print(aa, S1, S2)


#10592753371058848145, 16956729450365202520

cry4baby

题目

from sage.all import *
from ast import literal_eval
from secret import flag
import random

ells = [*primes(3, 128), 163]
p = 4*prod(ells)-1
B = QuaternionAlgebra(-1, -p)
i,j,k = B.gens()
O0 = B.quaternion_order([1, i, (i-j)/2, (1-k)/2])

def action(O, priv):
    for i,ell in zip(priv,ells):
        for _ in range(abs(i)):
            O = O.left_ideal([ell, j-sign(i)]).right_order()
    return B.quaternion_order(O.basis())


def check_safe_key(key): # for safety
    if len(key) != len(ells) or 0 in key or any(abs(i) > 3 for i in key):
        return False
    return True


menu = '''
1. Start
2. Share
3. Guess
'''

started = False
alice = [randint(-3, 3) for _ in range(len(ells))]

for __ in range(16):
    print(menu)
    choice = input("Enter your choice: ")
    if choice == '1':
        start = literal_eval(input("Enter start: "))
        if check_safe_key(start) and started == False:
            O0 = action(O0, start)
            Oa = action(O0, alice)
            started = True
    elif choice == '2':
        if started:
            bob = literal_eval(input("Hi bob, what's your key? "))
            if check_safe_key(bob):
                coeff = random.choice([1, -1]) # random the direction :)
                bob = [ _ * coeff for _ in bob]
                Ob = action(O0, bob)
                O_share = action(Oa, bob)
                assert O_share.isomorphism_to(action(Ob, alice)) # it's a Diffie-Hellman protocol
                print("This is your share:", O_share.basis())
        else:
            print("You don't have enough tickets.")
            continue
    elif choice == '3':
        guess = literal_eval(input("Enter your guess: "))
        if guess == alice:
            print("You are really good at QuaternionAlgebra!, This is you flag:", flag)
        else:
            exit("Go away, you thief!")
    else:
        exit("Invalid choice")

题目基于CSIDH的group action在四元代数下的实现。连接上靶机后，靶机随机生成alice的私钥，之后有以下几个交互选项：

输入1，可以输入一个私钥，靶机会用该私钥对应的group action移动起始点$O_0$，并在这之后再用alice的私钥计算$O_a$

这一步必须第一个进行，并且只能进行一次
输入2，可以输入一个bob的私钥，靶机会随机颠倒该私钥的正负性，之后利用该私钥计算$O_{ab}$并给出。该操作最多进行14次
输入3之后，如果能正确给出alice的私钥，则拿到flag

所有自行构造的私钥输入均需满足：

def check_safe_key(key): # for safety
    if len(key) != len(ells) or 0 in key or any(abs(i) > 3 for i in key):
        return False
    return True

思路

@hashhash之前出过一道类似的题，也是关于CSIDH的group action在四元代数下的实现。而在其中能了解的最核心的一点就是：CSIDH之所以困难是因为无法通过曲线计算出它对应的自同态环，而对于四元代数下的经历了group action的两个order来说，其connect ideal的norm会泄露该次group action的各因子，很简单的例子实现如下：

ells = [*primes(3, 128), 163]
p = 4*prod(ells)-1
B = QuaternionAlgebra(-1, -p)
i,j,k = B.gens()
O0 = B.quaternion_order([1, i, (i-j)/2, (1-k)/2])

def action(O, priv):
    for i,ell in zip(priv,ells):
        for _ in range(abs(i)):
            O = O.left_ideal([ell, j-sign(i)]).right_order()
    return B.quaternion_order(O.basis())

alice = [randint(-3, 3) for _ in range(len(ells))]
Oa = action(O0, alice)
I = O0*Oa
Connect_I = (1/I.norm())

print(alice)
print(factor(Connect_I))

其输出为：

1
2

[-2, -1, 3, 1, 1, 2, 3, 2, 2, 0, -1, 1, 3, 2, 3, 2, 0, -3, -2, -1, 1, 0, 0, 3, -1, -1, -3, -1, 0, 3, -3]
3^2 * 5 * 7^3 * 11 * 13 * 17^2 * 19^3 * 23^2 * 29^2 * 37 * 41 * 43^3 * 47^2 * 53^3 * 59^2 * 67^3 * 71^2 * 73 * 79 * 97^3 * 101 * 103 * 107^3 * 109 * 127^3 * 163^3

而对于这道题目，我们能拥有$O_0$以及$O_{ab}$，这相当于是说我们能够计算出多个alice的私钥与我们输入的$bob$私钥叠加的结果，只是这个结果存在一定扰动：

正负号我们不知道
我们输入的bob私钥本身可能被颠倒了正负

不过既然能交互多次，所以我们可以对私钥的每个分量进行多次排除，排除几次后就可以拿到唯一私钥了。

最开始输入一个全3让$Oa$对应的alice私钥变全正，能比较有效的排除多解

exp

ells = [*primes(3, 128), 163]
p = 4*prod(ells)-1
B = QuaternionAlgebra(-1, -p)
i,j,k = B.gens()
O0 = B.quaternion_order([1, i, (i-j)/2, (1-k)/2])

def action(O, priv):
    for i,ell in zip(priv,ells):
        for _ in range(abs(i)):
            O = O.left_ideal([ell, j-sign(i)]).right_order()
    return B.quaternion_order(O.basis())

from pwn import *
from tqdm import *

context.log_level = "critical"
sh = process(["sage", "task.sage"])

################################################################################## First time
sh.recvuntil(b"Enter your choice: ")
sh.sendline(b"1")
sh.sendline(str([3 for _ in range(len(ells))]).encode())

################################################################################## get alice key
alice = [set(range(-3+3, 4+3)) for _ in range(len(ells))]
for _ in trange(14):
    sh.recvuntil(b"Enter your choice: ")
    sh.sendline(b"2")
    bob = [choice([-3,-2,-1,1,2,3]) for _ in range(len(ells))]
    sh.sendline(str(bob).encode())

    sh.recvuntil(b"This is your share:")
    Oab = B.quaternion_order(sage_eval(sh.recvline().strip().decode(), locals=globals()))
    I = O0*Oab
    Connect_I = (1/I.norm())
    temp = list(factor(Connect_I))

    for ii in ells:
        ind = ells.index(ii)
        FIND = 0
        for jj in temp:
            if(ii == jj[0]):
                FIND = 1
                alice[ind] = alice[ind] & set([jj[1]-bob[ind], jj[1]+bob[ind], -jj[1]+bob[ind], -jj[1]-bob[ind]])
                break
        if(FIND == 0):
            alice[ind] = alice[ind] & set([-bob[ind], bob[ind]])
    print(alice)

################################################################################## get flag
alice = [list(_)[0]-3 for _ in alice]
sh.recvuntil(b"Enter your choice: ")
sh.sendline(b"3")
sh.recvuntil(b"Enter your guess: ")
sh.sendline(str(alice).encode())
print(sh.recvline())

sh.close()

HITCONCTF

HITCON比赛的时候正好还因为高校密码挑战赛在西安旅游，看的几个题都是最喜欢的maple的题目，发现有几个trick和我之前出的题目都蛮接近σ(´∀｀*)，但只能拿着手机云一下比赛，实操都交给了rec和dbt他们，现在回家了就来写写wp。

BabyLWE

题目

题目描述：

1	Simple and straightforward LWE challenge!

题目：

import os
from hashlib import sha256
from random import SystemRandom

from Crypto.Cipher import AES
from sage.all import *

flag = os.environb.get(b"FLAG", b"flag{test_flag}")


n = 64
m = 200
p = 1048583
F = GF(p)

random = SystemRandom()
errs = random.sample(range(p), 3)
A = matrix(F, [[random.randrange(0, p - 1) for _ in range(n)] for _ in range(m)])
s = vector(F, [random.randrange(0, p - 1) for _ in range(n)])
e = vector(F, [random.choice(errs) for _ in range(m)])
b = A * s + e

key = sha256(str(s).encode()).digest()[:24]
aes = AES.new(key[:16], AES.MODE_CTR, nonce=key[-8:])
ct = aes.encrypt(flag)

print(f"A = {A.list()}")
print(f"b = {b.list()}")
print(f"{ct = }")

题目基于$m=200, n=64, p=1048583$的LWE，唯一区别在于错误向量$\mathbf{e}$的每个分量$e_i$均从给定的集合$E$中取值，而$E$由三个未知的$GF(p)$下的随机数组成，给出$A,\mathbf{b}$，要求还原私钥$\mathbf{s}$，从而解AES得到flag。

思路

前置

这题其实和之前我出的easy_mod_α很像，mod_α这一道题$E$的取值集合仅由两个未知的$GF(p)$下的随机数组成，而二元的error有一个性质，那就是一定存在线性变换$\mathbf{y} = k\mathbf{x} + t\cdot \mathbf{1}$，使得：

$(0,1) = k\mathbf{e} + t\cdot \mathbf{1} \quad(mod\;p)$

$\mathbf{1}$代表对应长度的全1向量

虽然不知道集合$E$的具体取值就没法显式找出$a,b$，但由于找$a,b$的过程本身也是规约的过程，所以我们完全可以将两步合并在一起。因此在当时的wp中构造了一个$(m+2, m+2)$的格，去规约出$(e’_1, e’_2, \cdots, e’_m, k, t)$，由于映射后的$e’_i$都是0或1，而$k,t$是$GF(p)$下的随机数，因此还要配下平才行。

而这个格其实并不好，这一点在当时wp里也有提到：

而实现这一点优化其实并不难，由于在$GF(p)$下有：

$M = \left(\begin{matrix} A \\ \mathbf{b} \\ \mathbf{1} \end{matrix}\right)_{n+2, m} \quad \Rightarrow \quad (-k\mathbf{s}, k, t)M = \mathbf{e}' \;, \; e'_i \in \{0, 1\}$

所以利用该线性关系去构造最终的$(m, m)$的格$L$即可。

题目思路

回到这个题来，对于三元error来说其映射到$(-1, 0, 1)$这样好的$\mathbf{e}’$概率很低，然而依然肯定存在线性变换$\mathbf{y} = k\mathbf{x} + t\cdot \mathbf{1}$，使得他映射到一个最短的$\mathbf{e}’$(为什么以及怎么找可以参考另一道题easy_mod_X)，因此做法其实没区别。

唯一的细节在于，$\mathbf{1}$是存在于我们的格中的，在二元的情况下由于$\mathbf{e}’$都是01，因此目标向量比这个短，所以规约后取第一行，而对于二元以上则应该取规约后的第二行才是$\mathbf{e}’$。

exp

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5

A = 
b = 
ct = 

p = 1048583
m, n = 200, 64
A = Matrix(Zmod(p), m, n, A)
b = vector(Zmod(p), b)

def primal_attack_binary_error(A,b,m,p):
    M = block_matrix(Zmod(p), [
        [A.T],
        [matrix(ZZ, b)],
        [matrix(ZZ, [1]*m)]
    ])

    M1, M2 = M[:, :M.nrows()], M[:, M.nrows():]
    
    L = block_matrix(ZZ, [
        [1, M1^(-1)*M2],
        [0, p]
    ])
    X = L.BKZ(block_size=20, fp="ld")
    print(X[:10])
    Y = Matrix(ZZ, X) * Matrix(ZZ, L)^(-1) # X = Y*L
    Y = Matrix(ZZ, Y)

    k, t = (Y[:M.nrows(), :M.nrows()] * M1^(-1))[1][-2:]
    e = (X[1] - vector(Zmod(p), [t]*m)) * inverse(k, p)
    
    return e

nums = m
e2 = primal_attack_binary_error(A, b, m, p)

s = A[:nums].solve_right(b[:nums]-e2[:nums])

from hashlib import sha256
from Crypto.Cipher import AES

key = sha256(str(s).encode()).digest()[:24]
aes = AES.new(key[:16], AES.MODE_CTR, nonce=key[-8:])
flag = aes.decrypt(ct)
print(flag)

#hitcon{why_does_not_hiding_the_set_of_errors_help_QAQ}

MRSA

题目

题目描述：

1	An obvious generalization of RSA, what could go wrong?

题目：

from sage.all import *
from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
import os


flag = os.environb.get(b"FLAG", b"flag{test_flag}")

n = getPrime(1024) * getPrime(1024)
k = 16
e = 65537

key = os.urandom(k * k)
M = matrix(Zmod(n), k, k, key)
C = M**e

aes = AES.new(key[:32], AES.MODE_CTR, nonce=key[-8:])
ct = aes.encrypt(flag)

print(f"C = {C.list()}")
print(f"{ct = }")

题目生成2048bit的公钥$n$，然后生成256字节的密钥并编码到$(16,16)$的矩阵$M$，并计算密文$C = M^e$，仅给出$C$，要求还原$M$从而得到key来解AES得到flag。

思路

和matrix9_v2类似，这一题最核心的trick是矩阵可交换，也就是在$Z_n$下会有$MC = CM$，因此一旦有$n$就可以如法炮制展平后LLL，从而得到$M$。

应该说得到$M-kI$，因为$I$为$CX = XC$这一方程的平凡解，因此展平的$M$会和$I$产生一定程度的约简

而本题没有给出公钥$n$，要想办法拿到他才行，对可交换方程进行移项可以得到：

$CM - MC = O \quad (mod\;n)$

我们将该方程的$O$从$Z_n$展开到$Z$下，那么$O$中的每个值均为$k_in$的形式。而由于$C$内部的值均在$n$的数量级，而$M$的每个值都在8bit内，因此$k_i$最多也就12、13bit左右，是很小的。因此对于$O$中的任意一个位置的分量，我们能提取出一条包含几个小量的线性等式，如：

$\left(\begin{matrix} {\color{red}c_{1,1}} & {\color{red}c_{1,2}} & &{\color{red}c_{1,16}}\\ c_{2,1} & c_{2, 2}& & c_{2,16}\\ && \ddots &\\ c_{16,1} & c_{16, 2}& & c_{16,16}\\ \end{matrix} \right) \left(\begin{matrix} {\color{red}m_{1,1}} & m_{1,2}& & m_{1,16}\\ {\color{red}m_{2,1}} & m_{2,2}& & m_{2,16}\\ && \ddots &\\ {\color{red}m_{16,1}} & m_{16,2}& & m_{16,16}\\ \end{matrix} \right) - \left(\begin{matrix} {\color{red}m_{1,1}} & {\color{red}m_{1,2}} & &{\color{red}m_{1,16}}\\ m_{2,1} & m_{2, 2}& & m_{2,16}\\ && \ddots &\\ m_{16,1} & m_{16, 2}& & m_{16,16}\\ \end{matrix} \right) \left(\begin{matrix} {\color{red}c_{1,1}} & c_{1,2}& & c_{1,16}\\ {\color{red}c_{2,1}} & c_{2,2}& & c_{2,16}\\ && \ddots &\\ {\color{red}c_{16,1}} & c_{16,2}& & c_{16,16}\\ \end{matrix} \right) = \left(\begin{matrix} {\color{red}k_{1,1}n} & k_{1,2}n & & k_{1,16}n\\ k_{2,1}n & k_{2,2}n & & k_{2,16}n \\ && \ddots &\\ k_{16,1}n & k_{16,2}n & & k_{16,16}n\\ \end{matrix} \right)$

而之所以不能对该线性等式进行规约是因为不知道$n$，而消去$n$很简单，我们只需要再取一条线性等式消元即可，此时等式就仅仅由$m_{i,j},k_{i,j}$等小量组成，进行一次规约就可以拿到这些小量，也就得到了$n$，之后用matrix9_v2的展平LLL即可。

一个小的实现问题在于sage并没有实现模合数下矩阵的高斯消元，因此还要手动实现一下(这一部分当然是交给AI做XD)。

但这样看的话由于$n$有点大了，其实不如逐行求解快

exp

C = 
ct = 

from Crypto.Util.number import *
from itertools import *
from Crypto.Cipher import AES

k = 16
e = 65537
C = Matrix(ZZ, k, k, C)

L = block_matrix(ZZ, [
    [1, 2^100*Matrix(ZZ, C[:1, :].list() + [_*(-1) for _ in C[:, :1].list()] + C[:, 1:2].list()).T],
])
L = L.LLL()
res = L[2][k+1:2*k]
k1 = gcd(res)
m1 = list(map(abs, [_//k1 for _ in res]))

CT = C.T
L = block_matrix(ZZ, [
    [1, 2^100*Matrix(ZZ, CT[:1, :].list() + [_*(-1) for _ in CT[:, :1].list()] + CT[:, 1:2].list()).T],
])
L = L.LLL()
res = L[2][k+1:2*k]
k1 = gcd(res)
m11 = list(map(abs, [_//k1 for _ in res]))

###############################################################################
L = block_matrix(ZZ, [
    [1, 2^100*Matrix(ZZ, C[1:2, :].list() + [_*(-1) for _ in C[:, :1].list()] + C[:, 1:2].list()).T],
])
L = L.LLL()
res = [L[2][k]] + L[2][k+2:2*k].list()
k1 = gcd(res)
m2 = list(map(abs, [_//k1 for _ in res]))

CT = C.T
L = block_matrix(ZZ, [
    [1, 2^100*Matrix(ZZ, CT[1:2, :].list() + [_*(-1) for _ in CT[:, :1].list()] + CT[:, 1:2].list()).T],
])
L = L.LLL()
res = [L[2][k]] + L[2][k+2:2*k].list()
k1 = gcd(res)
m21 = list(map(abs, [_//k1 for _ in res]))


for _ in product(range(256), repeat=2):
    i, j = _
    m1_ = vector(ZZ, [i] + m1)
    m1__ = vector(ZZ, [i] + m11)
    m2_ = vector(ZZ, [m2[0]] + [j] + m2[1:])
    m2__ = vector(ZZ, [m21[0]] + [j] + m21[1:])
    n = GCD(m1_*vector(ZZ, C[:, :1].list()) - m1__*vector(ZZ, C[:1, :].list()), m2_*vector(ZZ, C[:, 1:2].list()) - m2__*vector(ZZ, C[1:2, :].list()))
    if(n > 2^2040):
        for t in range(2, 2000):
            while(n % t == 0):
                n //= t
        break

def gaussian_elimination(A):
    R = A.base_ring()
    n = R.cardinality()
    M = A
    nrows, ncols = M.nrows(), M.ncols()
    pivot_row = 0

    for j in range(ncols): 
        if pivot_row >= nrows:
            break

        pivot_candidate_row = -1
        for i in range(pivot_row, nrows):
            if M[i, j] != 0:
                pivot_candidate_row = i
                break
        
        if pivot_candidate_row == -1:
            continue
        M.swap_rows(pivot_row, pivot_candidate_row)
        pivot_val = M[pivot_row, j]
        g, inv, _ = xgcd(Integer(pivot_val), n)
        
        M.rescale_row(pivot_row, R(inv))

        for i in range(nrows):
            if i != pivot_row:
                M.add_multiple_of_row(i, pivot_row, -M[i, j])

        pivot_row += 1

    return M

L = Matrix(Zmod(n), k^2, k^2)

for i in range(k):
    for j in range(k):
        for t in range(k):
            L[k*i+j, k*i+t] += C[t,j]
            L[k*i+j, j+k*t] -= C[i,t]
L = gaussian_elimination(L)[:k^2-k].T

L = Matrix(Zmod(n), L)
M1, M2 = L[:k], L[k:]
M = block_matrix(ZZ, [
    [1, M1*M2^(-1)],
    [0, n]
])

from re import findall
from subprocess import check_output

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

M = flatter(M)

v = vector(ZZ, M[0])
MM = vector(ZZ, M[1])
for i in range(-512, 512):
    key = list(map(abs, (i*v + MM).list()))
    if(all([0 <= j < 256 for j in key])):
        key = bytes(key)
        aes = AES.new(key[:32], AES.MODE_CTR, nonce=key[-8:])
        flag = aes.decrypt(ct)
        if(b"hitcon" in flag):
            print(flag)


#hitcon{neither_e_nor_n_matters_here_lol}

pedantic

题目

题目描述：

1	You can never be too pedantic!

题目：

#!/usr/bin/env python3
import hashlib
import json
import os
import secrets

from fastecdsa.curve import secp256k1
from fastecdsa.point import Point

p = secp256k1.p
q = secp256k1.q
G = secp256k1.G
field_bytes = (p.bit_length() + 7) // 8
scalar_bytes = (q.bit_length() + 7) // 8


def encode_point(pt: Point):
    return pt.x.to_bytes(field_bytes, "big") + pt.y.to_bytes(field_bytes, "big")


def decode_point(data: bytes):
    if len(data) != 2 * field_bytes:
        raise ValueError("Invalid point encoding")
    x = int.from_bytes(data[:field_bytes], "big")
    y = int.from_bytes(data[field_bytes:], "big")
    return Point(x, y, secp256k1)


def hash_point(pt: Point):
    h = hashlib.sha256(encode_point(pt)).digest()
    return int.from_bytes(h, "big") % q


def hash_points_to_scalars(pts: list[Point], n: int):
    s = sum([hash_point(pt) for pt in pts]) % q
    ret = []
    for _ in range(n):
        ret.append(s)
        s = (1337 * s + 7331) % q
    return ret


ProofType = list[tuple[Point, int]]


def prove(x: int, n: int) -> ProofType:
    rs = [secrets.randbelow(q) for _ in range(n)]
    Grs = [G * r for r in rs]
    cs = hash_points_to_scalars(Grs, n)
    zs = [(r + c * x) % q for r, c in zip(rs, cs)]
    return list(zip(Grs, zs))


def verify(Y: Point, proof: ProofType):
    Grs, zs = zip(*proof)
    n = len(Grs)
    cs = hash_points_to_scalars(Grs, n)
    return all(G * z == Gr + Y * c for Gr, z, c in zip(Grs, zs, cs)) * n


def serialize_proof(proof: ProofType):
    return json.dumps([(encode_point(pt).hex(), z) for pt, z in proof])


def deserialize_proof(s: str) -> ProofType:
    return [(decode_point(bytes.fromhex(pt)), z) for pt, z in json.loads(s)]


def main():
    flag = os.environ.get("FLAG", "flag{test}")

    sk = int.from_bytes(hashlib.sha256(flag.encode()).digest(), "big") % q
    pk = G * sk

    print("Hey, I know the flag!")
    proof = prove(sk, 10)
    assert verify(pk, proof) == 10, "wtf"
    print("Here is the proof:")
    print(serialize_proof(proof))
    print("Do you know it too?")
    proof = deserialize_proof(input("proof:"))
    n = verify(pk, proof)
    if n >= 42:
        print("I am convined :D")
        print(f"Here is it: {flag}")
    elif n > 0:
        print("Hmm, not sure about that... :thinking:")
    else:
        print("I think you don't :(")


if __name__ == "__main__":
    main()

题目是基于secp256k1曲线的ZKP，靶机会给一个$n=10$的proof，需要给出一个$n>=42$的proof通过verify，从而拿到flag。题目的verify主要操作是：

$z_i \cdot G == Gr_i + c_i \cdot Y$

其中$z_i, Gr_i$都是可以自己输入的，$Y$为公钥，满足$Y = x\cdot G$，$x$是私钥。

$c_i$通过输入的点列表$Grs$算出，具体计算过程主要是这段代码：

def hash_point(pt: Point):
    h = hashlib.sha256(encode_point(pt)).digest()
    return int.from_bytes(h, "big") % q

def hash_points_to_scalars(pts: list[Point], n: int):
    s = sum([hash_point(pt) for pt in pts]) % q
    ret = []
    for _ in range(n):
        ret.append(s)
        s = (1337 * s + 7331) % q
    return ret

ProofType = list[tuple[Point, int]]

def prove(x: int, n: int) -> ProofType:
    rs = [secrets.randbelow(q) for _ in range(n)]
    Grs = [G * r for r in rs]
    cs = hash_points_to_scalars(Grs, n)
    zs = [(r + c * x) % q for r, c in zip(rs, cs)]
    return list(zip(Grs, zs))

也就是把$Grs$中每个点的sha256值加起来得到初始值$s$，然后用$s = 1337s+7331$迭代直至生成长为$n$的列表，也就是$c$。

思路

这个题赛中早早被dbt他们做掉了，后面剩最后一题paranoid的时候就来看了看前置题，所以这里就顺便写写思路。

思路也很容易，由于这里$c_i$是一个存在不动点的LCG迭代，因此如果控制初始$s$为不动点，就可以得到一个长为$n$的全部一样的列表$c$。而此时假设每一次都随便输入$z_i$，就能通过$Gr_i = s \cdot Y - z_i \cdot G$算出一个对应的$Gr_i$。

现在就只剩下一个问题：如何组合这些$Gr_i$，能够使他们的sha256的和为不动点$s$，而这个问题用LLL找一组比较短的正整数解就解决了，偷懒就不写exp。

LILCTF

Space Travel

题目

题目描述：

Jump up!

题目：

from Crypto.Cipher import AES
from hashlib import md5
from params import vecs
from os import urandom

key = int("".join([vecs[int.from_bytes(urandom(2)) & 0xfff] for _ in range(50)]), 2)

print("🎁 :", [[nonce := int(urandom(50*2).hex(), 16), (bin(nonce & key).count("1")) % 2] for _ in range(600)])
print("🚩 :", AES.new(key=md5(str(key).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).encrypt(open("flag.txt", "rb").read()))

params.py里的vecs其实还很重要，但是由于真的太长所以就不放了TT

题目给定一个长4096的列表，其中元素均为长16的01串，在其中随机抽取50个组成长为800的01串key，并且给出600组关于key的$GF(2)$下的线性等式，要求解出key。

思路

题目对应的情境为$GF(2)$下800个变量，600个等式的线性系统求解，直接求解的话显然是欠定的，会有200维的解空间。因此要想办法利用key中每16维的特殊选取空间vecs的结构对该解空间进行压缩。

观察vecs发现其长度4096正好对应2的12次幂，因此可以预想到其张成的空间并不是16维的，如果是12维的子空间就可以唯一求解出key。

此时将vecs拼成矩阵可以发现其秩为13，离预想的还差一维，也就是还剩余50维的解空间，但由于题目是用key的md5去AES加密，因此没有MITM之类的结构，所以唯一的方法就是在这个基础上把这一维降掉。

而检查vecs之间的差分可以发现，与同一向量做差后拼起来的矩阵秩就只有12，说明vecs是由一个12维的空间经历了一个12到16的仿射变换得到的，因此可以唯一求解出key。

exp

from Crypto.Cipher import AES
from hashlib import md5

vecs = 
gift = 
enc = 

vecs_bin = [list(map(int, i)) for i in vecs]
vecs_bin = [vector(GF(2), i) for i in vecs_bin]

nonce_bin = [list(map(int, bin(i[0])[2:].zfill(800))) for i in gift]
nonce_bin = [vector(GF(2), i) for i in nonce_bin]

A = Matrix(GF(2), nonce_bin).T
b = vector(GF(2), [i[1] for i in gift])

v0 = vecs_bin[0]
L = Matrix(GF(2), [i - v0 for i in vecs_bin[1:]])
L1 = L.echelon_form()[:12]

v0_ = vector(GF(2), v0.list()*50)
L1_ = block_diagonal_matrix([L1 for _ in range(50)])
x = (L1_*A).solve_left(b - v0_*A)

x_ = [(vector(GF(2), x.list()[12*j:12*j+12])*L1+v0).list() for j in range(50)]
key = ""
for i in x_:
    for j in i:
        key += str(j)
        
key = int(key, 2)
flag = AES.new(key=md5(str(key).encode()).digest(), nonce=b"Tiffany", mode=AES.MODE_CTR).decrypt(enc)
print(flag)


#LILCTF{Un1qUe_s0luti0n_1N_sUbSp4C3!}

其他

这个比赛友情援助了一道题目，当时看比赛主要面向学了一年的师傅，就比较纠结到底出个什么能够简单一点的同时又比较有趣，最后就搞了这样一道题目出来。题目的灵感来源是NKCTF 2024里lem0出的EZ_random(NKCTF没仓库，都找不到链接TT)，这个题目与本题目很像：

key有512bit，但是只有关于key的448个$GF(2)$上的方程
通过观察可以知道，key的每个字节的奇偶性是交替的

而由于汉明重量为奇、汉明重量为偶的所有向量其实分别张成了一个7维的子空间，但是这个7到8维的仿射变换非常的隐蔽，这样的题目设置就使得仿射子空间的结构嵌入精巧了很多，当时的唯一解来自@tl2cents的非预期。

当时赛后和lem0、rec他们讨论了一下，从编码的角度来讲，其实可以设置任意的从$m$维到$n$维的仿射子空间，于是就有了这个题目，但是要找到像汉明重量奇偶向量这种结构精巧的子空间很难，所以只能直接给出该空间仿射变换后的所有向量。此时直接看vecs的列表长度$2^{12}$就能看出来意图，比EZ_random的题目容易很多，但是就显得并不精巧:(

由于只涉及线性代数的知识，所以最开始想的是即使对学了远不到一年、甚至是刚刚了解密码学的师傅，只要有学到线代那么就有机会完成这道题目。但最终的解数依然比预想多不少，一方面是来打的师傅确实很多，另一方面是没料到AI真的就可以一眼看破题目的仿射子空间设置，虽然题目本身很容易并且方向明确，但是这代表着想出代码简短易读、不设混淆的题目越来越难了。

很难想象之后需要多么巧妙的idea才能出出来AI做不出来的短题目，感觉没好trick只能被迫套娃混淆AI视线( ´•̥̥̥ω•̥̥̥` )

NSSCTF 4th

LeetSpe4k

题目

题目描述：

1	LeetSpe4k!

题目：

from functools import reduce
from random import choice
from secret import flag

le4t = lambda x: "".join(choice(next((j for j in ['a@4A', 'b8B', 'cC', 'dD', 'e3E', 'fF', 'g9G', 'hH', 'iI', 'jJ', 'kK', 'l1L', 'mM', 'nN', 'o0O', 'pP', 'qQ', 'rR', 's$5S', 't7T', 'uU', 'vV', 'wW', 'xX', 'yY', 'z2Z'] if i in j), i)) for i in x.decode())
h4sH = lambda x: reduce(lambda acc, i: ((acc * (2**255+95)) % 2**256) + i, x, 0)

print(le4t(flag), h4sH(flag))
#nSsCtf{H@pPy_A7h_4nNiv3R$arY_ns$C7F_@nD_l3t$_d0_7h3_LllE3t$pEAk!} 9114319649335272435156391225321827082199770146054215376559826851511551461403

这次周年赛又来出题玩，呼朋唤友和@hashhash，@yolbby，@shikaku一人出了一道，这里写下我自己这道的解法。

有空来补