Stimulating Understanding of Computational science through Collaboration, Exploration, Experiment, and Discovery for students with Hearing Impairments
a collaboration of the Shodor Education Foundation, Inc., Eastern North Carolina School for the Deaf, Barton College, the National Technical Institute for the Deaf, and Interpreters, Inc.

For Teachers!

RSA Cryptology

The Math Behind RSA Cryptography

Although your students will probably gain a limited insight into the math behind RSA Cryptography, it is important that you, as the teacher, understand it. The steps to encrypting and decrypting a message using RSA Cryptography, and the math behind it, are included below. Please make sure you understand the math in order to help your students gain a better understanding of RSA Cryptography. 

Step One: Finding Your Keys 

The first thing that you must do is find your encryption and decryption keys. To do this first choose two primes of equal length. In the real world application of this we would use primes that were more than hundreds of digits long, but for our purposes we will use smaller prime numbers. Let one of these primes be denoted by the letter "P" and the other by "Q". 

Next, you must find your encryption key, "E." Finding E requires a somewhat guess-and-check approach. Randomly choose a number to be E. However, this
number must meet the following qualification: E and (P-1)(Q-1) must have no factors in common. In other words, the GCD of E and (P-1)(Q-1) must be 1. This is due to the nature of modular mathematics. Try it yourself. Make a multiplication table for the numbers 0 - 5 in mod 6 (You are using 0 - 5 since these are the numbers that are possible in mod 6). Look at the first row of your table. This row has all the numbers from 0 - 5 in it. However, look at the second and third rows. The second row does not have 1 or 3. The third row does not have 1, 2 or 4. This is because the GCD of 2 and 6 or of 3 and 6 are not 1. We need all the numbers from 0 to the encryption key to appear in order to ensure that we will receive a unique combination of numbers to be uniquely interpreted. 

Once you have an E that meets that qualification, it is time to find your decryption key, "D". The following formula is used to obtain the value of D:
D = E-1 (mod (P-1)(Q-1))

The program that the students will use finds D for them. They do not need to understand modular math to complete this module, although it would greatly enhance their understanding. If you need to refresh your memory of modular math, go look at the Modular Math Module also available at this sight. 

Before continuing on to encrypting and decrypting, we must calculate the value of a number "N." The variable N is used for the math in both encryption and decryption, and is equivalent to P * Q. 

At this point, P and Q may be discarded, but not made public. The values of E and N may become public. The value of D is to stay private. 

Step Two: Encryption 

Encryption is done through a relatively simple process. The message to be sent is written out. Each letter is changed to its two digit numerical equivalent (where a=01, b=02, and so on) in mod 26 (making z=00). The equivalents do not need to be in two digits. However, breaking a message is more simpler this way. 

After this has been done, the long number string is broken into blocks. These new number blocks MUST have a value less than the number N. If not, the
deciphering process will not work correctly (because we are working in mod N). 

Each number block is encrypted using the following formula where M denotes the message block and C denotes the cipher value:
C=ME (mod N)


In the real world scenario, these new numbers would form a new cipher string that would be changed back into letters. These letters would then be split into blocks of equal length. However, since this makes the deciphering process more difficult, the students will simply leave the cipher in the cipher blocks they just created. 

Step Three: Decryption 

Decryption is completed through a process very similar to encryption. Each cipher number block is translated back to message numbers using the following formula:
M=CD (mod N)

All of these new number blocks are then recorded in order and the spaces removed out of the string. Every two digits are equivalent to one letter. Starting at the beginning of the string all the number pairs are translated back into their alphabet equivalent. The message is then apparent in the string. 

Developed by
The Shodor Education Foundation, Inc.

Copyright © 1999-2001 by The Shodor Education Foundation, Inc.

This project is supported, in part, by the National Science Foundation Opinions expressed are those of the authors and not necessarily those of the National Science Foundation.