F.3 Digital signature giving message recovery

This appendix outlines the digital signature scheme with message recovery using a hash function as described in the EMV ¢ specification for security [4], which is further adapted from the standard ISO/IEC 9796-2 as follows :

The signature generation and signature verification functions are performed only with the secret and public RSA operations with odd exponents. This is because the Rabin variant of RSA, using even exponents, and in particular a public exponent equal to 2, was proven insecure . When the attacker can persuade the signer to produce signatures on a few particular messages chosen by the attacker, the attacker can actually compute the signer's private signing key [2]. This is the reason way the Rabin variant was removed from the list of approved cryptographic algorithms for asymmetric cryptography in the EMV 2000 specifications [4].
The redundancy function is implemented with a hash function, like the SHA-1 with a hash code of 160 bits (see Appendix D, Section D.2), which avoids some of the recent attacks on the standard ISO/IEC 9796-1 [5 “8]. In the RSA case with odd exponents, the details of the attack vary depending on the particularities of the methods for padding and adding redundancy to the data string before applying the RSA secret operation. In all cases the attack requires the construction of a large set of chosen data strings with special mathematical properties, which are not meaningful for specific applications. However, none of these attacks would succeed if a hash code is always signed rather than any other redundancy-built message.
Add a header and trailer byte to obtain a unique recovery procedure.

F.3.1 Signature generation

The signature is computed by the signer on a message M = M _R M ² , where M _R is the part recoverable from the signature and M ² is the part that must be separately sent by the signer. The byte-length of the message M is L . The secret RSA operation is performed with respect to the modulus n _S of bytelength N and the secret exponent d _S . In this setup the signature generation algorithm takes place in the following way.

Case 1: Message M entirely recoverable from S In this case M = M _R and M ² is empty, which is equivalent to L ‰ N “ 22.

Compute the hash code of M through the SHA-1 algorithm and store the result of 20 bytes in H .
When L = N “ 22, define B = 4A. Otherwise, define block B as a byte string of N “ 21 “ L bytes, B = (4B BB BB BA).
Define E = BC.
Define the N -byte block X as the concatenation of B , M , H , and E (i.e., X = B M H E ).
Compute the RSA secret operation on X corresponding to the signature generation mode and obtain the signature S = Sign ( KS _A )[ X ] = S ( n _S , d _S )[ X ] = X ^( d _S ) mod n _S .

Case 2: Message M is not entirely recoverable from S In this case M = M _R M ² , where M _R is N “ 22 bytes and M ² is L “ N + 22 bytes.

Compute the hash code of M through the SHA-1 algorithm and store the result of 20 bytes in H .
Split M = M _R M ² , where M _R is N “ 22 bytes and M ² is L “ N + 22 bytes.
Define B = 6A.
Define E = BC.
Define the N -byte block X as the concatenation of B, M _R , H , and E (i.e., X = B M _R H E ).
Compute the RSA secret operation on X corresponding to the signature generation mode and obtain the signature S = Sign ( KS _A )[ X ] = S ( n _S , d _S )[ X ] = X ^( d _S ) mod n _S .

F.3.2 Signature verification

The verifier performs the signature verification on the signature S .If the message M is bigger than N “ 22 bytes, then the part M ² of the message that can not be retrieved from S is also an input to the recover predicate. The public RSA operation is performed with respect to the modulus n _S of bytelength N and the public exponent e _S . In this setup the signature verification algorithm takes place in the following way.

Case 1: Message M entirely recoverable from S In this case M = M _R and M ² is empty, which is equivalent to L ‰ N “ 22.

Check that the byte-length of S is N .
Retrieve the N byte number X from the digital signature S with the formula X = Recover ( KV _A )[ S , M ² = empty ] = P ( n _S , e _S )[ S ] = S ^( e _S )mod n _S .
Check the redundancy of X . To this end X is first split in X = B M H E , where:
- B = ˜4A or B is a leading byte string of the form B = (4B BB BB BA).
- H is 20 bytes long.
- E is 1 byte long.
- M = M _R consists of the remaining bytes.
Check whether the byte E is equal to BC.
Check whether SHA-1( M )?= H .

If and only if all the checks from steps 3 to 5 are passed, is the signature accepted as genuine .

Case 2: Message M is not entirely recoverable from S. In this case M = M _R M ² , where M _R is N “ 22 bytes and can be recovered from the signature. The part M ² is L “ N + 22 bytes and has to be separately sent to the verifier.

Check that the byte-length of S is N .
Retrieve the N byte number X from the digital signature S with the formula X = Recover ( KV _A )[ S , M ² ] = P ( n _S , e _S )[ S ] = S ^( e _S )mod n _S .
Check the redundancy of X . To this end X is first split in X = B M _R H E , where:
- B is 1 byte long.
- H is 20 bytes long.
- E is 1 byte long.
- M _R consists of the remaining N “ 22 bytes.
Check whether the byte B is equal to 6A.
Check whether the byte E is equal to BC.
Concatenate the part M _R recovered from X with the part sent separately by the signer M ² (i.e., compute M = M _R M ² ). Check whether SHA-1( M ) = H .

If and only if all the checks from steps 3 to 6 are passed is the signature accepted as genuine.