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

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 .

1 1Recall that a number is primeif it has no factors save itself and 1. So 11 is prime, but is not since 2 and 3 divide 6, i.e. they are factors of 6.

2 2Fermat's theorem says that when is prime and is not a multiple of .

3 3Testing for primality means to see whether the number in question is a prime number.

4 4is Euler's Phi Function see Chapter 19for further details.

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.