LOADING

加载过慢请开启缓存 浏览器默认开启

NepCTF2025-个人writeup

2025/7/30 CTF CTF Crypto Writeup

NepCTF2025-个人writeup

Crypto

ezRSA2

task.py

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=0x73915608ed64c9cf1a2279684cab4f4a78fba229d45d4f860971a241481363470a19cb0dc0d00f816b5befdaca017cf71483e96ef17b36179012f5194a0e6bf481bb06c2644f74c6812efb65d05c00631f282d6aa55c0bc140a1830b95a1cf4b6024cb0db53f2c2189897c41f22e2eec773723f531ec4bfa537fae6de5fe480cf46fe17850f7eb47df08194d95db3d26ac923b26e110ee645239ab586bbc546ddc5906f280a106edbb727ccb05536b5a3f5c0ebcf865c95ce58be54f7f3547aa53baa218b0dfa98e42d925fa341e45f94a3b16b0c83802660c7f34de3336cb21f219073cf8e9f5e39d47f0a9a9ee7c255f09a6add9a2f7a47960f4a853183d29
N=0xba8956e81394f3f1265ca5d9c4ad1ab0078bb43c4b80a231ab2cc62246ae45f66a562252622aed2cbbfc08647ef2fec0f97a632bf2242845f4b3af0c427cec3d90f42e90278a5a0feeed0922a8cd2278074ac54e9cfc0e96ff68f8d8f266dd87dc1cc59c2895ec884de2022311767f6a9a7e0bd288c79620e28b83bb3c8d8ad1047c839d6ccf5544eaf434a5f00b951769ab3121298d04b63a162757beb3d49917cd0c9e02ee1ac29398c8130961d5a2f2833aba1e538edb7bb97071f40fae543d1622f0c9206c6d4d8abb2ac1b93ebfb603c2f3a909ede357ade4043550fe540d13a4e87db8d731fe130f15a43a1a00364f5da2d87f7b660c3a04e734218a11

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]

ct=0x101b284ad196b5bbd3d3df00a7d3577caeb29c681bdd122582b705afc671febf45d4f3786640e55aadd6a31ecc49175f97b772720f1735f8555f768b137a4643cd6958f80a3dfca4d0270ad463d6dde93429940bd2abb5ad8408b0906fa8d776544a1c50cc0d95939bef4c3fb64d0b52dca81ff0f244fc265bfc0bc147435d05f8f1a146e963a1403b3c123b4d6e73d1fd897109995009be1673212607f0ea7ae33d23f3158448b05c28ea6636382eee9436c4a6c09023ead7182ecd55ac73a68d458d726e1abc208810468591e63f4b4c2c1f3ce27c4800b52f7421ccab432c03e88b3b255740d719e40e0226eabb7633d97ed210e32071e2ac36ed17ef442e
"""

这里可以采用中国剩余定理求出d的低位，设为$d_0$

即

设r=p+q

所以

使用Wiener攻击的格构造思想，这里我们是构造三维格

我们对于规约的目标总是希望它位数小的,所以造格

我们要让v的各个分量位数一致，比如$X_2$,我们的r应该是1025位，根据等式$ed=1+k*phi$测算了一下e是2047位，而d是675位，所以k大概是675位，所以$X_2=2^{1025+675}$,$X_1=2^{1025+675-(675-341)}=2^{1366}$

算了一下$|v|=2^{1701}$,而$det(L)^{\frac{1}{3}}=2^{1716}$

满足海默尔定理

试了一下，X1是要1360才会输出正确字符串

exp

from Crypto.Util.number import *
e=0x73915608ed64c9cf1a2279684cab4f4a78fba229d45d4f860971a241481363470a19cb0dc0d00f816b5befdaca017cf71483e96ef17b36179012f5194a0e6bf481bb06c2644f74c6812efb65d05c00631f282d6aa55c0bc140a1830b95a1cf4b6024cb0db53f2c2189897c41f22e2eec773723f531ec4bfa537fae6de5fe480cf46fe17850f7eb47df08194d95db3d26ac923b26e110ee645239ab586bbc546ddc5906f280a106edbb727ccb05536b5a3f5c0ebcf865c95ce58be54f7f3547aa53baa218b0dfa98e42d925fa341e45f94a3b16b0c83802660c7f34de3336cb21f219073cf8e9f5e39d47f0a9a9ee7c255f09a6add9a2f7a47960f4a853183d29
N=0xba8956e81394f3f1265ca5d9c4ad1ab0078bb43c4b80a231ab2cc62246ae45f66a562252622aed2cbbfc08647ef2fec0f97a632bf2242845f4b3af0c427cec3d90f42e90278a5a0feeed0922a8cd2278074ac54e9cfc0e96ff68f8d8f266dd87dc1cc59c2895ec884de2022311767f6a9a7e0bd288c79620e28b83bb3c8d8ad1047c839d6ccf5544eaf434a5f00b951769ab3121298d04b63a162757beb3d49917cd0c9e02ee1ac29398c8130961d5a2f2833aba1e538edb7bb97071f40fae543d1622f0c9206c6d4d8abb2ac1b93ebfb603c2f3a909ede357ade4043550fe540d13a4e87db8d731fe130f15a43a1a00364f5da2d87f7b660c3a04e734218a11
ct=0x101b284ad196b5bbd3d3df00a7d3577caeb29c681bdd122582b705afc671febf45d4f3786640e55aadd6a31ecc49175f97b772720f1735f8555f768b137a4643cd6958f80a3dfca4d0270ad463d6dde93429940bd2abb5ad8408b0906fa8d776544a1c50cc0d95939bef4c3fb64d0b52dca81ff0f244fc265bfc0bc147435d05f8f1a146e963a1403b3c123b4d6e73d1fd897109995009be1673212607f0ea7ae33d23f3158448b05c28ea6636382eee9436c4a6c09023ead7182ecd55ac73a68d458d726e1abc208810468591e63f4b4c2c1f3ce27c4800b52f7421ccab432c03e88b3b255740d719e40e0226eabb7633d97ed210e32071e2ac36ed17ef442e
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]
d0 = CRT(hints, list(sieve_base)[1:len(hints)+1])
M = prod(list(sieve_base)[1:len(hints)+1])
print(d0)
X1 = 2 ** 1360
X2 = 2 ** 1700
G = Matrix(ZZ, 3, 3)
G[0, 0] = K1
G[1, 1] = K2
G[0, 2] = e*M
G[1, 2] = e*d0
G[2, 2] = N+1
L = G.BKZ()
for row in L:
    d = d0 + row[0]//X1*tmp
    print(int(d).bit_length(), row[1]==X2)
    if int(d).bit_length() == int(2048*0.33):
        m = pow(ct, d, N)
        print(long_to_bytes(int(m)))

latticebros

task.py

#已知α的极小多项式为三次多项式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)

首先是这行注释

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

https://eprint.iacr.org/2023/032

这里就是一个极小多项式的问题，这个可以求出a0,从而求出p

from sage.all import *
from Crypto.Util.number import long_to_bytes
#step1 求a0
beta = 54236.606188881754809671280151541781895183337725393
# 构造基矩阵
M = matrix(ZZ, [[10**50, 1, 0, 0], [10**50 * beta, 0, 1, 0],
[10**50 * beta ^ 2, 0, 0, 1], [10**50 * beta ^ 3, 0, 0, 0]])
M_reduced = M.LLL()
a0, a1, a2 = M_reduced[0][1], M_reduced[0][2], M_reduced[0][3]

接着就是一个HNP问题

构造格

归约的目标向量就是$(\beta_1+a_1,…,\beta_i+a_i,\frac{\alpha}{p})$,但是对B使用LLL后我们不知道哪个向量合适，所以这里要进一步思考。回顾一下

 B = 2**30
 beta = random.randint(-B + 1, B - 1)

由于这里的beta很小，所以我们就要找到一个最小的$\beta$,就比较接近我们目标向量，这里就需要babai 算法了

babai算法是找到在格基中，寻找一个与某个向量最近的格点，在这里就是我们找到一个点v，使得它离a最近

exp

from sage.all import *
from Crypto.Util.number import long_to_bytes
def babai_cvp(B_reduced, t):
    G = B_reduced.gram_schmidt()[0]
    t_proj = t
    v = 0
    for i in reversed(range(B_reduced.nrows())):
        c = (t_proj * G[i]) / (G[i] * G[i])
        c = round(c)
        v += c * B_reduced[i]
        t_proj -= c * B_reduced[i]
    return v
d = 981020902672546902438782010902608140583199504862558032616415
p = d - a0
f = open(r"samples.txt")
samples = f.readlines()
samples = eval(samples[0])
m = 30
# 构造格基矩阵 B（m+1 维）
B_matrix = [[0 for _ in range(m + 1)] for _ in range(m + 1)]
for i in range(m):
    B_matrix[i][i] = p
for j in range(m):
    B_matrix[m][j] = samples[j][0]
B_matrix[m][m] = 1 / p
#构造⽬标向量
target = [samples[i][1] for i in range(m)]
target.append(0) # 补上最后⼀位⽬标（α所在维度是第 m+1 位）
B = matrix(B_matrix)
a = vector(target)
B_reduced = B.LLL()
v = babai_cvp(B_reduced, a)
u = v - a
flag = u[m] * p
print(long_to_bytes(int(flag)%p))