find as there are too many values of to try. It is a remarkable fact that if there is just a single value of, say, such that theroot ofis a whole number lying between 1 and. To see this, let be any whole number, i.e. a positive integer not necessarily lying between 1 and such that . Then
(3.1)
Let be a decryption index (there may be several). If is the message, then, by definition,
(3.2)
Applying , we have
(3.3)
and
(3.4)
Therefore, . In particular, if lies between 1 and , as does by assumption, then . In effect, we are saying that the mapping is 1 to 1 if lies between 1 and .
Moreover, it can be shown that if for any positive integer the th root of is a whole number , then the remainder of upon division by must be (see Chapter 19).
The recipient Bob, however, can calculate immediately from a formula involving his private key consisting of a “decryption index” along with two prime numbers , . The reason is that is the product of and . Bob knows and . Anybody else, even knowing , cannot in general determine what the factors , are in a reasonable amount of time.
Eve can try guessing the message without knowing by guessing . Alternatively, Eve can try guessing and from which she can calculate . In other words, Eve can try to guess the private key and then determine the message.
We detail some potential weaknesses with public key algorithms such as RSA. However, this algorithm is still a central public key algorithm. Its security, when carefully implemented, seems to still be strong after many years of constant use.
A fact in cryptography is that in a brute‐force attack on a key‐space (one where we try all possible keys), the correct key is likely to be found after trying about half the total number of keys. In this chapter, we provide a short simple proof of this fact.
The encryption exponent mentioned above must be chosen to have no factors in common with and no factors in common with . The reason for assuming this is so that exists. Another reason is that this condition must be satisfied in order that two different messages get two different encryptions. This comes up in Problem 3.1. We mention also that, for a given
find 