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

The Laws of Cryptography with Java Code.

---

History of the RSA Cryptosystem.

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.

---

Description of the RSA Cryptosystem.

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. E is the public encryption algorithm and D is the private decryption algorithm These satisfy:

1. Encryption/decryption works: If c = E(m) is the ciphertext corresponding to some plaintext m, then m = D(c). (In other words: m = D(E(m)), for any message m.)
2. Sign/verify works: If s = D(m) is the signature corresponding to some plaintext m, then m = E(s). (In other words: m = E(D(m)), for any message m.)
3. Can encrypt efficiently: For any message m, there is an efficient algorithm to calculate E(m).
4. Can decrypt efficiently: For any message or ciphertext x, there is an efficient algorithm to calculate D(x).
5. Public/private keys stay that way: From a knowledge of E, there is no efficient way to discover D.

Users A, B, ... can create their own pairs (E_A, D_A), (E_B, D_B), ... of RSA key pairs. The encryption algorithms are ``published'' or made available on a secure public key server, while the decryption algorithms are kept secret from everyone except the originator. The previous section has gone over how these can be used.

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:

1. Choose random ``large'' prime integers p and q of roughly the same size, but not too close together.
2. Calculate the product n = p*q (ordinary integer multiplication).
3. Choose a random encryption exponent e less than n that has no factors in common with either p - 1 or q - 1.
4. Calculate the (unique) decryption exponent satisfying e*d mod (p - 1)*(q - 1) = 1.
5. The encryption function is E(m) = m^e mod n, for any message m.
6. The decryption function is D(c) = c^d mod n, for any ciphertext c.
7. The public key (published): This is the pair of integers (n, e).
8. The private key (kept secret): This is the triple of integers (p, q, d).

There is more to the story about each of the above items:
1. At present, ``large'' means at least 512 bits. For better security each prime should be at least 1024 bits long. There are efficient algorithms for generating random numbers of a given size that are almost certainly prime (see below).
2. n is then either 1024 or 2048 bits long.
3. The encryption exponent e can be just 3. If one is using this exponent, then the primes must be such that p - 1 and q - 1 are not divisible by 3.
4. The decryption exponent must be calculated, and there are efficient algorithms to do this, but they require a knowledge of p and q (see the chapter on favorite algorithms). The modulus for division, (p - 1)*(q - 1), is the Euler phi function of n = p*q, where this is a function studied in number theory. One of the function's properties is important in proving that RSA works.
5. There are efficient algorithms for carrying out the modular exponentiation needed here (see below).
6. Ditto.
7. If it is known that 3 is the encryption exponent, then only n needs to be published.
8. Only d needs to be kept as the secret data for decryption (along with the public n and e). However, p and q can be efficiently calculated from the other numbers, and they are needed anyway for the most efficient form of modular exponentiation.

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 1024 bits long. This is the same as 128 bytes. In principle then, one can just run 128 bytes of Ascii text together and regard the whole as a single RSA plaintext (a single large integer) to be encrypted or signed. In practice, the protocols will demand additional data besides just the raw message, such as a timestamp, but there is room for a lot of data in a single RSA encryption.

---

RSA Works: Decryption in the Inverse of Encryption.

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

D(E(m)) = m, for any message m, or specifically to show that
(m^e)^d mod n = m.

But recall that

e*d mod (p - 1)*(q - 1) = 1, so that
(m^e)^d mod n = m^e*d mod n = m^{e*d mod (p - 1)*(q - 1)} mod n = m¹ mod n = m.

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).

---

Java Implementation of the Basic RSA Cryptosystem.

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 BigInteger class, and implementations in symbolic algebra packages such as Maple or Mathematica.

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:

• 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 p and q are chosen at random, differing in length by 10-20 bits. (If the primes are too close to sqrt(n), then factoring might be easier than it should be.) The primes are also chosen so that p - 1 and q - 1 are relatively prime to 3, because this implementation uses 3 as the encryption exponent.
  • 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 3. The main known weakness here is that the message m must be bigger than the cube root of n, since otherwise the ciphertext will be m^3, without any modular division. Smaller messages must be padded to make them long enough.

• 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 public n values first, using the longer one before the shorter one. Otherwise one might need to use two RSA blocks in some cases.

• The Test:
  There is just a simple test of this software, though 1024 bits is a realistic size.

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

---

Faster RSA Implementation Using the Chinese Remainder Theorem.

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.

• 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. If c is ciphertext, then RSA decryption calculates
  c^d mod n, where n = pq.

  Suppose one calculates

  v₁ = c^d mod p and v₂ = c^d mod q

  instead. The Chinese Remainder Theorem (and associated algorithm) allows one to deduce x mod (p q) from a knowledge of x mod p and x mod q.

  Arithmetic mod p should be done mod (p-1) in an exponent, because

  a^p-1 mod p = 1 (Fermat's theorem).

  Thus we can use the simpler calculation:

  v₁ = c^{d mod (p-1)} mod p and v₂ = c^{d mod (q-1)} mod q.

  Finally, following the algorithm 14.71 referred to above, calculate

  C₂ = p^-1 mod q, and
  u = (v₂ - v₁)C₂ mod q.

  The final answer is:

  c^d mod n = v₁ + u p.

  (In calculating u in my implementation, I had to check for a result less than 0, and I had to add q to the result in that case.)

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

• 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.

One does have to be careful with exponent 3 in two ways: if the message is less than the cube root of m, then the encrypted message will be the same as the message, and if someone obtains ciphertext for a message encrypted under several different public keys, it may be possible to calculate the message.

Here is the implementation code: Faster RSA.

Exercise: Write a ``toy'' implementation of RSA in the Java language, using the long type (64-bit integers) for the calculations. This should be a working implementation in every respect except that the integers cannot be very large.