RSA - PKCS#1 padding - overall correction of algorithm From PKCS#1, page 24:

After we create the EM byte string and convert it to an integer, we then encrypt that integer with RSAEP (page 10) to get the ciphertext (as an integer).

My question arrives from the fact that RSAEP demands the input ($m$) to be less than the modulus ($n$).

My question is simple - how are we guaranteed that the integer representation of EM is in fact less than $n$?

Since that 15th bit (starting from the MSB) is $1$ (because the second byte (starting from the MSB) is 0x02), we know that m (the integer representation of EM) must be larger than $2^{8k-15+1}$ (where $k$ is the number of bytes in EM).

So overall, we know that $m\geq 2^{8k-14}$.

What stops $n$ (the modulus) from being less than $2^{8k-14}$?

I don't see a reason why $n$'s first 2 bytes can't be $0$, and the $k-2$ bytes that are left would be 1. In this case, $n=2^{8(k-2)+1}-1 = 2^{8k-15}-1$, and we can clearly see that
$m \geq 2^{8k-14} &gt; 2^{8k-15}-1 = n.$

i.e. $m &gt; n$.

What am I getting wrong here?

P.S. I hope I managed to make my question clear. Please ask me if I didn't explain myself well enough.
The case that the (encoded) message may be too long for proper encryption has already been envisioned and mitigated by the designers of the specification of the padding scheme.

First note, that $k$ in fact denotes the length of the modulus $n$ - in bytes. This length is always accurate, so if $k=256$ the modulus has a bitlength somewhere in $[2041;2048]$ or otherwise $k&lt;256$ if the modulus was shorter. 

So let's consider what can happen regarding the length issue.
If you choose the length of your message $mLen$ to be larger than the modulus, step one of the specification tells you to output "message too long". Theoretically you could apply the rest of the scheme if your message was three bytes shorter than the modulus, but it allows only for 11 bytes shorter to allow the random string $PS$ to take at least 64-bits length.

And finally let's consider how long $EM$ is. If you convert EM to an integer you'll get $k-1 = EM$ as the first byte is zeroed out. To make things sure even the second most significant byte is nearly completely zeroed out (except for the bit #15 you correctly identified). But as the modulus is guaranteed to be of accurate length, you'll never get this equation not to hold: $$n&gt;2^{8(k-1)}&gt;2^{8k-14}&gt;EM &gt; 2^{8k-15}$$