RSA, cipher, Cryptosystem

Question

I genuinely have no idea how to go about solving this, any hints would be helpful

Answer 1

Hint: company B uses the same modulus with three different public exponents. That means that the attacker has access to:

$$C_1 \equiv M^{17} \pmod{9997}$$ $$C_2 \equiv M^{19} \pmod{9997}$$ $$C_3 \equiv M^{21} \pmod{9997}$$

More importantly, for any (possibly negative) integers $k_1$ and $k_2$ we have:

$$C_1^{k_1} \equiv \left ( M^{17} \right )^{k_1} \equiv M^{17k_1} \pmod{9997}$$

$$C_2^{k_2} \equiv \left ( M^{19} \right )^{k_2} \equiv M^{19k_2} \pmod{9997}$$

Multiply these two together (using basic modular arithmetic) to get:

$$C_1^{k_1} \cdot C_2^{k_2} \equiv M^{17k_1 + 19k_2} \pmod{9997}$$

Now, big hint: 17 and 19 are coprime. Can you finish? Note that negative $k_1$ and $k_2$ are perfectly allowed, because inverses are well-defined modulo $9997$ and can be computed efficiently using the extended Euclidean algorithm - the only case inverses don't exist is when $C_1$ or $C_2$ are not coprime to $9997$, in which case you have accidentally factored the public key anyway.

---

(this is of course ignoring the fact that these particular public keys are easily factored into the private key anyway, and that RSA is, thankfully, not used like that in the real world)