Sky's blog

上海赛的RSA研究

Word count: 1,308 / Reading time: 7 min
2017/11/05 Share

题目程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#!/usr/bin/python 
from hashlib import md5
from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from libnum import invmod
from os import urandom
import random
import sys
def 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 welcome():
global secret
#secret="hahahaha"
md5obj=md5()
md5obj.update(secret+"guest")
token=md5obj.hexdigest()
print "Welcome to RRRSA world!"
print "This is your token:",token
sys.stdout.flush()


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)

def read_flag():
f=open("./flag")
return f.readline()
f.close()

def 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

def read_int():
try:
x = raw_input()
x = int(x)
return x
except ValueError:
return -1

def option():
print "There are some options for you!"
print "1. regenerated the key"
print "2. get public key"
print "3. get encrypted flag"
print "Option:"
sys.stdout.flush()
return read_int()
len_n=2048
secret=urandom(8)
p = getPrime(len_n/2)
q = getPrime(len_n/2)

n = p * q
phi_n = (p-1) * (q-1)
e = getPrime(16)
d = invmod(e, phi_n)




welcome()

for i in range(3):
op=option()
if op==1:
if auth():
regen_key()
elif op==2:
print "n =",n
print "e =",e
sys.stdout.flush()

elif op==3:
print_flag_enc()
sys.stdout.flush()
break
else:
print "Wrong Option"
sys.stdout.flush()

程序分析

一共3个选项:

1
2
3
print "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
29
def 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
2
print "n =",n
print "e =",e

可以给出重新生成的n和e
然后选项3:

1
2
3
4
5
6
def 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
16
from 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和d

1
2
e = 40213
d = 7500700469928887286518458227664699159278535487520757641922238090199917409016343569173939993906922756556831035504721854231002147097871069085579605909683755970246918670465100763853106096318395019569333288936689100858056883923422787373585911487853097453104638315266112565971841143733065838415785677352565366518286696159642641689659349714647415916777285391063620441166105432812587414551700794114394465506916507947677896007952395030521123001124229725209405882460927276297059921329305310826295983712199378473680414182815794064434492991619912020752957362646533601970102561949600259252301371098109684898098632567518246029061

然后获取不变的n和第二轮的e:

1
2
n = 16524717470949999696091971769521752440260107793769365422375442958484045294952841940896929215744211078147145479140490874058581566934021218492215673721914911457379024844979625103644603925450699551960861203528794105780148001600427357073029653134336087650342235280326312639863345637042556103665917352949033642897308785366329872282202458250082221058049458136595784478449079400726888282283678741404349251932226122657413860087195339718695834408124378779278152097697039166079786373183546878203429827668279703612664272707566842472777033850849491863616969677973480717909379202648999260739897757062596992962034283964483339890331
e = 51713

最后是密文:

1
c=14393216781722178003306512831950927649138730534659938473432658453893579089181643910227146230219873790364049290575161577576737668749258349821047730143664996540304846267849691627722700417655460486917490004775172766040499375305064669817859170100795609015892650599502208001994020595343601282023820768649108270834062429381494838401660862935250942907635115481123369593205062636738018108000462370324278749923060060752122371413390939737682554633793909003693581999343058203409653003990465873405008587925422815425152341277900009601352181012736488572123959271273718435444053362323902987467288142530197426611139316340183388954578

然后问题来了,如果用已知的n,e,d去得到p和q
这里我一开始思考了一下:
我们可以知道

1
2
3
4
5
d = 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
40
import 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
2
p = 116803972359246830950002720138413077148113956408220776890535345803005303891268315330897200540246172887169335591551592243064609663151911089959259139601097749649631698099961451191394321447353119887438164810634953619671204382075221416442255785950963637188549460847726333017672845807932145101586045638150628232999
q = 141473933952570870291987109677740142115118495048607431322824021521561294210766639642610839458071357533353534950484614107837113133499907017656928417943568186729082488790080005204231835973916579530731477122069042925690924156112706754053655741356596095895117019307476005281377103443987986040076775474329685986669

然后就很简单了,直接可以得到flag

1
2
3
4
5
6
7
8
n = 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

CATALOG
  1. 1. 题目程序
  2. 2. 程序分析
  3. 3. 程序攻击
  4. 4. 总结