CTF-RSA题目类型及解题思路详解

一、RSA算法概述

1. RSA加密算法介绍

RSA是一种非对称加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman在1977年提出，名称来自三人姓氏首字母。

2. RSA算法原理

2.1 算法基础-数论知识

• 互质关系：两个正整数除了1以外没有其他公因数
• 欧拉函数φ(n)：小于等于n且与n互质的正整数个数
• 模运算：求余数的运算
• 费马小定理：若p是质数且a与p互质，则a^(p-1) mod p = 1
• 欧拉定理：若a与n互质，则a^φ(n) mod n = 1

2.2 密钥生成过程

1. 选择两个大质数p和q
2. 计算n = p × q和φ(n) = (p-1)×(q-1)
3. 选择整数e，1 < e < φ(n)且与φ(n)互质
4. 计算d，使得e × d mod φ(n) = 1

2.3 加密过程

c = m^e mod n

2.4 解密过程

m = c^d mod n

二、CTF-RSA题目类型及解题思路

2.1 分解n得到p和q

适用情况：题目给出n、c和e的值

解题方法：

1. 爆破：当n较小时编写脚本爆破
2. 在线分解：使用factordb.com等网站
3. yafu工具：
   • 小数字：.\yafu-x64.exe "factor(n)"
   • 大数字：.\yafu-x64.exe "factor(@)" -batchfile data.txt

示例代码：

import gmpy2
from Crypto.Util.number import long_to_bytes

p = 768780063730500942699787302253
q = 813910604866037851538498611597
c = 118795719073790634455854187484104547013000179946116068066473
e = 0x10001

n = p * q
phi_n = (q-1)*(p-1)
d = gmpy2.invert(e, phi_n)
m = pow(c, d, n)
print(long_to_bytes(m))

2.2 低加密指数攻击(e很小)

适用情况：e值很小(如3)，n值很大

攻击原理：c = m^e + kn，爆破k直到c-kn可开e次方

示例代码：

import gmpy2
import binascii

n = gmpy2.mpz(133024413746207623787624696996450696028790885302997888417950218110624599333002677651319135333439059708696691802077223829846594660086912881559705074934655646133379015018208216486164888406398123943796359972475427652972055533125099746441089220943904185289464863994194089394637271086436301059396682856176212902707)
e = 3
c = gmpy2.mpz(1402983421957507617092580232325850324755110618998641078304840725502785669308938910491971922889485661674385555242824)

k = 0
while True:
    res = gmpy2.iroot(k*n + c, e)
    if res[1] == True:
        print(binascii.unhexlify(hex(res[0])[2:]))
        break
    k += 1

2.3 低指数加密广播攻击

适用情况：多组不同的n和c，相同的e且很小

攻击原理：利用中国剩余定理(CRT)求解同余方程组

示例代码：

from sympy.ntheory.modular import crt
import gmpy2
from Crypto.Util.number import long_to_bytes

N1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)

N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)

N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)

e = 3
n = [N1, N2, N3]
c = [c1, c2, c3]

resultant, mod = crt(n, c)
value, is_perfect = gmpy2.iroot(resultant, e)
print(long_to_bytes(value))

2.4 dp泄露

适用情况：题目给出dp = d mod (p-1)

攻击原理：利用dp和e的关系求解

示例代码：

import gmpy2

e = 65537
n = 159054389158529397912052248500898471690131016887756654738868415880711791524038820158051782236121110394481656324333254185994103242391825337525378467922406901521793714621471618374673206963439266173586955520902823718942484039624752828390110673871132116507696336326760564857012559508160068814801483975094383392729
c = 37819867277367678387219893740454448327093874982803387661058084123080177731002392119369718466140559855145584144511271801362374042596420131167791821955469392938900319510220897100118141494412797730438963434604351102878410868789119825127662728307578251855605147607595591813395984880381435422467527232180612935306
dp = 947639117873589776036311153850942192190143164329999603361788468962756751774397111913170053010412835033030478855001898886178148944512883446156861610917865

for x in range(1, e):
    if (e*dp % x == 1):
        p = (e*dp-1)//x + 1
        if (n % p != 0):
            continue
        q = n//p
        phin = (p-1)*(q-1)
        d = gmpy2.invert(e, phin)
        m = pow(c, d, n)
        if (len(hex(m)[2:]) % 2 == 1):
            continue
        print(bytes.fromhex(hex(m)[2:]))

2.5 dp,dq泄露

适用情况：同时给出dp和dq

攻击原理：

m1 = c^dp mod p
m2 = c^dq mod q
m = (((m1-m2)*I)%p)*q + m2
其中I为对pq求逆元

示例代码：

import gmpy2

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

I = gmpy2.invert(q, p)
m1 = pow(c, dp, p)
m2 = pow(c, dq, q)
m = (((m1-m2)*I)%p)*q + m2
print(bytes.fromhex(hex(m)[2:]))

2.6 e与φ(n)不互素

适用情况：e和φ(n)有公因数

解题思路：

1. 计算gcd(e, φ(n)) = t
2. 计算d = invert(e//t, φ(n))
3. 解密得到m^t，再开t次方

示例代码：

from Crypto.Util.number import *
from gmpy2 import gcd, invert, iroot

p = 86053582917386343422567174764040471033234388106968488834872953625339458483149
q = 72031998384560188060716696553519973198388628004850270102102972862328770104493
c = 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123
e = 74

n = p*q
phi = (p-1)*(q-1)
t = gcd(e, phi)
d = invert(e//t, phi)
m2 = pow(c, d, n)
m = iroot(m2, 2)[0]
print(long_to_bytes(m))

2.7 小明文攻击

适用情况：明文m很小，e也不大

攻击原理：直接对c开e次方

示例代码：

from gmpy2 import iroot
import sympy
import binascii

flag = 25166751653530941364839663846806543387720865339263370907985655775152187319464715737116599171477207047430065345882626259880756839094179627032623895330242655333
n = 134109481482703713214838023035418052567000870587160796935708584694132507394211363652420160931185332280406437290210512090663977634730864032370977407179731940068634536079284528020739988665713200815021342700369922518406968356455736393738946128013973643235228327971170711979683931964854563904980669850660628561419

def small_m_atk(c, n):
    e = 2
    while e < 2**10:
        i = 0
        while i < 10:
            res = iroot(c + i*n, e)
            if res[1]:
                return res[0]
            i += 1
        e = sympy.nextprime(e)
        
print(binascii.unhexlify(hex(small_m_atk(flag, n))[2:]))

2.8 共模攻击

适用情况：相同的明文用不同的公钥加密，且n相同

攻击原理：利用扩展欧几里得算法找到x,y使e1x + e2y = 1，然后计算m = (c1^x * c2^y) mod n

示例代码：

import gmpy2
import hashlib
from Crypto.Util.number import long_to_bytes

def attack(n, e1, e2, c1, c2):
    def extended_gcd(a, b):
        if b == 0:
            return a, 1, 0
        else:
            g, x, y = extended_gcd(b, a % b)
            return g, y, x - (a // b) * y
    
    g, x, y = extended_gcd(e1, e2)
    if g != 1:
        raise ValueError("e1 and e2 must be coprime")
    
    if x < 0:
        c1 = gmpy2.invert(c1, n)
        x = -x
    if y < 0:
        c2 = gmpy2.invert(c2, n)
        y = -y
    
    m = (pow(c1, x, n) * pow(c2, y, n)) % n
    return m

p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837

phi = (p-1)*(q-1)
e1 = pow(3, 65537, phi)
e2 = pow(5, 65537, phi)
e3 = pow(7, 65537, phi)

m = attack(p*q, e2, e3, c2, c3)
print(long_to_bytes(m))

2.9 共享素数

适用情况：两个n有相同的素数因子

攻击原理：计算gcd(n1, n2)得到共享素数p

示例代码：

from Crypto.Util.number import *

p = 7552850543392291177573335134779451826968284497191536051874894984844023350777357739533061306212635723884437778881981836095720474943879388731913801454095897
a = list(map(int, open('output.txt').read().splitlines()))
c = 38127524839835864306737280818907796566475979451567460500065967565655632622992572530918601432256137666695102199970580936307755091109351218835095309766358063857260088937006810056236871014903809290530667071255731805071115169201705265663551734892827553733293929057918850738362888383312352624299108382366714432727
e = 65537

for i in a[::-1]:
    n = int(i)
    q = n//p
    d = inverse(e, (p-1)*(q-1))
    m = pow(c, d, n)
    c = m

print(long_to_bytes(m))

2.10 维纳攻击

适用情况：d相对于n较小(d < 1/3 n^(1/4))

攻击原理：利用连分数展开逼近d

示例代码：

import gmpy2
import libnum

def continuedFra(x, y):
    cf = []
    while y:
        cf.append(x//y)
        x, y = y, x%y
    return cf

def gradualFra(cf):
    numerator = 0
    denominator = 1
    for x in cf[::-1]:
        numerator, denominator = denominator, x*denominator + numerator
    return numerator, denominator

def solve_pq(a, b, c):
    par = gmpy2.isqrt(b*b - 4*a*c)
    return (-b + par)//(2*a), (-b - par)//(2*a)

def getGradualFra(cf):
    gf = []
    for i in range(1, len(cf)+1):
        gf.append(gradualFra(cf[:i]))
    return gf

def wienerAttack(e, n):
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for d, k in gf:
        if k == 0:
            continue
        if (e*d - 1)%k != 0:
            continue
        phi = (e*d - 1)//k
        p, q = solve_pq(1, n-phi+1, n)
        if p*q == n:
            return d

n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
e = 11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
c = 4218884541887711839568615416673923480889604461874475071333225389075770098726337046768413570546617180777109293884545400260353306419150066928226964662256930702466709992997796154415790565112167663547017839870351167884417142819504498662037048412313768450136617389372395690363188005647619061128497371121168347810294424378348301835826084732747005110258557662466626720961279087145559906371505117097599774430970980355531235913439823966628008554872896820907555353892843539526041019103819804854883231421963308265517622470779089941078841902464033685762524196275032288319744157255628189204988632871276637699312750636348750883054

d = wienerAttack(e, n)
m = pow(c, d, n)
print(libnum.n2s(m).decode())

三、总结

本文详细介绍了CTF中常见的RSA题目类型及解题思路，包括：

1. 分解n得到p和q
2. 低加密指数攻击
3. 低指数加密广播攻击
4. dp泄露攻击
5. dp,dq泄露攻击
6. e与φ(n)不互素情况
7. 小明文攻击
8. 共模攻击
9. 共享素数攻击
10. 维纳攻击

每种攻击方法都附有示例代码和解题思路，希望能帮助CTF选手更好地理解和解决RSA相关题目。