• 对于目前的RSA加密来说，只介绍一些正常的RSA加密题型，而不会详细归纳RSA加密中考察某个数论知识点的题目。（当然如果是leak类型的题目还是会归纳的，但是如果是单单考察一个求ϕ(n)\phi(n)的公式，那我觉得没什么必要）
  • 接下来就介绍一下针对RSA加密的早期攻击方式，以便后续的RSA加密的学习。接下来就先来了解一下RSA加密的早期攻击：对于RSA加密早期的攻击，本篇博客中主要学习的是共模攻击、循环攻击、共明文攻击，对于相关明文攻击个人认为篇幅比较多，所以单开一篇博客进行论文的细读，进行学习。

image-20260121010932547

共模攻击

  • 共模攻击英文全称为Common Modulus Attack，出现该攻击的原因是由于一个早期提出的密码学协议共模协议，该协议的具体内容为：

    • 由一个密钥机构（即可信第三方）生成一个RSA模数，并向系统内的用户分发使用同一模数的和法密钥对。
    • 在该协议中，用户的私钥仅为(d,N)(d,N)，因此用户并不知道模数NN的因数分解即不知道(p,q)(p,q)的值。
    • 该方案的初衷是只有中央密钥机构掌握该公共模数的分解信息。

  • 在1983年，Simmons在这篇文章A "weak" privacy protocol using the RSA crypto algorithm. 指出，当同一明文使用具有相同模数且公钥指数互素的两个不同公钥进行加密时，会存在协议失效的问题。接下来具体说明一下：

    • 给定两个密文c1,c2c_1,c_2，以及两个公钥对(e1,n)，(e2,n)(e_1,n)，(e_2,n)，其中公钥对中(e1,e2)=1(e_1,e_2)=1。Simmons证明了在这种已知条件下，可以很容易地计算出原始明文。
    • 由于(e1,e2)(e_1,e_2)互素，那么我们就可以轻易地求出整数a1a_1和a2a_2，a1e1+a2e2=1a_1e_1+a_2e_2=1（可以由裴蜀定理得到该式子）
    • 对于任意明文mm，给定的c1=me1 mod( N),c2=me2 mod( N)c_1=m^{e_1}~mod(~N),c_2=m^{e_2}~mod(~N)，只需要计算c1a1∗c2a2 mod( N)c_1^{a_1}*c_2^{a_2}~mod(~N)，即可得到明文。
    • 因为在ZNZ_N中有：c1a1∗c2a2=ma1e1∗ma2e2=ma1e1+a2e2=m mod( N)c_{1}^{a_1}*c_{2}^{a_2}=m^{a_1e_1}*m^{a_2e_2}=m^{a_1e_1+a_2e_2}=m~mod(~N)
    • 这类攻击可以由任何能够获取公钥并且观察到这两个密文的人实施

  • 在1984年，DeLaurentis在这篇文章A further weakness in the common modulus protocolfor the RSA cryptoalgorithm证明了共模协议是完全不安全的。他指出只要掌握任意一组公钥—私钥对，就足以计算出在相同模数下对应与任何其他公钥的有效私钥，具体定理如下：

    • 设(e,N)(e,N)是一个有效的RSA公钥，其私钥对应的是(d,N)(d,N)；设(e1,N)(e_1,N)是另一个有效的公钥，并且满足e1≠ee_1≠e。

    • 在已知(e,d,N,e1)(e,d,N,e_1)的情况下，公钥(e1,N)(e_1,N)对应有效的解密指数d1d_1能在关于log(N)log(N)的多项式时间内计算得到。

    • d1d_1的计算公式如下：d1=e1−1 mod( ed−1gcd(e1,ed−1))d_1=e_1^{-1}~mod(~\frac{ed-1}{gcd(e_1,ed-1)})

    • 证明如下：

      • 由于ϕ(N)\phi(N)是λ(N)\lambda(N)的倍数，所以密钥等式就可以写成ed−1=kλ(N)ed-1=k\lambda(N)，kk是一个正整数。
      • 对于有效的公钥指数e1e_1，必须满足gcd(e1,λ(N))=1gcd(e_1,\lambda(N))=1，因此就有gcd(e1,kλ(N))=gcd(e1,k)=k′gcd(e_1,k\lambda(N))=gcd(e_1,k)=k'，也就有k′∣kk'|k。
      • 设k~=kk′≥1\tilde{k}=\frac{k}{k'}≥1，所以就有ed−1gcd(e1,ed−1)=kλ(N)k′=k~λ(N)\frac{ed-1}{gcd(e_1,ed-1)}=\frac{k\lambda(N)}{k'}=\tilde{k}\lambda(N)。
      • 因此对于私钥指数d1d_1就满足e1d1=1+k1(k~λ(N))e_1d_1=1+k_1(\tilde{k}\lambda(N))，其中k1k_1是正整数。
      • 因此就有e1d1≡1 ( mod λ(N))e_1d_1\equiv1~(~mod~\lambda(N))，所以d1d_1是公钥(e1,N)(e_1,N)的一个有效私钥指数。
      • 所以可以在关于log(N)log(N)的多项式时间内计算得到d1d_1

    • 此外DeLaurentis利用一个归因与Simmons的思想证明了：在已知单个公钥-私钥对的情况下，可以使用概率多项式时间的Las Vegas算法对模数进行分解（Las Vegas算法是结果一定正确，只是运行时间是随机的随机算法）。在给定ee和dd的条件下，只需要计算ϕ(N)\phi(N)的一个倍数，即ed−1=kϕ(N)ed-1=k\phi(N)，然后应用Miller的结论（该结论就是在已知ϕ(N)\phi(N)的某个倍数时，可以以概率方式分解NN），因此共模协议不安全。

题型1 共模攻击1-e1,e2

共模攻击1-例题1

  • 题目附件如下：
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
from Crypto.Util.number import *
import gmpy2
import uuid
flag = b'flag{' + str(uuid.uuid4()).encode()+b'}'
m = bytes_to_long(flag)
e1 = getPrime(16)
e2 = getPrime(16)
p = getPrime(512)
q = getPrime(512)
n = p*q
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
print("e1 =",e1)
print("e2 =",e2)
print("n =",n)
print("c1 =",c1)
print("c2 =",c2)
print("gcd(e1,e2) =",gmpy2.gcd(e1,e2))
"""
e1 = 35603
e2 = 53849
n = 65844835114811311147300780798656143825222359960203887804404336766671754915238143105361685751338600606205234241717554977556014391502151140599030174376626752597123335946780943028787393505875282845874194789937021373169837205020116739523929406808658690735666690634468817779530981170477446002242151051007841320499
c1 = 3652946455096596922421828601712210382877573893656617028922252423601007198550547136141125408399184017530737069617361752419721283095525888153494847215557513043342658287550672860273427773994030007220020707376113461073627581510167395737557600247794396378096347654764650186631167120330986770904279007941507562441
c2 = 16647423266182678960959947505427682046836995492595463854876112200789807987236540245845356081678424736418596164492737256401436506552449871347507391421521217966841767869954716106409257585276208800895615701515817235738827206889142921421410764420295206520038281264810899421047195121134469562492729516621808418924
gcd(e1,e2) = 1
"""
  • 接下来推导一下，先介绍一下推导需要的定理：
    • 著名的裴蜀定理：若(a,b)=d(a,b)=d,则存在s,t∈Z,as+bt=ds,t∈Z,as+bt=d
    • 同余的基本运算，这里就不写出了
  • 先列出本题的已知量：
    • c1=me1  mod (n)c_1=m^{e_1}~~mod~(n)，c2=me2  mod (n)c_2=m^{e_2}~~mod~(n)，gcd(e1,e2)=1gcd(e_1,e_2)=1，(e1,n),(e2,n)(e_1,n),(e_2,n)
    • 推导如下：
      • 因为存在gcd(e1,e2)=1gcd(e_1,e_2)=1，所以由裴蜀定理得存在s,t∈Z，e1s+e2t=1s,t∈Z，e_1s+e_2t=1
      • 可以得到：c1s=(me1)s  mod (n)=me1s  mod (n)c_1^{s}=(m^{e_1})^{s}~~mod~(n)=m^{e_1s}~~mod~(n)，c2t=(me2)t  mod (n)=me2t  mod (n)c_2^{t}=(m^{e_2})^{t}~~mod~(n)=m^{e_2t}~~mod~(n)
      • 最后可以推导得到：c1sc2t=me1sme2t  mod(n)=me1s+e2t  mod(n)=mc_1^{s}c_2^{t} = m^{e_1s}m^{e_2t}~~mod(n)= m^{e_1s+e_2t}~~mod(n)=m
    • 现在就将问题转换为求s、t，这里我们可以使用拓展欧几里得算法进行计算。在Python中的gmpy2库有一个函数gcdext(a1,a2)这个函数可以用来计算s、t，接下来就介绍这个函数的使用
    • 这个函数传入的是两个参数：e1、e2，这个函数内部实现的就是拓展欧几里得算法，这个算法的具体过程不多介绍
    • 这个函数返回值有三个：第一个返回值返回的是gcd(e1,e2)的值，第二个返回值返回的是s，第三个返回值返回的是t
1
2
3
4
5
import gmpy2
e1 = 43019
e2 = 54011
gmpy2.gcdext(e1,e2)
mpz(1), mpz(23050), mpz(-18359)
  • 所以本题的exp如下：
1
2
3
4
5
6
7
8
9
10
11
import libnum
import gmpy2
e1 = 35603
e2 = 53849
n = 65844835114811311147300780798656143825222359960203887804404336766671754915238143105361685751338600606205234241717554977556014391502151140599030174376626752597123335946780943028787393505875282845874194789937021373169837205020116739523929406808658690735666690634468817779530981170477446002242151051007841320499
c1 = 3652946455096596922421828601712210382877573893656617028922252423601007198550547136141125408399184017530737069617361752419721283095525888153494847215557513043342658287550672860273427773994030007220020707376113461073627581510167395737557600247794396378096347654764650186631167120330986770904279007941507562441
c2 = 16647423266182678960959947505427682046836995492595463854876112200789807987236540245845356081678424736418596164492737256401436506552449871347507391421521217966841767869954716106409257585276208800895615701515817235738827206889142921421410764420295206520038281264810899421047195121134469562492729516621808418924
_, s1, s2 = gmpy2.gcdext(e1,e2)
m = (pow(c1,s1,n)*pow(c2,s2,n))%n
print(libnum.n2s(int(m)))
# flag{12025e72-7f21-4cf1-b779-7d343e6c28e8}

共模攻击1-例题2

  • 题目附件如下：
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
from Crypto.Util.number import *
import gmpy2
import random
import uuid
flag = b'flag{' + str(uuid.uuid4()).encode()+b'}'
m = bytes_to_long(flag)
e1 = random.randint(2**9,2**10)
e2 = random.randint(2**9,2**10)
p = getPrime(2048)
q = getPrime(2048)
n = p*q
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
print("e1 =",e1)
print("e2 =",e2)
print("n =",n)
print("c1 =",c1)
print("c2 =",c2)
print("gcd(e1,e2) =",gmpy2.gcd(e1,e2))
"""
e1 = 620
e2 = 852
n = 488299974280423468494491626502681510610622659676141469092313160639335198605509520549543910200860692389482956804442328919460210907938788226737631175309269170231353511539442511424239677675149154457627848373105899173402934535598095770004433870876157591481297053960142849187408256787914412843465792603656398426013081792330465154956892414604271973196644568417323222139043401871093745522455188827823044351104882983674468767765961775652024641310717860122884618152301539493228747913896937962785784957986419998916692245635401195820992423078160726261717908408189428396339427882648702774054419338096378028965388611007017876360158498562008559695287857235179316227579175353902917899829421618762143523437857428839150119571518691898416800958688263677380894566152337630920863812465019986053142112885615184964434198042379709422202804833291339537609443480826182595407581926714160370588411136585162069348998755083916752583742266010449549495271013630650415054683729365253317245949418543450761600084286473579505710272197521290005718605536244324311874746509743166352224068944318138638055571192352548251874129295277575292735181477678218297295453519564513089291601095167751488505181686317543648478821489265394401629441721194595397763561134807248621390722843
c1 = 455859530700302196090940205765775115175363478145257129307983594140510107024045380156072179160489755831590028651905457987088748018536274660599932305137405160984117009869263808841260297027304543512845866312722914773489150272216207489060876904038193675914965643774544691868203081823078795428004261665509434152591324782305090200350510428199643900001311813031016645003100136345874510070647372036381845865679770695023185114415696625593974754981468556258670357532589012014375068858408147782130899885021117527747786575955253131253571641726280287562314889560748603938679367430249850608779280468651258201338161917604528304880319104162119424882696127565963591727463304280012236237363326425615325905715818404553114773582740829906535796365751291240889176647711167385111272081354586514847390729794349805844389084279525782070775920922645483384413350620436954995967864606023606924526637171024346957127097175802894508022645712868591034283531532389207560019603340677987951116649700085014515023992870540930574813329948735264272175802064003808610560684476013761149356380745945736889540788175482281830186868296676940900682105551463011163424493615062687006829566538524822912369277715906335340724655512076421588615732220595970905341881665092823336035046637
c2 = 449676732943777585638465632047671348316180209644557835117039289543643904788974364916336061971711707678174956137025056540469815796501588167706394457243211048758626422203771299943562210878287290612939545311264168557089451974544981438766420076475143698158920331882783433455648106881644966809905923260554087033402048646196871011269720619876202809124069648277977357024726510496161742458126360998740714426774306483156720410587772486855664510522835335994299528918151418339349531911774213874616535746703962779798005518742303586806488864482415042832868075445851930700174294286095693946421892274717395984567314458694724179268625941288578303339082816236986079403667887450560106731711918966588378942671460910248928231897514772093854082176050069718068332722116150583816065298947573598883941196976856454089010265800485254503561397147592223557040559114335354897495880876248437620907524260369485513430444785552126079385937017870888611821252850338771412587774293803426304654866779775618781384120502214584843529655663279438141415343700660714110798446342140394882789559506987022589570906951263551587051261428101604460732780664071269217563755426673321062841732008010986189433708664416314356149549291717154381508919608875476115629883341062772663877830388
gcd(e1,e2) = 4
"""
  • 例题2对于例题1来说不同的点就在于gcd(e1,e2)=4≠1gcd(e_1,e_2)=4≠1，这就导致了使用共模攻击得到的结果并不是mm，而是m4m^4。但是对于本题来说，nn是比较大的这就使得m4<nm^4 < n，可以直接开方得到mm。（直接开方算是小公钥指数的最简单的一个攻击方式）
  • 推到过程如下：
    • 已知：c1=me1  mod (n)c_1=m^{e_1}~~mod~(n)，c2=me2  mod (n)c_2=m^{e_2}~~mod~(n)，gcd(e1,e2)=4gcd(e_1,e_2)=4，e1,e2e_1,e_2
    • 因为有gcd(e1,e2)=4gcd(e_1,e_2)=4，所以由裴蜀定理得s,t∈Z.e1s+e2t=4s,t∈Z.e_1s+e_2t=4
    • 可以得到：c1s=(me1)s  mod (n)=me1s  mod (n)c_1^{s}=(m^{e_1})^{s}~~mod~(n)=m^{e_1s}~~mod~(n)，c2t=(me2)t  mod (n)=me2t  mod (n)c_2^{t}=(m^{e_2})^{t}~~mod~(n)=m^{e_2t}~~mod~(n)
    • c1sc2t=me1sme2t=me1s+e2t=m4 mod( n)c_1^{s}c_2^{t} = m^{e_1s}m^{e_2t}=m^{e_1s+e_2t}=m^{4}~mod(~n)
  • exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
import gmpy2
e1 = 620
e2 = 852
n = 
c1 = 
c2 = 

_ , s, t = gmpy2.gcdext(e1,e2)
print(_)
print(s)
print(t)
C = (pow(c1,s,n) * pow(c2,t,n)) % n
m = gmpy2.iroot(C,4)[0]
flag = long_to_bytes(int(m))
print(flag)
"""
b'flag{d13c541a-e36d-486f-9e2e-eae4f5b4f064}'
"""

共模攻击1-例题3

  • 题目附件如下：
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
from Crypto.Util.number import *
import gmpy2
import random
import uuid
flag = b'flag{' + str(uuid.uuid4()).encode()+b'}'
m = bytes_to_long(flag)
k1 = random.randint(2**128,2**256)
k2 = random.randint(2**128,2**256)
e1 = getPrime(128)*k1
e2 = getPrime(128)*k1*k2
e3 = getPrime(128)*k2
p = getPrime(1024)
q = getPrime(1024)
n = p*q
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
c3 = pow(m,e3,n)
print("e1 =",e1)
print("e2 =",e2)
print("e3 =",e3)
print("n =",n)
print("c1 =",c1)
print("c2 =",c2)
print("c3 =",c3)
print("gcd(e1,e2) =",gmpy2.gcd(e1,e2))
print("gcd(e2,e3) = ",gmpy2.gcd(e2,e3))
"""
e1 = 6839979093843017245130935971073531650625865408597324093158075653007572029459535748591107780971041110617821327885728
e2 = 527282383778630558435877705949699484729936503257091129495571879289998217841325217564810314237039659729265596452756258253436101100968118657130954223308875205257774585781949600635959096231751360
e3 = 20987998930730242130690830835028138615595244455228017878066112490327400892650229366898248406466316235857196958485710
n = 22175144708990630853036480868376123403731448276285717131186187150462023495494103565746117568235683365313517827941106620902013918484064641114476913481110938950785308733160550905735102713320438455824065792338146147847335388226116646541800245464845211085540907602598972170387771602880693683773805550988596358558621125283407314509610950378661338714027095643635739361829648482049383174885258194773716516785232715071895492339469667922183918303613284066664177945669438336799055529602328784963091965710713100236033780379337460945498971432359098326842627948461349746702776166953869600658895170340420434234372122272110975044659
c1 = 11426478179683336827224880779953157546776076551240828268809350458296893628522712784864907995111968644902442693072364448063747658422225255036189101385357784689296259496649527761401899948136054211133883265341970543967599869525260654979500412480663418057379308458996911392485335767582507518973447401423943878293895212638047157663802239344638641314156758830964491691323026524366328874683360987516802872498983112781643154651435374108641997212467699796213730738052002284134749351805453079045833498972827333585113428885026516509660161906337450878179654072288419436265826131479983858828205102056301019221745568319757344882310
c2 = 924553363795544361249557963373014280364009962681904215742379062140845462422058966956557303658832168491456051793505960008265313560082631349096509445336008684455437098964906094258030833746463869703797105150834953261601859026067804458980569864595116130499800793859913206222086000196754618550748639846744131641000960761007475985837366717289369284418559314663298108941564271462247365885229310605727917343982395106384199224643917254074484080305027204503813125672333323007771938062630610901748714884555438154614828690121207720526744717299121320271203097954739219600201683737833195114592138439396587112769674492174781048345
c3 = 14746267922953594508934987983405936746727004380259552828471117039223733948341026916910718225093159503573963075699179842175533457878937869802023486477372942785557938018982551170721496415115172951210353253311347031831419025904122683204153082041761968643487702640595950727384113933573702782931552657234931764298271273287655619903274377134978785223623709621560907111004144880046847332195005770181319177034333945769165118402546185793312611428185399654124299299022380187589974664553807713456469247091344949181479956722950070165387894955829314074403945814066771174510119236751891447097319232129235383321537697205679053840336
gcd(e1,e2) = 29540346448235016595457107953809410509141879299370840061983373145010008818272
gcd(e2,e3) =  68493250011952459219512675036017846580344175598507893778164361048080116129970
"""

  • 从题目附件中会看到，gcd(e1,e2),gcd(e2,e3)gcd(e_1,e_2),gcd(e_2,e_3)这两个值是比较大的，这就使得例题2的直接开根这一方法失效，但是第一步还是需要使用上共模攻击。所以进行共模攻击：

  • 设gcd(e1,e2)=x,gcd(e2,e3)=ygcd(e_1,e_2)=x,gcd(e_2,e_3)=y

  • 通过裴蜀定理就可以得到：s11e1+s12e2=xs_{11}e_1+s_{12}e_2=x，s21e2+s22e3=ys_{21}e_2+s_{22}e_3=y

  • 通过第一次共模攻击，就可以得到：c1s11c2s12=ms11e1+s12e2=mx mod (n)c_1^{s_{11}}c_2^{s_{12}}=m^{s_{11}e_1+s_{12}e_2}=m^{x}~mod~(n)

  • 通过第二次共模共计，就可以得到：c2s21c3s22=ms21e2+s22e3=my mod( n)c_2^{s_{21}}c_3^{s_{22}}=m^{s_{21}e_2+s_{22}e_3}=m^{y}~mod(~n)

  • 通过运用两次共模攻击，其实我们就会构造出新的两个RSA加密，其中公钥对是(x,n),(y,n)(x,n),(y,n)，不难发现构造出的两个RSA加密其实也是共模的，所以我们还可以再进行一次共模攻击。

    • 如果gcd(x,y)=1gcd(x,y)=1，这刚好就符合共模攻击的要求，所以我们再使用一次共模攻击即可得到明文。如果gcd(x,y)=zgcd(x,y)=z其中zz是一个比较小的数，那么可能可以使用直接开方的方法计算得到。
    • 通过第三次共模攻击，就可以得到：mxs31+ys32=mz mod( n)m^{xs_{31}+ys_{32}}=m^{z}~mod(~n)
    • 即可得到开方得到。

  • exp如下：

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
from Crypto.Util.number import *
import gmpy2
import libnum
e1 = 
e2 = 
e3 = 
n = 
c1 = 
c2 = 
c3 = 
x =  
y =  

# 计算得到gcd(x,y)=6
z = gmpy2.gcd(x,y)
print(z)

# 使用拓展欧几里得算法计算
_,s1,s2 = gmpy2.gcdext(e1,e2)
_,s3,s4 = gmpy2.gcdext(e2,e3)

# 第一次使用共模攻击
C1 = (pow(c1,s1,n)*pow(c2,s2,n)) % n
# 第二次使用共模攻击
C2 = (pow(c2,s3,n)*pow(c3,s4,n)) % n
# 继续使用拓展欧几里得算法计算
_,s5,s6 = gmpy2.gcdext(x,y)
# 第三次使用共模攻击
C = pow(C1,s5,n)*pow(C2,s6,n) % n
m = gmpy2.iroot(C,6)[0]
flag = libnum.n2s(int(m))
print(flag)
"""
6
b'flag{a1c50828-6199-48c1-8297-a9c44a823ed0}'
"""

题型2 共模攻击2-泄露d1

共模攻击2-例题1

  • 题目来源uoftctf2026，题目附件如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
from Crypto.Util.number import *
flag = b'flag{test_flag}'
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e1 = 65537
d1 = gmpy2.invert(e1,(p-1)*(q-1))
e2 = 6767671
print("n=",n)
print("e1=",e1)
print("d1=",d1)
print("e2=",e2)
print("c2=",pow(m,e2,n))

"""
n=144193923737869044259998596038292537217126517072587407189785154961344425600188709243733103713567903690926695626210849582322575275021963176688615503362430255878068025864333805901831356111202249176714839010151878345993886718863579928588098080351940561045688931786378656665718140998014299097023143181095121810219
e1=65537
d1=12574092103116126584156918631595005114605155027996964036950457918490065036621732354668884564796078087090438462300608898225025828108557296714458055780952572974382089675780912070693778415852291145766476219909978391880801604060224785419022793121117332853938170749724540897211958251465747669952580590146500249193
e2=6767671
c2=31703515320997441500407462163885912085193988887521686491271883832485018463764003313655377418478488372329742364292629844576532415828605994734718987367062694340608380583593689052813716395874850039382743513756381017287371000882358341440383454299152364807346068866304481227367259672607408256375720022838698292966
"""

  • 这这题本质上就是上面所说的，共模攻击知道一个私钥，可以求解另一个的私钥。接下来推导一下：

    • 已知：(n,e1,d1)(n,e_1,d_1)，(n,e2,c2)(n,e_2,c_2)，求解d2d_2。
    • 首先有e1d1−1=kλ(n)e_1d_1-1=k\lambda(n)，并且公钥e2e_2必须满足gcd(e2,λ(n))=1gcd(e_2,\lambda(n))=1
    • 对于公钥e2e_2就可以有gcd(e2,kλ(n))=k′gcd(e_2,k\lambda(n))=k'，并且k′∣kk'|k
    • 所以有ed−1gcd(e2,kλ(n))=kλ(n)k′=k~λ(N)\frac{ed-1}{gcd(e_2,k\lambda(n))}=\frac{k\lambda(n)}{k'}=\tilde{k}\lambda(N)
    • 那么对于公钥e2e_2来说有，e2d2=1+k∗(k~λ(N))e_2d_2=1+k*(\tilde{k}\lambda(N))
    • 取模k~λ(N)\tilde{k}\lambda(N)就满足e2d2≡1 mod( k~λ(N))⇒e2d2≡1 mod( ed−1gcd(e2,kλ(n)))e_2d_2\equiv1~mod(~\tilde{k}\lambda(N))\Rightarrow e_2d_2\equiv1~mod(~\frac{ed-1}{gcd(e_2,k\lambda(n))})

  • exp如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n=
e1=65537
d1=
e2=6767671
c=

x = e1*d1-1
y = gmpy2.gcd(e2,e1*d1-1)
print(x,y)
d2 = gmpy2.invert(e2,x)
m = pow(c,d2,n)
flag = long_to_bytes(m)
print(flag)
# b'uoftctf{1_5h0u1dv3_ju57_ch4ng3d_th3_wh013_th1ng_1n5734d}'

题型3 共模攻击3-公钥指数

  • 该类型的共模攻击基本思路就是共模攻击1的思路，只不过题目没有直接给出共模攻击中的e1,e2。
  • 可能还有些是用共模攻击2的方法破解，但是私钥d不直接给我们，而是变着法子让我们求解。

共模攻击3-例题1

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 gmpy2 import *
from Crypto.Util.number import *

flag  = '****************************'
flag = {"asfajgfbiagbwe"}
p = getPrime(2048)
q = getPrime(2048)
m1 = bytes_to_long(bytes(flag.encode()))

e1e2 = 3087
n = p*q
print()

flag1 = pow(m1,e1,n)
flag2 = pow(m1,e2,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))


#flag1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
#flag2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
#n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437

  • 对于这题来说，我们只知道公钥e1、e2e_1、e_2之间的关系e1e2=3087e_1e_2=3087，并不知道e1、e2e_1、e_2的具体的值，那么第一步我们就先要求e1,e2e_1,e_2，如何进行求解。
  • 我们不妨将e1e2e_1e_2进行分解，如果结果是两个素数相乘，那么就可以确定e1,e2e_1,e_2，但是这题分解后很显然不是两个素数相乘，还有带平方和立方。

image-20260127201615650

  • 接下来我们的思路其实就是变量这些因数，看看11个因数的组合是不是其中一个公钥ee，如果不是那就2个，再不是那就3个，以此类推。但是这样写排列组合还是比较麻烦了，所以我们就直接暴力遍历0~3087，当在这之间的一个数能整除30873087，再进行共模计算，如果得到的明文包含flag那就解出来了（但是此时还是属于尝试阶段，我们并不知道e1,e2e_1,e_2是否互素。）具体实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
import gmpy2
flag1= 
flag2= 
n= 
fact = 3087
for i in range(1,3087):
    if fact % i == 0:
        e1 = i
        e2 = fact//i
        _ , s, t = gmpy2.gcdext(e1,e2)
        #print(_)
        #print(s)
        #print(t)
        m = (pow(flag1,s,n) * pow(flag2,t,n)) % n
        flag = long_to_bytes(int(m))
        if b'CTF' in flag:
            print(flag)

但是运行发现没有出现结果

image-20260127202520005

  • 那就需要考虑到e1,e2e_1,e_2不互素的情况了，那就考虑需要开方的情况，并且综合考虑不互素的情况gcd(e1,e2)gcd(e_1,e_2)的结果只有三种可能，分别为3、7、213、7、21，其余的不满足条件（这里通过列举所以可能就能得出结论）
  • 最终exp如下：
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
from Crypto.Util.number import *
import gmpy2
flag1= 
flag2= 
n= 
fact = 3087
for i in range(1,3087):
    if fact % i == 0:
        e1 = i
        e2 = fact//i
        _ , s, t = gmpy2.gcdext(e1,e2)
        #print(_)
        #print(s)
        #print(t)
        m = (pow(flag1,s,n) * pow(flag2,t,n)) % n
        flag = long_to_bytes(int(m))
        if b'CTF' in flag:
            print(flag)
        m1 = gmpy2.iroot(m, 3)[0]
        m2 = gmpy2.iroot(m, 7)[0]
        m3 = gmpy2.iroot(m, 21)[0]
        flag11 = long_to_bytes(int(m1))
        flag22 = long_to_bytes(int(m2))
        flag33 = long_to_bytes(int(m3))

        if b'CTF' in flag11:
            print('flag1=',flag11)
        if b'CTF' in flag22:
            print('flag2=',flag22)
        if b'CTF' in flag33:
            print('flag3=',flag33)

#flag2= b'NSSCTF{d64dba66-b608-4255-b888-0b0f25c2f90e}'

共模攻击3-例题2

1
2
3
4
e1*e2= 59653
n= 16282992590526808657350657123769110323293742472515808696156540766049532922340638986423163288656942484229334024198335416611687418341772216996129634991032127943095069143600315325916614910606100091970611448259491799589221889445348698100959509165262891180065554743420149168801638644589921791426690475846945077068114953844817073866258377206796158690941199907230130273657375727245023893672164113928189304228859412794067127721813637080447782673535996272223836127807775157150041664783263093604946744032762535394974814371771505843653571711445892969781888188805943142126747365056482511805191315474848971218180999336497135314654469910566730389765499603897685968204361422568601724914800686608628299192714352963744010136960423806304763245890692476493455775025753944860040020178234660999290356849442926396627701588938894161779071628447041006556793933320976506046066961014953196791133933438500843139378274786265308568167479880984705152809744111382599071097574636570516674122980589207824718402382459624138317432883921371298272851693734695823787102433937406420318428888224246291987404818042038201886113203158444083427668636941
c1= 15508846802476602732219982269293312372397631462289816533805702700260237855119470146237752798828431803179124957728439730580289236458563016332461725094295883030444173189424666004498359269921250956676320570006883951982237098373954348825003467019876101438948387668628518937831820206221522881150831840296199498447304138839838135264071071817072965792514115711621435317078108239744829134467948386247696344881838815422262901903767893118533887779588425725845820071451782420200868341564360095012698956683395031351656817392008005928265838760875070634021907630535014959579709368637536268853337028760833769278841040734409299575870823873616769863828516877971432999417800417684146077045836940988096634144368727546539602310924702126212020003620219218637652874119299016382481718659448722433296761241365473608283436835986184098161365747699791248301452334044327014782249692551362625130537300221641910570569803981153117200694806974917501061411963827755822672178568783269357196133308719688843211664095412087717861154226475203597889635926903753481174280305996204091501578865951177135086807765873529089048911740160698421289371229606
c2= 7038544062804420883340530319534054090343999593726615071597649914714397773106261660516938820194721330117082799104642674913839235601210294807255855747823709326405317366422536981850436536877639492293904186333547681934006229055311359852552059601531864585759120757265084674695094298158389804437120173997679271166467086009884419942249925895393890707373985126949313101489352481737754459985522998334847972008827503987883850638250024631354158979424169551575287515128697843093987592614974905262077415255065744686115142126350167970451060399517705823298929164793769442986603707135790651560436497661713972277808036463771768932747376668116480068277125579165831615220097562066809632099809702980365194257899499384219864311379004681733844738981954144617140038448109869114888325128710654235506628539192955240723379334422880368605005772426413018696218105733457019400100498450734710865067764542737004071080719589912326985050985424145053072697267879019954400205613591419766583673115931337146967400159040252514654983240188915104134405655336152730443436887872604467679522955837013574944135975481174502094839012368918547420588186051
  • 这题大致思路与共模攻击3的例题2一致，分解e1e2e_1e_2会发现gcd(e1,e2)gcd(e_1,e_2)只有1、11两种可能，其中如果是1的话，那就直接板子了。那么可以直接确定公因数是11，为什么这题比较反套路呢。因为经过共模攻击后得到如下式子：

c1s1e1∗c2s2e2≡m11≡x mod( n)c_1^{s_1e_1}*c_2^{s_2e_2}\equiv m^{11}\equiv x~mod(~n)

  • 这题存在一个情况是m11>nm^{11}>n，这就导致直接开方得不到想要的结果，需要爆破一下m11=x+k∗nm^{11}=x+k*n这个kk，先求出正确的mm再开方就能得到flag了

  • exp如下：

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
from Crypto.Util.number import *
import tqdm
import gmpy2
fact= 59653
n= 
c1= 
c2= 


for i in tqdm.tqdm(range(1,59653),leave=True):
    if fact % i == 0:
        e1 = i
        e2 = fact//i
        x , s, t = gmpy2.gcdext(e1,e2)
        #print(_)
        #print(s)
        #print(t)
        m = (pow(c1,s,n) * pow(c2,t,n)) % n
        #print(x)
        for i in range(10000):
            m1 = m + i*n
            m2 = gmpy2.iroot(m1,x)[0]
            m3 = int(m2)

            flag = long_to_bytes(int(m3))
            if b'flag' in flag:
                print(flag)

题型4 共模攻击4-格*

  • 对于共模攻击来说，最关键的就是求一个二元不定方程的解，而这个解是线性的，所以大概率可以和格扯上关系。

共模攻击4-例题1

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
from Crypto.Util.number import *

flag = b'NSSCTF{******************************}'

a = getPrime(512)
seed = getPrime(512)
b = bytes_to_long(flag)
n = getPrime(1024)

e1 = 2333
e2 = 23333
c1 = pow(a,e1,n)
c2 = pow(a,e2,n)

output = []
for i in range(10):
    seed = (a*seed+b)%n
    output.append(seed)

print("c1 = ",c1)
print("c2 = ",c2)
print("output1 = ",output[0])
print("output2 = ",output[1])


e = [getPrime(128) for _ in range(20)]
out = []
m = getPrime(64)

for i in e:
    out.append(pow(m,i,n))

print("e=",e)
print("out=",out)

"""
c1 =  132894829064255831243210470637067717685821770359549730768366345840525257033166172926149293454192143005551270166547902269036843756318967855047301751521125394803373953151753927497701242767032542708689455184991906629946511295108898559666019232955132938245031352553261823905498810285940911315433144300083027795647
c2 =  24086830909813702968855830967174364278115647345064163689290457852025690324300607354444884288995399344650789235347773145941872226843099538451759854505842021844881825309790171852845467221751852440178862638893185965125776165397575087879479327323737686652198357863042305078811580074617322063509435591981140533310
output1 =  54997286032365904331111467760366122947903752273328087460831713533712307510311367648330090376100815622160705007873798883153287827481112070182047111994066594911019010222064952859306742931009422376955635523160546531204043294436812066746785938062292942759004837173423765427628610568097898331237064396308950601636
output2 =  115015764780168428067411132384122324817310808727138440691727747976276050930701648349452842302609389394467134068064132550313721128807222231505312226682756817617177620169804112319332815872107656884931985435898097063491690413460967856530075292289784649593915313885813931026280791070577034075346669028068003251024
e= [297332330847212015073434001239859795661, 247136911662054641479463124065475615181, 269964458627145370722389742095701827701, 270745917671094194052444327351021588037, 254010082507930275771798119457499420531, 219178601856077385518322602059961601013, 226562702503988968288128483964146379529, 236756812424464516919183114495913408541, 330800121752029915693039296018980956519, 244800084005240595691424199440981715431, 171753849214889522920105847094773384191, 175843874533972361422410968920873382741, 326554577162848075059517044795930784993, 181842368629269753698222635712342485771, 221634122983362091660188171985742369561, 314244561819808202322467576330355199409, 286703236198397527318161582654787197007, 298101543059628501506668748374542117409, 304158884506393754601331945634109778837, 227577031261920314010408499530794497453]
out= [100163998802948218573427220530909801629443946118807841130458771881611961921044413091457977957530737347507311468578174294420439883266450142918647561103714976340598499984679873518770686239019753272419975426555435266764099822607336645955391865380657632176223122712125661464370522088500110746571354290680063421912, 123528268396018633078964378145622645321836134964966941909300627704018826667414656614011250938241127521627117348901416042868382174504514240509791471909819407751786633761392047187057200130450960708049681366686147337178110669163142189940397343388837018627392202704211693014162963133958078984558400205296509955066, 50364974727218716170137342348825758682286710377257708196467656986986475658591351848251278364177715325447140300281348027787487944839878770556527568407280736570303345044999352851718908253510696083227344179177110348363623815158409862985684687329665113210373028159714648637297476014803935686233984711925346269925, 9159042298258514259206302054907530984498816597282237786310355131965025367180505822032135021520906576471052417629425493533222088036674196397387325202128095476044308794426593565419139845832998557280786358482011226957053125314152322427131984411160984485669030286331376124575677908877399942011661647598763754231, 83466948172962290899792524342204996697711370224947233607865306692546824512672969402433314856742908546253967225963904395036102408684746619744412073888614033881366518452878344698289278946024167788789718690655953517892282374396760436658422838909903123439370164929347147855359470889455753772857233516742991766128, 72028057477369331020972407277180913909557985390590548305094935208898254733240351763155769013959589016793318772858662702447133499307826143247356049051993727167694036585280387890126287679890730586145740176250715386149857291210207281073772478229355625725300592003798974298248102432508449566953296818450441875311, 63397152736399466888877444377156185012692670493456346196278062009641363047685720620967313379507212944658351683022480839941265221126018392433078546696140135677499181555082643172378488800458657825640013090182171355299282023794908520172571785687147143015581400891531296496177973817400317905868361800342940667657, 45427004823510815929685208038284324980662968275105063862891077759131069014314933978878667052450145039482242546093735499108826130367476890384431317243013990394189191560941678120985717370542332803012619694821129395559214706968432476548145608291516176910849698455496733056096163035964057523545705356926187216133, 85046100612081858546755294340770681541320509587396377967875404950325314121709046137842413744740490231945105758075761946555179595664901813127463402854440384657046429776033129391138370272524736543471909307910018577738207910417672603889922445435939876023878220177983424547612635006926243055642166274730894301704, 5833380233103086014860892228744764647016585478949686583145531659689295506666493518453642500086277427538189091865461553097914845680665917702500908205558454036911757659426809969367680394533585635383007758339917554453268182491874683638880986360065633842854622244953985055815937671635222264056071882344388307409, 83587615309194701727032548415548847571046191382552371312058083137102227325098839286526833147951063338204327145093831238962818333112251936853329663907079943414231588222256242520221314528944937229985997926851198158564313703719031124442094987245466116488897263358510493905440842917634723859176839440753120904481, 108651960334634726889543063749359050688114025706494125848785084643330096858725917513596985853593252388835207675036982640195609499739937405655156895161071906340785173459426867946058638393154997931747445494284445204735492709747637173698383609764016673932827648159152658645291248613736662020472251048171789274368, 118612010487916657134965416492319303083994743753602531817008130269546146141506819718265549648441671373744766173780682168587021797626910931105508317440664521595783406848956221465897709761805869130021172013000282497881581247777388315282629463546261696169893882772397797722134711444928443061384985458691749569847, 106808406616890955924408992591724627593882118490933791849624747503316110669154243209826761617940864170830792705070618439466645580274835929100331418955890808763286193770831205511071440703609240364726061677822134370309018443508205980554831705850988319397384130044484586798585896460152167042282847992593429629533, 88091869606421350393441194783722851111189272445506506936925797213395319937783082680078622732926273935980894566775394134783157488360516905477700601820480975112122167589887641130656305741351643175495552454293030309247254533571254198691204714097846510872592569447050033289483493274672346210063885124570695832880, 94400859500860667431780782962782396345261822402898708716634581228428633704975879685572548692997007974004673676539496590659276952154740096463133011458100387006276325192223993452314873089466451613079029429327880672384210802191677586975844471189127835578979108767548290181668434770385199468588493042256788539610, 76177813724283720012398394789596589415486093955132688784865364048503447246391866424200071522136707581280434193680972230914105236504028522288780213089260160776489804587209115330412067560802680789338779056583047491942817016437672075192528508677997165703606520158178725128251694801612417667440677124932361973397, 17188209523466762369281362386525396145127294763502094183797065621821932913685690176344514910405677170931795652509426794846131051983826422536084073462084935517166603832542862106287058675490933197600813710203114108790043880150305327523679949543592622443904084453387396870899883324751789625806819506542619123964, 120007173989070249117019147454557020213723707722383599019972471016186584968096445904023372671513462965078400715365736756710078805039115601609874780421117795585342458478316236202328120583456334489780231976628584606042971207759763658961365139429661536955996519512283283500790612975034779837647053750631763512799, 18797057418663411295612229938999282286746920748194349166509084258061650142260043277698907538088835210620841171754186980908772147495732980563542600139935202965632319542217264685208215907551992891370166006725534397313373079841419662622936316343820775075897977228084528246337988431658221881343556854053475137330]
"""

广播攻击

  • 另一个出现协议失效的情况就是几个相关的明文消息被小公钥指数和不同的模数加密。同样的，对这个失效的协议攻击经常指的是Håstad's Broadcast attack，也就是Håstad广播攻击。该攻击分为两类，一类就是共明文攻击，另一类就是消息相关攻击。
  • 这里主要介绍共明文攻击，该协议失效是出现在相同的明文mm被几个公钥(e,Ni)(e,N_i)加密，每个公钥都有相同的公钥指数ee和不同的模数NiN_i。这个协议失效的攻击在1985年由Håstad发表的两篇文章On using RSA with low exponent in a public key network和Solving simultaneous modular equations of low degree
  • 该攻击的具体定理如下：
    • 设(e,N1),...,(e,Nl),l≥e(e,N_1),...,(e,N_l),l≥e，这些公钥对都是有效的RSA公钥，其中模数Ni,i=1,...,lN_i,i=1,...,l两两互素
    • 设N0=min{N1,...,Nl}N_0=min\{N_1,...,N_l\}，N=Πi=1lNiN=\Pi^{l}_{i=1}N_i
    • 对于任何一个消息m<N0m<N_0，给定ci=me mod ( Ni)c_i=m^e~mod~(~N_i)和(e,Ni),i=1,...,l(e,N_i),i=1,...,l，明文mm是能在关于log(N)log(N)的多项式时间内计算出来的。
    • 证明如下：
      • 由于模数N1,...,NlN_1,...,N_l两两互素，由中国剩余定理可以用cic_i和NiN_i得到C≡me mod( N)C\equiv m^e~mod(~N)。
      • 因为m<N0m<N_0，这就使得me<N1N2...Nl=Nm^e<N_1N_2...N_l=N，因此C=meC=m^e。
      • 在整数范围内计算C=meC=m^e的e次方根，即可得到明文mm，由于所有计算都可以在关于log(N)log(N)的多项式时间内完成，因此结论成立。

题型1 中国剩余定理

CRT 例题1

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
import libnum
import gmpy2
import random
import uuid

flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)

p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
n1 = p * q
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
n2 = p * q
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
n3 = p * q
e = 13
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)
c3 = pow(m, e, n3)
print("e=", e)
print("n1=", n1)
print("n2=", n2)
print("n3=", n3)

print("c1=", c1)
print("c2=", c2)
print("c3=", c3)
"""
e = 13
n1 = 16655230929893303490818415854457831426545038662809855283873228642358207995734291242944120042612699642460820594813654718158395826755230956722936107927889550129166619245152453353908373751380196656611349200623414836128383308653618062999595622747482867683840133843768870236300348203389275090871132570173650238774275209757683812077533989960172822335488251744796657926473009279723460304257252876756936524918018903158795894385111046938638194925881670388700872760201130485273663156422785999102754192840209476417602399017445296045070405343876349687582470436774316410697773759057621576657298096301937899052773787116133124199739
n2 = 17197151926745749646602149115445210421300330711044282276861045275221683290586877554048509794473112203880585601275129330843554946888863132721219683639579200702355880529569042889789589005950061966309684759066705732225014741164779016525568884409690021988879475589545329149547046975086877521757237117008484775731784935960191717287332176327498377273179740487245459081737196777751408106728622513560888261855065717079007065635401835089216224111969668029246916986663313301660909538148574652809266532053889578734157117390082522831069594417637550812101652367765364077901612478983024721669687150628356918237152414368862535409859
n3 = 18719461901666732419189610536735130974364055134601694187780706398369536769336080321122034942831217438281120989017698755904233940669427542442488330152862658754609065361849067002424120904308655036927580582916373684567047102601602588472175947665724244201887952599804681827419266055359412641159981152796138695901074514583606207162167385730873921563442166111892785482387108299191119048884993267729877797586421940344366636285656854837470348603688925980178978612114344024951042846249621559376348599687263736342957456838732355009637030035658212442442824658869094581324944034490700706979663405137522294780606800571433058912041

c1 = 3530761236149189046680124371485374220252032991305088864647979778627799354583229731576585900490173357726425570018182390597284149666834264690795437972634538596441103368165128688664787322126097802985602065455316693754513332761284857157982201975554297034291092099307950246864758375115838291339394148547902128382917596947095456178572561422004708150053706114994560773293625641699691472764190426577272488084620105693964419578988589192873196530900413833531923536786853211065167782657153004342018675666293830194703777994380600060782651326623229047839109994778831432598543154184891096335217588164509636922274833553782288823349
c2 = 7557835478962501903223351987016911891266554255050134264644805724502475848487138948948076311894495847429608136390014902405718084026208891531815323418707377349405409096779206918831458396991602033494429461919844309109113047361743133772636443322195238900874786548606687215969337920658068807801603115402783849082788527952834594443136756890747461628705174983562847145588532659589787532039981477468881131005056101092222499397893730056830156407331988257383965698358904379729558105489119604343081747549319382873235286788453435066434264212954607441597606413293491628299838317713381567250093086011058119721189087729804152444980
c3 =8471234074077377509408346140986116360421840978074779990698043926601850838824365885362094731657766299393262223086536737448516669969503891677808275285733096884405583100485903641986516527279324847718603091709062689898441711907846902050004165404073776422495381050861998133576074526490209080137421773440295749900582039873013319584167081936219517593826232230971430937112005615502869367413205660317010303160932970748420125111225082886082306332340892549579826854620461821084886193470846195356695313518639669516456574134135244251956477677377976434266541164893562226872334598362396368708087248848222008201970781942468960022694
"""
  • 根据题目的已知条件就可以知道如下式子：

c1≡me mod( n1)c2≡me mod( n2)c3≡me mod( n3)c_1\equiv m^e~mod(~n_1)\\ c_2\equiv m^e~mod(~n_2)\\ c_3\equiv m^e~mod(~n_3)

  • 通过中国剩余定理就可以得到如下的一个式子，中国剩余定理具体步骤这里就不多介绍了：

x1=n2n3x2=n1n3x3=n1n2y1=x1−1 mod( n1)y2=x2−1 mod( n2)y3=x3−1 mod( n3)C=me=c1∗x1∗y1+c2∗x2∗y2+c3∗x3∗y3 mod( n1n2n3)x_1=n_2n_3\\ x_2=n_1n_3\\ x_3=n_1n_2\\ y_1=x_1^{-1}~mod(~n_1)\\ y_2=x_2^{-1}~mod(~n_2)\\ y_3=x_3^{-1}~mod(~n_3)\\ C=m^e=c_1*x_1*y_1+c_2*x_2*y_2+c_3*x_3*y_3~mod(~n_1n_2n_3)\\

  • 最后就是低加密指数的极端情况了，直接开根即可。
  • 最终的exp如下：
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
from Crypto.Util.number import *
import gmpy2
n1 = 
n2 = 
n3 = 

c1 = 
c2 = 
c3 =

N = n1*n2*n3
n = [n1,n2,n3]
c = [c1,c2,c3]

e = 13

# 衍数
M = [n2*n3,n1*n3,n1*n2]

# 乘率
y1 = gmpy2.invert(M[0],n[0])
y2 = gmpy2.invert(M[1],n[1])
y3 = gmpy2.invert(M[2],n[2])
Y = [y1,y2,y3]

# 求C
x = 0
for i in range(3):
    x = x + c[i]*M[i]*Y[i]
C = x % N

# 求m
flag = gmpy2.iroot(C,e)[0]
flag = long_to_bytes(flag)
print(flag)

"""
b'flag{f3d4fb6a-95d7-4ca0-beda-2e5e97f0fed1}'
"""

CRT 例题2

  • 题目来源byuctf2025，题目附件如下：
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
#!/usr/local/bin/python

from Crypto.Cipher import AES
from Crypto.Util.number import bytes_to_long, getPrime
from Crypto.Util.Padding import pad
import os


print("[+] Generating values...", flush=True)
# 读取flag
#flag = open("/app/flag.txt").read().encode()
flag = b'flag{test_flag}'
# 生成秘钥
key = os.urandom(160)
# 生成p、q、n
p, q, n, e = [], [], [], []
for i in range(3):
    p.append(getPrime(1024+512*i))
    q.append(getPrime(1024+512*i))
    n.append(p[i]*q[i])

# 使用密钥key对flag进行AES加密
cipher = AES.new(key[:16], AES.MODE_ECB)
print(cipher.encrypt(pad(flag, AES.block_size)).hex())
print("We will encrypt the key three times, and you can even choose the value of e. Please put your distinct e values in increasing order.")

# 要求用户输入公钥指数e,要求每次输入的e要比前一个e大,并且都大于1
try:
    e = list(map(int, input().split(" ")))
    assert e[0]>1
    assert e[1]>e[0]
    assert e[2]>e[1]
except Exception as e:
    print("sorry, invalid input")
    quit()

# 对key进行RSA加密操作
key = bytes_to_long(key)
for i in range(3):
    print(f"n{i}=",n[i], sep="")
    print(f"c{i}=", pow(key, e[i], n[i]), sep="")

  • 通过解读程序代码，我们发现flag被程序使用密钥key的前16字节进行了AES加密，要得到flag就必须获取密钥key。而，密钥key又被RSA加密了，并且会加密三次，输出三个对应的模数n和加密指数e以及密文c，并且用户输入的e必须满足当前的输入值比前一次输入的值大且都大于1。
  • 首先我们先将加密过程进行公式化表述：
    • 首先先来看一下密钥key的比特长度，发现key的长度达到了1280比特。
    • 其次我们来看看公钥nin_i的长度n1=2048,n2=3072,n3=4096n_1=2048,n_2=3072,n_3=4096，并且1<e1<e2<e31<e_1<e_2<e_3
  • 我的思路如下，在做这题的时候，原本我想要让ee变得很大，这样有可能生成比较小的私钥指数d，这样就可以进行小私钥指数攻击，但是系统学习RSA加密后，发现生成较小的私钥指数其实不太可能，在生成私钥指数的时候大概率就是和模数NN或者ϕ(N)\phi(N)的位数差不多。所以我们转向小公钥指数攻击（这里共模攻击的方法已经被排除了，因为模数不一样。）
  • 此时我们就考虑使用CRT来使得me<n1n2n3m^{e}<n_1n_2n_3，这样就能直接开方了。但是这里还有一个问题e1,e2,e3e_1,e_2,e_3是不一样的，而我们的CRT使用的条件是这样的：

c1≡me mod( n1)c2≡me mod( n2)c3≡me mod( n3)c_1\equiv m^e~mod(~n_1)\\ c_2\equiv m^e~mod(~n_2)\\ c_3\equiv m^e~mod(~n_3)

  • 但是我们其实可以考虑到一点，我们能在密文上继续做一幂运算，所以我们只要得到计算得到e=lcm(e1,e2,e3)e= lcm(e_1,e_2,e_3)，并且满足me<n1n2n3m^e<n_1n_2n_3，所以我们要选取ee尽量足够小。此时自然而然就会想到e1,e2,e3e_1,e_2,e_3分别取2,3,6，就可以使得ee是最小。并且测得keye=7679<n1n2n3=9215key^{e}=7679<n_1n_2n_3=9215，这样广播攻击和小公钥指数攻击都满足，就可以直接求解了。

  • exp如下：

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
import os
from Crypto.Util.number import *
from Crypto.Cipher import AES
import gmpy2
C = "778cce4c9b0063a68a9b501eae73d7fa"
c1 = 17752294717925161400474921690646974135901988990680710284908998422026547149182517457686939500239128773848529798569435934370027225956555492517963577893387629308663584029970428349508510055104414272893523222046142802199095506010110660292518102426052783175262814693049669486376392998388163783184537153371136645661031216252871803132514346508920699892756025104339713869685544516731830853216125518207663622067213772462904776239128160949742158359107581848689630900948260001166223551410232933066765230847962148855933388981752604168349935163481883672938845944294658147894046808725827785453247425650210067728200354592794299489514
c2 = 753401991422453240302564237878641307963640351998466978900558280649760617979940226171879140985243716071412303376043751907077112672443240016354183733268434832508456147807850274680422886512118736259354888462763124948331757726160425884497986249650719972225472819209032156669218457702914127729151085372656428104537119757697583660182668053871802068918124055415219618026043968048731378911686218229652057090691909487852047486239197192307320750451166445948673793009165411057801649198256081721287688965344410455008141448874719056811874057679510695094681675786087873118240421065731222920919772614202678874319151538044042867843422537852268027360437566177592014529935518448201855138896072016445621419110656313215002690534284480617995457634377338551778523824958304779754124846300536196574424673064714460185717792275784544833021543513216916311230995020744221038450059304434700538718592373987751625424645183315612428759100792951774697297442
c3 = 13727730205642414994322398714432148155677011386362440948481478644698201920443178419582034287391074781504177196884375374646407097781119892716792673209133063011297366050027994996312797919514137644986042769415163452251196832454319487345523317618583872833225920622892489104799195771098912665366099530327577730038284609603098548683099701576796417770465930958208686978637043842759586109093993045669635759274061938387840631379855530523025367585779427196585192899830079253095484678355957912777955026482895383430272765389607391940415170643887727885215414730209680807547643733544710563702177227881478776389585053895534239449184364100361880873565003411594754868175251066327556314373039691461284793650627521652217930880478718759008555760525510701103408361646096196299718710338927979858151714976811055524183723030075087677441506131840020337735093849739434223783814457110961159670311632424093771073281358194734655854828310618168170211612235885921729268492999980612041024282645757086952968109467361765523274610835708424431958756374607926413318726559044283867727562794286561177771934772712496937254753487097118545519875579261682810493653902604786505304101900509915281516663858090954072908968902972412314757014065830044489100238967365574345258587385
n1 = 21572329391655165399886678831561049078523605393024083324410763086198868503158344398018855454411470337532903086734209822211818015827230616510112208619852794761385522469264777655579993249858221114662602905485808530348639653975532664002861860845605752350719363553450029440660743664220615673323151972479870812484568323276624728901969825332270190934145710780129709218334981622539341789417056807918852801326613750873760309613562023970838752521139618828917711563731698515037189092473250322863364984587442893661099836033006248935450474348835734942873634572448961670483146699089812778203557073074467741962237422468920638383817
n2 = 1778170357852911386696036177875681775863905312543146044872976195004771058179503488855175550357255551556263073920718179876910145804469399704012797991202568995543320357546847158011484553343545829479381326843081951341010172643871663882633226465814585822135846731029073408271334939185923847107543034338619414254214892895001283973921319772481642297800687732901096499293379961815584592729922593249065364060059152155834836996320501728028403164130465877686625011448951745643924223790231519420629669636700168663870525720213589412105496761281636683467131985026599989268304553418625925359632696474745643625132688817563693224699255398696314029077658402580993275760521781793643773726876265914872970785494782580846186992152845136094338603074397128900708616833017437376845260718996575866900234433178083725869942699668013394161315827499363820316422357688711318660940499778303214059683017408297448757998804917021738448799749663859905578731379
n3 = 516035933387169178062893548957198358820827435225534922651380295157765713070381115117254265659059000244282093167359006617473755002135242806242197926823232318074229716603229796935750009833658374132411536291520702086793184542131702893030551797629400341930916724993861314255420194647445247560639045548310690549628641772869323237780305560458704324194246434459748308699526997751371110187474548353599288653537442924170740808327077051007245015395359830671010163503250084281172696985136654908220682216563262633403203100959023387362980785728437393459392937267755106611878910684153406538931035184840935655389630181609320357490776445781087020520756990648685651585375440868884540608515522310255842190426764124869567818615395069582029053789123498628995912064633789648597225748374743902613531596493313913348571132797013514471826625491296493266009071050572227404766446531213571404879949461944538966854871689519392276595845976077700947852303892916918097332475347016605011632265116159519193334155418804135458118808213374556186595943528041048135206299230322196805733458090401692715514651202521345416030359714372437857081521840607370890813583981385611525699572531904775380986850647463158575353619044394838073471957516639987877649580748210204528016550687
e1 = 2
e2 = 3
e3 = 6
C1 = pow(c1,3)
C2 = pow(c2,2)
new_C = [C1,C2,c3]
e = 6
n_list = [n1,n2,n3]
new_n = n1*n2*n3
new_C2 = 0
for i in range(len(n_list)):
    x = new_n//n_list[i]
    y = pow(x,-1,n_list[i])
    new_C2 = new_C2 + x*y*new_C[i]

new_C2 = new_C2 % new_n
key = gmpy2.iroot(new_C2,6)[0]
key = long_to_bytes(key)
ciper = AES.new(key=key[:16],mode=AES.MODE_ECB)
flag = ciper.decrypt(bytes.fromhex(C))
print(flag)
# b'flag{test_flag}\x01'

题型2 拓展中国剩余定理

  • 对于拓展中国定理，其实是解决模不互质的情况下，但是对于两个素数的RSA模数来说，如果模数之间如果两两不互质那么就可以直接使用gcdgcd进行分解了，所以拓展中国剩余定理一般是在多个素数的RSA模数。

exCRT 例题1

  • 题目附件如下：
1
1

循环攻击

  • 循环攻击，英文名称为Cycling Attacks，这个是最后一个RSA加密的早期攻击。虽然这些攻击总体上并不对RSA的安全性构成实质性威胁，但仍然要将其纳入讨论，用来表明在使用具有特殊结构的RSA素数时，可能潜藏风险

  • 在1997年Simmons和Norris观察到，只要不断对密文进行重复加密，最终总能通过循环回到自身，从而恢复出明文。

    • 给定密文c≡me mo( N)c\equiv m^{e}~mo(~N)以及公钥(e,N)(e,N)
    • 如果在经过l+1l+1次重新加密后再次得到原密文，即cel+1≡c mod( N)c^{e^{l+1}}\equiv c~mod(~N)
    • 那么就可以推出cel≡m mod( N)c^{e^{l}}\equiv m~mod(~N)
    • 因此，在经过ll次重新加密后，明文就被恢复出来了。

  • 最初的循环攻击方法如下：

    • 寻找使明文被恢复的最小ll。这个最小的ll有时被称为该明文mm的恢复指数。注意总存在一些明文，其恢复指数非常小。例如，明文m=±1m= \pm1的指数为l=1l=1（因为ee是奇数，此时c=mc=m）。

    • 此外还可以证明：任意明文的恢复指数都可以由下面定理刻画，该定理记为定理3.4，定理如下：

      • 设(e,N)(e,N)是一个有效的RSA公钥，对于任意的明文m∈ZNm\in Z_N，mm的恢复指数必然整除λ(λ(N))\lambda(\lambda(N))

    • 这个这个定理意味着λ(λ(N))\lambda(\lambda(N))是可能出现的最大恢复指数。因此·，如果素数的选择使得λ(λ(N))\lambda(\lambda(N))足够小，那么这种攻击对所有明文都可行。另一方面，如果λ(λ(N))\lambda(\lambda(N))只含有较小的素因子，那么该攻击可能对部分明文是可行的。

    • 然而如果使用的是安全素数，则可以预期大多数明文具有较大的恢复指数，因此λ(λ(N))\lambda(\lambda(N))本身很大且包含大的素因子。进一步，Friedlander、Pomerance、Shparlinski证明了，对于几乎所有由平衡素数和公钥指数构成的RSA参数，除了一个可以忽略不计的小集合外，其余明文的恢复都满足l>N1−ϵl>N^{1-\epsilon}（其中ϵ\epsilon是一个很小的常数）。因此，当NN足够大时，原始的循环攻击在实践中是不可行的。

  • 在1979年，Williams和Schmid对循环攻击进行了推广不再在模N下寻找循环，而是在模p(或q)下寻找循环，具体而言，攻击者寻找满足下式的最小kk：

    g=gcd(cek−c,N)>1g=gcd(c^{e^{k}}-c,N)>1

    • 如果1<g<N1<g<N，则说明在模pp或者模qq下发现了一个循环，而gg就直接泄露了模数的因子（即g=pg=p或g=qg=q）。如果g=Ng=N则说明是在模NN下发现了循环，与原始循环攻击相同，此时

    cel−1≡m mod( N)c^{e^{l-1}}\equiv m~mod(~N)

    • 这种改进后的攻击是否有效，显然取决于kk的大小。如果素数pp被选取使得λ(λ(p))=λ(p−1)\lambda(\lambda(p))=\lambda(p-1)，只含义较小的素因子，或者其本身就足够小，那么就可能在相对较小的kk下找到模pp的循环（对q同理）、
    • 当素数是随机选取的，除了极少数明文外，几乎所有密文都满足k>N12−ϵk>N^{\frac{1}{2}-\epsilon},因此当使用足够大的随机素数时，这种改进的循环攻击在实践中同样是不可行的。

总结

共模攻击

  • 关于协议错误如果还要拓展，可以参见：

    • Moore写的Protocol failures in cryptosystems. Proceedings of the IEEE
    • Simmons写的An RSA-related number-theoretic surprise. In Computer Systems Theory, Technology, and Applications,Monographs in Computer Science, chapter 39, pages 269–271. Springer New York, 2004

  • 共模协议在早期曾被反复提出，是一种较早且多此出现的方案，但最终证明是完全不安全的。例如在下面论文中提到这种类型的协议曾被多次重新发明

    • DeLaurentis所写的A further weakness in the common modulus protocol for the RSA cryptoalgorithm
    • Håstad所写的On using RSA with low exponent in a public key network. In H. C. Williams, editor, CRYPTO, volume 218 of Lecture Notes in Computer Science, pages 403–408. Springer, 1985
    • Moore写的Protocol failures in cryptosystems. Proceedings of the IEEE

  • 在已知RSA公钥和私钥指数的情况下，对RSA模数进行分解的确定性多项式时间算法，直到在发现概率型多项式时间算法二十多年之后才被找到。这种确定性方法利用了Coppersmith的小根方法来求解二元整数方程的小根，最早由May于2004年提出，随后又被Coron和May进一步改进。

    • May所写的Computing the RSA secret key is deterministic polynomial timeequivalent to factoring. In M. K. Franklin, editor, CRYPTO, volume3152 of Lecture Notes in Computer Science, pages 213–219. Springer,2004.
    • Coron 和 May所写的Deterministic polynomial-time equivalence ofcomputing the RSA secret key and factoring. Journal of Cryptology,20(1):39–50, 2007.

Håstad广播攻击

  • 共明文攻击首次于1985年由Håstad所发表，但是在此之前这个攻击已经被Blum、Lieberherr和Williams所知道。事实上这个攻击在1983年就被提及，只是没有发表。

  • Håstad的消息相关攻击最初适用于线性相关的消息情形，当所有公钥指数相同的时候，由于当时仅有基于格的技术，该攻击需要l≥12e(e+1)l≥\frac{1}{2}e(e+1)个密文。

  • 随着Coppersmith提出的用于求解一元模方程小解的方法，所需的密文数量被降低为l≥el≥e（针对线性相关的明文）。该攻击推广到任意多项式相关的明文很显然的，这个观点是由Shimizu在Improvement of H˚astad bound. Proceedings of the Society Conference of IEICE以及Bleichenbacher在On the security of the kmov public key cryptosystem.提出。

  • 事实上定理3.3的结果并非最优。

    • Bleichenbacher还在论文中指出，只要使用不同的公钥指数，在密文数量少于δ=maxi{eideg(fi(x))}\delta=max_i\{e_ideg(f_i(x))\}的情况下，仍然可以恢复明文。
    • 更进一步的结果最近由May和Ritzenhofen在论文Solving systems of modular equations in one variable: How many RSA-encrypted messages does Eve need to know?中提出。
      • 令δi=eideg(fi(x))\delta_i=e_ideg(f_i(x))，他们证明：如果这些δi\delta_i满足∑i=1l1δi≥1\sum_{i=1}^{l}\frac{1}{\delta_i}≥1，那么明文就可以被恢复。
      • 因此，对所需密文数量的唯一要求就是满足上述不等式。

循环攻击

  • 一些广义的循环攻击由Gysin和Seberry所提出，可以看这篇论文Generalised cycling attacks on RSA and strong RSA primes.

    • 利用中国剩余定理，可以证明恰好存在K1=(gcd(e−1,p−1)+1)(gcd(e−1,q−1)+1)K_1=(gcd(e-1,p-1)+1)(gcd(e-1,q-1)+1)个恢复指数l=1l=1的明文。
    • 这些明文正是RSA函数的不动点。关于该结论的证明可以参考 Katzenbeisser所写的An attack on RSA given a small fraction of the private key bits.
    • 由上述表达式可以看出，由于p、q、ep、q、e都是奇数，因此不动点的数量至少为9个。
    • 更一般地，恢复指数为ll的明文个数为：Kl=(gcd(el−1,p−1)+1)(gcd(el−1,q−1)+1)K_l=(gcd(e^l-1,p-1)+1)(gcd(e^l-1,q-1)+1)，该结论的证明可以参考Joye写的How to choose secret parameters for RSA-type cryptosystems over elliptic curves.。对KlK_l在所有素数选择下的期望值，可以参考Yu的An approximate expression related with RSA fixed points.

  • 在论文Are ‘strong’ primes needed for RSA. Cryptology ePrint Archive中Rivest和Silverman认为，使用随机素数即可高概率意义下避免循环攻击。

  • 随后Friedlander、Pomerance 和 Shparlinski在论文Period of the power generator and small values of Carmichael’s function.为这一论断提供了严格的数学证明。

  • 关于RSA循环攻击的历史，可以参考上面提到的Rivest和Silverman写的Are ‘strong’ primes needed for RSA. Cryptology ePrint Archive

共模攻击刷题

共模刷题1

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
46
47
48
49
50
51
52
53
54
55
56
from Crypto.Util.number import *
import os
import random
import string

flag = os.getenv('FLAG')
# 菜单操作
def menu():
    print('''=---menu---=
1. Guess
2. Encrypt
''')

# 生成RSA公钥
p = getPrime(512)
q = getPrime(512)
n = p*q

# 生成一个随机的消息
def randommsg():
    return ''.join(random.choices(string.ascii_lowercase+string.digits, k=30))

mymsg = randommsg()

# 让用户猜测消息
def guess():
    global mymsg
    msg = input()

    if msg == mymsg:
        print(flag)
    else:
        print(mymsg)
        mymsg = randommsg()

# 加密消息
def encrypt():
    e = random.getrandbits(8)
    c = pow(bytes_to_long(mymsg.encode()), e, n)
    print(f'Cipher_{e}: {c}')
# 主函数
def main():
    # 给公钥n
    print(f'n: {n}')
    # 无限循环次数
    while True:
        # 让用户输入选项
        opt = int(input())
        # 选项1是猜测消息
        if opt == 1:
            guess()
        # 选项2是加密随机消息
        elif opt == 2:
            encrypt()

main()
  • 通过看附件代码大致可以了解到该题目的具体操作：
    • 生成一个随机消息mm
    • 程序会给用户两个选项
      • 选项1是让用户猜测随机消息m，猜测对了就给flag，猜测错了就重新生成一个随机消息继续让用户猜测
      • 选项2是将消息m通过RSA加密，并返回加密后的密文。其中程序所使用的RSA加密模数是固定的，公钥指数ee在每次加密就会随机生成
  • 首先不急着分析如何破解该密码系统，先看看消息的格式是怎么样的，发现消息其实就是纯数字加字母组合。

image-20260127212334788

  • 接下来分析如何破解这个密码系统，由于使用RSA加密明文m的模数n是相同的，所以存在共模攻击，我们只要选择n次选项2，选择其中两个加密所用的公钥指数互素的即可，也就是gcd(e1,e2)=1gcd(e_1,e_2)=1即可完成共模攻击操作。

  • exp如下：

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
from pwn import *
from Crypto.Util.number import *
import gmpy2
context.log_level = 'debug'
p = remote('node4.anna.nssctf.cn',20609)
n = p.recvline().decode().strip()[2:]
n = int(n,10)
print(n)

def my_recv():
    while True:
        p.sendline(b'2')
        p.sendline(b'2')
        c1 = p.recvline().decode().strip()
        c2 = p.recvline().decode().strip()
        x1 = c1.split(':')
        x2 = c2.split(':')
        c11 = int(x1[1],10)
        c22 = int(x2[1],10)
        e1 = int(x1[0][7:],10)
        e2 = int(x2[0][7:],10)
        print('c11=',c11)
        print('c22=',c22)
        print('e1=',e1)
        print('e2=',e2)
        if gmpy2.gcd(e1,e2) == 1:
            return [e1,e2,c11,c22]
x = my_recv()
e1 = x[0]
e2 = x[1]
c1 = x[2]
c2 = x[3]
_ , s, t = gmpy2.gcdext(e1,e2)
print(_)
print(s)
print(t)
m = (pow(c1,s,n) * pow(c2,t,n)) % n

flag = long_to_bytes(int(m))
print(flag)
p.sendline(b'1')
p.sendline(flag)
p.interactive()

image-20260127214055376