Читать книгу Security Engineering - Ross Anderson - Страница 186

Suppose that the base and the generator are public values chosen in some suitable way, and that each user who wishes to sign messages has a private signing key with a public signature verification key . An ElGamal signature scheme works as follows. Choose a message key at random, and form (mod ). Now form the signature using a linear equation in , , the message and the private key . There are a number of equations that will do; the one that happens to be used in ElGamal signatures is

So is computed as ; this is done modulo . When both sides are passed through our one-way homomorphism mod we get:

or

An ElGamal signature on the message consists of the values and , and the recipient can verify it using the above equation.

A few more details need to be fixed up to get a functional digital signature scheme. As before, bad choices of and can weaken the algorithm. We will also want to hash the message using a hash function so that we can sign messages of arbitrary length, and so that an opponent can't use the algorithm's algebraic structure to forge signatures on messages that were never signed. Having attended to these details and applied one or two optimisations, we get the Digital Signature Algorithm (DSA) which is a US standard and widely used in government applications.

DSA assumes a prime of typically 2048 bits⁷, a prime of 256 bits dividing , an element of order in the integers modulo , a secret signing key and a public verification key . The signature on a message , , is where

The hash function used by default is SHA256⁸.

DSA is the classic example of a randomised digital signature scheme without message recovery. The most commonly-used version nowadays is ECDSA, a variant based on elliptic curves, which we'll discuss now – this is for example the standard for cryptocurrency and increasingly also for certificates in bank smartcards.