Page 320 - Discrete Mathematics and Its Applications

4.6 Cryptography 299

The RSA Cryptosystem

In 1976, three researchers at the Massachusetts Institute of Technology—Ronald Rivest, Adi
Shamir,andLeonardAdleman—introducedtotheworldapublickeycryptosystem,knownasthe
M.I.T. is also known as
RSA system, from the initials of its inventors.As often happens with cryptographic discoveries,
the ’Tute.
the RSA system had been discovered several years earlier in secret government research in the
United Kingdom. Clifford Cocks, working in secrecy at the United Kingdom’s Government
Communications Headquarters (GCHQ), had discovered this cryptosystem in 1973. However,
his invention was unknown to the outside world until the late 1990s, when he was allowed to
share classified GCHQ documents from the early 1970s. (An excellent account of this earlier
discovery, as well as the work of Rivest, Shamir, and Adleman, can be found in [Si99].)
In the RSA cryptosystem, each individual has an encryption key (n, e) where n = pq, the
Unfortunately, no one
calls this the Cocks modulus is the product of two large primes p and q, say with 200 digits each, and an exponent
cryptosystem. e that is relatively prime to (p − 1)(q − 1). To produce a usable key, two large primes must be
found. This can be done quickly on a computer using probabilistic primality tests, referred to
earlier in this section. However, the product of these primes n = pq, with approximately 400
digits, cannot, as far as is currently known, be factored in a reasonable length of time. As we
will see, this is an important reason why decryption cannot, as far as is currently known, be
done quickly without a separate decryption key.

RSA Encryption

To encrypt messages using a particular key (n, e), we first translate a plaintext message M
into sequences of integers. To do this, we first translate each plaintext letter into a two-digit
number, using the same translation we employed for shift ciphers, with one key difference.
That is, we include an initial zero for the letters A through J, so that A is translated into 00,
B into 01, ... , and J into 09. Then, we concatenate these two-digit numbers into strings of digits.
Next, we divide this string into equally sized blocks of 2N digits, where 2N is the largest even
number such that the number 2525 ... 25 with 2N digits does not exceed n. (When necessary,
we pad the plaintext message with dummy Xs to make the last block the same size as all other
blocks.)
After these steps, we have translated the plaintext message M into a sequence of integers
m 1 , m 2 ,...,m k for some integer k. Encryption proceeds by transforming each block m i to a
ciphertext block c i . This is done using the function
e
C = M mod n.
(To perform the encryption, we use an algorithm for fast modular exponentiation, such as
Algorithm 5 in Section 4.2.) We leave the encrypted message as blocks of numbers and send
these to the intended recipient. Because the RSA cryptosystem encrypts blocks of characters
into blocks of characters, it is a block cipher.

CLIFFORD COCKS (BORN 1950) Clifford Cocks, born in Cheshire, England, was a talented mathematics
student. In 1968 he won a silver medal at the International Mathematical Olympiad. Cocks attended King’s
College, Cambridge, studying mathematics. He also spent a short time at Oxford University working in number
theory. In 1973 he decided not to complete his graduate work, instead taking a mathematical job at the Govern-
ment Communications Headquarters (GCHQ) of British intelligence. Two months after joining GCHQ, Cocks
learned about public key cryptography from an internal GCHQ report written by James Ellis. Cocks used his
number theory knowledge to invent what is now called the RSA cryptosystem. He quickly realized that a public
key cryptosystem could be based on the difficulty of reversing the process of multiplying two large primes. In
1997 he was allowed to reveal declassified GCHQ internal documents describing his discovery. Cocks is also
known for his invention of a secure identity based encryption scheme, which uses information about a user’s identity as a public key.
In 2001, Cocks became the Chief Mathematician at GCHQ. He has also set up the Heilbronn Institute for Mathematical Research,
a partnership between GCHQ and the University of Bristol.