RSA Cryptography

Mathematical Functions for RSA Cryptography

We need the following functions that we wrote last week.

modPow2[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
]

gcdExtended[a_,b_] := Module[{r,s,t,i,q},
r[0]=a;r[1]=b;
s[0]=1;s[1]=0;
t[0]=0;t[1]=1;
i=1;
While[r[i]>0,
r[i+1]=Mod[r[i-1],r[i]];
q=Floor[r[i-1]/r[i]];
s[i+1]=s[i-1]-q*s[i];
t[i+1]=t[i-1]-q*t[i];
i=i+1;
];
{r[i-1],s[i-1],t[i-1]}
]

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

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=

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,λ]  (* make sure this equals 1 *)

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,λ]  (* make sure this equals 1 *)

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.

Encrypting and Decrypting Numbers

A message is simply a number m. The encryption of m is simply the value (m^e) mod n, where e and n are as defined above.

If c=(m^e) (mod n) is an encrypted message, then the decryption of c is simply m=(c^d) mod n.

Try it! Encrypt and decrypt some numerical messages. For example:

m=234854;
c=modPow2[m,e,n]

modPow2[c,d,n]

Text to (Encrypted) Numbers and Back

In order to encrypt text, we first must convert text into numbers. We will devise a method that converts each 10 text characters into a 30-digit number. In order to read the decrypted message, we will also have to convert numbers back to text.

Converting a text string to a list of numbers

The first step is to take a text string and convert it to a list of numbers:

"here is a message" ⟹ {(Subscript[a, 1]),(Subscript[a, 2]),...,(Subscript[a, k])}

Mathematica provides a function ToCharacterCode that converts each text character into a numerical code (ASCII code, for standard English characters). Try it out:

text="Here is a sample message."
numsFromText=ToCharacterCode[text,"ASCII"]

Length[numsFromText]

For convenience later, we will make the list of numbers have a length that is divisible by 18. We can accomplish this by “padding” the list with extra values that represent space characters.

Module: textToNums
Argument: a string of text (e.g. “Here is my message.”)
Return: a list of numbers, one for each character in the string, padded so that the length of the list is divisible by 18.

textToNums[text_]:=Module[{nums},
nums=ToCharacterCode[text,"ASCII"];
(* pad to even multiples of 18 *)
While[Mod[Length[nums],18]>0,
AppendTo[nums,32]
];
nums
]

Try it out:

numsFromText=textToNums[text]

Converting a list of numbers into a text string

We also need to be able to reverse the previous process, converting a list of numbers back into a text string. This is easy if we use the Mathematica function FromCharacterCode.

FromCharacterCode[numsFromText,"ASCII"]

We will formalize this by writing a module with the following specification.

Module: numsToText
Argument: a list of numbers, each the code for some character of text
Return: a string of text

numsToText[numList_]:=Module[{},
FromCharacterCode[numList,"ASCII"]
]

Try it out. Make sure your functions textToNums and numsToText are inverses of each other:

numsToText[numsFromText]

numsToText[ textToNums["this is a text string"]]

It' s not necessary to remove the trailing spaces resulting from "padding" the original string, but you can if you want to.

Making a block of numbers

In order to make our encryption more efficient, we will package many character codes as a single number, which we will call a block.

First, we will write a module that concatenates the digits of numbers together. We will assume that each individual number has at most 3 digits. For example:

{273,32,501,447} ⟹ 273032501447

We will write a module with the following specification:

Module: makeBlock
Argument: a list of numbers, each at most three digits
Return: the “block” formed from the list of numbers

Here is one way to do it: Start with tot = 0. For each number in the list, do the following:
   tot = tot*1000 + nextNumber
For the list of numbers {273, 32, 501, 447}, the algorithm proceeds like this:
tot = 0
tot = 0*1000 + 273 = 273
tot = 273*1000 + 32 = 273032
tot = 273032*1000 + 501 = 273032501
tot = 273032501*1000 + 447 = 273032501447

Implement the module here:

makeBlock[numList_]:=Module[{tot=0},
Do[
tot=tot*1000+numList[[i]]
,{i,1,Length[numList]}];
tot
]

Try it out!

makeBlock[{23,54,1,393,45,293}]

Splitting a block of numbers

We also need to reverse the previous process, to split a block into a list of numbers.

273032501447 ⟹ {273,32,501,447}

We will write a module with the following specification:

Module: splitBlock
Argument: a “block” -- really just a big number
Return: a list of numbers, each containing 3 digits of the “block”

Note that we can use modular arithmetic to extract the rightmost three digits from the block. Thus, here is one way to write the algorithm:
   while block > 0:
      the next number is Mod[block,1000]; put this in the return list
      remove 3 digits from block by setting block = Floor[block/1000]

splitBlock[block_]:=Module[{b=block,retList={}},
While[b > 0,
PrependTo[retList,Mod[b,1000]];
b=Floor[b/1000];
];
retList
]

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

splitBlock[25434645634252]

splitBlock[makeBlock[{23,54,234,7,234}]]

Converting a list of numbers into a list of blocks

Now we want to take a list of numbers (i.e. character codes from some text string) and make each 18 consecutive numbers into a block. We will assume that the length of our list of numbers is a multiple of ten.

Mathematica provides a function that partitions a big list into sublists of a certain size. The function is Partition. It works like this:

Partition[ Range[54],18]

Write a module that partitions a list of numbers into sublists of size 18, and then uses makeBlock to convert each sublist into a block. The output should be a list of blocks.

Module: numsToBlocks
Argument: a list of numbers (each the code for some text character), whose length is divisible by ten
Return: a list of blocks, each formed from ten consecutive numbers

numsToBlocks[numList_]:=Module[{parts,k,i,blockList={}},
parts=Partition[numList,18];
k=Length[parts];
Do[
AppendTo[ blockList, makeBlock[ parts[[i]] ] ];
,{i,1,k}];
blockList
]

Test your function:

numsFromText
numsToBlocks[numsFromText]

Converting a list of blocks into a list of numbers

Lastly, we need to undo the previous function, converting a list of blocks into a list of numbers.

Write a module to do this. Your splitBlock function will be important for this.

Module: blocksToNums
Argument: a list of blocks
Return: a list of numbers, 18 of which come from each block

blocksToNums[blockList_]:=Module[{},



]

Make sure that blocksToNums returns a list, not a list of lists.

Try it out! Make sure that blocksToNums “undoes” numsToBlocks.

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

Here is an implementation. Note that you need to supply your modPow2 function, as well as a public key, in order for this to work.

encryptRSA[text_,e_,n_]:=Module[{blocks, k,i,cyphertext={}},
blocks=numsToBlocks[ textToNums[ text ]];
k=Length[blocks];
For[i=1,i≤k,i++,
AppendTo[ cyphertext,modPow2[ blocks[[i]], e, n ] ];
];
cyphertext
]

Try it out!

e

n

encryptRSA["Here is a sample message",e,n]

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[cyphertext_,d_,n_]:=Module[{},


]

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

Assignment

Post your public key to the RSA Forum on Moodle.

Copy someone else’s public key from the RSA Forum. Then use the functions in this notebook to encrypt a message to send to that person. Send them the encrypted message (i.e., the list of numbers) 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.

Prepare a single notebook to hand in for the RSA Project. Include all of the functions necessary to for encryption and decryption, and show samples of your encrypted communication. Add explanation, introduction, and conclusion to explain what you did. Submit this notebook to the RSA Project assignment on Moodle.