0
$\begingroup$
    Code

In[210]:= ClearAll["`*"]

In[211]:= nAlice = 942379549442875863440792026289676733726442280425825833;

In[212]:= eAlice = 3161;

In[213]:= nBob = 79850514653997998597600783722865275412086926043219979;

In[214]:= eBob = 8171;

In[215]:= AbsoluteTiming[FactorInteger[nBob]]

Out[215]= {15.5277, {{135920551079483184945633467, 1}, {587479332741251690052305137, 
   1}}}

In[216]:= AbsoluteTiming[FactorInteger[nAlice]]

Out[216]= {15.5157, {{950161244808815071986341851, 1}, {991810131797677153304382283, 
   1}}}

In[217]:= pBob = 135920551079483184945633467

Out[217]= 135920551079483184945633467

In[218]:= qBob = 587479332741251690052305137

Out[218]= 587479332741251690052305137

In[220]:= CheckPBOBandQBOBisNBOB = pBob*qBob; 

In[221]:= CheckPBOBandQBOBisNBOB == nBob

Out[221]= True

In[222]:= \[Phi]Bob = (pBob - 1)*(qBob - 1)

Out[222]= 79850514653997998597600782999465391591352051045281376

In[223]:= dBob = PowerMod[eBob, -1, \[Phi]Bob]

Out[223]= 8746323658711076825951866452640010460685361116818851

In[224]:= pAlice = 950161244808815071986341851

Out[224]= 950161244808815071986341851

In[225]:= qAlice = 991810131797677153304382283

Out[225]= 991810131797677153304382283

In[226]:= CheckPALICEandQALICEisNALICE = pAlice*qAlice;

In[227]:= CheckPALICEandQALICEisNALICE  == nAlice

Out[227]= True

In[228]:= \[Phi]Alice = (pAlice - 1)*(qAlice - 1)

Out[228]= 942379549442875863440792024347705357119950055135101700

In[229]:= dAlice = PowerMod[eAlice, -1, \[Phi]Alice]

Out[229]= 563460091251830237868743095861171504257103955775179441

In[230]:= cipher = {77874568741928116959970598529095971025860629087414125, 
   495328811744891527856291411108284515481309125912040821, 
   369267441143730519486552355172358225351959954243105382, 
   124119224439232442304278849939683049126254632833712437, 
   20954238328685282593893345826949043203535916444385374, 
   470035748197881238544363935112112802526262356262748013, 
   928665615831283703818297614394854444081685899417409053, 
   136549435712631532796261906293828466502726501184053084, 
   670416167338086414037064641226988540538267588585588252, 
   567230880992106994477625733651596614938553331658312653, 
   85499759711527459137249750519966533739083416815698030, 
   237194267190181172048965935283718337718749307564150239, 
   714940137644676544345837579711131076374048982073080384, 
   245202745375389337687548072467435228030738801235203381, 
   615798346416635545198716207339517311423843506763563210, 
   213861629662009084700094170270897896167083142563121180, 
   687507111871183164556540582320572223190911067058656586, 
   151206066523006982482036176972140280229959592662783715, 
   238434706300724254272644179998180762810110457064427775, 
   632893072732510932417630599227031114123544559673433880, 
   111253190643850701616200389944385735772515201477791379};

In[159]:= 
c1 = PowerMod[cAlice, eAlice, nAlice]

Out[159]= {53132731837440434547009702248721568338805404985817658, \
69540645986149689226714225714238822549727958387239172, \
7754537788541816511353949315771583230643363155275654, \
10632842904637884543730305601152596891244548641300284, \
44364698378263153436111702142488389245494700289027636, \
63388254804271803219769871467303892115199170764959786, \
16212391704058420639692906479221189600249367495853130, \
71649516473218468929927344516043816757158682877843178, \
64279751614262005085023176463942140616807811924070564, \
62137129688404336913445615424078316013945251807998586, \
20355232507548573436577612747187823915428639143950500, \
51597199912887585200473359895279515077043096035107570, \
59736339472114782168722956340795541474882957243580160, \
46661476490413632637187732567003741586666235008809184, \
72814049661621294436193340859951669300801131370986919, \
68147338124333931333169886682098872619390566476160110, \
44771964624017859554589254594674370739144045835265971, \
30243156959706048380330503429340975327646226339351684, \
957907768693084406076261446953050125746887557130395, \
75174109814970694655418370232300551391685976579249692, \
71103072233909234453323914233061989068431229490907036}

B = 256;

In[231]:= mAlice = PowerMod[c1, dBob, nBob]

Out[231]= PowerMod[c1, 8746323658711076825951866452640010460685361116818851, \
79850514653997998597600783722865275412086926043219979]

In[232]:= firstcharacter = Mod[mAlice, B]

Out[232]= Mod[PowerMod[c1, 8746323658711076825951866452640010460685361116818851, 
  79850514653997998597600783722865275412086926043219979], B]

In[233]:= q = mAlice; ascii = {};
While[q != 0,
  AppendTo[ascii, Mod[q, B]];
  q = Quotient[q, B]
  ];
ascii

Out[235]= {}

In[236]:= messageFromAlice = FromCharacterCode[ascii]

Out[236]= ""

This is my code. This is an RSA signed message. I'm trying to decrypt the cipher using mathematica but the last 2 steps keep failing and returning nothing. what am i doing wrong? I'm not allowed to use the built in functions private and public key which is why I have to decipher the message the long way. I don't know what else to try. The only other info I got was to use base 256 when converting the cipher into ascii and then to letters. I have seen examples of cracking decryptions like this when you're the one sending the message in text and encrypting it. But I am struggling to find examples where you're only given the cipher.

$\endgroup$
3
  • 1
    $\begingroup$ Does this help? mathematica.stackexchange.com/a/230687/72682 Please also avoid using In[...] and Out[...] and just copy your input, don't display the outputs here. $\endgroup$
    – flinty
    Sep 30, 2021 at 17:39
  • $\begingroup$ As I mentioned in that answer, you don't need mathematica's built-in public/private key functions - they're just being used for wrapping up the data there, but everything else there works. $\endgroup$
    – flinty
    Sep 30, 2021 at 17:53
  • $\begingroup$ omg, thank you so much!! I had so many questions and you literally answered all of them in one post. Sorry for not reading the other code properly, I saw public and private key and just assumed it was not what I was looking for. thanks again, I really appreciate it. $\endgroup$
    – Dyson
    Sep 30, 2021 at 19:04

1 Answer 1

5
$\begingroup$

This is very easy to adapt from my other answer, but without using PublicKey / PrivateKey,

Remove["Global`*"];
ciphertext = {77874568741928116959970598529095971025860629087414125,
   495328811744891527856291411108284515481309125912040821, 
   369267441143730519486552355172358225351959954243105382, 
   124119224439232442304278849939683049126254632833712437, 
   20954238328685282593893345826949043203535916444385374, 
   470035748197881238544363935112112802526262356262748013, 
   928665615831283703818297614394854444081685899417409053, 
   136549435712631532796261906293828466502726501184053084, 
   670416167338086414037064641226988540538267588585588252, 
   567230880992106994477625733651596614938553331658312653, 
   85499759711527459137249750519966533739083416815698030, 
   237194267190181172048965935283718337718749307564150239, 
   714940137644676544345837579711131076374048982073080384, 
   245202745375389337687548072467435228030738801235203381, 
   615798346416635545198716207339517311423843506763563210, 
   213861629662009084700094170270897896167083142563121180, 
   687507111871183164556540582320572223190911067058656586, 
   151206066523006982482036176972140280229959592662783715, 
   238434706300724254272644179998180762810110457064427775, 
   632893072732510932417630599227031114123544559673433880, 
   111253190643850701616200389944385735772515201477791379};

aliceModulus = 942379549442875863440792026289676733726442280425825833;
alicePublicExponent = 3161;
bobModulus = 79850514653997998597600783722865275412086926043219979;
bobPublicExponent = 8171;
{aliceP, aliceQ} = FactorInteger[aliceModulus][[All, 1]];
{bobP, bobQ} = FactorInteger[bobModulus][[All, 1]];
totientAlice = (aliceP - 1) (aliceQ - 1);(*EulerPhi[aliceModulus]*)
totientBob = (bobP - 1) (bobQ - 1);(*EulerPhi[bobModulus]*)

alicePrivateExponent = PowerMod[alicePublicExponent, -1, totientAlice];
bobPrivateExponent = PowerMod[bobPublicExponent, -1, totientBob];

c1 = PowerMod[ciphertext, alicePublicExponent, aliceModulus];
decryptInteger[c_, d_, n_] := PowerMod[c, d, n]

toText[numbers_] := StringJoin[
   FromCharacterCode[Reverse[IntegerDigits[#, 256]]] & /@ numbers
];

stage1 = decryptInteger[#, bobPrivateExponent, bobModulus] & /@ c1;
toText@stage1

Result:

"Congratulations! You have now managed to crack the RSA cipher. This \
means that you have a pass grade for project 2. If you want to pursue \
the requirements for a higher grade you need to solve one more \
problem. The quote you should encrypt and crack is:Simplicity is a \
great virtue but it requires hard work to achieve it and education to \
appreciate it. And to make matters worse: complexity sells better. \
Edsger Dijkstra"
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.