Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 57

Goals, Discussion This chapter is important and does not require too much mathematical background. We avoid making essential use of number theory in the text, although it can be used to shorten the calculations. We discuss one of the main public key algorithms, namely RSA, as well as some of its applications to e‐Commerce with Transport Layer Security (TLS) and to the encryption of email.

Public key and symmetric cryptography are 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 the root of is 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 , the decryption index need not be unique! We provide several examples. This is important because some attacks on RSA are possible if is small; we refer to Chapter 7. So if is not unique, this makes it more difficult to guard against this attack.

What we mean by “not unique” is that there may be more than one value of such that the remainder of , on division by , is . The reason for nonuniqueness is that, instead of working with , we can work with any number that is divisible by and , as explained in the algorithm description and in Chapter 19. It is often possible to find so that the calculations are simplified, and we get a shortcut even if the resulting is the same.

We present new insights on public key and symmetric encryption.