简单的RSA解密
分析
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c: 6069289304028593572251019981010887160501287635882514185652058567970262989035334810476961467173511523743011129198511429462130681373361508406893616711963614358508217875196430201412185574769926412372819672861734402715681036791007063359788795901109823969449011898187549181753493557877160022208060803439178540468 根据公式去算
n=p*q
T=(p-1)*(q-1)
d=pow(e,-1,T)
m=pow(c,d,n)代码实现
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 6069289304028593572251019981010887160501287635882514185652058567970262989035334810476961467173511523743011129198511429462130681373361508406893616711963614358508217875196430201412185574769926412372819672861734402715681036791007063359788795901109823969449011898187549181753493557877160022208060803439178540468
n=p*q
T=(p-1)*(q-1)
d=pow(e,-1,T)
m=pow(c,d,n)
print(m)
滚动吧RSA-神秘古墓的数字谜题
分析
首先求出p和q
RSA 的 n是两个质数的乘积，它的分解结果是唯一的，不存在其他的 p和 q
所以通过遍历求模得到p,q
然后再去常规求法
代码实现
from Crypto.Util.number import long_to_bytes
n=1005203797981
e=65537
list_c=[106107998738, 834934142560, 580110822712, 385628976267, 104623972097, 655184240416, 664525703242, 253707368074, 994534403912, 52359520446, 875258200721, 655184240416, 208464036537, 108273932688, 875258200721, 360948061641, 360948061641, 253707368074, 108273932688, 360948061641, 52359520446, 571286080801, 896859099618, 108273932688, 580110822712, 253707368074, 580110822712, 994534403912, 108273932688, 484517690826, 69673871710, 360948061641, 69673871710, 571286080801, 571286080801, 415335390586, 571286080801, 415335390586, 655184240416, 52359520446, 896859099618, 109777792081, 221520463705]
def get_pq(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return (i, n // i)
return (n, 1)
p, q = get_pq(n)
T=(p-1)*(q-1)
d=pow(e,-1,T)
flag=b''
for c in list_c:
m=pow(c,d,n)
flag+=long_to_bytes(m)
print(flag)RSA共模攻击-公司机密泄露事件
分析
共模攻击 = 同一套 n，两个不同 e，加密同一个 m → 不用分解 n 就能直接算出 m
逐个变量解释
n:RSA 公共模数
两台设备 / 两次加密 用的同一个 n
是大质数乘积 n=p×q
全程固定不变，公开给你
e1、e2:两个不同的公钥指数
加密用的两个不一样的 e
常见：3、5、17、65537 这些
题目会给你 e1、e2
c1、c2：两段密文
c1=m^e1modn
c2=m^e2modn
都是拦截到的加密后大数字
old_r, r, old_s, s, old_t, t, q
扩展欧几里得算法内部变量不用管原理，只需要知道作用：自动算出一对整数 x,y，满足：e1⋅x+e2⋅y=1
x、y:扩欧算出来的系数共模解密核心全靠它。
m:最终明文数字公式：m=(c1^x*c2^y)modn解出来的原始密码 / 原文数字。
代码实现
n = 24607683138537687468391817467678324139861854643873178338457995201367012379839397932373297827073082591927291668577022215105940914234291186017704038355643875864472446749737901767080280605143704078853226764502589019162846645878966898806069632421536837287763596399602788430557150785175184849034484972742377006222451177952935618920350049295275954091506150070794670504886679512303114750690722558260904732810708250858824106221517873153653452468972939175218445821982199936264404199841455709964150023062778457236877939530739149341401157218288608665289218633932957534355674484329862601108364925598302121016231792162862686931591
e1 = 65537
e2 = 61463
c1 = 24110147715258936895675674092330079548455001266007145115625324241755621210555809835515220201229171421987915820227648206540717868153779969972387531813473832640929194894435020656701066522526510950516315701483397815696607941193592092875159556897506982149216121571358672329972179370429092332818558912626314162768679195164264046299500310660491295505203936088724396512251985609751459563615717179370539555494971479571019791925087447799270716743465979417597710259509624414501142400799820305158023495945343397266410471234421869069809900157625356663632182561847515815726574239050139581504658475129199241060074837159729201610965
c2 = 3400371515109439987001061100442556325039971342048551260016249781649564408512731246492544987433356081343279562743734114888197051581853693128177270714272802311173360854153840285937883573829328019570425082501390863195458576594300068998129053042048484050120011772302011861279138024765955490093329031189128506838385732329462780635852722862445410249074325084056489666918636474996678551223059789345192696456293637762924472172003573432230394823411182757838412577943314136461791043153240908731265473877248346810817902514169226661499142813894813775116337271578087381502363951431235553649348402607043616979111828138212595641343
old_r, r = e1, e2
old_s, s = 1, 0
old_t, t = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q * r
old_s, s = s, old_s - q * s
old_t, t = t, old_t - q * t
x = old_s
y = old_t
# 共模解密 m = c1^x * c2^y mod n
m = (pow(c1, x, n) * pow(c2, y, n)) % n
print("明文 m =", m)
RSA低指数加密-智能家居的 "便捷" 漏洞
分析
加密算法：RSA，e=3（低指数）。
核心漏洞：同一临时密码 m，用三个不同的模数 n1, n2, n3加密，得到三个密文c1, c2, c3。
攻击原理：当 e=3且m相同时，可通过中国剩余定理合并密文，直接得到 m^3，再开立方根即可恢复明文m。
- 数学原理
我们有以下方程组：
根据中国剩余定理，可以求得一个数 x，满足：
由于临时密码 m 是一个远小于 n1, n2, n3的数，因此 m^3也远小于 n1 n2 n3。
这意味着：x = m^3。
所以，直接对 x 开立方根就能得到密码 m。
代码实现
import gmpy2
from Crypto.Util.number import long_to_bytes
n1 = 27004614775645395088645285512858802489647942376300899758055811434040652371224191703721755177513435859822509521912912054192139195416995286040467752593879119531806148521789953486798750475226122528238214422656397126885649067717427472809114780926690328713348822829764742485900386634442579624038980649262600010748020526967018352996301198137180740319192081243464549560913640212339338837483198307870601112543438017140105294922344864396431671855525397599698392977205243720365636437904532031046450774571150299947689042235683213339344011855785797197702303213178624179657339315907898946924426108408166858070668776295064049706127
c1 = 6621012241157334216705076469938161557854442520489957022323779894098509858094007713437803952950311689714601078017438817308332167811624541294012973908727965184
n2 = 21719990436228175598656775603201442622872782184809374904175472780992965207090286952083864720342145272499719631590745329911198219298440250207307974872695879826500359285309915261730602684075263114407625402676693056033250983138269718385992458326988660266292587206515731241778664896615956757881901332451768361032965155900623132060227051130480121641261336599337645515152704204511262241933188981706401176095574684661924145876452904017731473036278202890695580286355896898045123330734845657099813661008593442303482809190325622566490260561563029743554757109356623825756902039851777287106859279521340329665713398399770559009819
c2 = 6621012241157334216705076469938161557854442520489957022323779894098509858094007713437803952950311689714601078017438817308332167811624541294012973908727965184
n3 = 11785010815459318393802526184397150247791583622107300485925637562445143352213337990794126625405855032346103132074086515352083485625995768221684741695184324430351008427527500614814644690484840742616840082035412343445065336699746826102447535683712782476778980370491181576558113665138489141746699356062029807635394014973531420784243717378015882978258240366334075052495609515051536026694919222201725115647048629286714032841485148005953937646550386388300666465649615030248734609239587119598324610354090424766303550020002431313230246527674827829244745914466184731001903671936502273373633323902419888320754830543713882342043
c3 = 6621012241157334216705076469938161557854442520489957022323779894098509858094007713437803952950311689714601078017438817308332167811624541294012973908727965184
def crt(a_list, m_list):
M = 1
for m in m_list:
M *= m
result = 0
for a, m in zip(a_list, m_list):
Mi = M // m
inv = gmpy2.invert(Mi, m)
result += a * Mi * inv
return result % M
# 合并得到 m^3
x = crt([c1, c2, c3], [n1, n2, n3])
# 开立方根
m, _ = gmpy2.iroot(x, 3)
print(m)
print("临时密码 (十六进制):", hex(m))
print("临时密码 (字符串):", long_to_bytes(m))
RSA-txn_dp、txn_dq泄露
代码实现
def egcd(a, b):
"""扩展欧几里得算法"""
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
"""计算模逆元"""
g, x, y = egcd(a, m)
if g != 1:
raise Exception('模逆元不存在')
else:
return x % m
p = 149047476182457038470427824192213745127758483443878677508893313577324819302446680318322405663591248491138392571967360796123081027757592604918119089214138277575148141920412358952530080892848820230998392661704834746803342097387129924143619084273312138027000590927329283786565403521710369017849195313187178262213
q = 123355556438954148857328958861003230781352940344000131732829763266446150089539505603325069435241575211601732781066428962246350025706425533146527664855192741025054027032316810103321232530746040769556194634555031424276978893250696419700532983686258349910698206069608405895861384925259698344941250383322228824993
txn_dp = 42126524677633826824844327684153186784972840385340337482435586794246545475457859127610590620156516587915623775792948874249829760378187363144912521880537063198699298287583719740869952244229754710692975350855025527776892540368331683574967181119643067420938271378158864058850857283016475257012279776617280288415
txn_dq = 47316994843688281095697413519852638960948679270213615876194029568936822612869218864851168426372579021763458045143318081315838170761498668076629579690248518348928549613536214274475599591367149237977279800164759117096482107145457644454145039852514366939736329258105312925967830856493998435098855845034704144843
C = 12482180643044479333085613857683996163691775422407517528206160927379826012546629064793353069657684246447430881691920546083650165584878824562253097860769382670173222025879893148510821119307761735607538157956212159002221781164864170956901122468354901439435956681291395373667654657491393485452893529911356703117285831856410901071506143984646502621701609443582922428264354959751961829341395744718260766389457406678381101500580210024389474898337922028825854316835039769209103929372370015870105776081214277380604544684839660210306763359789014096142119694044322504789464819950288159907143648914446939444654883036577639470199
e = 65537
# RSA-CRT 解密
# 步骤1：计算中间值 m1 = C^dp mod p，m2 = C^dq mod q
m1 = pow(C, txn_dp, p)
m2 = pow(C, txn_dq, q)
# 步骤2：计算 q 在模 p 下的逆元
q_inv = modinv(q, p)
# 步骤3：合并结果得到明文
h = ( (m2 - m1) * q_inv ) % p
plaintext = m1 + h * q
# 转换明文为字符串
def int_to_bytes(n):
"""大整数转换为字节串"""
return n.to_bytes((n.bit_length() + 7) // 8, byteorder='big')
# 转换并输出结果
plain_bytes = int_to_bytes(plaintext)
try:
result = plain_bytes.decode('utf-8')
print(" 解密成功！原始交易记录明文：")
print(result)
except:
print(" 解密成功！原始明文（十六进制）：")
print(plain_bytes.hex())
2025年数字密码管理员比赛ERSA解题步骤
分析
附件中含有三个数
密文,n和p-q
已知: n=p*q和p-q，需要分别求p和q
首先需要求出p+q
完全平方公式
(p+q)^2=p^2+q^2+2pq
(p-q)^2=p^2+q^2-2pq两式联立可得
(p+q)^2-(p-q)^2=4pq所以
(p+q)^2=(p-q)^2+4pq得到p+q以后，即可求得p和q
(p+q)-(p-q)=2q
q=0.5*((p+q)-(p-q))
(p+q)+(p-q)=2p
p=0.5*((p+q)+(p-q))E一般为65537
代码实现
使用了pycryptodome和gmpy2库
import gmpy2
from Crypto.Util.number import long_to_bytes
c = gmpy2.mpz(9770696378649599298335400149775800715278098395147272306126448777137278396736011727171893364673565527155223414914391695677662714372703334029492906594424180598856390103756148323078728616423112890680089381676909198635512847985842520084149817878301301549069609714683746667017517022441032437836984100201649521840529543340604204522906463708710970350337103229055624130836951088663226808981359344280485482464307017127139718730517463626060659603182668778899105742684687481146096184168045912805224630356362355241072789095254777822518083568596449809490848892863318817733333054146542365433313199368414727666368039248188714397128)
n = gmpy2.mpz(14936456980075783281922696832049096859221239201249171982141610258623112327968680537838099310211984453360226488577822212626095978045216530376208986236704143560705437756664226713691638742459855042144729993839511315308913815059681238743382692670368631286955063026418961862377638938848583503792443856492719474542034456285951706815893826312300947717749918478527247231204266257390058353494592957218853834915527042603661225894611873097295901222573134018399015617591564511819475791631668157430824467297886642079947309566578299940770281749782665274445486625638309935537123768790341685291775792134855237673460858730137431332457)
d = gmpy2.mpz(33592333200998386040362834713014895724281133303213331571491951785196332425258583214521710608125318093619017193570907121774399377343191391602029873328929592320596625058289207378302506832182734714605207645165835350634120951823332889155095618617191430939499014551009714045296821289677791960512135184215407566096)
S = gmpy2.isqrt(d**2+4*n)
p=(S+d)//2
q=(S-d)//2
T=(p-1)*(q-1)
e=65537
d=gmpy2.invert(e,T)
m=gmpy2.powmod(c,d,n)
print(m)
print(long_to_bytes(m).decode())