discussed as well as the average number of guesses required when searching a key space for the key (Theorem 3.6). Some cryptographic attacks, both mathematical and real world are discussed here and in Chapter 7.
In Section 3.7, we discuss another important algorithm which straddles the border between symmetric and public‐key exchanges, called the Diffie–Hellman key‐exchange.
In Section 3.3, we denote by the remainder when the positive integer is divided by the positive integer . For example, . Another way of stating this is that or . We are working here with the integers . This is covered in detail in Chapters 5and 19.
Let us briefly explain the idea. Alice wants to send a secret message to Bob. Bob has chosen a number and another number (for encryption). The pair represents Bob's public key and is listed in a “public key directory.” Alice represents the secret message as a number lying between 1 and . To encrypt or scramble the message , Alice multiplies by itself times, gets the remainder after dividing by , and transmits the result to Bob. The result is called the cipher text . An eavesdropper, noting , realizes the message itself must be equal to the th root of , or , or , or for some unknown . Eve (the eavesdropper) cannot 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
