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

Notation In some of the problems/solutions below, we used the notation introduced in this chapter. Recall that just means the remainder when is divided by . For example, . Later on, in Chapter 19 we will also use the equivalent or mod notation.

Some of these problems need background material and may be skipped on a first reading.

1 3.1 An essential property. In a cryptographic system suppose messages are encrypted, resulting in cipher texts . If , must ? (See Solution 3.1.)

2 3.2 In the RSA algorithm suppose that , and . Must (See Solution 3.2.)Repeated squaring

3 3.3 Using the repeated squaring method, find the remainder when is divided by 97. (See Solution 3.3.)

4 3.4 Using the repeated squaring method, find the remainder when is divided by 167. (See Solution 3.4.)RSA encryption

5 3.5 Using the RSA algorithm, given the cipher text with , can there be more than one decryption index such that ? (See Solution 3.5.)

6 3.6 In the RSA algorithm, we assume that are large primes which must be unequal. Why is it that must be unequal? (See Solution 3.6.)

7 3.7 Show that for security reasons in the RSA algorithm, and should not be chosen too close together. (See Solution 3.7.)

8 3.8 In the RSA algorithm, why must we choose to be relatively prime to ? (See Solution 3.8.)

9 3.9 In the RSA algorithm, show that must be odd. (See Solution 3.9.)

10 3.10 In the RSA algorithm, the restriction is sometimes made – even in textbooks – that . Is this restriction necessary? (See Solution 3.10.)

11 3.11 Suppose an eavesdropper Eve knows and also .⁴ Show that Eve can then find and . (See Solution 3.11.)Calculations using RSA (The Euclidean Algorithm of Chapter 19 can be used)

12 3.12 Find an RSA decryption exponent given that , and , using both methods as described in the text. (See Solution 3.12.)

13 3.13 Repeat the previous problem with , and . (See Solution 3.13.)

14 3.14 Find an RSA decryption exponent , given that and . (See Solution 3.14.)

15 3.15 Let so and . Let . Suppose . Find the cipher text . (See Solution 3.15.)

16 3.16 Let be as in the previous question. Suppose . What is ? (See Solution 3.16.)

17 3.17 Find all possible values of for . What is a compact formula for this quantity in general? (See Solution 3.17.)Sending text messages with RSA

18 3.18 Suppose Alice wishes to send a text message to Bob using the RSA algorithm. Bob's public key is the pair . Note that . Alice encodes the 26 letters of the English alphabet by putting . Alice transmits the message in blocks. Each block corresponds to two letters which are encoded into their numerical equivalents. For example the pair becomes the block which then gets enciphered to , since the block corresponds to the decimal number 405. Now suppose Bob receives the cipher text 0300. What was the message transmitted by Alice? (See Solution 3.18.)

19 3.19 In the above problem, why can't we put more than 2 letters in a block? (See Solution 3.19.)

20 3.20 Are the text messages that are sent in this way secure? (See Solution 3.20.)Elementary attacks, pitfalls and incorrect implementations of RSASmall message, small exponent

21 3.21 Show that if the message is a small integer and the enciphering index is a small integer, then RSA is not secure. (See Solution 3.21.)

22 3.22 For , decrypt assuming that is “small.” (See Solution 3.22.)

23 3.23 Can you think of a real‐world example of enciphering a small integer where the attack of Problem 3.22 might cause difficulties? (See Solution 3.23.)

24 3.24 Using the fact that , how can RSA be attacked if is small? (This is similar to the above attack.) (See Solution 3.24.)

25 3.25 Decipher given that , using the method of the previous problem. (See Solution 3.25.)Semantic Security and RSA

26 3.26 RSA leaks information in various ways. For example, if are the cipher texts for messages , respectively, then show that is the cipher text for (we are working here by taking remainders upon division by , i.e. we are working ). (See Solution 3.26.)Another way in which RSA leaks information is through the Jacobi symbol, since the Jacobi symbol of the cipher text equals that of the message . This reveals one bit of . A cryptosystem has semantic security if no information is leaked.Broadcast Attack

27 3.27 Given an enciphering index show how a plain text message can be recovered if it is enciphered and sent to three different entities having pairwise relatively prime moduli . This is most easily solved using the Chinese Remainder Theorem of Chapter 19. (See Solution 3.27.)

28 3.28 Use the broadcast attack to find when it is enciphered to 80 using ; 235 using ; and 121 using . (See Solution 3.28.)Common Modulus Attack

29 3.29 Let Alice's public key be and let Bob's public key be , with . Show that Bob can recover all messages sent to Alice. (See Solution 3.29.)Cycling Attack

30 3.30 Given , an eavesdropper can compute etc. How can the eavesdropper obtain the message using this idea? (See Solution 3.30.)

31 3.31 For , decrypt using the cycling attack. (See Solution 3.31.)

32 3.32 Find , where . (See Solution 3.32.)

33 3.33 The following problem is an easy version of the discrete log problem: Find if and . (See Solution 3.33.)