RSA学习笔记

非对称加密

RSA

RSA加密

RSA的加密过程表达式

密文= 明文^Emod N

公钥=(E,N)

E是加密（Encryption）的首字母，N是数字（Number）的首字母

RSA解密

明文=密文^DmodN

私钥(D,N)

D是解密（Decryption）的首字母；N是数字（Number）的首字母

生成密钥对(E,D,N)

步骤

准备两个质数p，q。这两个数不能太小，太小则会容易破解，将p乘以q就是N

N=p*q

求L(L为中间过程的中间数)

L 是 p－1 和 q－1的最小公倍数

就是phi_N

求E

E必须满足两个条件：E是一个比1大比L小的数，E和L的最大公约数为1
用gcd(X,Y)来表示X，Y的最大公因数则E条件如下：

1 < E < L
gcd（E，L）=1

求D

#求逆元
D=inverse（E,phi_n）

1 < D < L
E＊D mod L ＝ 1
$$
E*D\equiv1\pmod{L}
$$

RSA算法原理

私钥解密的证明
$$
c^d\equiv m(modn)
$$

$$
根据加密规则m^e\equiv c(mod n)
$$

$$
c=m^e-kn
$$

$$
带入加密规则(m^e-kn)^d\equiv m(mod n)
$$

消除kn^d
$$
m^{ed}\equiv m(modn)
$$

$$
因为ed\equiv 1(mod phi_n)
$$

$$
所以ed=h(phi_n)+1
$$

$$
m^{h*(phi_n)+1}\equiv m \pmod{n}
$$

分情况

m与n互质

根据欧拉定理此时
$$
m^{φ(n)} ≡ 1 (mod n)
$$
得到
$$
(m^{φ(n)})^h × m ≡ m (mod n)
$$

m与n不互质

此时，由于n等于质数p和q的乘积，所以m必然等于kp或kq。

以 m = kp为例，考虑到这时k与q必然互质，则根据欧拉定理，下面的式子成立：

$$
(kp)^{q-1} ≡ 1 (mod q)
$$

$$
[(kp)^{q-1}]^{h(p-1)} × kp ≡ kp (mod q)
$$

$$
即　　(kp)^{ed} ≡ kp (mod q)
$$

$$
改写　(kp)^{ed} = tq + kp\
　 (kp)ed = t’pq + kp\
　 因为 m=kp，n=pq，所以\
　 　　m^{ed }≡ m (mod n)
$$

RSA密钥生成与读取

公钥、私钥生成

from Crypto.PublicKey import RSA
import libnum
import gmpy2

p=libnum.generate_prime(1024)
q=gmpy2.next_prime(p)
n=p*q
phi_n=(p-1)*(q-1)
e=65537
d=gmpy2.invert(e,phi_n)

#生成公钥
rsa_components=(int(n),int(e))
keypair=RSA.construct(rsa_components)
with open('pubckey.pem','wb')as f:
    f.write(keypair.exportKey())

#生成私钥
rsa_components=(int(n),int(e),int(d))
keypair=RSA.construct(rsa_components)
with open('private.pem','wb')as f:
    f.write(keypair.exportKey())

基本出题原理

import libnum
import gmpy2

p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
n=p*q
e=65537
phi_n=(p-1)*(q-1)
d=gmpy2.invert(e,phi_n)
flag='flag{c248ad62-d5de-469e-a856-b823a67d08bf}'
m=libnum.s2n(flag)
c=pow(m,e,n)

print("n=",n)
print("e=",e)
print("d=",d)
print("c=",c)

基于N分解的rsa题目

费马分解

主要用于p、q接近的情况
$$
n=a^{2}-b^{2}=(a+b)(a-b)
$$
令p=a+b，q=a-b就分解出了n=p*q

为什么p，q相近时有效

若p≈q，则：
$$
a=（p+q）/2≈\sqrt{n}\
b=(p-q)/2≈0
$$

$$
所以
a 非常接近 \sqrt{n}
，从 ⌈n⌉\开始往上搜索，很快就能找到满足条件的
a。

反之，若
p、
q 差距很大，\
b 也会很大，
a 距离 n\sqrt{n}\
n​ 很远，需要迭代极多步，算法退化。
$$

出题脚本

import libnum
import gmpy2



flag='flag{0699946d-f9b3-4d4b-a033-baf75af95d13}'
p=libnum.generate_prime(1024)
q=gmpy2.next_prime(p)
n=p*q
e=65537

m=libnum.s2n(flag)
c=pow(m,e,n)
print("n=",n)
print("e=",e)
print("c=",c)

n= 16290466342838210653504598493316331708587060781419114066151509695322093995785139350813769223100018177571592036131101173742297768069652540301012610058053921590502996562352044556821525730844956966260365784636221970748015234834941506363233110978161361455825483360423372540669890058019934295111311313832433308981795809877707868211726927789191580556161256828770274143990004479270507678293606587738535030689582281446452887993966167750877206680026601488955988240299292080083782069851906937848949401976680161901196292233751201825016300015157486003734045580377429851477864775066420027874396978375483290661627757648799241367157
e= 65537
c= 4498561497986519156163815308454421441860929811674829270313449648169619791206287925774004606208420768283264743854310851626628145294716076122221633534515311970771475828463804922670999094709918524599588586663172701990594432783349185922126621998950279266506179893445424607311398056828509584637099478107604419684560167002447375500434478179561430493403252837179916973785570560422901729322470133422779531346027657565837615046405835202065350231441027341665665717663571262579609839635914448761212365626684713720174317243885020478225195866629166535214807499279094148126946100053737687412428909580146857138190336757663958401679

exp

from math import isqrt

n= 16290466342838210653504598493316331708587060781419114066151509695322093995785139350813769223100018177571592036131101173742297768069652540301012610058053921590502996562352044556821525730844956966260365784636221970748015234834941506363233110978161361455825483360423372540669890058019934295111311313832433308981795809877707868211726927789191580556161256828770274143990004479270507678293606587738535030689582281446452887993966167750877206680026601488955988240299292080083782069851906937848949401976680161901196292233751201825016300015157486003734045580377429851477864775066420027874396978375483290661627757648799241367157
e = 65537
c= 4498561497986519156163815308454421441860929811674829270313449648169619791206287925774004606208420768283264743854310851626628145294716076122221633534515311970771475828463804922670999094709918524599588586663172701990594432783349185922126621998950279266506179893445424607311398056828509584637099478107604419684560167002447375500434478179561430493403252837179916973785570560422901729322470133422779531346027657565837615046405835202065350231441027341665665717663571262579609839635914448761212365626684713720174317243885020478225195866629166535214807499279094148126946100053737687412428909580146857138190336757663958401679
  

a = isqrt(n) + 1  #a=(p+q)/2>根号p*q=根号n，可以发现a一定大于根号n
b2 = a * a - n   # b2=b^{2}

#找到b^{2}为完全平方数停止，不然a+1
while True:
    b = isqrt(b2)
    if b * b == b2:
        break
    a += 1
    b2 = a * a - n

p, q = a - b, a + b
print(f"p = {p}")
print(f"q = {q}")
assert n==p*q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(m.to_bytes((m.bit_length() + 7) // 8, "big"))

dp，dq泄密

模p

m=c^d%n
m=c^d-k*n

m=c^d-k*p*q
#两边同时模p
m%p=c^d%p
#因为m<p
m=c^d%p
#即只要m<p/q只需要模p/q就可以了

模dp

c=m^e mod n
m=c^d mod n
phi_n=(p-1)*(q-1)
d*e≡1 mod phi_n
dp=d mod(p-1)
dq=d mod(q-1)

gcd(p,q)=1
n=p*q
#根据中国剩余定理
m1=c^d mod p
m2=c^d mod q

dp=d mod(p-1)
dp=d-k*(p-1)
d=dp+k*(p-1)

m=c^d mod n
m=c^d mod p
m=c^(dp+k*(p-1))mod p
m=(c^dp*c^(k*(p-1)))%p
#根据费马小定理 任意a^{p-1}=1%p
即c^k*(p-1)%p=1
m=c^dp%p

出题脚本

import gmpy2
import libnum


flag="flag{d5669498-6b49-4a0c-a52c-7ed522e1fb06}"
m=libnum.s2n(flag)
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=65537
n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
dp=d%(p-1)
dq=d%(q-1)
c=pow(m,e,n)
print("p=",p)
print("q=",q)
print("c=",c)
print("dp=",dp)
print("dq=",dq)

p= 101489347482547067109673618422166113631163911050641526700944866710707812256549977617479875716456322681871911368393359769820399280338616065977353823895473930278752762384076169434491147374428884271495324567520191078864488230748885074059996844573963394737398498150793875613037464108524120193513421251190193442201
q= 173924099615913993014541292024384134889346572808429220821705016228017710852658253971289385464387995109482513776083692337950585229912361648193410959486789225523518567767094721915427732996519631330901613845214634952000611151470597161154994955115860486418842809588054455952634306713199306181221877117331066144417
c= 9439535009117178021162033048193292661359367935646595396152109199344161160939837363276129577508939582116874602845587430523317594815049115962243518984480723889365526986606040440326230940343930772623936214835104951044046249388184175568241943215950456495422668170870426969634327058167848685027324027502193919530728917813297685669967722164781931547864105130196125373179222052497574080381341440343306467849490584555773158979415666799837791491763064435087997030017688799578759729093442887402685510451846154480882423352385819531935941975448514974919104060226042622099584503877824491214204600584634772847573773357312907993899
dp= 50624658720294584294098604755161701339951163711438151721631881801726491760057300735356128859219580462838925409221467632561738756329244515508272790285898626039377856098048950287363628161457720916725722194131598433848955319154245723119693560064809761468487942735364795270851698112085722771047610572999353248073
dq= 147489292464623587832463293186248572266205733103457014760930130794639856849525231895087948587344968738340177084999729700382100565140446022246929329759338968791599675331859198089198646398440194559503610038018959550977096378444693956518455218052688746711225841672119786441607095684769895483888292760925756931841

exp

import gmpy2
import libnum


p= 101489347482547067109673618422166113631163911050641526700944866710707812256549977617479875716456322681871911368393359769820399280338616065977353823895473930278752762384076169434491147374428884271495324567520191078864488230748885074059996844573963394737398498150793875613037464108524120193513421251190193442201
q= 173924099615913993014541292024384134889346572808429220821705016228017710852658253971289385464387995109482513776083692337950585229912361648193410959486789225523518567767094721915427732996519631330901613845214634952000611151470597161154994955115860486418842809588054455952634306713199306181221877117331066144417
c= 9439535009117178021162033048193292661359367935646595396152109199344161160939837363276129577508939582116874602845587430523317594815049115962243518984480723889365526986606040440326230940343930772623936214835104951044046249388184175568241943215950456495422668170870426969634327058167848685027324027502193919530728917813297685669967722164781931547864105130196125373179222052497574080381341440343306467849490584555773158979415666799837791491763064435087997030017688799578759729093442887402685510451846154480882423352385819531935941975448514974919104060226042622099584503877824491214204600584634772847573773357312907993899
dp= 50624658720294584294098604755161701339951163711438151721631881801726491760057300735356128859219580462838925409221467632561738756329244515508272790285898626039377856098048950287363628161457720916725722194131598433848955319154245723119693560064809761468487942735364795270851698112085722771047610572999353248073
dq= 147489292464623587832463293186248572266205733103457014760930130794639856849525231895087948587344968738340177084999729700382100565140446022246929329759338968791599675331859198089198646398440194559503610038018959550977096378444693956518455218052688746711225841672119786441607095684769895483888292760925756931841

# 法一
m=pow(c,dp,p)
print(libnum.n2s(int(m)))

#法二
def decrypt(dp,dq,p,q,c):
    InvQ=gmpy2.invert(q,p)
    mp=pow(c,dp,p)
    mq=pow(c,dq,q)
    m=(((mp-mq)*InvQ)%p)*q+mq
    print(libnum.n2s(int(m)).decode())

decrypt(dp,dq,p,q,c)

共模攻击(同模攻击)

同一明文，同一n，不同e进行加密

m,n相同 e，c不同，且e1，e2互质
$$
c1=pow(m,e1,n)\
c2=pow(m,e2,n)\
gcd(e1,e2)=1\
\
根据扩展欧几里得算法，对不完全为0的整数a，b，存在gcd(a,b)=ax+by\
\
->e1s1+e2s2=1
$$

$$
m^{1} % n
$$
出题脚本

import libnum
import gmpy2

p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
n1=p*q
n2=p*q
e1=2333
e2=23333
flag='flag{91e99e9e-a3e0-4c69-871d-c266d4236c69}'
m=libnum.s2n(flag)
c1=pow(m,e1,n1)
c2=pow(m,e2,n2)
print("n1=",n1)
print("n2=",n2)
print("e1=",e1)
print("e2=",e2)
print("c1=",c1)
print("c2=",c2)
n1= 21470383416523032205317773080412106910790260834841133836275605514150147972017060131067995673203180688788098510103602971280307371138583861170622293525440199055673008676348244121282682266369187902359833090841517639258732456242192755501139848622453259115286188942302035851898605658388782669039211632190120278769651176426444487369409410782025580167186326986474046561395643287484045983452321035118734461060228047317031465893487334303374703573715563930128025996052094575891033941839165748187669449468123636292014007189901699235954617691389844991311488945378574327904418816896702087915558439292169849141751720480058753294623
n2= 21470383416523032205317773080412106910790260834841133836275605514150147972017060131067995673203180688788098510103602971280307371138583861170622293525440199055673008676348244121282682266369187902359833090841517639258732456242192755501139848622453259115286188942302035851898605658388782669039211632190120278769651176426444487369409410782025580167186326986474046561395643287484045983452321035118734461060228047317031465893487334303374703573715563930128025996052094575891033941839165748187669449468123636292014007189901699235954617691389844991311488945378574327904418816896702087915558439292169849141751720480058753294623
e1= 2333
e2= 23333
c1= 8544520767167684863754182024978418105941521372757818582091487828118603715250105135154168557433646392354741205515715518865430523441579003829709267333198239037107232382347646908074089654153667624537398580447922632289860121465342244752735821141400767212179856249852130195217848346522103361892430335251858405986487450319170547247476099184825895694257803627087842853186288455481847701738659114854740262727452902185071421909274134482949933250181201392206636159548985230708421382714233385612661480317304027250526618112951813272110005103849356331179073822581826072484126034670284518981454379317343505996893348402749933853488
c2= 15597187527075025875064860495763256682941094651606261651315181591356706529113784109230894676348804288438333256337745718406178142199347043644608911175639775139095816449252257722227749061449668967475479128401543411428014282144625845660307654242256480476039278162837826753096499248623210385955907615138703709796881868302089727008996158646145110196929785214656732904921362213157800343555706305268586178440004707304165924985247707271104487083941215200045585604995950676045095274042680547254524074451399448048598426484344048735746684996734752149876901123111250235824721656808154514432335858022980226550483013418819659430459

exp

from Crypto.Util.number import bytes_to_long, long_to_bytes

n1= 21470383416523032205317773080412106910790260834841133836275605514150147972017060131067995673203180688788098510103602971280307371138583861170622293525440199055673008676348244121282682266369187902359833090841517639258732456242192755501139848622453259115286188942302035851898605658388782669039211632190120278769651176426444487369409410782025580167186326986474046561395643287484045983452321035118734461060228047317031465893487334303374703573715563930128025996052094575891033941839165748187669449468123636292014007189901699235954617691389844991311488945378574327904418816896702087915558439292169849141751720480058753294623
n2= 21470383416523032205317773080412106910790260834841133836275605514150147972017060131067995673203180688788098510103602971280307371138583861170622293525440199055673008676348244121282682266369187902359833090841517639258732456242192755501139848622453259115286188942302035851898605658388782669039211632190120278769651176426444487369409410782025580167186326986474046561395643287484045983452321035118734461060228047317031465893487334303374703573715563930128025996052094575891033941839165748187669449468123636292014007189901699235954617691389844991311488945378574327904418816896702087915558439292169849141751720480058753294623
e1= 2333
e2= 23333
c1= 8544520767167684863754182024978418105941521372757818582091487828118603715250105135154168557433646392354741205515715518865430523441579003829709267333198239037107232382347646908074089654153667624537398580447922632289860121465342244752735821141400767212179856249852130195217848346522103361892430335251858405986487450319170547247476099184825895694257803627087842853186288455481847701738659114854740262727452902185071421909274134482949933250181201392206636159548985230708421382714233385612661480317304027250526618112951813272110005103849356331179073822581826072484126034670284518981454379317343505996893348402749933853488
c2= 15597187527075025875064860495763256682941094651606261651315181591356706529113784109230894676348804288438333256337745718406178142199347043644608911175639775139095816449252257722227749061449668967475479128401543411428014282144625845660307654242256480476039278162837826753096499248623210385955907615138703709796881868302089727008996158646145110196929785214656732904921362213157800343555706305268586178440004707304165924985247707271104487083941215200045585604995950676045095274042680547254524074451399448048598426484344048735746684996734752149876901123111250235824721656808154514432335858022980226550483013418819659430459
#e1,e2互素  gcd=1
import libnum
import gmpy2


#欧几里得扩展
s,s1,s2=gmpy2.gcdext(e1,e2)
print(s,s1,s2)
m=(pow(c1,s1,n1)*pow(c2,s2,n2)%n1)
print(libnum.n2s(int(m)))

题目

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

给定一个共同的模数n
$$
c1 ≡ m^{e1} \pmod n
$$

$$
c2 ≡ m^{e2} \pmod n
$$

由扩展欧几里得算法可以找到s1，s2

e1s1+e2s2=1

$$
c1^s1 · c2^s2 ≡ m^(e1·s1 + e2·s2) ≡ m^1 ≡ m (mod n)
$$

题解

import gmpy2
from Crypto.Util.number import *
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291
#验证gcd(e1,e2)=1
#扩展欧几里得算法
def extend_gcd(a,b):
    if b==0:
        return a,1,0
    g,x,y=extend_gcd(b,a%b)
    return g,y,x-(a//b)*y   #x-(a//b)*y取余数

g,s1,s2=extend_gcd(e1,e2)
print(f"s1={s1},s2={s2}")
print(f"验证：e1*s1+e2*s2={e1*s1+e2*s2}")

#共模攻击
#考虑s1<0
if s1<0:
    c1=pow(c1,-1,n)
    s1=-s1
if s2<0:
    c2=pow(c2,-1,n)
    s2=-s2
m=pow(c1,s1,n)*pow(c2,s2,n)%n
flag=bytes.fromhex(hex(m)[2:]).decode('utf-8',errors='replace')
print(f"flag={flag}")

dp泄露

第一种理解

c=m^e mod n
m=c^d mod n
phi=(p-1)*(q-1)
d*e≡1 mod phi
dp=d mod(p-1)

->dp=d mod(p-1)
#两边同时乘e
dp*e=d*e mod(p-1)
dp*e=d*e-k*(p-1)
1、d*e=dp*e+k(p-1)
2、d*e≡1 mod phi
#合并两个式子
k*(p-1)+dp*e≡ 1 mod phi
k*(p-1)+dp*e≡ 1 mod (p-1)*(q-1)
k1*(p-1)+dp*e=k2*(p-1)*(q-1)+1
dp*e-1=k2(p-1)*(q-1)-k1*(p-1)
      =(p-1)[k2*(q-1)-k1]
    dp<(p-1)则e=65537>[k2*(q-1)-k1]
脚本中就是把[k2*(q-1)-k1]当作一个整体进行枚举

第二种理解

$$ dp = d \pmod {p-1}\\ 已知关系：

e⋅d≡1(modλ(n))\

\lambda=lcm(p-1,q-1)=\frac{(p-1)(q-1)}{gcd(p-1,q-1)}\
\所以(p-1)|\lambda(n)，从而ed_{p}\equiv1\pmod {p-1}\
存在某个正整数k使得
ed_{p}=k(p-1)+1
\
->进一步变形\
p=\frac{e*d_{p}-1}{k}+1
$$
接下来枚举k就能还原p

k的范围：因为k<e

``出题脚本`

import gmpy2
import libnum


flag="flag{d5669498-6b49-4a0c-a52c-7ed522e1fb06}"
m=libnum.s2n(flag)
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=65537
n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
dp=d%(p-1)
c=pow(m,e,n)
print("n=",n)
print("c=",c)
print("e=",e)
print("dp=",dp)

n= 17377277405201156805742531167354045259708771107274319592513868834745507369072106587330706735505619583760175108740795227754165623544999713286721596401822278775741700562897354412971305335762302376356369645438678013088897197463506870023052042521388315901880819991791994803924331101003050286060991616426079057542117141434101099763043415070717585421374338191639005609703526555202250740926127604503935819750905568635255222152864877613911600066415582347400500173079511432779850371250816460924175549751714633154149284985304062061952819345886553431005059340161697130697498368526599244699438461389763105816841633220873579205407
c= 6974166609735941990528969199336075944330636809090040949842700030534693936449298280112300425406597646933830761793174046528450595308102821166645492513983135461412141250205994617298531178422816420205592656599408467601146303615947529456444972859291464203180336359532994286038059444407072931639344766917731041503782291013881892281347329296217726687156244457242623433811219534461058086079111914434973694843745826909451005182038061894785351969584533881987590404618151698035941500941145979501794145568245711327860374819397324048571507503663171136320554811213294093738968968902133675961897128818078285688495548962264307419089
e= 65537
dp= 78206905677192569717811461862426477200840360445024817778137627921233681153208920106938465196985444947780786102239388785604622796322575139695582049603394380762191671998623171536030210898287030755581587633657152345408415580547659830702794186051314850108852947918666380581540858316070303280730313325162095710333

exp

import gmpy2
import libnum


n= 17377277405201156805742531167354045259708771107274319592513868834745507369072106587330706735505619583760175108740795227754165623544999713286721596401822278775741700562897354412971305335762302376356369645438678013088897197463506870023052042521388315901880819991791994803924331101003050286060991616426079057542117141434101099763043415070717585421374338191639005609703526555202250740926127604503935819750905568635255222152864877613911600066415582347400500173079511432779850371250816460924175549751714633154149284985304062061952819345886553431005059340161697130697498368526599244699438461389763105816841633220873579205407
c= 6974166609735941990528969199336075944330636809090040949842700030534693936449298280112300425406597646933830761793174046528450595308102821166645492513983135461412141250205994617298531178422816420205592656599408467601146303615947529456444972859291464203180336359532994286038059444407072931639344766917731041503782291013881892281347329296217726687156244457242623433811219534461058086079111914434973694843745826909451005182038061894785351969584533881987590404618151698035941500941145979501794145568245711327860374819397324048571507503663171136320554811213294093738968968902133675961897128818078285688495548962264307419089
e= 65537
dp= 78206905677192569717811461862426477200840360445024817778137627921233681153208920106938465196985444947780786102239388785604622796322575139695582049603394380762191671998623171536030210898287030755581587633657152345408415580547659830702794186051314850108852947918666380581540858316070303280730313325162095710333

for i in range(1,65537):
    p=(dp*e-1)//i+1
    if n%p==0:
        q=n//p
        break

print(p)
print(q)
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(libnum.n2s(int(m)))

wiener(维纳)攻击脚本

e指数很大（理论上d<N**0.25）

利用连分数逼近从公钥 (e, N) 中直接恢复 d。

$$
由ed-k*phi(N)=1\
|\frac{e}{N}-\frac{k}{d}|=\frac{1-k(N-\phi(N))}{dN}<\frac{1}{dN^{\frac{1}{2}}}\
\
利用了N-\phi(N)\approx p+q<3\sqrt{N},以及d<\frac{1}{3}N^{\frac{1}{4}}\

\
正好满足了 连分数逼近定理（Legendre 定理）\若 |x - p/q| < 1/(2q^2)
\则p/q必为x 的某阶渐近分数。因此 k/d
一定会出现在
e/N 的连分数展开序列中
$$
exp

cf=continued_fraction(Integer(e)/Integer(N))
for frac in cf.convergents():
    k=frac.numerator()
    d=frac.denominator()
    if k==0:
        continue
    #e*d-1必须整除k
    if (e*d-1)%k!=0:
        continue
    phi=(e*d-1)//k
    if phi<=0:
        continue
    b=N-phi+1
    delta=b^2-4*N
    if delta>=0 and Integer(delta).is_square():
        p=(b+Integer(delta).isqrt())//2
        q=(b-Integer(delta).isqrt())//2
    if p*q==N:
        print(f"d={d}")
        print(f"p={p},q={q}")
        break
    

低加密指数攻击

加密指数e，一般选取65537

当e很小时可以直接破译，一般e=3
$$
如果e=3，m^{e}<n \
c开3次根式得到m\
如果e=3，且m^{e}>n,那么设k，有：c=m^{e}+kn\
爆破k,如果c-kn能开三次根式，得到m
$$

gmpy2.iroot(x, n) 的作用

gmpy2.iroot(x, n) 计算整数的 n 次方根，返回一个元组 (root, exact)：

• root：⌊x1/n⌋\lfloor x^{1/n} \rfloor ⌊x1/n⌋，即向下取整的整数 n 次根
• exact：布尔值，若 root^n == x 则为 True，否则为 False

出题脚本

import libnum
import gmpy2



e=3
m="flag{9af5c4d8-2945-40cd-ac4e-ecf48781657d}"
m=libnum.s2n(m)

while True:
    p = libnum.generate_prime(502)
    q = libnum.generate_prime(502)
    e = 3
    n = p * q
    phi_n = (p - 1) * (q - 1)
    if gmpy2.gcd(e,phi_n)==1:
        break


c=pow(m,e,n)

print("n=",n)
print("e=",e)
print("c=",c)

n= 123686794281651627687924729229074454149792082628480218135022051645824564787474676962649347948802550638431117648531461723762514213518487604932439613749117409812142901792727242581127147001893270200328458026996613089865022579123676046327835721100980479004913374200037469486562854492084468079707905599520169
e= 3
c= 51989355984780297516552934579149418903234050810577579725299302820617993142810044581688340881884178318438512966462495420407219842915795721289096370511773313225735868960023048861446550385573041380295485861971267909690803588306196517088891599255707844571208421852408732943386149916483102731156964864465852

exp

import libnum
import gmpy2

n= 123686794281651627687924729229074454149792082628480218135022051645824564787474676962649347948802550638431117648531461723762514213518487604932439613749117409812142901792727242581127147001893270200328458026996613089865022579123676046327835721100980479004913374200037469486562854492084468079707905599520169
e= 3
c= 51989355984780297516552934579149418903234050810577579725299302820617993142810044581688340881884178318438512966462495420407219842915795721289096370511773313225735868960023048861446550385573041380295485861971267909690803588306196517088891599255707844571208421852408732943386149916483102731156964864465852

def exp(n,e,c):
    k=0
    while 1:
        m1=k*n+c
        m,t=gmpy2.iroot(m1,e)
        if t:
            print(m)
            print(k)
            print(libnum.n2s(int(m)))
            break
        k+=1

exp(n,e,c)

低加密指数广播攻击

选取加密指数较低，并且使用相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文

n，c不同，明文m，e相同，其e比较小，使用扩展中国剩余定理

N不互素（共享素数）

两个n里使用有相同素数p或q在CTF中，同样一个e（一般为65537）和m，有两个或多个n和c时，那么n之间可能是共享素数。

出题脚本

import gmpy2
import libnum

flag="flag{8fe9018f-a519-408a-9ff2-a1c2d64286bb}"
m=libnum.s2n(flag)
p=libnum.generate_prime(1024)
q1=libnum.generate_prime(1024)
q2=libnum.generate_prime(1024)
n1=p*q1
n2=p*q2
e=65537
c1=pow(m,e,n1)
c2=pow(m,e,n2)
print("n1=",n1)
print("n2=",n2)
print("c1=",c1)
print("c2=",c2)

n1= 21132104988497221866479580499499524802212602171432260688282063504597167707804294832572651841102290034012274413794023419798816589125245193348002379588804318392587323426562415019104046025144440534113793608097934579479372712222488369742817031939224057451734348033990072730823181013146794607379665802090973158593011107358903680514705037972248874698691466740974943331622539967737794414888698478118388494527460613030583811933373975680060061814157458639617914703341680601582865047417493321953039697984259479130975852752061481855548796248528741028752067640336730691158376359540917410219569802309254835040197174258455502661643
n2= 21132104988497221866479580499499524802212602171432260688282063504597167707804294832572651841102290034012274413794023419798816589125245193348002379588804318392587323426562415019104046025144440534113793608097934579479372712222488369742817031939224057451734348033990072730823181013146794607379665802090973158593011107358903680514705037972248874698691466740974943331622539967737794414888698478118388494527460613030583811933373975680060061814157458639617914703341680601582865047417493321953039697984259479130975852752061481855548796248528741028752067640336730691158376359540917410219569802309254835040197174258455502661643
c1= 21132104988497221866479580499499524802212602171432260688282063504597167707804294832572651841102290034012274413794023419798816589125245193348002379588804318392587323426562415019104046025144440534113793608097934579479372712222488369742817031939224057451734348033990072730823181013146794607379665802090973158593011107358903680514705037972248874698691466740974943331622539967737794414888698478118388494527460613030583811933373975680060061814157458639617914703341680601582865047417493321953039697984259479130975852752061481855548796248528741028752067640336730691158376359540917410219569802309254835040197174258455502661643
c2= 21132104988497221866479580499499524802212602171432260688282063504597167707804294832572651841102290034012274413794023419798816589125245193348002379588804318392587323426562415019104046025144440534113793608097934579479372712222488369742817031939224057451734348033990072730823181013146794607379665802090973158593011107358903680514705037972248874698691466740974943331622539967737794414888698478118388494527460613030583811933373975680060061814157458639617914703341680601582865047417493321953039697984259479130975852752061481855548796248528741028752067640336730691158376359540917410219569802309254835040197174258455502661643

exp

import gmpy2
import libnum


n1= 24557551741430206839845054267937792689705746815357001070850635130331051734809288216289728903861439917837841474919312699790623797788672141145389461133444455034463716830825125872080657576895656880822108121327296826226843538889226555949726713149534184652742626589658519218641650833960975030490706714656906849889395751850198175972019776027384596893603707668857639909872395137759561066223593794715921031364209123015778173237678273494919878234654983868734762072029220959549825975483525437825496795892355313604204076997646431221378640684876992966697153206606399252049397445089292049462694169595493102052146947239642912010371
n2= 14102169165416385291090778049651976114616889205466686272521039140777564794678945533542069048670836968230446660985150618651182512255229066227152554977871156324410903026178097752319690842694266671687500557716825828965574758502469485347676488293885881086476751440550321572156205747594836421431232599059950220412910666503111466573143110840403744444839032022003096527544846322987666918279058499261603857353007845414505244523144295102867874023149617439630085799717594721772297466995522512623849101158075192298399015961569611819097605893399011735106913460994123013149422842269328089424498916444390201408524579916726142535207
c1= 1796247511503556081647321723183341266455009804873850889900392501079303742735417783550615676053607920707013918441572290476539177046618123433613791387858849722345597666279301231914535387873075026446624312758647151961776091149829315397440833703941040061267421250380171089553740448914267412755229057535676219402123194576328179164346654643942973771273120030318969379186826394072606014810997801262940858558310141223507510887798235662036388512636039303723310103525316519967020978120480487207085856967920683362454164210833098546593490471044593183323992996547633111727553905541206078609173526639128091439670154728013594535823
c2= 4625883763604540136236914857928115049443398147785845063735250932919683965015478306247086986579837585389771252746073392862045144087866084706169521129882601693657365413098727130756179196987147201004030440955308850887225479330526826796156472431305949676816171283888191012196239756654852722503149473565820204896622398989044421377055209778530522431360305538502624907406848037897622858468822745694148414572250860681876157102069498381197460402536515607821576408850390905873777341777287223495401225378825977801830438419551141146461578382399884241358059147676808264060455929347694954552447464110671963512728905208121127148615
e=65537

p=gmpy2.gcd(n1,n2)
print(p)
q=n1//p

phi_n=(p-1)*(q-1)
d=gmpy2.invert(e,phi_n)
m=pow(c1,d,n1)
print(libnum.n2s(int(m)))

e和phi_n不互素

求出b=gcd(e,phi)，然后把e里面的b因子除掉bb=e//b

bb就会与phi互素，进而可以得到a=gmpy2.invert(bb,phi)

c^a=m^{b*bb*a}(mod n)

因为bb*a (mod phi)同余1

c^a同余m^b(mod n)

即mm=m^b(进行开b次方就可以得到明文m)

n是p的r次方

欧拉函数phi_n的定义是小于n的自然数中与n互质的数的个数，p^{r}的质因数就只有p，那么不与它互质的数都包含p，和他不互质的数的个数：p^{r}/p=p^{r-1},剩下的都是和它互质的数即phi_n=p^{r}-p^{r-1}

n=p^{r},p为素数，没有q了，因为p=q

那么计算n的欧拉函数phi_n就是

$$
phi_{n}=p^{r}-p^{r-1}
$$

素数分解

sagemath

PR= PolynomialRing(Zmod(r))
(1)Zmod(r):指定模，定义界限为r的环；Z表示整数；指定模是划定这个环的界限，就是有效的数字只有从0到r，其他的都通过与r取模来保证在0～r这个范围内；Zmod代表这是一个整数域中的r模环。
ZZ：整数环；QQ：有理数环；RR：实数环；CC：复数环
(2)R：只是一个指针，指向用polynomialring指定的那个环（可以使用任意字符）
(3)PolynomialRing：这个就是说建立多项式环
(4)：指定一个变量的意思（可以用任意字符）,一般用x
(5) f=(x^2)-a则是定义一个函数f（math.rsa）那道题
(6) ans=f.roots()是求解f中所有满足函数的自变量
2、得到p之后，来验证p*q==n是否成立，经验证发现第一个p即满足，下面就很好做了，经典RSA类型，直接上脚本

n分解三个素数

法一:利用工具

对n进行分解，得到了3个素数 n=p*q*r

NC不互素

c=pow(m*p,e,n)
c=(m*p)^e%n
c=(m*p)^e-kp*q
#两边同时模p
c%p=m^e%p*p^e%p
   =0
#p是c的因数
p=gcd(c,n)

sagemath
coppersmith

sage脚本

coppersmith

1、建立整数模 n 的环 Z/nZ\mathbb{Z}/n\mathbb{Z} Z/nZ，也就是说所有运算都在模 nn n 下进行

2、在这个环上建立多项式环，x 是符号变量

P.<x> = PolynomialRing(R)

3、写方程

f = high_part + x        # 一次多项式
f = x^2 + 3*x + high    # 二次多项式
f = (high + x)^e - c    # 任意组合

标准RSA，p ≈ q ≈ √N

roots = f.small_roots(X=2^128, beta=0.5)

不确定时保守一点

roots = f.small_roots(X=2^128, beta=0.4)

如果0.5找不到，试着调小

roots = f.small_roots(X=2^128, beta=0.49)