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



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

Thank you in advance!


2 Answers 2


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.

  • $\begingroup$ Ok thanks. So there is no possible way to get the original message right? $\endgroup$
    – Krachwas
    Commented Aug 18, 2016 at 6:10
  • $\begingroup$ 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.) $\endgroup$
    – fkraiem
    Commented Aug 19, 2016 at 2:12
  • $\begingroup$ 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) $\endgroup$
    – Krachwas
    Commented Aug 19, 2016 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.

  • $\begingroup$ Thank you very much for the explanation. It's a really exciting topic. $\endgroup$
    – Krachwas
    Commented Aug 19, 2016 at 12:30
  • $\begingroup$ @tylo would you mind expanding more on how to use hensel pls? $\endgroup$ Commented Oct 28, 2020 at 18:37
  • $\begingroup$ @user2608855 When you have the root $x \mod p$, then the root $x' \mod p^2$ would be: $x' = x - (x^2-c) \cdot a$. where $a=(2x)^{-1} \mod p$. $\endgroup$
    – tylo
    Commented Nov 7, 2020 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.