Mathematics behind Public Key Cryptography
Contextual Teaching and Learning Essay
Amena Warrayat
*Please maximize browser to properly view the essay*
Jump to Section:
I. Introduction
II. Examples of asymmetric key techniques
III.RSA Encryption Algorithm and how to generate keys using RSA
IV. Example using RSA
V. Proof of RSA using Fermat's Little Theorem
VI. Security Issues of RSA
VII. How to teach RSA at the high school level
VIII. Additional Information regarding public key cryptography
I. Introduction
Public key cryptography is an algorithmic, cryptographic system that requires two separate keys, a public and a private key, designed to encode and decode a message, respectively. The algorithms for public key cryptography are based on mathematical relationships that have no efficient solution (such as the RSA algorithm involving factoring large numbers into products of primes). Since these relationships make it extremely difficult for anyone to derive the private key based only on the knowledge of the public key, it ensures the security of public key cryptography. This sense of security gives rise to many practical uses of public key cryptography.
Two common uses of public key cryptography are public key encryption and digital signatures. Public key encryption is when a secret message is encrypted using a public key but only the person who possesses the secret key can decode and read the secret message. Digital signatures is a message that is signed with a sender's private key and can be verified by anyone with access to the sender's public key. Both of these applications are examples of confidentiality and authenticity of public key encryption.
II. Examples of asymmetric key techniques
These examples are often implemented for public key encryption.
1. Diffie-Hellman Key Exchange
2. Digital Signature Standard (DSS)
3. Elliptic Curve Techniques
4. Paillier Cryptosystem
5. RSA Encryption Algorithm
6. Internet Key Exhange
7. McEliece Cryptosystem
8. Cramer-Shoup Cryptosystem
III. RSA Encryption Algorithm and how to generate keys using RSA
Let's discuss the mathematics behind public key encryption via the RSA Encryption Algorithm. RSA stands for Ron Rivest, Adi Shamir, and Leonard Adleman who first publicly described the algorithm in 1977, based on the difficulty of factoring large integers.
This public-key cryptography algorithm defines n = pq, where p and q are primes, a private key d, and a public key e such that
(1)
where
represents a secret that is not disclosed to the public. Similarly, the private key is not publicized but rather must be calculated using the congruence relation stated in (1). Only the public key is easily accessible by everyone.
Suppose the message sent using the RSA algorithm is denoted M. To encode this message, M, the sender chooses a value n = pq and a public key e and sends message E:
(2)
Then to decode, the receiver (who is the only one to know d) computes:
(3)
Using the RSA algorithm, the identity of the sender can be determined as legitimate without revealing his or her private code.
IV. Example using RSA
Suppose Bob would like to send Alice a message, M = 65 using the RSA algorithm. As a result, Bob provides Alice with n = pq = 61 * 53 = 3233.
Therefore:
Suppose Bob provides the public key of e = 17 since it can be any number 1 < e < 3120 that is coprime to 3120.
So, Bob must first encode his message M = 61 by using equation (2).
Then, after calculating d, the modular multiplicative inverse of e (mod (p-1)(q-1)), it is found that d = 2753.
Finally, to decrypt the message, we calculate:
V. Proof of RSA using Fermat's Little Theorem
Fermat's little theorem states that if p is prime and p does not divide an integer a then
We want to show that
for every integer m when p and q are distinct prime numbers and e and d are positive integers satisfying
We can write
for some nonnegative integer h.
To check two numbers, like
and m, are congruent mod pq it suffices (and in fact is equivalent) to check they are congruent mod p and mod q separately. (This is part of the Chinese remainder theorem, although it is not the significant part of that theorem.) To show
In the first case,
In the second case,
where we used Fermat's little theorem to replace
Similarly, the verification that
is done, treating the cases m is congruent to (0 (mod m)) and m is not congruent to (0 (mod m)) separately with Fermat's little theorem for modulus q in the second case.
Therefore,
for any integer m. Q.E.D.
VI. Security Issues of RSA
Let's expand upon the brief security issues explained in the introduction. The security of the RSA cryptosystem is based on two mathematical problems: the problem of factoring large numbers and the RSA problem, which is simply computing the private key when given only the public key. Specifically, the RSA problem consists of taking the eth roots modula n (the product of distinct primes p and q) to recover the message M. Currently the most promising approach to solving the RSA problem is to factor the modulus n. An attacker who wishes to surpass the security issues of RSA will try to compute the secret exponent d from the public key (n, e) then decrypt E using the standard procedure. No polynomial-time medthod for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists.
Besides the RSA problem, another security issue lies with a faulty key generation. As a general rule, in constructing the integer n, the numbers p and q should not be "too close" (i.e. p - q shouldn't be less than two times the fourth root of n) because if they are too close, n can be factored quickly by Pollard's p-1 algorithm which causes the need for the values of p or q to be discarded. Similarly, the value of the private key e should not be too small since smaller exponents have a greater risk of leading to an attack.
VII. How to teach RSA at the high school level
Since RSA and cryptography involve university-level mathematics such abstract algebra and number theory, I think the best way to introduce RSA to secondary students is to discuss the generality of public key versus private key cryptography and provide many interesting application problems in order to encourage students to study this field. Sparking secondary students' interest in mathematics may be a difficult feat, but the subject of cryptography can be especially interesting. For instance, to spark students' interest in cryptography, an educator can introduce cryptography as associated with the military, war, and secret agents. For example, in World War II, many systems were created so that the high command could communicate with generals in the field over radio waves with the enemy not being able to decipher it. A present-day example could be that we need cryptography because of the everyday use of computers and technology. It's important for businesses to be able to protect the information in their computers. Another example of using cryptography could be to protect an online buyer's identity. No one wants their credit card and personal identification details stolen when making online purchases.
After this discussion, it would be advisable to introduce some terminology, such as:
1) Code: information that will allow words to be changed to other words or symbols. For instance, a code word for "rifle" may be "escargot". The only way to decode a message is by having the set of words and their codes.
2) Plaintext: the message you wish to put in secret form. Plaintext is usally written in all lower case letters without spaces. For example, the message:
"I will meet you at 5 PM in the mall" is written as "iwillmeetyouatfivepminthemall"
3) Cipher: the method for altering the plaintext
4) Ciphertext: the secret version of the plaintext. So the plaintext: "iwillmeetyouatfivepminthemall" may be changed to NBNQQRJJYDTZFYKNAJURNSYMJRFQQ.
To make the cipertext easier, the letters are usually written in blocks of five. The above is: NBNQQ RJJYD TZFYK NAJUR NSYMJ RFQQ.
5) Encipher: changing from plaintext to ciphertext
6) Decipher: changing from ciphertext to plaintext
7) Key: information that will allow someone to encipher the plaintext and also decipher the cipertext.
Afterwards, the educator might provide an example of encryption such as Mononalphabetic Substitution Ciphers.
A. The Additive (or shift) Cipher System
In this method, each plaintext leter is replaced by another character whose position in the alphabet is a certain number of units away. See the pictorial representation below for an example of each letter in plaintext and its corresponding letter in cipher text.
Then, the educator could encourage the students to try their own additive key of 16 to encipher the message "The Eagles will win the Super Bowl". The students should start by completing the chart first.
Other excercises can be given to the students to practice the additive method.
B. Modular Arithmetic
Although secondary students do not typically learn about modular arithmetic, I think it would be beneficial for the students to be exposed to this mathematical concept to better understand cryptography. The educator could start this discussion by relaying this scenario:
After this scenario, the educator can explain that this process of subtracting off the value you don't need (such as 12 in the time example) is the essence of modular arithmetic. The instructor can then proceed to demonstrate and allowing the students to practice modular arithmetic by solving the following problems:
C. The Multiplicative Cipher
This cipher is a direct application of modular arithmetic using the equation
. So if k = 3, we have an example of the following table to find the ciphertext.
Then, the students can use the above table to encode, "The answer is seventeen."
The educator can then suppose the key was 11. Have the students complete the table below and encode several messages of the educator's choosing.
After these excerises, there should be a discussion of how to calculate inverses in modular arithmetic. After demonstrating several examples, have the students practice this skill by completing this chart. Given the key k, find the inverse of k if possible.
Present this scenario to the students. Suppose you were given this message and were told that is was created by a multiplcative cipher.
YQDIU SOQJG MGQQQ TWPGF UMGQX BGTKY FUUV
You wish to respond, but how will you decipher it? Have the students work in pairs to figure this out. Then ask the students how they would encode a response of "No problem" to send back.
Another common ciphering method is the Polyalphabetic Substitution Cipher. A common application of this ciphering method is by using matrices. Depending on which secondary level math course cryptography is discussed in, students may already have a rudimentary knowledge of matricies. If not, this can be an interesting interdisciplinary connection. To use matricies in cryptography, students would first have to be comfortable solving such matrix problems:
Now that we have an elementary idea of how to work with matricies, students can be introduced to the more sophisticated cipher system called the Hill Cipher.
Steps of the Hill Cipher Method:
1. Choose a 2 x 2 matix of numbers mod 26 to act as the key.
2. Take consecutive pairs of letters in the plaintext and convert the numbers to mod 26.
3. Write these numbers in a 2 by 1 (2 rows, 1 column) matrix.
4. Multiply these two matricies mod 26.
5. Convert these numbers to ciphertext.
The Hill Cipher Method can also be adapted in high school classrooms to be completely demonstrated on a graphing calculator, such at a TI-83 or TI-84.
Here is an example. Let's convert the word "book" to a Hill Cipher:
So the word "book" gets converted to "CLDS".
Note that the letter “o” appears consecutively in the plaintext, but not in the ciphertext.
Blocking each letter of plaintext into 2 consecutive letters is called a digraph model. If there is an odd number of letters in the plaintext, you have to add an extra letter, usually at the end, usually an “x.”
You can group them into blocks of 3 consecutive letters is called a trigraph model. The greater the number of letters in a block, the harder it is to decipher the message.
Then the students could encode the message "Hi Ron" with the key
. There will be 6 letters in the ciphertext.
To convert a plaintext message into ciphertext using the digraph model of the Hill system involves a lot of work. The spreadsheet that goes along with this document can encode plaintext very quickly. Go to the Hill Digraph Method sheet and input your message into cell F2 (no spaces, all lower case, 120 characters maximum).
You now need to input your key matrix. We will call the key matrix
. and you input them in the
box in cells B10, C10, B11, and D11. Not every matrix can create a ciphertext as we will see later.
Experiment with some of them.
So, of course, the question becomes: how do you decipher a message that was encrypted by the digraph Hill method? It isn’t easy, nor should it be. But it can be done if you have the key.
First, realize that there are 26 numbers that could be a, b, c, and d (mod 26). So there are 26
permutations of 26^4 or 456,976 possible encryptions of a plaintext message.
To reverse the procedure, we need to find another matrix to multiply the ciphertext so that we get back to the original plaintext. We will call this new matrix c, d, e, and f. So by the same argument, there are 456,976 possible decryptions of a ciphertext message. We will reduce this number somewhat later. But if it took 5 seconds to check out each one (a gross underestimation), it would take 1.75 years to go
through all of them.
Obviously we need to find this “inverse” key, the matrix c, d, e, and f, that will “undo” the original key a, b, c, and d. To accomplish this, we need to go back into matrix theory.
First, we define the determinant of a 2 by 2 matrix a, b, c, and d ad - bc. So the determinant ofThe determinant of
Depending on the abilities of the students, the inverse of matrix A can be done by hand or using a graphing calculator.
Now, to summarize the Hill method, see the example below.
Suppose we would like to encipher and decipher the word "go" using the key matrix
.
It would then be beneficial to allow students time to practice finding the inverses of matricies, preferably by using technology such as a TI-84 graphing calculator. Some sample problems are given below.
Now comes the interesting (and hard) part. Let’s suppose you received this message:
KMYEM UPAUO AHOJR YUKTT CACQC XXIYE DKSTQ ZXDAW
Let’s also assume that you know it was created by a Hill digraph cipher system. (again, it may seem unlikely that you would know this, but we will see later that there is a reason that this information might be public knowledge). Still, where do you begin?
We know that there 157,248 possible combinations of a, b, c, and d mod 26. We can simply try them with the spreadsheet.
Type KMYEMUPAUOAHOJRYUKTTCACQCXXIYEDKSTQZXDAW in cell N27 (make sure that there is a message at least that long in F2 - doesn’t matter what). Now try some combinations of a, b, c, and d mod 26.
After a few trials (unless you were unbelievably lucky) you should be convinced that this is not the way to proceed. If you could get some help, it may make the process easier. 100 people working on this would give each person approximately 1,572 of them to try. Still, that would be expensive. Of course, you could program the computer to run through them all. Still, you would have to examine each by sight to see the right answer which, hopefully, will pop out at you. That, still, is a good option. But we would like to solve it without use of a computer, except for checking the final answer.
But, again, where do you begin? So I will give you a clue. Suppose you know that the message is about Bob. This is not as farfetched as it sounds. Many times, a message is sent and the person receiving it has some idea what it is about. That knowledge is called a “crib.” For us, it is a foothold into the key.
When the allies deciphered German messages during World War II, frequently they discovered cribs to help them. If a message came from a certain sector where Colonel Klink was commanding, it was normal that the message would mention who was sending it and hopefully, the word “Klink” might appear in the ciphertext. So it might make sense that the word “Steve” might appear in the message above. We will start with that premise.
Then we are saying that via the enciphering process that the letters on top converted to the letters on the
bottom:We are searching for variables a, b, c, and d mod 26 that could make this happen. The positions for “stev” are 19, 20, 5, and 22. The position for ”YEMU” are 25, 5, 13, and 21.
So these two equations must be true:
And solve each independently. Solving them can be done using technology such as the TI-84 or by hand to get the solution of
. The determinant is odd so it is possible. BINGO!
The educator can then provide time for students to practice several codes. Below are just two example of practice problems with a differentiation option.
For the secondary level, I would anticipate that the above ciphering and deciphering methods explained above would be beneficial and quite enjoyable. Although there any many other monoalphabetic and polyaphabetic ciphering methods, it is important that students understand the core differences between determining which method was used to encrypt a message.
Deciding between Monoalphabetic and Polyalphabetic:
You have been given a message but have no idea whether or not it was created by monoalphabetic
(every unique letter of the plaintext is always replaced by the same letter) or polyalphabetic (there is no
guarantee that unique letters are always replaced by the same letters).William F. Friedman is said to be the dean of modern American cryptologists. He did most of his work
from 1920 through 1955. he is responsible for the Friedman test, a test which will help determine
whether an enciphered message is monoalphabetic or polyalphabetic.The Friedman test determines what is known as the Index of Coincidence (IC), the probability of two
letters randomly selected from a text being equal, suggesting whether the underlying enciphering
scheme is monoalphabetic or polyalphabetic.
To compute the IC, let:
n = number of letters in the text;
a = number of a' s in the text;
b = number of b' s in the text;
.
.
.
z = number of z's in the text;Friedman determined that the Index of Coincidence is:
If a message is from a monoalphabetic cipher, certain letters will appear more than others. The IC for the English language is approximately .065.
If a message is from a polyalphabetic cipher, letters will have the same chance of being chosen; no one letter should appear more than others. If all letters have the same chance of being chosen, the IC is approximately .038, about half of the IC for the English language.
After this discussion, the educator could allow the students to work in pairs and assess whether the following ciphertext came from a monoalphabetic and polyalphabetic ciphering scheme.
An analysis of the frequency of letters gives:
From this, the IC (there were 114 letters in the message) comes out to be .038508. This is very strong evidence that the message came from a polyalphabetic ciphering scheme.
VIII. More information regarding Public Key Cryptography
It is also important to be able to respond to student questions such as:
Why would you know the actual enciphering scheme of an encoded message? If secrecy and privacy is so important, why help someone out by telling them the actual scheme? Although a lot of work is still need to decipher the message, why give someone a head start?
The answer:
Suppose Bob owns a business and he wishes to communicate with one of his employees, Alice, in privacy. First, they must meet in secret to decide on one of the classical systems of enciphering. Then they will have to decide on a key. If they cannot meet, they will need a trusted associate to act as a go-between. Still, that is not too much work. But suppose Bob’s business involves 100 employees, each wanting to talk with each other in privacy. That would involve 4,950 enciphering schemes with 4,950 keys.
If the business was huge (like Bank of America), and there were a million people all wishing to communicate with each other, it would involve about 500,000,000 (about half a trillion) enciphering schemes and keys.
Public Key cryptography systems is based on publishing, for the entire world to see, the means by which messages are enciphered. This is done with the full assurance and confidence that this knowledge alone does not lead to the deciphering process being discovered, at least in a reasonable amount of time.
Before public key cryptography was invented, cryptographic systems, now referred to as private key or classical systems, depended for their security on the knowledge that both keys (encryption and decryption) were kept private.
In these systems, if the encryption key is known, the decryption key is known as well. In the cases of an additive or multiplicative system, the decryption key is known immediately. In the case of an affine method, some work is needed to find the decryption key. In the case of the Hill digraph system, having a crib can help us find the key. But even without a crib, computers, even home computers, can find the key by trial and error (called the method of exhaustion) in a short period of time. In short, these methods are insecure.
With public key cryptography, knowing the key for the enciphering process does not give you the key for the deciphering process. These systems use keys with such large numbers (often over 100 digits in length) that using trial and error to decipher would take 3.8 billion years, even with a state-of-the-art computer.
Any two people with entries in the public-key directory could communicate with each other without any prior exchange of keys. If Alice wants to send a message to Bob, Alice looks up Bob’s enciphering key in the public directory. She writes her message, then uses Bob’s enciphering key to get a ciphertext which she send to Bob. Bob then uses his secret deciphering key (not public) to convert the ciphertext back to the original message. Only Bob can decipher the message because he is the only person who knows the deciphering key.
Using this system, messages can be authenticated and protected from forgeries.
