# RSA with shared modulus multiple primes

It was suggested to choose $k$ large Blum primes ($k > 2$), and compute $m = p_1\cdot p_2\cdots p_k$.

The trusted center (TC), who knows the prime factors of $m$, computes for each user $U$: $(e_U , d_U )$ and sends it to him. Each user publishes $e_U$ and keeps $d_U$.

The question is whether someone apart from the TC can find the factorization of $m$.

One weakness of the scheme is that if the same message $x$ is transmitted to two different users an eavesdropper can obtain $x$ using Bezout's identity, which is also a weakness of the regular RSA in a shared modulus system.

In a 'two primes RSA' system with shared modulus a user can find $p,q$ with very high probability using his public and private key.

But what can be said with $k$ primes? I don't see how to use a similar approach like I used in the two primes case in order to obtain $(p,q)$, nor do I know how to prove the security of it.

The question is whether someone apart from the TC can find the factorization of $m$.

Yes, however I will first address the easier to answer question of "could the holder of private key $a$ decrypt traffic to the holder of private key $b$"

The answer to that is "yes"; Alice, the holder of the private key $a$ has $e_a$, $d_a$, and $e_b$ (Bob's public key).

We know that $e_a d_a \equiv 1 \pmod {\lambda(n)}$ (where $\lambda(n) = \text{lcm}(p_1 - 1, p_2 - 1, ..., p_k-1)$, that is, $e_a d_a - 1 = m\lambda(n)$ for some integer $m$. So, what Alice can do is compute $d'_b = e_b^{-1} \bmod{ e_a d_a - 1} = e_b^{-1} \bmod{ m\lambda(n)}$; it is easy to see that $e_b d'_b \equiv 1 \pmod{ \lambda(n)}$, that is, $d_b'$ will work as a decryption key for traffic to Bob. It likely not to be larger than Bob's key $d_b$, however it is not so large that Alice can't practically use it.

However, to address the question "could Alice factor $n$ (even though the above argument shows she doesn't need to)", the answer is "yes"; the same probabilistic method that works against two factor RSA primes also works in this case (it just may take more iterations to complete the factorization).

To review: Alice computes $e_a d_a - 1 = 2^k z$ for $k$ large enough to make $z$ odd. Then, she selects a random value $g$ and computes:

\begin{align*} h_0 &= g^z \bmod n \\ h_1 &= h_0^2 \bmod n \\ h_2 &= h_1^2 \bmod n \\ &\vdots \\ h_k &= h_{k-1}^2 \bmod n \end{align*}

It should be clear that, unless the original $g$ just happened to not be relatively prime to $n$, that the final value $h_{k} = 1$; we look at the largest $i$ where $h_i \ne 1$. If $i > 0$ and $h_i \ne -1 \pmod n$, that gives us a nontrivial factor $\gcd(n, h_i - 1)$.

It can be shown that at least half the possible initial $g$ values will yield a factor, and that this factor is effectively random over the possible factorizations, hence rerunning this test using different $g$ values will quickly reveal all the factors.