Security Engineering. Ross Anderson

in section 4.7.1 in that they were principally designed to help you set up a pairing key with the right device in a benign environment, rather than defending against a sophisticated attack in a hostile one. The more modern ones appear to be better, but it's really just theatre.

      So many things go wrong: protocols that will generate or accept very weak keys and thus give only the appearance of protection; programs that leak keys via side channels such as the length of time they take to decrypt; and software vulnerabilities leading to stack overflows and other hacks. If you're implementing public-key cryptography you need to consult up-to-date standards, use properly accredited toolkits, and get someone knowledgeable to evaluate what you've done. And please don't write the actual crypto code on your own – doing it properly requires a lot of different skills, from computational number theory to side-channel analysis and formal methods. Even using good crypto libraries gives you plenty of opportunities to shoot your foot off.

       5.7.2.3 ElGamal digital signature and DSA

      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.

      5.7.3 Elliptic curve cryptography

      Discrete logarithms and their analogues exist in many other mathematical structures. Elliptic curve cryptography uses discrete logarithms on an elliptic curve – a curve given by an equation like . These curves have the property that you can define an addition operation on them and the resulting Mordell group can be used for cryptography. The algebra gets a bit complex and this book isn't the place to set it out⁹. However, elliptic curve cryptosystems are interesting for at least two reasons.

First is performance; they give versions of the familiar primitives such as Diffie-Hellmann key exchange and the Digital Signature Algorithm that use less computation,