Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
35 lines (27 sloc) 5.66 KB

Close Encounter writeup

Let's try to factor n. Close can hint to the two primes being close, which makes it easy to factor.

$ python2 fermat.py 647580559066350764512574139212258654419619377791696792933162647847016182264786947024323483613445156926567953673211035865775396889491136493021394983865794529477091872229948860215774356455333826515720143910504339782998354975787558272036453370109286642626999091302012693562994565167763421804705602666440082138719409120664293876204553614511882382199434919365954997082834057119072868066696185230896273866269308019520562618860020221768639470528300841159704088859374399286986458302241337120121430937058280863472916553328255990461105886678126859657320418919609691089677744300138990131567897731188913573095161012997609872471436323858576012929455006921387033623358406327954425701649820631580290471076284227572599505740170534938538303275799383217459413578897504327360744415747939112249827320135553789275968404788584789483305709222531189435482276931098037440920811828069795012367922134191531348046137386595744872323763751900274523135348273825558806037832123609238684829315071013742451094194097286985647180549444633529585827947422469423955056342229557961062943802754823402381380268562309956425582717559687406317915547051766896665477764999756658000565784673316779579644624160889528487904071313946671365415309957045804828537561845474437630201414013
q: 25447604191089399379159931601501080444223112829447986750317096149517867285845804966271224749129184435412473271409883249120061873968316995978986208798525834614270065406921367971958806946394627934176702490478759393791972348471983612822611594685811932943967049526367295051671357595632868487646701478129716574546371021473575044516208082932409236271197813454910887142831892249406409490190907510457662553380813454668746280863597454887291739055374694568403834521593202067598993705171014838010676808696015931234887447378008864624871506336318997332815619367547971665857733583462023685385857017492039424076060074104480283423261
p: 25447604191089399379159931601501080444223112829447986750317096149517867285845804966271224749129184435412473271409883249120061873968316995978986208798525834614270065406921367971958806946394627934176702490478759393791972348471983612822611594685811932943967049526367295051671357595632868487646701478129716574546371021473575044516208082932409236271197813454910887142831892249406409490190907510457662553380813454668746280863597454887291739055374694568403834521593202067598993705171014838010676808696015931234887447378008864624871506336318997332815619367547971665857733583462023685385857017492039424076060074104480283422433

We get the primes almost instantly!

Now we have to compute phi and d, then we can decrypt the message.

import gmpy2
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse

q = 25447604191089399379159931601501080444223112829447986750317096149517867285845804966271224749129184435412473271409883249120061873968316995978986208798525834614270065406921367971958806946394627934176702490478759393791972348471983612822611594685811932943967049526367295051671357595632868487646701478129716574546371021473575044516208082932409236271197813454910887142831892249406409490190907510457662553380813454668746280863597454887291739055374694568403834521593202067598993705171014838010676808696015931234887447378008864624871506336318997332815619367547971665857733583462023685385857017492039424076060074104480283423261
p = 25447604191089399379159931601501080444223112829447986750317096149517867285845804966271224749129184435412473271409883249120061873968316995978986208798525834614270065406921367971958806946394627934176702490478759393791972348471983612822611594685811932943967049526367295051671357595632868487646701478129716574546371021473575044516208082932409236271197813454910887142831892249406409490190907510457662553380813454668746280863597454887291739055374694568403834521593202067598993705171014838010676808696015931234887447378008864624871506336318997332815619367547971665857733583462023685385857017492039424076060074104480283422433
n = 647580559066350764512574139212258654419619377791696792933162647847016182264786947024323483613445156926567953673211035865775396889491136493021394983865794529477091872229948860215774356455333826515720143910504339782998354975787558272036453370109286642626999091302012693562994565167763421804705602666440082138719409120664293876204553614511882382199434919365954997082834057119072868066696185230896273866269308019520562618860020221768639470528300841159704088859374399286986458302241337120121430937058280863472916553328255990461105886678126859657320418919609691089677744300138990131567897731188913573095161012997609872471436323858576012929455006921387033623358406327954425701649820631580290471076284227572599505740170534938538303275799383217459413578897504327360744415747939112249827320135553789275968404788584789483305709222531189435482276931098037440920811828069795012367922134191531348046137386595744872323763751900274523135348273825558806037832123609238684829315071013742451094194097286985647180549444633529585827947422469423955056342229557961062943802754823402381380268562309956425582717559687406317915547051766896665477764999756658000565784673316779579644624160889528487904071313946671365415309957045804828537561845474437630201414013
c = 3301725813323793523830449827529001764170324266525813942905248339398533386704146778215164605307364778538312368834939155244976282618558606453065237517755562156941816361506386129237655201821569225442531883605299886901781519717
e = 3

	phi = n - (p + q - 1)
d = inverse(e, phi)

plain = gmpy2.powmod(c, d, n)
	print "plaintext: {}".format(long_to_bytes(plain))

Run the script and it gives us the flag:

$ python2 decrypt.py
plaintext: TG17{t00_cl0se_f0r_g00d_crypt0}