文章总结： 本文详细解析了一道综合性CTF密码学题目，涵盖弱密钥生成攻击、低加密指数广播攻击、共模攻击及非标准RSA解密技术。作者通过四道关卡展示了如何利用数学原理破解RSA系统，重点阐述了针对e与欧拉函数不互质情况下的特殊解密方法，强调了密钥生成规范及安全填充方案的重要性。 综合评分： 90 文章分类： CTF,漏洞分析,实战经验

---

simpleRSA – 深入浅出的RSA密码学攻击实战

原创

破镜安全 破镜安全

破镜安全

2026年2月2日 14:26 四川

simpleRSA – 深入浅出的RSA密码学攻击实战

前言

RSA加密算法是现代密码学的基石，广泛应用于数据加密和数字签名。然而，如果在实现过程中出现任何细微的疏漏，都可能导致整个系统的安全性崩溃。本文将通过分析一道综合性的CTF密码学题目，深入探讨RSA算法的多个攻击面，包括弱密钥生成、低加密指数攻击、共模攻击以及非标准RSA的特殊处理方法。

本题的特殊之处在于，它不是单一的RSA攻击场景，而是将四个独立的密码学问题串联在一起，只有依次攻破每一关，才能最终获得FLAG。这种设计充分考察了选手对RSA数学原理的深入理解和灵活运用能力。

基础知识回顾

在开始分析之前，我们需要先了解几个关键的数学概念。

RSA算法基础

RSA加密的核心流程如下：

1. 密钥生成：

• 选择两个大素数 p 和 q
• 计算模数 n = p × q
• 计算欧拉函数 φ(n) = (p-1) × (q-1)
• 选择加密指数 e，要求 gcd(e, φ(n)) = 1
• 计算解密指数 d，使得 e × d ≡ 1 (mod φ(n))

1. 加密过程：c = m^e mod n
2. 解密过程：m = c^d mod n

这个过程的安全性基于大整数分解的困难性：已知 n，很难分解出 p 和 q。

欧拉定理和费马小定理

欧拉定理指出：如果 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)

这是RSA能够正确解密的数学基础。因为：

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

中国剩余定理 (CRT)

中国剩余定理用于求解一组同余方程。假设我们有：

• x ≡ a1 (mod n1)
• x ≡ a2 (mod n2)
• x ≡ a3 (mod n3)

如果 n1, n2, n3 两两互质，那么在 [0, n1×n2×n3) 范围内存在唯一解。

CRT的求解公式为：

N = n1 × n2 × n3
对每个 i：
  Ni = N / ni
  Mi = Ni^(-1) mod ni
x = (a1×N1×M1 + a2×N2×M2 + a3×N3×M3) mod N

同余的基本性质

理解同余运算的性质对于解决本题至关重要：

1. 传递性：如果 a ≡ b (mod n×m)，则 a ≡ b (mod n) 且 a ≡ b (mod m)
2. 相乘性：如果 a ≡ b (mod n) 且 c ≡ d (mod n)，则 a×c ≡ b×d (mod n)
3. 幂运算：如果 a ≡ b (mod n)，则 a^k ≡ b^k (mod n)

题目分析

让我们先看看题目提供的加密代码结构：

#!/usr/bin/env python3.9
# -*- coding: utf-8 -*-
import gmpy2
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from secret import FLAG, E1, E2, P, Q1, Q2

def next_prime(num: int) -> int:
    num = num + 2 if num % 2 else num + 1
    while not isPrime(num):
        num += 2
    return num

# 第一部分：特殊构造的RSA
p = getPrime(1024)
q = next_prime(getPrime(16) * p + 38219)
n = p * q
c = pow(E1, 65537, n)

# 第二部分：多次加密
assert E2.bit_length() == 69
ns = [getPrime(1024) * getPrime(1024) for _ in range(3)]
cs = [pow(E2, 89, n) for n in ns]

# 第三部分：高位泄露
qq = getPrime(1024)
nn = P * qq
qqq = qq >>&nbsp;460&nbsp;<<&nbsp;460

# 第四部分：共享素因子的双重加密
assert&nbsp;len(FLAG) ==&nbsp;42
n1 = P * Q1
n2 = P * Q2
c1 = pow(bytes_to_long(FLAG), E1, n1)
c2 = pow(bytes_to_long(FLAG), E2, n2)

题目给出了相应的输出数据（n, c, ns, cs, nn, qqq, n1, n2, c1, c2）。

整体结构分析

观察代码可以发现：

1. 第一部分加密了某个秘密值E1，这个E1在第四部分用来加密FLAG
2. 第二部分加密了某个秘密值E2，这个E2也在第四部分用来加密FLAG
3. 第三部分提供了P的部分信息（虽然我们会发现有更简单的方法获取P）
4. 第四部分是最终目标，需要用E1和E2来解密FLAG

这意味着我们需要按顺序攻破四个关卡：E1 → E2 → P → FLAG

安全漏洞分析

在深入解题前，我们先识别每个部分的安全漏洞：

1. 第一部分的漏洞：q的生成方式引入了可预测性。getPrime(16)只能生成16位的素数，取值空间很小（约6000个素数），可以暴力枚举。
2. 第二部分的漏洞：同一个明文E2使用相同的小指数89在三个不同的模数下加密，这是典型的低加密指数攻击场景。
3. 第三部分的漏洞：虽然提供了qq的高位信息，但第四部分有更严重的漏洞使这个信息变得不必要。
4. 第四部分的漏洞：n1和n2共享素因子P，这是致命的安全缺陷。更复杂的是，E1和E2与对应的欧拉函数不互质，需要特殊处理。

第一关：破解E1 – 弱密钥生成攻击

漏洞原理

观察q的生成方式：

q = next_prime(getPrime(16) * p + 38219)

这里的关键问题是 getPrime(16) 生成的是一个16位（bit）的素数，取值范围是 [2^15, 2^16)，即 [32768, 65536)。

在这个范围内，素数的数量是有限的。根据素数定理，π(n) ≈ n/ln(n)，所以这个范围内大约有：

π(65536) - π(32768) ≈ 65536/ln(65536) - 32768/ln(32768) ≈ 5909 - 3114 ≈ 2795 个素数

这个数量级完全可以进行暴力枚举。

攻击思路

我们的策略是：

1. 从已知的 n = p × q，我们知道 q ≈ k × p（其中k是那个16位素数，38219相对于k×p可以忽略）
2. 因此 n ≈ p × k × p = k × p²
3. 可以推导出 p² ≈ n / k，进而 p ≈ √(n/k)
4. 对每个可能的16位素数k，估算p，然后计算可能的q，检验是否能整除n

数学推导细节

为什么可以忽略+38219？让我们看具体数值：

• p 是1024位的数，约为 10^308
• k 是16位的数，最大约为 6.5×10^4
• k × p 约为 10^308 × 6.5×10^4 = 6.5×10^312
• 38219 约为 3.8×10^4

相比于 6.5×10^312，38219完全可以忽略。因此：

q ≈ next_prime(k × p)
n = p × q ≈ p × k × p = k × p²
p ≈ √(n/k)

实现代码

def next_prime(num: int) -> int:
    """获取下一个素数"""
    num = num + 2 if num % 2 else num + 1
    while not isPrime(num):
        num += 2
    return num

# 题目给出的数据
n = 1605247600724752598798254639224215706171506359654961357324428027985787942008103766562745464838961569081446916113769517713344420113584254259000172572811154232107339480903672251992191997458469905064423618888336088652352540882576826988355783159237971043770132628344798937353150930071309347972804118952814447576207066147031238749098842662046825743988208813903138796789940911515825517078554074496474819128789835309636804325132602557092847746454786387067599510769382078521691609970320528531270474091713477040343897269903489441410062592732302402854035415438078656688806905350495825334584533345448091335565792091890185673190424063
c = 751639057610677013264061431434189083017589908118307247217007533938435229431015858783222167911772848893015518607229280589985711010766459396989232072512314594917029375221335361209036112742388866873824163350886610514973038316512032459352053158417705406031466332440378871927174731975794579894912999936641163063898365134788537389162378185448090279397717831977803284480743612393591614284972981435749362255654561121758163485884075260156288337176713756471879489767416836868661153693157792733142765671887792303181376620864506386820826866340907593080654521498766421056474652652337037121881207188033108746890998208582406826010121861

e = 65537

# 遍历所有16位素数
for k in range(2**15, 2**16):
    if isPrime(k):
        # 估算p：p ≈ √(n/k)
        p_estimate = gmpy2.iroot(n // k, 2)[0]

        # 计算可能的q
        q_candidate = next_prime(k * p_estimate + 38219)

        # 验证是否正确
        if n % q_candidate == 0:
            q = q_candidate
            print(f"找到16位素数 k = {k}")
            break

# 计算p
p = n // q

# 验证
assert n == p * q
print(f"验证成功: n = p × q")
print(f"p的位长度: {p.bit_length()} bits")
print(f"q的位长度: {q.bit_length()} bits")

运行后找到 k = 51031，成功分解了n。

标准RSA解密

得到p和q后，就可以进行标准的RSA解密：

# 计算欧拉函数
phi = (p - 1) * (q - 1)

# 求私钥d
d = gmpy2.invert(e, phi)

# 解密
E1 = pow(c, d, n)

print(f"E1 = {E1}")
# 输出: E1 = 377312346502536339265

验证：E1是一个69位的数，符合题目中E2的位长度要求（说明E1和E2可能长度相近）。

安全启示

这个攻击告诉我们：

1. 熵的重要性：密钥生成的每个环节都必须有足够的随机性（熵）。即使只有一个参数的熵不足，也可能导致整个系统崩溃。
2. 不要自创加密方案：这种”p和q存在数学关系”的构造方式看似巧妙，实则引入了巨大的安全风险。
3. 密钥生成规范：标准的RSA密钥生成应该独立地生成p和q，两者之间不应有任何可预测的关系。

第二关：破解E2 – 低加密指数攻击

问题描述

题目的第二部分提供了以下信息：

ns = [getPrime(1024) * getPrime(1024) for _ in range(3)]
cs = [pow(E2, 89, n) for n in ns]

我们有三个RSA加密结果，它们使用相同的明文E2、相同的加密指数89，但使用不同的模数。

攻击原理

这是著名的Hastad广播攻击（Hastad’s Broadcast Attack）。当同一明文m使用相同的加密指数e在k个不同的模数下加密时，如果满足以下条件：

1. k ≥ e
2. m^e < n1 × n2 × … × nk

就可以使用中国剩余定理恢复明文。

为什么这个攻击有效？

让我们详细分析这个攻击的数学原理：

假设我们有k个加密：

c1 ≡ m^e (mod n1)
c2 ≡ m^e (mod n2)
...
ck ≡ m^e (mod nk)

这是k个同余方程，我们要求解m^e。

关键观察：如果 m^e < n1×n2×…×nk，那么这些同余方程在整数意义上也成立，即：

c1 = m^e + k1×n1（其中k1是某个整数，实际上k1=0）
c2 = m^e + k2×n2（其中k2=0）
...

使用中国剩余定理，我们可以找到一个数C，使得：

C ≡ c1 (mod n1)
C ≡ c2 (mod n2)
...
C ≡ ck (mod nk)

根据CRT，C在 [0, n1×n2×…×nk) 范围内唯一。而如果 m^e < n1×n2×…×nk，那么C就正好等于m^e（而不只是同余）。

此时我们只需要对C开e次方，就能得到m。

本题的条件验证

让我们验证攻击条件：

1. 条件1：k = 3，e = 89，满足 k < e，但这并不妨碍攻击，因为E2很小
2. 条件2：E2是69位的数，那么E2^89的位长度约为 69×89 = 6141 bits

• 而 n1×n2×n3 的位长度约为 2048×3 = 6144 bits
• 条件勉强满足！

实际上，因为E2只有69位（远小于典型的1024位RSA消息），E2^89 ≈ 2^(69×89) = 2^6141，而三个模数相乘约为 2^6144，条件满足。

实现代码

首先实现中国剩余定理：

from functools import reduce

def chinese_remainder(modulus, remainders):
    """
    求解中国剩余定理
    输入: modulus = [n1, n2, n3], remainders = [a1, a2, a3]
    输出: x，满足 x ≡ ai (mod ni)
    """
    # 计算所有模数的乘积
    N = reduce(lambda a, b: a * b, modulus)

    result = 0
    for ni, ai in zip(modulus, remainders):
        # Ni = N / ni
        Ni = N // ni

        # Mi = Ni^(-1) mod ni
        Mi = inverse(Ni, ni)

        # 累加
        result += ai * Ni * Mi

    return result % N

然后求解E2：

# 题目给出的数据
ns = [15863230586500684911356384742123404120213699052018048588650392009927565369685497256344682150189923131009586323640507773706997704860898682946308031020361302334248895233255911348365179153799197341744863134926804603973507415697810440916305092395180382239729550833607847524005391137474497849077097574452115379368463540087172800902210822143687014813631366360652583216269138116785489485772437870528892032119729929607857459621078790511144060710035933887337208301078892163837203412081114510143406013892393607932596921308889058909544584619676380766485493114814753878272881866907210235681877689493671668534251778397658670518117, 14144098469438619358682652828507744381697293556670717685553585719665002440476256008471235313826051740009083510860714991201047915737216102220242621674841600987122005914542061963618272275986835928673920375768272390912778741502655909281390948606467847118377641357547931472588836726339758576038273820470879637555458446243401248151675266602656677360819563744765522495640821496694918515669243614141704744848980746101569785439728585144841655665959389460512628800782742764147773150430552859331269667626942993392101897661719871375721143240270211821269260950380944670195863016621594387236339317938305273510719419578308449465183, 27563822879593503938377821960427219022565215631856333510782568496016547757945464794632272818101891677705256471714805217606503652132995136255720639088424576003650628211271025648183600635145895528466199068640094470078526413324708028578289949241288828542143203769199399500669311878391255837977932634772778594526940501234736059441483897017015324765266787399950699732518347518591167932031031320265136158304460199654008895095274754918153773566824931440342525688741289235153882699461549523425169846266597156773535163599640189457171272058311480951820887261040891344076039474315985825984444520336790670313179493074014037981261]

cs = [3833095607830862948079097323254872789586576953317671099752083261949616608759231291050566542764984974722790226120399722937104503590740358249900089784508490830379531632752169777949200718567033018577184658177019404903817920024468923715441355404672443007723525750768430895425376124679225715687382380114628103058312176343693900115638265002657622618744666247132114654135429040069316368839938881716554901593031901272992940200484460436193699175500376368456706998564064693820008778900344357745691652875500810447147088715289581351501876012044611990972521570253106671158207677490849249612002954497927762168699886110455354481924, 1502420121177211156091634258259634977709023894278792755694473756163084431123774101512866316989917922052023168401167212284219907272528117024670443698990238243030221117004372456475521502350404137469088570170885409265567084376069256924135270283335242133163303599239181417949980292944203204296598188175632723968779672994090788585343302473442389865459398142634104331743517384589200789331489394375604801951994831647339839112698394141328178967516636452592385248135340133712522135715943787590172334743893259621909532456281362868290556461907936774231166936915669816509378419892149164552548131776979706381641477878931403040942, 8992204063713908492214256291861339175525948946919629972908439132005643626148678347198381531633907182877152728077958345519083406637446972079387161726967295886447791613166577391233866583354793842121902234644830640050181130381996083089350911224037154798259291124104894554037604500881250119806371348673833105103600782286898276354573884788251542211434143476774391457587885772379990104835187104619922442613860682792470389490804228050671124495925536024571104944112397143299499508504917890140939438891891453283594000764399193028606955089853654071198909973555844004685149713774167524224100487937899126480545681565581673958854]

e2 = 89

# 使用中国剩余定理求解
C = chinese_remainder(ns, cs)

# 开89次方
E2_result = gmpy2.iroot(C, e2)
E2 = E2_result[0]
is_perfect = E2_result[1]

print(f"E2 = {E2}")
print(f"是否为完全开方: {is_perfect}")
# 输出: E2 = 561236991551738188085
# 输出: 是否为完全开方: True

完全开方成功，说明我们的攻击完全正确！

验证

我们可以验证E2是否正确：

# 验证每个加密
for i in range(3):
    c_verify = pow(E2, e2, ns[i])
    assert c_verify == cs[i]
    print(f"验证通过: pow(E2, 89, ns[{i}]) == cs[{i}]")

全部验证通过。

防御措施

如何防御这种攻击？

1. 使用填充方案：OAEP（Optimal Asymmetric Encryption Padding）会在明文前添加随机数，使得即使是相同的原始消息，加密后的”明文”也不同。
2. 避免小指数：虽然小指数（如e=3）可以提高加密效率，但需要配合安全的填充方案。
3. 不要重复加密：同一消息不应该用相同的参数在多个系统中加密。

第三关：获取公共素因子P

问题分析

题目的第四部分是这样的：

n1 = P * Q1
n2 = P * Q2
c1 = pow(bytes_to_long(FLAG), E1, n1)
c2 = pow(bytes_to_long(FLAG), E2, n2)

这里出现了一个严重的安全漏洞：两个RSA模数n1和n2共享一个素因子P。

共模攻击原理

当两个RSA模数存在公共因子时，可以通过欧几里得算法轻松分解它们：

如果 n1 = P × Q1 且 n2 = P × Q2
那么 gcd(n1, n2) = P

这是因为：

• n1和n2的公共因子包括P的所有因子
• 而P是素数，它的因子只有1和P
• 因此 gcd(n1, n2) = P

攻击实现

# 题目给出的数据
n1 = 21655617838358037895534605162358784326495251462447218485102155997156394132443891540203860915433559917314267455046844360743623050975083617915806922096697304603878134295964650430393375225792781804726292460923708890722827436552209016368047420993613497196059326374616217655625810171080545267058266278112647715784756433895809757917070401895613168910166812566545593405362953487807840539425383123369842741821260523005208479361484891762714749721683834754601596796707669718084343845276793153649005628590896279281956588607062999398889314240295073524688108299345609307659091936270255367762936542565961639163236594456862919813549

n2 = 24623016338698579967431781680200075706241014384066250660360949684385831604822817314457973559632215801205780786144608311361063622813017396858888436529116737754653067203843306015767091585697803364656624926853551997229897087731298797904208292585562517602132663331748784390752958757661484560335406769204491939879324079089140420467301773366050084810282369044622442784113688062220370531522036512803461607049619641336524486507388232280683726065679295742456158606213294533956580462863488082028563360006966912264908424680686577344549034033470952036766850596897062924137344079889301948258438680545785139118107899367307031396309

# 求最大公约数
P = gmpy2.gcd(n1, n2)

# 计算Q1和Q2
Q1 = n1 // P
Q2 = n2 // P

print(f"P的位长度: {P.bit_length()} bits")
print(f"Q1的位长度: {Q1.bit_length()} bits")
print(f"Q2的位长度: {Q2.bit_length()} bits")

# 验证
assert n1 == P * Q1
assert n2 == P * Q2
assert isPrime(P)
assert isPrime(Q1)
assert isPrime(Q2)
print("验证成功：n1 = P × Q1, n2 = P × Q2")

输出显示P、Q1、Q2都是1024位的素数，分解完全成功。

关于第三部分的说明

题目的第三部分提供了：

nn = P * qq
qqq = qq >>&nbsp;460&nbsp;<<&nbsp;460&nbsp;&nbsp;# qq的高位信息

这原本是一个高位泄露攻击（Partial Key Exposure Attack）的场景。当RSA的某个素因子的部分位（通常是高位或低位）泄露时，可以使用Coppersmith方法来恢复完整的素因子。

然而，由于第四部分存在更严重的共模漏洞，我们可以直接通过gcd获得P，这使得第三部分的信息变得多余。这可能是出题者的一个小失误，也可能是故意设置的多条解题路径。

实际场景中的共模攻击

在现实世界中，共模攻击可能发生在以下场景：

1. 随机数生成器故障：如果系统的随机数生成器存在缺陷，可能导致不同用户生成的密钥共享素因子。2012年，研究人员扫描了互联网上的RSA公钥，发现约0.2%的公钥可以被分解，原因就是随机数生成器的问题。
2. 虚拟机克隆：在虚拟化环境中，如果不恰当地克隆虚拟机，可能导致多个实例使用相同的随机数种子。
3. 嵌入式设备：某些嵌入式设备由于缺乏足够的熵源，可能在密钥生成时产生可预测的结果。

第四关：解密FLAG – 非标准RSA的特殊处理

现在我们掌握了所有必要的信息：E1、E2、P、Q1、Q2，以及两个密文c1、c2。按照常规思路，应该可以直接解密了。但是，当我们尝试计算私钥时，会遇到一个严重的问题。

问题发现

让我们尝试标准的RSA解密流程：

# 计算欧拉函数
phi1 = (P - 1) * (Q1 - 1)
phi2 = (P - 1) * (Q2 - 1)

# 尝试求私钥
gcd1 = gmpy2.gcd(E1, phi1)
gcd2 = gmpy2.gcd(E2, phi2)

print(f"gcd(E1, φ(n1)) = {gcd1}")
print(f"gcd(E2, φ(n2)) = {gcd2}")

# 输出:
# gcd(E1, φ(n1)) = 35
# gcd(E2, φ(n2)) = 35

问题出现了：E1和E2都与对应的欧拉函数不互质！这意味着标准RSA的私钥 d = e^(-1) mod φ(n) 不存在。

为什么会出现这个问题？

标准RSA要求加密指数e与φ(n)互质，即 gcd(e, φ(n)) = 1。这是为了保证模逆元d存在。

在本题中：

E1 = 377312346502536339265 = 35 × 10780352757215323979
E2 = 561236991551738188085 = 35 × 16035342615763948231

两个加密指数都包含因子35 = 5 × 7。

这种情况下，RSA加密变成：

c1 = m^(35×k1) mod n1
c2 = m^(35×k2) mod n2

直接解密需要从 m^35 恢复 m，但问题是：

1. 无法直接求逆：35与φ(n)不互质，无法求 35^(-1) mod φ(n)
2. 无法直接开方：即使得到了 m^35 mod n，也无法直接开35次方，因为模运算下的高次方根问题是困难的

解决思路

我们需要利用35 = 5 × 7的因子分解，将问题分解为两个子问题。整体策略是：

1. 先消除k1和k2（因为它们与φ互质）
2. 利用同余性质和中国剩余定理，构造新的RSA系统
3. 在新系统中分别处理因子7和因子5

第一步：部分解密

首先，我们消除k1和k2部分：

k1 = E1 // 35  # k1 = 10780352757215323979
k2 = E2 // 35  # k2 = 16035342615763948231

# 验证k1和k2与phi互质
assert gmpy2.gcd(k1, phi1) == 1
assert gmpy2.gcd(k2, phi2) == 1

# 计算k1和k2的模逆
d1 = gmpy2.invert(k1, phi1)
d2 = gmpy2.invert(k2, phi2)

# 部分解密
m35_mod_n1 = pow(c1, d1, n1)  # 得到 m^35 mod n1
m35_mod_n2 = pow(c2, d2, n2)  # 得到 m^35 mod n2

现在我们有了：

m^35 ≡ m35_mod_n1 (mod n1)
m^35 ≡ m35_mod_n2 (mod n2)

第二步：利用同余性质构造方程组

这是本题最精妙的部分。我们利用同余的传递性：

对于任意整数a和b，如果 a ≡ b (mod P×Q)，则必然有：

a ≡ b (mod P)
a ≡ b (mod Q)

因此，从 m^35 ≡ m35_mod_n1 (mod P×Q1)，我们可以得到：

m^35 ≡ m35_mod_n1 (mod P)
m^35 ≡ m35_mod_n1 (mod Q1)

同理，从 m^35 ≡ m35_mod_n2 (mod P×Q2)，可以得到：

m^35 ≡ m35_mod_n2 (mod P)
m^35 ≡ m35_mod_n2 (mod Q2)

注意到 m^35 在模P下有两个来源的信息。根据同余的相乘性质：

如果 a ≡ b (mod m) 且 c ≡ d (mod m)
则 a×c ≡ b×d (mod m)

因此：

(m^35) × (m^35) ≡ m35_mod_n1 × m35_mod_n2 (mod P)
即 m^70 ≡ m35_mod_n1 × m35_mod_n2 (mod P)

现在我们有三个独立的同余方程：

m^35 ≡ m35_mod_n1 (mod Q1)
m^35 ≡ m35_mod_n2 (mod Q2)
m^70 ≡ m35_mod_n1 × m35_mod_n2 (mod P)

为什么要构造m^70而不是m^35？

这是一个精妙的技巧。虽然我们在P处得到的是m^70，但通过后续的中国剩余定理和因子分解处理，这个额外的35次方最终会被巧妙地消除。

关键观察：

• Q1、Q2、P是三个不同的大素数
• 它们两两互质，可以使用中国剩余定理
• 最终我们要处理35 = 5×7，额外的35次方可以在处理7和5时被吸收

第三步：使用中国剩余定理

# 构造三个同余方程的右侧
c1_mod_q1 = m35_mod_n1 % Q1
c2_mod_q2 = m35_mod_n2 % Q2
c3_mod_p = (m35_mod_n1 * m35_mod_n2) % P

# 使用中国剩余定理求解
result = chinese_remainder([Q1, Q2, P], [c1_mod_q1, c2_mod_q2, c3_mod_p])

这个result是什么？它满足：

result ≡ c1_mod_q1 (mod Q1)
result ≡ c2_mod_q2 (mod Q2)
result ≡ c3_mod_p (mod P)

第四步：构造新的RSA系统

现在我们构造一个新的RSA系统：

n_new = Q1 * Q2
c_m = result % n_new

在这个新系统中，由于Q1和Q2都是1024位的大素数，我们可以更容易地处理35 = 5×7的问题。

第五步：处理因子7

phi_new = (Q1 - 1) * (Q2 - 1)

# 验证7与phi_new互质
assert gmpy2.gcd(7, phi_new) == 1

# 求7的模逆
d_7 = gmpy2.invert(7, phi_new)

# "解密"7次方
m5 = pow(c_m, d_7, n_new)

这一步我们得到了m^5（在模n_new意义下）。

第六步：开5次方

由于FLAG只有42字节（336位），而n_new是2048位，所以 m^5 << n_new。这意味着m^5 mod n_new就等于整数意义下的m^5，可以直接开方：

# 直接开5次方
flag_result = gmpy2.iroot(m5, 5)
flag_long = flag_result[0]
is_perfect = flag_result[1]

print(f"是否为完全开方: {is_perfect}")  # True

# 转换为字节
flag = long_to_bytes(int(flag_long))
print(f"FLAG: {flag.decode()}")

成功得到：

FLAG: flag{27dab675-9e9b-4c1f-99ab-dd9fe49c190a}

验证正确性

最重要的验证是反向加密：

m = bytes_to_long(flag)

# 验证c1
c1_verify = pow(m, E1, n1)
assert c1_verify == c1
print("验证通过: pow(FLAG, E1, n1) == c1")

# 验证c2
c2_verify = pow(m, E2, n2)
assert c2_verify == c2
print("验证通过: pow(FLAG, E2, n2) == c2")

完全匹配！证明我们的解法完全正确。

这个方法为什么有效？

让我们回顾整个过程的数学原理：

1. 部分解密：通过消除与φ互质的k1和k2，将问题从 m^(35k) 降到 m^35
2. 同余拆分：利用”mod (P×Q) → mod P 且 mod Q”的性质，将大模数的同余方程拆分为多个小模数的方程
3. 信息整合：通过同余相乘性质，在P处构造了m^70的信息（虽然是m^70而不是m^35，但这个技巧性的构造在后续步骤中会被妥善处理）
4. CRT重组：使用中国剩余定理，将三个独立的同余方程合并为一个在Q1×Q2系统中的方程
5. 因子分解：在新系统中，35 = 5×7的两个因子都可以被处理：

• 因子7：与φ(Q1×Q2)互质，可以求模逆
• 因子5：由于消息小，可以直接开方

这个解法展示了数论在密码学攻击中的强大威力。通过灵活运用同余性质、中国剩余定理和因子分解，我们将一个看似无解的问题转化为可解的形式。

完整解题代码

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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import gmpy2
from Crypto.Util.number import *
from functools import reduce

# ========== 辅助函数 ==========

def next_prime(num: int) -> int:
    """获取下一个素数"""
    num = num + 2 if num % 2 else num + 1
    while not isPrime(num):
        num += 2
    return num

def chinese_remainder(modulus, remainders):
    """中国剩余定理求解"""
    Sum = 0
    prod = reduce(lambda a, b: a*b, modulus)
    for m_i, r_i in zip(modulus, remainders):
        p = prod // m_i
        Sum += r_i * (inverse(p, m_i) * p)
    return Sum % prod

# ========== 题目数据 ==========

# 第一部分数据
n = 1605247600724752598798254639224215706171506359654961357324428027985787942008103766562745464838961569081446916113769517713344420113584254259000172572811154232107339480903672251992191997458469905064423618888336088652352540882576826988355783159237971043770132628344798937353150930071309347972804118952814447576207066147031238749098842662046825743988208813903138796789940911515825517078554074496474819128789835309636804325132602557092847746454786387067599510769382078521691609970320528531270474091713477040343897269903489441410062592732302402854035415438078656688806905350495825334584533345448091335565792091890185673190424063
c = 751639057610677013264061431434189083017589908118307247217007533938435229431015858783222167911772848893015518607229280589985711010766459396989232072512314594917029375221335361209036112742388866873824163350886610514973038316512032459352053158417705406031466332440378871927174731975794579894912999936641163063898365134788537389162378185448090279397717831977803284480743612393591614284972981435749362255654561121758163485884075260156288337176713756471879489767416836868661153693157792733142765671887792303181376620864506386820826866340907593080654521498766421056474652652337037121881207188033108746890998208582406826010121861

# 第二部分数据
ns = [15863230586500684911356384742123404120213699052018048588650392009927565369685497256344682150189923131009586323640507773706997704860898682946308031020361302334248895233255911348365179153799197341744863134926804603973507415697810440916305092395180382239729550833607847524005391137474497849077097574452115379368463540087172800902210822143687014813631366360652583216269138116785489485772437870528892032119729929607857459621078790511144060710035933887337208301078892163837203412081114510143406013892393607932596921308889058909544584619676380766485493114814753878272881866907210235681877689493671668534251778397658670518117, 14144098469438619358682652828507744381697293556670717685553585719665002440476256008471235313826051740009083510860714991201047915737216102220242621674841600987122005914542061963618272275986835928673920375768272390912778741502655909281390948606467847118377641357547931472588836726339758576038273820470879637555458446243401248151675266602656677360819563744765522495640821496694918515669243614141704744848980746101569785439728585144841655665959389460512628800782742764147773150430552859331269667626942993392101897661719871375721143240270211821269260950380944670195863016621594387236339317938305273510719419578308449465183, 27563822879593503938377821960427219022565215631856333510782568496016547757945464794632272818101891677705256471714805217606503652132995136255720639088424576003650628211271025648183600635145895528466199068640094470078526413324708028578289949241288828542143203769199399500669311878391255837977932634772778594526940501234736059441483897017015324765266787399950699732518347518591167932031031320265136158304460199654008895095274754918153773566824931440342525688741289235153882699461549523425169846266597156773535163599640189457171272058311480951820887261040891344076039474315985825984444520336790670313179493074014037981261]
cs = [3833095607830862948079097323254872789586576953317671099752083261949616608759231291050566542764984974722790226120399722937104503590740358249900089784508490830379531632752169777949200718567033018577184658177019404903817920024468923715441355404672443007723525750768430895425376124679225715687382380114628103058312176343693900115638265002657622618744666247132114654135429040069316368839938881716554901593031901272992940200484460436193699175500376368456706998564064693820008778900344357745691652875500810447147088715289581351501876012044611990972521570253106671158207677490849249612002954497927762168699886110455354481924, 1502420121177211156091634258259634977709023894278792755694473756163084431123774101512866316989917922052023168401167212284219907272528117024670443698990238243030221117004372456475521502350404137469088570170885409265567084376069256924135270283335242133163303599239181417949980292944203204296598188175632723968779672994090788585343302473442389865459398142634104331743517384589200789331489394375604801951994831647339839112698394141328178967516636452592385248135340133712522135715943787590172334743893259621909532456281362868290556461907936774231166936915669816509378419892149164552548131776979706381641477878931403040942, 8992204063713908492214256291861339175525948946919629972908439132005643626148678347198381531633907182877152728077958345519083406637446972079387161726967295886447791613166577391233866583354793842121902234644830640050181130381996083089350911224037154798259291124104894554037604500881250119806371348673833105103600782286898276354573884788251542211434143476774391457587885772379990104835187104619922442613860682792470389490804228050671124495925536024571104944112397143299499508504917890140939438891891453283594000764399193028606955089853654071198909973555844004685149713774167524224100487937899126480545681565581673958854]

# 第四部分数据
n1 = 21655617838358037895534605162358784326495251462447218485102155997156394132443891540203860915433559917314267455046844360743623050975083617915806922096697304603878134295964650430393375225792781804726292460923708890722827436552209016368047420993613497196059326374616217655625810171080545267058266278112647715784756433895809757917070401895613168910166812566545593405362953487807840539425383123369842741821260523005208479361484891762714749721683834754601596796707669718084343845276793153649005628590896279281956588607062999398889314240295073524688108299345609307659091936270255367762936542565961639163236594456862919813549
n2 = 24623016338698579967431781680200075706241014384066250660360949684385831604822817314457973559632215801205780786144608311361063622813017396858888436529116737754653067203843306015767091585697803364656624926853551997229897087731298797904208292585562517602132663331748784390752958757661484560335406769204491939879324079089140420467301773366050084810282369044622442784113688062220370531522036512803461607049619641336524486507388232280683726065679295742456158606213294533956580462863488082028563360006966912264908424680686577344549034033470952036766850596897062924137344079889301948258438680545785139118107899367307031396309
c1 = 2615722342860373905833491925692465899705229373785773622118746270300793647098821993550686581418882518204094299812033719020077509270290007615866572202192731169538843513634106977827187688709725198643481375562114294032637211892276591506759075653224150064709644522873824736707734614347484224826380423111005274801291329132431269949575630918992520949095837680436317128676927389692790957195674310219740918585437793016218702207192925330821165126647260859644876583452851011163136097317885847756944279214149072452930036614703451352331567857453770020626414948005358547089607480508274005888648569717750523094342973767148059329557
c2 = 6769301750070285366235237940904276375318319174100507184855293529277737253672792851212185236735819718282816927603167670154115730023644681563602020732801002035524276894497009910595468459369997765552682404281557968383413458466181053253824257764740656801662020120125474240770889092605770532420770257017137747744565202144183642972714927894809373657977142884508230107940618969817885214454558667008383628769508472963039551067432579488899853537410634175220583489733111861415444811663313479382343954977022383996370428051605169520337142916079300674356082855978456798812661535740008277913769809112114364617214398154457094899399

# ========== 第一步：求解E1 ==========

print("[*] 步骤1：求解E1")
e = 65537
for k in range(2**15, 2**16):
    if isPrime(k):
        p_estimate = gmpy2.iroot(n // k, 2)[0]
        q = next_prime(k * p_estimate + 38219)
        if n % q == 0:
            break

p = n // q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
E1 = pow(c, d, n)
print(f"[+] E1 = {E1}")

# ========== 第二步：求解E2 ==========

print("[*] 步骤2：求解E2")
e2 = 89
m_e = chinese_remainder(ns, cs)
E2 = gmpy2.iroot(m_e, e2)[0]
print(f"[+] E2 = {E2}")

# ========== 第三步：求解P ==========

print("[*] 步骤3：求解P")
P = gmpy2.gcd(n1, n2)
Q1 = n1 // P
Q2 = n2 // P
print(f"[+] 已获取 P, Q1, Q2")

# ========== 第四步：求解FLAG ==========

print("[*] 步骤4：求解FLAG")

# 计算欧拉函数
phi1 = (P - 1) * (Q1 - 1)
phi2 = (P - 1) * (Q2 - 1)

# 部分解密
k1 = E1 // 35
k2 = E2 // 35
d1 = gmpy2.invert(k1, phi1)
d2 = gmpy2.invert(k2, phi2)
m35_mod_n1 = pow(c1, d1, n1)
m35_mod_n2 = pow(c2, d2, n2)

# 构建同余方程组
c1_mod_q1 = m35_mod_n1 % Q1
c2_mod_q2 = m35_mod_n2 % Q2
c3_mod_p = (m35_mod_n1 * m35_mod_n2) % P

# 使用中国剩余定理
result = chinese_remainder([Q1, Q2, P], [c1_mod_q1, c2_mod_q2, c3_mod_p])
n_new = Q1 * Q2
c_m = result % n_new

# 处理35 = 5 * 7
phi_new = (Q1 - 1) * (Q2 - 1)
d_7 = gmpy2.invert(7, phi_new)
m5 = pow(c_m, d_7, n_new)

# 开5次方
flag_long = gmpy2.iroot(m5, 5)[0]
flag = long_to_bytes(int(flag_long))

print(f"[+] FLAG: {flag.decode()}")

# ========== 验证 ==========

print("[*] 验证解密结果")
m = bytes_to_long(flag)
assert pow(m, E1, n1) == c1
assert pow(m, E2, n2) == c2
print("[+] 验证成功！")

知识点总结与安全启示

通过这道题目，我们学习了多个重要的RSA攻击技术和安全原则。

1. 弱密钥生成的危害

漏洞：素数生成过程中引入可预测的小参数

攻击：暴力枚举小参数空间

教训：

• 密钥生成的每个步骤都需要足够的熵
• 不要在素数生成中引入任何可预测的关系
• 使用经过验证的密码学库，而不是自己实现

现实案例：2012年，研究人员发现互联网上约0.2%的RSA公钥可以被分解，主要原因是随机数生成器的熵不足。

2. 低加密指数攻击（Hastad攻击）

漏洞：同一明文使用相同小指数在多个模数下加密

攻击：中国剩余定理 + 开根

防御：

• 使用安全的填充方案（如OAEP）
• 每次加密前添加随机性
• 避免在多个系统中使用相同的明文和参数

理论基础：当k个加密满足 k ≥ e 且 m^e < ∏ni 时，可以恢复m

3. 共模攻击

漏洞：多个RSA模数共享素因子

攻击：欧几里得算法求最大公约数

防御：

• 确保每个密钥对使用独立的素数
• 使用高质量的随机数生成器
• 定期进行密钥审计

检测方法：收集大量公钥，计算它们的两两最大公约数

4. 非标准RSA的处理

问题：当 gcd(e, φ(n)) > 1 时，标准RSA解密失效

解决方案：

• 因子分解：将e分解为互质因子的乘积
• 同余变换：利用同余性质拆分和重组方程
• 中国剩余定理：整合多个信息源
• 灵活处理：针对具体问题设计特殊方法

深层含义：这提醒我们，密码学不仅仅是套用公式，更需要深入理解数学原理，才能应对各种非标准情况。

5. 中国剩余定理的威力

中国剩余定理在本题中多次出现：

• 用于恢复E2（低指数攻击）
• 用于整合m^35的信息（FLAG解密）

核心思想：将大问题分解为小问题，分别求解后再整合

应用场景：

• 秘密分享方案
• 快速模运算（RSA-CRT）
• 多方安全计算

RSA安全实践建议

基于本题的分析，我们总结以下RSA使用的最佳实践：

密钥生成

1. 素数选择：

• p和q长度相近（相差不超过几位）
• p和q独立生成，无任何数学关系
• 使用密码学安全的随机数生成器（CSPRNG）

1. 参数验证：

• 验证 |p-q| 足够大（防止Fermat分解）
• 验证 p-1 和 q-1 有大素因子（防止Pollard p-1算法）
• 验证 gcd(e, φ(n)) = 1

加密操作

1. 填充方案：必须使用OAEP或其他安全的填充方案，永远不要使用”教科书RSA”
2. 参数选择：

• 模数长度至少2048位（推荐3072或4096位）
• 公钥指数通常使用65537（0x10001）

1. 消息处理：

• 对称加密 + RSA封装密钥（混合加密）
• 不要直接用RSA加密大量数据

密钥管理

1. 密钥独立性：每个应用使用独立的密钥对
2. 定期更换：建立密钥轮换机制
3. 安全存储：私钥加密存储，限制访问权限

总结

本文通过深入分析一道综合性的CTF题目，系统地探讨了RSA加密算法的多个攻击面。从弱密钥生成到低指数攻击，从共模攻击到非标准RSA的特殊处理，每一个环节都展现了密码学的数学之美和实用价值。

这道题目的设计充分体现了”牵一发而动全身”的密码学特点：任何一个环节的微小漏洞都可能导致整个系统的崩溃。同时，最后一关的非标准RSA处理也告诉我们，扎实的数学基础和灵活的思维方式在密码学研究中至关重要。

对于密码学学习者来说，这道题目不仅是一次技术挑战，更是一次深入理解RSA数学原理的机会。只有真正理解了欧拉定理、同余性质、中国剩余定理等基础概念，才能在面对复杂问题时游刃有余。

对于系统开发者来说，这道题目是一个警示：永远不要自己实现密码学算法，始终使用经过验证的密码学库，并严格遵循安全最佳实践。密码学的安全性不仅取决于算法本身，更取决于实现的每一个细节。

最后，希望本文能够帮助读者深入理解RSA密码系统的工作原理和潜在风险，在今后的学习和工作中更加重视密码学安全，为构建更安全的信息系统贡献力量。

---

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：破镜安全 破镜安全 破镜安全《simpleRSA – 深入浅出的RSA密码学攻击实战》