# 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} > 2^{8k-15}-1 = n.$

i.e. $m > 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.

• maybe the very first step: "If $mLen > k-11$, output "message too long" and stop" and please note: usually one specifically sets the MSB of the primes to guarantee that n is actually of the desired size. Commented Aug 27, 2015 at 18:23
• @SEJPM Correct my if I'm wrong, but what you're saying is that usualy the msb of n is 1? Commented Aug 27, 2015 at 19:41
• The MSB of any integer is by definition one, because it's the highest significant bit. What I'm saying is that a) I think the above check should prevent $|EM|>k$ and b) $n$ is always of size $8k$. Commented Aug 27, 2015 at 19:48
• @SEJPM Could you please convert the comments into an answer? Commented Aug 27, 2015 at 20:50

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<256$ if the modulus was shorter.
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>2^{8(k-1)}>2^{8k-14}>EM > 2^{8k-15}$$