HiddenKey

By PGODULTIMATE

Ugh, another RSA problem? Help me decrypt this message please file.

File:

n = 26520361246721655719312292942299590997777406526676863843012099874597354135915059455042239376324387799865053683242414636060009865587583173045275105457073082968243533504387905119043247388529642262414438526116242340640646581052259140730856602869915716683075789898757359771098724847778465228984815596078931371664087053561549606914105075834487920908928691828802759345002239892841824320364955010193182040747111546094295252827762503139260982913152531075677337995125360354293156865458241440186309803882568716210602936866629058410889597625550416294217700072058777542777083497633525029159889586234144102169842680272161183745721

e = 65537

c = 7418057243095790130042687065779702583554288701684857484514194801172294222458626819803912260156980577116251379730360494595360787198176052366623880562576447483406219805426610686644675038623537403087409914772622449653592895702054870869175670435789095639112627664236615046540518795677000409954873160628316626272163567705830245764662598626052114608721632793989844962828953647706639614802279473020211192036611008393324264343853025429310141786756433031256006580696886806558123345474279809833474067840131549259039990436737446672931220529391217431088545326280625895692744865166426041282243083293457565493214530087442183221292

2d + phi(n) = 45614762360410229300212698129832564750331302865657508323173977053637449841505611287528058184192348840566221315228568671446549156638679494257938961387272062063098949100738786162532797890920043101547869966269453672948648924362631904429625232239887534242738487644500448074790752720083799014401870217385681081039018262858805431651444719629084023758324666731580812040390477922196960548253698139132501827455548068644079880155486688825629841080221071744769415881019858426562758569708023957635165912129811734183443537045716249795296152683405537442868538321416720588711975920577513834780887193070997464962139948390468804712622

This problem was one that kind of trolled me for a while (like most of the problems in this year's competition) but I eventually figured it out. In this problem there are the usual three (n,e,c) that we find in an RSA problem. So, because I have Forced Factoring Syndrome I immediately tried factoring it. This was pretty dumb and unsurprisingly didn't pan out to anything. So I was left to look at the most suspicious part of the problem: 2d + phi(n).

I realized that the problem was likely related to the formula: d = (e^-1) mod phi(n). After a long time of aimlessly staring at this equation and doing stuff that was not useful at all, I finally did something that moved me forward. I plugged in (e^-1) mod phi(n) for d in the equation 2d + phi(n) = <number I don't wanna write out>. So some easy algebra leaves me with ((e^-1) mod phi(n)) + phi(n) = <num/2>. At this point I was horribly stuck. I had no idea what to do with that extra phi(n). So I spent a lot of time looking up modular math and I eventually came upon three Wikipedia Articles: Congruence Relation, Chinese Remainder Theorem, and Modular Arithmetic. The articles basically say something like x mod y is the same as (x mod y) + y because the remainder would be the same in the end. We know that(e^-1) mod phi(n) = d. So, essentially d = number/2.

From this point on the problem becomes SUPER EASY. Now I know c, d, and n! That's exactly what I need to find m (the secret message). I used python on my terminal to do this next part:

>>> c = 7418057243095790130042687065779702583554288701684857484514194801172294222458626819803912260156980577116251379730360494595360787198176052366623880562576447483406219805426610686644675038623537403087409914772622449653592895702054870869175670435789095639112627664236615046540518795677000409954873160628316626272163567705830245764662598626052114608721632793989844962828953647706639614802279473020211192036611008393324264343853025429310141786756433031256006580696886806558123345474279809833474067840131549259039990436737446672931220529391217431088545326280625895692744865166426041282243083293457565493214530087442183221292

>>> d = 22807381180205114650106349064916282375165651432828754161586988526818724920752805643764029092096174420283110657614284335723274578319339747128969480693636031031549474550369393081266398945460021550773934983134726836474324462181315952214812616119943767121369243822250224037395376360041899507200935108692840540519509131429402715825722359814542011879162333365790406020195238961098480274126849069566250913727774034322039940077743344412814920540110535872384707940509929213281379284854011978817582956064905867091721768522858124897648076341702768721434269160708360294355987960288756917390443596535498732481069974195234402356311`

>>> n = 26520361246721655719312292942299590997777406526676863843012099874597354135915059455042239376324387799865053683242414636060009865587583173045275105457073082968243533504387905119043247388529642262414438526116242340640646581052259140730856602869915716683075789898757359771098724847778465228984815596078931371664087053561549606914105075834487920908928691828802759345002239892841824320364955010193182040747111546094295252827762503139260982913152531075677337995125360354293156865458241440186309803882568716210602936866629058410889597625550416294217700072058777542777083497633525029159889586234144102169842680272161183745721`

>>> m = pow(c,d,n)

Great! Now I have m. What do I do now? I convert it to hexidecimal so that I have something easier and familiar to work with:

>>> hex(m)

This gives me 656173796374667b7634306932766a7462356530393332786f787d! The next step is super easy: just plug it into a Hex to ASCII converter to get:

easyctf{v40i2vjtb5e0932xox}