RSA PKCS#1, v1.5 padding output

Question

If I make use of RSA PKCS#1 in v1.5 what padding length is used. Basically, it is not allowed that the plaintext is bigger than the modulus. But what if the length in bits is the same (padding to modulus size) but then the plaintext value is bigger than the modulus. How to avoid that?

Answer 1

The overhead of PKCS#1 v1.5 padding is at least 11 bytes. 8 of these bytes are a random value in the range [1..255]. This makes it unlikely that the same ciphertext is generated for identical plaintext input. Note that the padding is placed before encryption. The output size will be identical to the modulus size (in bytes, rounded downwards, if applicable).

Or, as PKCS#1 v2.1 puts it:

Input:

(n, e) : recipient's RSA public key (k denotes the length in octets of the modulus n)

M : message to be encrypted, an octet string of length mLen, where mLen <= k - 11

and, in case the plaintext message is larger:

Error: "message too long"

(which in API's is translated into a runtime specific error, e.g. an Exception - which may well have a different error text - in Java).

Note that PKCS#1 v1.5 padding is used both for encryption as well as for signature generation. The v1.5 paddings used are however different for encryption and signature generation. I've focussed on padding for encryption as the padding for signature generation is performed over a message digest (secure hash value). Hash values are limited in size of course, so for practical key sizes the padding overhead doesn't matter.

Notes:

• usually the RSA padding is simply used to wrap a newly created symmetric data/session key, which in turn is used to encrypt the data (i.e. the overhead doesn't matter much); this is called a hybrid cryptosystem.