Paper 3, Section I, H

Coding and Cryptography
Part II, 2013

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

The Cabinet decides to communicate using Rabin ciphers to maintain confidentiality. The Cabinet Secretary encrypts a message, represented 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. The Defence Secretary deciphers this message to read it but then foolishly 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}. Mr Rime (the Leader of the Opposition) knows this has happened. Explain how Rime can work out what the original message was using the two different encrypted versions.

Can Rime decipher other messages sent out by the Cabinet using the original modulus NN ?