散题(1)

以后一些我觉得比较有趣的题的WP都会放到“散题”栏目里面

NepCTF 2025 | Lattice Bros

#已知α的极小多项式为三次多项式f(x),即f(α)=0,且α≈54236.606188881754809671280151541781895183337725393
#上述极小多项式的常数项为a0

from secret import a0,alpha
import gmpy2
from Crypto.Util.number import long_to_bytes
import random
from math import sqrt,log2

d=981020902672546902438782010902608140583199504862558032616415
p = d - a0

k=sqrt(log2(p))+log2(log2(p))
B = 2**30
assert B < p/2**k

m = 30
assert m > 2*sqrt(log2(p))

samples = []
betas = []

f = open("samples.txt",'w')
for _ in range(m):
    t = random.randint(1, p-1)
    beta = random.randint(-B + 1, B - 1)
    a = (t * alpha - beta) % p
    samples.append((t, a))
    betas.append(beta)

f.write(str(samples))

for i in range(0,30):
    assert (betas[i]-samples[i][0]*alpha+samples[i][1])%p == 0

#flag = long_to_bytes(alpha)

观察对flag的加密可以得知这是一个HNP，在求解HNP之前我们需要先知道p，由题可知$p=d-a_0$，且$a_0$是$\alpha\approx54236.6061888\cdots$的三次极小多项式的常数项，参考A Gentle Tutorial for Lattice-Based Cryptanalysis的3.6可以知道如果我们要求该极小多项式，可以构造如下格：

$$\pmb{B}=\left(\begin{matrix} 10^{45}& 1&0&0\\ \lfloor10^{45}\alpha\rfloor&0&1&0\\ \lfloor10^{45}\alpha^2\rfloor&0&0&1\\ \lfloor10^{45}\alpha^3\rfloor&0&0&0 \end{matrix}\right)$$

上述矩阵中第一列乘上的系数$10^{45}$是依照题目给出的$\alpha$的近似值精度选取的，对于该格基，有：

$$(a_0, a_1, a_2, a_3)\pmb{B}=\left(\sum_{i=0}^{3}\lfloor10^{45}a_i\alpha^{i}\rfloor, a_0, a_1,a_2\right)$$

根据A Gentle Tutorial for Lattice-Based Cryptanalysis之3.6节所述可以知道直接对$\pmb{B}$进行规约即可得到目标向量，从而恢复出$a_0$：

alpha = RealField(200)(54236.606188881754809671280151541781895183337725393)
N = 10^45

L = matrix(ZZ, [[floor(N), 1, 0, 0], [floor(N * alpha), 0, 1, 0], [floor(N * alpha^2), 0, 0, 1], [floor(N * alpha^3), 0, 0, 0]])
res = L.LLL()[0]
a0 = res[1]
print(res)

# 重新求根验证
R.<x> = RealField(1000)[]
f = res[1] + res[2] * x + res[3] * x^2 + x^3
eps = f.roots()[0][0] - alpha

求出$p$之后尝试直接构造如下格进行规约求解：

$$\pmb{B}_{HNP}=\left(\begin{matrix} p&&&&&\\ &p&&&&\\ &&\ddots&&&\\ &&&p&&\\ t_1&t_2&\cdots&t_m&\frac{B}{p}&\\ a_1&a_2&\cdots&a_m&&B \end{matrix}\right)$$

发现无法规约出想要的$\alpha$（与求极小多项式时的$\alpha$不同），可能是$\alpha$比较大，这个格难以直接规约出我们想要的目标向量，可能需要进行一次配平，但是我们不知道$\alpha$的具体大小，无法计算出具体的配平系数，故尝试添加一个未知的配平系数进行爆破，得到如下格：

$$\pmb{B}_{HNP}'=\left(\begin{matrix} p&&&&&\\ &p&&&&\\ &&\ddots&&&\\ &&&p&&\\ t_1&t_2&\cdots&t_m&\frac{2^{k}B}{p}&\\ a_1&a_2&\cdots&a_m&&B \end{matrix}\right)$$

测试发现当$k=2$的时候可以得到flag：

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

samples = [...]

alpha = RealField(200)(54236.606188881754809671280151541781895183337725393)
N = 10^45

L = matrix(ZZ, [[floor(N), 1, 0, 0], [floor(N * alpha), 0, 1, 0], [floor(N * alpha^2), 0, 0, 1], [floor(N * alpha^3), 0, 0, 0]])
res = L.LLL()[0]
a0 = res[1]
print(res)

# 重新求根验证
R.<x> = RealField(1000)[]
f = res[1] + res[2] * x + res[3] * x^2 + x^3
eps = f.roots()[0][0] - alpha

assert abs(eps) < 1/N

n = 30
d = 981020902672546902438782010902608140583199504862558032616415

B = 2^30
p = d - a0

def solve(k):
    L = matrix(QQ, n+2, n+2)

    for i in range(n):
        t, a = samples[i]
        L[i, i] = p
        L[-2, i] = -t
        L[-1, i] = a
    L[-2, -2] = (B * 2^k) / p
    L[-1, -1] = B
    res = L.LLL()[1]

    betas = res[:-2]
    alpha = int(abs(res[-2] * p)) // (B * 2^k)

    flag = long_to_bytes(alpha)
    if b'NepCTF' in flag:
        return flag
    return None

for i in trange(1000):
    try:
        if solve(i):
            print(solve(i))
            break
    except:
        pass

补充

后来看了一下SeanDictionary师傅的wp（NepCTF 2025 - SeanDictionary | 折腾日记）才知道原来对格：

$$\pmb{B}_{HNP}=\left(\begin{matrix} p&&&&&\\ &p&&&&\\ &&\ddots&&&\\ &&&p&&\\ t_1&t_2&\cdots&t_m&\frac{B}{p}&\\ a_1&a_2&\cdots&a_m&&B \end{matrix}\right)$$

直接规约之后得到的$\alpha$只需要在模$p$下取相反数就能得到flag（学到了>ω<）：

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

samples = [...]

alpha = RealField(200)(54236.606188881754809671280151541781895183337725393)
N = 10^45

alpha = RealField(200)(54236.606188881754809671280151541781895183337725393)
N = 10^45

L = matrix(ZZ, [[floor(N), 1, 0, 0], [floor(N * alpha), 0, 1, 0], [floor(N * alpha^2), 0, 0, 1], [floor(N * alpha^3), 0, 0, 0]])
res = L.LLL()[0]
a0 = res[1]
print(res)

# 重新求根验证
R.<x> = RealField(1000)[]
f = res[1] + res[2] * x + res[3] * x^2 + x^3
eps = f.roots()[0][0] - alpha

assert abs(eps) < 1/N

n = 30
d = 981020902672546902438782010902608140583199504862558032616415

B = 2^30
p = d - a0

L = matrix(QQ, n+2, n+2)

for i in range(n):
    t, a = samples[i]
    L[i, i] = p
    L[-2, i] = -t
    L[-1, i] = a
L[-2, -2] = B / p
L[-1, -1] = B

res = L.LLL()[1]
betas = res[:-2]
alpha = (p - int(abs(res[-2] * p)) // B) % p

flag = long_to_bytes(alpha)
print(flag)

NepCTF 2025 | ezRSA2

from Crypto.Util.number import getStrongPrime, getRandomNBitInteger, GCD, inverse, long_to_bytes, bytes_to_long, sieve_base  
from flag import flag  
  
def gen_parameters(gamma=0.33, beta=0.33):  
    p = getStrongPrime(1024)  
    q = getStrongPrime(1024)  
    N = p*q  
    phi = (p-1)*(q-1)  
    while True:  
        d = getRandomNBitInteger(int(2048*beta))  
        if GCD(d, phi) == 1:  
            break  
    e = inverse(d, phi)  
      
    hints = []  
    M = 1  
    for i in range(1, len(sieve_base)):  
        li = sieve_base[i]  
        hints.append(d%li)  
        M *= li  
        if M.bit_length() >= 1024*gamma:  
            break  
    return e, N, hints  
  
  
  
def main():  
    e,N,hints = gen_parameters()  
    print(f'e={hex(e)}')  
    print(f'N={hex(N)}\n')  
    print(f'hints={hints}\n')  
      
    flag_prefix = b'NepCTF{'  
    assert flag.startswith(flag_prefix)  
    assert flag.endswith(b'}')  
      
    pt = bytes_to_long(flag[len(flag_prefix):-1])  
    ct = pow(pt, e, N)  
    print(f'ct={hex(ct)}')  
      
main()  
  
  
"""  
e=...  
N=...  
  
hints=[...]  
  
ct=...
"""

根据参数生成函数可以知道本题中使用的$d<N^{\frac{1}{3}}$（大约是675 bits），显然私钥比较小，但是还是大于维纳攻击（$d<N^{0.25}$）以及Boneh&Durfee攻击的边界（$d<N^{0.292}$）的，题中还给出了：

$$\begin{cases} hint_0\equiv d\pmod{p_2}\\ hint_1\equiv d\pmod{p_3}\\ \cdots\\ hint_{r}\equiv d\pmod{p_{r+2}}\\ \end{cases}$$

其中$p_i$为第$i$个质数，令$M=\prod_{i=2}^{r+2}p_{i}$，则可以通过CRT还原出$d_0=d\mod{M}$，也就是$d_0=d-lM$（$l\ge0$）.因为$d<N^{\frac{1}{3}}$还算是比较小的，而且我们已经知道$d$的大小约为$N^{\frac{1}{6}}$的部分了，所以可以考虑用类似于维纳攻击的方法来求解这道题，因为$ed-k\varphi(N)=1$，那么可以得到：

$$e(d_0+lM)-k(N-p-q+1)=1$$

令$s=1-p-q$，则有：

$$ed_0+eMl-kN=ks+1$$

于是构造格：

$$\pmb{B}=\left(\begin{matrix} 1&0&ed_0\\ 0&1&eM\\ 0&0&-N \end{matrix}\right)$$

预期有$(1, l, k)\pmb{B}=(1, l, ks+1)$，由$ed-k\varphi(N)=1$可以知道$k\approx2^{675},l\approx2^{333}$有$\det(\pmb{B})=N$，$||(1, l, ks+1)||\approx 2^{675+1024}=2^{1699}$，显然有：

$$||(1, l, ks+1)||>\sqrt{3}N^{1/3}$$

故需要进行配平，粗略计算可以得到如下格：

$$\pmb{B}'=\left(\begin{matrix} 2^{1699}&0&ed_0\\ 0&2^{1366}&eM\\ 0&0&-N \end{matrix}\right)$$

此时进行规约就可以得到目标向量$(2^{1699}, 2^{1366}l, ks+1)$，从而可以计算出$d=d_0+lM$进行解密得到flag了：

from Crypto.Util.number import *
from sympy import prod
from tqdm import trange

e = ...
N = ...
ct = ...

hints = [1, 3, 0, 3, 9, 16, 10, 14, 5, 11, 21, 18, 30, 30, 38, 2, 20, 62, 66, 1, 22, 56, 41, 13, 78, 59, 51, 6, 57, 117, 73, 75, 96, 112, 50, 93, 158, 97, 146, 8, 65, 96, 186, 161, 90, 131, 46, 32, 140, 133, 50, 43, 151, 234]
mod = [sieve_base[i] for i in range(1, len(hints) + 1)]
M = prod(mod)

d0 = crt(hints, mod)

L = matrix(ZZ, [[2^1699, 0, e*d0], [0, 2^1366, e*M], [0, 0, -N]])

d = ZZ(abs(L.LLL()[0][1] // 2^1366) * M + d0)

assert d.bit_length() == floor(2048 * .33)

m = pow(ct, d, N)
flag = long_to_bytes(m)
print(flag)

DeadSec CTF 2025 | imrul kAES

#!/usr/local/bin/python  
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime  
from Crypto.Util.Padding import pad  
from Crypto.Random import get_random_bytes  
from Crypto.Cipher import AES  
  
print('Yo welcome to my sign as a service...')  
  
p, q = getPrime(512), getPrime(512)  
e = 12389231641983877009741841713701317189420787527171545487350619433744301520682298136425919859970313849150196317044388637723151690904279767516595936892361663  
n = p * q  
d = pow(e, -1, (p - 1) * (q - 1))  
  
k = get_random_bytes(16)  
cipher = AES.new(k, AES.MODE_ECB)  
  
flag = open('flag.txt', 'rb').read()  
assert len(flag) <= 50  
ct = pow(bytes_to_long(flag), e, n)  
  
print(ct)  
  
while 1:  
    try:  
       i = int(input("Enter message to sign: "))  
       assert(0 < i < n)  
       print(cipher.encrypt(pad(long_to_bytes(pow(i, d, n) & ((1<<512) - 1)), 16)).hex())  
    except:  
       print("bad input, exiting")

一道比较折磨的题，观察服务端代码可以看到对于每一次连接，代码都会生成一个模数$n=pq$，并计算$d\equiv e^{-1}\pmod{\varphi(n)}$，然后对flag进行RSA加密，之后用户可以进行无数次输入，对于每个输入的数据$i$，程序会将其使用前面计算出的RSA私钥进行解密，然后与$2^{512}-1$相与，最终转换成bytes，再进行AES加密（密钥是随机的16字节，无法爆破）.

可以知道，对于输入的数据$i$，计算$i^{d}\mod{n}$之后与$2^{512}-1$相与，实际上就是取$i^{d}\mod{n}$转换得到的字符串的后$512\div8=64$字节，既然存在这种关系，且我们又已知RSA加密flag（设为$pt$）后得到的密文$ct$，那么我们就可以让输入的$i$解密后的内容是flag + k * b'\x00'，实际上就是让：

$$i\equiv (2^{8k}pt)^e\equiv2^{8ke}ct\pmod{n}$$

那么就可以通过控制$k$的大小，从后向前通过类似Padding Oracle Attack的方式来爆破flag，但是在进行攻击操作之前我们需要知道$n$的具体数值，由输入部分的代码可以知道，如果我们输入的$i$不在$(0, n)$的区间内，尽管它会显示bad input, exiting，但是程序并不会真的退出，那么我们可以通过二分的方式来爆破出$n$（大概率需要爆破1024次），在获得$n$之后，我们就可以通过类似Padding Oracle Attack的方式来逐字恢复flag了：

from Crypto.Util.number import *  
from pwn import *  
from Crypto.Util.Padding import pad  
from tqdm import trange  
from string import printable  
  
e = 12389231641983877009741841713701317189420787527171545487350619433744301520682298136425919859970313849150196317044388637723151690904279767516595936892361663  
io = remote("ip", port)  
  
io.recvline()  
ct = int(io.recvline().decode())  
log.success(f"Got ciphertext: {ct}")  
  
l = 1  
r = 2**1024  

# 二分法爆破n
while l < r:  
    m = (l + r) // 2  
    io.sendlineafter(b'Enter message to sign: ', str(m).encode())  
    res = io.recvline()  
    if b'bad input, exiting' in res:  
        r = m  
    else:  
        l = m + 1  
    log.info(f'{r - l = }')  
log.success(f"Found n: {l}")  
n = l  

# Padding Oracle Attack还原flag
flag = ""  
for i in trange(1, 512 // 8):  
    isUpdate = False  
    c0 = pow(2**(512 - 8 * i), e, n)  
    c = ct * c0 % n  
  
    io.sendlineafter(b'Enter message to sign: ', str(c).encode())  
    data = io.recvline().decode()  
  
    for c in printable:  
        tmp = c + flag + '\x00' * (64 - len(flag) - 1)  
        tmp_ct = pow(bytes_to_long(tmp.encode()), e, n)  
        io.sendlineafter(b'Enter message to sign: ', str(tmp_ct).encode())  
        res = io.recvline().decode()  
        if res.strip() == data.strip():  
            flag = c + flag  
            log.success(f"Update flag: {flag}")  
            isUpdate = True  
            break  
    if not isUpdate:  
        break  
  
log.success(f"Final flag: {flag}")

在我的电脑上大概20分钟左右就可以爆破出flag：