3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ you presumably mean "the plaintext was encrypted with.." $\endgroup$ – kodlu Feb 14 '18 at 21:39
  • $\begingroup$ ah, you're right. I've fixed that. $\endgroup$ – cookingboy3 Feb 14 '18 at 22:18
  • $\begingroup$ @fgrieu: actually, the answer is "yes" (unless the $e$'s are all a multiple of some integer > 1) $\endgroup$ – poncho Feb 14 '18 at 22:27
  • $\begingroup$ @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. $\endgroup$ – fgrieu Feb 15 '18 at 6:25
  • 1
    $\begingroup$ @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... $\endgroup$ – cookingboy3 Feb 15 '18 at 16:23
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Ok, here's a hint:

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$?

$\endgroup$
4
  • $\begingroup$ Excuse my lack of knowledge about this, but what is P? $\endgroup$ – Aaron Esau Feb 14 '18 at 23:14
  • $\begingroup$ $P$ is the plaintext. $\endgroup$ – puzzlepalace Feb 15 '18 at 1:40
  • $\begingroup$ 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. $\endgroup$ – fgrieu Feb 15 '18 at 16:36
  • $\begingroup$ @fgrieu I think you are right, one ciphertext is given. $\endgroup$ – kodlu Feb 15 '18 at 21:23

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.