In the RSA cryptosystem encryption is performed using C = Me (mod N), where N = pq for suitably…

In the RSA cryptosystem encryption is performed using C = Me (mod N), where N = pq for suitably chosen large primes p, q, and gcd(e, f(N)) = 1. In a chaining attack on RSA, given a ciphertext C = Me (mod N) the atacker computes, C e (mod N), Ce 2 (mod N), . . . , Ce k (mod N), unless C = C e k (mod N) is obtained. That is, k is the least positive integer that specifies the cycle. (a) Explain why the attacker can always find k ? [1, N – 1] so that C = C e k (mod N). Hint: Recall that RSA is an encryption algorithm and therefore bijective, i.e. M1 6= M2 cannot be mapped to the same ciphertext. (b) Can attacker recover the message M from the observed sequence above in case C = C e k (mod N) is valid ? 17 (c) Explain how the attacker can factor N by finding integer u such that gcd(C e u , N) > 1. Hint: Analyze different cases w.r.t. (mod p) and (mod q) congruences.