RSA题目常见分析

最近驹宝给我塞了很多RSA的题,自己也做了很多,学下点 RSA 算法的精髓,写一篇总结,后续持续在这里更新。

RSA的介绍

RSA的介绍见我这篇博客

RSA常用做法分析

低指数攻击

我们知道,RSA的安全在于取模运算的不可逆特性,如果说我的信息本来就是 2,你的加密指数为 2,那么平方下来也就是个 4,取模之后就是取了个寂寞,根据所给公钥和密文,我们直接开个方就得到了明文。

模不互素

如果两个公钥模不互素,含有公约数的话,我们用辗转相除法可以很快分解出 p 和 q,而辗转相除法的时间复杂度不会超过 O(log2N),这优秀的复杂度也让我们能很快地分解得到两个质数。

例题

1
2
3
4
5
n1=28170992834270720831179261369471274598997702487696049830156332106869494605756009553416359364123120058506393684721611134396175255085248520813138288550002318384024725495758952465143175548462425605668727426820108069752293438648949444194603512285742873214792072294105948293367708158997811248728037063455817833123285203002351350137897355454137123787850275750591595704048821577823564124943498574623818380616182913536791603277118981723293551366839681774271977694827633752127448663006058876017157727926930195199823324400467529841773190345386219832514302786638128439120112894598351249563655852372309078552091992786038041766277
n2=30426052411541162629650340351029618556957464479756072258366284852617100608440692462790708527260160603801880998062586095228968453145338155923161883183976907495994708490254171467816217449157828401468749415010271748760024562712415222883445840692381712769800218961961965983057269763458953887162943884366520363358693455535663411308843107559177367470269889790117080885165058052596106490369729956697643818346630535515535267060826393590576457246653806670129899406037697985668889417354391424342725773231355312621066562784839302709229489550567684239158552675013440867386238425395428315796266930676815788000373750994287793821091
c1=2582291333174688473482837371310695558013344522219801451176882867544382844570171875599043056723912248821021128705894777239584884707037606324176075924881206372661647696306877429822668287235786023020814823874667156587819928274230054865962630859689154098113218782923808109545553391020429182265395418495962822105988502721180599540017512038621869581406476916453238250489026172610106413861344378397008077526294299119321017408325053654182442842084345081920983250459754887618685974033809325906564138957727999316089837005460571267003092757134432108859653429713579692972626913060573924381433177244348871427046105683280661716738
c2=9479980959348294048040415043005053472430206540648250182203975873154652511903511233814860462809419869817942169405620776050389695639672610182559325440498062679122369415235835023694654421107733717733775846408272826799042552945154258022884833151833319678933958340634903581390433575987867437793326943284375631246178387198398978881023408777618571874239336944658161598413171690119933787696662425323587221393547627048996325679636765500603814636055989176181848082280852597546562839789752131657822041737796527736673507903567282808259265596977598085942774362863079389090752606097401982926590840320148439167865891839785863650767
e=65537

这里我们 GCD 大可不必自己写,直接用 Crypto 库的 GCD 函数即可,安装方法也在上一篇博客。

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
def solve(c,p,q,e):
n=p*q
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
return long_to_bytes(m).decode()
n1=28170992834270720831179261369471274598997702487696049830156332106869494605756009553416359364123120058506393684721611134396175255085248520813138288550002318384024725495758952465143175548462425605668727426820108069752293438648949444194603512285742873214792072294105948293367708158997811248728037063455817833123285203002351350137897355454137123787850275750591595704048821577823564124943498574623818380616182913536791603277118981723293551366839681774271977694827633752127448663006058876017157727926930195199823324400467529841773190345386219832514302786638128439120112894598351249563655852372309078552091992786038041766277
n2=30426052411541162629650340351029618556957464479756072258366284852617100608440692462790708527260160603801880998062586095228968453145338155923161883183976907495994708490254171467816217449157828401468749415010271748760024562712415222883445840692381712769800218961961965983057269763458953887162943884366520363358693455535663411308843107559177367470269889790117080885165058052596106490369729956697643818346630535515535267060826393590576457246653806670129899406037697985668889417354391424342725773231355312621066562784839302709229489550567684239158552675013440867386238425395428315796266930676815788000373750994287793821091
c1=2582291333174688473482837371310695558013344522219801451176882867544382844570171875599043056723912248821021128705894777239584884707037606324176075924881206372661647696306877429822668287235786023020814823874667156587819928274230054865962630859689154098113218782923808109545553391020429182265395418495962822105988502721180599540017512038621869581406476916453238250489026172610106413861344378397008077526294299119321017408325053654182442842084345081920983250459754887618685974033809325906564138957727999316089837005460571267003092757134432108859653429713579692972626913060573924381433177244348871427046105683280661716738
c2=9479980959348294048040415043005053472430206540648250182203975873154652511903511233814860462809419869817942169405620776050389695639672610182559325440498062679122369415235835023694654421107733717733775846408272826799042552945154258022884833151833319678933958340634903581390433575987867437793326943284375631246178387198398978881023408777618571874239336944658161598413171690119933787696662425323587221393547627048996325679636765500603814636055989176181848082280852597546562839789752131657822041737796527736673507903567282808259265596977598085942774362863079389090752606097401982926590840320148439167865891839785863650767
e=65537
p=GCD(n1,n2)
q1=int(n1//p)
q2=int(n2//p)
print(solve(c1,p,q1,e)+solve(c2,p,q2,e))
#flag{79a0ad16-d357-49af-81e9-d33dc3e541a2}

共模攻击

当一个明文信息在两个不同的指数对同一模数进行了加密之后,我们可以在不求出私钥的情况下计算得到明文信息。

假设有两个密钥

$key_1=<e_1,n>$

$key_2=<e_2,n>$

明文为 m,我们用这两个公钥分别加密出两串密文。

$c_1=m^{e_1}%n$

$c_2=m^{e_2}%n$

这里需要用到点高数知识。对于整数 $k_1,k_2$,使得方程 $k_1x+k_2y=b$ 存在整数解的前提是 b 能整除 $k_1$ 和 $k_2$ 的最小公约数,也就是 $\gcd(k_1,k_2)$。

特殊地,对于 b=1,存在整数解的充要条件则是 $k_1$ 与 $k_2$ 互质。

一般情况下,RSA 的加密指数我们会取质数,所以很容易有 $e_1x+e_2y=1$ 存在一对整数解 (x,y)。

那么

$c_1^{x}\times c_2^{y}%n=(m^{xe_1}\times m^{ye_2})%n=m^{xe_1+ye_2}%n$

最后化简即得到明文 m。

我们的目标就是找到一对整数解,对于这个问题,我们可以使用扩展欧几里得算法去计算,或者是使用 Z3 去求解。

但是我们也很容易能看出,这个整数解应该会是一正一负的,对于负数我们需要做点特殊处理。

其实比较简单,负数指数我们并不好处理,因为在乘法模的群当中,数集为整数,负指数表示了分数,显然不满足群的封闭性,其实这里处理的方法与我们之前逆元的处理方法一样。

举个栗子:假设 x>0,y<0,则 $x^y$ 它的逆元为多少,假设不在模乘法代数而是在普通乘法代数,数集被扩展到了实数集,那我们脱口而出肯定是 $x^{-y}$。那么其实,在模乘法体系中,$x^y$ 的逆元一样是 $x^{-y}$,但是它不好被辨别,于是我们再去找到它逆元的逆元,一个数的逆元的逆元一定是自身。

我们直接找到 $x$ 在模乘法意义下的逆元 $x^{-1}$ 之后再保持指数不变即是它的逆元,我们可以证明一下:

$x^{y}\times (x^{-1})^y%n=(x\times x^{-1})^y%n=1$

因此对于负指数,我们直接符号变正,底数变为逆元即可。

例题

1
2
3
4
5
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
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)
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291
s=egcd(e1, e2)
x=s[1]
y=s[2]
if x<0:
x=-x
c1=inverse(c1,n)
else:
y=-y
c2=inverse(c2,n)
m=(pow(c1,x,n)*pow(c2,y,n))%n
print(long_to_bytes(m).decode())
#flag{49d91077a1abcb14f1a9d546c80be9ef}

数学推导

这是一类比较泛的题目,题目除了给出密文和公钥以外,还会额外给出一些表达式信息,帮助破解 RSA 的密文,只要理解了 RSA,熟悉 RSA 的推导过程就不会有太大问题。

例题1

1
2
3
4
5
n=14113714305072797946493506481186688069348068525719522300918296843166886149586712593527278499546480608243022456418279126062291885234984378509284469719982424691272187376834036952743111743737743509787289516031073996690244502575328189110938473272385195987277353305316883743349963569552297946004952533211450648686747906145487061115730661553947322806175740991677666279314224690585522184085274523080051179955809948156424572176333474623245604759865579902860320192130044881910837668330885305900309636233281430338678478325361905450208233862057975227437570700376032367636653508625619621365742913511560163593564542385538976273511
e=65537
c=8618327949649600151577805769536868884186050491362368463626647780332443491577028760576306554954308943953267510827791879308004801627303605775129313660121772370222619585966214292305860970821159935577290407908606708688407395127864609535430976332421315463289482130097266383749917829831497635736596409478627650432841064479081322546224912505920515470753069832953929215867402615727986720952496172221103420158414576649301068869241456517428304569955008818909581293445988877086661570321362965360400214418049394686624646829322189252357911547541529314699149144426085781464325489219068048330497460674000186446200265603018557000483
dp=22254124501058125233734227965547943196721474032074981803310625346887468776340246924403662046504410526020245040082211662134244900364674425023930821673400316961211254098599523105818306877684796612309587274228054352459332784217520606687007798656236622150535124212386499498298989015161102829904127676310132589861
dp=d % (p -1)

这个题目中,它给了我们 d % (p-1) 的值 dp。

首先我们联立一下方程组

$e\times d%(p-1)(q-1)=1$

$d%(p-1)=dp$

根据①式我们可以推出

$e\times d=k(p-1)(q-1)+1$

我们在②式左右同乘一个 e。

$e\times d%(p-1)=dp\times e%(p-1)$

从左边不难看出,结果应当=1,于是得到等式

$dp\times e%(p-1)=1$

首先不难得到 $dp<p$ 则 $dp\times e<p\times e$。

$dp\times e=k(p-1)+1$

图中只有 k 与 p 未知,但是我们应当明白 k 不会超过 e。

于是我们可以将 $dp\times e -1$ 对 $k(k\le e)$ 进行取模判断,若取模结果为零则有可能是这个结果。

那么我们跑个脚本循环 $[2,65537]$ 即可。

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
n=14113714305072797946493506481186688069348068525719522300918296843166886149586712593527278499546480608243022456418279126062291885234984378509284469719982424691272187376834036952743111743737743509787289516031073996690244502575328189110938473272385195987277353305316883743349963569552297946004952533211450648686747906145487061115730661553947322806175740991677666279314224690585522184085274523080051179955809948156424572176333474623245604759865579902860320192130044881910837668330885305900309636233281430338678478325361905450208233862057975227437570700376032367636653508625619621365742913511560163593564542385538976273511
e=65537
c=8618327949649600151577805769536868884186050491362368463626647780332443491577028760576306554954308943953267510827791879308004801627303605775129313660121772370222619585966214292305860970821159935577290407908606708688407395127864609535430976332421315463289482130097266383749917829831497635736596409478627650432841064479081322546224912505920515470753069832953929215867402615727986720952496172221103420158414576649301068869241456517428304569955008818909581293445988877086661570321362965360400214418049394686624646829322189252357911547541529314699149144426085781464325489219068048330497460674000186446200265603018557000483
dp=22254124501058125233734227965547943196721474032074981803310625346887468776340246924403662046504410526020245040082211662134244900364674425023930821673400316961211254098599523105818306877684796612309587274228054352459332784217520606687007798656236622150535124212386499498298989015161102829904127676310132589861
#dp=d % (p -1)
for i in range(2,65537):
if (dp*e-1)%i==0:
if isPrime((dp*e-1)//i+1):
p=(dp*e-1)//i+1
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m).decode())
#flag{0cd82bfc-5544-43c5-b48c-ce11136bea49}

e phi不互素

我们知道 RSA 的加密指数一般为质数,若不是质数会发生什么?

我们前面推导过 RSA 的计算过程,若 e 不是质数会导致可能求不出 phi 的逆元,或者说找不到一个这样的数 d,使得 $e\times d %\phi=1$,如果 $\gcd(e,\phi)=k$ 则 $e\times d%\phi$ 的结果至少为 k 的整倍数。

我们按照 RSA 的解密方法最后推导出来的结果也就是

$m^{k}%n$

因此我们就回到了怎么解这个指数的问题,若指数 k 小可以直接开方,或者是动用一下低指数攻击。

例题1

1
2
3
4
p=136959726431205865477775151957746058501964084915586200859223998224419328617512480807779057493884259671732817083158742688893426777301273633213099180123980988559064240005229990903986655711210993445188959348127903344696563428112042019089659624505185444899365837872965591393711833751140798071913532034918073969303
q=100775514992570031279080353204884456896540523509595089891057558352540088307146118253575941345444101592071454319892938692060454946607143974473707141313645549356430599711832162076318618985329980795933151213484006411944383963148067340413103907427302327136609462283013833061184517264215353793537565873817217882871
e=618
c=11474180598339059739824064616811901863008672847264841633401805944654527375502760803872877763162433116575938389089158136355223441822920717752520632181250987580240513955742874287005589873425759901749449152080440281411772036003528325772394140583924413056042024007990830484221229380940124523505145729796879325683192331242784866357454098755097887413530621128405967607900565276243646588213591552811550038972567938749944372033373196416854332876524071485674100971839799288548733601138685897794138343613068716766810753454049042387074495749784721897884348181557610094355833915443696680454373648737843918284068627924128987496538

题目中给出了 $p,q$,我们就照例求一下私钥,但是注意到 $e$ 并非一个质数,所以我们先看看有没有公约数,可以发现有公约数 6。但是这里需要注意,在 Crypto.Util.number 中的 inverse 函数,如果有公约数,则会自动帮你除公约数之后的逆元,而 gmpy2 的 invert 函数则会直接报错。

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from math import sqrt
import gmpy2
p=136959726431205865477775151957746058501964084915586200859223998224419328617512480807779057493884259671732817083158742688893426777301273633213099180123980988559064240005229990903986655711210993445188959348127903344696563428112042019089659624505185444899365837872965591393711833751140798071913532034918073969303
q=100775514992570031279080353204884456896540523509595089891057558352540088307146118253575941345444101592071454319892938692060454946607143974473707141313645549356430599711832162076318618985329980795933151213484006411944383963148067340413103907427302327136609462283013833061184517264215353793537565873817217882871
e=618
c=11474180598339059739824064616811901863008672847264841633401805944654527375502760803872877763162433116575938389089158136355223441822920717752520632181250987580240513955742874287005589873425759901749449152080440281411772036003528325772394140583924413056042024007990830484221229380940124523505145729796879325683192331242784866357454098755097887413530621128405967607900565276243646588213591552811550038972567938749944372033373196416854332876524071485674100971839799288548733601138685897794138343613068716766810753454049042387074495749784721897884348181557610094355833915443696680454373648737843918284068627924128987496538
n=p*q
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,p*q)
s=gmpy2.iroot(m,6)
print(long_to_bytes(int(s[0])).decode())
#flag{d8600272-fa37-4f2d-92e4-2b74bf3adf71}

在这里需要使用 gmpy2 的 iroot 函数,直接进行开 6 次方的操作。

例题2

1
2
3
4
5
6
7
8
9
10
e1=14606334023791426
p1=121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q1=130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
c1=11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248
n1=p1 * q1
e2=13813369129257838
p2=121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q2=94582257784130735233174402362819395926641026753071039760251190444144495369829487705195913337502962816079184062352678128843179586054535283861793827497892600954650126991213176547276006780610945133603745974181504975165082485845571788686928859549252522952174376071500707863379238688200493621993937563296490615649
c2=7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919
n2=p2 * q2

这题略微有点难,因为需要用到新的数学知识了。

首先可以看到有 $c_1,c_2$,并且两个公钥由公因数 p。我们任意使用其中一个加密体系都发现 e 与 $\phi$ 不互素,并且有公约数 14,这题就不能像之前那么故技重施了,因为 14 这个指数虽然小但是也不小,直接开是开不了的,但是我们可以转换密钥体系。

根据之前的一些理论我们可以得出以下式子

$res_1=m^{14}%n_1=c_1^{d_1}%n_1$

$res_2=m^{14}%n_2=c_2^{d_2}%n_2$

我们在其中分解 p 和 q 可以得到三个式子。

$res_1%p=m^{14}%p$

$res_1%q_1=m^{14}%q_1$

$res_2%q_2=m^{14}%q_2$

对于这三个等式,我们可以使用中国剩余定理求出满足这三个方程的数 。

中国剩余定理

定义

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组(其中 $n_1, n_2, \cdots, n_k$ 两两互质):

$$
\begin{cases}
x &\equiv a_1 \pmod {n_1} \
x &\equiv a_2 \pmod {n_2} \
&\vdots \
x &\equiv a_k \pmod {n_k} \
\end{cases}
$$

上面的「物不知数」问题就是一元线性同余方程组的一个实例。

过程
  1. 计算所有模数的积 $n$;
  2. 对于第 $i$ 个方程:
    1. 计算 $m_i=\frac{n}{n_i}$;
    2. 计算 $m_i$ 在模 $n_i$ 意义下的 逆元 $m_i^{-1}$;
    3. 计算 $c_i=m_im_i^{-1}$(不要对 $n_i$ 取模)。
  3. 方程组在模 $n$ 意义下的唯一解为:$x=\sum_{i=1}^k a_ic_i \pmod n$。
证明

我们需要证明上面算法计算所得的 $x$ 对于任意 $i=1,2,\cdots,k$ 满足 $x\equiv a_i \pmod {n_i}$。

当 $i\neq j$ 时,有 $m_j \equiv 0 \pmod {n_i}$,故 $c_j \equiv m_j \equiv 0 \pmod {n_i}$。又有 $c_i \equiv m_i \cdot (m_i^{-1} \bmod {n_i}) \equiv 1 \pmod {n_i}$,所以我们有:

$$
\begin{aligned}
x&\equiv \sum_{j=1}^k a_jc_j &\pmod {n_i} \
&\equiv a_ic_i &\pmod {n_i} \
&\equiv a_i \cdot m_i \cdot (m^{-1}_i \bmod n_i) &\pmod {n_i} \
&\equiv a_i &\pmod {n_i}
\end{aligned}
$$

即对于任意 $i=1,2,\cdots,k$,上面算法得到的 $x$ 总是满足 $x\equiv a_i \pmod{n_i}$,即证明了解同余方程组的算法的正确性。

因为我们没有对输入的 $a_i$ 作特殊限制,所以任何一组输入 ${a_i}$ 都对应一个解 $x$。

另外,若 $x\neq y$,则总存在 $i$ 使得 $x$ 和 $y$ 在模 $n_i$ 下不同余。

故系数列表 ${a_i}$ 与解 $x$ 之间是一一映射关系,方程组总是有唯一解。

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
e1=14606334023791426
p1=121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q1=130968576816900149996914427770826228884925960001279609559095138835900329492765336419489982304805369724685145941218640504262821549441728192761733409684831633194346504685627189375724517070780334885673563409259345291959439026700006694655545512308390416859315892447092639503318475587220630455745460309886030186593
c1=11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248

e2=13813369129257838
p2=121009772735460235364940622989433807619211926015494087453674747614331295040063679722422298286549493698150690694965106103822315378461970129912436074962111424616439032849788953648286506433464358834178903821069564798378666159882090757625817745990230736982709059859613843100974349380542982235135982530318438330859
q2=94582257784130735233174402362819395926641026753071039760251190444144495369829487705195913337502962816079184062352678128843179586054535283861793827497892600954650126991213176547276006780610945133603745974181504975165082485845571788686928859549252522952174376071500707863379238688200493621993937563296490615649
c2=7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919
n2=p2 * q2
phi1=(p1-1)*(q1-1)
phi2=(p2-1)*(q2-1)
d1=inverse(e1,phi1)
d2=inverse(e2,phi2)
res1=pow(c1,d1,p1*q1)
res2=pow(c2,d2,p1*q2)
print(res2)
'''
res1%q1=m^14%q1
res2%q2=m^14%q2
res1%p=m^14%p
'''
a1=res1%q1
a2=res2%q2
a3=res1*res2%p1
n=p1*q1*q2
n1=n//q1
n2=n//q2
n3=n//p1
m1=inverse(n1,q1)
m2=inverse(n2,q2)
m3=inverse(n3,p1)
res=(n1*m1*a1+n2*m2*a2+n3*m3*a3)
n=q1*q2
e=14
c=res%n
phi=(q1-1)*(q2-1)
d=inverse(e,phi)
m=pow(res,d,n)
l=iroot(m,2)
print(long_to_bytes(int(l[0])))
#flag{gcd_e&φ_isn't_1}
文章目录
  1. 1. RSA的介绍
  2. 2. RSA常用做法分析
    1. 2.1. 低指数攻击
    2. 2.2. 模不互素
      1. 2.2.1. 例题
      2. 2.2.2. 解题脚本
    3. 2.3. 共模攻击
      1. 2.3.1. 例题
      2. 2.3.2. 解题脚本
    4. 2.4. 数学推导
      1. 2.4.1. 例题1
      2. 2.4.2. 解题脚本
    5. 2.5. e phi不互素
      1. 2.5.1. 例题1
      2. 2.5.2. 解题脚本
      3. 2.5.3. 例题2
      4. 2.5.4. 中国剩余定理
        1. 2.5.4.1. 定义
        2. 2.5.4.2. 过程
        3. 2.5.4.3. 证明
      5. 2.5.5. 解题脚本
|