1
$\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$
  • $\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 '17 at 14:03
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.

  3. 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.

  2. 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, privacy policy and cookie policy

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