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.
Answer
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}$$
No comments:
Post a Comment