以后一些我觉得比较有趣的题的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^{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：
