Overview

A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives any recipient confidence that the message came from a sender known to the recipient. In contrast, a message authentication code only gives confidence to a specific recipient that the message came from a known sender.

Digital signatures are a type of public-key cryptography, and are commonly used for software distribution, financial transactions, contract management software, and in other cases where it is important to detect forgery or tampering.

A digital signature on a message or document is similar to a handwritten signature on paper, but it is not restricted to a physical medium like paper—any bitstring can be digitally signed—and while a handwritten signature on paper could be copied onto other paper in a forgery, a digital signature on a message is mathematically bound to the content of the message so that it is infeasible for anyone to forge a valid digital signature on any other message.

Definition

Here 1^(n) refers to a unary number in the formalism of computational complexity theory.

A digital signature scheme is secure if for every non-uniform probabilistic polynomial time adversary A,

where A^(S(sk, · )) denotes that A has access to the oracle, S(sk, · ), Q denotes the set of the queries on S made by A, which knows the public key, pk, and the security parameter, n, and x ∉ Q denotes that the adversary may not directly query the string, x, on S.

History

In 1976, Whitfield Diffie and Martin Hellman first described the notion of a digital signature scheme, although 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, which could be used to produce primitive digital signatures (although only as a proof-of-concept – "plain" RSA signatures are not secure). The first widely marketed software package to offer digital signature was Lotus Notes 1.0, released in 1989, which used the RSA algorithm.

Other digital signature schemes were soon developed after RSA, the earliest being Lamport signatures, Merkle signatures (also known as "Merkle trees" or simply "Hash trees"), and Rabin signatures.

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, and also presented the GMR signature scheme, the first that could be proved to prevent even an existential forgery against a chosen message attack, which is the currently accepted security definition for signature schemes.

The first such scheme which is not built on trapdoor functions but rather on a family of function with a much weaker required property of one-way permutation was presented by Moni Naor and Moti Yung.

Method

One digital signature scheme (of many) is based on RSA. To create signature keys, generate an RSA key pair containing a modulus, N, that is the product of two random secret distinct large primes, along with integers, e and d, such that e d ≡ 1 (mod φ(N)), where φ is Euler's totient function. The signer's public key consists of N and e, and the signer's secret key contains d.

Used directly, this type of signature scheme is vulnerable to key-only existential forgery attack. To create a forgery, the attacker picks a random signature σ and uses the verification procedure to determine the message, m, corresponding to that signature. In practice, however, this type of signature is not used directly, but rather, the message to be signed is first hashed to produce a short digest, that is then padded to larger width comparable to N, then signed with the reverse trapdoor function.

This forgery attack, then, only produces the padded hash function output that corresponds to σ, but not a message that leads to that value, which does not lead to an attack. In the random oracle model, hash-then-sign (an idealized version of that practice where hash and padding combined have close to N possible outputs), this form of signature is existentially unforgeable, even against a chosen-plaintext attack.

There are several reasons to sign such a hash (or message digest) instead of the whole document.

Applications

As organizations move away from paper documents with ink signatures or authenticity stamps, digital signatures can provide added assurances of the evidence to provenance, identity, and status of an electronic document as well as acknowledging informed consent and approval by a signatory. The United States Government Printing Office (GPO) publishes electronic versions of the budget, public and private laws, and congressional bills with digital signatures.^([failed verification]) Universities including Penn State, University of Chicago, and Stanford are publishing electronic student transcripts with digital signatures.