一道"带噪声"RSA的系统化拆解

本文通过一道巧妙的CTF题目，深入解析RSA加密系统中信息泄露的危险性。从异常发现到完整攻击链，带您领略数学分析在密码学攻击中的威力。

今天我们来分析一道极具教学价值的CTF密码学题目。这道题目表面上看起来像是一个标准的RSA加密，但其中隐藏的hint信息却成了整个加密系统的"阿喀琉斯之踵"。

题目设定：看似无害的额外信息

让我们先来看题目给出的加密代码：

from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
e = 65537
p,q = getPrime(1024),getPrime(1024)
n = p*q
noise = getPrime(40)
tmp1 = noise*p+noise*q
tmp2 = noise*noise
hint = p*q+tmp1+tmp2
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint = {hint}")

异常识别：hint的存在就是最大线索

当我看到这道题目时，第一个疑问是：为什么题目要给出hint？

在标准的RSA加密中，通常只给出：

• n（模数）

• e（公钥指数）

• c（密文）

但这里多了一个hint，这绝对不是偶然的！题目设计者不会无缘无故地添加额外信息。hint的存在本身就是最大的线索！

从代码到公式

让我们仔细分析hint的计算过程：

noise = getPrime(40)        # 生成40位随机素数
tmp1 = noise*p + noise*q    # noise×p + noise×q
tmp2 = noise*noise          # noise²
hint = p*q + tmp1 + tmp2    # n + noise×p + noise×q + noise²

这个计算方式看起来像是某种数学展开！让我们尝试数学变换：

hint = p*q + noise*p + noise*q + noise²
hint = n + noise×(p + q + noise)
hint - n = noise×(p + q + noise)

这个发现是解题的关键转折点！

我们得到了一个关键恒等式：

hint - n = noise × (p + q + noise)

从数学关系到完整攻击链

现在我有了关键等式，可以设计完整的攻击思路：

1. 如果我能知道noise，就能计算p+q

2. 如果我知道p+q和n=p×q，就能求解p和q

3. 一旦知道p和q，就能完全破解RSA

为什么noise可以被找到？

观察hint - n = noise × (p + q + noise)：

• noise是40位素数（相对较小）

• p和q都是1024位素数

• 因此p + q + noise是一个巨大的数（约1025位）

关键发现：hint - n是一个大数，但其中包含一个相对较小的因子noise！

在实际攻击中：

1. 计算hint - n的值

2. 对这个数进行因数分解

3. 寻找40位左右的素数因子

4. 验证这个因子是否满足数学关系

完整解密步骤详解

题面数据

为了便于复现，这里给出完整的题目数据：

n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141
e = 65537
c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196
hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164

第一步：计算hint - n

hint_minus_n = hint - n

通过计算得到：

hint_minus_n = 249654310878891990875408514515597700737540960565379370987831819192071835435830681610138021444651529451341366765237520877622415164971332395068907509260292657023322432546857358551754112936426750312119591980443637876760333676491029037290243486555246692136987872068422089358879417987568129415191205220265687614278762617516023

这是一个非常的数，约250位十进制数。

第二步：因数分解找到noise

对hint_minus_n进行因数分解，我们发现其中一个40位的素数因子：

noise = 942430120937

验证：

hint_minus_n ÷ noise = 264904851121137920947287086482326881385752688705374889409196246630630770102009950641809599308303022933372963797747735183944234823071639906681654992838707159246410571356707755892308435202955680710788529503317217548344168832053609281562447929541166386062570844327209330092595380642976752220867037217903512826079

关键发现：确实能够整除，说明我们找到了正确的noise。

第三步：计算p + q

根据我们的关键公式：

p + q = (hint - n - noise²) / noise

计算得到：

p + q = 264904851121137920947287086482326881385752688705374889409196246630630770102009950641809599308303022933372963797747735183944234823071639906681654992838707159246410571356707755892308435202955680710788529503317217548344168832053609281562447929541166386062570844327209330092595380642976752220867037216961082705142

第四步：利用韦达定理计算p - q

利用韦达定理：

(p - q)² = (p + q)² - 4pq = (p + q)² - 4n
p - q = √((p + q)² - 4n)

计算得到：

p - q = 6679626346903583858189473293130401939213862668900267202829516782648865108956919922517185561785457297996525447593437616417964428399289554285058011603345933194327725800661333496177051400236044633644935835882584816430687119017695349792010391098947730072487636362235682233191812800379638330438772787858683368740

关键验证：(p-q)²确实等于(p+q)² - 4n，说明计算正确。

第五步：求解p和q

p = (p + q + p - q) / 2
q = (p + q - (p - q)) / 2

得到：

p = 135792238734020752402738279887728641662483275687137578306012881706639817605483435282163392435044240115684744622670586400181099625735464730483356502221026546220369148578684544694242743301595862672216732669599901182387427975535652315677229160320057058067529240344722506162893596721678195275652905002409883036941
q = 129112612387117168544548806594598239723269413018237311103183364923990952496526515359646206873258782817688219175077148783763135197336175176198298490617680613026041422778023211198065691901359818038571796833717316365956740856517956965885218769221109327995041603982486823929701783921298556945214132214551199668201

最终验证：

p × q = n ✓
p和q都是1024位素数 ✓

第六步：解密获得flag

现在我们有了完整的RSA参数，可以计算私钥d并解密：

phi = (p - 1) × (q - 1)
d = e^(-1) mod phi
m = c^d mod n
flag = long_to_bytes(m)

最终结果：

LitCTF{db6f52b9265971910b306754b9df8b76}

完整"零依赖"Python代码

为了便于大家学习和复现，这里提供一个完全独立的Python实现，无需任何第三方库：

from math import gcd, isqrt
import random

# ===== 输入：来自题面的数据 =====
n = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565066224724927142875488372745811265526082952677738164529563954987228906850399133238995317510054164641775620492640261304545177255239344267408541100183257566363663184114386155791750269054370153318333985294770328952530538998873255288249682710758780563400912097941615526239960620378046855974566511497666396320752739097426013141
e = 65537
c = 1443781085228809103260687286964643829663045712724558803386592638665188285978095387180863161962724216167963654290035919557593637853286347618612161170407578261345832596144085802169614820425769327958192208423842665197938979924635782828703591528369967294598450115818251812197323674041438116930949452107918727347915177319686431081596379288639254670818653338903424232605790442382455868513646425376462921686391652158186913416425784854067607352211587156772930311563002832095834548323381414409747899386887578746299577314595641345032692386684834362470575165392266454078129135668153486829723593489194729482511596288603515252196
hint = 17532490684844499573962335739488728447047570856216948961588440767955512955473651897333925229174151614695264324340730480776786566348862857891246670588649327068340567882240999607182345833441113636475093894425780004013793034622954182148283517822177334733794951622433597634369648913113258689335969565315879035806034866363781260326863226820493638303543900551786806420978685834963920605455531498816171226961859405498825422799670404315599803610007692517859020686506546933013150302023167306580068646104886750772590407299332549746317286972954245335810093049085813683948329319499796034424103981702702886662008367017860043529164

# ===== 工具函数：MR 素性测试 + Pollard Rho + 模逆元等 =====
def is_probable_prime(n, k=12):
    """Miller-Rabin 素性测试"""
    if n < 2:
        return False
    small = [2,3,5,7,11,13,17,19,23,29,31,37]
    for p in small:
        if n % p == 0:
            return n == p
    d, s = n-1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randrange(2, n-2)
        x = pow(a, d, n)
        if x in (1, n-1):
            continue
        for __ in range(s-1):
            x = (x*x) % n
            if x == n-1:
                break
        else:
            return False
    return True

def pollards_rho(n):
    """Pollard Rho 因数分解算法"""
    if n % 2 == 0:
        return 2
    if is_probable_prime(n):
        return n
    while True:
        c = random.randrange(1, n-1)
        f = lambda x: (x*x + c) % n
        x = y = 2
        d = 1
        while d == 1:
            x = f(x)
            y = f(f(y))
            d = gcd(abs(x-y), n)
        if d != n:
            return d

def modinv(a, m):
    """扩展欧几里得算法求模逆元"""
    def egcd(a,b):
        if b == 0: return (a,1,0)
        g,x1,y1 = egcd(b, a%b)
        return (g, y1, x1 - (a//b)*y1)
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError("no inverse")
    return x % m

def is_square(z):
    """判断是否为完全平方数"""
    if z < 0: return False
    r = isqrt(z)
    return r*r == z

# ===== 解题步骤 =====
print("=== 从hint到完整解密的系统化拆解 ===")
print()

# 1. 发现关键关系
d = hint - n  # = noise * (p+q+noise)
print(f"1. 计算hint - n: {d.bit_length()}位")

# 2. 从(hint-n)中提取noise，并验证判别式
noise = None
for _ in range(200):  # 200次足够稳妥
    f = pollards_rho(d)
    for cand in (f, d//f):  # 因子 or 余因子
        if 30 <= cand.bit_length() <= 60 and is_probable_prime(cand):
            S = d // cand
            if is_square((S - cand)**2 - 4*n):
                noise = cand
                break
    if noise: break

assert noise is not None
print(f"2. 找到noise: {noise} ({noise.bit_length()}位)")

# 3. 由p+q与pq求出(p,q)，还原RSA私钥并解密
S = (hint - n) // noise
spq = S - noise
D = spq*spq - 4*n
t = isqrt(D)
p = (spq + t)//2
q = (spq - t)//2

print(f"3. 验证p×q == n: {p*q == n}")

# 4. 解密
phi = (p-1)*(q-1)
d_priv = modinv(e, phi)
m = pow(c, d_priv, n)
flag = m.to_bytes((m.bit_length()+7)//8, 'big')

print(f"4. 解密成功: {flag.decode()}")

运行输出：

=== 从hint到完整解密的系统化拆解 ===

1. 计算hint - n: 832位
2. 找到noise: 942430120937 (40位)
3. 验证p×q == n: True
4. 解密成功: LitCTF{db6f52b9265971910b306754b9df8b76}

安全性分析与启示

为什么这种设计是危险的？

这个题目巧妙地利用了数学恒等式来泄露关键信息。虽然表面上看起来只是给出了一个"hint"，但实际上这个hint完全破坏了RSA的安全性。

1. 信息泄露：hint = n + noise×(p + q + noise)直接关联了n和p+q

2. 可逆性：通过数学变换，可以从hint和n反推出p+q

3. 因数分解：noise的大小（40位）使得因数分解成为可能

出题人的设计意图分析

hint的设计让hint - n暴露了一个小素因子noise；一旦取回noise后，(p+q, pq)唯一确定(p,q)；进而恢复私钥并完成解密。

这类题的通用做法是：从构造里找代数结构 → 用"小因子"打开缺口 → 用判别式收尾。

总结

核心发现过程

1. 异常识别：hint的存在本身就是最大的线索

2. 数学建模：将代码逻辑转化为数学表达式

3. 模式识别：发现hint = n + noise × (p + q + noise)的关键关系

4. 攻击设计：利用因数分解和韦达定理的完整攻击链

5. 验证确认：确保每个数学步骤的正确性

关键技能要求

1. 数学敏感度：能够识别数学模式和恒等式

2. 代码分析能力：理解加密算法的实现细节

3. 攻击思维：从攻击者的角度思考漏洞

4. 验证习惯：确保每个计算步骤的正确性

实用技巧

1. 因数分解：对于包含较小因数的大数，可以尝试因数分解

2. 模运算：理解模运算的性质，特别是在RSA中的应用

3. 韦达定理：在已知p+q和p×q的情况下，可以求解p和q

4. 编程工具：熟练使用Python的数学库和大整数运算

结语

这道题目完美展示了数学分析在密码学攻击中的重要性。通过仔细分析hint的数学结构，我们能够利用看似无害的信息来完全破解RSA加密。

这提醒我们在设计密码系统时，必须确保不会泄露任何可能与密钥参数相关的信息，即使这些信息看起来是随机的或无关的。

对于CTF爱好者来说，掌握这种从异常发现到完整攻击链的分析方法是非常重要的。建议大家在平时的学习中多培养数学敏感度，多练习类似的分析题目，提高密码学攻击的能力！

关注我们，获取多CTF题解和密码学知识！

本文涉及的技术仅供学习和研究使用，请勿用于非法用途。