# Identification of correct plaintext after decryption in Rabin cryptosystem

In the Rabin cryptosystem, decrypting a message can produce four different outputs, of which only one is the correct plaintext. How can one know which of the outputs is the correct one?

-

This is a solution that should work with very high probability, but possibly can fail. As a bonus it also resists tampering with the ciphertext.

As encrypter generate a random key (say a 128-bit key for AES128-CTR) and encrypt the plaintext using that key. Then compute a MAC over the ciphertext (for example using HMAC-SHA1) using the same key. Finally you encrypt the randomly generated key using the Rabin cryptosystem. You then send $encrypted\_key || MAC || ciphertext$ to the receiver.

The receiver first decrypts the encrypted key to get 4 potential keys. For each key he computes the MAC over the ciphertext and see if it equals the sent MAC. If yes he proceeds to decrypt the ciphertext using that key.

Another bonus of this system is authentication. If you have a shared secret/token of sufficient cryptographic length (say 128 bits) between sender and receiver you can use that as the key for the MAC instead of the randomly generated key.

-
Just for posterity's sake it should be pointed out that the failure scenario Nightcracker mentions is if two of the Rabin decrypted keys result in correct MACs for the ciphertext. Like he says, with very very high probability this will not happen. EDIT: Now I'm second-guessing myself. nightcracker, is this correct? –  pg1989 Aug 19 '13 at 17:52

Nightcracker's method works fine. There also are deterministic solutions to select the correct ciphertext that require very few additional bits. One very useful ingredient is the use of the Jacobi symbol.

For example, you might look at The Rabin cryptosystem revisited by M. Elia, M. Piva and D. Schipani (http://arxiv.org/pdf/1108.5935.pdf).

-
This is arguably a better solution than mine - I just used the bruteforce technique by making use of a very low collision probability. This solution has a lot more finesse and has a lot more thought in it on a deeper level. –  nightcracker Aug 19 '13 at 17:57
can you please explain it in simple words. –  Aria Aug 22 '13 at 10:35