Consequences of Flipping a bit in an RSA public key

Question

I'm taking a cryptography class and one of the previous exam questions is "Alice requests Bob's public key which Bob sends her. She then encrypts the secret number $M$. Unfortunately, Malice flips the fourth least significant bit of Bob's key $e$ in transit which Alice then uses to form the ciphertext $C_1$. Bob can't decrypt so he sends his public key again. Malice leaves the key alone this time and Alice encrypts and sends $M$ in the form $C_2$.

Where $(e_\text{Bob}, n) = (17, 113291)$ and $C_1 = 68496, C_2 = 12465$.

I don't really know how to go about doing a problem like this in an exam situation (i.e. with just a calculator) so I'm wondering if there's some trick to doing it without just finding the factors of $n$.

Answer 1

First note that $e=17=10001_2$ and thus that $e'=11001_2=25$ with $e'$ being the one with the flipped bit. Now note that $M^{e'}\equiv C_1\pmod n$ and $M^{e}\equiv C_2\pmod n$.

Next note how $C_2/C_1\equiv M^{25}/M^{17}\equiv M^8 \pmod n$.
Now compute $M^{17}/M^8\equiv M^{9}\pmod n$ and continue this.
$M^{9}/M^{8}=M \pmod n$ and you are done.

Note that all divisions here are in $\mathbb Z^*_n$, that is, they are multiplications with the multiplicative inverses $\bmod n$.