0
$\begingroup$

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

Thank you in advance!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok thanks. So there is no possible way to get the original message right? $\endgroup$ – Krachwas Aug 18 '16 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 Aug 19 '16 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 Aug 19 '16 at 6:19
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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