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