2012 May 8,
Carleton College, Spring 2012
Prof. Joshua R. Davis, , Goodsell 106B, x4473
In our course, we have studied various classical cryptosystems, such as Rot13, the Caesar cipher, and the substitution cipher. These cryptosystems are not in active use today, because they are too easy to break. In these notes, we describe another cryptosystem, called RSA, that is in active use.
The basic idea is this. Using some mathematical trickery, I find a pair of numbers that constitutes a encryption key, and a third number that constitutes a decryption key. I make the encryption key publicly available, and I keep the decryption key secret. Then, anyone who wants to send me a message can obtain my encryption key, encrypt their message, and send me the encrypted version. When I receive the encrypted message, I use my private decryption key to decrypt it.
I begin by choosing two distinct large prime numbers p and q. (Recall that a prime number is an integer, greater than 1, whose only divisors are 1 and itself. For example, 17 is prime, but 18 is not.) In practice, these primes are as much as 1000 digits long. We won't go into the mathematics needed to find them; just trust that there is an algorithm for generating such large prime numbers.
I then compute n = p q and m = (p - 1) (q - 1). The number n is one part of my encryption key.
I then choose a number e to serve as the other part of my encryption key. This e must satisfy 0 < e < m and GCD(e, m) = 1. In order to prevent people from breaking our cryptosystem, we don't want to pick e in any simple mechanical way. So let's pick e randomly:
# Returns an RSA encryption key for the given m = (p - 1) (q - 1).
# Input: Integer m >= 2.
# Output: Integer e such that 0 < e < m and GCD(m, e) == 1.
def encryptionKey(m):
e = random.randint(1, m - 1)
while gcd(m, e) != 1:
e = random.randint(1, m - 1)
return e
I then compute my decryption key d. Namely, d is the unique number 0 < d < m such that (e d) % m = 1. This number can be computed using an "extended" version of the Euclidean algorithm:
# Returns c and d such that a c + b d == gcd(a, b).
# Input: Integer >= 0. Integer >= 0. Assumes that not both are 0.
# Output: List of two integers.
def gcdCombination(a, b):
if b == 0:
return [1, 0]
elif a == 0:
return [0, 1]
else:
cd = gcdCombination(b, a % b)
return [cd[1], cd[0] - cd[1] * (a / b)]
# Computes the inverse of e modulo m.
# Input: Integer. Integer. Assumes 0 < e < m and GCD(m, e) == 1.
# Output: Integer d such that (e d) % m == 1.
def inverse(m, e):
return gcdCombination(m, e)[1] % m
The two numbers n and e together constitute my encryption key. I make them publicly available, so that anyone can send me an encrypted message. For example, I post these numbers to my web site, or I add them to my e-mail signature.
How exactly do you send me an encrypted message? Well, first you need to have my public key (n, e). Just as your e-mail software can store the addresses of people whom you e-mail frequently, it can also store the public keys of those people (or at least some e-mail software can).
You express your message as a number t such that 1< t < n. The details of how to do this well are rather complicated, so we won't go into them, but I hope that it's not unbelievable. After all, all data within a computer are numbers, so any message transmitted by computer is inherently numeric. And if the message is too big to fit into a number smaller than n, then we can break it into pieces and send each piece separately.
Once you have my public key (n, e) and your message t, you simply compute
c = te % n.
This number c is the ciphertext — the encrypted message — that you transmit to me.
When I receive the number c, I simply raise it to the dth power, and mod out by n. I can do this, because I know the decryption key d. The result that I get just happens to equal the original number t, that you wanted to send:
t = cd % n.
In order to understand why the algorithm works — that is, outputs the same t that you chose in the first place — you need to know a little bit of mathematics, that you may never have seen before. There are two crucial facts:
Mod Out Whenever You Like: For any integers a, b, c,
(a b) % c == ((a % c) (b % c)) % c.
Euler's Theorem: If p and q are distinct primes, 0 < t < p q, and t is divisible by neither p nor q, then
t(p - 1) (q - 1) % (p q) == 1.
Also, you have to remember how e and d were chosen. Their product is 1 more than a multiple of m. So there is some number k such that
e d == k m + 1.
Now, the net effect of the RSA encryption and decryption is to take the original number t, raise it to the eth power, and raise that to the dth power. So it is computing
(te)d == ted == tkm + 1 == (tm)k t == (t(p - 1)(q - 1))k t.
We just want to know what this number is modulo p q. The Mod Out Whenever You Like rule implies that I can mod out t(p - 1)(q - 1) by p q, and, when I do, Euler's theorem tells me that the answer is simply 1. Therefore,
(t(p - 1)(q - 1))k t == 1k t == t
(where I've omitted writing a lot of "% (p q)", to avoid clutter). So computing (te)d really does bring us back to t.
There is one detail here, where I've been a bit dishonest. Euler's theorem applies only if t is divisible by neither p nor q, but the message t might be divisible by one or the other. The result is still true, even if t is divisible by one or the other, but the proof given above is not quite good enough to handle that rare case. Let's not go through a complete proof here.
Recall that the numbers n and e are made public, while the numbers p, q, m, and d are kept private. If any one of these four numbers were accidentally made public along with n and e, then an attacker could break the cryptosystem by deducing d. (How?) Alternatively, if an attacker were clever enough to deduce any of these numbers from n and e, then he could break the cryptosystem.
One approach to breaking RSA is to factor n into the numbers p and q. There are several extremely clever factoring algorithms, but even the best of them takes an astronomical amount of time to factor large integers. It may be that there is no fast algorithm for factoring, or it may be that we just haven't found one yet. Anyone who discovers such an algorithm would be instantly famous, unless she kept it to herself and brought down the financial system instead. The film Sneakers is a comedy/thriller along those lines.
Another approach to breaking the cryptosystem is to compute m somehow. In fact, m = (p - 1) (q - 1) is simply the value of the Euler totient function at n. However, there is no known fast algorithm for computing this function, without knowing the prime divisors of n. So this attack seems to be roughly as difficult as factoring.
In summary, no one has ever proven that RSA is safe from such attacks, but the experts in the field have not succeeded in breaking it, and they suspect that it is secure for the near future, because coming up with a fast factoring algorithm will probably require the invention of new mathematical tools by many people.
Both the encryption and decryption steps amount to exponentiation: raising one number to an integer power. How long does this take? Well, how do you raise a number to a power? You just multiply the number by itself, that many times. For example,
64 == 6 * 6 * 6 * 6.
In general, the number of multiplications required is one less than the exponent. That is, computing ab is O(b).
There is a much faster algorithm for exponentiation, called repeated squaring. Here's the basic idea. Suppose that I want to compute 61024. I can square 6 to get 62, then square that to get 64, then square that to get 68, and so on. After 10 steps I have 1024. So, instead of 1024 multiplications, this algorithm requires only 10.
Of course, 1024 is a special number, in that it's a power of 2. What if our exponent is not so convenient? Suppose that we want to compute 61099. Well, we can break 1099 into powers of 2, like this:
6 == 61024 664 68 62 61.
So, to compute 61099, we use repeated squaring to compute 62, 64, ..., 61024. Then we figure out which of these powers are needed to make 1099 (how?), and we multiply them together. This algorithm computes ab in time O(log b) (why?).
By the way, raising numbers to high powers like this produces extremely large numbers. But the Mod Out Whenever You Like rule lets us mod out by p q on every step. So we never need to deal with any number bigger than (p q)2.