Digital signature

• 1. Mathematical Foundations And Algorithms

  ›

  Alice signs a message by appending a signature computed from the message and her private key. Bob receives both the message and signature. He uses Alice's public key to verify the authenticity of the signed message. A digital signature scheme consists of three algorithms that define its operation. The first algorithm is key generation, which selects a private key at random from a set of possible private keys. This process outputs the private key and a corresponding public key. The second algorithm is signing, which takes a message and a private key as inputs to produce a signature. The third algorithm is verification, which accepts or rejects the message's claim to authenticity based on the public key and signature. Two main properties are required for any valid scheme. Correctness ensures signatures produced with a private key pass verification with the corresponding public key. Security requires existential unforgeability under chosen-message attack, meaning it must be computationally infeasible to generate a valid signature without knowing the private key.

• 2. Historical Development And Pioneers

  ›

  In 1976, Whitfield Diffie and Martin Hellman first described the notion of a digital signature scheme. They only conjectured that such schemes existed based on functions that are trapdoor one-way permutations. Soon afterwards, Ronald Rivest, Adi Shamir, and Len Adleman invented the RSA algorithm. This could be used to produce primitive digital signatures, although plain RSA signatures were not secure. The first widely marketed software package to offer digital signature was Lotus Notes 1.0, released in 1989. It used the RSA algorithm. Other digital signature schemes were soon developed after RSA. The earliest being Lamport signatures from October 1979. Merkle signatures, also known as Merkle trees or Hash trees, followed shortly. Rabin signatures emerged as another early variant. In 1988, Shafi Goldwasser, Silvio Micali, and Ronald Rivest became the first to rigorously define the security requirements of digital signature schemes. They described a hierarchy of attack models for signature schemes. They presented the GMR signature scheme, the first that could be proved to prevent even an existential forgery against a chosen message attack. This is the currently accepted security definition for signature schemes.

• 3. Security Models And Attack Vectors

  ›

  Goldwasser, Micali, and Rivest laid out a hierarchy of attack models against digital signatures in their foundational paper. In a key-only attack, the attacker is only given the public verification key. In a known message attack, the attacker is given valid signatures for a variety of messages known by the attacker but not chosen by the attacker. In an adaptive chosen message attack, the attacker first learns signatures on arbitrary messages of the attacker's choice. They also describe a hierarchy of attack results. A total break results in the recovery of the signing key. A universal forgery attack results in the ability to forge signatures for any message. A selective forgery attack results in a signature on a message of the adversary's choice. An existential forgery merely results in some valid message/signature pair not already known to the adversary. The strongest notion of security is security against existential forgery under an adaptive chosen message attack. To create a forgery, the attacker picks a random signature and uses the verification procedure to determine the corresponding message. In practice, however, this type of signature is not used directly. Instead, the message to be signed is first hashed to produce a short digest. This digest is then padded to larger width comparable to N before being signed with the reverse trapdoor function.

• 4. Practical Implementation And Hardware Security

  ›

  A private key can be stored on a user's computer and protected by a local password. This has two disadvantages: the user can only sign documents on that particular computer. The security of the private key depends entirely on the security of the computer. A more secure alternative is to store the private key on a smart card. Many smart cards are designed to be tamper-resistant, although some designs have been broken notably by Ross Anderson and his students. In a typical digital signature implementation, the hash calculated from the document is sent to the smart card. Its CPU signs the hash using the stored private key of the user and returns the signed hash. Typically, a user must activate their smart card by entering a personal identification number or PIN code. This provides two-factor authentication. It can be arranged that the private key never leaves the smart card, although this is not always implemented. If the smart card is stolen, the thief will still need the PIN code to generate a digital signature. Entering a PIN code commonly requires a numeric keypad. Some card readers have their own numeric keypad. This is safer than using a card reader integrated into a PC and then entering the PIN using that computer's keyboard. Specialized card readers are also less vulnerable to tampering with their software or hardware and are often EAL3 certified.

• 5. Legal Frameworks And Global Adoption

  ›

  Legislatures enacted statutes and regulations in many jurisdictions authorizing digital signatures. The first appears to have been in Utah in the United States. Other countries have also passed statutes or issued regulations in this area as well. The UN has had an active model law project for some time. These enactments vary from place to place and have typically embodied expectations at variance with the state of the underlying cryptographic engineering. They have had the net effect of confusing potential users and specifiers. Most digital signature schemes share goals regardless of cryptographic theory or legal provision. Quality algorithms must be used because some public-key algorithms are known to be insecure. Practical attacks against them have been discovered. Users must carry out the signature protocol properly. The private key must remain private. If the private key becomes known to any other party, that party can produce perfect digital signatures of anything. In several countries, a digital signature has a status somewhat like that of a traditional pen and paper signature. The 1999 EU digital signature directive and 2014 EU follow-on legislation generally mean that anything digitally signed legally binds the signer of the document to the terms therein.

• 6. Industry Standards And Interoperability

  ›

  Adoption of technical standards for digital signatures have lagged behind much of the legislation. This delays a more or less unified engineering position on interoperability, algorithm choice, and key lengths. Some industries have established common interoperability standards for use between members of the industry and with regulators. These include the Automotive Network Exchange for the automobile industry. The SAFE-BioPharma Association serves the healthcare industry. The United States Government Printing Office publishes electronic versions of the budget, public and private laws, and congressional bills with digital signatures. Universities including Penn State, University of Chicago, and Stanford publish electronic student transcripts with digital signatures. Some digital signature algorithms include RSA, DSA, ECDSA, and EdDSA. Others include ElGamal signature scheme as the predecessor to DSA. Variants Schnorr signature and Pointcheval, Stern signature algorithm exist. Pairing-based schemes such as BLS are also used. CRYSTALS-Dilithium is a quantum-resistant scheme based on LWE in lattices. Falcon is another quantum-resistant scheme based on CVP in lattices. SPHINCS+ is a quantum-resistant scheme based on hash functions. Undeniable signatures support aggregation where n signatures from n users can be combined into a single constant-size signature.