The RSA Algorithm:

Background, Mechanics, Mathematics, and Algorithms;
Everything anyone needs to implement RSA encryption.

by

Ray Dillinger © Nov 1995-Feb 2002

Background:

The RSA algorithm for public key cryptography is now in the public domain. That means it is legal for everyone to use for whatever reasons and means they want to use it for. The only thing you need in order to use it is to understand it well enough to implement it. Hence this page.

Mechanics of RSA encryption:

The "key" of an RSA cipher is three numbers: The first is Xpub, the public exponent, the second is Xpriv, the private exponent, and the third is Mod, the modulus.

The message M (which must be shorter than Mod) is interpreted as a number. It is broken into chunks as necessary to meet the length requirement. This number is raised to the power of Xpub, modulo Mod, to give C, the ciphertext.

C may in turn be raised to the power of Xpriv, modulo Mod, to give M.

The public key is the pair (Xpub, Mod). The private key is the pair (Xpriv, Mod). If Bob and Alice want private communications, they each generate a pair of keys, then may exchange public keys using a non-secure channel, such as email or telephone. Thereafter, when Bob desires to send Alice a message, he can encrypt it using Alice's public key and send it via a non-secure channel. When Alice receives it, she uses her private key to decrypt it and read it. The nice part is that Sam, even though he has been able to read every message sent over the non-secure channel, cannot decrypt that message; he would need Alice's private key, which she has never had to send.

But Sam can use Alice's public key to send a message to Alice, forging Bob's name. So Alice needs a way to verify that the messages she gets from Bob are actually from Bob. All she's really sure about is that if Bob has been careful, Bob is the only one who has Bob's private key. So if Bob first encrypts his message using his own private key, then attaches a copy of his public key, then encrypts this whole new message with Alice's public key, Alice has some assurance: She can first decrypt the message with her own private key, then read Bob's public key in cleartext, make sure it matches the public key she has recorded for Bob, and then decrypt the message using Bob's public key. Sam may intercept the message, but he can't read it without Alice's private key. Furthermore, Sam can't generate this type of message without Bob's private key. It is "digitally signed" by Bob, and Sam is unable to duplicate Bob's signature.

Actually, Bob doesn't need to attach his public key; if Alice already knows his public key, then any information that identifies Bob ought to be enough, because she can then look it up.

Digital signing does not usually require that the entire message be encrypted; instead a small "signature block" is usually calculated from the message itself, using some method which attempts to ensure that a change in the message would result in a change in the signature block. Then the signature block is encrypted using Bob's private key, and the whole is encrypted using Alice's public key. When the message arrives, Alice decrypts the message using her private key, then computes the signature block from the message, then decrypts the signature block using Bob's public key to see if it matches.

Now, suppose Alice wants to send a message to Bob and Carol and Donald, which may be read by any of them. She first generates a new key pair, then prepares a short message to each of them using the technique above; in this message she discloses the key which may be used to read the message. She then encrypts the message using the new key, attaches the short messages, and sends it.

When this message is received by one of the intended recipients, they will decrypt the header with their own private key. Doing so, each will find the short message to them, containing the decryption key and Alice's public key (the short messages to other recipients will be further scrambled by this process). Decrypting the message, first with one and then with the other, they will regain the cleartext.

Many other permutations are possible.

Mathematics of RSA encryption:

Exponentiation under a modulus is easier than exponentiation followed by a modulo operation. Let's face it, we're talking about taking very large numbers to very large powers here, and it would be totally easy to choke your computer.

So, for an 'easy' example, using numbers big enough to show off the method but small enough to write: Suppose we want to take 299 to the 153rd power, under a modulus of 355. The first thing we do is to note that 153 equals 128 + 16 + 8 + 1 (binary decomposition), and that therefore,

299^153 = 299^128 x 299^16 x 299^8 x 299^1.

Now, forgetting for the moment about the scary looking terms on the left, we can compute the one on the far right; it's 299, of course. Under the modulus, it's still 299. But knowing the one on the right, we can compute the one next to it: Doubling the powers by squaring the numbers, and applying the modulus to intermediate results, gives:

                     299 mod 355 is 299.  (299 = 299^1 mod 355)  
299^2 = 89401, but 89401 mod 355 is 296.  (296 = 299^2 mod 355)
296^2 = 87616, but 87616 mod 355 is 286.  (286 = 299^4 mod 355)
286^2 = 81796, but 81796 mod 355 is 146.  (146 = 299^8 mod 355)
146^2 = 21316, but 21316 mod 355 is 16.   ( 16 = 299^16 mod 355) 
 16^2 = 256,   and 256   mod 355 is 256.  (256 = 299^32 mod 355)
256^2 = 65536, but 65536 mod 355 is 216.  (216 = 299^64 mod 355)
216^2 = 46656, but 46656 mod 355 is 151.  (151 = 299^128 mod 355)

so

299^153 mod 355 = (151 x 16 x 146 x 299) mod 355

which looks a whole lot easier. Now, calculating the product and applying the modulus to intermediate results, we get:

151 x 16  =  2416, but  2416 mod 355 is 286.
286 x 146 = 41756, but 41756 mod 355 is 221.
221 x 299 = 66079, but 66079 mod 355 is  49.

so

299^153 mod 355 = 49.

And that is how you take a large number to a large power under a large modulus without causing your computer to choke. The constant application of the modulus operation to intermediate results prevents you from having to deal with any number larger than the square of the modulus in any case, and saves you from having to compute a number too big to fit in memory. On ordinary machines, you can't do this type of calculation in hardware registers as we are talking about (often) 1500- bit moduluses; but given any finite modulus, you do have an upperbound for the largest number you'll have to work with. You can code your routines for standard operations on that size number any way you like.

Generation of Key pairs:

What we are looking for, is an exponential inverse under a modulus, ie, numbers Kpub, Kpriv, and Mod, such that

for any M, (Kpriv ^ ((M ^ Kpub) mod Mod) mod Mod) = M.

Euler developed Euler's Totient Function, denoted J(N), which is defined as the number of numbers in the range (1...N-1) which have no prime factors in common with N.

In order to calculate J(N), it is necessary to know the prime factors of N, and factoring numbers which are compositions of very large primes is difficult. This difficulty is what the security of RSA encryption is based on. So in practice, what you do is choose two very large prime numbers P and Q, and multiply them together to get a Mod that you can use for N; that's really the only way to know the factors P and Q without having to factor Mod. Because you know P and Q, J(Mod) is easy:

Mod = (P x Q) ==> J(Mod) = (P-1)x(Q-1).

Now, pick a number Kpub which has no prime factors in common with J(Mod), and we need to find a Kpriv which is its exponentiation inverse mod Mod. If Kpub has any factors in common with J(Mod), then Kpriv will not exist. In practice, this is easy; we either pick a prime number which is not a factor of J(Mod) for Kpub, or pick prime numbers that we know are not factors of J(Mod) to multiply together to get Kpub. Thus, we never need to factor Kpub to find out what its factors are, and incur only a small number of individual divisibility checks on J(Mod).

J(Mod) is important, because when we are manipulating exponents in arithmetic mod Mod, the exponents must be manipulated in mod J(Mod). For example,

(T^E)^D = T^(E x D)

==>

((T^E)^D)mod N = (T^ ((E x D) mod J(N)) mod N.

Which is a little bit magical, but all the math professors agree on it.

Anyway, this reduces our requirement to finding a Kpriv such that

(Kpub x Kpriv) mod J(Mod) = 1.

This is straightforward; You can successively subtract smallest known multiples of Kpub to get new multiples of Kpub which, under the modulus, are smaller until ultimately, you reach 1. Having kept track of the multiples, you can then sum them under the modulus to get Kpriv.

For an example, consider the case where our two primes P and Q were 89 and 97. Mod is 8633, and J(Mod) = 8448. Now, we pick a Kpub which has no factors in common with 8448 -- say, 49. We are looking for the number Kpriv such that

(49 x Kpriv) mod 8448 = 1.

(because 173 > 8448/49 > 172, we pick as our starting point the factor 173.)

173 x 49 = 8477, and 8477 mod 8448 = 29 at factor 173.

Subtracting 29 (the factor at 173) from 49 (the factor at 1) gives us 20 at a factor of (1 - 173 = -172, mod 8448 = ) 8276.

subtracting 20 (the factor at 8276) from 29 (the factor at 173) gives us 9 at a factor of (173 - 8276 = -8103, mod 8448 = ) 345.

subtracting 9 (the factor at 345) from 20 (the factor at 8276) gives us 11 at a factor of (8276 - 345 = ) 7931.

subtracting 9 (the factor at 345) from 11 (the factor at 7931) gives us 2 at a factor of (7931 - 345 = ) 7586.

Subtracting 2 (the factor at 7586) from 9 (the factor at 345) gives us 7 at a factor of (345 - 7586 =) 1207.

Subtracting 2 (at 7586) from 7 (at 1207) gives us 5 (at 2069).

Subtracting 2 (at 7586) from 5 (at 2069) gives us 3 (at 2931).

Subtracting 2 (at 7586) from 3 (at 2931) gives us 1 (at 3793).

So, our key 49, has an exponentiation inverse of 3793, under the modulus 8633.

So for all M (barring the possibility of errors in the above),

M^49 mod 8633 = C implies that C^3793 mod 8633 = M.

That's the basic key-generation technique, but it still needs an optimization to guarantee that it will run in logarithmic rather than arithmetic time complexity.

Note that the last four lines are just subtractions of 2 from the previous result. When we had factors at 9 and 2, we could have *divided* 9 by 2, realized that we were about to subtract 2 four times, and instead subtracted the product 4x2, after calculating the factor at 8 (4x the factor at 2, under the modulus). Similarly, We could have done a division to find that 9 would go into 20 twice, then performed multiplication to find the factor at 18, saving us a few steps of this process.

This factoring is a crucial step in implementing RSA encryption -- if you don't do it the generation of keys can take a huge amount of time. To understand how huge, consider the case where we could get down to two fifty-digit numbers, but the difference between them was only ten. You'd have to subtract ten more than 10E49 times without the optimization, but with it you only have to do a division, two multiplications, two modulus operations, and two subtractions.

Difficulty of breaking RSA:

In order to break RSA encryption, you have to factor Mod, from the public key. So breaking RSA is as difficult as factoring. The existence of RSA cryptosystems has sparked a lot of research into factoring, and better factoring algorithms have been discovered recently; the fastest known factoring algorithm for linear computers at this writing is the 'number field sieve' which can factor any number in an amount of time not predictable, but uniformly distributed between zero and time proportional to the limit

exp(log^{1/3} n log^{2/3} log n)

where n is the length of the number in bits.

Addendum: In January 2002, Daniel J Bernstein published a paper outlining a hardware implementation of the number field sieve that reduces the cost of factoring substantially. It turns out that while the above estimate of factoring time is appropriate for linear implementations, there are non-linear implementations for some of the subparts of the algorithm that can be implemented as integrated circuits. The result is that the cost of factoring a number of 2n bits in custom hardware is roughly the same as the cost of factoring a number of n bits in a general-purpose computer using the standard Number Field Sieve. The remainder of this discussion is revised to take this into account.

Addendum (2 September 2002): Recently some researchers have discovered methods for fabricating a quantum chip with a million qbits. This permits the use of Shor's Algorithm to do factoring of an N-bit number in O(log N) time. This fundamentally compromises the security of the RSA public- key cipher, and it should not be used in the future. The remainder of this discussion refers to classical (linear computers) and is of academic interest only, as RSA is now a dead cipher. If you are interested in a public-key cipher which gives forward security or which is secure against opponents with a lot of money to spend on custom hardware, you should stop reading now.

It is important to remember that the limit given above is an upper bound; in theory, the first pair of numbers tried might be the factors, resulting in a rapid factoring time. It is astronomically unlikely, however. For 3072-bit keys on present (2002) hardware, the "limit" presented above exceeds by an order of magnitude the expected epoch of the heat death of the universe. Assuming a uniform distribution of probability, the chances of a solution before that time are less than ten percent.

In 2001 and earlier, most experts believed that RSA would be secure "forever" with a key length of 2048 bits or more, unless some fundamentally new and unexpected factoring algorithm were discovered. Daniel Bernstein's paper on hardware for factorization represents a new method of implementing the Number Field Sieve that has greater efficiency, and is, in an unanticipated way, exactly such a breakthrough. According to current (February 2002) information, RSA with a 6144 (6K) bit key should be considered "secure forever" barring yet another completely unexpected breakthrough in factoring. And as of September 2002, the technical ability to fabricate Qchips, combined with Shor's algorithm, which had been long known, provided such a breakthrough in factoring, this time rendering RSA effectively useless.

My recommendation at this time is to quit using RSA entirely. While quantum chips may not exist outside simulations yet, they have been demonstrated to be feasable and capable of being fabricated, and at this point it's just a matter of time until they find their way into the hands of people who are interested in breaking the security of applications.