HeartSky's blog


在渗透之路上渐行渐远


HackCon 2017 RSA-3 writeup

I was finally able to capture the modulos and ciphertext that my friend uses to send the flag to everyone. Please hack it, and tell me what he is sending.
Note: Different flag format.

rsa3.txt

We are giving following data:

1
2
3
4
n = 27889790942966947036861378043158080483040875117204641483879866390238208620663956576973777874507240669643888065763137780499805909939066661612708826993608654680300732401951416830721424144957953976708056088725541261145598655543913301108486073727361975257751155861693187124732625567462532590982339774968025316953820269111867532777587735148492283985886531900163665810672858631477638383286430874438461463017230692713981299647992939576135711541276805459680629858238737522674183159028538781619179277007783213596156511625151052311022548741688444363119109174839265715141719292947895928622131533978133711731642378245705631956649
ciphertext = 27565432352959169185267553837899918221071526625835688441598442671911411122049381510509743510890496110212243616256779662952985804971850105832078504709537095259376624037980191442815236496206629132445698638752008471224630238657804976392808705657174518751058814995018236045588302953757877948476094692393461773107162692398429932051387701451649957934778348969875044313103315581471155771861778522866249975693209102641771607970433761749835749459436417356404889295590430882236042943244986093685207061420612079333415995591395030262118706403057290219600617207992171928187137731325872336342093957597097019557095193031636012448452

......

That have 1000 group of n and c, so many!
Firstly, I think that could have the same factor. But failed. All n are relatively prime. Stuck! I am no idea. So I begin to do other things.

Suddenly I’m aware of that if e are same(should be same), it might be done by Chinese remainder theorem. You can understand it at wiki, I will not explain it. But no e, don’t worry, we can blast it. So I write a python script to solve the challenge.

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

# get all n and c
s = open('file.txt').read().split('\n')
num = 0
n = []
c = []
for i in range(len(s)):
if num % 3 == 0:
n.append(int(s[i].split(' ')[2]))
elif num % 3 == 1:
c.append(int(s[i].split(' ')[2]))
num += 1
le = len(n)

# calc N
N = 1
for num in n:
N *= num

# N1,N2...Nn
# NN1 * t1 = 1 (mod n1)
NN = [None] * le
t = [None] * le
x = 0
for i in range(le):
NN[i] = N / n[i]
t[i] = gmpy2.invert(NN[i],n[i])
x += c[i]*t[i]*NN[i]

res = x % N
for i in range(2, 65537):
num = 0
try:
flag = long_to_bytes(gmpy2.iroot(res,i)[0])
for j in flag:
if j not in string.printable:
num = 1
break
if num == 0:
print 'e is ' + str(i)
print flag
except:
continue

Although flag isn’t standard format, we can print all the printable message.

Nice!