Fork me on GitHub

Whitzard-CTF_RSA

2018.7.29:在二进制训练营的时候做了下复旦OJ上的rsa,差一个level3没搞出来,这里记录一下脚本

2018.7.30:level3解出


0x00 level0_all_give_you

题目给了p,q,n,e,c,直接解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/python
# -*- coding: utf-8 -*-
__Author__ = "L1B0@10.0.0.55"

from libnum import n2s,s2n
import gmpy2

p=6224751407196587

q=7943494850559647

e=65537

N=49446280749080005222860298324789

cipher=18445170944028011076605277003494

m = (p-1)*(q-1)

d = gmpy2.invert(e,m)

flag = n2s(pow(cipher,d,N))
print flag


0x01 level1_factor_N

在线分解N即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/python
# -*- coding: utf-8 -*-
__Author__ = "L1B0@10.0.0.55"

from libnum import n2s,s2n
import gmpy2

e=65537
N=578901120681462344392977129803201
cipher=129662878945371130040081904349606

#facotrize
p = 809
q = 715576168951127743378216476889

m = (p-1)*(q-1)

d = gmpy2.invert(e,m)

flag = n2s(pow(cipher,d,N))
print flag


0x02 level2_e=3

低加密指数攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/python
# -*- coding: utf-8 -*-
__Author__ = "L1B0@10.0.0.55"

from gmpy2 import iroot
from libnum import n2s

e=3
n=1644116071238440794835968435021522925333145828466704580586342018443583533528696283940813360961939555816101473973555088162098477
c=874548130355489823053470195390273835709184088374326753413151756170831483190524376329024877919019666940077812490613442032246774

i = 0
while True:
if iroot(c + i * n, 3)[1] == True:
print "Success!"
print iroot(c + i * n, 3)
break
i += 1

print n2s(8663725283768549127679518803938707801269629L)


0x03 level3_e=33

Solved at 2018.7.29 17:30pm

这道题很有意思,e=33,直接求逆元是求不出来的,如下图

求解推导

我们知道 ( flag ** e ) mod N == cipher,这里e = 33

那么将e分解,e = e1*e2 = 3*11

故{ ( flag ** e1 ) ** e2 } mod N == cipher,即 { ( flag ** 3 ) ** 11 } mod N == cipher

第一步

按照level0的思路,我们可以直接把flag**3当做一个新的明文flag1

e2 = 11

N2 = N

p2 = p

q2 = p

cipher2 = cipher

直接解出flag1

第二步

然后出了一点问题:直接对flag1开三次方,发现无解。

后来发现我这里算出来的flag1是一定小于N的,而flag**3不一定小于N。

也就是说 ( flag**3 ) mod N = flag1

这里又是一组rsa,并且e=3,那直接低加密指数攻击即可。

e1 = 3

N1 = N

cipher1 = flag1

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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
__Auther__ = 'L1B0'

from libnum import n2s,s2n
import gmpy2
from z3 import *

e=33
p=954147044541943113765937481348204894039415441663225351583
q=1343515508931258195091391392918235484113725429556823769736956904341937
N=1281911352143024584350260661717626471379161729718150347407768402523661151300375453147248077816866067782874939959917466076236271
cipher=1197113886220503890500226974976842298261128760760143948519182172387778320755699233509310951033610880543097406233423486693032107

m = (p-1)*(q-1)
#print 'm = {}'.format(m)

#(flag**3)**11 mod N == cipher
#flag1 = flag**3

e1 = 11
m1 = m
d1 = gmpy2.invert(e1,m1)
#print d1

flag1 = pow(cipher,d1,N)
#print pow(flag1,e1,N) == cipher
print flag1

#e=3
n = N
c = flag1
i = 0
while True:
if gmpy2.iroot(c + i * n, 3)[1] == True:
print "Success!"
print gmpy2.iroot(c + i * n, 3)
break
i += 1

print n2s(8663725283690131533285369823529813978998141)
#flag = n2s(pow(cipher,d,N))
#print flag

一个小技巧:大数分解可以用gmpy2.iroot()


0x04 level4_wiener_attack

wiener_attack脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/python
# -*- coding: utf-8 -*-
__Author__ = "L1B0@10.0.0.55"

from libnum import n2s
import gmpy2

e=160222447153262895889250928158012827757109871196102040037421857250766491575699886894325697077956068896677359953037375582060511979328323570880578946073240834317364119936983046746942944368567355131867682895196198904859001202051459879133425754080440276218324680838480108302184726980362910704693149535052743526713
n=356096033429997161372356441930246707554046995590506452306084931488519008238592151695866774341246347160182054216879883209187019942641996111166252052256475412435016177136773967956292472785118669272929844214105480922945372638910276569650465033695573697459823872295312452877368652943145314840314022954151337366463
cipher=81734547217423194200627584129880698303540239605864202915000885082303608683684019444597240499822470812273165739947662626400159428633441652507543459604648534096971317225195148800012614358689629135280756866839465060038852820973512256929393244791492926888258798803335090942130962336363237126444758225836896001850

#wiener_attack
d = 731297

print n2s(pow(cipher,d,n))


0x05 level5_Common_Modulus_Attack

共模攻击

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
#!/usr/bin/python
# -*- coding: utf-8 -*-
__Author__ = "L1B0@10.0.0.55"

import sys
from libnum import n2s
import gmpy2

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m

n = 67429986223463725630760851214095205122861566712757096290156130852775779636888134368717091439692391485149944760480157303572754994563434765296623953452761257431107573064032023044818486821895477023173750051598133603675847214577862821214777097737040107831560275593671162948631151791

e1 = 61967635785437322652331201078567365048930922666568441115110461719490654534113
e2 = 205766126176929848227168949492841490531179790972829078582852699147634573122171458527896514644790639038940007774239040950019816134072019031167

c1 = 5822762981879944424561473864620287634409555456758877462439567398879989944707712816448957643839287371123037868433108662054545710675854869153861985791456418794257498996377335090618281582018030521712938036930671348275101114834456069272996599241973297974161300649826701817737861423L
c2 = 705997633009417848857145957952988147669825773624353180591567961488716033203631101756073664193075066102031563449119189790932235272762840949103671277483248720788931071047154630535727579468256892221981227270895827194426781684443499389831949250120695006941674077440102842342282716L


s = egcd(e1,e2)
s1 = s[1]
s2 = s[2]
print s1,s2

if s1 < 0:
s1 = -s1
c1 = modinv(c1,n)
if s2 < 0:
s2 = -s2
c2 = modinv(c2,n)

print c1,c2
m = (pow(c1,s1,n)*pow(c2,s2,n)) % n
print(n2s(m))