Hr. Vænge had been happy to see that he had been joined in his RSA interest by his old school friend, Fru Stræde.
It was also great to see that the Danish Geocacher reviewers had employed RSA cryptology - it really was about time too!
However, something had gone wrong, so Fru Stræde's cache message had been decoded and the secret revealed.
The reviewers assessed the situation carefully. Toa Takanuva and Toa Ignika were not too concerned about it ("it is just a game after all"), but the newest reviewer, Toa Onua, was really upset! He felt that his private key must somehow have been compromised and decided immediately to update his public/private key pair.
Toa Onua's new public key is:
n=22388232863920470596802550685774448260887084292474361213703548733447392487686990105367069308738942636151787118341191458544391973164685732565316022125864455526760847852641966850520178365981384625989732743139140734649614936813017784674034276766399163392028630325265939035016182729069582023782586176082574346599295847156708947432288967517240462327670580346184157829060575513234062919660483076475229553917970422053050553506811
e=65537
Toa Onua now told Hr. Vænge that things were safe again, and that it was ok for him to send by RSA-encoded message details of his new cache; just like Fru Stræde had done.
So, Mr. Vænge encoded the message with Toa Onua's public key and sent it to him for review. However, the message was intercepted by the mysterious Mr. X. The encoded message (let's call it y) is shown below:
y=986916454166166585725207936431288924995856082460355391635533863939487650554436684032533435249098863744255583271109272514576850243967607782806941326645224983296574188365252359516778791343274605845806362211741490623153875633693551620323802778529387789000024781634721399173359619784980682164165420116743413545330135872572320382030430540455103795515598800674072138450260865569305319175615996012285139581466487909667890581307
Unlike the friendly Hr. Vænge and Fru Stræde, Mr. X was an evil hacker, so he went on to employ a few RSA tricks...
First Mr. X found a value x0 which is co-prime to n. The value is shown below:
x0=11194116431960235298401275342887224130443542146237180606851774366723696243843495052683534654369471318075893559170595729272195986582342866282658011062932227763380423926320983425260089182990692312994866371569570367324807468406508892337017138383199581696014315162632969517508091364534791011891293088041287173299647923578354473716144483758620231163835290173092078914530287756617031459830241538237614776958985211026525276753405
Then he RSA-encoded x0 with Toa Onua's public key to get y0.
Next, he calculated yet another value, y' as follows: y' = (y0 * y) mod n.
And finally, he created a fake geocaching.com profile and sent a message to Toa Onua. The message contained y' and mentioned in the subject that the message was RSA encoded.
Toa Onua went on to decode y' using his private key. However, he was not really able to make anything useful from the result (let's call it x'), it looked like random text. So, he sent x' back to Mr. X with the following subject "I don't understand your RSA message as attached. Please notice that I have a new public key!"
The value of x' as sent back by Toa Onua was:
x'=22388232863920470596802550685774448260887084292474361213703548733447392487686990105367069308738942636151787118341191458544391973164684069082361920571374263227105894734435921985615841064282875270580613503735809493636578037635868832552026747033132391409761714158212633586823401734991534462685282511088995482739540861190509919955546609213778432846976825417870462100679674582495627689687126184019380966900107027113133470220259
Mr. X smiled and laughed his evil laugh, before hurrying out the door to find Mr. Vænge's cache...
Can you do the same?
Danish on request.
Geochecker
