Paper 2, Section II, G

Coding and Cryptography
Part II, 2015

Briefly describe the RSAR S A public key cipher.

Just before it went into liquidation, the Internet Bank decided that it wanted to communicate with each of its customers using an RSA cipher. So, it chose a large modulus NN, which is the product of two large prime numbers, and chose encrypting exponents eje_{j} and decrypting exponents djd_{j} for each customer jj. The bank published NN and eje_{j} and sent the decrypting exponent djd_{j} secretly to customer jj. Show explicitly that the cipher can be broken by each customer.

The bank sent out the same message to each customer. I am not a customer of the bank but have two friends who are and I notice that their published encrypting exponents are coprime. Explain how I can find the original message. Can I break the cipher?