CISCN 2025 Crypto - RSA_NestingDoll 深度技术解析

一、题目初探

本题是 CISCN 2025 密码学赛道的一道题目，题目名称为 "RSA_NestingDoll"（RSA套娃），从名字就可以看出这道题涉及到某种嵌套或者多层的RSA结构。我们先来看看题目给了什么。

1.1 题目附件

题目提供了两个文件：

1. src.py- 加密源代码

2. output.txt- 加密后的输出数据

让我们先查看 output.txt 的内容：

[+] inner RSA modulus = 16141229822582999941795528434053604024130834376743380417543848154510567941426284503974843508505293632858944676904777719167211264225017879544879766461905421764911145115313698529148118556481569662427943129906246669392285465962009760415398277861235401144473728421924300182818519451863668543279964773812681294700932779276119980976088388578080667457572761731749115242478798767995746571783659904107470270861418250270529189065684265364754871076595202944616294213418165898411332609375456093386942710433731450591144173543437880652898520275020008888364820928962186107055633582315448537508963579549702813766809204496344017389879

[+] outer RSA modulus = 484831124108275939341366810506193994531550055695853253298115538101629337644848848341479419438032232339003236906071864005366050185096955712484824249228197577223248353640366078747360090084446361275032026781246854700074896711976487694783856878403247312312487197243272330518861346981470353394149785086635163868023866817552387681890963052199983782800993485245670437818180617561464964987316161927118605512017355921555464359512280368738197370963036482455976503266489446554327046948670215814974461717020804892983665655107351050779151227099827044949961517305345415735355361979690945791766389892262659146088374064423340675969505766640604405056526597458482705651442368165084488267428304515239897907407899916127394598273176618290300112450670040922567688605072749116061905175316975711341960774150260004939250949738836358264952590189482518415728072191137713935386026127881564386427069721229262845412925923228235712893710368875996153516581760868562584742909664286792076869106489090142359608727406720798822550560161176676501888507397207863998129261472631954482761264406483807145805232317147769145985955267206369675711834485845321043623959730914679051434102698588945009836642922614296598336035078421463808774940679339890140690147375340294139027290793

[+] Ciphertext = 657984921229942454933933403447729006306657607710326864301226455143743298424203173231485254106370042482797921667656700155904329772383820736458855765136793243316671212869426397954684784861721375098512569633961083815312918123032774700110069081262242921985864796328969423527821139281310369981972743866271594590344539579191695406770264993187783060116166611986577690957583312376226071223036478908520539670631359415937784254986105845218988574365136837803183282535335170744088822352494742132919629693849729766426397683869482842748401000853783134170305075124230522253670782186531697976487673160305610021244587265868919495629

从输出可以看到三个关键信息：

• inner RSA modulus（内层RSA模数）：一个2048位的大整数，记为 n1

• outer RSA modulus（外层RSA模数）：一个4096位的大整数，记为 n

• Ciphertext（密文）：记为 c

这立刻引发了一个疑问：为什么会有两个模数？通常RSA只需要一个模数。这就是题目的关键点。

1.2 加密源码分析

接下来我们查看 src.py 的完整代码：

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

flag=open("./flag.txt","rb").read()
flag=bytes_to_long(flag+os.urandom(2048//8-len(flag)))
e=65537

def get_smooth_prime(bits, smoothness, max_prime=None):
    assert bits - 2 * smoothness > 0
    p = 2
    if max_prime!=None:
        assert max_prime>smoothness
        p*=max_prime

    while p.bit_length() < bits - 2 * smoothness:
        factor = getPrime(smoothness)
        p *= factor

    bitcnt = (bits - p.bit_length()) // 2
    while True:
        prime1 = getPrime(bitcnt)
        prime2 = getPrime(bitcnt)
        tmpp = p * prime1 * prime2
        if tmpp.bit_length() < bits:
            bitcnt += 1
            continue
        if tmpp.bit_length() > bits:
            bitcnt -= 1
            continue
        if isPrime(tmpp + 1):
            p = tmpp + 1
            break
    return p

p1=getPrime(512)
q1=getPrime(512)
r1=getPrime(512)
s1=getPrime(512)
n1=p1*q1*r1*s1
assert n1>flag

p=get_smooth_prime(1024,20,p1)
q=get_smooth_prime(1024,20,q1)
r=get_smooth_prime(1024,20,r1)
s=get_smooth_prime(1024,20,s1)
n=p*q*r*s

print(f"[+] inner RSA modulus = {n1}")
print(f"[+] outer RSA modulus = {n}")
print(f"[+] Ciphertext = {pow(flag,e,n1)}")

现在加密流程就清晰了：

内层RSA（第36-41行）：

1. 生成4个512位的素数：p1, q1, r1, s1

2. 计算内层模数：n1 = p1 × q1 × r1 × s1（2048位）

3. 确保 n1 > flag（保证可以加密）

外层RSA（第43-47行）：

1. 使用get_smooth_prime函数生成4个1024位的素数：p, q, r, s

2. 计算外层模数：n = p × q × r × s（4096位）

加密（第51行）：

• 使用内层模数 n1 对 flag 进行加密：c = flag^e mod n1

这里有个关键细节：虽然有两个模数，但实际加密只用了内层模数 n1，外层模数 n 似乎只是"摆设"。但事实真的如此吗？

二、核心函数深度剖析

整个题目的关键在于get_smooth_prime函数，这个函数决定了外层素数的生成方式，也是整个题目的突破口。

2.1 函数签名分析

def get_smooth_prime(bits, smoothness, max_prime=None):

函数接收三个参数：

• bits：目标素数的位数（本题中为1024）

• smoothness：平滑度参数（本题中为20）

• max_prime：可选的最大素数因子（本题中为p1, q1, r1, s1）

以第43行的调用为例：p = get_smooth_prime(1024, 20, p1)

这意味着要生成一个1024位的"平滑素数"，平滑度为20，并且要包含因子p1。

2.2 函数执行流程详解

让我们一步步分析这个函数的每个阶段：

阶段一：初始化（第10-14行）

assert bits - 2 * smoothness > 0
p = 2
if max_prime != None:
    assert max_prime > smoothness
    p *= max_prime

执行过程：

1. 检查参数有效性：1024 - 2×20 = 984 > 0，满足条件

2. 初始化 p = 2

3. 因为 max_prime = p1（一个512位素数），所以 p = 2 × p1

此时 p 约为513位。

阶段二：累乘小素数（第16-18行）

while p.bit_length() < bits - 2 * smoothness:
    factor = getPrime(smoothness)
    p *= factor

循环条件：p 的位数 < 1024 - 40 = 984位

循环体：不断生成20位的素数并乘到 p 上

假设生成的素数因子为 f1, f2, f3, ..., fk，那么循环结束时：

p = 2 × p1 × f1 × f2 × f3 × ... × fk

此时 p 的位数约为 984 位。

让我们估算一下需要多少个因子：

• 初始：p = 2 × p1 ≈ 513位

• 目标：984位

• 需要增加：984 - 513 = 471位

• 每个因子：20位

• 大约需要：471 / 20 ≈ 23-24个因子

阶段三：添加两个平衡素数（第20-33行）

bitcnt = (bits - p.bit_length()) // 2
while True:
    prime1 = getPrime(bitcnt)
    prime2 = getPrime(bitcnt)
    tmpp = p * prime1 * prime2
    if tmpp.bit_length() < bits:
        bitcnt += 1
        continue
    if tmpp.bit_length() > bits:
        bitcnt -= 1
        continue
    if isPrime(tmpp + 1):
        p = tmpp + 1
        break
return p

此时 p ≈ 984位，距离目标1024位还差40位。

执行过程：

1. 计算每个素数应该的位数：bitcnt = (1024 - 984) // 2 = 20位

2. 生成两个20位左右的素数 prime1 和 prime2

3. 计算 tmpp = p × prime1 × prime2

4. 调整 prime1 和 prime2 的位数，使得 tmpp 恰好为1024位

5. 检查 tmpp + 1 是否为素数

6. 如果是素数，返回 tmpp + 1

最终返回的素数形式为：

p_outer = 2 × p1 × f1 × f2 × ... × fk × prime1 × prime2 + 1

2.3 关键数学性质

从上面的分析可以得出，外层素数 p 满足：

p = 2 × p1 × f1 × f2 × ... × fk × prime1 × prime2 + 1

移项得到：

p - 1 = 2 × p1 × f1 × f2 × ... × fk × prime1 × prime2

这个式子揭示了一个重要性质：p-1 的素因子分解中，所有素数都比较小！

• 2 是最小的素数

• p1 是512位的素数（这是已知的内层素数）

• f1, f2, ..., fk 都是20位的小素数

• prime1, prime2 都是20位左右的小素数

在数论中，如果一个整数的所有素因子都小于某个界限B，我们称这个整数为"B-平滑数"（B-smooth number）。

p-1 除了包含一个512位的因子p1外，其他所有因子都小于 2^20 = 1048576，因此 p-1 是一个"高度平滑"的数。

这就是题目名称"NestingDoll"（套娃）的含义：

• 外层素数 p 的构造依赖于内层素数 p1

• p1 被"嵌套"在 p-1 的因子分解中

• 外层保护内层，但外层本身存在弱点

三、攻击向量识别

3.1 传统RSA分解的困难

在标准RSA中，如果给定模数 n = p × q（两个大素数的乘积），要分解 n 是计算上困难的。目前对于2048位的RSA模数，没有已知的高效分解算法。

本题的内层模数 n1 = p1 × q1 × r1 × s1 是2048位，如果直接分解，几乎是不可能的。

3.2 平滑数的脆弱性

然而，当素数 p 满足"p-1 平滑"这个特殊性质时，存在一种经典的分解算法可以高效地分解包含 p 的合数，这就是：

Pollard's p-1 算法

这个算法由英国数学家 John Pollard 于1974年提出，专门用于攻击那些素因子 p 满足 p-1 平滑的RSA模数。

3.3 为什么给出外层模数？

现在我们理解了题目的设计意图：

1. flag 使用内层模数 n1 加密，我们需要分解 n1 才能解密

2. 内层素数 p1, q1, r1, s1 直接分解是困难的

3. 但外层模数 n = p × q × r × s 中的素数是"平滑"的

4. 我们可以分解外层模数 n，得到 p, q, r, s

5. 然后从 p, q, r, s 中提取出 p1, q1, r1, s1（因为 p-1 包含因子 p1）

6. 最后用 p1, q1, r1, s1 解密

这是一个"曲线救国"的攻击路径：外层→内层→解密。

四、Pollard's p-1 算法原理

4.1 费马小定理基础

Pollard's p-1 算法的理论基础是费马小定理。

费马小定理：如果 p 是素数，a 是不被 p 整除的整数，那么：

a^(p-1) ≡ 1 (mod p)

这意味着 p 能够整除 a^(p-1) - 1，即：

a^(p-1) - 1 ≡ 0 (mod p)

等价于：

gcd(a^(p-1) - 1, n) 是 n 的一个因子（如果 p 是 n 的因子）

4.2 算法核心思想

问题在于：我们不知道 p-1 的值，怎么计算 a^(p-1) 呢？

Pollard 的巧妙想法是：如果 p-1 是平滑的，我们可以构造一个数 M，使得 (p-1) | M（p-1 整除 M）。

如果 (p-1) | M，那么存在整数 k 使得 M = k × (p-1)，因此：

a^M = a^(k×(p-1)) = (a^(p-1))^k ≡ 1^k ≡ 1 (mod p)

这样 gcd(a^M - 1, n) 就能找到 n 的因子。

4.3 如何构造 M

假设 p-1 的素因子分解为：

p-1 = 2^a₁ × 3^a₂ × 5^a₃ × ... × pk^ak

如果所有素数 pi 都小于某个界限 B，我们可以令：

M = 2 × 3 × 5 × 7 × 11 × ... × (B以内的所有素数)

或者更严格地，令 M = LCM(1, 2, 3, ..., B)。

为了简化，我们可以逐步计算：

1. 从 a = 2 开始

2. 对于每个素数 p ≤ B，计算 a = a^p mod n

3. 定期检查 gcd(a - 1, n) 是否大于1

4.4 本题的特殊优化

回忆外层素数的构造：

p - 1 = 2 × p1 × (多个20位素数)

这里 p1 是512位的素数，是 p-1 的一个大因子。

如果我们知道 p-1 包含因子 p1，而题目又给出了 n1（p1 是 n1 的因子），我们可以利用这个信息：

优化策略：不是从 a = 2 开始，而是从 a = 2^n1 mod n 开始。

这样做的好处是：如果 p1 整除 p-1，而 p1 整除 n1，那么：

2^n1 ≡ 2^(k×p1) ≡ (2^p1)^k (mod p)

这更容易满足指数是 p-1 的倍数的条件。

五、攻击实施步骤

5.1 步骤一：生成素数表

首先，我们需要生成所有小于 2^21 的素数。为什么是 2^21？

因为：

• smoothness 参数是 20

• p-1 的小因子都是20位的

• 2^20 = 1048576，为了安全起见，我们取 2^21 = 2097152

生成素数的代码使用经典的试除法（Sieve of Eratosthenes 的简化版）：

limit = 2**21
primes = []
num = 2
while num < limit:
    is_p = True
    for p in primes:
        if p * p > num:
            break
        if num % p == 0:
            is_p = False
            break
    if is_p:
        primes.append(num)
    num += 1

算法逻辑：

1. 从 num = 2 开始遍历

2. 对于每个数，检查它是否能被已知素数整除

3. 如果不能被整除（且检查到 √num），则它是素数

4. 将素数加入列表

这会生成大约 155,611 个素数。

5.2 步骤二：实现 Pollard's p-1 算法

核心函数实现：

def pollard(target_n, a=2):
    g = gmpy2.mpz(a)
    base = gmpy2.powmod(g, n1, target_n)

    current_n = target_n
    found_factors = []

    for i, p in enumerate(primes):
        base = gmpy2.powmod(base, p, current_n)

        if i % 500 == 0:
            d = gmpy2.gcd(base - 1, current_n)
            if d > 1:
                if d < current_n:
                    found_factors.append(d)
                    current_n //= d
                    base %= current_n

        if current_n == 1:
            break

    if current_n > 1:
        found_factors.append(current_n)

    return found_factors

详细解释每一行：

g = gmpy2.mpz(a)
base = gmpy2.powmod(g, n1, target_n)

• 初始化底数为 a（默认为2）

• 计算 base = a^n1 mod target_n

• 这是优化步骤，利用 n1 包含内层素数的信息

current_n = target_n
found_factors = []

• current_n 跟踪当前待分解的数

• found_factors 存储找到的因子

for i, p in enumerate(primes):
    base = gmpy2.powmod(base, p, current_n)

• 遍历素数表中的每个素数 p

• 计算 base = base^p mod current_n

• 这相当于逐步计算 a^(n1 × p1 × p2 × p3 × ...) mod n

if i % 500 == 0:
    d = gmpy2.gcd(base - 1, current_n)
    if d > 1:
        if d < current_n:
            found_factors.append(d)
            current_n //= d
            base %= current_n

• 每处理500个素数，检查一次 gcd

• 如果 gcd(base-1, n) > 1，说明找到了因子

• 将 n 除以找到的因子，继续分解剩余部分

• 更新 base 以匹配新的模数

if current_n == 1:
    break

• 如果已经完全分解，提前结束

if current_n > 1:
    found_factors.append(current_n)

• 最后剩余的部分也是一个因子

为什么使用多个底数？

不同的底数 a 对不同的素因子可能有不同的效果。为了提高成功率，我们尝试多个底数：

bases = [2, 3, 5, 7, 11, 13]
for b in bases:
    res = pollard(curr, a=b)
    if len(res) > 1 or (len(res) == 1 and res[0] < curr):
        factors = res
        break

5.3 步骤三：递归分解外层模数

to_factor = [n_outer]
final_primes = []

while to_factor:
    curr = to_factor.pop(0)

    if gmpy2.is_prime(curr):
        final_primes.append(curr)
        continue

    factors = []
    for b in bases:
        res = pollard(curr, a=b)
        if len(res) > 1 or (len(res) == 1 and res[0] < curr):
            factors = res
            break

    for f in factors:
        if gmpy2.is_prime(f):
            final_primes.append(f)
        else:
            to_factor.append(f)

这是一个工作队列模式：

1. 初始队列包含外层模数 n

2. 取出一个数，检查是否为素数

3. 如果是素数，加入结果列表

4. 如果不是素数，用 Pollard's p-1 分解

5. 将分解结果加入队列或结果列表

6. 重复直到队列为空

最终得到4个1024位的素数：p, q, r, s

5.4 步骤四：恢复内层素数

这是最巧妙的一步。我们知道：

p_outer = 2 × p_inner × (其他小因子) + 1

因此：

p_outer - 1 = 2 × p_inner × (其他小因子)

同时，内层模数 n1 = p1 × q1 × r1 × s1，其中 p_inner 就是 p1, q1, r1, s1 中的一个。

因此：

p_inner = gcd(p_outer - 1, n1)

代码实现：

factors_inner = []
for p_out in final_primes:
    p_in = gmpy2.gcd(p_out - 1, n1)
    if p_in > 1:
        factors_inner.append(p_in)

对每个外层素数计算 gcd，提取出内层素数。

这一步为什么有效？让我们详细分析：

假设 p_outer 对应的内层素数是 p1，那么：

• p_outer - 1 = 2 × p1 × f1 × f2 × ... × fk × prime1 × prime2

• n1 = p1 × q1 × r1 × s1

gcd(p_outer - 1, n1) 会提取出两个数的公共因子。

由于：

• 2, f1, f2, ..., prime1, prime2 都是很小的素数（20位左右）

• q1, r1, s1 都是512位的素数

• 小素数不太可能整除大素数

因此 gcd 的结果恰好是 p1（或者它的倍数，但通常就是 p1）。

5.5 步骤五：计算私钥并解密

有了4个内层素数 p1, q1, r1, s1，我们可以计算欧拉函数。

对于多素数RSA，欧拉函数计算公式为：

φ(n1) = φ(p1 × q1 × r1 × s1) = (p1-1) × (q1-1) × (r1-1) × (s1-1)

代码实现：

phi = 1
for p in factors_inner:
    phi *= (p - 1)

然后计算私钥 d，满足：

e × d ≡ 1 (mod φ(n1))

即：

d = e^(-1) mod φ(n1)

代码实现：

d_priv = gmpy2.invert(e, phi)

最后使用 RSA 解密公式：

m = c^d mod n1

m = gmpy2.powmod(c, d_priv, n1)

提取 flag：

flag_padded = long_to_bytes(m)
if b'flag{' in flag_padded:
    start = flag_padded.index(b'flag{')
    end = flag_padded.index(b'}', start) + 1
    flag = flag_padded[start:end].decode()

由于加密前进行了填充（src.py 第6行添加了随机字节），解密后的明文包含随机数据，我们需要提取其中的 flag 部分。

六、完整攻击代码

将以上所有步骤整合，得到完整的攻击脚本：

from Crypto.Util.number import *
import gmpy2

# 从 output.txt 读取的数据
n1 = 16141229822582999941795528434053604024130834376743380417543848154510567941426284503974843508505293632858944676904777719167211264225017879544879766461905421764911145115313698529148118556481569662427943129906246669392285465962009760415398277861235401144473728421924300182818519451863668543279964773812681294700932779276119980976088388578080667457572761731749115242478798767995746571783659904107470270861418250270529189065684265364754871076595202944616294213418165898411332609375456093386942710433731450591144173543437880652898520275020008888364820928962186107055633582315448537508963579549702813766809204496344017389879

n_outer = 484831124108275939341366810506193994531550055695853253298115538101629337644848848341479419438032232339003236906071864005366050185096955712484824249228197577223248353640366078747360090084446361275032026781246854700074896711976487694783856878403247312312487197243272330518861346981470353394149785086635163868023866817552387681890963052199983782800993485245670437818180617561464964987316161927118605512017355921555464359512280368738197370963036482455976503266489446554327046948670215814974461717020804892983665655107351050779151227099827044949961517305345415735355361979690945791766389892262659146088374064423340675969505766640604405056526597458482705651442368165084488267428304515239897907407899916127394598273176618290300112450670040922567688605072749116061905175316975711341960774150260004939250949738836358264952590189482518415728072191137713935386026127881564386427069721229262845412925923228235712893710368875996153516581760868562584742909664286792076869106489090142359608727406720798822550560161176676501888507397207863998129261472631954482761264406483807145805232317147769145985955267206369675711834485845321043623959730914679051434102698588945009836642922614296598336035078421463808774940679339890140690147375340294139027290793

c = 657984921229942454933933403447729006306657607710326864301226455143743298424203173231485254106370042482797921667656700155904329772383820736458855765136793243316671212869426397954684784861721375098512569633961083815312918123032774700110069081262242921985864796328969423527821139281310369981972743866271594590344539579191695406770264993187783060116166611986577690957583312376226071223036478908520539670631359415937784254986105845218988574365136837803183282535335170744088822352494742132919629693849729766426397683869482842748401000853783134170305075124230522253670782186531697976487673160305610021244587265868919495629

e = 65537

print("[*] 步骤1: 生成素数表")
print("[*] 生成所有小于 2^21 的素数用于 Pollard's p-1 攻击...")

limit = 2**21
primes = []
num = 2
while num < limit:
    is_p = True
    for p in primes:
        if p * p > num:
            break
        if num % p == 0:
            is_p = False
            break
    if is_p:
        primes.append(num)
    num += 1

print(f"[+] 成功生成 {len(primes)} 个素数")

def pollard(target_n, a=2):
    """
    Pollard's p-1 算法实现

    参数:
        target_n: 待分解的合数
        a: 底数（默认为2）

    返回:
        找到的因子列表
    """
    g = gmpy2.mpz(a)
    # 优化：使用 n1 作为初始指数
    base = gmpy2.powmod(g, n1, target_n)

    current_n = target_n
    found_factors = []

    # 逐个素数累乘到指数上
    for i, p in enumerate(primes):
        base = gmpy2.powmod(base, p, current_n)

        # 定期检查是否找到因子
        if i % 500 == 0:
            d = gmpy2.gcd(base - 1, current_n)
            if d > 1:
                if d < current_n:
                    found_factors.append(d)
                    current_n //= d
                    base %= current_n

        if current_n == 1:
            break

    # 剩余部分也是一个因子
    if current_n > 1:
        found_factors.append(current_n)

    return found_factors

def solve():
    print("\n[*] 步骤2: 使用 Pollard's p-1 算法分解外层模数")
    print("[*] 这可能需要一些时间...")

    to_factor = [n_outer]
    final_primes = []

    # 使用多个底数提高成功率
    bases = [2, 3, 5, 7, 11, 13]

    while to_factor:
        curr = to_factor.pop(0)

        # 检查是否已经是素数
        if gmpy2.is_prime(curr):
            final_primes.append(curr)
            print(f"[+] 确认素因子: {curr.bit_length()} bits")
            continue

        # 尝试分解
        factors = []
        for b in bases:
            print(f"[*] 使用底数 a={b} 尝试分解...")
            res = pollard(curr, a=b)

            # 检查是否成功分解
            if len(res) > 1 or (len(res) == 1 and res[0] < curr):
                factors = res
                print(f"[+] 成功! 找到 {len(res)} 个因子")
                break

        # 处理找到的因子
        for f in factors:
            if gmpy2.is_prime(f):
                final_primes.append(f)
                print(f"[+] 确认素因子: {f.bit_length()} bits")
            else:
                to_factor.append(f)
                print(f"[*] 继续分解合数: {f.bit_length()} bits")

    print(f"\n[+] 外层模数分解完成! 共找到 {len(final_primes)} 个素因子")

    print("\n[*] 步骤3: 从外层素数恢复内层素数")
    print("[*] 利用 gcd(p_outer - 1, n1) 提取内层素数...")

    factors_inner = []
    for p_out in final_primes:
        p_in = gmpy2.gcd(p_out - 1, n1)
        if p_in > 1:
            factors_inner.append(p_in)
            print(f"[+] 恢复内层素数: {p_in.bit_length()} bits")

    print(f"\n[+] 成功恢复 {len(factors_inner)} 个内层素数!")

    print("\n[*] 步骤4: 计算欧拉函数 φ(n1)")
    phi = 1
    for p in factors_inner:
        phi *= (p - 1)
    print(f"[+] φ(n1) 计算完成")

    print("\n[*] 步骤5: 计算私钥 d")
    d_priv = gmpy2.invert(e, phi)
    print(f"[+] 私钥计算完成")

    print("\n[*] 步骤6: 解密密文")
    m = gmpy2.powmod(c, d_priv, n1)

    print("\n[*] 步骤7: 提取 flag")
    flag_padded = long_to_bytes(m)
    if b'flag{' in flag_padded:
        start = flag_padded.index(b'flag{')
        end = flag_padded.index(b'}', start) + 1
        flag = flag_padded[start:end].decode()
        print(f"\n{'='*60}")
        print(f"[+] 成功!")
        print(f"[+] Flag: {flag}")
        print(f"{'='*60}")
        return flag
    else:
        print("[-] 解密失败: 未找到 flag 格式")
        return None

if __name__ == "__main__":
    solve()

七、运行结果

执行脚本后，输出如下：

[*] 步骤1: 生成素数表
[*] 生成所有小于 2^21 的素数用于 Pollard's p-1 攻击...
[+] 成功生成 155611 个素数

[*] 步骤2: 使用 Pollard's p-1 算法分解外层模数
[*] 这可能需要一些时间...
[*] 使用底数 a=2 尝试分解...
[+] 成功! 找到 4 个因子
[+] 确认素因子: 1024 bits
[+] 确认素因子: 1024 bits
[+] 确认素因子: 1024 bits
[+] 确认素因子: 1024 bits

[+] 外层模数分解完成! 共找到 4 个素因子

[*] 步骤3: 从外层素数恢复内层素数
[*] 利用 gcd(p_outer - 1, n1) 提取内层素数...
[+] 恢复内层素数: 512 bits
[+] 恢复内层素数: 512 bits
[+] 恢复内层素数: 512 bits
[+] 恢复内层素数: 512 bits

[+] 成功恢复 4 个内层素数!

[*] 步骤4: 计算欧拉函数 φ(n1)
[+] φ(n1) 计算完成

[*] 步骤5: 计算私钥 d
[+] 私钥计算完成

[*] 步骤6: 解密密文

[*] 步骤7: 提取 flag

============================================================
[+] 成功!
[+] Flag: flag{fak3_r5a_0f_euler_ph1_of_RSA_040a2d35}
============================================================

成功获取 flag：flag{fak3_r5a_0f_euler_ph1_of_RSA_040a2d35}

八、核心知识点详解

8.1 多素数 RSA (Multi-Prime RSA)

传统 RSA 使用两个素数 p 和 q，模数 n = p × q。本题使用了4个素数，这种变体被称为多素数 RSA。

多素数 RSA 的特点：

1. 更快的加解密速度：使用中国剩余定理（CRT）时，计算量与素数个数成反比

2. 相同安全级别下更小的素数：4个512位素数的安全性约等于2个1024位素数

3. 欧拉函数计算：φ(n) = φ(p1 × p2 × ... × pk) = (p1-1) × (p2-1) × ... × (pk-1)

安全性考量：

虽然多素数 RSA 在某些场景下有优势，但如果素数选择不当，会引入新的攻击面。本题就是一个典型例子。

8.2 平滑数理论 (Smooth Numbers)

定义：一个正整数 n 被称为 B-平滑数（B-smooth），如果 n 的所有素因子都不超过 B。

例子：

• 100 = 2^2 × 5^2 是 5-平滑数

• 144 = 2^4 × 3^2 是 3-平滑数

• 2310 = 2 × 3 × 5 × 7 × 11 是 11-平滑数

在密码学中的意义：

平滑数在密码学中通常被认为是"弱"的，因为：

1. Pollard's p-1 算法可以高效分解素因子 p 满足 p-1 平滑的合数

2. Williams' p+1 算法可以攻击 p+1 平滑的情况

3. 椭圆曲线分解法（ECM）也对平滑数更有效

RSA 素数选择要求：

安全的 RSA 素数应该满足：

• p-1 应该有大素因子（至少一个 > 2^100）

• p+1 也应该有大素因子

• 这种素数被称为"强素数"（Strong Prime）

8.3 Pollard's p-1 算法深入

算法复杂度：

如果 p-1 的最大素因子为 B，算法的时间复杂度约为 O(B log B log^2 n)。

对于本题：

• p-1 的素因子除了 p1 外都小于 2^20

• 我们生成了 2^21 以内的所有素数

• 算法可以在合理时间内完成

算法的局限性：

1. 只对 p-1 平滑的素数有效

2. 如果 p-1 有一个很大的素因子，算法会失败

3. 需要提前知道或猜测平滑度界限 B

其他变体：

• Williams' p+1 算法：攻击 p+1 平滑的情况

• Pollard's rho 算法：通用的整数分解算法，不依赖平滑性

• Lenstra 椭圆曲线分解法（ECM）：更强大的算法，对中等大小的因子非常有效

8.4 费马小定理与欧拉定理

费马小定理：如果 p 是素数，a 不是 p 的倍数，则：

a^(p-1) ≡ 1 (mod p)

欧拉定理：对于互质的 a 和 n：

a^φ(n) ≡ 1 (mod n)

RSA 的数学基础：

RSA 的正确性就基于欧拉定理：

c = m^e mod n
m = c^d mod n

其中 e × d ≡ 1 (mod φ(n))，即 e × d = k × φ(n) + 1

因此：

c^d = (m^e)^d = m^(e×d) = m^(k×φ(n)+1) = (m^φ(n))^k × m ≡ 1^k × m ≡ m (mod n)

8.5 最大公约数（GCD）的密码学应用

GCD 在密码学攻击中有很多应用：

1. 共模攻击：如果两个 RSA 模数有公共因子：

gcd(n1, n2) = p（公共素数）

2. 本题的应用：提取嵌套的素数：

gcd(p_outer - 1, n1) = p_inner

3. 小指数攻击：如果多个消息用相同的小指数加密：

通过 gcd 可以恢复明文

4. Wiener 攻击：利用连分数和 gcd 攻击小私钥

GCD 的高效计算（欧几里得算法）使得这些攻击在实践中可行。

九、攻击流程图解

让我们用流程图的方式总结整个攻击过程：

[题目给定]
   |
   +-- n1 (内层模数, 2048-bit)
   +-- n (外层模数, 4096-bit)
   +-- c (密文)
   +-- e = 65537
   |
   v
[分析源码]
   |
   +-- 发现 p = get_smooth_prime(1024, 20, p1)
   +-- 推断 p-1 包含因子 p1 且高度平滑
   |
   v
[选择攻击方法]
   |
   +-- 识别出 Pollard's p-1 算法适用
   |
   v
[步骤1: 生成素数表]
   |
   +-- 生成所有 < 2^21 的素数
   +-- 共 155,611 个素数
   |
   v
[步骤2: 分解外层模数 n]
   |
   +-- 使用 Pollard's p-1 算法
   +-- 尝试多个底数 [2,3,5,7,11,13]
   +-- 递归分解直到得到素数
   |
   v
[得到外层素数]
   |
   +-- p (1024-bit)
   +-- q (1024-bit)
   +-- r (1024-bit)
   +-- s (1024-bit)
   |
   v
[步骤3: 恢复内层素数]
   |
   +-- 计算 p1 = gcd(p-1, n1)
   +-- 计算 q1 = gcd(q-1, n1)
   +-- 计算 r1 = gcd(r-1, n1)
   +-- 计算 s1 = gcd(s-1, n1)
   |
   v
[得到内层素数]
   |
   +-- p1 (512-bit)
   +-- q1 (512-bit)
   +-- r1 (512-bit)
   +-- s1 (512-bit)
   |
   v
[步骤4: 计算欧拉函数]
   |
   +-- φ(n1) = (p1-1)(q1-1)(r1-1)(s1-1)
   |
   v
[步骤5: 计算私钥]
   |
   +-- d = e^(-1) mod φ(n1)
   |
   v
[步骤6: 解密]
   |
   +-- m = c^d mod n1
   |
   v
[步骤7: 提取 flag]
   |
   +-- 从填充的明文中提取 flag
   |
   v
[成功!]
   |
   +-- flag{fak3_r5a_0f_euler_ph1_of_RSA_040a2d35}

十、安全启示与防御

10.1 本题暴露的安全问题

1. 素数生成不当：

   • 外层素数的构造使得 p-1 高度平滑

   • 违反了 RSA 安全素数的基本要求

2. 素数之间的关联：

   • 外层素数依赖于内层素数

   • 创建了意外的数学关系

3. 过度复杂的设计：

   • 嵌套结构增加了攻击面

   • 复杂性不等于安全性

10.2 安全的 RSA 实现要求

素数选择：

1. 使用密码学安全的随机数生成器：

   • 不要使用可预测的生成方法

   • 确保素数真正随机

2. 验证强素数属性：

   # p 应该满足：
   # 1. p-1 有大素因子
   # 2. p+1 有大素因子
   # 3. p 足够大（至少 1024 位，推荐 2048 位）
   

3. 避免素数之间的关联：

   • 独立生成每个素数

   • 不要让素数之间有数学关系

参数选择：

1. 公钥指数 e：

   • 常用 65537（0x10001）

   • 避免使用太小的 e（如 3）

2. 私钥保护：

   • d 应该足够大

   • 避免 Wiener 攻击（d < n^0.292）

3. 模数长度：

   • 至少 2048 位（推荐）

   • 未来考虑 3072 位或 4096 位

使用标准库：

不要自己实现 RSA，使用经过审计的标准库：

• Python:cryptography库

• OpenSSL

• BoringSSL

10.3 识别类似漏洞的方法

当遇到 RSA 题目时，应该检查：

1. 素数生成方法：

   • 是否使用了特殊的生成函数？

   • 是否有 "smooth", "prime", "generate" 等函数？

2. 参数之间的关系：

   • 多个参数是否有数学关联？

   • 是否可以用 gcd 提取公共信息？

3. 已知的攻击方法：

   • 小指数攻击

   • 共模攻击

   • Wiener 攻击

   • Coppersmith 攻击

   • Pollard 系列算法

4. 数值大小分析：

   • 模数是否足够大？

   • 私钥是否可能很小？

   • 是否有参数泄露？

十一、总结

本题 "RSA_NestingDoll" 是一道设计精巧的密码学题目，通过嵌套 RSA 结构考察了以下知识点：

1. 多素数 RSA的原理和实现

2. 平滑数理论及其在密码学中的应用

3. Pollard's p-1 算法的原理和实现

4. 数论工具（GCD）在密码攻击中的应用

5. RSA 安全素数的选择要求

攻击路径总结为：

外层模数 n（平滑素数）
  ↓ [Pollard's p-1]
外层素数 p, q, r, s
  ↓ [GCD 提取]
内层素数 p1, q1, r1, s1
  ↓ [RSA 解密]
Flag

这道题告诉我们：

• 密码系统的安全性依赖于正确的参数选择

• 复杂的设计不一定更安全，反而可能引入新的攻击面

• 数学关系和结构性弱点是密码分析的重要突破口

• 理解经典攻击算法（如 Pollard's p-1）对于解决现代密码题目仍然至关重要

希望这份详细的技术解析能够帮助读者深入理解 RSA 的安全性要求、平滑数理论以及 Pollard's p-1 算法的实际应用。在实际的密码系统设计中，应该始终遵循安全标准，使用经过验证的算法和实现，避免引入类似的结构性弱点。