Return to Answer

PKCS#1 v1.5 describes a method (known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption system for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider).

For a $k$-byte ($8k-7$ to $8k$-bit) public modulus part of public key $(N,e)$, the message to be encrypted $M$ is a $\mathrm{mLen}$-byte bytestring with $\mathrm{mLen}\le k-11$. Message $M$ is turned into $\mathrm{EM}=\mathtt{0x00}\mathbin\|\mathtt{0x02}\mathbin\|\mathrm{PS}\mathbin\|\mathtt{0x00}\mathbin\|M$ where $\mathrm{PS}$ is drawn as a $k-\mathrm{mLen}-3$-byte bytestring consisting of fresh near uniformly random non-zero bytes. Then (with big-endian conversion between bytestrings and integer left implicit) the ciphertext is $C\gets\mathrm{EM}^e\bmod N$. That's textbook RSA encryption of $\mathrm{EM}$.

While plaintext $M$ might still be easily guessable, verify such guess becomes much harder. A brute-force method becomes: try all the possible $\mathrm{PS}$ and compute the corresponding $C$, until one matches. That seems to require $255^{k-\mathrm{mLen}-3}/2$ try on average (for each possible $M$). That's next to $2^{63}$ at least, and growing by a factor of $255$ for each byte of message capacity that we remove. That's believed to solve the guessable plaintext problem by an (offline) adversary; but we have no formal proof that it does.

Thanks to the $\mathtt{0x02}$ as the second byte of $\mathrm{EM}$, it holds that $\mathrm{EM}>2^{8k-15}$. It follows that for $e\ge3$, $\mathrm{EM}^e\gg N^2$ for all practical $k$, and that's more than enough to solve a number of small $e$ issues

• any known extension of the $e^\text{th}$ root attack (in this attack against textbook RSA, where $C\gets M^e\bmod N$, it is used that for $M<N^{1/e}$, we can compute back $M$ from $C$ as $M\gets\sqrt[e]C$ )
• Coppersmith's Short Pad Attack (which extends the Franklin-Reiter related messages attack to random padding).

RSAES-PKCS1-v1_5 also practically thwarts Hastad's broadcast attack. In this attack against textbook RSA, sending the same message to at least $e$ recipients allows decryption. The random $\mathrm{PS}$ makes $\mathrm{EM}$ for the same $M$ potentially different. For $e=3$, $\mathrm{PS}$ at the 8-byte minimum, and $2^{36}$ recipients of the same message $M$, probability that $e$ padded messages $\mathrm{EM}$ are identical is lower than one in a million, if I got the math right.

However, many RSAES-PKCS1-v1_5 implementations are vulnerable when used with small $e$, such as $e=3$. That because implementations often check that the first two bytes of $C^d\bmod N$ are $\mathtt{0x00}\mathbin\|\mathtt{0x02}$, and/or parse what follows in order to find the first $\mathtt{0x00}$, indicating the start of $M$ and allowing recovery of $\mathrm{mLen}$. When the result of such check is made available in a way leaking where the failure occurred (by a detailed error code, or timing, or some other side channel) to adversaries able to submit cryptograms for decryption, then Bleichenbacher's padding oracle attack applies. It turns a moderate number of queries to a decrypting entity into an RSA private-key operation for arbitrary argument, allowing decryption of any message, or computing a signature if the same key is used for encryption and signature.

That's not a fatality, though: RSAES-PKCS1-v1_5 padding can be checked in constant time, with a single error code regardless of the particular failure. Another possible strategy is to not check the left 10 bytes; or when $\mathrm{mLen}$ is known in advance, make no padding check and simply extract $M$ as the rightmost $\mathrm{mLen}$ bytes of $C^d\bmod N$.

PKCS#1 v1.5 describes a method (formally known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption scheme for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider).

For a $k$-byte ($8k-7$ to $8k$-bit) public modulus part of public key $(N,e)$, the message to be encrypted $M$ is a $\mathrm{mLen}$-byte bytestring with $\mathrm{mLen}\le k-11$. Message $M$ is turned into $\mathrm{EM}=\mathtt{0x00}\mathbin\|\mathtt{0x02}\mathbin\|\mathrm{PS}\mathbin\|\mathtt{0x00}\mathbin\|M$, where $\mathrm{PS}$ is drawn as a $k-\mathrm{mLen}-3$-byte bytestring consisting of fresh near-uniformly-random non-zero bytes. Then (with big-endian conversion between bytestring and integer left implicit) the ciphertext is $C\gets\mathrm{EM}^e\bmod N$. That's textbook RSA encryption of $\mathrm{EM}$.

While plaintext $M$ might still be easily guessable, verifying such guess becomes much harder. A brute-force method becomes: try all the possible $\mathrm{PS}$ and compute the corresponding $C$, until one matches. That strategy requires $255^{k-\mathrm{mLen}-3}/2$ try on average (for each possible $M$). That's next to $2^{63}$ at least, and growing by a factor of $255$ for each byte of message capacity that we remove. That's believed to solve the guessable plaintext problem; but we have no formal proof that it does.

Thanks to $\mathtt{0x02}$ at the second byte of $\mathrm{EM}$, it holds that $\mathrm{EM}>2^{8k-15}$. It follows that for $e\ge3$, $\mathrm{EM}^e\gg N^2$ for all practical $k$, and that's more than enough to solve a number of small $e$ issues :

• any known extension of the $e^\text{th}$ root attack (in this attack against textbook RSA, where $C\gets M^e\bmod N$, it is used that for $M<N^{1/e}$, we can compute back $M$ from $C$ as $M\gets\sqrt[e]C$ )
• Coppersmith's Short Pad Attack (which extends the Franklin-Reiter related messages attack to random padding).

RSAES-PKCS1-v1_5 also practically thwarts Hastad's broadcast attack. In this attack against textbook RSA, sending the same message to at least $e$ recipients allows decryption. The random $\mathrm{PS}$ makes $\mathrm{EM}$ for the same $M$ potentially different. Even for $e=3$, $\mathrm{PS}$ at the 8-byte minimum, and $2^{36}$ recipients of the same message $M$, probability that $e$ padded messages $\mathrm{EM}$ are identical is lower than one in a million, if I got the math right.

However, many RSAES-PKCS1-v1_5 implementations are vulnerable when used with small $e$, such as $e=3$. That's because implementations often check that the first two bytes of $C^d\bmod N$ are $\mathtt{0x00}\mathbin\|\mathtt{0x02}$, and/or parse what follows in order to find the first $\mathtt{0x00}$, indicating the start of $M$ and allowing recovery of $\mathrm{mLen}$. When the result of such check is made available in a way leaking where the failure occurred (by a detailed error code, or timing, or some other side channel) to adversaries able to submit cryptograms for decryption, then Bleichenbacher's padding oracle attack applies. It turns a moderate number of queries to a decrypting entity into an RSA private-key operation for arbitrary argument, allowing decryption of one message, or computing one signature if the same key is used for encryption and signature.

That's not a fatality, though: RSAES-PKCS1-v1_5 padding can be checked in constant time, with a single error code regardless of the particular failure. Another possible strategy is to not check the left 10 bytes; or when $\mathrm{mLen}$ is known in advance, make no padding check and simply extract $M$ as the rightmost $\mathrm{mLen}$ bytes of $C^d\bmod N$.

PKCS#1 v1.5 describes a method (known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption system for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider).

For a $k$-byte ($8k-7$ to $8k$-bit) public modulus part of public key $(N,e)$, the message to be encrypted $M$ is a $\mathrm{mLen}$-byte bytestring with $\mathrm{mLen}\le k-11$. Message $M$ is turned into $\mathrm{EM}=\mathtt{0x00}\mathbin\|\mathtt{0x02}\mathbin\|\mathrm{PS}\mathbin\|\mathtt{0x00}\mathbin\|M$ where $\mathrm{PS}$ is drawn as a $k-\mathrm{mLen}-3$-byte bytestring consisting of fresh near uniformly random non-zero bytes. Then (with big-endian conversion between bytestrings and integer left implicit) the ciphertext is $C\gets\mathrm{EM}^e\bmod N$. That's textbook RSA encryption of $\mathrm{EM}$.

A brute-force method to verify a guess of plaintext $M$ becomes: try all the possible $\mathrm{PS}$ and compute the corresponding $C$, until one matches. That seems to require $255^{k-\mathrm{mLen}-3}/2$ try on average. That's next to $2^{63}$ at least, and growing by a factor of $255$ for each byte of message capacity that we remove. That's believed to solve the guessable plaintext problem for an offline adversary (but we have no formal proof that it does).

Thanks to the $\mathtt{0x02}$ as the second byte of $\mathrm{EM}$, it holds that $\mathrm{EM}>2^{8k-15}$. It follows that for $e\ge3$, $\mathrm{EM}^e\gg N^2$ for all practical $k$, and that's more than enough to solve a number of small $e$ issues

• any known extension of the $e^\text{th}$ root attack (in this attack against textbook RSA, where $C\gets M^e\bmod N$, it is used that for $M<N^{1/e}$, we can compute back $M$ from $C$ as $M\gets\sqrt[e]C$ )
• Coppersmith's Short Pad Attack (which extends the Franklin-Reiter related messages attack to random padding).

RSAES-PKCS1-v1_5 also practically thwarts Hastad's broadcast attack. In this attack against textbook RSA, sending the same message to at least $e$ recipients allows decryption. The random $\mathrm{PS}$ makes $\mathrm{EM}$ for the same $M$ potentially different. For $e=3$, $\mathrm{PS}$ at the 8-byte minimum, and $2^{36}$ recipients of the same message $M$, probability that $e$ padded messages $\mathrm{EM}$ are identical is lower than one in a million, if I got the math right.

However, many RSAES-PKCS1-v1_5 implementations are vulnerable when used with small $e$, in particular $e=3$. That because implementations often check that the first two bytes of $C^d\bmod N$ are $\mathtt{0x00}\mathbin\|\mathtt{0x02}$, and/or (in order to recover the length $\mathrm{mLen}$) parse what follows in order to find the first $\mathtt{0x00}$, indicating the start of $M$. When the result of such check is made available in a way leakign where the failrue occurred (by a detailed error code, or timing, or some other side channel) to adversaries able to submit cryptograms for decryption, then Bleichenbacher's padding oracle attack applies. It turns a moderate number of queries to a decrypting entity into an RSA private-key operation for arbitrary argument, allowing decryption of any message, or computing a signature if the same key is used for encryption and signature.

That's not a fatality, though: RSAES-PKCS1-v1_5 padding can be checked in constant time, with a single error code regardless of the particular failure. Another possible strategy is to not check the left 10 bytes; or when $\mathrm{mLen}$ is known in advance, make no padding check and simply extract $M$ as the rightmost $\mathrm{mLen}$ bytes of $C^d\bmod N$.

PKCS#1 v1.5 describes a method (known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption system for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider).

For a $k$-byte ($8k-7$ to $8k$-bit) public modulus part of public key $(N,e)$, the message to be encrypted $M$ is a $\mathrm{mLen}$-byte bytestring with $\mathrm{mLen}\le k-11$. Message $M$ is turned into $\mathrm{EM}=\mathtt{0x00}\mathbin\|\mathtt{0x02}\mathbin\|\mathrm{PS}\mathbin\|\mathtt{0x00}\mathbin\|M$ where $\mathrm{PS}$ is drawn as a $k-\mathrm{mLen}-3$-byte bytestring consisting of fresh near uniformly random non-zero bytes. Then (with big-endian conversion between bytestrings and integer left implicit) the ciphertext is $C\gets\mathrm{EM}^e\bmod N$. That's textbook RSA encryption of $\mathrm{EM}$.

While plaintext $M$ might still be easily guessable, verify such guess becomes much harder. A brute-force method becomes: try all the possible $\mathrm{PS}$ and compute the corresponding $C$, until one matches. That seems to require $255^{k-\mathrm{mLen}-3}/2$ try on average (for each possible $M$). That's next to $2^{63}$ at least, and growing by a factor of $255$ for each byte of message capacity that we remove. That's believed to solve the guessable plaintext problem by an (offline) adversary; but we have no formal proof that it does.

Thanks to the $\mathtt{0x02}$ as the second byte of $\mathrm{EM}$, it holds that $\mathrm{EM}>2^{8k-15}$. It follows that for $e\ge3$, $\mathrm{EM}^e\gg N^2$ for all practical $k$, and that's more than enough to solve a number of small $e$ issues

• any known extension of the $e^\text{th}$ root attack (in this attack against textbook RSA, where $C\gets M^e\bmod N$, it is used that for $M<N^{1/e}$, we can compute back $M$ from $C$ as $M\gets\sqrt[e]C$ )
• Coppersmith's Short Pad Attack (which extends the Franklin-Reiter related messages attack to random padding).

RSAES-PKCS1-v1_5 also practically thwarts Hastad's broadcast attack. In this attack against textbook RSA, sending the same message to at least $e$ recipients allows decryption. The random $\mathrm{PS}$ makes $\mathrm{EM}$ for the same $M$ potentially different. For $e=3$, $\mathrm{PS}$ at the 8-byte minimum, and $2^{36}$ recipients of the same message $M$, probability that $e$ padded messages $\mathrm{EM}$ are identical is lower than one in a million, if I got the math right.

However, many RSAES-PKCS1-v1_5 implementations are vulnerable when used with small $e$, such as $e=3$. That because implementations often check that the first two bytes of $C^d\bmod N$ are $\mathtt{0x00}\mathbin\|\mathtt{0x02}$, and/or parse what follows in order to find the first $\mathtt{0x00}$, indicating the start of $M$ and allowing recovery of $\mathrm{mLen}$. When the result of such check is made available in a way leaking where the failure occurred (by a detailed error code, or timing, or some other side channel) to adversaries able to submit cryptograms for decryption, then Bleichenbacher's padding oracle attack applies. It turns a moderate number of queries to a decrypting entity into an RSA private-key operation for arbitrary argument, allowing decryption of any message, or computing a signature if the same key is used for encryption and signature.

That's not a fatality, though: RSAES-PKCS1-v1_5 padding can be checked in constant time, with a single error code regardless of the particular failure. Another possible strategy is to not check the left 10 bytes; or when $\mathrm{mLen}$ is known in advance, make no padding check and simply extract $M$ as the rightmost $\mathrm{mLen}$ bytes of $C^d\bmod N$.

PKCS#1 v1.5 describes a method (known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption system for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider).

For a $k$-byte ($8k-7$ to $8k$-bit) public modulus part of public key $(N,e)$, the message to be encrypted $M$ is a $\mathrm{mLen}$-byte bytestring with $\mathrm{mLen}\le k-11$. Message $M$ is turned into $\mathrm{EM}=\mathtt{0x00}\mathbin\|\mathtt{0x02}\mathbin\|\mathrm{PS}\mathbin\|\mathtt{0x00}\mathbin\|M$ where $\mathrm{PS}$ is drawn as a $k-\mathrm{mLen}-3$-byte bytestring consisting of fresh near uniformly random non-zero bytes. Then (with big-endian conversion between bytestrings and integer left implicit) the ciphertext is $C\gets\mathrm{EM}^e\bmod N$. That's textbook RSA encryption of $\mathrm{EM}$.

A brute-force method to verify a guess of plaintext $M$ becomes: try all the possible $\mathrm{PS}$ and compute the corresponding $C$, until one matches. That seems to require $255^{k-\mathrm{mLen}-3}/2$ try on average. That's next to $2^{63}$ at least, and growing by a factor of $255$ for each byte of message capacity that we remove. That's believed to solve the guessable plaintext problem for an offline adversary (but we have no formal proof that it does).

Thanks to the $\mathtt{0x02}$ as the second byte of $\mathrm{EM}$, it holds that $\mathrm{EM}>2^{8k-15}$. It follows that for $e\ge3$, $\mathrm{EM}^e\gg N^2$ for all practical $k$, and that's more than enough to solve a number of small $e$ issues

• any known extension of the $e^\text{th}$ root attack (in this attack against textbook RSA, where $C\gets M^e\bmod N$, it is used that for $M<N^{1/e}$, we can compute back $M$ from $C$ as $M\gets\sqrt[e]C$ )
• Coppersmith's Short Pad Attack (which extends the Franklin-Reiter related messages attack to random padding).

RSAES-PKCS1-v1_5 also practically thwarts Hastad's broadcast attack. In this attack against textbook RSA, sending the same message to at least $e$ recipients allows decryption. The random $\mathrm{PS}$ makes $\mathrm{EM}$ for the same $M$ potentially different. For $e=3$, $\mathrm{PS}$ at the 8-byte minimum, and $2^{36}$ recipients of the same message $M$, probability that $e$ padded messages $\mathrm{EM}$ are identical is lower than one in a million, if I got the math right.

However, many RSAES-PKCS1-v1_5 implementations are vulnerable when used with small $e$, in particular $e=3$. That because implementations often check that the first two bytes of $C^d\bmod N$ are $\mathtt{0x00}\mathbin\|\mathtt{0x02}$, and/or (in order to recover the length $\mathrm{mLen}$) parse what follows in order to find the first $\mathtt{0x00}$, indicating the start of $M$. When the result of such check is made available (by an error code, or timing, or some other side channel) to adversaries able to submit cryptograms for decryption, then Bleichenbacher's attack applies. It turns a moderate number of queries to a decrypting entity into an RSA private-key operation for arbitrary argument, allowing decryption of any message, or a signature if the same key is used for encryption and signature. That's not a fatality, though: the padding can be checked in constant time, with a single error code regardless of the particular failure. Another possible strategy is to not check the left 10 bytes; or when $\mathrm{mLen}$ is known in advance, make no padding check and simply extract $M$ as the rightmost $\mathrm{mLen}$ bytes of $C^d\bmod N$.

PKCS#1 v1.5 describes a method (known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption system for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider).

For a $k$-byte ($8k-7$ to $8k$-bit) public modulus part of public key $(N,e)$, the message to be encrypted $M$ is a $\mathrm{mLen}$-byte bytestring with $\mathrm{mLen}\le k-11$. Message $M$ is turned into $\mathrm{EM}=\mathtt{0x00}\mathbin\|\mathtt{0x02}\mathbin\|\mathrm{PS}\mathbin\|\mathtt{0x00}\mathbin\|M$ where $\mathrm{PS}$ is drawn as a $k-\mathrm{mLen}-3$-byte bytestring consisting of fresh near uniformly random non-zero bytes. Then (with big-endian conversion between bytestrings and integer left implicit) the ciphertext is $C\gets\mathrm{EM}^e\bmod N$. That's textbook RSA encryption of $\mathrm{EM}$.

A brute-force method to verify a guess of plaintext $M$ becomes: try all the possible $\mathrm{PS}$ and compute the corresponding $C$, until one matches. That seems to require $255^{k-\mathrm{mLen}-3}/2$ try on average. That's next to $2^{63}$ at least, and growing by a factor of $255$ for each byte of message capacity that we remove. That's believed to solve the guessable plaintext problem for an offline adversary (but we have no formal proof that it does).

Thanks to the $\mathtt{0x02}$ as the second byte of $\mathrm{EM}$, it holds that $\mathrm{EM}>2^{8k-15}$. It follows that for $e\ge3$, $\mathrm{EM}^e\gg N^2$ for all practical $k$, and that's more than enough to solve a number of small $e$ issues

• any known extension of the $e^\text{th}$ root attack (in this attack against textbook RSA, where $C\gets M^e\bmod N$, it is used that for $M<N^{1/e}$, we can compute back $M$ from $C$ as $M\gets\sqrt[e]C$ )
• Coppersmith's Short Pad Attack (which extends the Franklin-Reiter related messages attack to random padding).

RSAES-PKCS1-v1_5 also practically thwarts Hastad's broadcast attack. In this attack against textbook RSA, sending the same message to at least $e$ recipients allows decryption. The random $\mathrm{PS}$ makes $\mathrm{EM}$ for the same $M$ potentially different. For $e=3$, $\mathrm{PS}$ at the 8-byte minimum, and $2^{36}$ recipients of the same message $M$, probability that $e$ padded messages $\mathrm{EM}$ are identical is lower than one in a million, if I got the math right.

However, many RSAES-PKCS1-v1_5 implementations are vulnerable when used with small $e$, in particular $e=3$. That because implementations often check that the first two bytes of $C^d\bmod N$ are $\mathtt{0x00}\mathbin\|\mathtt{0x02}$, and/or (in order to recover the length $\mathrm{mLen}$) parse what follows in order to find the first $\mathtt{0x00}$, indicating the start of $M$. When the result of such check is made available in a way leakign where the failrue occurred (by a detailed error code, or timing, or some other side channel) to adversaries able to submit cryptograms for decryption, then Bleichenbacher's padding oracle attack applies. It turns a moderate number of queries to a decrypting entity into an RSA private-key operation for arbitrary argument, allowing decryption of any message, or computing a signature if the same key is used for encryption and signature. 

That's not a fatality, though: RSAES-PKCS1-v1_5 padding can be checked in constant time, with a single error code regardless of the particular failure. Another possible strategy is to not check the left 10 bytes; or when $\mathrm{mLen}$ is known in advance, make no padding check and simply extract $M$ as the rightmost $\mathrm{mLen}$ bytes of $C^d\bmod N$.