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.[1][2]
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,[3] but not all electronic signatures use digital signatures.[4]
[5]
Electronic signatures have legal significance in some countries, including Canada,[6] South Africa,
[7]
the United States, Algeria,[8] Turkey,[9] India,[10] Brazil, Indonesia, Mexico, Saudi Arabia,[11] Uruguay,
[12]
Switzerland, Chile[13] and the countries of the European Union.[14][15]
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.[16] 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.[17][18] 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[edit]
Main article: Public-key cryptography

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.[19]
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.[19][20]

History[edit]
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.[21][22] Soon afterwards, Ronald Rivest, Adi Shamir,
and Len Adleman invented the RSA algorithm, which could be used to produce primitive
digital signatures[23] (although only as a proof-of-concept – "plain" RSA signatures are not
secure[24]). The first widely marketed software package to offer digital signature was Lotus
Notes 1.0, released in 1989, which used the RSA algorithm.[25]
Other digital signature schemes were soon developed after RSA, the earliest being Lamport
signatures,[26] Merkle signatures (also known as "Merkle trees" or simply "Hash trees"),
[27]
and Rabin signatures.[28]
In 1988, Shafi Goldwasser, Silvio Micali, and Ronald Rivest became the first to rigorously
define the security requirements of digital signature schemes.[29] 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.[29] 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.[30]

Method[edit]
This Method section needs additional citations
for verification. Please help improve this article by adding
citations to reliable sources in this Method section. Unsourced
material may be challenged and removed.
Find sources: "Digital
signature" – news · newspapers · books · scholar · JSTOR (January
2022) (Learn how and when to remove this template message)

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.[31] 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.[32] 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.[22][clarification needed]
There are several reasons to sign such a hash (or message digest) 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
(such as, in the case of RSA, numbers modulo a composite number N). 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 (separated) 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[edit]
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.
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[edit]
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.[33]
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.[33][1][2]
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 an 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.[2]
Limitations[edit]
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.[33]
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.[34] 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.[35]
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.[36]

Non-repudiation[edit]
Non-repudiation,[14] or more specifically non-repudiation of origin, is an important
aspect of digital signatures. By this property, an entity that has signed some
information cannot at a later time deny having signed it. Similarly, access to the
public key only does not enable a fraudulent party to fake a valid signature.
Note that these authentication, non-repudiation etc. properties rely on the secret
key not having been revoked prior to its usage. Public revocation of a key-pair is
a required ability, else leaked secret keys would continue to implicate the
claimed owner of the key-pair. Checking revocation status requires an "online"
check; e.g., checking a certificate revocation list or via the Online Certificate
Status Protocol.[15] Very roughly this is analogous to a vendor who receives
credit-cards first checking online with the credit-card issuer to find if a given
card has been reported lost or stolen. Of course, with stolen key pairs, the theft
is often discovered only after the secret key's use, e.g., to sign a bogus
certificate for espionage purpose.

Notions of security[edit]
In their foundational paper, Goldwasser, Micali, and Rivest lay out a hierarchy of
attack models against digital signatures:[29]

1. In a key-only attack, the attacker is only given the public verification

key.
2. 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.
3. 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:[29]

1. A total break results in the recovery of the signing key.

2. A universal forgery attack results in the ability to forge signatures for
any message.
3. A selective forgery attack results in a signature on a message of the
adversary's choice.
4. An existential forgery merely results in some valid message/signature
pair not already known to the adversary.
The strongest notion of security, therefore, is security against existential forgery
under an adaptive chosen message attack.

Additional security precautions[edit]

Putting the private key on a smart card[edit]
All public key / private key cryptosystems depend entirely on keeping the private
key secret. A private key can be stored on a user's computer, and protected by
a local password, but 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[37]). In a typical digital
signature implementation, the hash calculated from the document is sent to the
smart card, whose CPU signs the hash using the stored private key of the user,
and then returns the signed hash. Typically, a user must activate their smart
card by entering a personal identification number or PIN code (thus
providing 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. This reduces the security of the scheme to that of the PIN system,
although it still requires an attacker to possess the card. A mitigating factor is
that private keys, if generated and stored on smart cards, are usually regarded
as difficult to copy, and are assumed to exist in exactly one copy. Thus, the loss
of the smart card may be detected by the owner and the corresponding
certificate can be immediately revoked. Private keys that are protected by
software only may be easier to copy, and such compromises are far more
difficult to detect.

Using smart card readers with a separate

keyboard[edit]
Entering a PIN code to activate the smart card 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. Readers with a numeric keypad are meant to circumvent
the eavesdropping threat where the computer might be running a keystroke
logger, potentially compromising the PIN code. Specialized card readers are
also less vulnerable to tampering with their software or hardware and are
often EAL3 certified.

Other smart card designs[edit]

Smart card design is an active field, and there are smart card schemes which
are intended to avoid these particular problems, despite having few security
proofs so far.

Using digital signatures only with trusted

applications[edit]
One of the main differences between a digital signature and a written signature
is that the user does not "see" what they sign. The user application presents a
hash code to be signed by the digital signing algorithm using the private key. An
attacker who gains control of the user's PC can possibly replace the user
application with a foreign substitute, in effect replacing the user's own
communications with those of the attacker. This could allow a malicious
application to trick a user into signing any document by displaying the user's
original on-screen, but presenting the attacker's own documents to the signing
application.
To protect against this scenario, an authentication system can be set up
between the user's application (word processor, email client, etc.) and the
signing application. The general idea is to provide some means for both the
user application and signing application to verify each other's integrity. For
example, the signing application may require all requests to come from digitally
signed binaries.

Using a network attached hardware security

module[edit]
One of the main differences between a cloud based digital signature service
and a locally provided one is risk. Many risk averse companies, including
governments, financial and medical institutions, and payment processors
require more secure standards, like FIPS 140-2 level 3 and FIPS
201 certification, to ensure the signature is validated and secure.

WYSIWYS[edit]
Main article: WYSIWYS

Technically speaking, a digital signature applies to a string of bits, whereas

humans and applications "believe" that they sign the semantic interpretation of
those bits. In order to be semantically interpreted, the bit string must be
transformed into a form that is meaningful for humans and applications, and this
is done through a combination of hardware and software based processes on a
computer system. The problem is that the semantic interpretation of bits can
change as a function of the processes used to transform the bits into semantic
content. It is relatively easy to change the interpretation of a digital document by
implementing changes on the computer system where the document is being
processed. From a semantic perspective this creates uncertainty about what
exactly has been signed. WYSIWYS (What You See Is What You Sign)
[38]
means that the semantic interpretation of a signed message cannot be
changed. In particular this also means that a message cannot contain hidden
information that the signer is unaware of, and that can be revealed after the
signature has been applied. WYSIWYS is a requirement for the validity of digital
signatures, but this requirement is difficult to guarantee because of the
increasing complexity of modern computer systems. The term WYSIWYS was
coined by Peter Landrock and Torben Pedersen to describe some of the
principles in delivering secure and legally binding digital signatures for Pan-
European projects.[38]

Digital signatures versus ink on paper signatures[edit]

An ink signature could be replicated from one document to another by copying
the image manually or digitally, but to have credible signature copies that can
resist some scrutiny is a significant manual or technical skill, and to produce ink
signature copies that resist professional scrutiny is very difficult.
Digital signatures cryptographically bind an electronic identity to an electronic
document and the digital signature cannot be copied to another document.
Paper contracts sometimes have the ink signature block on the last page, and
the previous pages may be replaced after a signature is applied. Digital
signatures can be applied to an entire document, such that the digital signature
on the last page will indicate tampering if any data on any of the pages have
been altered, but this can also be achieved by signing with ink and numbering
all pages of the contract.

Some digital signature algorithms[edit]

 RSA
 DSA
 ECDSA
 EdDSA
 RSA with SHA
 ECDSA with SHA[39]
 ElGamal signature scheme as the predecessor to DSA, and
variants Schnorr signature and Pointcheval–Stern signature algorithm
 Rabin signature algorithm
 Pairing-based schemes such as BLS
 NTRUSign is an example of a digital signature scheme based on hard
lattice problems
 Undeniable signatures
 Aggregate signatureru – a signature scheme that supports aggregation:
Given n signatures on n messages from n users, it is possible to aggregate
all these signatures into a single signature whose size is constant in the
number of users. This single signature will convince the verifier that the n
users did indeed sign the n original messages. A scheme by Mihir
Bellare and Gregory Neven may be used with Bitcoin.[40]
 Signatures with efficient protocols – are signature schemes that facilitate
efficient cryptographic protocols such as zero-knowledge proofs or secure
computation.