**by Neal R. Wagner**

**Copyright © 2001 by Neal R. Wagner. All rights reserved.**

**
NOTE: This site is obsolete. See book draft (in PDF):**

The history of RSA is still fascinating to me because I watched it unfold. In 1976, as discussed in the previous section, Diffie and Hellman introduced the idea of a public key cryptosystem. (Actually, the concept had been discovered earlier in classified work by British and American military researchers, but no one knew this at the time.) Then a 1977 Scientific American article by Martin Gardener talked about a new public key implementation by MIT researchers Rivest, Shamir, and Adelman. This article caught my attention (along with many others), but did not contain the details needed to fully understand the system. A year later the details were finally published and the revolution in cryptography was in full motion. After more than twenty years of research, RSA remains secure and has become the most popular public key cryptosystem.

*Encryption/decryption works:*Ifis the ciphertext corresponding to some plaintext`c = E(m)`, then`m`. (In other words:`m = D(c)`, for any message`m = D(E(m))`.)`m`*Sign/verify works:*Ifis the signature corresponding to some plaintext`s = D(m)`, then`m`. (In other words:`m = E(s)`, for any message`m = E(D(m))`.)`m`*Can encrypt efficiently:*For any message, there is an efficient algorithm to calculate`m`.`E(m)`*Can decrypt efficiently:*For any message or ciphertext, there is an efficient algorithm to calculate`x`.`D(x)`*Public/private keys stay that way:*From a knowledge of, there is no efficient way to discover`E`.`D`- Choose random ``large'' prime integers
and`p`of roughly the same size, but not too close together.`q` - Calculate the product
(ordinary integer multiplication).`n = p*q` - Choose a random
*encryption exponent*less than`e`that has no factors in common with either`n`or`p - 1`.`q - 1` - Calculate the (unique)
*decryption exponent*satisfying.`e*d mod (p - 1)*(q - 1) = 1` - The encryption function is
, for any message`E(m) = m`^{e}mod n.`m` - The decryption function is
, for any ciphertext`D(c) = c`^{d}mod n.`c` **The public key (published):**This is the pair of integers.`(n, e)`**The private key (kept secret):**This is the triple of integers.`(p, q, d)`- At present, ``large'' means at least
bits. For better security each prime should be at least`512`bits long. There are efficient algorithms for generating random numbers of a given size that are almost certainly prime (see below).`1024` -
is then either`n`or`1024`bits long.`2048` - The encryption exponent
can be just`e`. If one is using this exponent, then the primes must be such that`3`and`p - 1`are not divisible by`q - 1`.`3` - The decryption exponent must be calculated, and there are
efficient algorithms to do this, but they require a knowledge
of
and`p`(see the chapter on favorite algorithms). The modulus for division,`q`, is the`(p - 1)*(q - 1)`*Euler phi function*of, where this is a function studied in number theory. One of the function's properties is important in proving that RSA works.`n = p*q` - There are efficient algorithms for carrying out the modular exponentiation needed here (see below).
- Ditto.
- If it is known that
is the encryption exponent, then only`3`needs to be published.`n` - Only
needs to be kept as the secret data for decryption (along with the public`d`and`n`). However,`e`and`p`can be efficiently calculated from the other numbers, and they are needed anyway for the most efficient form of modular exponentiation.`q` *Key generation:*- Using public keys of size 1024 bits, it took about 15-60 seconds to generate two sets of keys on a Sun Ultra 10.
- The key generation has no unusual features. Primes
and`p`are chosen at random, differing in length by 10-20 bits. (If the primes are too close to`q`, then factoring might be easier than it should be.) The primes are also chosen so that`sqrt(n)`and`p - 1`are relatively prime to`q - 1`, because this implementation uses`3`as the encryption exponent.`3` - The only weak point with this key generation that I know of is with the random number generation. For a good implementation, one would need a special generator, with more bits for the seed. (The current generator just uses the number of milliseconds since 1 Jan 1970, and that is clearly insecure.)

*Encryption and Verification:*

This uses an exponent of. The main known weakness here is that the message`3`must be bigger than the cube root of`m`, since otherwise the ciphertext will be`n`, without any modular division. Smaller messages must be padded to make them long enough.`m^3`*Decryption and Signing:*

This can be sped up using the Chinese Remainder Theorem, as is shown in the next subsection.*Combination of Signing and Encrypting:*

This common combination, used to keep the message secret and to authenticate its source, is done in a simple way that checks the lengths of the publicvalues first, using the longer one before the shorter one. Otherwise one might need to use two RSA blocks in some cases.`n`*The Test:*

There is just a simple test of this software, though 1024 bits is a realistic size.*Algorithm.*

The algorithm presented here is described in items 14.71 and 14.75 in the*Handbook of Applied Cryptography*, by Menezes, van Oorschot and Vanstone, CRC Press, 1996. Ifis ciphertext, then RSA decryption calculates`c`, where`c`^{d}mod n.`n = pq`Suppose one calculates

and`v`_{1}= c^{d}mod p`v`_{2}= c^{d}mod qinstead. The Chinese Remainder Theorem (and associated algorithm) allows one to deduce

from a knowledge of`x mod (p q)`and`x mod p`.`x mod q`Arithmetic

should be done`mod p`in an exponent, because`mod (p-1)`(Fermat's theorem).`a`^{p-1}mod p = 1Thus we can use the simpler calculation:

and`v`_{1}= c^{d mod (p-1)}mod p.`v`_{2}= c^{d mod (q-1)}mod qFinally, following the algorithm 14.71 referred to above, calculate

, and`C`_{2}= p^{-1}mod q

.`u = (v`_{2}- v_{1})C_{2}mod qThe final answer is:

=`c`^{d}mod n.`v`_{1}+ u p(In calculating

in my implementation, I had to check for a result less than 0, and I had to add`u`to the result in that case.)`q`*Security.*

The CRT version of decryption requires the primesand`p`, as well as the decryption exponent`q`, so this might seem to be an extra source of insecurity. However, it is simple to factor the modulus`d`given the decryption exponent`n`, so no security is lost in using this method.`d`*Performance.*

Theory predicts that the CRT decryption should be 4 times as fast. I tried 600 1024-bit decryptions using a Sun Ultra 10 workstation. The average decryption time for the normal method was about**0.157**seconds per decryption. With the CRT method here, the average decryption time was about**0.046**seconds per decryption, giving a speedup by a factor of about**3.4**. The more complicated algorithm has various sources of extra overhead, so it is not surprising that the full speedup by a factor of 4 is not achieved.*Summary.*

If one uses an encryption and verifying exponent of**3**as I am with this software, then these operations are quite fast compared with decryption and signing (at least 100 times faster). A speedup by a factor of**3.4**for decryption and signing is significant. The extra algorithmic complexity is minimal, so no one would want an RSA algorithm without this speedup factor.

The RSA system is a *symmetric public key cryptosystem*
in the terms of the previous section. Recall that this means
that there are any number of pairs of algorithms
** (E, D)** both defined on the same set of values.

Users ** A**,

In RSA, the plaintexts and ciphertexts are just large positive integers, up to a certain size depending on the specific key pair. The underlying algoriths are not secret but only certain information used in them. The RSA system itself is constructed as follows:

Some people are surprised that RSA just deals with large integers.
So how does it represent data? Suppose the value of
** n** is at least

To show that RSA decryption reverses what RSA encryption does, one only needs to show that:

But recall that

The last line follows from the chapter on favorite algorithms which
shows that the exponent can be reduced modulo
** phi(n) = phi(p*q) = (p - 1)*(q - 1)**.

RSA uses arithmetic on integers at least ** 200**
digits long. RSA has been implemented many times in hardware,
but if it is only used for key exchange, a software implementation
is fast enough. Any such implementation must start with routines
to do extended precision arithmetic on the large integers.
Writing such routines is perhaps a reasonable project for an
undergraduate CS major as part of one course, with division
causing the most grief. (Twenty years ago, I laid out one weekend
for such a project, but I ended up devoting more than a week to it.)
Many implementations are available,
including the Java

This Java implementation of the RSA cryptosystem uses the
Java ** BigInteger** library class. This
arbitrary precision integer arithmetic classt has all the
methods one needs to implement RSA without difficulty. In fact,
it seems as if a number of specialized methods were included just
to make RSA implementation easy.
Additional comments about the particular implementation
presented here:

Here is the implementation code and the simple test: RSA implementation and test.

Here is an altered implementation of the RSA cryptosystem, using the the Chinese Remainder Theorem (CRT) to speed up decryption. Please refer first to the comments in the earlier subsection and to other material about the RSA cryptosystem.

One does have to be careful with exponent ** 3**
in two ways: if the message is less than the cube root of

Here is the implementation code: Faster RSA.

*Exercise:* Write a ``toy'' implementation of RSA in
the Java language, using the ** long** type
(