Rabin Cryptosystem - Decryption

Decryption

To decode the ciphertext, the private keys are necessary. The process follows:

If c and r are known, the plaintext is then with . For a composite r (that is, like the Rabin algorithm's ) there is no efficient method known for the finding of m. If, however is prime (as are p and q in the Rabin algorithm), the Chinese remainder theorem can be applied to solve for m.

Thus the square roots

and

must be calculated (see section below).

In our example we get and .

By applying the extended Euclidean algorithm, we wish to find and such that . In our example, we have and .

Now, by invocation of the Chinese remainder theorem, the four square roots, and of are calculated ( here stands for the ring of congruence classes modulo n). The four square roots are in the set :

One of these square roots is the original plaintext m. In our example, .

Rabin pointed out in his paper, that if someone is able to compute both, and, then he is also able to find the factorization of because:

either or, where means Greatest common divisor.

Since the Greatest common divisor can be calculated efficiently you are able to find the factorization of efficiently if you know and . In our example (picking and as and ):