# Textbook-RSA meet-in-the-middle attack against other RSA based schemes?

A “meet-in-the-middle” (not “man-in-the-middle”!) attack on textbook-RSA was presented to me. The only requirements for it was that the attacker gets the output of RSA and the public key, and that the message be the product of 2 numbers of the same magnitude, which apparently happens with 20% probability. (ie: only eavesdropping).

This attack can reduce the attack of a 64-bit message to O(2^34) instead of O(2^64) for exhaustive search. (ie: almost square root of attack time)

The ISO public key encryption scheme has RSA(pk,x) sent "in the clear" as header. So it seems to me that textbook-RSA can be used to recover x, from which Hash(x) gives the symmetric key…

What am I missing here? Could someone clarify please?

Or maybe I do understand correctly, but that meet-in-the-middle attack on textbook-RSA is not that significant (20% chance of achieving sqrt the time of exhaustive search).

edit: Sorry, I made a mistake: the attack can reduce a O(2^64) exhaustive search into O(2^34) attack which is not almost half the time, but almost square root of the exhaustive search time.

meta: I would like to accept answer but I cannot, neither can I add comments

-
nlognfan, I see your comment that you are unable to edit your question or accept an answer. Make sure you are logged in as nlognfan. If you have lost access to that account, please try the account recovery process (or try clicking "click here to recover your account" on the sign-in page) and the StackExchange OpenID recovery page; if neither of those works for you, contact team@stackoverflow.com with as much information as you have to ask them to help you regain access. –  D.W. Aug 18 '13 at 7:14

## 1 Answer

I suspect that the meet-in-the-middle attack you have in mind is what is presented in this answer (or something similar).

If so, then it's not actually correct to say "the only requirement is that the message be a product of 2 numbers of the same magnitude"; the message needs to be a product of two numbers of the same small magnitude.

For example, the attack can work if the message were a product of two 64 bit numbers; however this would imply that the message itself was no longer than 128 bits.

This is a credible attack against textbook RSA used to pass 128 bit messages; however any sane public key encryption method (such as ISO 18033-2) would include padding to make the message presented to the RSA primitive much larger; this completely invalidates this attack.

-