题目均来源CTF

通过了解CTF中常见和以前奇葩题型，有助于我们学习更多的内容

关于rsa的一些基础知识之前就有写过啦，这篇直接开始做题 O(∩_∩)O

已知p,q,e 求d

题目RSA如下

直接带入即可

1
2
3
4
5
6
7
import gmpy2
p=473398607161
q=4511491
e=17
fai=(p-1)*(q-1)
d=gmpy2.invert(e,fai)
print('d=',d)

输出结果

1
d= 125631357777427553

所以答案套个flag{}

1
flag{125631357777427553}

已知p,q,e,c 求m

题目rsarsa如下

2

求解，比上一题多一个步骤而已

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2

p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

n=p*q
fai=(p-1)*(q-1)
d=gmpy2.invert(e,fai)
m=pow(c,d,n)
print('m=',m)

输出结果

1
m= 5577446633554466577768879988

所以答案是

1
flag{ 5577446633554466577768879988}

已知p,q,dp,dq,c 求m

题目RSA1如下

1
2
3
4
5
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

对新出现的dp，dq先来分析一下，直接手写了hhh

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
import libnum

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

niyuan=gmpy2.invert(p,q)
n=p*q
mp=pow(c,dp,p)
mq=pow(c,dq,q)

m=(((mp-mq)*niyuan % p)*q+mq)%n


print('m=',m)
hex_m=hex(m)
print(hex_m)
import binascii
mingwen= binascii.unhexlify('6e6f784354467b57333163306d335f37305f4368316e343730776e7d')
print(mingwen)

输出结果

1
2
3
m= 11630208090204506176302961171539022042721137807911818876637821759101 
0x6e6f784354467b57333163306d335f37305f4368316e343730776e7d 
b'noxCTF{W31c0m3_70_Ch1n470wn}'

所以答案

1
flag{W31c0m3_70_Ch1n470wn}

总结

1、关系公式：dp≡dmod(p-1),dq≡dmod(q-1)

2、mp=pow(c,dp,p)，mq=pow(c,dq,q)

3、推出 m=(((mp-mq)niyuan % p)q+mq)%n

已知e,n,dp.c 求m

题目

1
2
3
4
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

分析一波只含dp的情况

现在来解题

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

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751


for x in range(1,e):          #在(1,e)中遍历取一个数x

  if (dp*e-1)%x==0:           

​    if n%(((dp*e-1)//x)+1) == 0:   #存在p，使得n能被p整除
​       p=((dp*e-1)//x)+1           #求p
​       q=n//p                      #求q
​       fai=(p-1)*(q-1)             
​       d=gmpy2.invert(e,fai)      
​       m=pow(c,d,n)                

print('m=',m)
hex_m=hex(m)
print(hex_m)
import binascii 
mingwen= binascii.unhexlify('666c61677b776f775f6c65616b696e675f64705f627265616b735f7273613f5f39383932343734333530327d')
print(mingwen)

输出结果为

1
2
3
m= 3670434958110785066911905751469631231338751225710158680692616521935747246580688484040488309932916523151997 
0x666c61677b776f775f6c65616b696e675f64705f627265616b735f7273613f5f39383932343734333530327
d b'flag{wow_leaking_dp_breaks_rsa?_98924743502}'

因此答案为

1
flag{wow_leaking_dp_breaks_rsa?_98924743502}

总结

1、存在p的前提是，n要存在，所以 if (dp*e-1)%x==0:不能漏

2、存在的这个p,必须满足被n整除（%==0）

3、注意==和=区别，前者表等于，后者是赋值

已知c1,c2,e1,e2,n 求m

题目RSA3如下(共模攻击)

1
2
3
4
5
c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

原理

对于同一明文m，用同一模数n，不同指数e1，e2对其加密，因此c1和c2也是不同的。在这情况下已知n，c1,c2,e1,e2,就可以列出两个式子求得一个未知数m。

假设e1,e2互质，即gcd(e1,e2)=1,此时有e1s1+e2s2=1(s1,s2一正一负，且为整数)，在之前的数论提到过，这样可以求出一组解（s1,s2).假设s1为正数，s2为负数。

c1≡m^e1^ mod n,c2≡m^e2^ mod n

相乘c1c2≡m^(e1+e2)^mod n

因此 c1^s1^c2^s2^≡m^e1s1+e2s2^ mod n

所以 c1^s1^c2^s2^ ≡m mod n

等式变换后 m≡ c1^s1^c2^s2^ mod n

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import libnum   
import gmpy2    

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

s = gcdext(e1,e2)    #gmpy2.gcdext(),扩展欧几里得算法，返回tuple元组，满足s[1]*e1+s[2]*e2=1

m = pow(c1,s[1],n)*pow(c2,s[2],n)%n 

print(m)
hex_m=hex(m) #把m十进制数字转化成十六进制
print(hex_m)
import binascii
mingwen=binascii.unhexlify('666c61677b34396439313037376131616263623134663161396435343663383062653965667d')
print (mingwen)

输出结果即答案

1
flag{49d91077a1abcb14f1a9d546c80be9ef}

总结

1、gmpy2.gcdext(),扩展欧几里得算法，返回tuple元组，满足s[1]e1+s[2]e2=1

2、 m≡ c1^s1^c2^s2^ mod n，表示出s1,s2即可

已知flag.enc,pub.key 求m

将pub.key的后缀改为txt，打开

1
2
3
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMAzLFxkrkcYL2wch21CM2kQVFpY9+7+/AvKr1rzQczdAgMBAAE=
-----END PUBLIC KEY-----

之前写过一篇用虚拟机openssl命令解key的，后来发现在线网站也可以实现

SSL在线工具-公钥解析 (ssleye.com)

1
2
n=86934482296048119190666062003494800588905656017203025617216654058378322103517
e=65537

再分解n

1
2
p=285960468890451637935629440372639283459
q=304008741604601924494328155975272418463

后来我又get到一个方便的tool，可以直接计算d

1
d=81176168860169991027846870170527607562179635470395365333547868786951080991441
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
import rsa

e= 65537
n= 86934482296048119190666062003494800588905656017203025617216654058378322103517
p= 285960468890451637935629440372639283459
q= 304008741604601924494328155975272418463
d= 81176168860169991027846870170527607562179635470395365333547868786951080991441

key = rsa.PrivateKey(n,e,d,q,p)         
with open(r"C:\Users\Lenovo\Desktop\0eaf8d6c-3fe5-4549-9e81-94ac42535e7b (1)\flag.enc","rb") as f:  
    f = f.read()
    print(rsa.decrypt(f,key))

输出结果

1
b'flag{decrypt_256}

总结

1、with open("C:\Users\Lenovo\Desktop\0eaf8d6c-3fe5-4549-9e81-94ac42535e7b (1)\flag.enc","rb") as f: 行不通，就在open（“加个r

2、flag.enc的路径要复制完整

3、“rb”，表示读取

已知n,e,c 求m，且c为字符串

题目RSAROLL如下，有两个文件

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
#data.txt
{920139713,19}

704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148
1
2
3
4
5
#题目.txt
RSA roll！roll！roll！
Only number and a-z
（don't use editor
which MS provide）

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2

p=18443
q=49891
n=920139713
e=19
d = gmpy2.invert(e,(p-1)*(q-1))
flag = []
with open(r"C:\Users\Lenovo\Desktop\02c01a13-3a86-47de-8648-f03328a5e5d8 (1)\RsaRoll\data.txt") as f:
    f.readline() 
    f.readline()
    for i in f:
        flag.append(chr(pow(int(i),d,n)))
print("".join(flag))

输出

1
flag{13212je2ue28fy71w8u87y31r78eu1e2}

总结

1、 f.readline() 用于从文件读取整行，包括 “\n” 字符

已知n，c，e，且e=3，求m

题目 Dangerous RSA如下

1
2
3
4
#n:  0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
#e:  0x3
#c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
so,how to get the message?

思路

e=3，属于低加密指数攻击，存在以下两种情况

总的关系式：c=m^3^ mod n，c=kn+m^3^

1、如果明文m较小，导致m^3^<n,所以c=m^3^，所以m=c开3次方

2、如果明文m较大，导致m^3^>n,满足c=kn+m^3^，所以m=（c-kn）开3次方

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2 
import libnum
n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
e=3

k = 0
while 1:
    if(gmpy2.iroot(c+k*n,3)[1]==1):    
        print(gmpy2.iroot(c+k*n,3))
        break
    i=i+1
hex_m=hex(13040004482819713819817340524563023159919305047824600478799740488797710355579494486728991357)
print(hex_m)
import binascii
mingwen=binascii.unhexlify('666c61677b32356466386361663030366565356462393464343831343463333362326333627d')

print(mingwen)
1
2
3
(mpz(13040004482819713819817340524563023159919305047824600478799740488797710355579494486728991357), True)
0x666c61677b32356466386361663030366565356462393464343831343463333362326333627d
b'flag{25df8caf006ee5db94d48144c33b2c3b}'
1
flag{25df8caf006ee5db94d48144c33b2c3b}

总结

1、gmpy2.iroot指开根，gmpy2.iroot(81,2)，表示求大整数x=81开n=2次根，输出的结果是(mpz(9),True)

2、对k进行爆破，只要能开方成功就break，否则继续遍历