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.
Copyright © 1999-2001 by The Shodor Education Foundation, Inc.
by the National Science FoundationOpinions expressed are those of the authorsand not necessarily those of the National Science Foundation. |