Purpose of leading zero in PKCS1-v1_5 padding

Question

According to this document the padded message has the following structure:

$EM \;= \; 0x00 \; || \; 0x02 \; || \; PS \; || \; 0x00 \; || \; M$

What is the purpose of this null byte at the beginning of the message?

After OS2IP decoding (also described in the document) to convert the message to a "bignum" I would expect this byte to be discarded, since a most significant byte of zero does not change the value of the number.

Also, when decoding the message, the standard document expects this zero byte to be present in the ouput too. Why should a bignum routine preserve a zero leading digit?

Instructions for decoding the message are given in the document and quoted below.

If the first octet of EM does not have hexadecimal value 0x00, if the second octet of EM does not have hexadecimal value 0x02, if there is no octet with hexadecimal value 0x00 to separate PS from M, or if the length of PS is less than 8 octets, output "decryption error" and stop.

Answer 1

The first byte is 0x00, because some standards allow RSA key sizes $8b+1, b \in \Bbb Z_+$. Such key would have 0x01 at the first bit, but it is possible for almost all other bits to be zero. Thus, 0x00 as the first byte allows interoperability with all possible RSA key sizes.

NIST's recommendations and few other standards actually recommend only few specific key sizes, where usually the most significant bit is set so technically it would be possible to use shorter encoding.

The 0x02 is simply number describing what encoding and how RSA was used. Currently there are two commonly used choices: 0x01 (private-key operations [commonly signing]), 0x02 public key encryption. (In addition, 0x00 used to exists, but it is not in common use anymore.)

You may also take a look at http://tools.ietf.org/html/rfc2313 (PKCS#1v1.5) [especially section 8.1] for details, or one of later RFC's for PKCS#1v2.x.