【0】扩展欧几里得算法分析

（1）举例说明：

（2）推导：

【1】dp泄露

（1）概述：遍历1到e的值除e*dp-1能整除的数进行排除最后得到符合结果的p最终求解m。

（2）原理分析：

（3）代码举例(buu中rsa2)：

def buu_rsa2():
p = 0
e = 65537
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
n = 48254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
# 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
temp=dp*e - 1
for i in range(2,e) :
if temp%i==0:
p=temp//i+1
q=n//p
d=gmpy2.invert(e,(p-1)*(q-1))
m=pow(c,d,n)
print(m)
# p = 913127778735150773404608108707415336420768487291895507949690875024961998723921084218161740762247806472238721460807860416768595691382327159766463278002713
# 之后复制m的值调用binascii.a2b_hex()方法进行十六进制编码
# m = 198684253432954596193345784793734665149302336175065992640002388748307071802369561479775356746782694904065947170519261584314403457835655705269315447475440706251964502468599639100901659265781324059990023263154237810704131086853449073568846031342829740365587788703247933638196834034686786623463634700146737869245
# 这个函数或许因为vscode上插件的原因对n赋正确的值之后会报错，所以要放到cmd中去跑，上面就是m的值

【2】共模攻击

（1）概述：用扩展欧几里得算法求得m^(gcd(e1,e2))最后解密。

（2）原理分析：

共模问题的通式就是最后推到的形式，e1,e2互质可以看作是通式的一种特殊情况。

（3）代码举例（buu上rsa3）：

def buu_rsa3():
s1 = 1
s2 = 1
c1 = 5
# c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n = 2
# n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1 = 11187289
c2 = 1
# c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2 = 9647291
temp1 = gmpy2.powmod(c1,s1,0)
temp2 = gmpy2.powmod(c2,s2,0)
m = gmpy2.powmod(temp1*temp2,1,n)
m = gmpy2.iroot(m,gcd(e1,e2))
print(m)
# 直接将m复制下来十进制换十六进制放到binascii.a2b_hex()方法中对其十六进制解码
# 与rsa2一样因为vscode插件的原因要放到cmd命令行中执行才行，代码要合理转换