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

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 in Chapter 19. The main point is this. We have . By the Chinese Remainder Theorem, there is a unique less than such that . Now also satisfies these three equations. Moreover, since , we get . Thus, . The cube root of , then gives . Note that this attack can be generalized to any small value of .

28 3.28 First, we check that , and are pairwise relatively prime. They factor as , and , and are Thus, pairwise relatively prime. Now, as described in the previous solution is 74 088, and so the answer is . [See Solution 3.28.]

29 3.29 By hypothesis, Bob knows the factors of , i.e. he knows , where .In order to decrypt a cipher sent to Alice, i.e. to find the message sent to Alice, Bob merely has to find the inverse of modulo , i.e. to find such that . Then Bob raises to the power and gets the remainder of upon division by to find .

30 3.30 Since is relatively prime to , there are integers , so that . This follows from a generalization to Fermat's Theorem. Using this fact, we have . Now , by Fermat's Theorem. Then . To see this, we are calculating(3.13) This is equal to(3.14) Now,Thus, is divisible by . Similarly, it is divisible by so that is divisible by . From (3.14), we get . Then, given that , we conclude that . Thus, if is small, RSA can be attacked. Note that in using Fermat's Theorem, we have supposed that and , but, we in fact can only be guaranteed that one of or is true, although it is possible that both are true. However, the result still holds in this case, and the proof is similar.

31 3.31 For , , so .

32 3.32 69.

33 3.33 .