RSASSA-PKCS1-v1_5 algorithms 2 – Digital Signatures
These attacks illustrate why the input to the RSA signature generation function must be constructed in a secure manner and why the EMSA-PKCS1-v1_5 encoding uses a cryptographically secure hash function.
More precisely, the EMSA-PKCS1-v1_5 encoding is computed as follows:
- Compute H = h(M).
- Encode the ID of the hash function h and the hash value into an ASN.1 value of type DigestInfo T with Distinguished Encoding Rules (DER).
- Generate an l − lT − 3-byte string P of 0xff values where lT is the length of the DER encoding of T.
- Concatenate P, DER encoding T, and additional padding into the string
5. Output m.
With the EMSA-PKCS1-v1_5 encoding function and the RSASP1 function in place, Alice can generate the digital signature S for a plaintext message M. She does this as follows:
- Compute the EMSA-PKCS1-v1_5 encoding for the input message M:
where k is the size RSA modulus n in bytes.
2. Compute the integer representation for the encoded message m′ as
where OS2IP is an octet-string-to-integer data conversion primitive that takes a byte string and converts it into a non-negative integer.
3. Compute the RSASP1 function using the integer representation m and Alice’s private key (n,d) as inputs to obtain the signature as integer representation s:
4. Convert the integer representation s into a byte string S as
where I2OSP is a data conversion primitive that takes a non-negative integer and outputs a byte string of length l.
5. Output signature S.
To verify Alice’s digital signature for the message he received, Bob needs three inputs:
- Alice’s public RSA key (n,e)
- The byte string M representing Alice’s message whose signature Bob wants to verify
- The signature S itself
With these inputs, Bob performs the signature verification using the following steps:
- Check that the signature length is l bytes, reject the signature otherwise.
- Convert signature S into its integer representation:
3. Compute the RSAVP1 function using Alice’s public key (n,e) and the signature’s integer representation s:
4. Convert the message integer representation m obtained in the previous step into the encoded message m′:
5. Compute the EMSA-PKCS1-v1_5 encoding for the received message M to produce a second encoded message m′′:
- If m′ = m′′, the digital signature is valid. Otherwise, the signature is invalid.
In Chapter 7, Public-Key Cryptography, we learned that the security of the RSA algorithm relies on the computational hardness of the factoring problem and the RSA problem. Moreover, the public key of the signing party – Alice in the preceding examples – must be authentic. Because the fastest known factoring algorithms have subexponential (but not polynomial!) running times (on conventional computers), cryptographers consider computing the e-th roots modulo n for large enough n to be computationally infeasible. With this assumption and the assumption that the hash function used in EMSA-PKCS1-V1_5 encoding is cryptographically secure, EMSA-PKCS1-V1_5 generates secure digital signatures.
In other words, without knowing Alice’s private RSA key, Eve cannot forge a signature in polynomial time. In addition, because the EMSA-PKCS1-V1_5 encoding includes the use of a cryptographically secure hash function, Eve must find collisions for that specific hash function if she wants to find a message that produces the same signature as some previous message signed by Alice. By definition, this is also computationally infeasible for a cryptographically secure hash function.