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?)

  • 4
    $\begingroup$ Writing the encryption function as $x \rightarrow (x ^e)^2 \pmod N$. Does this help? $\endgroup$ – DrLecter Dec 8 '13 at 17:09
  • 1
    $\begingroup$ 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$. $\endgroup$ – Ilmari Karonen Dec 8 '13 at 19:21
  • $\begingroup$ 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 $? $\endgroup$ – user10783 Dec 8 '13 at 20:44
  • $\begingroup$ 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))$. $\endgroup$ – DrLecter Dec 9 '13 at 1:58

Your Answer

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

Browse other questions tagged or ask your own question.