Introduction

Digital signatures serve the same role as traditional pen and ink signatures to provide authentication, confirmation and to associate identities with documents. The signature must be tied to the document mathematically so that it may not be removed and replaced by another or placed on some other document. Cryptographically secure digital signature schemes are formed of two parts, the signing protocol and the authentication process. These processes are designed such that the signature is made using private information but verifiable using only public information that does not compromise the security of the signatory. This requirement explains why digital signature schemes usually stem from public-key cryptosystems.

There is also the concept of a ‘blind signature’ where the signatory is able to sign a document without seeing its content thereby ensuring sender privacy. This is useful in electronic voting systems for endorsing that a vote was made legally without acquiring knowledge of how the vote was cast. Blind signatures are also used in applications of digital cash and cryptocurrencies.

A good digital signature will be impossible to forge, quick to compute and verify and widely applicable. We will consider several digital signature schemes as well as engage in discussion of generalized attacks such as birthday attacks. Note that attacks of this kind are not interested in decrypting messages (which under signature schemes are often already public) but are interested in forging or changing signatures.

ElGamal Signature Scheme

The ElGamal digital signature scheme stems from the ElGamal cryptosystem based upon the security of the one-way function of exponentiation in modular rings and the difficulty of solving the discrete logarithm problem. To read more about the discrete log problem, read the following tutorial: Discrete Logarithms, The ElGamal Cryptosystem and Diffie-Hellman Key Exchange.

Signing protocol

The signing protocol for an ElGamal signature is as follows. Suppose Alice wants to sign a message, m.

The initial setup is the same as that for ElGamal encryption.

1. Alice chooses a large prime p and a primitive root α.
2. She then chooses a secret integer z and calculates β ≡ α^z (mod p).
3. The values of p, α and β are made public and z is kept private.

In order to sign the message m Alice follows the steps below:

1. She selects a secret random integer k such that GCD(k, p – 1) = 1.
2. She then computes r ≡ α^k (mod p).
3. She then finally computes s ≡ k^-1(m – zr) (mod p – 1).
4. The signed message is the triplet (m, r, s).

The verification process can then be performed by Bob using public information only.

1. Bob computes v₁ ≡ β^rr^s (mod p) and v₂ ≡ α^m (mod p).
2. The signature is declared valid if and only if v₁ ≡ v₂ (mod p).

Correctness

The verification procedure works by the following argument. Assume that the signature is valid. As s ≡ k^-1(m – zr) (mod p – 1), we have sk ≡ (m – zr) (mod p – 1) and hence m ≡ sk + zr (mod p – 1). Therefore by Fermat’s little theorem, that a congruence mod p – 1 in the exponent yields a congruence mod p overall, we have:

Example

Suppose that the message to be signed is numerically encoded so that m = 15. Alice chooses the prime p = 71 with primitive root α = 7. Her secret integer is z = 16 therefore the calculation of β is as follows:

Alice then publishes (p, α, β) as (71, 7, 19).

After this initial setup, Alice’s signing protocol begins by choosing the random integer k = 31 such that it is coprime to p - 1 = 70. She then computes r as below.

She may then compute the message signature s.

The signature will therefore be the triplet (m, r, s) = (15, 11, 49). Bob is then able to check the validity of this signature by the following congruences.

Since v₁ ≡ v₂ (mod 71) the signature is declared valid.

Security

Let’s say we have an attacker Eve who would like to forge Alice’s signature and apply it on another message m*.

Eve cannot compute the signature element s since she does not know Alice’s secret integer z. If Eve tried to skip this step by choosing an s that satisfies:

This can be rearranged to give r^s ≡ β^-rα^m (mod p) which is an instance of the discrete log problem which suggests that Eve will not be able to find a suitable s and hence the signature is secure.

If Eve chooses s first then the equation to solve is akin to the discrete log problem but harder and hence this approach does not benefit Eve either. It is not known if there is a way to choose r and s simultaneously though it is considered highly unlikely. Thus the signature scheme is considered secure.

Using different keys for each signature

As in the ElGamal encryption protocol it is advised not to repeat use of a private key k. Suppose that the same k is used for two consecutive signatures for messages m­₁ and m₂ leading to the same value of r in each signature and signature elements s₁ and s­­₂ for m­­₁ and m₂ respectively. The fact that r is the same for both of the messages will alert Eve to the fact that k has been repeated. Eve knows the following:

Hence Eve can rearrange to compute the following:

There are x = GCD(s­₁ – s₂, p – 1) solutions to this congruence and they can be found by computing the inverses of (s­₁ – s₂) mod (p – 1) and multiplying through. Usually x is small and hence Eve can compute α^k for each candidate k value until the k that matches the calculation of r (i.e. the ‘correct’ key) is found. Eve now knows k and can solve the following for z.

Again there will be GCD(r, p – 1) possibilities found for z each of which can be tested until the z that satisfies α^z ≡ β (mod p) is found. Eve now has all of the private information and has therefore removed the security of the signature rendering it impotent as a means of authentication.

Final notes

The ElGamal signature scheme is known as a signature with appendix: the message is not readily recovered from the signature pair (r, s) and the message m must be included in the verification procedure. This is in contrast to a message recovery scheme wherein the message is easily recoverable from the signature.

The Digital Signature Algorithm (DSA)

In 1991 the National Institute of Standards and Technology proposed the Digital Signature Algorithm as a standardized general use secure signature scheme. Like the ElGamal scheme DSA is a digital signature scheme with an appendix meaning that the message cannot be easily recovered from the signature itself.

When using DSA it is usually a hash of the message that is signed. A hash is an encoding that reduces the size of a message to a fixed bit length by using a specific encoding. Let the hash of a message m be h(m) = x and let x be a 160-bit message.

Signing Protocol

Initial setup: Let us consider key generation for DSA.

1. Alice finds a 160-bit prime q and chooses a prime p such that p – 1 is divisible by q. This renders the discrete log problem hard for this choice of p.
2. Alice chooses a primitive root g (mod p) and calculates α ≡ g^{(p – 1)/q} (mod p). This means that α^q ≡ 1 (mod p), from Fermat’s little theorem.
3. Alice then chooses a secret z ∈ (1, q – 1) and calculates β ≡ α^z (mod p).
4. Alice publishes (p, q, α, β) and keeps z secret.

Signing Protocol: Once the initialization is complete Alice may sign a message hash (x) by the following process:

1. Alice selects a random secret integer k ∈ (1, q – 1).
2. Alice computes r ≡ (α^k (mod p)) (mod q).
3. Alice further computes s ≡ k^-1(x + zr) (mod q)
4. Alice publishes her signature for x, (r, s) which is sent alongside x and m.

Signature Verification: To verify the message, Bob performs the following steps:

1. Download the public information (p, q, α, β).
2. Compute u­₁ ≡ s^-1x (mod q) and u₂ ≡ s^-1r (mod q).
3. Compute v = (α^u1β^u2 (mod p)) (mod q).
4. The signature is then only accepted if v = r.

Example

Alice chooses p = 131, q = 13 such that p and q are prime and p - 1 is divisible by q. The primitive root g = 2 (mod 13) is also chosen. Alice may then calculate the following.

Alice then chooses her secret z = 6 and uses it to compute β.

Alice then publishes (p, q, α, β) = (131, 13, 107, 45) and may begin the signing protocol by selecting another random integer k = 4 and computing r.

Alice then computes s for the message hash x = 27.

The message m and its hash h(m) = x is then published with the signature (r, s) = (6, 6).

Bob may then verify the validity of the signature by calculating the following.

Now Bob may compute v.

Since v = r the signature is accepted.

Correctness

Let us now show why this verification works. From the definition of s we may attain the following:

Which implies that:

Therefore,

Hence:

and thus v = r.

Advantages over ElGamal Signature Scheme

The private knowledge required to sign a document is solely represented by the integer z and hence this must be kept secret as in the ElGamal signature scheme. Similarly the repeated use of a key k will lead to the signature scheme no longer being secure and hence becoming impotent. The solution for finding z here from repeated signatures using k is analogous to the ElGamal case and hence will not be repeated.

Where this builds upon the ElGamal scheme is that the value of r only carries partial information about the value k. Knowing r allows us to find only the mod q value of k and there are many values in the congruent set mod p that reduce to this value mod q.

Again the value of designing the protocol such that α^q ≡ 1 (mod p) is that it limits any possible information leakages to the ring modulo q so the only information revealed in the protocol is mod q but the valuable information is modulo p which cannot easily be determined from values mod q (as q << p).

Computation of the DSA is also faster than computation of ElGamal signatures due to the verification step only requiring two exponentiations rather than three. The calculations of these modular exponentiations are the slowest parts of the process and hence removing one can vastly speed up verification calculation.

Hash Functions & Digital Signatures

Hash functions are functions that map messages of any arbitrary size to a hash of fixed size. The message that needs to be signed may be extremely long and hence the signature will often be at least as long which slows computation and requires greater data transfer. Hence the hash of a message is often what is signed so that the shared signature and message are shorter and more efficient to compute.

The choice of hash function is very important. It should be cryptographically secure and fast to implement. Cryptographically secure generally means that it should be a one-way function so that one cannot work out a message given the hash of the message. It should also be strongly collision-free meaning that it is unlikely that an attacker, Eve, will be able to find two distinct messages m­_1­ and m₂ such that h(m₁) = h(m₂) where h is a collision-free hash function. Even where this is possible it is very unlikely that both m_­1­ and m­₂ are meaningful messages. One way of trying to find an exploit a collision is through a birthday attack.

In the case that two messages (m­₁ and m₂) with the same hash can be created one could hash a message m₁ and send it for signing and then take the resulting signature and hash and use them as a signature of the other message m₂. This clearly highlights the need for secure hashes when applied to digital signatures.

This cryptographic security requires that the output of the hash function not be too small so as to overly limit the set of possible hashes. This will prevent the hash function from being collision free and open up the possibility of birthday attacks.

Birthday Attacks

Birthday attacks derive their name from the following question from probability theory: how many people need to be in a group before the probability that two of them share a birthday exceeds 50%? The answer is 23 which is surprisingly small when one considers that they are randomly chosen from an (assumed) uniform distribution over 365 days. The potential for a match is higher than many anticipate. Let us now consider an application of this probability theory to the security of digital signatures.

Suppose that you have signed the 50-bit hash of a message. There are 2⁵⁰ possible hashes so you would think that the chances of a possible alternative message sharing this hash, and thereby enabling the signature to be copied across, would be small.

Let us consider an attacker who has found 30 possible places in the message where small changes can be made to words or punctuation or spacing. This then leads to 2³⁰ possible and inconsequential message changes. The attacker has also done the same for a fraudulent message which is in their favor. The attacker can now make the list of the 2³⁰ legitimate documents and their hashes and the 2³⁰ fraudulent documents and their hashes.

The mathematics of finding matches can be summarized as follows. Suppose we have N objects (where N is large), there are r people each of whom pick an object (with replacement so that the same object may be picked twice). Then:

This approximation only holds for a large N.

Applying the above formula with r = 2³⁰ and N = 2⁵⁰ enables us to see that there is near certainty that there will be a match between a fraudulent and legitimate message hash.

Given that there is almost definitely a match between the hashes some version of the legitimate message and some version of the fraudulent message the attacker may pick out the two messages with matching hashes and send the legitimate one for signing but then apply that signature to the fraudulent message in a successful implementation of a birthday attack.

A general rule of thumb is to use a secure hash function which generates hashes that are twice as long as you consider sufficient for security in order to avoid such an attack. One should also be wary of many minor changes to a document to be signed without explanation of the changes. You should yourself make a slight change to a document before digitally signing in order to foil such attacks.

Summary

We have seen that digital signatures are important for authentication, verification of identity and trust in the digital era. However, this trust is conditional on the correct implementation of the signature schemes to avoid issues such as collision which opens the door to birthday attacks and impersonation. Digital signatures are used in software authentication, online security and verification of legal documentation.

These digital signature schemes are built upon the elements that form public key cryptosystems. The private information is used to create a signature that can be verified using solely the public information of the cryptosystem enabling signatures to be made without compromising the security of the signatory.