2
$\begingroup$

I am reading a content, and am not sure if I follow how they come up with the maximum data size which can be signed by an RSA key. The author states:

"... if you are trying to sign a message using a 2048-bit RSA key whose public key size is 256 bytes, the maximum length is 256 bytes minus the encoding parameters, in this case 11 bytes. Therefore the maximum length of the data message that can be signed directly is 254 bytes ..."

I am not sure if I need to know a little more about RSA to know what the 11 bytes of encoding parameters are. My question(s) are:

  • How did he come up with the 254? 256 - 11 = 245
  • How did he get the maximum of 256 bytes?
$\endgroup$
1
  • $\begingroup$ The quote lacks precision. Indeed, there is 254 where 245 is thought, and the reasoning is not given. Also, "public key size is 256 bytes" should be "the public modulus in the public key is 256 bytes, ignoring formatting". $\endgroup$
    – fgrieu
    Mar 9, 2017 at 14:03

1 Answer 1

3
$\begingroup$

See step 3, 4 & 5 of 9.2 EMSA-PKCS1-v1_5 that defines the PKCS#1 v1.5 padding mechanism for signature generation:

  1. If emLen < tLen + 11, output "intended encoded message length too short" and stop.
  2. Generate an octet string PS consisting of emLen - tLen - 3 octets with hexadecimal value 0xff. The length of PS will be at least 8 octets.
  1. Concatenate PS, the DER encoding T, and other padding to form the encoded message EM as
    EM = 0x00 || 0x01 || PS || 0x00 || T

EM will have the same length as the modulus.

This means that T, the data that is padded and then used as input for modular exponentiation is modulus size - 11 bytes (if the modulus size in bits is a multiple of 8). So the data that can be "directly" signed is 11 bytes shorter than the modulus.

This is however half the story. PKCS#1 v1.5 uses signatures in combination with a hash mechanism. This is in step 1..2:

  1. Apply the hash function to the message M to produce a hash value H:
    H = Hash(M).
 If the hash function outputs "message too long," output "message
  too long" and stop.
  1. Encode the algorithm ID for the hash function and the hash value into an ASN.1 value of type DigestInfo (see Appendix A.2.4) with the Distinguished Encoding Rules (DER), where the type DigestInfo has the syntax

DigestInfo ::= SEQUENCE { digestAlgorithm AlgorithmIdentifier, digest OCTET STRING }

 The first field identifies the hash function and the second
  contains the hash value.  Let T be the DER encoding of the
  DigestInfo value (see the notes below) and let tLen be the length
  in octets of T.

So if you use the PKCS#1 v1.5 standard then T will always fit into the modulus as it just contains an (identified) hash value. The message size is than limited to the input size of the hash function, which is virtually unlimited.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.