题目程序
1 | #!/usr/bin/python |
程序分析
一共3个选项:1
2
3print "1. regenerated the key"
print "2. get public key"
print "3. get encrypted flag"
选项1:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29def auth():
global secret
print "Give me your username"
sys.stdout.flush()
username = raw_input()
username = username.rstrip("\n")
print "Give me your token"
sys.stdout.flush()
token = raw_input()
token = token.rstrip("\n")
if md5(secret+username).hexdigest() != token:
print "Token error!"
sys.stdout.flush()
return 0
elif username.find("root")>=0:
return 1
else:
print "Permission deny!"
sys.stdout.flush()
return 0
def regen_key():
global phi_n,e,d
print "e =",e
print "d =",d
print "The value above will be abondanded!"
sys.stdout.flush()
e = getPrime(16)
d = invmod(e, phi_n)
容易想到这里应该是一个hash长度拓展攻击
因为secret是我们已知长度,不知具体的salt
而secret+username我们已知知道了secret+guest的md5
所以我们可以利用hashpump进行攻击,从而成为root,得到第一组e和d
然后选项2:1
2print "n =",n
print "e =",e
可以给出重新生成的n和e
然后选项3:1
2
3
4
5
6def print_flag_enc():
global e,n,d
flag = read_flag()
flag_long=bytes_to_long(flag)
flag_enc=pow(flag_long,e,n)
print "flag_enc =",flag_enc
可以给出第二轮生成的e和n得到的密文
程序攻击
首先我们确定一下思路:
先得到第一轮的e和d,再得到第二轮重新生成的e和不变的n,最后获取flag
所以我们首先进行hash长度拓展攻击
这里我们选择pwntools与题目进行交互1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16from pwn import *
from hashpumpy import *
p=remote('106.75.98.74
',10030)
p.recvuntil('This is your token: ')
h=p.recvline().strip()
a=hashpump(h,'guest','root',8)
p.recv()
p.sendline('1')
p.recv()
p.sendline(a[1])
p.recv()
p.sendline(a[0])
print p.recv()
p.interactive()
可以容易得到第一组e和d1
2e = 40213
d = 7500700469928887286518458227664699159278535487520757641922238090199917409016343569173939993906922756556831035504721854231002147097871069085579605909683755970246918670465100763853106096318395019569333288936689100858056883923422787373585911487853097453104638315266112565971841143733065838415785677352565366518286696159642641689659349714647415916777285391063620441166105432812587414551700794114394465506916507947677896007952395030521123001124229725209405882460927276297059921329305310826295983712199378473680414182815794064434492991619912020752957362646533601970102561949600259252301371098109684898098632567518246029061
然后获取不变的n和第二轮的e:1
2n = 16524717470949999696091971769521752440260107793769365422375442958484045294952841940896929215744211078147145479140490874058581566934021218492215673721914911457379024844979625103644603925450699551960861203528794105780148001600427357073029653134336087650342235280326312639863345637042556103665917352949033642897308785366329872282202458250082221058049458136595784478449079400726888282283678741404349251932226122657413860087195339718695834408124378779278152097697039166079786373183546878203429827668279703612664272707566842472777033850849491863616969677973480717909379202648999260739897757062596992962034283964483339890331
e = 51713
最后是密文:1
c=14393216781722178003306512831950927649138730534659938473432658453893579089181643910227146230219873790364049290575161577576737668749258349821047730143664996540304846267849691627722700417655460486917490004775172766040499375305064669817859170100795609015892650599502208001994020595343601282023820768649108270834062429381494838401660862935250942907635115481123369593205062636738018108000462370324278749923060060752122371413390939737682554633793909003693581999343058203409653003990465873405008587925422815425152341277900009601352181012736488572123959271273718435444053362323902987467288142530197426611139316340183388954578
然后问题来了,如果用已知的n,e,d去得到p和q
这里我一开始思考了一下:
我们可以知道1
2
3
4
5d = e^-1 mod phi_n
所以我们容易得到
d*e = 1 mod phi_n
即
d*e-1|phi_n
所以我们可以分解d*e-1
,他必有因素是phi_n,得到phi_n后我们就可以得到第二轮的d
但是由于分解的因素过多,直接排列组合配对出phi_n就很痛苦
所以这里有一个很好的算法:1
https://www.di-mgt.com.au/rsa_factorize_n.html
可以很好的帮我们解决问题
算法实现: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
40import random
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
def getpq(n, e, d):
p = 1
q = 1
while p == 1 and q == 1:
k = d * e - 1
g = random.randint(0, n)
while p == 1 and q == 1 and k % 2 == 0:
k /= 2
y = pow(g, k, n)
if y != 1 and gcd(y - 1, n) > 1:
p = gcd(y - 1, n)
q = n / p
return p, q
def main():
n = 16524717470949999696091971769521752440260107793769365422375442958484045294952841940896929215744211078147145479140490874058581566934021218492215673721914911457379024844979625103644603925450699551960861203528794105780148001600427357073029653134336087650342235280326312639863345637042556103665917352949033642897308785366329872282202458250082221058049458136595784478449079400726888282283678741404349251932226122657413860087195339718695834408124378779278152097697039166079786373183546878203429827668279703612664272707566842472777033850849491863616969677973480717909379202648999260739897757062596992962034283964483339890331
e = 40213
d = 7500700469928887286518458227664699159278535487520757641922238090199917409016343569173939993906922756556831035504721854231002147097871069085579605909683755970246918670465100763853106096318395019569333288936689100858056883923422787373585911487853097453104638315266112565971841143733065838415785677352565366518286696159642641689659349714647415916777285391063620441166105432812587414551700794114394465506916507947677896007952395030521123001124229725209405882460927276297059921329305310826295983712199378473680414182815794064434492991619912020752957362646533601970102561949600259252301371098109684898098632567518246029061
p, q = getpq(n, e, d)
print p
print q
if __name__ == '__main__':
main()
可以得到p和q:1
2p = 116803972359246830950002720138413077148113956408220776890535345803005303891268315330897200540246172887169335591551592243064609663151911089959259139601097749649631698099961451191394321447353119887438164810634953619671204382075221416442255785950963637188549460847726333017672845807932145101586045638150628232999
q = 141473933952570870291987109677740142115118495048607431322824021521561294210766639642610839458071357533353534950484614107837113133499907017656928417943568186729082488790080005204231835973916579530731477122069042925690924156112706754053655741356596095895117019307476005281377103443987986040076775474329685986669
然后就很简单了,直接可以得到flag1
2
3
4
5
6
7
8n = 16524717470949999696091971769521752440260107793769365422375442958484045294952841940896929215744211078147145479140490874058581566934021218492215673721914911457379024844979625103644603925450699551960861203528794105780148001600427357073029653134336087650342235280326312639863345637042556103665917352949033642897308785366329872282202458250082221058049458136595784478449079400726888282283678741404349251932226122657413860087195339718695834408124378779278152097697039166079786373183546878203429827668279703612664272707566842472777033850849491863616969677973480717909379202648999260739897757062596992962034283964483339890331
c = 14393216781722178003306512831950927649138730534659938473432658453893579089181643910227146230219873790364049290575161577576737668749258349821047730143664996540304846267849691627722700417655460486917490004775172766040499375305064669817859170100795609015892650599502208001994020595343601282023820768649108270834062429381494838401660862935250942907635115481123369593205062636738018108000462370324278749923060060752122371413390939737682554633793909003693581999343058203409653003990465873405008587925422815425152341277900009601352181012736488572123959271273718435444053362323902987467288142530197426611139316340183388954578
e = 51713
p=141473933952570870291987109677740142115118495048607431322824021521561294210766639642610839458071357533353534950484614107837113133499907017656928417943568186729082488790080005204231835973916579530731477122069042925690924156112706754053655741356596095895117019307476005281377103443987986040076775474329685986669
q=116803972359246830950002720138413077148113956408220776890535345803005303891268315330897200540246172887169335591551592243064609663151911089959259139601097749649631698099961451191394321447353119887438164810634953619671204382075221416442255785950963637188549460847726333017672845807932145101586045638150628232999
d = modinv(e,(p-1)*(q-1))
m = fastExpMod(c,d,n)
print hex(m)
flag:flag{Do_you_think_change_e_d_means_change_the_key?}
总结
CTF还真是每次打RSA都有不同的套路,这次是根据已有的n,d,e去分解p,q,真的是又涨知识了……
还有神奇的pwntools,是不是我该考虑转pwn了?或者写写socket?233333333333