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

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 .

Notes

      1 1 Recall 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 2 Fermat's theorem says that when is prime and is not a multiple of .

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

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