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

  • $\begingroup$ For the interested reader: $M^{23}\bmod n=C_1$ and $M^{17}\bmod n=C_2$. $\endgroup$ – SEJPM Dec 28 '17 at 19:57

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


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.