Discrete Mathematics: Elementary and Beyond

15.6 Public Key Cryptography 247

11630000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000371

The smallest 200 digit integer starting with 1163 is 1163· 10196. This is of
course not a prime, but above we found a prime very close by. There must
be zillions of such primes! Indeed, a computation very similar to what we
did in section 6.4 shows that the number of primes Alice can choose from
is about 1. 95 · 10193.
This is a large number of possibilities, but how do we find one? It would
not be good to use the prime above (the smallest eligible): Bob could guess
this and thereby find out Alice’s move. What Alice can do is to fill in the
missing 196 digits randomly, and then test whether the number she obtains
is a prime. If not, she can throw it away and try again. As we computed
in Section 6.4, one in every 460 numbers with 200 digits is a prime, so on
the average in 460 trials she gets a prime. This looks like a lot of trials, but
of course she uses a computer; here is one we computed for you with this
method (in a few seconds again):

11631467128765557632799097045596606908283654760066

68873814489354662474360419891104680411103886895880

57457155724800095696391740333854584185935354886223

23782317577559864739652701127177097278389465414589

So we see that in the “envelope” scheme above, both computational facts
mentioned in Section 6.10 play a crucial role: It is easy to test whether a
number is a prime (and thereby it is easy to compute the encryption), but
it is difficult to find the prime factors of a composite number (and so it is
difficult to break the cryptosystem).

15.6 Public Key Cryptography

Cryptographic systems used in real life are more complex than those de-
scribed in the previous section; but they are based on similar principles. In
this section we sketch the math behind the most commonly used system,
the RSA code (named after its inventors, Rivest, Shamir, and Adleman).

The protocol.Alice generates two 100-digit prime numbers,pandqand
computes their productm=pq. Then she generates two 200-digit numbers
dandesuch that (p−1)(q−1) is a divisored−1. (We will return to the
question of how this is done.)
The numbersmandeshe publishes on her web site (or in the phone
book), but the prime factorspandqand the numberdremain her closely
guarded secrets. The numberdis called herprivate key, and the number