20.5 Bleichenbacher attack
Long before Bleichenbacher published this work, it was well known that plain RSA is vulnerable to chosen-ciphertext attacks. If Eve wants to decrypt the ciphertext c ≡ md (mod n) that Bob encrypted for Alice, she can choose a random integer s and ask Alice to decrypt an apparently innocuous message c′≡ sec (mod n).
If Alice, thinking she is decrypting ciphertexts received from a legitimate party such as Bob, returns Eve the result m′≡ (c′)d (mod n), Eve can easily recover the original message m by computing m ≡ m′s−1 (mod n). This works because:
and for the term (c′)ds−1 it holds that:
Moreover, because ed (mod n) ≡ 1 by the definition of the RSA algorithm, Eve can easily determine m because:
In his publication [34], Bleichenbacher showed that Eve can also decrypt any ciphertext c if she has access to an oracle that for every ciphertext returns whether the corresponding...