# Given one message encrypted repeatedly with the same 'n' but different 'e's, is it possible to decrypt the ciphertext without simply bruteforcing n?

I'm trying to solve a problem where I've been provided with a few public keys and the ciphertext, and I've been told that the plaintext was encrypted repeatedly using all of these keys. However, all of the keys have the same $n$ and a multitude of $e$s, varying from 2 to 126 digits. All of the other attacks involving matching $n$s only seem to work for multiple plaintexts encrypted with multiple keys, where in this case it's one plaintext encrypted with multiple keys. Is there any attack other than brute factoring that could allow me to find the plaintext?

As a better example: Bob is concerned about his security, so he asks Alice to produce 3 keypairs, $(n, e_1), (n,e_2), (n,e_3)$ and then encrypts his plaintext, $M$, with each of the 3 keys, feeding the ciphertext $C$ from each into the next, so that by the time he's done, $M$ has been encrypted with all three keys in series to produce one final $C$ which is sent to Alice.

• you presumably mean "the plaintext was encrypted with.." Feb 14 '18 at 21:39
• ah, you're right. I've fixed that. Feb 14 '18 at 22:18
• @fgrieu: actually, the answer is "yes" (unless the $e$'s are all a multiple of some integer > 1) Feb 14 '18 at 22:27
• @poncho: I had understood "encrypted repeatedly" as meaning the ciphertext of the previous encryption was re-encrypted with textbook RSA, and we only get the final outcome and the public keys sharing a common public modulus. That can't be solved, except for special, unlikely combinations of $e$. Your reading that we get multiple encryptions of the same plaintext with textbook RSA is most likely right.
– fgrieu
Feb 15 '18 at 6:25
• @fgrieu You are correct, you have one plaintext that's encrypted by one set of keys, and then the ciphertext created is then encrypted by another set of keys and so on... Feb 15 '18 at 16:23

As in the discussion in the comments under @poncho's answer this is equivalent to encrypting with the key $$(n,\prod_{i} e_i)$$ whihc means unless there is a specific weakness in the key itself, i.e., some of the bits of the final key is leaked, or say $$\prod_{i} e_i \equiv e'~(\textrm{mod}~\phi(n))$$ with $e'=1,$ or $e'$ very small with the message $M$ also being small, say $0<M<n^{1/e'}$ making taking direct integer roots feasible, this cannot be solved.
Suppose you know the values of $P^{e_1} \bmod N$ and $P^{e_2} \bmod N$. How could you use those two values to compute $P^{e_1 - e_2} \bmod N$? How could you then use this repeatedly to compute $P^{\gcd(e_1, e_2)} \bmod N$?
• Excuse my lack of knowledge about this, but what is P? Feb 14 '18 at 23:14
• $P$ is the plaintext. Feb 15 '18 at 1:40
• If we trust this comment by the OP, we only get $P^{\left(\displaystyle\prod e_i\right)} \bmod N$; or is it all the $P^{\left(\displaystyle\prod_{j=1}^i e_j\right)} \bmod N$ but I fail to see how to solve that.