Decrypting a message encrypted twice with RSA but with same n

Question

A file has been encrypted with the same public key twice, in an effort to improve security. However, both n's are the same, only differing by the value of e they used.

#Public key 1
n1 =  24016279469503302311768363568486449460171750320351449411053109064904102702186605107662009320942295421144872090146373296123251966130145432041792751439876360474093585612002400165121650447690296909966552951831431726123370359155905316115223804791521947206341327545023938257688891564488348042571100942123588832599
e1 =  11

#Pub Key 2
n2 =  24016279469503302311768363568486449460171750320351449411053109064904102702186605107662009320942295421144872090146373296123251966130145432041792751439876360474093585612002400165121650447690296909966552951831431726123370359155905316115223804791521947206341327545023938257688891564488348042571100942123588832599
e2 =  1979012594580741578965814515737507102724629115259135437002620173501789696652411313993744725896645142948111090785385183099262030766961088009028637044476121912549313185770249316009240104504564277494277703059316855002885408408101154109370574780029908357870187035294088105105999982886731850954738596033927830763

assert(n1 == n2) # True
c =  19077240875014404240513831497347701592496448798525581251271555405125029031254112763878818905801024929555186756783763228867690958988427269235733424681439935493781830895580741081706308780868332000845463226253464982424465795348256005266884842524968814407751760246714244563807678549191109606785376890867915099095

How would I go about finding m?

Looking at RSA cracking: The same message is sent to two different people problem it seems there's a way to solve this but I cant seem to figure out how.

I've tried finding the d when e = 11 since it's easy to brute force and got d = 2. Assuming this is true, i can decrypt the first layer, but the second layer seems impossible.

Am I approaching this the wrong way?

Answer 1

The approaches in the question are leading nowhere.

In both the present question, and the other question that it links to, it is used textbook RSA encryption (no padding), and two public keys sharing the same public modulus. But the similarity stops here. In the present question the plaintext is enciphered with the first public key, that first ciphertext (that we do not get) is enciphered again with the other public key, and we only get the final ciphertext. In the other question, it was given two separately obtained ciphertexts, and that's central to the cryptanalysis method that was used.

There's no easy way to find a $d_1$ corresponding to $e_1=11$; whatever was made to get $d_1=2$, that's wrong. To find a $d_1$ directly, we would need a factorization of $n$ (or equivalent information), and it is 1022-bit, which is out of our reach for proper generation.

---

A first observation is that the first of the two chained encryptions perform $m\mapsto c_1=m^{e_1}\bmod n$; and the second $c_1\mapsto c={c_1}^{e_2}\bmod n$. Thus $$\begin{align} c&=(m^{e_1}\bmod n)^{e_2}\bmod n\\ &={(m^{e_1})}^{e_2}\bmod n\\ &=m^{(e_1\cdot e_2)}\bmod n \end{align}$$ and we see that the two encryptions are equivalent to one encryption using $e=e_1\cdot e_2$, which we can compute. But that alone is not enough to conclude.

---

The crucial observation is that $e_2$ is unusually large (1018-bit): there's seldom a good reason to use $e$ larger than the common $2^{16}+1$, which is 17-bit, and it is exceptional to use $e$ more than 128-bit.

This hints that $e_2$ (and/or $e=e_1\cdot e_2$) may have been chosen such that a corresponding private exponent $d_2$ (or $d$) is short. Like, a $d_2$ sizably shorter than $n$ was chosen, then it was computed an $e_2\equiv {d_2}^{-1}\bmod\lambda(n)$, where $\lambda$ is the Carmichael function (or same for $e$ computed from a short $d$). In practice that would be almost as silly as reusing the same $n$ is, and comparable to the sin of leaving aside random padding; but this obviously is a puzzle. For short-enough choice of $d_2$ (and/or $d$), such a poor key generation method would allow to carry Wiener's attack. If that succeeds, we can factor $n$ and conclude. As a shortcut, if we find $d$, we can directly use it to decipher $c$.

---

It turns out attacking either $e_2$ or $e$ works, I guess because the actual generation method chose $d$, computed $e$, then chose $e_1$ as a small factor of $e$.

Note: a question with the same numeric values was recently asked, and got rightly deleted as off-topic after failing migration (this one is better because there is some general question, and some level of effort shown). It was discussed in the side channel.