RSA encryption/decryption with signed message

Question

I was going through a book with some tasks that you can work with mathematica on, and I found this particular task interesting:

Proffesor Alice has sent an assignment to Bob, one of her students. To ensure that the information really comes from her, she signs the message using the method in section 2.2.6 above. You have to solve the problem, but then you have to start by cracking the crypt that was sent to Bob. Use base 256 when translating to ASCII code.

And the method given is this:

In RSA it's not just Alice that can send a message to Bob. Anyone that access Bob's public keys can see an encrypted message. So how can Bob know that the message is from Alice? A rather straight forward way of doing this is that Alice also encrypt the message with her secret key dAlice. Bob will later decrypt, using Alice's public key. Let's say Alice wants to send a message to Bob.

Bob decrypts the cipher by

And this is the information that is given for the task:

nAlice = 173067809568650650254651948453757071454112069885961677;
eAlice = 3287;

nBob = 685746563565213593998991828025682278267914215114717399;
eBob = 4141;

cipher = {531301545192540526538562996119874005598394953581889980, 
   253835033608045670746495776870704267971322752833501069, 
   295494800605225121649532827884904960119794411935318191, 
   356889556103931306723253587635046687635524222913958813, 
   665170545927968575573343996326340876350432556729975135, 
   469306660346680678018973492642493227583506074572127129, 
   669864849052286592977992159216572272286187322129900601, 
   67443874762881965068907073487271177009837307742146186, 
   206963942810038249337504906086720011644974589155509486, 
   12361993292067904922905562651618411716312523967763152, 
   596105513854241524904599343954988876751152556443182365, 
   118957298362710351312498532203563871421459266333348755, 
   439001139546986502255653331254032172395219069204122787, 
   34270241039450294802362132705578076084635135877988959, 
   627063000861103394259253981356349035768721801641804458, 
   634987884160816833480771068222516460351076121185551581, 
   398172872629132780981103160396970382112041774336326577, 
   381781261026724515120629160669181445588834230492536128, 
   164633715063442543263858143455229965317936486655924024, 
   552098460217762425462814236077839572074083170864774859, 
   683958399609386999975662847975279796030167103223715834, 
   263312158667004158391146985765292815817678708765542785};

And so far my code that I've been able to figure out is:

In[626]:= nBob = 685746563565213593998991828025682278267914215114717399;
          eBob = 4141;
          nAlice = 173067809568650650254651948453757071454112069885961677;
          eAlice = 3287;

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

Out[630]= {23.7556, {{721686482133125777709443749, 
   1}, {950200094559506336203163851, 1}}}

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

Out[636]= {23.3899, {{368184399282912041074710523, 
   1}, {470057422057325534746781399, 1}}}

In[631]:= pBob = 721686482133125777709443749;
In[632]:= qBob = 950200094559506336203163851;

In[633]:= ControlofBobPrimes = pBob*qBob;
In[635]:= ControlofBobPrimes == nBob
Out[635]= True

In[637]:= PHIBob = (pBob - 1)*(qBob - 1)
Out[637]= 685746563565213593998991826353795701575282101202109800

In[638]:= dBob = PowerMod[eBob, -1, PHIBob]
Out[638]= 22355901009732874955291933484125191913224603637354461

In[639]:= pAlice = 368184399282912041074710523;
In[640]:= qAlice = 470057422057325534746781399;

In[641]:= ControlofAlicePrimes = pAlice*qAlice;
In[642]:= ControlofAlicePrimes == nAlice
Out[642]= True

In[643]:= PHIAlice = (pAlice - 1)*(qAlice - 1)
Out[643]= 173067809568650650254651947615515250113874494064469756

In[644]:= dAlice = PowerMod[eAlice, -1, PHIAlice]
Out[644]= 1632218465661140905961122718613012702625527628840451

In[645]:= B = 256;

In[646]:= chiper = {531301545192540526538562996119874005598394953581889980, 
   253835033608045670746495776870704267971322752833501069, 
   295494800605225121649532827884904960119794411935318191, 
   356889556103931306723253587635046687635524222913958813, 
   665170545927968575573343996326340876350432556729975135, 
   469306660346680678018973492642493227583506074572127129, 
   669864849052286592977992159216572272286187322129900601, 
   67443874762881965068907073487271177009837307742146186, 
   206963942810038249337504906086720011644974589155509486, 
   12361993292067904922905562651618411716312523967763152, 
   596105513854241524904599343954988876751152556443182365, 
   118957298362710351312498532203563871421459266333348755, 
   439001139546986502255653331254032172395219069204122787, 
   34270241039450294802362132705578076084635135877988959, 
   627063000861103394259253981356349035768721801641804458, 
   634987884160816833480771068222516460351076121185551581, 
   398172872629132780981103160396970382112041774336326577, 
   381781261026724515120629160669181445588834230492536128, 
   164633715063442543263858143455229965317936486655924024, 
   552098460217762425462814236077839572074083170864774859, 
   683958399609386999975662847975279796030167103223715834, 
   263312158667004158391146985765292815817678708765542785};

So now, obviously I'm stuck on how to go further when it comes to Bob decrypting Alice's message. I know that Bob need's to decrypt the message 2 times: one for verifying that it's Alice who is the sender and one for the message.

I would appreciate if someone can explain for me how to go further into this task? I would be glad if the explanation is a bit simpler than the standard on this forum. The reason for that is that I'm not all to bright with mathematica (beginer) and my first language is not english.

Thank you!

Answer 1

I've written this out using Mathematica's PublicKey / PrivateKey as this is the way you should be doing crypto in v10.1+. But these aren't strictly necessary as I do not use Mathematica's built in Decrypt. Why is that? Because your cipher is not a list of ByteArrays as Decrypt would expect but a lot of big integers, so we need to create a manual decryption function.

bobsPublicKey = 
  PublicKey[<|"Type" -> "RSA", "PublicExponent" -> 4141, 
    "PublicModulus" -> 
     685746563565213593998991828025682278267914215114717399|>];
bobsFactors = FactorInteger[bobsPublicKey["PublicModulus"]][[All, 1]];

(* Since we haven't been given Bob's private key, we have to crack it from pub *)
bobsPhi = Times @@ (bobsFactors - 1); (* i.e EulerPhi[n] *)

bobsPrivateExponent = 
 PowerMod[bobsPublicKey["PublicExponent"], -1, bobsPhi];
bobsPrivateKey = 
  PrivateKey[<|"Type" -> "RSA", 
    "PrivateExponent" -> bobsPrivateExponent, 
    "PublicModulus" -> bobsPublicKey["PublicModulus"]|>];

alicesPublicKey = 
  PublicKey[<|"Type" -> "RSA", "PublicExponent" -> 3287, 
    "PublicModulus" -> 
     173067809568650650254651948453757071454112069885961677|>];

(* Since we haven't been given Alice's private key, we have to crack it from pub *)
alicesFactors = 
  FactorInteger[alicesPublicKey["PublicModulus"]][[All, 1]];
(* Since we haven't been given Alice's private key, we have to crack \
it from pub *)
alicesPhi = Times @@ (alicesFactors - 1); (* i.e EulerPhi[n] *)

alicesPrivateExponent = 
 PowerMod[alicesPublicKey["PublicExponent"], -1, alicesPhi];
alicesPrivateKey = 
  PrivateKey[<|"Type" -> "RSA", 
    "PrivateExponent" -> alicesPrivateExponent, 
    "PublicModulus" -> alicesPublicKey["PublicModulus"]|>];

cipher = {531301545192540526538562996119874005598394953581889980, 
   253835033608045670746495776870704267971322752833501069, 
   295494800605225121649532827884904960119794411935318191, 
   356889556103931306723253587635046687635524222913958813, 
   665170545927968575573343996326340876350432556729975135, 
   469306660346680678018973492642493227583506074572127129, 
   669864849052286592977992159216572272286187322129900601, 
   67443874762881965068907073487271177009837307742146186, 
   206963942810038249337504906086720011644974589155509486, 
   12361993292067904922905562651618411716312523967763152, 
   596105513854241524904599343954988876751152556443182365, 
   118957298362710351312498532203563871421459266333348755, 
   439001139546986502255653331254032172395219069204122787, 
   34270241039450294802362132705578076084635135877988959, 
   627063000861103394259253981356349035768721801641804458, 
   634987884160816833480771068222516460351076121185551581, 
   398172872629132780981103160396970382112041774336326577, 
   381781261026724515120629160669181445588834230492536128, 
   164633715063442543263858143455229965317936486655924024, 
   552098460217762425462814236077839572074083170864774859, 
   683958399609386999975662847975279796030167103223715834, 
   263312158667004158391146985765292815817678708765542785};

decryptInteger[c_, d_, n_] := PowerMod[c, d, n]
stage1 = decryptInteger[#, bobsPrivateKey["PrivateExponent"], 
     bobsPrivateKey["PublicModulus"]] & /@ cipher;
stage2 = decryptInteger[#, alicesPublicKey["PublicExponent"], 
     alicesPublicKey["PublicModulus"]] & /@ stage1;

StringJoin[
  FromCharacterCode[Reverse[IntegerDigits[#, 256]]] & /@ stage2
]

(** 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. By \
Edsger W. Djikstra'      
**)