2. (a) Suppose Alice uses RSA to send the same message x (e.g. her credit card number), encrypted, to three companies, all of which use the easy choice of e = 3 in their public key. Eve intercepts these encrypted messages, i.e. x 3 (mod N1), x3 (mod N2), x3 (mod N3), where N1, N2, N3 are the moduli used in the companies public keys (all > x). There is a method (the Chinese Remainder Theorem) by which she can use these to deduce the value of x 3 (mod N1N2N3). Assuming this can be done, explain how she can now compute x exactly. This is one reason why e = 3 is a poor choice in practice.

(b) A popular choice for e is 65537. What is special about this value of e (as opposed to nearby values) that makes it a good choice?