Fathom: The Source for Online Learning     » Media Index  
 
Help About Us Course Directory
Browse Fathom


 
 
 
The Mathematics of Public Key Cryptography
From: Columbia University | By: Deane Yang

EDITOR'S INTRODUCTION | Numerous e-businesses employ public key cryptography systems to protect the security of their electronic transactions. At their heart, many of these systems employ the RSA algorithm. Deane Yang, professor of mathematics at Polytechnic University and a former postdoctoral associate at Columbia University, reviews the mathematical fundamentals of this successful encryption system.


ntil the 1970s, the only means of exchanging secure information were variants on private key cryptography, so called because the sender and receiver of encrypted messages had to share and keep private a common cipher used for both encoding and decoding messages.


In 1976 Whitfield Diffie and Martin Hellman proposed an innovative, alternative approach: What if there were a cryptographic system in which the key used to encrypt a message is different from the key used to decrypt it? This system is now called public key cryptography, in which one publicly distributed key performs one function (either encoding or decoding) and another key, kept private, performs the reverse function. This system remained largely hypothetical until three mathematicians--Ron Rivest, Adi Shamir and Leonard Adelman--used large primes to create an algorithm that gained wide acceptance as the backbone for public key cryptography. The RSA algorithm relies on the ease of doing modular arithmetic and the difficulty of factoring large numbers.

Modular arithmetic: the basis of RSA

To do modular arithmetic, you first fix a number m, which is called the modulus. Modular arithmetic with modulus m is called arithmetic mod m.


Arithmetic mod m uses only the numbers 0, ..., m-1. To do modular arithmetic, you just do ordinary arithmetic (addition, subtraction and multiplication). If, however, you end up with a number that is not 0, ..., or m-1, you just subtract the appropriate multiple of m to obtain a number that is between 0 and m-1. For example, in arithmetic mod 2 the only numbers permitted are 0 and 1. Ordinarily, 1 + 1 = 2, but the number 2 is not permitted in arithmetic mod 2. On the other hand, if you subtract a multiple of the modulus once, 2 - 2 x 1 = 0, you reach zero, a number that is permitted. So, we say that 1 + 1 $equiv$0 mod 2. (We use the funny equals sign, $equiv$, to emphasize that we are doing a non-standard kind of arithmetic.) Addition mod 2 has the following addition table:

begindisplaymathbeginarraycvert cc + & 0 & 1 hline 0 & 0 & 1 1 & 1 & 0 endarray enddisplaymath


In arithmetic mod 3, the only numbers permitted are 0, 1 and 2. To compute 2 x 2 mod 3, observe that 2 x 2 = 4 and 4 - 3 x 1 = 1. Therefore, 2 x 2 $equiv$1 mod 3. The full multiplication table mod 3 is the following:


begin{displaymath}begin{array}{cvert ccc} times & 0 & 1 & 2 hline 0 & 0 & 0 & 0 1 & 0 & 1 & 2 2 & 0 & 2 & 1 end{array} end{displaymath}


Given a number x that is less than m and a number d, which does not have to be less than m, you can compute xd mod m two different ways. Remember that xd is the number obtained by multiplying together d copies of x. You can multiply the factors using ordinary multiplication and then subtract the appropriate multiple of m to obtain a number less than m. Or you could do each of the d multiplications using modular arithmetic and automatically get an answer less than m.


For example, suppose you want to calculate 23 mod 3. The first way is just to use ordinary multiplication: 23 = 2 x 2 x 2 = 8$equiv$2 mod 3. Or you could observe that 2 x 2 = 4$equiv$1 mod 3 and therefore (2 x 2) x 2$equiv$1 x 2 mod 3$equiv$2 mod 3.

Creating the keys for the RSA algorithm

To begin creating your public key cryptography system, choose two large primes p and q. The larger p and q are, the more secure your encryption system will be. Until recently, it sufficed to use primes that were approximately 80 digits long. Today, using primes from 100 to 300 digits long is recommended for maximum security. The requirements are certain to increase steadily, as more computing power and better methods for attacking the RSA algorithm become available.


The primes p and q are the basic ingredients used to create your public and private keys. It is important that you never reveal these primes to anyone else. Using p and q, you create three new numbers. Two of them--let's call them m and n--comprise your public key, which will be used by anyone who wants to send you an encrypted message. The third--we will call it k--is your private key. Like p and q, it must not be revealed to anyone else.


First, let m be the product of the two primes p and q,

m = pq.


We will use m as the modulus. The encryption and decryption processes are both done by raising a number to a power mod m. Encryption by the sender is accomplished by raising numbers to the power n mod m; decryption by raising numbers to the number k mod m.


Next, select n and k. Choose a number n such that the numbers n and (p-1)(q-1) have no factors in common except 1. Remember that m and n comprise the public key for the RSA algorithm and can be distributed freely to others who will use them to encrypt messages. Notice that n can be chosen to be fairly small, which means that encryption using the public key can be done quickly.


The number k, which will be your private key, must be chosen so that (p-1)(q-1) is a factor of the number kn - 1. It is not obvious that there is any number at all satisfying this requirement. The fact that there are infinitely many numbers satisfying the requirements for the private key follows from a classical result in number theory called Euclid's algorithm.


Since k is your private key, you must never reveal it to anyone. You also cannot reveal p and q, because if you do, then it is very easy for someone to find a number k' that satisfies the requirements for a private key. That person could then use k' to decrypt encrypted messages intended for your eyes only.

Encrypting and decrypting a message: an example

Suppose you have established a public key cryptography system and distributed m and n to counterparties in order to exchange secure messages. One of these counterparties wants to send you an encrypted message. First, the message to encrypt must be converted into a sequence of numbers less than m. The easiest way to do this is to convert each letter in the message into a number from 1 to 26. A better way is to group the message into blocks of letters and convert each block into a larger number. This results in fewer but larger numbers. There is no danger of getting numbers larger than m, because m is much too big.


The sender then encrypts each number by raising it to the power n mod m. The resulting set of numbers are sent to you.


When you receive the numbers, you decrypt the message using your private key k. If you raise each number in the message to the power k mod m, you receive the sender's original sequence of numbers. The numbers can now be converted back into the sender's message by converting each number into a block of letters.


Let's go through an example using small primes. Suppose you choose the primes p = 3 and q = 7. The modulus is
m = pq = 3 x 7 = 21. To find n, we first note that (p-1)(q-1) = 2 x 6 = 12. We need to choose n to be less than 21 (the modulus) and to have no factor in common with 12. There are many possibilities, but the easiest one is n = 5. The numbers 21 and 5 form your public key.


Next, the private key k must have the property that (p-1)(q-1) is a factor of the number kn - 1. In other words, k should be such that 12 divides into the number 5k - 1 evenly. Here, we can choose k = 17. Then 5k - 1 = 5 x 17 = 84, which is a multiple of 12.


Now, armed with the keys of our public cryptography system, we send out m = 21 and n = 5 to our counterparties. Suppose someone wants to send us a message and that the message corresponds to the sequence of numbers 10, 2 and 4. These numbers are encrypted by raising them to the power n mod m, or, in our system, power 5 mod 21:
105 = 10 x 100 x 100
$equiv$ 10 x 16 x 16 mod 21
= 10 x 256
$equiv$ 10 x 4 mod 21
$equiv$ 19 mod 21
25 = 32
$equiv$ 11 mod 21
45 = 4 x 16 x 16
= 64 x 16
$equiv$ 1 x 16 mod 21
= 16

The sender would therefore send you the numbers 19, 11 and 16.


You decrypt these numbers by raising each of them to the power 17 mod 21. For example, if we raise 19 to the 17th power mod 21, we get:
1917 = 19 x (19 x 19)8
= 19 x (361)8
$equiv$ 19 x 48 mod 21
= 19 x (16)4
= 19 x (256)2
$equiv$ 19 x 42 mod 21
= 19 x 16
= 304
$equiv$ 10 mod 21

Continuing like this, the encrypted numbers 19, 11 and 16 are transformed back to the original sequence of 10, 2 and 4.


How do we know that this procedure always works and that raising to the n power mod m and raising to the k power mod m always undo each other? This fact is deduced from a classical result in number theory known as Fermat's Little Theorem (which should not be confused with the more famous Fermat's Last Theorem, proved recently by Andrew Wiles).


Note that you can reverse the role of the keys. Suppose you want to send someone a message and you want them to know that the message is definitely from you. You can encrypt your message by converting it into numbers less than m and raising each number to the power k mod m The recipient can decrypt the message by raising each number to the power n mod m. Since encryption requires the number k, which is known only to you, the recipient knows that you are the only possible sender of the message.

Cracking the RSA encryption system

The most obvious way to crack the RSA system is to use the recipient's public key, the numbers m and n, to find the recipient's private key k. Actually, you do not need to find the exact same private key used by the recipient. All you need is any number k' that meets the requirement that (p-1)(q-1) is a factor of the number k'n - 1. Given any such number k', you can decrypt an encrypted number by raising it to the power k' mod m.


In principle, there could be a way to find a private key k' directly, without having to find the primes p and q first. In practice, there is no known strategy for finding a private key k' directly that would be faster than simply factoring the number m, finding the primes p and q, and finding k' using p and q.


On the other hand, if the primes p and q are chosen large enough, say, 100 digits each, then m will be a 200-digit number that cannot be factored within any reasonable amount of time. Much effort has been expended to try to factor large numbers like m quickly. The record so far is the factoring of a 155-digit number using nearly 300 computers and taking about four months.


The size of these numbers assures the security of RSA encryption today. Note, however, that no one knows for sure that factoring a 200-digit number requires so much computing power and time. It is possible that someone could find a revolutionary new approach that can factor a 200-digit number in a few hours or even minutes. We do not think this will happen, because too many brilliant people have already given their best efforts to this challenge. Still, sudden surprising advances in mathematics do occur. If factoring large numbers became feasible, it would immediately cripple all Internet activities--such as e-commerce--that rely on secure communication.

The best-known methods for factoring large numbers

There is no single best method for factoring a number, as most numbers have many factors. For such numbers the best method is the elliptic curve factorization method developed by Hendrik Lenstra. Naturally, the numbers used in RSA encryption are those that cannot be factored quickly by Lenstra's method. For such "hard" numbers that are approximately 100 digits or less, the quadratic sieve method developed by Carl Pomerance is the best-known method for factoring. For larger numbers, the most effective method is called the general number field sieve method, which was introduced by John Pollard and refined by Arjen Lenstra, Hendrik Lenstra and Mark Manasse. The sieve methods can be characterized as sophisticated trial-and-error approaches, which makes them so time-consuming and cumbersome.
 
 
 
 ©2002 Fathom Knowledge Network  Privacy : Terms and conditions : Help : About
  Our Consortium  American Film Institute : The British Library : The British Museum : Cambridge University Press : Columbia University
  London School of Economics : Natural History Museum : New York Public Library : RAND : Science Museum : University of Chicago
  University of Michigan : Victoria & Albert Museum : Woods Hole Oceanographic Institution