How to recover a message with shared modulus for textbook RSA

Question

Same message sent to two users encrypted with textbook RSA, known $n$, $e_1$, $e_2$, $c_1$, $c_2$. Show how the attacker can recover the message.

Problem statement

Consider an RSA system with $n=143$, $e_1=7$ and $e_2=17$. Suppose the same message $m$ was sent to the two users above and the attacker observed the ciphertext $c_1 =42$ and $c_2 =9$. Show how the attacker can recover the message.

Official solution

Use Extended Euclidian algorithm to find $a$ and $b$ such that $a\,e_1 + b\,e_2 = 1$. Then we obtain $m$ as ${c_1}^a + {c_2}^b \bmod n$ thus $m=3$

My attempt at solving the problem

Having read this and watched this, I did the following, but I get the wrong answer:

Using the Extended Euclidean algorithm I get $a = 5$ and $b = -2$ for $a\,e_2 + b\,e_1 = 1$. (According to the comment section of the YouTube video, $a$ from the video, let's call it alpha, needs to be greater than or equal to $b$ from the video, let's call it beta; alpha = $e_2$ and beta = $e_1$.)

Then $$\begin{align} m &= ({c_2}^a + {c_1}^b) \bmod n\\ i &= {c_1}^{-1} \bmod n\\ m &= ( {c_2}^a i^{-b} ) \bmod n\\ i &= 42^{-1} \bmod 143\\ 42i &= 1 \bmod 143\\ i &= (1+143\times \nu)/42\\ \nu &= 37\implies i = 126\\ m &= ({c_2}^5 + i^2) \bmod 143\\ m &= (9^5 + 126^2) \bmod 143\\ m &= 136 \neq 3 \end{align}$$

Could someone please help me figure out what I am doing wrong?

Edit: Here's my work (in a corrected way), and in a way that won't expire (since the message where I showed my work will eventually expire), in case it helps someone else: For 1 to 3 of the "Hint to derive the correct equation" part: To prove that m^1 mod n = m, we know that since m < n and anything less than than the divisor yields the dividend in a modulo expression.

Then, using the properties you mentioned ( the x^(u+v) and x^(uv) stuff from here: https://crypto.stackexchange.com/revisions/81829/21 ), with the constraints described in (4) from here ( Definition of $x^u \bmod k$ ), I get m = m^1 mod n

m = m^(a e_1 + b e_2) mod n

m = [m^(a e_1) mod n] ] m^(b e_2) mod n] mod n

m = ({[m^(e_1) mod n]}^a) mod n ({[m^(e_2) mod n]}^b) mod n

m = ({C_1}^a) mod n ({C_2}^b) mod n

m = {(C_1^a) mod n (C_2^b) mod n} mod n

m = (C_1^a · C_2^b) mod n.

From the constraints described in (4), we know that it must be the case that gcd(C_2,n) = 1 (which can be seen in the (4) from the case where u < 0, k > 1 and gcd(x,k) = 1, assuming x = C_2 and u = b < 0) for the modular inverse labelled as i, here ( RSA cracking: The same message is sent to two different people problem ), to be defined, and therefore for the whole expression for the (plaintext) message m to be defined (unless C_1^a * C_2^b yields an integer, even if a < 0 or b < 0).

Answer 1

what I am doing wrong?

Accepting as fact a recipe with an equation, rather than deriving it.

Illustration: « Then we obtain $m$ as ${c_1}^a + {c_2}^b \bmod n$ » is stated rather than derived. And wrong.

As an aside the question reverses $a$ and $b$ (or is it $c_1$ and $c_2$, or $e_1$ and $e_2$): they are correct per the official solution which asks $a\,e_1 + b\,e_2 = 1$, but the calculation then made assumes and states $a\,e_2 + b\,e_1 = 1$.

Hint to derive the correct equation:

1. Prove that $m^1\bmod n=m$, by combining the definition¹ of raising to an integer exponent, the assumed range of $m$ in textbook RSA, and the definition² of the $\bmod$ operator.
2. In this equation, substitute $1$ with $a\,e_1 + b\,e_2$ where $a$ and $b$ are the Bezout coefficients such that $a\,e_1 + b\,e_2=1$.
3. Properly use properties³ of modular exponentiation. In cryptanalysis it's OK to assume plausible preconditions when that's necessary, but it remains good to verify them (or the result derived) in the end.

---

Suggestion: apply this technique with a slightly larger $n=14835196795348830319$, $(e_1,e_2)=(3,5)$, and $(c_1,c_2)=(14562201346830272020,1832973312396331965)$. As a bonus find the menu by expressing $m$ in hex. The point of these larger numbers is that guessing the Bezout coefficients and inverse is harder, and slightly more computer skills are needed.

More mathematically interesting, for a different method is needed, which would still work if $n$ was too large to factor directly from its value: with the same $(n,e_1,e_2)$ find $m$ for $(c_1,c_2)=(11810011337245959646,2207245693327700143)$.

---

Note: in actual use, RSA encryption

• Does not reuse the same $n$ among several public keys, making this particular attack fail.
• Does not directly encode the message as $m$, but rather adds randomness to the message in order to form $m$. That makes it extremely unlikely that $m$ is reused (it would be enough to allow some other attacks including with different $n$).
• Uses $n$ with several hundred decimal digits in order to resist factorization. $n=143$ can be factored mentally, and the larger $n$ is factored in a small fraction of a second using a computer, which allows to find $m$ by using the normal RSA decryption equation, without needing $c_2$ or $e_2$.

---

Appreciation: taking at face value the statement that the extended Euclidean algorithm was used, the question shows fair skills to apply equations and algorithms, despite the inversion of $a$ and $b$. Be assured that the goal of such exercises is not learning the equations used. It's to learn to derive the necessary equations. That's easier when one gets the hang of it, and more fun. It's more reliable, and thus gets higher marks (which is a valid sub-goal) even when the reasoning is not considered in the notation. As a skill it's more useful, more adaptable, less likely to go obsolete, or unused and forgotten.

---

¹ ² ³ : See this definition of $x^u\bmod k$ and related typographical conventions, or refer to a previous version of the present answer.