# 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. – orlp Aug 19 '13 at 17:57
• can you please explain it in simple words. – Aria Aug 22 '13 at 10:35

Decoding produces three false results in addition to the correct one, so that the correct result must be guessed. This is the major disadvantage of the Rabin cryptosystem and one of the factors which have prevented it from finding widespread practical use.

That's straight from the Wikipedia page. It goes on to discuss that guessing the answer is easier with something like a text-based message, but obviously much more difficult if you're decrypting a number. Or imagine if you double-encrypted your result, meaning you'd have to perform decryption 5 times (first time results in 4; then one more for each of those) and result in 16 possible outcomes.

There may be use for this type of cryptosystem, but for most applications it seems this flaw is pretty major.

• -1 It does not answer the question - just rephrases the problem. – orlp Aug 19 '13 at 13:38
• But the answer is that there is no way to know the proper outcome! It's a 1 in 4 chance, though you may get some context clues. That's the answer. – armani Aug 19 '13 at 13:51
• No it's not. See my answer. – orlp Aug 19 '13 at 13:53