15.6 Public Key Cryptography 249How to do all this computation.We already discussed how to find
primes, and Alice can follow the method described in section 6.10.
The next issue is the computation of the two keyseandd. One of them,
saye, Alice can choose at random, from the range 1,...,(p−1)(q−1)−1.
She has to check that it is relatively prime to (p−1)(q−1); this can be done
efficiently with the help of the Euclidean Algorithm discussed in Section
6.6. If the number she chose is not relatively prime to (p−1)(q−1), she
just throws it out and tries another one. This is similar to the method we
used to find a prime, and it is not hard to see that she will find a good
number in about the same number of trials as it takes to find a prime.
But if she finally succeeds and the Euclidean Algorithm shows that she
found a numbererelatively prime to (p−1)(q−1), then (as in Section 6.6)
it also gives two integersuandvsuch that
eu−(p−1)(q−1)v=1.Soeu−1 is divisible by (p−1)(q−1). Letddenote the remainder ofu
modulo (p−1)(q−1), thened−1 is also divisible by (p−1)(q−1), and
so we have found a suitable private keyd.
Finally, how do we compute the remainder ofxemodulom, when just
to write downxewould fill the universe? This is done in the same way as
described in Section 6.10.
Signatures, etc.There are many other useful things this system can do.
For example, suppose that Alice gets a message from Bob as described
above. How can she know that it indeed came from Bob? Just because it
is signed “Bob,” it could have come from anybody. But Bob can do the
following. First, he encrypts the message with his private key, then adds
“Bob,” and encrypts it again with Alice’s public key. When Alice receives it,
she can decrypt it with her private key. She’ll see a still encrypted message,
signed “Bob.” She can cut away the signature, look up Bob’s public key in
the phonebook, and use it to decrypt the message.
Could anyone have faked this message? No, because the interloper would
have to use Bob’s private key to encrypt the message (using any other key
would mean that Alice gets garbage when she decrypts the message by
Bob’s public key, and she would know immediately that it is a fake).
One can use similar tricks to implement many other electronic gadgets,
using the RSA public key system: authentication, watermarking, etc.
Security.The security of the RSA protocol is a difficult issue, and since its
inception in 1977, thousands of researchers have investigated it. The fact
that no attack has been generally successful is a good sign; but unfortu-
nately, no exact proof of its security has been found (and it appears that
current mathematics lacks the tools to provide such a proof).
We can give, however, at least some arguments that support its security.
Suppose that you intercept the message of Bob, and want to decipher it.