RSA 加密体制破译
来源：“RSA 大礼包”——首届（2016）全国高校密码数学挑战赛 赛题三
截获数据处理
首先按照赛题描述的帧结构提取所有的截获数据：
1024bit 模数 N | 1024bit 加密指数 e | 1024bit 密文 m^e mod N
Frame0:
N = 90058705186558569935261948496132914380077312570281980020033760044382510933070450931241348678652103772768114420567119848142360867111065753301402088676701668212035175754850951897103338079978959810673297215370534716084813732883918187890434411552463739669878295417744080700424913250020348487161014643951785502867
e = 46786465362686334917265996843779843233606992585424976481745055335468678697948774988450305612127967926533923268260412557000125153569622340353246096040604284883505587337829322949633637609180797447754513992039018904786537115087888005528547900640339270052628915440787357271345416818313808448127098885767015748889
c = 48641173720475702278690317652676924796340996697567087705119344461991930773386153198223372579328462635803653561516674380209276666328375805315553713680858906705068657158073776194628700821011001144559278784795978097710145192236347629751116534400207288736776545247409895672030976932673010818369814246455196991083
--------
Frame1:
N = 92921790800705826977497755832938592891062287903332844896046168726101016067456726822505517352409138948392871113192427210529297191908638888388136391240683157994654207338463678065440899870434887094216772312358731142317774259942199808535233769089985063860828267808621928898445383706310204223006136919334252875849
e = 65537
c = 1626661141529320283833484152716550848856697186049377493478368799832043379420727509223318694347625977694500761460048670101820769656612419734057871562023463159698522348510157125720014700549254630959391701883372400982386084212421115166791728704867253734354874934210987301137512341070190760227227749365878233484
--------
Frame2:
N = 90252653600964453524559669296618135272911289775949194922543520872164147768650421038176330053599968601135821750672685664360786595430028684419411893316074286312793730822963564220564616708573764764386830123818197183233443472506106828919670406785228124876225200632055727680225997407097843708009916059133498338129
e = 65537
c = 39632263504870478574861695051251850807454294787974709214866410237055871793939895562441267574482198916367858789237648434983815369123479208726344716594227785308836601932181727610859898951190206345056426253251079929822424252271957269630987623886812686545521745791771387808772030614435314730783528512800343192265
--------
Frame3:
N = 92270627783020341903769877272635163757611737252302329401876135487358785338853904185572496782685853218459404423868889360808646192858060332110830962463986164014331540336037718684606223893506327126112739408023014900003600028654929488487584130630596342720833061628867179840913592694993869009133576053124769728363
e = 5
c = 83421434286602546493364204139182949897795123160498680670964040331447569764445309937195566103281638928183742488663157138572020817924561990979723444797045375101801354862472761507421896454904818874439231990567738173059815647539737800523632262742398190575822391771655932895657208471832891505814792263361394479317
--------
Frame4:
N = 90058705186558569935261948496132914380077312570281980020033760044382510933070450931241348678652103772768114420567119848142360867111065753301402088676701668212035175754850951897103338079978959810673297215370534716084813732883918187890434411552463739669878295417744080700424913250020348487161014643951785502867
e = 152206992575706893484835984472544529509325440944131662631741403414037956695665533186650071476146389737020554215956181827422540843366433981607643940546405002217220286072880967331118344806315756304650248634546597784597963886656422706197757265316981889118026978865295597135470735576032282694348773714479076093197
c = 19560634556305755550927540610989537766715902244072312818350844104485773927537226443429404190213856361759564153804627450805880512600339869169513348929194643809859468549718922965997647689203029517135396008631050292544022651948009392475583045438153697076529266662217519588521116539517972522591294232192817502376
--------
Frame5:
N = 99193711547257063160816850544214924340574358752670644615293764532335872088470223740970673347993652626497557387222167784182876395436088845281840169701654629849214222297784511349059698963212947299142320497759258889425182705042123217476724761095690092179821753840224757786599021225709340258545979566824267620959
e = 65537
c = 26054677793581772924866273737009673285775062802734786532404396138990264566536537921648515854012553861999940229349708989519156563830916553754762208466745321226835312974971739761769324569315525872096987367001543758380071859429619580182411498650200401467760546057912183435480924905200466941116258838789328064564
--------
Frame6:
N = 146839643970016464813197409569004275595828791825722617066607993001682901023784267554815946189374651530288894322286859792246413142980277245909181062525398546369553995023529451396820549308690493928593324007689135648753323161394735120908960458860801743476353228970081369439513197105039143930008573928693059198131
e = 65537
c = 47190775807472506173587993082023759909601357229808667044044468676457696140445235738005020994278091230440755033222450219378047807646817722376918364211727971804312327204294555178996480944188624972632371674822397258127227029990196956900925820980263353418653201918881814896866168764140848945600419602253279143149
--------
Frame7:
N = 155266493936043103849855199987896813716831986416707080645036022909153373110367007140301635144950634879983289720164117794783088845393686109145443728632527874768524615377182297125716276153800765906014206797548230661764274997562670900115383324605843933035314110752560290540848152237316752573471110899212429555149
e = 3
c = 124929943232081828105808318993257526364596580021564021377503915670544445679836588765369503919311404328043203272693851622132258819278328852726005776082575583793735570095307898828254568015886630010269615546857335790791577865565021730890364239443651479580968112031521485174068731577348690810906553798608040451024
--------
Frame8:
N = 102900163930497791064402577447949741195464555746599233552338455905339363524435647082637326033518083289523250670463907211548409422234391456982344516192210687545692054217151133151915216123275005464229534891629568864361154658107093228352829098251468904800809585061088484485542019575848774643260318502441084765867
e = 5
c = 25585088950095290712328215701309273521406235982885781641137768116285362079062975527364909549362511146004390419156826709543326814581466248280564194951706937822088902607754944405407698735824315900942915322054614437632116732271787823814807624841386886185122143173564380877370643120953803688563589496390425159539
--------
Frame9:
N = 97767951046154372321400443371234495476461828137251939025051233003462769415459435471728054384852461870179980010660162922547425212869925648424741526671585598167502856111641944825179295197098826911226483155821197251989297102189187139234080795582529077092266799813985026581245196104843272305656744384140745492897
e = 65537
c = 14375950543873882011796759348848479283522955796749853113492047625299699702886303193822347995567175524401038661237990847185236138967814088030767785916645492142741397786256445305366822277551514353423864240674522264407918605662008550545442780563568811883349771003546081844527788515420708612431091464410712019656
--------
Frame10:
N = 93836514358344173762895084384953633159699750987954044414830106276642828025218933012478990865656107605541657809389659063108620208004740646099662700112782252200834393363574089818787717951026690934986964275526538236750596344542450864284576226592039259070002692883820960186403938410354082341916474419847211138467
e = 65537
c = 78852785408127338210375705302361611580033298047358566712385067002412358292419274287993295604646693755514055710305938805847184012173449160624823261013152092151242661538772012880714981492275731658527465442787266554947828301571586721387286510359738598116104180351027973922256460236377354127082438812404967605644
--------
Frame11:
N = 112306066601652819062206435724795595603085908011001671184332227488970057128128821831260649058569739569103298091727188365019228385820143813415009397359257831092635374404034997011441653286642458431865026213129412677064308342580757248577955071384972714557250468686599901682728173096745710849318629959223270431039
e = 3
c = 108387832390337770947361518376552702503741092284778824448943971792044922720461955035726863109418657218498659460663504872870862538725835055240750735576735249122665348803252691221869146679004017916359067454693701495389784159620341860394035373599823801288442604273046729873467936004227013186659110262247417571857
--------
Frame12:
N = 90267480939368160749458049207367083180407266027531212674879245323647502822038591438536367206422215464489854541063867946215243190345476874546091188408120551902573113507876754578290674792643018845798263156849027209440979746485414654160320058352559498237296080490768064578067282805498131582552189186085941328701
e = 5
c = 44374979291120575503988741531987454898919254880086464254904878064332010355432423956182135846738023874326776872139229379943321321362822522900479438294291206287205647145759972233097276253408812699557305314344220807356024994977399840843758750494467535572805794732065369887057841293267499209427585419962565568495
--------
Frame13:
N = 94390533992358895550704225180484604016029781604622607833044135524814562613596803297695605669157378162035217814540004231075201420796787547733762265959320018107419058832819010681344133011777479722382525797938558181629835768471461434560813554411133962651212455645589624432040989600687436833459731886703583047283
e = 65537
c = 41663689952657185984513733558388033289292857758748468070934326941659317694408873831451567385012905508903797893149006067280788298408959017459890579859784072677410890657854942639040056924596925599973762214900728648657052474974405878868755028761443878403349272421153452240103741921751653022646614028009138548572
--------
Frame14:
N = 120008876536855131221255979370745233738591934188224528487535120483456214085493237482915446419599357910343450285858995374277365393767669569942204888383426461862651659865189178784473131914234181752055950431093341514138390898892413182538823693941124637301582389014479754627419560568004831093116617428970538503551
e = 65537
c = 35133765260146855599194761500993159592311136378033858818728078464540389548474611501950689942825550399101504201020687961256642455745888410410524955937773951578993882275525944145131794970001708655718844507774877602125183877782393564092461821246419013099835940432551540513624090850765797735157630551978900512155
--------
Frame15:
N = 147733349387696521015664992396355145811249793103958464053225389476050097503928022819269482555955365534137156079172704297584033078453033637103720972881068435459202133846880715879894340131656691631756162323422868846616160423755883726450486845175227682329583615739797782025647376042249605775433971714513081755709
e = 3
c = 52253817590056116368273294519761274350847193477090280916373828903718796358618956145225746496960677477661151583828604021049936963779103440560630451125137344639503705880024677345063113240530798352727432768980751992926293801206779839157443722614687126711272753610923903360818026083573711899014859313677159790039
--------
Frame16:
N = 90673177193017332602781813187879442725562909473411994052511479411887936365983777106776080722300002656952655125041151156684340743907349108729774157616323863062525593382279143395837261053976652138764279456528493914961780300269591722101449703932139132398288208673556967030162666354552157189525415838326249712949
e = 5
c = 24086371701602948122317790211004032014326487279907486724991846810668564197542368948703436295770758262739732290677177527297040556666434577730354732397784651220918412407485171180732327730242552955646750279842251200227937257322414662213662054605527282812231172173474061845763736546747711105935349033514358348526
--------
Frame17:
N = 111178307033150739104608647474199786251516913698936331430121060587893564405482896814045419370401816305592149685291034839621072343496556225594365571727260237484885924615887468053644519779081871778996851601207571981072261232384577126377714005550318990486619636734701266032569413421915520143377137845245405768733
e = 65537
c = 1395222187334055833498435136007269572138525113145744882969531037442244086277594803865217301719947066153176244638660864035949705664670633245110847416168796640199238733478540080417312141011028469385167826450855601412915611725028631975605932279023918771764204031806414734015476034106891049334159757621016327648
--------
Frame18:
N = 93394639108667212482180458616036741615058981058942739509025631675767304945732437421192075466824789572910657586684470553691049259504106442090140927782673066834126848556317079995332229262871079799089771973100731889841015960713908117908583988637159206246729697336281050046919985463146705713899703248595045701819
e = 65537
c = 49047978458885807127192385282227726754593888749388775377492411121925201201621099927332087316607446894372751446254341808051569111053293066232980434901592875347200122022210780536817524813076908750647137301610117592355818408280291766068780616226847056325075159440352473034526412778650516438709293396458312728764
--------
Frame19:
N = 94154993593274109828418786834159728190797445711539243887409583756844882924221269576486611543668906670821879426307992404721925623741478677756083992902711765865503466687919799394258306574702184666207180530598057989884729154273423032471322027993848437082723045300784582836897839491321003685598931080456249945287
e = 65537
c = 52958695992371180409414011678115981405835026800648278393085136639708219930134280877954018305615378579281651249142230848262822421713895227069561145945972448893229231020632492517869034217943260664130647322694583182800800838539691542175229797652856708373533581250607375664993806654537737027000328299623032632769
--------
Frame20:
N = 90916739755838083837461026375700330885001446224187511395518230504776419813625940046511904838818660297497622072999229706061698225191645268591198600955240116302461331913178712722096591257619538927050886521512453691902946234986556913039431677697816965623861908091178749411071673467596883926097177996147858865293
e = 5
c = 23204039098754030513954332212496652705175644349879686639449689791620605370809827884267260830136516742466455588549253481016504796674014871020503543639681251834114159250986728840380777774144853925216884802529230212783759821262799845229436535491711201551797166082529740271577684082458494926929260818927584104158
破解过程
从参数选择已经可以看到一些问题：
Frame0 和 Frame4 模数相同，考虑共模攻击（成功）；
Frames[0, 4]: Seq 0, Text My secre
Frame3、8、12、16、20 指数相同，考虑广播攻击（成功）；
Frames[3, 8, 12, 16, 20]: Seq 1, Text t is a f
- Frame7、11、15 指数为 3，考虑小指数攻击爆破 k（失败）；
- Frame4 指数非常大，则 d 较小，考虑维纳攻击（已破解，无意义）。
另外我们还可以尝试分解模数质因子，采用 GCD、费马小定理、Pollard（生日悖论）算法：
Frame1 和 18 成功被 GCD 分解，模数共享一个素因子；
Frame 1: Seq 11, Text . Imagin
Frame 18: Seq 10, Text m A to B
Frame10 成功被费马小定理分解，模数素因子 p、q 相近；
Frame 10: Seq 8, Text will get
Frame2、6、19 成功被 Pollard p-1 算法分解。
Frame 2: Seq 6, Text That is
Frame 6: Seq 7, Text "Logic
Frame 19: Seq 5, Text instein.
根据赛题描述的明文填充方式和已破解的明文，我们知道明文高位有固定的标志位 0x9876543210abcdef 和范围极小的顺序索引（0~20）以及 0 填充，且 Frame7、11、15 指数为 3，考虑 Coppersmith 攻击（成功）。
分片明文填充为 512 比特消息后再进行加密，填充规则为高位添加 64 比特标志位，随后加上 32 比特通信序号，再添加若干个 0，最后 64 比特为明文分片字符对应的 ASCII 码
Frame 7: Seq 2, Text amous sa
Frame 11: Seq 3, Text ying of
Frame 15: Seq 4, Text Albert E
最终 Frame5、9、13、14、17 无法在合理时间内破解。但可以根据顺序索引和已破解的明文上下文猜测其明文：
Frame5: Seq 12, Text ation wi
Frame9: Seq 13, Text ll take
Frame13: Seq 14, Text you ever
Frame14: Seq 9, Text you fro
Frame17: Seq 15, Text ywhere."
完整明文
My secret is a famous saying of Albert Einstein. That is "Logic will get you from A to B. Imagination will take you everywhere."
源代码
from sys import set_int_max_str_digits
from os import path
from dataclasses import dataclass
from collections import defaultdict
from concurrent.futures import ProcessPoolExecutor
from itertools import combinations
from gmpy2 import mpz, iroot, gcd, invert, powmod, is_prime
from sage.all import PolynomialRing, Zmod
DATA_DIR = '附件3-2（发布截获数据）'
FLAG_HEX = "9876543210abcdef"
FLAG_VAL = int(FLAG_HEX, 16)
@dataclass
class Frame:
idx: int
n: mpz
e: mpz
c: mpz
def load_frames() -> list[Frame]:
frames = []
for i in range(21):
with open(path.join(DATA_DIR, f'Frame{i}'), 'r') as file:
content = file.read().strip()
payload = bytes.fromhex(content)
n = mpz(int.from_bytes(payload[0:128], 'big'))
e = mpz(int.from_bytes(payload[128:256], 'big'))
c = mpz(int.from_bytes(payload[256:], 'big'))
frames.append(Frame(i, n, e, c))
return frames
def parse_plaintext(m: mpz) -> tuple[int, int, str]:
text_val = int(m & ((1 << 64) - 1))
text_bytes = text_val.to_bytes(8, 'big').replace(b'\x00', b'')
text = text_bytes.decode('ascii')
seq_val = int((m >> 416) & ((1 << 32) - 1))
flag_val = int((m >> 448) & ((1 << 64) - 1))
return flag_val, seq_val, text
def solve_coppersmith(frame: Frame, known_high_bits_val: int, unknown_bits: int = 64) -> int:
n, e, c, k = int(frame.n), int(frame.e), int(
frame.c), int(known_high_bits_val)
P = PolynomialRing(Zmod(n), names='x')
x = P.gen()
f = (k + x)**e - c
f = f.monic()
roots = f.small_roots(X=2**unknown_bits, beta=1.0)
if roots:
return int(roots[0])
return None
def solve_hastad(frames: list[Frame]) -> mpz:
e = frames[0].e
n_list = [f.n for f in frames]
c_list = [f.c for f in frames]
M = mpz(1)
for n in n_list:
M *= n
result = mpz(0)
for i in range(len(frames)):
Mi = M // n_list[i]
yi = invert(Mi, n_list[i])
result = (result + c_list[i] * Mi * yi) % M
m, exact = iroot(result, e)
return m if exact else None
def pollard_pm1(n: mpz, B: int = 200000) -> mpz:
a = mpz(2)
for i in range(2, B):
a = powmod(a, i, n)
d = gcd(a - 1, n)
if 1 < d < n:
return d
return None
def pollard_rho(n: mpz, c_start: int = 1) -> mpz:
if is_prime(n):
return None
x = mpz(2)
y = x
c = mpz(c_start)
g = mpz(1)
count = 0
while g == 1:
x = (x * x + c) % n
y = (y * y + c) % n
y = (y * y + c) % n
g = gcd(abs(x - y), n)
count += 1
if count > 2000000:
break
if g == n:
if c_start > 10:
return None
return pollard_rho(n, c_start + 1)
if g == n or g == 1:
return None
return g
def fermat_factor(n: mpz, limit: int = 100000) -> tuple[mpz, mpz]:
res = iroot(n, 2)
a = res[0] + (1 if res[0]*res[0] < n else 0)
for _ in range(limit):
val = a * a - n
if val >= 0:
res2 = iroot(val, 2)
if res2[1]:
return a - res2[0], a + res2[0]
a += 1
return None, None
def wiener_attack(frame: Frame) -> tuple[int, str, mpz, mpz]:
set_int_max_str_digits(100000)
n, e = frame.n, frame.e
cf_expansion = []
n_val, d_val = e, n
while d_val != 0:
q = n_val // d_val
cf_expansion.append(q)
n_val, d_val = d_val, n_val % d_val
p0, p1 = mpz(0), mpz(1)
q0, q1 = mpz(1), mpz(0)
for q_coeff in cf_expansion:
pn = q_coeff * p1 + p0
qn = q_coeff * q1 + q0
p0, p1 = p1, pn
q0, q1 = q1, qn
k, d = pn, qn
if k == 0:
continue
if (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
b = n - phi + 1
delta = b*b - 4*n
if delta >= 0:
res = iroot(delta, 2)
if res[1]:
x1 = (b - res[0]) // 2
x2 = (b + res[0]) // 2
if x1 * x2 == n:
return frame.idx, 'Wiener', x1, x2
return frame.idx, None, None, None
def attempt_factorization(frame: Frame) -> tuple[int, str, mpz, mpz]:
idx, method, p, q = wiener_attack(frame)
if method:
print(f" Frame {frame.idx} N factored by Wiener")
return idx, method, p, q
p, q = fermat_factor(frame.n)
if p:
print(f" Frame {frame.idx} N factored by Fermat")
return frame.idx, 'Fermat', p, q
p = pollard_pm1(frame.n)
if p:
print(f" Frame {frame.idx} N factored by Pollard p-1")
return frame.idx, 'Pollard p-1', p, frame.n // p
p = pollard_rho(frame.n, c_start=1)
if p:
print(f" Frame {frame.idx} N factored by Pollard Rho")
return frame.idx, 'Pollard Rho', p, frame.n // p
return frame.idx, None, None, None
frames = load_frames()
solved = {}
print("\n[1] Common Modulus Attack...")
n_map = defaultdict(list)
for f in frames:
n_map[f.n].append(f)
for n, group in n_map.items():
if len(group) > 1:
def egcd(a, b):
if a == 0:
return b, 0, 1
g, y, x = egcd(b % a, a)
return g, x - (b // a) * y, y
g, u, v = egcd(group[0].e, group[1].e)
if g == 1:
c1 = invert(group[0].c, group[0].n) if u < 0 else group[0].c
c2 = invert(group[1].c, group[1].n) if v < 0 else group[1].c
m = (powmod(c1, abs(u), n) * powmod(c2, abs(v), n)) % n
flag, seq, text = parse_plaintext(m)
print(
f" Solved Frames {[f.idx for f in group]}: Seq {seq}, Text '{text}'")
for f in group:
solved[f.idx] = (seq, text)
print("\n[2] Broadcast Attack...")
e_map = defaultdict(list)
for f in frames:
e_map[f.e].append(f)
for e, group in e_map.items():
if e > 20 or len(group) < e:
continue
print(f" Checking e={e} with {len(group)} frames...")
for subset in combinations(group, e):
if all(f.idx in solved for f in subset):
continue
m = solve_hastad(subset)
if m:
flag, seq, text = parse_plaintext(m)
print(
f" Solved Frames {[f.idx for f in subset]}: Seq {seq}, Text '{text}'")
for f in subset:
if f.idx not in solved:
solved[f.idx] = (seq, text)
print("\n[3] Factorization Attacks...")
for i in range(len(frames)):
for j in range(i + 1, len(frames)):
if frames[i].idx in solved and frames[j].idx in solved:
continue
g = gcd(frames[i].n, frames[j].n)
if g > 1 and frames[i].n != frames[j].n:
p = g
for f in [frames[i], frames[j]]:
if f.idx not in solved:
q = f.n // p
d = invert(f.e, (p-1)*(q-1))
m = powmod(f.c, d, f.n)
flag, seq, text = parse_plaintext(m)
print(
f" Frame {f.idx} Solved (GCD with Frame {frames[j].idx if f == frames[i] else frames[i].idx}): Seq {seq}, Text '{text}'")
solved[f.idx] = (seq, text)
print(" Running Fermat & Pollard in parallel...")
tasks = [f for f in frames if f.idx not in solved]
with ProcessPoolExecutor() as executor:
results = executor.map(attempt_factorization, tasks)
for idx, method, p, q in results:
if method:
f = next((fr for fr in frames if fr.idx == idx), None)
if f:
d = invert(f.e, (p-1)*(q-1))
m = powmod(f.c, d, f.n)
flag, seq, text = parse_plaintext(m)
print(f" Frame {idx} Solved ({method}): Seq {seq}, Text '{text}'")
solved[idx] = (seq, text)
print("\n[4] Coppersmith Attack...")
for f in frames:
if f.idx in solved or f.e > 3:
continue
print(f" Attempting Frame {f.idx} (e={f.e})...")
for seq_guess in range(21):
K = (FLAG_VAL << 448) | (seq_guess << 416)
root = solve_coppersmith(f, K)
if root is not None:
m = K | root
if powmod(m, f.e, f.n) == f.c:
flag, seq, text = parse_plaintext(m)
print(f" -> MATCH! Seq {seq}, Text '{text}'")
solved[f.idx] = (seq, text)
break
print("\n[5] Recover by context...")
context_solutions = {5: (12, "ation wi"), 9: (13, "ll take "), 13: (
14, "you ever"), 14: (9, " you fro"), 17: (15, 'ywhere."')}
for idx, (seq, text) in context_solutions.items():
if idx not in solved:
f = next((fr for fr in frames if fr.idx == idx), None)
if f:
text_val = int.from_bytes(text.encode('ascii'), 'big')
m = (FLAG_VAL << 448) | (seq << 416) | text_val
if powmod(m, f.e, f.n) == f.c:
print(
f" Frame {idx} Solved (Context): Seq {seq}, Text '{text}'")
solved[idx] = (seq, text)
print("\nResult:")
final_seqs = {seq: text for seq, text in solved.values()}
full_text = "".join([final_seqs[s] for s in sorted(final_seqs.keys())])
print(f"Full Message: {full_text}")
