Tags: cryptography crytography-rsa
Rating:
## 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](https://en.wikipedia.org/wiki/Congruence_relation), [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem), and [Modular Arithmetic](https://simple.wikipedia.org/wiki/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. Looks familiar? Well that's because it is! If we replace`((e^-1) mod phi(n)) + phi(n)`with x and y it becomes the same exact thing! So, what does this mean? Simply put it means that `(e^-1) mod phi(n) =`. Wait a minute. What was `(e^-1) mod phi(n)`** **again? That's right: d. 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:
```py
>>> 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:
```py
>>> 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}**
