NepCTF2025 ezRSA2官方题解

这是一个简单的RSA二元Coppersmith。题目中已知$d < N^{0.33}$, 以及一些$d \bmod l_i$的值。这些$l_i$的乘积约为$N^{0.17}$。

这道题也可以用Wiener攻击的思路构造三维格求解。以下为题目和两种解法的详细说明。

题目

题目描述

Easy RSA, easy strategy. No need to brute force.

Perhaps it’s easier than ezRSA in NepCTF 2024.

代码

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
"""

解法

符号约定：

设$M= \prod_{i=1}^{\mathrm{len(hints)}} \mathrm{sievebase} [i]$, 根据CRT，可由$\mathrm{hints}$求得 $d_0 := d \bmod M$.

记$d=d_1M+d_0$, $r=p+q$.

方法1

根据RSA等式有$e(d_1M + d_0) = 1 + k(N+1-r) \implies $

$1-ed_0+k(N+1-r) \equiv 0 \bmod eM \quad (1)$

考虑到题目中$d \approx N^{0.33}, M \approx N^{0.17}$, 与无额外信息的小$d$攻击（最佳渐进界为$N^{0.2928}$）界相差不大。且题目描述中提示了，不需要使用复杂的Coppersmith策略（界是富裕的），并且比NepCTF 2024的ezRSA更简单。

使用简单shift多项式策略的二元coppersmith方法，直接求解式 $(1)$即可。

from Crypto.Util.number import sieve_base, long_to_bytes
import itertools
from sage.all import *
import time

beta = 0.33

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

# defund small_roots
# https://github.com/defund/coppersmith
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    if isinstance(f, Polynomial):
        x, = polygens(f.base_ring(), f.variable_name(), 1)
        f = f(x)

    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N**(m-i) * f**i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    st1 = time.time()
    
    B = (B.dense_matrix()).LLL(epsilon=0.99)
    # B = flatter(B)
    
    end = time.time()
    print(f'time of lattice reduction: {end-st1}s')
    print(f'{B.dimensions() = }')
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

li_list = list(sieve_base[1:len(hints)+1])

def attack():
    M = prod(li_list)
    print(f'{M.bit_length() = }')
    dM = CRT(hints, li_list)
    # ed-1 = k(N+1-(p+q))
    # k(N+1)-k(p+q)-(e*dM-1) = 0(eM)
    print(f'{dM = }')
    print(f'{dM.bit_length() = }')

    PR = PolynomialRing(Zmod(e*M), 'x,y')
    x,y = PR.gens()

    f = x*(N+1)-x*y-(e*dM-1)

    XX = (e*2**ceil(2048*beta)) // N
    YY = 3*2**1024

    roots = list(small_roots(f, [XX,YY], m=1))
    print(roots)
    assert len(roots) == 1

    k, r = roots[0]
    # ed-1=k(N+1-r)
    k, r = ZZ(k), ZZ(r)
    d = (k*(N+1-r) + 1) // e
    
    print(f'{d=}')
    print(f'{d.bit_length() = }')
    assert e*d-1==k*(N+1-r)

    pt = pow(ct, d, N)
    print(long_to_bytes(pt))
    
def main():
    attack()
    
main()

方法2

由于界比较富裕，可以根据Wiener攻击对应的二维格构造思路进行攻击。

$e(d_1M + ed_0) = 1 + k(N+1-r)$

取其中小量为 $1-kr$，将其表为已知量的线性组合

$d_1\cdot eM + 1\cdot ed_0 - k\cdot (N+1) = 1-kr \quad (2)$

构造格$\mathbf{L}$如下

$(d_1,1,-k) \begin{bmatrix} eM & 0 & X_1\\ ed_0 & X_2 & 0\\ N+1 & 0 & 0 \end{bmatrix} =(1-kr,X_2,d_1X_1) =: \mathbf{v}$

格的行列式为 $\det(\mathbf{L}) = (N+1)X_1X_2$，攻击条件为$\lvert \mathbf{v} \rvert < \det(L)^{1/3}$.

最佳做法是令 $\mathbf{v}$ 的分量绝对值量级一致，因此选择如下参数配平

$X_1 = 2^{1024+675-338}\ , \ X_2 = 2^{1025+675}$

此时有$\lvert \bf{v} \rvert \approx 2^{1701}$, $\det(\mathbf{L})^{1/3} \approx 2^{1703}$，大致满足攻击条件。

用LLL解出$\mathbf{v}$，由第3个分量求$d_1$，再计算$d=d_1M+d_0$即可解密。

一些补充：

三维格的多种构造方法（例如X1放到最后一行第3个），但它们的界相同。第一行不放$X_1$，$\mathbf{v}$的分量中就不涉及$d_1$。但也可根据LLL算法的行变换矩阵算出$d_1$，或解出$k$后再用式$(2)$ 算 $d_1$
二维格的界不够，最佳配平下$\det(\mathbf{L})^{1/2} \approx 2^{1590}, \ \lvert \mathbf{v} \rvert \approx 2^{1700}$

from sage.all import Matrix, prod, CRT, ZZ
from Crypto.Util.number import sieve_base, long_to_bytes

# 攻击算法大框架与关键注释来自于SeanDictionary的wp，此处做了一些修改
# https://seandictionary.top/nepctf-2025/

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])

# 675 = int(2048*beta)
# 338 ~ 1024*gamma
X1 = 2**(1024+675-338)
X2 = 2**(1025+675)

L = Matrix(ZZ, 3, 3)
L[0, 0] = e*M
L[0, 2] = X1
L[1, 0] = e*d0
L[1, 1] = X2
L[2, 0] = N+1

L = L.LLL()
print(f'After LLL, L=\n{L}')

for row in L:
    d = d0 + row[2]//X1*M
    print(int(d).bit_length(), row[1]==X2)
    # 这里关注d的位数要等于675
    # 然后最短向量的中间一位应该为K2
    # 按照这两个约束进行调参
    if int(d).bit_length() == int(2048*0.33):
        m = pow(ct, d, N)
        print(long_to_bytes(int(m)))

后记 & 致谢

审wp时看到方法2的解法感觉比较惊喜，有2位选手用了类似的方法。此处我们对三维格构造的思想与细节做了补充，希望对大家有益。方法2的代码是基于SeanDictionary的wp改的，这位选手将额外获得出题人（我）的一份礼物。

此外，方法1有可用优化，但shift多项式选取策略较为复杂。见Partial Key Exposure Attacks on RSA: Achieving the Boneh-Durfee Bound的第5节。

顺带一提，ezRSA2的续作很可能会在NepCTF 2026出现。可能涉及前作所用的技术，但难度会更高。敬请期待！