2.II.12G

Coding and Cryptography
Part II, 2008

Describe the Rabin cipher with modulus NN, explaining how it can be deciphered by the intended recipient and why it is difficult for an interceptor to decipher it.

The Bursars' Committee decides to communicate using Rabin ciphers to maintain confidentiality. The secretary of the committee encrypts a message, thought of as a positive integer mm, using the Rabin cipher with modulus NN (with 0<m<N0<m<N ) and publishes both the encrypted message and the modulus. A foolish bursar deciphers this message to read it but then encrypts it again using a Rabin cipher with a different modulus NN^{\prime} (with m<N)\left.m<N^{\prime}\right) and publishes the newly encrypted message and NN^{\prime}. The president of CUSU, who happens to be a talented mathematician, knows that this has happened. Explain how the president can work out what the original message was using the two different encrypted versions.

Can the president of CUSU also decipher other messages sent out by the Bursars' Committee?