Problems with Textbook RSA + RSA PKCS#1 v1.5 + Problems with RSA PKCS#1 v1.5

Problems with textbook RSA: if you encrypt small messages (for example m = 2), then some malicious actor can encrypt all the small numbers between 0 and 100, for example, and quickly observe if any of their encrypted numbers match your ciphertext. If it does, they will know what you encrypted.

Standards fix this issue by making your messages too big to be brute-forced in such a way. Specifically, they maximize the size of a message (before encryption) with a nondeterministic padding. For example, the RSA PKCS#1 v2, RSA PKCS#1 v1.5 standard.

RSA PKCS#1 v1.5: the simplest way to pad is to use PKCS#v1.5. With this, we pad to the start of the message bytes,

where the first two bytes are 0x00 and 0x02, followed by a number of non-zero bytes.

RSA PKCS#1 v1.5: We then add a 0x00 byte to identify the end of the padding, and then followed by the message bytes

0x00 0x02 [some non-zero bytes ] 0x00 [message bytes]

The RSA PKCS#1 v1.5 standard specifies a padding to apply to a message prior to encryption.

The padding must be reversible (so that decryption can get rid of it) and must add enough random bytes to the message in order to avoid brute force attacks

Unfortunately, Daniel Bleichenbacher published a paper that showed how the PCKS#v1.5 padding method could be cracked

with a chosen cipher attack (million message attack).