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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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).
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.