# Rabin/RSA four possible messages?

Given this encryption method:

$$f_{N,e} : Z^{*}_{N} \to QR(N)^{*};\quad f_{N,e}(x) = x ^{2e} \bmod N$$

I need to show that, for any $x_{0} \in Z^{*}_{N}$, there are four elements $x \in Z^{*}_{N}$ such that $f_{N,e}(x) = f_{N,e}(x_{0})$.

This seems like a cross between RSA ($x \mapsto x^{e} \bmod N$) and Rabin ($x \mapsto x^{2} \bmod N$)? I know that Rabin decryption has four possible messages and that it uses Chinese Remainder Theorem, but I don't know how to start going about it here? This is homework, so it would probably be better for me to be pointed in the right direction, rather than given a complete solution. Thanks for any help.

I also need to give an algorithm that, given the public key $(n, e)$, the private key $(p, d)$ and a ciphertext $c$ such that $c = f_{N,e}(x_{0})$ for some $x_{0} \in Z^{*}_{N}$, returns the set of elements $x \in Z^{*}_{N}$ such that $f_{N,e}(x) = c$. I also need to say why this algorithm is polynomial time in $k$ (= size in bits of primes $p$ and $q$). Any pointers here would also be appreciated. (Is it just asking for the decryption algorithm?)

• Writing the encryption function as $x \rightarrow (x ^e)^2 \pmod N$. Does this help? – DrLecter Dec 8 '13 at 17:09
• Also, yes, the second part is just asking for the decryption algorithm. DrLecter's hint above should help with that too. Note that, for efficient decryption, you'll need to know the factors $p$ and $q$ of $N$. – Ilmari Karonen Dec 8 '13 at 19:21
• I still am struggling with the first part of the question but I will keep trying. For the second part is it $\ x^{(1/2)d} mod N$ for the decryption algorithm? Which is the same as $\ x^{(1/2)d} mod p$ and $\ x^{(1/2)d} mod q$? – user10783 Dec 8 '13 at 20:44
• I am "improving" my hint a bit. Write the encryption function $f_{N,e}(x)$ as $f_{Rabin}(f_{RSA}(x))=f_{RSA}(f_{Rabin}(x))$. – DrLecter Dec 9 '13 at 1:58