RSA的一团乱麻

网址：

公钥解析：http://www.hiencode.com/pub_asys.html

一、基础知识：

1、密钥对

（1）公钥：（e,n)

（2）私钥： (d,n)

2、公式

（1）加密：
$$
C = M^e mod N
$$
（2）解密：
$$
M = C^dmodN
$$

3、加密过程

（1）选择两个素数p，q

条件：
$$
p \neq q
$$

(2)计算模数n

$$
n = p*q
$$

（3）计算欧拉函数 ϕ(n)

phi = (p−1) * (q−1)

（4）选择公钥指数e

条件：

1、

$$
1 < e < ϕ(n)
$$

2、e与ϕ(n)互质

$$
gcd(e,ϕ(n)) = 1
$$

(5)计算私钥指数d

私钥指数d是公钥指数e的模逆
$$
d \times e \equiv 1 (mod ϕ(n))
$$
(d是使d*e与ϕ(n)同余1的最小整数)

二、共模攻击

1、RSA共模攻击的条件

• 有两个或多个RSA公钥使用相同的模数 ( n )。
• 每个公钥有不同的公钥指数 ( e_1, e_2, \dots, e_k )，但是模数 ( n ) 是相同的。
• 攻击者能够获得使用不同公钥加密的相同明文（或明文相同的加密密文）。

2、共模攻击的基本思路

由于模数 ( n ) 是相同的，可以利用中国剩余定理（Chinese Remainder Theorem，CRT）来解这个问题，从而恢复出原始的明文 ( m )。

共模攻击的步骤

1. 收集密文：假设有多个公钥 ( (e_1, n) ), ( (e_2, n) ), …, ( (e_k, n) )，并且攻击者获得了加密后的密文 ( c_1 = m^{e_1} \mod n )，( c_2 = m^{e_2} \mod n )，… ( c_k = m^{e_k} \mod n )。

2. 使用中国剩余定理（CRT）：根据中国剩余定理，给定一组模数和对应的余数，可以求解出一个唯一的解。对于 RSA 共模攻击，攻击者可以使用中国剩余定理来将这些不同指数的密文合成一个等效的方程组。这个过程的数学原理是将加密后的密文进行“结合”，从而恢复出原始明文的一个模 ( n ) 的值。

3. 求解出原始明文：通过求解方程组，攻击者能够恢复出 ( m ) 的值。由于中国剩余定理的作用，密文会被“合并”到一个合成的方程式中，进而通过模逆操作求解出原始明文。(分段明文相乘)%n=明文

数学原理

假设：

• ( c_1 = m^{e_1} \mod n )
• ( c_2 = m^{e_2} \mod n )
• …
• ( c_k = m^{e_k} \mod n )

我们需要求解出 ( m )。

通过中国剩余定理（CRT）：

假设我们有方程：
$$
[
m^{e_1} \equiv c_1 \pmod{n}
]、[m^{e_2} \equiv c_2 \pmod{n}]、[…]、[m^{e_k} \equiv c_k \pmod{n}]
$$

然后，我们通过中国剩余定理（CRT）将这些模数和余数的方程结合起来，得到一个统一的模 ( n ) 方程。接着，通过模运算、求逆等方法，攻击者可以恢复出原始明文 ( m )。

解决共模攻击的防护方法

1. 避免使用相同的模数 ( n )：最简单的防护措施是确保每个RSA公钥使用不同的模数 ( n )。这样，即使公钥指数 ( e ) 相同，攻击者也无法进行共模攻击。

2. 使用不同的公钥指数 ( e )：如果多个系统或用户共享相同的 ( n )，则可以选择不同的公钥指数 ( e )，尽量避免攻击者能够获得不同公钥加密的相同明文。

3. 使用签名而非直接加密：可以采用RSA签名的方式进行安全验证，而不是直接加密明文，进一步增加攻击的难度。

4. 增加额外的加密层：结合其他加密算法，如使用对称加密算法（例如AES）对数据进行加密，再使用RSA进行密钥传输，可以有效地避免单纯的RSA共模攻击。

攻防世界best_rsa

解密

from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy2
f1 = open("G:\\crpyto learning\\攻防世界\\best_rsa\\publickey1.pem","rb").read()
f2 = open("G:\\crpyto learning\\攻防世界\\best_rsa\\publickey2.pem","rb").read()
c1 = open("G:\\crpyto learning\\攻防世界\\best_rsa\\cipher1.txt","rb").read()
c2 = open("G:\\crpyto learning\\攻防世界\\best_rsa\\cipher2.txt","rb").read()
pub1 = RSA.importKey(f1)
pub2 = RSA.importKey(f2)
n1 = pub1.n
e1 = pub1.e
n2 = pub2.n
e2 = pub2.e
c1 = bytes_to_long(c1)
c2 = bytes_to_long(c2)
print("n1 =",n1)
print("e1 =",e1)
print("c1 =",c1)
print("n2 =",n2)
print("e2 =",e2)
print("c2 =",c2)
n1 = 13060424286033164731705267935214411273739909173486948413518022752305313862238166593214772698793487761875251030423516993519714215306808677724104692474199215119387725741906071553437840256786220484582884693286140537492541093086953005486704542435188521724013251087887351409946184501295224744819621937322469140771245380081663560150133162692174498642474588168444167533621259824640599530052827878558481036155222733986179487577693360697390152370901746112653758338456083440878726007229307830037808681050302990411238666727608253452573696904083133866093791985565118032742893247076947480766837941319251901579605233916076425572961
e1 = 117
c1 = 12847007370626420814721007824489512747227554004777043129889885590168327306344216253180822558098466760014640870748287016523828261890262210883613336704768182861075014368378609414255982179769686582365219477657474948548886794807999952780840981021935733984348055642003116386939014004620914273840048061796063413641936754525374790951194617245627213219302958968018227701794987747717299752986500496848787979475798026065928167197152995841747840050028417539459383280735124229789952859434480746623573241061465550303008478730140898740745999035563599134667708753457211761969806278000126462918788457707098665612496454640616155477050
n2 = 13060424286033164731705267935214411273739909173486948413518022752305313862238166593214772698793487761875251030423516993519714215306808677724104692474199215119387725741906071553437840256786220484582884693286140537492541093086953005486704542435188521724013251087887351409946184501295224744819621937322469140771245380081663560150133162692174498642474588168444167533621259824640599530052827878558481036155222733986179487577693360697390152370901746112653758338456083440878726007229307830037808681050302990411238666727608253452573696904083133866093791985565118032742893247076947480766837941319251901579605233916076425572961
e2 = 65537
c2 = 6830857661703156598973433617055045803277004274287300997634648800448233655756498070693597839856021431269237565020303935757530559600152306154376778437832503465744084633164767864997303080852153757211172394903940863225981142502888126928982009493972076013486758460894416710122811249903322437742241269681934551237431668187006176418124934488775505816544733929241927900392924886649420943699356314278255683484998359663404611236056664149725644051300950988495549164517140159041907329062655574220869612072289849679613024196448446224406889484578310512232665571188351621585528255501546941332782446448144033997067917984719103068519
d,x,y = gmpy2.gcdext(e1,e2)
print('d1=',x)
print('d2=',-y)
m1 = pow(c1,x,n1)
m2 = pow(c2,y,n2)
print('m1=',m1)
print('m2',m2)
m = (m1*m2)%n1
print(long_to_bytes(m))

BUUCTF rsa_output

import gmpy2
from Crypto.Util.number import *

n1=21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
e1=2767

n2=21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
e2=3659

c1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599

c2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
'''
共模攻击
'''
s = gmpy2.gcdext(e1,e2)
m1 = pow(c1,s[1],n1)
m2 = pow(c2,s[2],n2)
m = (m1*m2)%n1
print(long_to_bytes(m))

三、e与phi不互素

蜀道山crypto xorsa

原题

from Crypto.Util.number import *
from gmpy2 import *
import uuid
flag='LZSDS{'+str(uuid.uuid4())+'}'
 
while True:
    p=getPrime(512)
    if p.bit_length()==512:
        break
mask=??????
q=p^mask
hint1=p^q
hint2=q
n=p*q
e=2026
m=bytes_to_long(flag.encode())
c=pow(m,e,n)
print("c =",c)
print("n =",n)
print("hint1 =",hint1)
print("hint2 =",hint2)
 
'''
c = 13760578729891127041098229431259961120216468948795732373975536417751222443069805775693845560005881981622202089883866395577154701229046245882282127054969114210307175116574178428823043817041956207503299220721042136515863979655578210499512044917781566303947681251248645504273995402630701480590505840473412765662
n = 14247038211821385209759067256846232227444163173099199085257790370590450749665206556163364754269182255358084948354345827898987234756662133974633117062902370811855466665351784027125333112663075085395676501121759786699720149098576433141817737564928779420725539793335830274229206316999461309927000523188222801659
hint1 = 8938538619961731399716016665470564084986243880394928918482374295814509353382364651201249532111268951793354572124324033902502588541297713297622432670722730
hint2 = 1493298155243474837320092849325750387759519643879388609208314494000605554020636706320849032906759121914762492378489852575583260177546578935320977613050647
'''

解题

from Crypto.Util.number import *
from gmpy2 import *
import uuid
import gmpy2
flag='LZSDS{'+str(uuid.uuid4())+'}'

e=2026
c = 13760578729891127041098229431259961120216468948795732373975536417751222443069805775693845560005881981622202089883866395577154701229046245882282127054969114210307175116574178428823043817041956207503299220721042136515863979655578210499512044917781566303947681251248645504273995402630701480590505840473412765662
n = 14247038211821385209759067256846232227444163173099199085257790370590450749665206556163364754269182255358084948354345827898987234756662133974633117062902370811855466665351784027125333112663075085395676501121759786699720149098576433141817737564928779420725539793335830274229206316999461309927000523188222801659
hint1 = 8938538619961731399716016665470564084986243880394928918482374295814509353382364651201249532111268951793354572124324033902502588541297713297622432670722730
hint2 = 1493298155243474837320092849325750387759519643879388609208314494000605554020636706320849032906759121914762492378489852575583260177546578935320977613050647
# hint1 = p ^ q --->   hint1 = p ^ hint2
# hint2 = q   p ^ q ^ q = q
q = hint2
p = hint1 ^ hint2 #按位异或

n = p * q  #模数n

phi = (p - 1) * (q - 1)  #计算n的欧拉函数

k = gcd(e,phi)  #e和phi的最大公约数
print(k)

d = gmpy2.invert(e//k, phi)  #整除
m = pow(c, d, n)

flag = long_to_bytes(gmpy2.iroot(m,k)[0])   #gmpy2.iroot(m,k)[0] --->m 的k次根
print(flag)

'''
方式2：
flag = gmpy2.iroot(m,k)[0]
print(long_to_bytes(flag))
'''

运算明文m = pow(c,d,n)公式为
$$
M = C^dmodN
$$
gmpy2.iroot(m,k)[0] —>计算m的整数k次根，并返回到元组（r,is_exact)中。

四、dp、dq泄露

[1]BUUCTF RSA2

题干：

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

from Crypto.Util.number import *
import gmpy2
import libnum


e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

p = 13468634736343473907717969603434376212206335187555458742257940406618189481177835992217885676243155145465521141546915941147336786447889325606555333350540003
q = 18432009829596386103558375461387837845170621179295293289126504231317130550979989727125205467379713835047300158256398009229511746203459540859429194971855371


c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
n = p * q
phi = (p-1) * (q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

这里直接爆破n得到p,q，得到flag

flag{wow_leaking_dp_breaks_rsa?_98924743502}

[2]dq泄露

例题电协杯网络安全大赛

import string
import libnum

p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
e = 65537
n = p * q
phi_n = (p - 1) * (q - 1)
d = libnum.invmod(e, phi_n)
dp = d % (p - 1)
m = ""
# m已经被出题人删除
m = libnum.s2n(m)
n = p * q
c = pow(m, e, n)

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

# n= 30038614205597077838962156206021945065987448785762975768513393936133355431958722483020134901703000339859878814954989552721295590915406049266329363026232276341135608871315641237668039320490916011236818714749150280573511000851776770847745604291625501463171981064491803096697180543460139239872217490582916441261200021622931557415800428181536536826538542692450156170059013396816969074491652375495060144688482132746271605195131849144571012502481785313844747578789814573259457774033154400354808642561252919702886076654335154816816958357102141218546975378767958626296587517965799541151665664445860586849511650308753445217289
# e= 65537
# dp= 152048337012909482885768876872530458301144057739858720998474955248679363407397769707250829801482584840644770980607263090774768187750263484741350364190069406950759694139144618495136993686703559580612268170232189900268362520135693881443821790942559172260898483157726387106830093051321311632013036832670039105191
# c= 2009721638540203299179833882645599868122762393075349787569560589423302545675046484390916766109074377261379243471418478653033657440480228798647224116685145631925778654421031211388697437428066983048298122601793967600507237152786299059686410154432248816297187947466893453162379252285303360199156779850930421335929626931817077689707940568336348072687084429470701385603519825742959386639032474183696222456442824877174379428816045933948847760887329206619628974101306822417453491162862685427171219837714495106364698998031589212706833670612489091625272589920947128077607991471329839941611578695323341563847526313685979443694

原理：待更新

import gmpy2
from Crypto.Util.number import *

n= 30038614205597077838962156206021945065987448785762975768513393936133355431958722483020134901703000339859878814954989552721295590915406049266329363026232276341135608871315641237668039320490916011236818714749150280573511000851776770847745604291625501463171981064491803096697180543460139239872217490582916441261200021622931557415800428181536536826538542692450156170059013396816969074491652375495060144688482132746271605195131849144571012502481785313844747578789814573259457774033154400354808642561252919702886076654335154816816958357102141218546975378767958626296587517965799541151665664445860586849511650308753445217289
e= 65537
dp= 152048337012909482885768876872530458301144057739858720998474955248679363407397769707250829801482584840644770980607263090774768187750263484741350364190069406950759694139144618495136993686703559580612268170232189900268362520135693881443821790942559172260898483157726387106830093051321311632013036832670039105191
c= 2009721638540203299179833882645599868122762393075349787569560589423302545675046484390916766109074377261379243471418478653033657440480228798647224116685145631925778654421031211388697437428066983048298122601793967600507237152786299059686410154432248816297187947466893453162379252285303360199156779850930421335929626931817077689707940568336348072687084429470701385603519825742959386639032474183696222456442824877174379428816045933948847760887329206619628974101306822417453491162862685427171219837714495106364698998031589212706833670612489091625272589920947128077607991471329839941611578695323341563847526313685979443694

e = 65537
for i in range(1, e):
    if (dp * e - 1) % i == 0:
        if n % (((dp * e - 1) // i) + 1) == 0:
            p = ((dp * e - 1) // i) + 1
            q = n // (((dp * e - 1) // i) + 1)
            phi = (q - 1) * (p - 1)
            d = gmpy2.invert(e, phi)
            m = pow(c, d, n)

print(m)
print(long_to_bytes(m))

五、看不懂的

[1]BUUCTF RSA

用notebook打开pub.key得到

—–BEGIN PUBLIC KEY—–
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMAzLFxkrkcYL2wch21CM2kQVFpY9+7+
/AvKr1rzQczdAgMBAAE=
—–END PUBLIC KEY—–

公钥解析

爆破出p，q

import gmpy2
import rsa

e = 65537
n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
print('d=',d)

d= 81176168860169991027846870170527607562179635470395365333547868786951080991441

key = rsa.PrivateKey(n, e, d, q, p)  # 在pkcs标准中,pkcs#1规定,私钥包含(n,e,d,p,q)

with open("G:\\crpyto learning\\BUUCTFRSA\\flag.enc", "rb") as f:  # 以二进制读模式，读取密文
    f = f.read()
    print(rsa.decrypt(f, key))

打开加密文件：with open("G:\\crypto learning\\BUUCTFRSA\\flag.enc", "rb") as f: 这行代码是以二进制模式读取文件 flag.enc，即文件内容为密文。f.read() 读取整个文件的内容并将其存储在变量 f 中。

解密密文：rsa.decrypt(f, key) 调用 rsa.decrypt 函数使用私钥 key 对密文 f 进行解密。假设 f 是一个经过 RSA 加密的内容，rsa.decrypt 函数会使用私钥中的 d 和其他密钥参数来还原原始的明文数据。

输出解密后的内容：print(rsa.decrypt(f, key)) 会输出解密后的明文。如果 flag.enc 是一个包含标志信息的加密文件，这里会打印出文件的内容（明文标志信息）。

得到flag{decrypt_256}

六、n分解出多个数

攻防世界baigeirsa2

n = 175797137276517400024170861198192089021253920489351812147043687817076482376379806063372376015921
c = 144009221781172353636339988896910912047726260759108847257566019412382083853598735817869933202168
p = 9401433281508038261
q = 10252499084912054759
r = 11215197893925590897
s = 11855687732085186571
t = 13716847112310466417
phi = (p-1)*(q-1)*(r-1)*(s-1)*(t-1)

往下正常解rsa

HSCTF{@Tv0_br3ad5_c1ip_cHe3se_!@}