The Laws of Cryptography:
The RSA Cryptosystem
by Neal R. Wagner
Copyright © 2001 by Neal R. Wagner. All rights reserved.
NOTE: This site is obsolete. See book draft (in PDF):
Law RSA1: The RSA cryptosystem is the de facto world-wide
standard for public key encryption.
History of the RSA
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
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
- 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
- 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
- Can encrypt efficiently:
For any message m, there is an efficient
algorithm to calculate E(m).
- Can decrypt efficiently:
For any message or ciphertext x, there is an efficient
algorithm to calculate D(x).
- 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 (EA, DA),
(EB, DB), ... 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:
There is more to the story about each of the above items:
- Choose random ``large'' prime integers p and
q of roughly the same size, but not too close together.
- Calculate the product n = p*q (ordinary integer
- Choose a random encryption exponent e
less than n
that has no factors in common with either p - 1
or q - 1.
- Calculate the (unique) decryption exponent satisfying
e*d mod (p - 1)*(q - 1) = 1.
- The encryption function is E(m) = me mod n,
for any message m.
- The decryption function is D(c) = cd mod n,
for any ciphertext c.
- The public key (published): This is the pair of integers
- The private key (kept secret): This is the triple of integers
(p, q, d).
- 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).
- n is then either 1024 or
2048 bits long.
- 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.
- 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.
- There are efficient algorithms for carrying out the modular
exponentiation needed here (see below).
- If it is known that 3 is the encryption
exponent, then only n needs to be published.
- 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
(me)d mod n = m.
But recall that
e*d mod (p - 1)*(q - 1) = 1,
(me)d mod n =
me*d mod n =
me*d mod (p - 1)*(q - 1) mod n =
m1 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
- 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.
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.
Law RSA2: RSA encryption should use exponent 3,
making it hundreds of time faster, and RSA decryption should
use the Chinese Remainder Theorem, making it four times
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
Suppose one calculates
v1 = cd mod p and
v2 = cd 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
ap-1 mod p = 1 (Fermat's theorem).
Thus we can use the simpler calculation:
v1 = cd mod (p-1) mod p and
v2 = cd mod (q-1) mod q.
Finally, following the algorithm 14.71 referred to above, calculate
C2 = p-1 mod q, and
u = (v2 - v1)C2 mod q.
The final answer is:
(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.)
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.
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.
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
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:
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.
Revision date: 2001-12-31.
ISO 8601, the International Standard.)