2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.