A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives a recipient confidence that the message came from a sender known to the recipient.
Digital signatures are a standard element of most cryptographic protocol suites, 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.
Digital signatures are often used to implement electronic signatures, which include any electronic data that carries the intent of a signature, but not all electronic signatures use digital signatures. Electronic signatures have legal significance in some countries, including Canada, South Africa, the United States, Algeria, Turkey, India, Brazil, Indonesia, Mexico, Saudi Arabia, Uruguay, Switzerland, Chile and the countries of the European Union.
Digital signatures employ asymmetric cryptography. In many instances, they provide a layer of validation and security to messages sent through a non-secure channel: Properly implemented, a digital signature gives the receiver reason to believe the message was sent by the claimed sender. Digital signatures are equivalent to traditional handwritten signatures in many respects, but properly implemented digital signatures are more difficult to forge than the handwritten type. Digital signature schemes, in the sense used here, are cryptographically based, and must be implemented properly to be effective. They can also provide non-repudiation, meaning that the signer cannot successfully claim they did not sign a message, while also claiming their private key remains secret. Further, some non-repudiation schemes offer a timestamp for the digital signature, so that even if the private key is exposed, the signature is valid. Digitally signed messages may be anything representable as a bitstring: examples include electronic mail, contracts, or a message sent via some other cryptographic protocol.
Definition
A digital signature scheme typically consists of three algorithms: A key generation algorithm that selects a private key uniformly at random from a set of possible private keys. The algorithm outputs the private key and a corresponding public key. A signing algorithm that, given a message and a private key, produces a signature. A signature verifying algorithm that, given the message, public key and signature, either accepts or rejects the message's claim to authenticity.
Two main properties are required:
First, the authenticity of a signature generated from a fixed message and fixed private key can be verified by using the corresponding public key.
Secondly, it should be computationally infeasible to generate a valid signature for a party without knowing that party's private key. A digital signature is an authentication mechanism that enables the creator of the message to attach a code that acts as a signature. The Digital Signature Algorithm (DSA), developed by the National Institute of Standards and Technology, is one of many examples of a signing algorithm.
In the following discussion, 1n refers to a unary number.
Formally, a digital signature scheme is a triple of probabilistic polynomial time algorithms, (G, S, V), satisfying: G (key-generator) generates a public key (pk), and a corresponding private key (sk), on input 1n, where n is the security parameter. S (signing) returns a tag, t, on the inputs: the private key (sk), and a string (x). V (verifying) outputs accepted or rejected on the inputs: the public key (pk), a string (x), and a tag (t). For correctness, S and V must satisfy
Pr [ (pk, sk) ← G(1n), V( pk, x, S(sk, x) ) = accepted ] = 1.
A digital signature scheme is secure if for every non-uniform probabilistic polynomial time adversary, A
Pr [ (pk, sk) ← G(1n), (x, t) ← AS(sk, · )(pk, 1n), x ∉ Q, V(pk, x, t) = accepted] < negl(n),
where AS(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.