CTF密码学实战：手把手教你用Python脚本破解5种常见RSA攻击（附完整代码）

在CTF竞赛的密码学挑战中，RSA算法因其数学原理的优雅性和实际应用的广泛性，成为了出题人的宠儿。对于刚接触Crypto方向的选手来说，理解RSA原理只是第一步，更重要的是能够在实战中快速识别攻击场景并编写有效的破解脚本。本文将带你深入五种最常见的RSA攻击方式，从环境配置到代码调试，提供可直接复用的Python解决方案。

1. 环境准备与基础工具

在开始之前，我们需要配置好Python环境并安装必要的密码学库。推荐使用Python 3.8+版本，这是大多数CTF竞赛平台支持的标准环境。

核心依赖库包括：

  • gmpy2 ：提供高精度数学运算支持
  • pycryptodome ：包含 Crypto.Util.number 等密码学工具
  • sympy ：可选，用于更复杂的数学运算

安装命令：

pip install gmpy2 pycryptodome sympy

常见问题处理：

  1. gmpy2安装失败 ：在Linux/macOS上需要先安装GMP库： 
    # Ubuntu/Debian
sudo apt install libgmp-dev
# macOS
brew install gmp
  2. Windows环境问题 ：可以尝试从https://www.lfd.uci.edu/~gohlke/pythonlibs/下载预编译的whl文件

基础工具函数：

from Crypto.Util.number import bytes_to_long, long_to_bytes
from gmpy2 import mpz, invert, powmod, gcd

def read_rsa_params(filepath):
    """从文件读取RSA参数(N,e,c等)"""
    params = {}
    with open(filepath) as f:
        for line in f:
            if ':' in line:
                key, val = line.split(':', 1)
                params[key.strip()] = int(val.strip())
    return params

2. 因数分解攻击实战

当RSA模数N较小时（通常小于1024位），可以直接通过分解N来恢复私钥。这是CTF中最基础的RSA攻击方式。

2.1 攻击原理

RSA的安全性依赖于大整数分解的困难性。当N=p*q能被分解时，攻击者可以计算：

φ(N) = (p-1)*(q-1)
d ≡ e⁻¹ mod φ(N)

2.2 实战代码

def factorize_attack(N, e, c):
    from gmpy2 import is_prime
    
    # 尝试在线数据库分解
    try:
        p, q = factor_from_db(N)  # 需要实现factor_from_db函数
    except:
        # 本地分解尝试（仅适用于小N）
        p = pollards_rho(N)  # 需要实现Pollard's Rho算法
        q = N // p
    
    assert p * q == N and is_prime(p) and is_prime(q)
    
    phi = (p-1)*(q-1)
    d = invert(e, phi)
    m = powmod(c, d, N)
    return long_to_bytes(m)

# 示例：BUUCTF因数分解题解
N = 30578675145816634962204467309994126955968568987449100734690153203822106214253
e = 65537
c = 21852302692500130397613525359228623357937591161147471234750883538062728964508

print(factorize_attack(N, e, c))  # 输出: b'hello!Rsa'

2.3 优化技巧

  1. factordb查询 ：对于公开的N，可以优先查询http://factordb.com/
  2. 本地分解算法 ：
    • 试除法（适用于极小N）
    • Pollard's Rho算法（适用于中等大小N）
    • Williams' p+1算法

3. 共享素数攻击解析

当两个不同的RSA密钥使用了相同的素数时，可以通过计算gcd(N1,N2)来发现共享素数。

3.1 攻击场景

  • 同一系统生成多个密钥时使用了重复的随机数
  • CTF题目故意设置的漏洞

3.2 完整解决方案

def shared_prime_attack(n1, n2, e, c):
    # 计算最大公约数找到共享素数
    p = gcd(n1, n2)
    q1 = n1 // p
    q2 = n2 // p
    
    # 计算两个私钥
    d1 = invert(e, (p-1)*(q1-1))
    d2 = invert(e, (p-1)*(q2-1))
    
    # 双重解密
    m = powmod(powmod(c, d2, n2), d1, n1)
    return long_to_bytes(m)

# 羊城杯2021 Bigrsa示例
n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

print(shared_prime_attack(n1, n2, e, c))

4. 低加密指数攻击实践

当加密指数e很小（如3、5等）且明文m满足m^e < N时，可以直接对密文开e次方恢复明文。

4.1 攻击条件

  • e值很小（通常≤3）
  • 明文m较短，使得m^e不模N

4.2 自动化破解脚本

def low_exponent_attack(c, e, N=None):
    from gmpy2 import iroot
    
    if N is None:  # 完全不需要模数的情况
        m, exact = iroot(c, e)
        if exact:
            return long_to_bytes(m)
    
    # 可能需要尝试多个e值
    for possible_e in range(2, 6):
        m, exact = iroot(c, possible_e)
        if exact:
            return long_to_bytes(m)
    
    # 中国剩余定理扩展（多组密文情况）
    if isinstance(c, list) and isinstance(N, list):
        return crt_attack(c, N, e)
    
    raise ValueError("Attack failed - conditions not met")

# SWPUCTF 2021新生赛crypto5示例
c = 25166751653530941364839663846806543387720865339263370907985655775152187319464715737116599171477207047430065345882626259880756839094179627032623895330242655333
print(low_exponent_attack(c, 3))  # 输出: b'NSSCTF{because_i_like}'

5. 共模攻击深度解析

当相同的明文使用相同的N但不同的e加密，且e1和e2互质时，可以通过扩展欧几里得算法恢复明文。

5.1 数学原理

找到满足e1 s1 + e2 s2 = 1的整数s1,s2，则：

m = (c1^s1 * c2^s2) mod N

5.2 完整实现

def common_modulus_attack(c1, c2, e1, e2, N):
    from gmpy2 import gcdext
    
    # 计算贝祖系数
    g, s1, s2 = gcdext(e1, e2)
    assert g == 1  # 确保e1,e2互质
    
    # 处理可能的负数指数
    if s1 < 0:
        c1 = invert(c1, N)
        s1 = -s1
    if s2 < 0:
        c2 = invert(c2, N)
        s2 = -s2
    
    m = (powmod(c1, s1, N) * powmod(c2, s2, N)) % N
    return long_to_bytes(m)

# BJDCTF 2020示例
N = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
e1, e2 = 2767, 3659
c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

print(common_modulus_attack(c1, c2, e1, e2, N))

6. 广播攻击全面剖析

当相同的明文使用相同的e但不同的N加密（e较小），可以通过中国剩余定理(CRT)恢复明文。

6.1 攻击条件

  • 相同明文用(e,N1),(e,N2)...(e,Nk)加密
  • e等于密文数量k（最优情况）

6.2 高效实现

def broadcast_attack(c_list, n_list, e=None):
    from gmpy2 import iroot
    from functools import reduce
    
    if e is None:
        e = len(c_list)  # 常见情况e等于密文数量
    
    # 中国剩余定理实现
    N = reduce(lambda a,b: a*b, n_list)
    result = 0
    for c, n in zip(c_list, n_list):
        Ni = N // n
        inv = invert(Ni, n)
        result = (result + c * Ni * inv) % N
    
    # 开e次方
    m, exact = iroot(result, e)
    if not exact:
        raise ValueError("Exact root not found")
    
    return long_to_bytes(m)

# 鹤城杯2021 Crazy_Rsa_Tech示例
n_list = [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c_list = [62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]

print(broadcast_attack(c_list, n_list, e=9))

7. 实战调试技巧与常见问题

在实际CTF比赛中，RSA题目往往不会直接给出标准参数，需要选手从各种格式中提取。以下是一些实用技巧：

  1. 参数提取 ：

    • 从PEM文件读取： 
      from Crypto.PublicKey import RSA
with open('pubkey.pem') as f:
    key = RSA.import_key(f.read())
N, e = key.n, key.e
    • 处理JSON/文本格式： 
      import json
data = json.loads(open('output.txt').read())
N = data['modulus']

  2. 性能优化 ：

    • 对大整数运算使用gmpy2的mpz类型
    • 并行计算多个可能性（如尝试多个e值）

  3. 常见报错处理 ：

    • ValueError: invalid literal for int() with base 10 ：检查参数中是否有非数字字符
    • TypeError: pow() 3rd argument not allowed unless all arguments are integers ：确保所有参数为整数
    • ZeroDivisionError: invert() no inverse exists ：检查参数是否互质

  4. 调试建议 ：

    • 逐步验证中间结果
    • 对小规模测试用例先验证算法正确性
    • 使用断言检查关键条件
# 调试示例：验证私钥计算是否正确
p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537
d = invert(e, (p-1)*(q-1))
assert pow(pow(123456, e, p*q), d, p*q) == 123456

掌握这些RSA攻击技术后，你将能够解决CTF竞赛中80%以上的基础密码学挑战。真正的比赛题目往往会结合多种攻击方式或加入额外的混淆层，这时候需要灵活组合这些技术并发挥创造性思维。

# 密码学
Logo
亚马逊云科技技术品牌专区

更多推荐

主动推理-人工海马

2026年07月04日 00:21发言人00:00制造能够思考的机器是人类长久以来的梦想，但这到底意味着什么呢？智能的一个显著特性是能够泛化知识，并灵活地将其应用于新情况。这种泛化确实是现代机器学习的核心问题之一。在这段视频中，我们将探讨如何汲取海马体负责记忆和导航的大脑结构的生物学组织，来构建一个能够学习构建抽象和泛化的计算模型。我们将探索这个模型带给我们关于大脑自身及人工智能领域的启示。发言人

avatar 亚马逊云科技技术品牌专区

分布式事务尝试取消确认模式的具体实现步骤

首先需要事务协调器（Transaction Coordinator），负责协调整个分布式事务的流程，记录事务状态，并在必要时触发补偿操作。尝试取消确认模式（Try-Cancel-Confirm，简称TCC）作为一种补偿型分布式事务解决方案，通过业务逻辑层面的拆解，提供了更灵活的一致性实现方式。未来，随着事务中间件的成熟和云原生技术的发展，TCC模式的实施成本将进一步降低，应用场景也将更加广泛。Co

avatar 亚马逊云科技技术品牌专区
cover

WSaiOS：新一代模拟人工智能架构的理论基础与规范体系设计

avatar 亚马逊云科技技术品牌专区