TimisoaraCTF2018-NotYourAverageRSA

Question

1
2
c: 20318623659277133784436863405159350994457887674343039464217662595169547155252162707757860373904591558880102908865139317161642898188843552485749556428171374190436116308993843078746618097974105761149153341729931060530612128761115767471801348290177493316532913006382242873832659641556157675014368433683567068217
n: 134907508240262137946502074360739103059110939023118055674568339675274978708216465550239395185797633495974788047880328560410956605895894497803797294715631963939546472939054512693762329563642230731635928665937542607055460883018173012233396950213422702996807273870440698007181387418977498579818700406673368084937

Solution

直接將 n 扔上factordb發現好多prime

1
42125267 · 49833439 · 58693039 · 61513877 · 167006983813971973935755769744287313795624064948679838624701034583661551637974040070265964882467867666872657483049263378360657863549 · 106580625826530329045051134241813132858137977273664192502334106456384150414405388669523053631392655455506681541904952100571943163465502692906512867

醒起有樣野好似叫做 MPRSA (Multi Prime RSA)
但係佢好似無比 e 喎 , 咁是但塞住個65537落去試試先

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
import gmpy

def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)

    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * gmpy.invert(p, n_i) * p
    return sum % prod

c = 20318623659277133784436863405159350994457887674343039464217662595169547155252162707757860373904591558880102908865139317161642898188843552485749556428171374190436116308993843078746618097974105761149153341729931060530612128761115767471801348290177493316532913006382242873832659641556157675014368433683567068217

n = 134907508240262137946502074360739103059110939023118055674568339675274978708216465550239395185797633495974788047880328560410956605895894497803797294715631963939546472939054512693762329563642230731635928665937542607055460883018173012233396950213422702996807273870440698007181387418977498579818700406673368084937

e = 65537

primes = [
    42125267,
    49833439,
    58693039,
    61513877,
    167006983813971973935755769744287313795624064948679838624701034583661551637974040070265964882467867666872657483049263378360657863549,
    106580625826530329045051134241813132858137977273664192502334106456384150414405388669523053631392655455506681541904952100571943163465502692906512867]

n_ary = []
a_ary = []
for p in primes:
    phi = p - 1
    d = gmpy.invert(e, phi)
    mk = pow(c, d, p)
    n_ary.append(p)
    a_ary.append(mk)

m = chinese_remainder(n_ary, a_ary)
flag = ('%x' % m).decode('hex')
print flag