# Rabin cryptosystem decryption when p=q

I'm currently trying to implement the Rabin Cryptosystem when I realized something when gave p and q the same value:

So my values are as follows:

Original message = 20

p=11

q=11

Encrypted message = 37

After decryption I get four values

99, 99, 22, 22

None of the values are my original message. Why is that, and how can I still get the original message?

I implemented the algorithm following the wiki article found here: https://en.wikipedia.org/wiki/Rabin_cryptosystem

Rabin, like RSA, requires $p\ne q$. Basically, this is because the rings $\mathbf{Z}_{pq}$ (for $p\ne q$) and $\mathbf{Z}_{p^2}$ have fundamental differences. Crucially, $\mathbf{Z}_{pq}$ is isomorphic to $\mathbf{Z}_p \times \mathbf{Z}_q$, and your decryption algorithm depends on that property. On the other hand, $\mathbf{Z}_{p^2}$ is not isomorphic to $\mathbf{Z}_p^2 = \mathbf{Z}_p \times \mathbf{Z}_p$, so your decryption algorithm doesn't work.

• Ok thanks. So there is no possible way to get the original message right? – Krachwas Aug 18 '16 at 6:10
• Yes there is, but this is not secure because an attacker can recover the message as well. (In case you didn't know, prime powers can be easily factored.) – fkraiem Aug 19 '16 at 2:12
• Yes I knew that. So how would I do that? Do I have to factor p again, use 1 and 11 as p and q for the rest of the calculation? (for this example) – Krachwas Aug 19 '16 at 6:19

As fkraiem already pointed out, Rabin's requires $p\neq q$, otherwise your ring is not isomorphic to the direct product $\mathbb{Z}_p \times \mathbb{Z}_q$. And then the decryption doesn't work as stated in the algorithm.

Yes I knew that. So how would I do that? Do I have to factor p again, use 1 and 11 as p and q for the rest of the calculation? (for this example) – Krachwas

First, if you created the key then you know the factorization already. You never have to factor anything.

It is important to realize, that using $p=q$ is incredibly insecure. It is easy to find out, that a number is a perfect square. And then everyone can decrypt.

But here's how you get your numbers back, assuming you use the insecure $p^2 = n$ and ciphertext $c$:

• First you calculate the square root modulo $p$: Calculate $x$ s.t. $x^2 = c \mod p$ , e.g. with the Tonelli-Shanks algorithm
• Then you can use Hensel lifting with the polynomial $x^2 - c = 0 \mod p$ to get a solution $y^2 - c = 0 \mod p^2$.

But in the end, you just want to fix your problem by using $p, q$ prime and $p\neq q$, as it is stated in the requirements of the algorithm.

• Thank you very much for the explanation. It's a really exciting topic. – Krachwas Aug 19 '16 at 12:30