문제

RSA - 2 50

No p,q this time. LOL, what will you do now?

n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381

e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205

c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635

풀이

e가 크면 우선 wiener 방법을 돌려본다. 럭키!

wiener attack

 wieners-attack python3 wiener.py 
[+] Found the continued fractions expansion convergents of e/N.
[+] Iterating over convergents; Testing correctness through factorization.
[+] ...
[+] Factored N! :) derived keypair components:
[+] ++ SHA1(e):     3536a853c5b47f3dcf6d8a399c5e135f91a5a3c9
[+] ++      d :     21780352155588618020563641971337344243907391969899764877790673891831527301137
[+] ++ SHA1(d):     adfb9d8325e4bf11a3c118908225bdd9dd2773bf
[+] ++ SHA1(N):     b64dba5bdcff031d80b826196507ccf02da4d83a
[+] ++      p :     10114792273660656874618568712406420344176220457790563178092222929337786916374923318745284718351487926620784106195715878875311958793629905453919697155685507
[+] ++ SHA1(p):     6871a43c4f96cbe8e59937c0924d3b8f63be5b57
[+] ++      q :     10843221374140991753173625949764386011485161421520044246309105053489500519257941272796681417497061734054081478280518835582353321569961722963922828311576983
[+] ++ SHA1(q):     d5d021413e968ba2904d7cb273fb3b661ee14f77
[+] ++ SHA1(phiN):  483e6cee191447e1cd694a028e7aa3a6a8b469cc

찾은 d로 복호화 한다.

n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381

e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205

c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635

d = 21780352155588618020563641971337344243907391969899764877790673891831527301137

m = pow(c, d, n)
print hex(m)[2:-1].decode("hex")

d4rk{1_70ld_y0u_th15_would_8e_more_difficult}c0de