RSA cryptography

Programming, evaluate this cell first.

<< NumberTheory`PrimeQ`
\(GetNextPrime[num_] := 
      Module[{n}, 
		If[EvenQ[num], n = num + 1, 
          n = num]; 
		While[\(! PrimeQ[n]\), 
          n = n + 2]; 
		n]\)
\(GenerateRandomPrime[n_] := 
      GetNextPrime[Random[Integer, {10\^\(n - 1\), 10\^n}]]
\)
\(BreakUpMessage[cds_, blen_] := 
      Module[{c = cds}, 
		 (*\ 
          Pad\ the\ sentence\ with\ spaces\ *) 
		While[
          Mod[Length[c], blen] != 0, 
			c = Join[c, {32}]]; 
		Table[
          Take[c, {i, i + blen - 1}], {i, 1, Length[c] - 1, blen}]]\)
ListToNumber[l_] = ListToNumber[l, 0];
\(ListToNumber[l_, num_] := 
	
      If[Length[l] == 0, 
        num, 
		ListToNumber[
          Rest[l], \((num*256)\) + First[l]]]	
\)
\(convertMessage[mes_, L_] := 
 (*\ n\ is\ the\ public\ modulus\ *) 

      Module[{blklen, bitlen, l, blocks}, 
		bitlen = 
          Length[IntegerDigits[L, 2]] - 1; 
		blklen = 
          Quotient[bitlen, 8]; 
		l = ToCharacterCode[mes]; 
		blocks = 
          BreakUpMessage[l, blklen]; 
		Map[ListToNumber[#] &, 
          blocks]]\)
\(restoreCharacterCode[l_]\  := \ 
      Flatten[
			Map[IntegerDigits[#, 256] &, l]]\)
\(restoreMessage[
        l_] := 
		FromCharacterCode[
		Flatten[
			Map[
            IntegerDigits[#, 256] &, 
            l]]]


\)
encrypt[A_Integer]  :=  PowerMod[A,  r,  n]
decrypt[ B_Integer]  :=  PowerMod[ B, s, n]
encrypt[L_List]  :=  Map[encrypt,  L]
decrypt[L_List]  :=  Map[decrypt,  L]

Example  1.12.3  from the text:

Here are the computations for Example 1.12.3  in the text.    First two big prime numbers and one small prime number are chosen:

p  = 
      45884239840513596008917937166885472963043161712479
q  = 
      83030660830407235737628873770794657586154960341401
r   =  55589

The recipient computes the quantities n, m, s, and publishes n and r.

n  =  p*q
m  =  LCM[p - 1,  q - 1]
s  =  Mod[ExtendedGCD[r, m][[2, 1]],  m]
Mod[r*s,  m]  ==  1

The secret message is ALGEBRA IS REALLY INTERESTING.   The sender first encodes this message as an integer a, and then computes b = remainder of a^r   modulo n :

messge  =  "ALGEBRA IS REALLY INTERESTING"
ToCharacterCode[messge]
a  =  convertMessage[messge,   n]
b  =  encrypt[a]

The recipient decodes b,  recovering a, and then extracts the base 256 digits of a, which gives the character codes of the original message:

a1  =  decrypt[b]
restoreCharacterCode[a1]
restoreMessage[a1]

Generating a key

The following  code generates two large  random primes (the number of whose digits is governed by the parameter length,  and one   small prime which is relatively prime to p-1 and q-1.  It then computes the quantities n, m, and s.

leng =  100;
p  =  GenerateRandomPrime[leng]
q  =   GenerateRandomPrime[
        leng]

n  =  p*q
m  =  LCM[p - 1,  q - 1]
r  =  GenerateRandomPrime[5];
While[GCD[r,  m]  >  1,  
        r  =  GenerateRandomPrime[5]];
r
s  =  
      Mod[ExtendedGCD[r, m][[2, 1]],  
        m]

Example with a longer message, and an arbitary key.

We take a message and convert it to a list of  integers,  each smaller than n:

messge  =  "All there is to thinking is seeing \
something noticeable which makes you see something you weren't noticing  \
which makes you see something that isn't even visible."
ToCharacterCode[messge]
a  =  convertMessage[messge,   n]

The message is encrypted:

b  =  encrypt[a]

The encrypted message is decrypted and restored to its original form:

a1  =  decrypt[b]
restoreCharacterCode[a1]
restoreMessage[a1]