# Finding MSB in RSA

Scenario: Alice and Bob send each other encrypted AES (128) messages. In order to change key, Alice has a public RSA key (2049 bits). Bob has Alice's public key.

Bob picks a random AES key, encrypts it, and sends it to Alice. Alice decrypts the RSA encryption, if the result is bigger than 2^128, Alice assumes an error occurred and sends an error message to Bob.

Eve performs a man in the middle attack. Eve can change any message and avoid messages to reach their destination. Eve can't change Bob's and Alice's RSA keys.

How Eve can find the most significant bit in the AES key that Bob sent?

I got a hint:

let $$c = m^e \bmod n$$. The decryption of $$c\cdot a^e \bmod n$$ is $$m\cdot a \bmod n$$. That's because decryption of $$m^e\cdot a^e \bmod n$$ is $$(m^e \cdot a^e)^d \bmod n$$ when $$e\cdot d \bmod \varphi(n)=1$$.

So I assume Eve can modify Bob's encrypted message $$c$$ and multiply it with $$a^e \bmod n$$.

If Alice sent an error message so we can know that $$(m\cdot a \bmod n)\ge 2^{128}$$.

• Guessing that this is homework, here your hint as out HW policy. Hint: what will happen to a 128-bit multiplied with 2? Is it 129-bit or 128-bit? – kelalaka Jan 6 at 22:55
• @kelalaka Ssshl! – Maarten Bodewes Jan 6 at 23:06
• Note: for this reason, and others, when good practitioners RSA-encrypt something, they do not use textbook RSA as in the question. They use RSAES-OAEP. Additional hint: that also works when $a$ is a fraction whose denominator is coprime with $n$. There's a fine line between numerator and denominator, but only a fraction of the audience gets it. – fgrieu Jan 7 at 6:46
• Have you found the solution? If so, please delete the question; or make and accept an answer. Further note: I fixed an off-by-one in the last equation. Eve actually substitutes $c$ with $c'\gets c\cdot(a^e \bmod n)\bmod n$. She can find the AES key with about a hundred queries and appropriate $a$. Other (very different) attacks are possible that need no query, but only work for a sizable fraction of $a$, and require in the order of $2^{68}$ modular multiplications. – fgrieu Jan 7 at 17:15