Aiden A. Bruen - Cryptography, Information Theory, and Error-Correction

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 . 4 Show that Eve can then find and . (See Solution 3.11.)Calculations using RSA (The Euclidean Algorithm of Chapter 19can 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.)

1 3.1 Yes, we must have . First of all, we have and , where is the enciphering algorithm. Applying the decryption algorithm , we have and , since . Similarly, . Since , we have ; so .

2 3.2 This is a special case of Section 3.2. The reason is that if is any message with , then the enciphering transformation transforms to with . As we will see in Chapter 19, the decryption algorithm transforms to .

3 3.3 69.

4 3.4 7.

5 3.5 Yes, as we have seen in the first example discussed in the text, there can be more than one decryption index . Here is another example. Suppose that A is transmitting a message to B whose public key is . Now, we have with . Then, . Now, . (In another notation, we have that 581 is the multiplicative inverse of 5 mod 1452.) So we can take . Then, for any cipher text , it follows that . However, instead of working with , we can work with any integer that is divisible by both and . Such a number is 66. Note that . Thus, as will be shown in Chapter 19in the general case, if is such that , then also serves as a decryption index here. Now, . So .Let us summarize. We have two decryption indices, namely, 581 and 53, for the same values of and . For any message , in the form of an integer between 1 and , we have , but also .

6 3.6 Suppose a user announces his public key as . Then is easily factored. Just take the square root of to get .

7 3.7 The idea goes back to Fermat, involving Fermat's “Difference of Squares Method,” as follows. Suppose factors as with . Recall that are odd, so and are even. Then and . Then where are integers with . Thus, or . If is close to , then is bigger than, but close to, . So to factor , which is our goal, we only need to try a few integers until we find a such that is equal to a square integer denoted by . For example, take as in Problem 3.18. Here, So start with and immediately we get which is a square. Thus, and we have factored .

8 3.8 One explanation is as follows. The official procedure for calculating the decryption index is to find such that . (In other language, is the multiplicative inverse of modulo ). This can be carried out, as we shall see in Chapter 19, only if is relatively prime to , i.e. only if . For example, if , then it is impossible to find so that the remainder of on division by 40 is 1. To see that this is the case we would need to find so that for some . But the left side is even, the right side is odd. So, no such exists. What happens if we break the rules and choose an enciphering index such that ? Take . Then . However, we also get and . In other words, four different messages namely 2, 7, 8, 13 all encipher to the same cipher text, namely 4. But we saw in Problem 3.1 that in a proper cryptographic system, two different messages cannot encipher to the same cipher text.