网址：

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

一、共模攻击

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=明文

攻防世界best_rsa

屏幕截图 2024-12-03 200329

解密

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.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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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))

BUUCTF samemod

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

n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249

e1 = 773
e2 = 839

c1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
c2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

p = 4159
q = 64093705392379722528790901257895026952566998399131944106279664097465915559869776757296166647943384549637331014969781934511

s = gmpy2.gcdext(e1, e2)
if s[1] < 0:
    
    s1 = -s[1]
    c1 = inverse(c1,n)
    #s[1] = -89
s2 = s[2]
print(s1)
print(s2)

m1 = pow(c1,s1,n)
m2 = pow(c2,s2,n)
m = (m1*m2)%n
print(m)
#1021089710312311910410111011910111610410511010710511610511511211111511510598108101125
#flag需要是可见字符，所以不存在1开头的十位数，所以1开头的肯定是100以上的三位数，用ASCII码解
m_str = str(m)
flag = ""
i = 0
while i < len(m_str):
    if m_str[i] =='1':
        c = chr(int(m_str[i:i+3]))
        i += 3
    else:
        c = chr(int(m_str[i:i+2]))
        i += 2

    flag += c
print(flag)

NSSCTF BJDCTF2020rsa

题目：

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
from Crypto.Util.number import getPrime,bytes_to_long

flag=open("flag","rb").read()

p=getPrime(1024)
q=getPrime(1024)
assert(e<100000)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,n
print pow(294,e,n)

p=getPrime(1024)
n=p*q
m=bytes_to_long("BJD"*32)
c=pow(m,e,n)
print c,n

'''
output:
12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120  13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721  12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
'''

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

c1 = 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
n1 = 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
mx = 381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
c2 = 979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721
n2 = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047

q = GCD(n1,n2)
p1 = n1//q
p2 = n2//q

n = p1*q
n_1 = p1 * q
# mx = pow(294,e,n_1)
#爆破求e
def find_e():
    for i in range(2,100000000000000):
        if pow(294,i,n_1) == m :
            return i

# e = find_e()
# print(e)
#c2的作用是验证因此求出c1得出结果即可
e =52361
phi = (p1-1)*(q-1)

d = inverse(e,phi)
m1 = pow(c1,d,n)
print(long_to_bytes(m1))

NSSCTF BJDCTF2020 rsaoutput

非常简单的共模

题目：

1
2
3
4
5
6
7
{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,2767}

{21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111,3659}

message1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599

message2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from gmpy2 import *

n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111

e1 = 2767
e2 = 3659

c1=20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599
c2=11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227

d,x,y = gcdext(e1,e2)
m1 = pow(c1,x,n)
m2 = pow(c2,y,n)
md = (m1*m2)%n
m = iroot(md,d)[0]
print(long_to_bytes(m))

NSSCTF Spring —crypto1

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

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
from gmpy2 import *
from Crypto.Util.number import *
flag1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
flag2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
#
# flag  = '****************************'
# flag = {"asfajgfbiagbwe"}
# p = getPrime(2048)
# q = getPrime(2048)
# m1 = bytes_to_long(bytes(flag.encode()))

e1e2 = 3087

for e1 in range(1,3087):
    if 3087 % e1 == 0:
        e2 = 3087// e1
        d,x,y = gcdext(e1,e2)
        m1 = pow(flag1,x,n)
        m2 = pow(flag2,y,n)
        m_d = (m1*m2)%n
        m = long_to_bytes(iroot(m_d,d)[0])
        if m[0:6] == b'NSSCTF':
            print(m)

**注：**gcdext返回三个值

变量 满足的等式 作用
d d = gcd(e1, e2) e1 和 e2 的最大公约数。
x e1 * x + e2 * y = d 用于计算 c1^x（在 RSA 共模攻击中还原 m）。
y e1 * x + e2 * y = d 用于计算 c2^y（在 RSA 共模攻击中还原 m）。

如果 d = 1：x 是 e1 模 e2 的逆元，可直接解密。

如果 d > 1**：需对 m^d 开 d 次方才能还原 m。

二、e与phi不互素

蜀道山crypto xorsa

原题
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
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
'''

解题

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
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

题干：

1
2
3
4
5
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

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
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泄露

[例题]电协杯网络安全大赛

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
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

原理：待更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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))

原理

RSA侧信道攻击-CSDN博客

image-20250729164153306

通用代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
p_q = inverse(p,q)
m = m1 + p_q*((m2-m1)%q)*p
print(long_to_bytes(m))
##########################################
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))

四、低指数e攻击

[1]NSSCTF swpuctf crypto5

题目

1
2
3
c= 25166751653530941364839663846806543387720865339263370907985655775152187319464715737116599171477207047430065345882626259880756839094179627032623895330242655333
n= 134109481482703713214838023035418052567000870587160796935708584694132507394211363652420160931185332280406437290210512090663977634730864032370977407179731940068634536079284528020739988665713200815021342700369922518406968356455736393738946128013973643235228327971170711979683931964854563904980669850660628561419

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from gmpy2 import *

c= 25166751653530941364839663846806543387720865339263370907985655775152187319464715737116599171477207047430065345882626259880756839094179627032623895330242655333
n= 134109481482703713214838023035418052567000870587160796935708584694132507394211363652420160931185332280406437290210512090663977634730864032370977407179731940068634536079284528020739988665713200815021342700369922518406968356455736393738946128013973643235228327971170711979683931964854563904980669850660628561419

#爆破e
for e in range(1,100):
    root,baopo = iroot(c,e)
    if baopo:
        m = root
        print(long_to_bytes(m))

**iroot函数：**iroot（x,y） x的y开方 返回的是一个 元组（tuple），包含两个值：

1
(root, is_exact) = iroot(x, y)
  1. root
    • 类型：整数（int 或 mpz）
    • 含义：x 的 y 次方根的 整数部分（向下取整）。
    • 公式：root = floor(x^(1/y))
  2. is_exact
    • 类型：布尔值（bool）
    • 含义：x 是否是一个 完全的 y 次方数（即 root^y == x）。
      • 如果 True，说明 x 能精确表示为某个整数的 y 次方。
      • 如果 False，说明 x 不是完全的 y 次方数。

五、看不懂的

[1]BUUCTF RSA

屏幕截图 2024-11-26 133400

用notebook打开pub.key得到

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

公钥解析

屏幕截图 2024-11-26 133553

爆破出p，q

1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
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

1
2
3
4
5
6
7
8
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_!@}

七、中国剩余定理

解法

1.计算所有模的乘积N

2.对第i个方程计算

a. mi = N//ni

b. 计算mi在模ni下的逆元di

c. 计算ci = mi*di

3.方程组在模N下的唯一解image-20250722222100929

解题

[鹤城杯2021]Crazy_Rsa_Tech

题目：

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

FLAG = bytes_to_long(pad(b"flag{??????}", 64))


def init_key():
    p, q = getPrime(512), getPrime(512)
    n = p * q
    e = 9
    while (GCD((p - 1) * (q - 1), e) != 1):
        p, q = getPrime(512), getPrime(512)
        n = p * q
    d = inverse(e, (p - 1) * (q - 1))
    return n, e, d


n_list = list()
c_list = list()
for i in range(9):
    N, e, d = init_key()
    n_list.append(N)
    c = pow(FLAG, e, N)
    c_list.append(pow(FLAG, e, N))
    assert (pow(c, d, N) == FLAG)
print("n_list:", n_list)
print("c_list:", c_list)
'''
n_list: [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c_list: [62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]
'''

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
44
45
46
47
48
49
50
51
52
from Crypto.Util.number import *
from gmpy2 import *

n_list =[
    71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799,
    92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949,
    100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919,
    59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847,
    66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147,
    120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377,
    72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281,
    69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951,
    76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c_list = [
    62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585,
    46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900,
    85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198,
    14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656,
    1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839,
    2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981,
    16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376,
    31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996,
    25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]

e = 9
N = 1
for n in n_list:
    N = N*n
#定义列表M_list
M_list=[]
for n in n_list:
    M_list.append(N//n)

d_list=[]

for i in range(len(n_list)):
    d_list.append(inverse(M_list[i],n_list[i]))

#summary是唯一解即明文M
C_list=[]
summary = 0
for i in range(len(d_list)):
    C_list.append(d_list[i] * M_list[i])

for i in range(len(C_list)):
    summary = (summary+c_list[i] * C_list[i])%N

m = iroot(summary,e)[0]
print(long_to_bytes(m))



八、其他

NSSCTF HDCTF2023normal_rsa（多个数）

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
#from shin import flag
 
 
m=bytes_to_long(b'HDCTF{******}')
e=65537
p=getPrime(256)
q=getPrime(512)
r=getPrime(512)
n=p*q*r## phi=(p-1)*(q-1)*(r-1)
P=pow(p,2,n)
Q=pow(q,2,n)
c=pow(m,e,n)
print(f"P = {P}")
print(f"Q = {Q}")
print(f"n = {n}")
print(f"c = {c}")
'''
P = 8760210374362848654680470219309962250697808334943036049450523139299289451311563307524647192830909610600414977679146980314602124963105772780782771611415961
Q = 112922164039059900199889201785103245191294292153751065719557417134111270255457254419542226991791126571932603494783040069250074265447784962930254787907978286600866688977261723388531394128477338117384319760669476853506179783674957791710109694089037373611516089267817074863685247440204926676748540110584172821401
n = 12260605124589736699896772236316146708681543140877060257859757789407603137409427771651536724218984023652680193208019939451539427781667333168267801603484921516526297136507792965087544395912271944257535087877112172195116066600141520444466165090654943192437314974202605817650874838887065260835145310202223862370942385079960284761150198033810408432423049423155161537072427702512211122538749
c = 7072137651389218220368861685871400051412849006784353415843217734634414633151439071501997728907026771187082554241548140511778339825678295970901188560688120351732774013575439738988314665372544333857252548895896968938603508567509519521067106462947341820462381584577074292318137318996958312889307024181925808817792124688476198837079551204388055776209441429996815747449815546163371300963785
'''

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 *
from gmpy2 import *

# from shin import flag

m = bytes_to_long(b'HDCTF{******}')
e = 65537
p = getPrime(256)
q = getPrime(512)
r = getPrime(512)
n = p * q * r  ## phi=(p-1)*(q-1)*(r-1)
P = pow(p, 2, n)  ## P=p**2  p=iroof(P,2)
Q = pow(q, 2, n)  ## Q=q**2  q=iroof(Q,2)
c = pow(m, e, n)  ## 求d，d = gmpy2.invert(e, phi)
print(f"P = {P}")
print(f"Q = {Q}")
print(f"n = {n}")
print(f"c = {c}")

P = 8760210374362848654680470219309962250697808334943036049450523139299289451311563307524647192830909610600414977679146980314602124963105772780782771611415961
Q = 112922164039059900199889201785103245191294292153751065719557417134111270255457254419542226991791126571932603494783040069250074265447784962930254787907978286600866688977261723388531394128477338117384319760669476853506179783674957791710109694089037373611516089267817074863685247440204926676748540110584172821401
n = 12260605124589736699896772236316146708681543140877060257859757789407603137409427771651536724218984023652680193208019939451539427781667333168267801603484921516526297136507792965087544395912271944257535087877112172195116066600141520444466165090654943192437314974202605817650874838887065260835145310202223862370942385079960284761150198033810408432423049423155161537072427702512211122538749
c = 7072137651389218220368861685871400051412849006784353415843217734634414633151439071501997728907026771187082554241548140511778339825678295970901188560688120351732774013575439738988314665372544333857252548895896968938603508567509519521067106462947341820462381584577074292318137318996958312889307024181925808817792124688476198837079551204388055776209441429996815747449815546163371300963785



p = iroot(P,2)[0]
q = iroot(Q,2)[0]
r = n//p//q
phi = (p-1) * (q-1)*(r-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

[0]的作用：

iroot返回两个值形成的元组

第一个值：整数部分的开方结果（向下取整）。

第二个值：布尔值，表示 x 是否是完全平方数（即是否能被开方后得到整数）。

其中[0]代表返回第一个数值即开方结果

NSSCTF BJDCTF Easyrsa（方程组求pq）

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import getPrime,bytes_to_long
from sympy import Derivative
from fractions import Fraction
from secret import flag

p=getPrime(1024)
q=getPrime(1024)
e=65537
n=p*q
z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))
m=bytes_to_long(flag)
c=pow(m,e,n)
print(c,z,n)
'''
output:
7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441

'''

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from sympy import *
from fractions import *
from gmpy2 import *
c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
e=65537


x = iroot(z+2*n,2)[0]
y = iroot(z-2*n,2)[0]

p = (x+y)//2
q = x-p
n=p*q
phi = (p-1)*(q-1)

d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

其中

1
z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))

化简得z = p^2 + q^2

Fraction(a,b) = a/b

Derivative(arctan(p),p)为arctan（p）关于p求导

[方程组解flag] NSSCTF GWctf babyrsa

题目：

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

flag = 'GWHT{******}'
secret = '******'

assert(len(flag) == 38)

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)

N = p * q

e = 0x10001

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

output = open('secret', 'w')
output.write('N=' + str(N) + '\n')
output.write('m1=' + str(m1) + '\n')
output.write('m2=' + str(m2) + '\n')
output.close()

N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546


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
from Crypto.Util.number import *
from gmpy2 import *
from sympy import *
p = 797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737
q = 797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699

n=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
phi = (p-1)*(q-1)
e = 65537
d = inverse(e,phi)
c1 = pow(m1,d,n)
c2 = pow(m2,d,n)
print('c1=',c1)
print('c2= ',c2)
c1 = 2732509502629189160482346120094198557857912754
c2 = 5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554

# f1,f2 = symbols('f1 f2')
# sol = solve([f1+f2-c1,pow(f1,3)+pow(f2,3)-c2],[f1,f2])
# print(sol)
f2 = 1141553212031156130619789508463772513350070909
f1 = 1590956290598033029862556611630426044507841845
print(long_to_bytes(f1)+long_to_bytes(f2))

NSSCTF闽盾杯decode（共享素数）

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n1=
15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591
n2=
28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749
n3=
18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839
e1=
65537
e2=
27751
e3=
65537
c1=
5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206
c2=
21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741
c3=
13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486

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


n1=15228664629164509105936278301396170708905691970126305196584505186788860519598413718493859625462561931380632032431490419378905593909771649295663481782473029836321132574188559245931660756414915507930357509270674460219615256962333464689419869130366867401404262606367700782040693275068101244535880649261286041921882470460606034302142183971677715439862839410834231609821777031530457674591868138859358815039755085358568037032478394036448363183057305077227769673701227083943898736796552550712057417053897722979700329662099072959306298177351997084389916443815546425080826441671985030755256185725913397986385179516049927425591
n2=28182418532443955655250943929828439725377604572088962537896240628709829618999901367131159759359513146864646169253348651905865895468151210748207509325666501438590382812326109260537618829438786609626137074778638549998280533912080708785604673270460635181275360847313985764185991865570533815651261638439461846512012164531330949433517277559149828806588070421852157781670188281908625986974579194819272643409859915715455134433970119584552350648013116998668938513347083566970423327936691885137812528912263666957628197241313496232397910546498542303925205356813548741679943691886217742767778075067797422624969714343428365022749
n3=18355811159408154065817199279776805621878757240392366715869421799780946779485225342662736231980532326015283372375030686507311099745671828649419794838611580909610100636296701054995302819692794479292794716441442731393027118795245239019609474743841061251498233337758043553376098591254587406941205804917663153256036922860462415387926973551020540123742773938055950168965005226319984869124543783579240130888344231027912143592472823564266887957101575622993773291455143915263715932280728961208233983782906070719786115187115449430196335973764600533097718947377609348244073036523422892353195107093782201003551217830556519184839
e1=65537
e2=27751
e3=65537
c1=5368342382489380107251269030258282008067103595899117880173297169710980852124379736420135829984131832023988667774795223808420069001078159756328642298736759964890517323144475742861501409284299556459601222657540302786301791897975932176538612601162552795835603779910738886150925504885639254302406755008796950704938463132687940418772021406619622090999564746948113296328739593309200238996686945891130656599419832796482095787039339269564880847130379179831744694000940207887150388411084465949903406848727641093033681144598595895383689139227400553234701993087147186292040330589331703587405822925483701667354935313494938769206
c2=21521672635651854919517759696514027081496995002884626306313384597771682621826437868933822942195279941318573525337109548152966094293276717095298929811895186384560362917891928656637913236676702009205642367801075592458101830488916914437754803979953027152373619293870115731171449223105986403604973873007338969000153480949617700626516389419935352576014084068271819009465242491467427642787306345049280205827574043586767133396458785487959251540831856187380154825027964867977651727983254127239427622549059938701125498520279503972702883327594442747467858234391945790597844344295786118320620376681461727686876948563884520137741
c3=13940747781246179701167820858098775936269078279837839169409057305686612176371099274767269714494905207551971162649902129137425806839867713157472497469542260664882313041602553845621113546259276402534229231780532278276697961222319054833980226978574905974878218905613341365260453461080117407529132948986104191917111000811731784483944945364091757083949827612260904757837644538366763161154611658652020868326985526984718638276184626634240096213703958275241215175054246685206226179114590838833694648062135027841593419815101363262701960507235056752424778384286627997500871204804629047307688466887868894491042058198480775705486

print(GCD(n1,n2))
print(GCD(n1,n3))
print(GCD(n2,n3))

q = 164859868553249815375465515536987306623131320301180002030596754516169382971483280280050416812867330100920472805447067962573478106770149358778022505886042560677688273443121979605531497210263525146050862376433097961549457323861954433494105536481811775338295714354574957049936722814247877925363167027488513485709
p1 = n1//q
phi1 = (p1-1)*(q-1)
d1 = inverse(e1,phi1)
m1 = pow(c1,d1,n1)

p2 = n2//q
phi2 = (p2-1)*(q-1)
d2 = inverse(e2,phi2)
m2 = pow(c2,d2,n2)

p = 170947719294953951536954804874265400920113414452513922259518562825523270724522671134646540343587230143343957717391417413047862015209874483354836787138806208359442575426704287014199781192528646303567293038395409478835967812793376905814000735826363654051481172441177831363316445615089791419435137252709673060561
q3 = n3//p
phi3 = (p-1)*(q3-1)
d3 = inverse(e3,phi3)
m3 = pow(c3,d3,n3)
print(long_to_bytes(m1))
print(long_to_bytes(m2))
print(long_to_bytes(m3))

[一组c循环运行代码]NSSCTF HUDUCTF RSAaaa

题目：

1
2
3
4
5
6
就你小子是黑客？
我忘记怎么解密了！
靠你了,大黑阔！

(536970330703,65537)
message：[473878130775,40132555282,40132555282,94619939727,72818765591,208015808884,42561234694,159353248388,27748063975,159353248388,159353248388,278953790403,410746718603,496849210942,27748063975,142521857906,103632267191,17774494147,328684046745,278953790403,129956887006,129956887006,366275425558,328684046745,142521857906,410746718603,142521857906,129956887006,379067009467,328684046745,159353248388,366275425558,129956887006,103632267191,27748063975,27748063975,17774494147,160623996897,278953790403,182341799525]

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from gmpy2 import *

n = 536970330703
p =  992623
q = 540961
e = 65537
c_list = [473878130775,40132555282,40132555282,94619939727,72818765591,208015808884,42561234694,159353248388,27748063975,159353248388,159353248388,278953790403,410746718603,496849210942,27748063975,142521857906,103632267191,17774494147,328684046745,278953790403,129956887006,129956887006,366275425558,328684046745,142521857906,410746718603,142521857906,129956887006,379067009467,328684046745,159353248388,366275425558,129956887006,103632267191,27748063975,27748063975,17774494147,160623996897,278953790403,182341799525]

phi = (p-1)*(q-1)
d = inverse(e,phi)
m_ = b''

for c in c_list:
    m = pow(c,d,n)
    m_ += long_to_bytes(m)
print(m_)

巨简单的一题

[欧拉函数]NSSCTF HGAME Multi Prime RSA

（来自大佬的知识灌输）

image-20250730151533098

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import getPrime
from libnum import s2n
from secret import flag

p = getPrime(256)
q = getPrime(256)
r = getPrime(256)
s = getPrime(256)
n = p ** 2 * q ** 3 * r ** 5 * s ** 7
e = 65537
c = pow(s2n(flag), e, n)
print(f"p = {p}")
print(f"q = {q}")
print(f"r = {r}")
print(f"s = {s}")
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import  *
from gmpy2 import *

p = 61789932148719477384027458333380568978056286136137829092952317307711908353477
q = 91207969353355763685633284378833506319794714507027332929290701748727534193861
r = 105471299607375388622347272479207944509670502835651250945203397530010861809367
s = 83153238748903772448138307505579799277162652151244477391465130504267171881437
n = 1039344372165087100001063920598151812324151064684841845250974758525265148567706103784958424873181721352440209284812493753972556519482026327282644619091466886523804841248277210353173383407944598453848113815866908595335619458549486958764490103808475329598085842184963065068499489886467911087295087163762599284622055185456905774507245781667293199205317692029829495961487347944813874415423771980660778986211145841712412631156369129146470119135136378158203459576596246169191419488560832734046076107673091995860021863239882608638458149930255944184863801278386551031980146460231515747754411678651752698881001464973981424240781413084941947261875289725538959720572496329348499870580057997540844488309111059240745081048324762866572948371222839278718034435739827677190025500802453626872356208612718417249649474571197167076916403582394186357812640566250930361276229969553128128312736245440129556020108188835966131425956431796417720436474093381770796431629523054378258497546013222494974549262140415585158985940966415459478150722832119691308697510189026447359189994055885090735411738332296254011208547676914004864732327863884217733456287369771087094514708468685641820375220835485053482570852619363091173324203334503461823983610886849930944250553928855506012684504211525542998575275626784129736345142772399109273619522445919
e = 65537
c = 844677395496466411520394190869787261209960246734415406217975986418865760680024542119231873259131861208878522030009923057991526761346423130242121884493257732067700857897379859545356609151834223804262174935191718271211809221730601602827122249238086030580971376104724987801049500689134122609834321586609223761140538079460830213824674361601046367637227094018381901291488659642720549583856812747877519600804325570421770575999289389175021646347371879234023647657507178519047236746071420327155188213839293382288787853777540226192644761028822256165706787395891134765908229036044468473519166141610604791485071702808854944672418124203289328124793348198048601338476086482318248264508789781967910205393740835345086784345145351367491197717933757414967811594913692588314161669333147733048171044386546892346475181197482702164468542430187885074163177843285948999943328049159021873821254267471067523609151007885131921896462161216356454116929796355815756642621369974260365378070336290542971599886325232821981080341858950609157813769416455337935096696635623426418166316737131174435618543058086342714723330814586496030805366321181723292731710369013923285787724941830672247377301048663929453294620044701627159066468762709113137517559435822623284148112827473010030736329596829357275518641576798298066541516764673029908084962144713

phi = p**(2-1)*(p-1)*q**(3-1)*(q-1)*r**(5-1)*(r-1)*s**(7-1)*(s-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

九、维纳攻击

脚本：

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
# 维纳攻击
import gmpy2
import primefac
from Crypto.Util.number import *

def transform(x,y):       #使用辗转相处将分数 x/y 转为连分数的形式
    res=[]
    while y:
        res.append(x//y)
        x,y=y,x%y
    return res
    
def continued_fraction(sub_res):
    numerator,denominator=1,0
    for i in sub_res[::-1]:      #从sublist的后面往前循环
        denominator,numerator=numerator,i*numerator+denominator
    return denominator,numerator   #得到渐进分数的分母和分子，并返回

    
#求解每个渐进分数
def sub_fraction(x,y):
    res=transform(x,y)
    res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res)))))  #将连分数的结果逐一截取以求渐进分数
    return res

def get_pq(a,b,c):      #由p+q和pq的值通过维达定理来求解p和q
    par=gmpy2.isqrt(b*b-4*a*c)   #由上述可得，开根号一定是整数，因为有解
    x1,x2=(-b+par)//(2*a),(-b-par)//(2*a)
    return x1,x2

def wienerAttack(e,n):
    for (d,k) in sub_fraction(e,n):  #用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if k==0:                     #可能会出现连分数的第一个为0的情况，排除
            continue
        if (e*d-1)%k!=0:             #ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
            continue
        
        phi=(e*d-1)//k               #这个结果就是 φ(n)
        px,qy=get_pq(1,n-phi+1,n)
        if px*qy==n:
            p,q=abs(int(px)),abs(int(qy))     #可能会得到两个负数，负负得正未尝不会出现
            d=gmpy2.invert(e,(p-1)*(q-1))     #求ed=1 (mod  φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
            return d
    print("该方法不适用")
    
c = 
e = 
n = 
d=wienerAttack(e,n)
print("d=",d)
m = pow(c,d,n)
print("flag = ",long_to_bytes(m))

十、p高位泄露

代码公式

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
# SageMath 代码：已知 p 的高位，恢复完整的 p（Coppersmith 方法）

# 输入参数
n = 
p_high = 
p_total_bits =   
# p 的总位数（RSA-1024 则设为 512，RSA-2048 则设为 1024）

# ------------------ 计算未知低位位数 ------------------
kbits = p_total_bits - p_high.nbits()  # p_high.nbits() 返回已知高位的位数
print(f"[*] 已知 p 的高位位数: {p_high.nbits()}")
print(f"[*] 未知 p 的低位位数: {kbits}")

# ------------------ 构造多项式方程 ------------------
# 设 p = p_high << kbits + x，其中 x 是未知的低位部分
# 目标是找到 x，使得 p | n（即 p 是 n 的因子）

# 定义多项式环（在模 n 下）
PR.<x> = PolynomialRing(Zmod(n))

# 构造方程：f(x) = (p_high << kbits) + x
p_high_shifted = p_high << kbits
f = x + p_high_shifted

# ------------------ 使用 Coppersmith 方法求解小根 x ------------------
# X = 2^kbits 是 x 的上界
# beta = 0.4 是调整参数（如果失败，可以尝试 0.3~0.5）
roots = f.small_roots(X=2^kbits, beta=0.4)

if not roots:
    print("[!] 未能找到解，尝试调整 beta 或检查输入位数是否足够")
else:
    x0 = roots[0]
    print(f"[+] 找到解 x0 = {x0}")

    # 恢复完整的 p
    p = p_high_shifted + x0
    print(f"[+] 恢复的 p = {hex(p)}")

    # 验证 p 是否确实是 n 的因子
    if n % p == 0:
        print("[✓] 验证成功：p 是 n 的因子")
        q = n // p
        print(f"[+] 对应的 q = {hex(q)}")
    else:
        print("[!] 验证失败：恢复的 p 不是 n 的因子，请检查输入或调整参数")

[CISCN2021]

Sage 运行：Sage Cell Server

题干

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
from flag import text,flag
import md5
from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime

assert md5.new(text).hexdigest() == flag[6:-1]

msg1 = text[:xx]
msg2 = text[xx:yy]
msg3 = text[yy:]

msg1 = bytes_to_long(msg1)
msg2 = bytes_to_long(msg2)
msg3 = bytes_to_long(msg3)

p1 = getPrime(512)
q1 = getPrime(512)
N1 = p1*q1
e1 = 3
print pow(msg1,e1,N1)
print (e1,N1)

p2 = getPrime(512)
q2 = getPrime(512)
N2 = p2*q2
e2 = 17
e3 = 65537
print pow(msg2,e2,N2)
print pow(msg2,e3,N2)
print (e2,N2)
print (e3,N2)

p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200

1
2
3
4
5
6
7
8
9
10
11
out:
19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
(3, 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009L)
54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
(17, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L)
(65537, 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977L)
59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
(65537, 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147L)
7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902

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 *
from gmpy2 import *
from hashlib import *
c1 = 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
e1 = 3
n1 = 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009

c2 = 54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
c3 = 91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950
e2 = 17
n2 = 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
e3 = 65537

c4 = 59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
n3 = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p3200 = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
#Part1
m1 = iroot(c1,e1)[0]
print(m1)
#Part 2
d,x,y = gcdext(e2,e3)
m2 = pow(c2,x,n2)
m3 = pow(c3,y,n2)
m0 = (m2*m3)%n2
print(m0)

#Part3

p3 = int("0xda5f14bacd97f5504f39eeef22af37e8551700296843e536760cea761d334508003e01b886c0c69b4365759fb42a3faaf0c8888106bb9dbb1137769a37d191a7",16)
q3 = n3//p3
phi = (p3-1)*(q3-1)
d3 = inverse(e3,phi)
m4 = pow(c4,d3,n3)
print(m4)
flag = long_to_bytes(m1)+long_to_bytes(m0)+long_to_bytes(m4)

m = "NSSCTF{"+ md5(flag).hexdigest() + "}"
print(m)

利用sagemath恢复P

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
# SageMath 代码：已知 p 的高位，恢复完整的 p（Coppersmith 方法）

# 输入参数
n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
p_high = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
p_total_bits = 512  # p 的总位数（RSA-1024 则设为 512，RSA-2048 则设为 1024）

# ------------------ 计算未知低位位数 ------------------
kbits = p_total_bits - p_high.nbits()  # p_high.nbits() 返回已知高位的位数
print(f"[*] 已知 p 的高位位数: {p_high.nbits()}")
print(f"[*] 未知 p 的低位位数: {kbits}")

# ------------------ 构造多项式方程 ------------------
# 设 p = p_high << kbits + x，其中 x 是未知的低位部分
# 目标是找到 x，使得 p | n（即 p 是 n 的因子）

# 定义多项式环（在模 n 下）
PR.<x> = PolynomialRing(Zmod(n))

# 构造方程：f(x) = (p_high << kbits) + x
p_high_shifted = p_high << kbits
f = x + p_high_shifted

# ------------------ 使用 Coppersmith 方法求解小根 x ------------------
# X = 2^kbits 是 x 的上界
# beta = 0.4 是调整参数（如果失败，可以尝试 0.3~0.5）
roots = f.small_roots(X=2^kbits, beta=0.4)

if not roots:
    print("[!] 未能找到解，尝试调整 beta 或检查输入位数是否足够")
else:
    x0 = roots[0]
    print(f"[+] 找到解 x0 = {x0}")

    # 恢复完整的 p
    p = p_high_shifted + x0
    print(f"[+] 恢复的 p = {hex(p)}")

    # 验证 p 是否确实是 n 的因子
    if n % p == 0:
        print("[✓] 验证成功：p 是 n 的因子")
        q = n // p
        print(f"[+] 对应的 q = {hex(q)}")
    else:
        print("[!] 验证失败：恢复的 p 不是 n 的因子，请检查输入或调整参数")