Page 322 - Discrete Mathematics and Its Applications

4.6 Cryptography 301

By Fermat’s little theorem [assuming that gcd(M, p) = gcd(M, q) = 1, which holds except in
rare cases, which we cover in Exercise 28], it follows that M p−1 ≡ 1 (mod p) and M q−1 ≡
1 (mod q). Consequently,

d
C ≡ M · (M p−1 k(q−1) ≡ M · 1 = M(mod p)
)
and

d
)
C ≡ M · (M q−1 k(p−1) ≡ M · 1 = M(mod q).
Because gcd(p, q) = 1, it follows by the Chinese remainder theorem that

d
C ≡ M(mod pq).

Example 9 illustrates how to decrypt messages sent using the RSA cryptosystem.
EXAMPLE 9 We receive the encrypted message 0981 0461. What is the decrypted message if it was encrypted
using the RSA cipher from Example 8?

Solution: The message was encrypted using the RSA cryptosystem with n = 43 · 59 and expo-
nent 13.As Exercise 2 in Section 4.4 shows, d = 937 is an inverse of 13 modulo 42 · 58 = 2436.
We use 937 as our decryption exponent. Consequently, to decrypt a block C, we compute

M = C 937 mod 2537.

To decrypt the message, we use the fast modular exponentiation algorithm to compute
0981 937 mod 2537 = 0704 and 0461 937 mod 2537 = 1115. Consequently, the numerical version
of the original message is 0704 1115. Translating this back to English letters, we see that the
message is HELP. ▲

RSA as a Public Key System

Why is the RSA cryptosystem suitable for public key cryptography? First, it is possible to rapidly
construct a public key by finding two large primes p and q, each with more than 200 digits,
and to find an integer e relatively prime to (p − 1)(q − 1). When we know the factorization of
the modulus n, that is, when we know p and q, we can quickly find an inverse d of e modulo
(p − 1)(q − 1). [This is done by using the Euclidean algorithm to find Bézout coefficients s
and t for d and (p − 1)(q − 1), which shows that the inverse of d modulo (p − 1)(q − 1) is
s mod (p − 1)(q − 1).] Knowing d lets us decrypt messages sent using our key. However, no
method is known to decrypt messages that is not based on finding a factorization of n, or that
does not also lead to the factorization of n.
Factorization is believed to be a difficult problem, as opposed to finding large primes p
and q, which can be done quickly. The most efficient factorization methods known (as of 2010)
require billions of years to factor 400-digit integers. Consequently, when p and q are 200-digit
primes, it is believed that messages encrypted using n = pq as the modulus cannot be found in
a reasonable time unless the primes p and q are known.
Although no polynomial-time algorithm is known for factoring large integers, active re-
search is under way to find new ways to efficiently factor integers. Integers that were thought, as
recently as several years ago, to be far too large to be factored in a reasonable amount of time can
now be factored routinely. Integers with more than 150 digits, as well as some with more than
200 digits, have been factored using team efforts. When new factorization techniques are found,