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

, 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.)

3.12 Solutions

      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 19 in 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.

      9 3.9 If is even, then 2 divides . For security, and must be large, certainly bigger than 2. Thus, and being primes bigger than 2 are odd numbers. So (and ) are even. Then 2 divides as well as . This contradicts the assumption that .

      10 3.10 No, the algorithm works without that requirement. However, an attacker might test if , and if so, then . To see this, note that , since . Since divides , and is prime, this forces that divides or divides . Then, since and both and are prime, this implies that or . Thus, an attacker can easily factor when .

      11 3.11 We have . Thus, Eve knows and . Now so Eve knows . Eve can assume that is bigger than . So Eve calculates the positive square root of which is . Since Eve knows both and then, by adding, she gets and then . For example, suppose Eve knows and . Then . Now , so . Since we get and .

      12 3.12 Solution (a). We find such that . This gives .Solution (b). Let . Then 40 divides and 36 divides . We find such that . This gives .

      13 3.13 Solution (a). We find such that . This gives .Solution (b). Let . Then 16 divides and 18 divides . We find such that . This gives .

      14 3.14 If we get, using either method, that .

      15 3.15 .

      16 3.16 We can take giving .

      17 3.17 factors as , , so we find all for which there is a so that . That is, we find all integers relatively prime to, and less than, . There are 16 (excluding the number 1), they are 3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39. In general, this quantity is called Euler's Phi function, so as is the number of integers including 1 that are less than 40 and relatively prime to 40. Note that, for any prime , . If are relatively prime, i.e. have no nontrivial factors in common, then . This is further discussed in Chapter 19.

      18 3.18 We can take , so corresponding to the pair of letters .

      19 3.19 If we put three letters in a block, we might have a block as large as 252 525 which is larger than .

      20 3.20 If we encode with, say two letters in a block, we know that there are only possible messages even though the largest message is encoded as 2525. So to increase the security (i.e. to make a brute‐force attack more difficult), we need a large number of letters in a block and so a large modulus . More economical methods of encoding are possible (see Mollin [Mol02] and [Mol00]).

      21 3.21 If is less than , the message is immediately obtained by getting the th root of the cipher text . For example, if , we need only calculate the cube root of . The reason is that so .

      22 3.22 .

      23 3.23 Suppose A chooses a binary string of length 56 as a proposed session key for the DES algorithm and transmits this key to B using RSA. When we represent as an integer, it will be less than . Then the cipher text is less than . If is small, say , then this may be much less than when and are large. Then, by calculating the root of an eavesdropper can recover the key .

      24 3.24 From the stated fact, it follows that for some . If is small, then RSA can be attacked.

      25 3.25 For , we find so (One can verify from theory, or directly, that ).

      26 3.26 We have and . Therefore, , , . Then . Thus, .

      27 3.27 This follows from the Chinese Remainder Theorem discussed