# 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

I am assuming you meant to use a=2, so that if it sends an error message, we know that MCB was 1. Anyway RSA in practice is never used in raw form like this precisely because this malleability allows attacks like you just mentioned. Such malleability also allows an attacker to create fake signatures from an oracle and with good padding, we cannot trick any RSA decryption oracle into signing some message while it thinks it was decrypting something which would be possible if RSA was used raw.

• What you describe finds the top bit. When that bit is 0, it's easy to get the next one. But how to proceed if we conclude that the top bit is a 1? – fgrieu Jan 7 at 17:24
• I think the OP asked only about finding MCB. You are right, we can find out the number of 0's in the prefix, by repeatedly querying multiplying with each with 2. – Manish Adhikari Jan 7 at 17:30
• I don't know how to proceed after encountering a 1 tho. – Manish Adhikari Jan 7 at 17:38
• Why do you need to proceed? The question is "how can we determine the msbit"; once you've done that, you've answered the problem that was asked. What, are you going for extra credit??? If you are, then try this to obtain additional information: how can you determine the lsbit? – poncho Jan 8 at 19:28