首页 > itarticle > hackcon 2017 rsa-3 writeup

hackcon 2017 rsa-3 writeup

admin 11月 12, 2020 0

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


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!

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能