Worksheet 12.3 Activity: RSA Cryptography Lab
Let's implement the ideas behind RSA cryptography to create a public encryption key that you can use to have your friends send you secure messages.
We will use SAGE to compete this activity. You can use the interactive SAGE cells in the online version of this activity. Or use the online SAGE cell at https://sagecell.sagemath.org/. Of course if you have SAGE installed, you can use that.
1.
First you will need to select two very large prime numbers. Let's shoot for 20-25 digits. Luckily, SAGE has the command next_prime()which will give you the next prime larger than your input. So pick a random input and get two primes. You will want to save these as a constant. For example (but you will need to find a much bigger numbers):
2.
Now you can compute \(n = pq\) and \(m = (p-1)(q-1)\text{.}\)
Notice that you could ask SAGE to find \(m = \varphi(n)\) using euler_phi(n), but you should think about why this is a really really really bad idea. If you want, you can try it below, but maybe first with only small values of \(p\) and \(q\text{.}\)
3.
Now we need \(E\) and \(D\text{.}\) Recall that we want \(\gcd(E,m) = 1\) and \(DE \equiv 1 \pmod{m}\text{.}\) How are you going to find these?
SAGE has the command gcd(E, m)that will compute the gcd of the two inputs. You could try factoring \(m\) and looking for a reasonably large value of \(E\text{,}\) or just guess and check until you find a suitable \(E\text{.}\)
To find \(D\text{,}\) there is the command inverse_mod(E, m)which will run the Euclidean algorithm forwards and backwards on \(E\) and \(m\text{.}\)
You can now publish the encryption pair \((n,E)\) so your friends can send you messages. You will need to keep \(D\) private. But don't loose it! The whole point is that without \(p\) and \(q\text{,}\) you should not be able to find \(D\) again, even if you had \(n\) and \(E\text{.}\) Evaluate the cell below to refer to later:
If someone has a message \(x\) to send you, they would simply need to compute \(x^E \pmod{n}\text{.}\) SAGE can do this with mod(x^E,n), but if \(x\) and \(E\) are large, this would take a really long time. Luckily, there is a better way: power_mod(x,E,n)computes the same thing, but uses the method of repeated squaring to make this much more efficient.
For example:
You will need to use this function to decrypt the message \(y\) when you take \(y^D \pmod{n}\text{.}\)
4.
When you get an encrypted message, you can assign it to the variable encryptedand then decrypt it using the power_modfunction.
5.
The last piece of the puzzle is what to do with the number you get out of the decryption. You will find some \(x\text{,}\) but need that to be translated into text you can read.
This depends on the agreed upon method for translating a string of symbols into numbers. For this lab, you can use the following code do decrypt the message:
Here is why the code above works. First, we need to agree upon how to translate the original message into a number.
Suppose we have a string called message. We can create a list of ASCII code values (0 through 127) using digits = [ord(letter) for letter in message]. Here ord()converts a single letter into its ASCII code, so we do that for each letter in the message.
We must then convert a collection of letters into a single number base 128. SAGE can do this using the ZZ()function. So ZZ(digits,128). This will only work if \(128^k \lt n\text{,}\) where \(k\) is the number of digits. So in practice, we would break the longer message into chunks and encrypt each chunk separately.
To undo this coding, you can break down the received message decryptedusing digits = decrypted.digits(base=128), which makes a list of digits. Then you can create a list of letters using letters = [chr(ascii) for ascii in digits]. Finally, put these letters into a string using ''.join(letters).
To practice, you can try encoding and decoding messages below. The first set of cells allow you to encrypt and decrypt a very short message. The second pair show a way to break up the message word by word using for loops break up the message into word-long chunks so there is no limit to the length of the message.
For longer messages:
Here is an empty sage cell in case you want to experiment with other commands: