While Public exponent is an even number which means Can't get the d in normal way since gcd(e, phi) won't be 1, and in this case only used one prime number for N (multiple uses for one prime number) What is the idea of getting the m,could p = 3 mod 4 be helpful? Thank you for any idea.

  • 1
    $\begingroup$ 'Only used one prime number for N'; are you saying N is prime? $\endgroup$
    – poncho
    Jun 1, 2022 at 15:53
  • $\begingroup$ I meant N = p*p, I know when N is prime phi is simply N-1 if I remember correctly. But thanks for correcting I should make my words clearly. $\endgroup$
    – dlfls
    Jun 1, 2022 at 16:11
  • $\begingroup$ $e = 2$ is used in the Rabin signature scheme ( first true signature scheme). While some people also defined Rabin's cryptosystem, Rabin was not defined. $\endgroup$
    – kelalaka
    Jun 1, 2022 at 18:41
  • $\begingroup$ I have look it up, but in my case the e is actually not 2 so i think it works slightly different? but thanks for the comment. (and nice to know the information about the Rabin part, funny lol $\endgroup$
    – dlfls
    Jun 1, 2022 at 19:39

1 Answer 1


I'll address the case $e=2$; if $\gcd(e, \phi(n)) = 2$, then this is sufficient (as it would suffice to find the squareroot of $c$ (the ciphertext), and then take the $e/2$th root of that.

So, we're given $c$ and want to find the values $m$ s.t. $m^2 = c \pmod {p^2}$.

We start by finding the values $m'$ s.t. $m'^2 = c \pmod p$; this is a modular squareroot, and there are known algorithms for it. The easiest applies if $p \equiv 3 \pmod 4$; in that case, $m' = \pm c^{(p+1)/4} \bmod p$. The $p \equiv 1 \pmod 4$ case is also doable, but is more work.

Given those values, we convert those into values modulo $p^2$. That turns out to be even easier, because if we have $m = m' + xp$ (and $m$ will always be equivalent to one of the $m'$ values modulo $p$), then we have:

$$m^2 = (m' + xp)^2 = m'^2 + 2m'xp = c \pmod {p^2}$$

And, since $c-m'^2$ is a multiple of $p$, we can reduce this to:

$2m'x = (c - m'^2)/p \pmod p$, or $x = (2m')^{-1} (c - m'^2)/p \pmod p$

And, $m = m' + px$ gives you the values of $m$ (and remember, there are two possible values of $m'$ and hence two possible values of $m$).

Also note that, because we managed to do with without any private information, this doesn't work as 'public key encryption'

  • $\begingroup$ So if the public exponent is 2^a int (not 1), will that change the idea of this? And I do have a question for gcd(e, phi), What does gcd(e, phi) effects like in this case it is 2 but how if in other cases it is 4 or 8 or something is that matter at all? Sorry too many questions... $\endgroup$
    – dlfls
    Jun 1, 2022 at 17:11
  • $\begingroup$ @dlfls: if it is 4 or 8, just run the above procedure 2 or 3 times... $\endgroup$
    – poncho
    Jun 1, 2022 at 18:22

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.