I want to know if there is a easy way to calculate $r$ from $c=r^t\mod{n}$ where $(c,t,n)$ is known and $t=pq$ is an RSA?

If $n=t^2$, is it more easier?

  • 1
    $\begingroup$ Hint: that's a particular case of the RSA problem. If the factorization of $n$ gets known, that's easy. $n=t^2$ makes the later easier. $\endgroup$ – fgrieu Jul 5 '18 at 13:32
  • $\begingroup$ …How do you find yourself in this situation where $t = pq$ and $n = t^2$? $\endgroup$ – Squeamish Ossifrage Jul 6 '18 at 0:29
  • $\begingroup$ Because I want to get the random number in the paillier encryption $c=g^xr^t\mod{t^2}$, I can get $x$ from the private key, how can I get $r$ from $c/g^x = r^t\mod{t^2}$? $\endgroup$ – Felix LL Jul 8 '18 at 8:36

If $n$ is prime, then it is easy; we have

$$r = c^{t^{-1} \bmod n-1} \bmod n$$

If $n$ is a composite of known factorization, then it is still easy; one approach would be to have:

$$r = c^{t^{-1} \bmod \phi(n)} \bmod n$$

where $\phi(n)$ is the totient function. An equivalent approach would be to solve it for all the prime power factors of $n$, and then use the Chinese Remainder Theorem to reconstruct $r$

If $n$ is a composite of unknown factorization, well, it's believed to be hard. This is actually the RSA problem

  • $\begingroup$ If $t=pq$ and $n=t^2$, is it easy? Thank you! $\endgroup$ – Felix LL Jul 5 '18 at 13:44
  • $\begingroup$ @Felix LL: yes, that's easy, once $p$ and $q$ are known. Most often $r=c^{t^{-1} \bmod\phi(n)}\bmod n$ works, just be sure to compute the Euler totient $\phi(n)$ correctly. There are a corner cases, though: 1) $\min(p,q)$ might divide $\max(p,q)-1$, and then $t^{-1} \bmod \phi(n)$ will be undefined; 2) $c$ might be a multiple of $p$ or $q$ (including zero) [and that can combine with 1) or with $p=q$]. Solving modulo $p$, then modulo the highest power of $p$ in the factorisation of $n$, then if $p\ne q$ solving similarly modulo $q^2$ then using the CRT, will rigorously find all the solutions. $\endgroup$ – fgrieu Jul 5 '18 at 16:47

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.