Digital signature


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 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.
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.

Definition

A digital signature scheme consists of three algorithms:
  • A key generation algorithm that selects a private key 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:
  1. Correctness: Signatures produced by the signing algorithm with a private key pass the verification algorithm with the corresponding public key.
  2. Security : It should be computationally infeasible to generate a valid signature for a party without knowing that party's private key.
Formally, a digital signature scheme is a triple of probabilistic polynomial-time algorithms,, satisfying:
  • G generates a public key, and a corresponding private key, on input 1n, where n is the security parameter.
  • S returns a tag, t, on the inputs: the private key, and a string.
  • V outputs accepted or rejected on the inputs: the public key, a string, and a tag.
Here 1n refers to a unary number in the formalism of computational complexity theory.
For correctness, S and V must satisfy
A digital signature scheme is secure if for every non-uniform probabilistic polynomial time adversary A,
where AS denotes that A has access to the oracle, S, 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. 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, 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 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 , 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, this form of signature is existentially unforgeable, even against a chosen-plaintext attack.
There are several reasons to sign such a hash instead of the whole document.
;For efficiency: The signature will be much shorter and thus save time since hashing is generally much faster than signing in practice.
;For compatibility: Messages are typically bit strings, but some signature schemes operate on other domains. A hash function can be used to convert an arbitrary input into the proper format.
;For integrity: Without the hash function, the text "to be signed" may have to be split in blocks small enough for the signature scheme to act on them directly. However, the receiver of the signed blocks is not able to recognize if all the blocks are present and in the appropriate order.

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 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 are publishing electronic student transcripts with digital signatures.
Below are some common reasons for applying a digital signature to communications:

Authentication

A message may have letterhead or a handwritten signature identifying its sender, but letterheads and handwritten signatures can be copied and pasted onto forged messages.
Even legitimate messages may be modified in transit.
If a bank's central office receives a letter claiming to be from a branch office with instructions to change the balance of an account, the central bankers need to be sure, before acting on the instructions, that they were actually sent by a branch banker, and not forged—whether a forger fabricated the whole letter, or just modified an existing letter in transit by adding some digits.
With a digital signature scheme, the central office can arrange beforehand to have a public key on file whose private key is known only to the branch office.
The branch office can later sign a message and the central office can use the public key to verify the signed message was not a forgery before acting on it.
A forger who doesn't know the sender's private key can't sign a different message, or even change a single digit in an existing message without making the recipient's signature verification fail.
Encryption can hide the content of the message from an eavesdropper, but encryption on its own may not let recipient verify the message's authenticity, or even detect selective modifications like changing a digit—if the bank's offices simply encrypted the messages they exchange, they could still be vulnerable to forgery.
In other applications, such as software updates, the messages are not secret—when a software author publishes a patch for all existing installations of the software to apply, the patch itself is not secret, but computers running the software must verify the authenticity of the patch before applying it, lest they become victims to malware.

Limitations

Replays.
A digital signature scheme on its own does not prevent a valid signed message from being recorded and then maliciously reused in a replay attack.
For example, the branch office may legitimately request that bank transfer be issued once in a signed message.
If the bank doesn't use a system of transaction IDs in their messages to detect which transfers have already happened, someone could illegitimately reuse the same signed message many times to drain an account.
Uniqueness and malleability of signatures.
A signature itself cannot be used to uniquely identify the message it signs—in some signature schemes, every message has a large number of possible valid signatures from the same signer, and it may be easy, even without knowledge of the private key, to transform one valid signature into another.
If signatures are misused as transaction IDs in an attempt by a bank-like system such as a Bitcoin exchange to detect replays, this can be exploited to replay transactions.
Authenticating a public key.
Prior knowledge of a public key can be used to verify authenticity of a signed message, but not the other way around—prior knowledge of a signed message cannot be used to verify authenticity of a public key.
In some signature schemes, given a signed message, it is easy to construct a public key under which the signed message will pass verification, even without knowledge of the private key that was used to make the signed message in the first place.