RSA Cryptography

Math 242 Modern Computational Math, spring 2021

Converting Text to Numbers and Back

Before we can encrypt text, we have to convert the text to numbers. We will use the ASCII code to convert each character to a numeric code (2- or 3-digits). Every 18 numeric codes will be joined into a 54-digit number called a block, which we can encrypt. We also have to reverse the process, converting a list of blocks back to text.

Text to Blocks

The following module takes a string of text and returns a list of blocks. Each block is a 54-digit number, each 3 digits of which is the ASCII code of a character in the text string.

textToBlocks[text_]:=Module[{asciiList,sublists,blockList},
(* convert text to a list of ASCII codes *)
asciiList=ToCharacterCode[text,"ASCII"];

(* partition asciiList into sublists of length 18 (the last sublist might be shorter) *)
sublists=Partition[asciiList,UpTo[18]];

(* make a block from each sublist *)
blockList=makeBlock/@sublists;

(* return the list of blocks *)
blockList
]

textToBlocks["Math 242 is the most fun math course!"]

While[Mod[Length[asciiList],18]>0,
AppendTo[asciiList,32]
];
sublists=Partition[asciiList,18];

Notice that the previous module calls another module, makeBlock. This module takes a list of numbers (each at most 3 digits) and joins them together. For example:

{273,32,501,447} ⟹ 273032501447

We still need to write this module. How do we join digits of numbers together? Here is one algorithm:

Start with total = 0. 
For each number in the list, do the following:
   total = total*1000 + nextNumber

For example, suppose we have the list of numbers {273, 32, 501, 447}. The algorithm proceeds like this:
total = 0
total = 0*1000 + 273 = 273
total = 273*1000 + 32 = 273032
total = 273032*1000 + 501 = 273032501
total = 273032501*1000 + 447 = 273032501447

Now implement the module here:

makeBlock[nums_]:=Module[{total=0},
Do[
total=total*1000+n
,{n,nums}];
total
]

Try it out!

makeBlock[{35,189,99,201,41}]

Blocks to Text

We also need to reverse the above process, converting a list of blocks back to text. The following module takes a list of blocks and returns a string of text. Each block must be a 54-digit number, whose digits are the ASCII codes of 18 characters.

blocksToText[blockList_]:=Module[{asciiList={}, text},
(* split each block into 18 numbers *)
asciiList=splitBlock/@blockList;

(* we want a list, not a list of lists *)
asciiList=Flatten[asciiList];

(* convert ASCII codes back to text *)
text = FromCharacterCode[asciiList,"ASCII"];

(* return the text *)
text
]

Notice that the previous module calls another module, splitBlock. This module takes a a block and splits it into a list of numbers. For example:

273032501447 ⟹ {273,32,501,447}

How can we do this? we can use modular arithmetic to extract the rightmost three digits from the block, then we can divide by 1000 to shift the remaining digits to the right by three digits. The algorithm is as follows:

while block > 0:
      the next number is Mod[block,1000]; put this in the list of numbers
      remove 3 digits from block by setting block = Floor[block/1000]

Now implement the module here:

splitBlock[block_]:=Module[{b=block,numList={}},
While[b>0,
(*Print[Mod[b,1000]];*)
PrependTo[numList,Mod[b,1000]];
b=Floor[b/1000]
];
numList
]

Try it out! Make sure that splitBlock “undoes” makeBlock.

splitBlock[123456789555]

test=makeBlock[{23,345,123,657,43}]

splitBlock[test]

Then make sure that blocksToText “undoes” textToBlocks.

test=textToBlocks["here is my sample message!"]

blocksToText[test]

Mathematical Functions for RSA Cryptography

We need the following functions that we wrote last week. First, modPow efficiently computes (b^e) (mod m).

modPow[base_, exponent_, modulus_]:=Module[{b=base,e=exponent,result},
result=1;
b=Mod[b,modulus];
While[e > 0,
If[Mod[e,2]==1,
result = Mod[(result*b),modulus];
];
e=Floor[e/2];
b=Mod[b*b,modulus];
];
result
]

Second, fermatPrime uses Fermat’s Little Theorem to test if a number n is probably prime.

fermatPrime[n_,m_]:=Module[{a},
(* Select m random values of a in the range 2, ..., n-1. If (a^(n-1)) ≡ 1 (mod n) for each of these values of a then return True. Otherwise return False. *)
Do[
a=RandomInteger[{2,n-1}];
If[modPow[a,n-1,n]≠1,Return[False,Module]]
,m];
True (* return value if all modPow expressions = 1*)
]

Third, modInverse computes the multiplicative inverse of a mod n.

modInverse[a_, n_]:=Module[{g,s,t},
{g,{s,t}}=ExtendedGCD[a,n];
If[g≠1,Print["ERROR: ",a," and ", n, " are NOT relatively prime!"];Return;];
If[s<0,s+=n];
s
]

Create Your Encryption and Decryption Keys

This section reviews how to create your encryption and decryption keys.

1. Choose two primes p and q

Use your fermatPrime function to find two prime numbers p and q with 30 digits each. These primes are private values.

p=

q=

2. Compute the product p·q

Compute n=p q. Note that it’s easy to multiply p and q, but very hard to factor n. (You can try it with Mathematica’s FactorInteger function.) This number will be public.

n=p*q

3. Compute the totient function of n

Compute λ = λ(n)=lcm(p-1, q-1). Here, lcm is the least common multiple, which you can compute using Mathematica’s LCM function. The value λ is private.

λ=LCM[p-1,q-1]

4. Choose your encryption key

Find a value e such that gcd(e,λ) = 1. This value doesn’t need to be huge — four digits or so is good. This value will be public.

e=
GCD[e,λ]

5. Determine your decryption key

Compute the modular inverse of e mod λ. Call this value d. This value is private.

d=modInverse[e,λ]

Mod[d*e,λ]

6. Your Public and Private Keys

Your public key is the pair (e,n). Share this on the RSA Forum on Moodle, so that others can send you encrypted messages. Your private key is d. Don’t share it outside of your own Mathematica notebooks.

Putting it all together: RSA Encryption

We are finally ready to encrypt and decrypt text!

Encryption takes a text string, converts it to a list of numbers, converts that to a list of blocks, and then encrypts each block. The following function accomplishes this.

Module: encryptRSA
Argument: a text string and a public key (e, n)
Return: a list of encrypted blocks

encryptRSA[text_,e_,n_]:=Module[{blocks,cypher={}},
blocks=textToBlocks[text];
Do[
AppendTo[ cypher,modPow[ m, e, n ] ]
,{m,blocks}
];
cypher
]

Try it out!

encryptRSA["here is my message that I want to sent",eProfWright,nProfWright]

Decryption takes a list of encrypted blocks, decrypts each block, splits each block into a list of numbers, and converts the list of numbers into a text string. You can write the implementation. (It isn’t much different than the encryption function above.)

Module: decryptRSA
Argument: a list of encrypted blocks and a private key (d, n)
Return: a text string

decryptRSA[cypher_,d_,n_]:=Module[{blocks={}},
Do[
AppendTo[blocks,modPow[c,d,n] ],
{c,cypher}];

blocksToText[blocks]
]

Try it out! You should now be able to encrypt and decrypt text!

decryptRSA[{9518079576307174485407638150095225935814396055463289919612,63875750429961334209594443203102917441129691174865036085434,36084720344838472805563180185520530218447743340965054243389},dProfWright,nProfWright]

Assignment

Post your public key to the RSA Forum on Moodle.

Send messages to Prof. Wright and at least two other people using the RSA Forum. To do this, copy the  public key of the person to whom you want to send a message. Then use the functions in this notebook to encrypt your message to send to that person. Copy your encrypted message (i.e., the list of numbers) and paste it below in the recipient’s discussion thread in the forum.

When someone else sends you an encrypted message, use your private key to decrypt it. Send that person an encrypted reply using their public key.

Important: When copying huge numbers and lists from Mathematica, use Copy As -> Plain Text. Otherwise, your numbers might include spaces and return characters that will make it harder for you to send and receive messages in the RSA Forum.