Score:0 Crypto

# RSA question for public exponent is an even number but not 2, and not big 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.  'Only used one prime number for N'; are you saying N is prime?  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.  $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.  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
Score:2 Crypto 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'  WOW, that was quite a lot and amazing! Thank you for helping, I just need time to get through that and understand what is going on here. But anyway thank you so much for answering.  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...  @dlfls: if it is 4 or 8, just run the above procedure 2 or 3 times...  Thanks for answering back, have a great day!  