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 ≡ m^d (mod n) that Bob encrypted for Alice, she can choose a random integer s and ask Alice to decrypt an apparently innocuous message c′≡ s^ec (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⁻¹ (mod n). This works because:

and for the term (c′)^ds⁻¹ 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...