2
$\begingroup$

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions?

$$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and $q$ are large primes.

Actually, I am investigating the question that is it possible (how difficult) to make more than one valid RSA signatures for a given message $a$ and a public key $n$ (with the private key $d$ known). Apparently signing $a$ with $d$ gives one valid signature. My question is how difficult to find another one. Thanks.

$\endgroup$
1
$\begingroup$

The solution is unique in the RSA setting where $d \equiv n^{-1} \pmod {\varphi(pq)}\;$ is assumed to exist, if $\gcd(a,pq)=1.\;$ But the case $\gcd(a,pq)\ne 1$ must be avoided anyway because otherwise you can factor $pq\;$ and your specific RSA system is broken (in practice with large primes this is very unlikely, and I do not know if in actual implementations this situation is checked).

By Euler's theorem the unique solution is $$x \equiv a^{d} \pmod {pq}\equiv a^{n^{−1}\pmod {\varphi(pq))}} \pmod {pq}$$

$\endgroup$
1
  • $\begingroup$ I think gcd$(n, \phi(pq))$ is a sufficient condition of unique solution. $\endgroup$
    – updogliu
    Sep 19 '14 at 16:30

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.