D.3 Digital signature schemes

A digital signature of a message is a string of bits dependent on some secret information known only to the originating entity and on the content of the message being signed. A digital signature associates a message with an originating entity, named the signer. A digital signature scheme is a suitable security mechanism for enforcing data authentication (data origin authentication and data integrity), entity authentication, and non- repudiation security services.

In the communication framework presented in Figure B.1, the sender of a message is the signer, while the receiver of a pair message/digital signature is the verifier of the signature.

A digital signature scheme consists of the following items:

A key generation algorithm KG , which generates a pair of a public verification key and private signing key ( KV , KS ) for the signer;
A signature generation algorithm Sign ( KS )[ M ], which is a method for producing a digital signature S on a suitably formatted message M using the private signing key KS ;
A signature verification algorithm Verify ( KV )[ S , M ² ]?= "True", which is a method that allows the receiver to verify a signature S on the formatted message M using the public verification key of the signer. The output of the verification algorithm yields either true or false .

A signing procedure consists of a method for formatting data into formatted messages that can be signed, a signature generation algorithm, and a signing protocol between the signer and the verifier. A verification procedure consists of a signature verification algorithm and a method for recovering data from the message.

The ordinary signing protocol between the signer and the verifier, which is needed for establishing a signing procedure, is a one-step protocol where the signer computes S = Sign ( KS )[ M ] using his or her private signing key KS on the message M . She sends to the receiver the signature S , eventually together with the message M in case it cannot be recovered from S . After receiving it, the receiver verifies the signature S on the message M using the public verification key KV of the signer. If the verification predicate Verify(KV) [ S , M ] yields true , the originating entity is considered authentic , the integrity of the message is accepted, and the receiver has an irrefutable proof in case the sender later repudiates having sent the message M . The protocol is schematized in Figure D.4.

Figure D.4: Ordinary signing protocol.

A digital signature scheme must fulfill the following requirements:

Each signer (Alice) can efficiently generate signatures on messages of her choice, using her private signing key KS.
Each verifier (Bob) can efficiently check the validity of a signature generated by a signer, using his public verification key KV.
An attacker, which knows only the public verification key of the signer and has recorded a finite sequence of pairs message/signature ( M _i , Sign ( KS )[ M _i ]), cannot efficiently generate signatures on behalf of the signer on new messages that she did not previously sign.

For the purposes of this book, only two types of attacks are considered in connection with digital signature schemes: the no-message attack and the adaptively chosen message attack. In both cases, the attacker has a limited computational power. In the no-message attack, the attacker only knows the signer's public verification key. In the adaptively chosen message attack, the attacker can dynamically ask the legitimate signer to sign any message, using her as a kind of oracle. At a first glance, the second type of attack seems only theoretical. The following example proves the contrary. Assume the attacker controls a card acceptor device and the signer is a chip card that implements an RSA signature scheme. Then, the attacker can format messages and send them to be signed by the card. With the supplementary knowledge the attacker accumulates from the pairs ( M _i , Sign ( KS )[ M _i ]), where the messages are chosen by herself, the chance to derive a signature on a new message that was never signed by the signer increases . This is the strongest attack on digital signature schemes.

Digital signature schemes can be grouped into signature schemes with appendix and signature schemes with recovery.

D.3.1 Signature scheme with appendix

A signature scheme with appendix requires the entire message M as an input to the verification algorithm. Thus, in this case M ² = M and the signer has to transmit the entire message M to the verifier for completing the verification algorithm. The verification predicate becomes Verify ( KV )[ S , M ] ?= "True".

Examples of signature schemes with appendix are RSA with PKCS#1 [10, 11] and DSA [12].

When the signer has to produce a signature on a message of variable length, or with a length that is much larger than the bit length of the formatted message accepted in the signature generation algorithm, then a signature scheme with appendix is the suitable mechanism. This approach is adopted on a communication channel between a mobile phone implementing a payment token and a wallet server implementing a payment mechanism. In this case the wallet server needs a non-repudiation guarantee for the payment order sent from the mobile phone of the customer.

The method of formatting messages to be signed from the message set into messages that can be signed, which form the signing set, uses a collision-resistant hash function H , which is applied to the message set.

D.3.2 Signature scheme with recovery

A signature scheme with recovery does not require a priori knowledge of the entire message M for performing the verification algorithm. In this case the verifier can recover a part M _R of M from S , such that the signer has to send only M ² separately to the verifier (i.e., M = M _R M ² ). There are situations when the entire message M can be recovered from S , the case for which M ² is empty and M = M _R . Since the verification algorithm recovers part of the formatted message, the verification predicate is referred to as the recovery predicate and is denoted Recover ( KV )[ S, M ² ] = {?"True", M _R }.

The ISO 9796-2 [13] standard describes signature schemes with recovery and illustrates the use of the RSA for implementing them.

Most signature schemes with message recovery are applied to messages of fixed length. As it will be presented in Section D.4, a public key certificate is a digital signature produced by a certification authority on the public encryption key or on the public verifying key of a participant in an electronic payment system. The length of such a public key is fixed and limited by a security parameter, like the bit length of the key. If the length of the formatted messages accepted in the signature algorithm is greater than the bit length of the key to be certified (plus some redundancy needed in the verification algorithm), then the signature scheme with recovery is the suitable mechanism for certification.

The method of formatting messages to be signed from the message set into messages that can be signed, which form the signing set, applies a redundancy function to the message set. A well-known example of a redundancy function is given in ISO 9796-2 [13].

The two types of schemes are not mutually exclusive. Specifically, any scheme giving message recovery can be used for provision of digital signatures with appendix. For example, in EMV ¢ [14] producing the signature consists of applying the scheme to a hash value of the message. If the message is short enough, then the verification algorithm recovers the entire message and the hash value from the signature (as will be described in Appendix F, Section F.3). Otherwise, the verification algorithm recovers only a part of the message in addition to the hash value.