Important! These are all exam-level problems. Do not attempt these problems without a solid foundation in the subject and use them for exam practice.
1. Why do we never let e be equal to 2?
We know that d = e-1 mod (p-1)(q-1). For this to happen, we need GCD(e, (p-1)(q-1)) to be equal to 1. If we let e = 2, then we need for GCD(2, (p-1)(q-1)) = 1, which means (p-1)(q-1) must be odd. For this to happen, both p-1 and q-1 must be odd, making p,q both even. We know importantly, however, that the RSA method requires p and q to be primes, and the only even prime is 2. As we have determined what p and q must be, we can now solve for d, breaking the RSA system. 2. What is 2147 mod 21?
8. From our proofs about RSA, we learned that x(p-1)(q-1) = 1 mod (pq). Here, it's easy to tell that p = 7 and q = 3, so (p-1)(q-1) = 12. We notice that, 2147 = 212(12)23 = 11223 = 23 = 8. 3. Jack is sending Tommy a message with RSA. The public key is 3, while N is 55. What is the value of d that Tommy must use to decrypt the message?
If N = 55, then p = 5 and q = 11, as these are the only two primes whose product is equal to 55.
Next, we want d = e-1 mod (p-1)(q-1). To do this, we must run the extended-gcd algorithm.
1 = 40 - 3(13)
1 = 40(1) + 3(-13)
So, d = -13, which, mod 40, is 27.