Overview

Content

RSA signature: PKCS, ISO/IEC 9796

ElGamal signature family: ElGamal, Schnorr, DSS, ECDSA

? Attacks on ElGamal signatures: existential forgery, Bleichenbacher attack

? Provable security: interactive proofs, random oracle model

As public-key cryptosystems are the asymmetric alternative to conventional encryption, there is an alternative to MAC algorithms which is the notion of digital signature. With it, a secret key is given to each person, and a corresponding public key is released. The person can sign any document, and anybody else can verify the correctness of the signature. We have already seen in Chapter 5 several signature schemes based on conventional cryptography: the Lamport scheme and the Merkle scheme based on hash trees. We study other schemes based on asymmetric cryptography techniques in this chapter.

10.1 Digital Signature Schemes

Formally, a public-key signature scheme consists of

• a pseudorandom key generator which generates a public key K _p and a secret key K _s;

• a signature algorithm which from each message X and the secret key K _s computes (in a deterministic or a probabilistic way) a signature ?;

• a verification algorithm which from each message X, signature ?, and public key K _p verifies (in a deterministic way) the correctness of the signature

(see Fig. 10.1).

Figure 10.1: Digital signature.

Digital signatures face several security issues.

1. They must provide authenticity and integrity. For this, it must be impossible for anyone who does not have access to the secret...