
# 4.5: Digital Signatures


$$\newcommand{\NN}{\mathbb N}$$
$$\newcommand{\RR}{\mathbb R}$$
$$\newcommand{\QQ}{\mathbb Q}$$
$$\newcommand{\ZZ}{\mathbb Z}$$
$$\newcommand{\Cc}{\mathcal C}$$
$$\newcommand{\Dd}{\mathcal D}$$
$$\newcommand{\Ee}{\mathcal E}$$
$$\newcommand{\Ff}{\mathcal F}$$
$$\newcommand{\Kk}{\mathcal K}$$
$$\newcommand{\Mm}{\mathcal M}$$
$$\newcommand{\Pp}{\mathcal P}$$
$$\newcommand{\ind}{\operatorname{ind}}$$
$$\newcommand{\ord}{\operatorname{ord}}$$

Public-key cryptosystems allow several use-cases which symmetric cryptosystems do not. One which has come to have more and more importance in the modern digital economy is the creation of digital signatures – these are parts of electronic documents which are supposed to have something of the qualities of a physical signature in that are hard for an imposter to forge. Such a signed document might be needed, for example, if Bob from the last section (whose RSA public key is on his website) wished to send a legally binding contract via e-mail. Perhaps Alice and Bob wish to e-mail to their future landlord Larry a signed lease for an apartment that they will share. When Larry gets an e-mail from Bob saying “I agree to be bound by the terms of this lease,” Larry needs to have confidence that this e-mail did originate from Bob, which he can if there is a digital signature.

Here’s what Bob can do: he takes a copy of the lease, adds a section at the end stating his agreement to its terms and giving some personally identifying information (perhaps a scan of his driver’s license). Call this whole chunk of data $$m$$. Then Bob applies his decryption algorithm, using his private (decryption) key $$k_d$$, yielding $$s=d_{k_d}(m)$$ – this $$s$$ is called Bob’s signature on the message $$m$$. He then e-mails both $$m$$ and $$s$$ to Larry.

When Larry receives this signed message, the first thing he does is detach the signature $$s$$ and compute its encryption $$e_{k_e}(s)$$ using the public key he got off Bob’s website. Since $$e_{k_e}$$ and $$d_{k_d}$$ are inverses and it does not matter in which order they are applied, the result should be $$m$$. If that is so, Larry can be sure that whoever sent the message also had access to Bob’s secret key and so presumably is Bob himself.

Graphically:

 Larry on public network Bob pick $$k_d\in\Kk_d$$ compute $$k_e=\Ee(k_d)$$ download $$k_e$$ $$\leftarrowtail\; \; \;$$ public key $$k_e\; \; \; \leftarrowtail$$ publish $$k_e$$ message $$m\in\Mm$$ compute $$s=d_{k_d}(m)$$ receive $$(m,s)$$ $$\leftarrowtail\; \; \;$$ signed message $$(m,s)\; \;\; \leftarrowtail$$ transmit $$(m,s)$$ if $$e_{k_e}(s)=m$$ accept otherwise, reject

One problem with this scheme is that it has effectively doubled the size of the message. The way to make a smaller, more efficient signature is for it to consist of the decryption not of all of $$m$$ but instead of some function $$h(m)$$. Here the function $$h$$ should take a message of arbitrary size and produce a small, digested piece of data ... which nevertheless depends upon every part of the input $$m$$. After, all, if $$h(m)$$ depended only upon the first $$100$$ bits of $$m$$, for example, then a malicious Eve could alter the message in transit, and her change would go undetected as long as she did not change the first $$100$$ bits of the message.

Cryptologists have a name for functions like this $$h$$.

Definition: Cryptographic Hash Function

A function $$h$$ which takes as input arbitrary length strings of bits and produces output bit strings of a fixed length is called a cryptographic hash function if it satisfies

ease of computation

it is feasible to compute the $$h(m)$$ for any $$m$$;

pre-image resistance

given a hash value $$t$$, it is infeasible to find an $$m$$ such that $$h(m)=t$$;

second pre-image resistance

given a specific input $$m_1$$, it is infeasible to find another $$m_2$$ such that $$h(m_2)=h(m_1)$$;

collision resistance

it is infeasible to find two messages $$m_1$$ and $$m_2$$ such that $$h(m_2)=h(m_1)$$.

The words feasible and infeasible here have the same meaning here as in the previous section that it is, or is not, possible to complete the computation in an amount of time bounded by a polynomial function of the size of the inputs.

Notice that since a hash function takes inputs of arbitrary length but has a fixed output size, there will necessarily be an infinite number of collisions

The creation of cryptographic hash functions is something of a black art. It turns out that if one builds a candidate hash function with some clear structure (usually mathematical) – particularly if it is one that is fast to compute – a way to break one of the resistance requirements is usually found by the cryptological community. For this reason, the algorithms currently in wide use tend to be very ad hoc computations that just seem messy and have resisted attempts at inversion or breaking resistance.

Example $$\PageIndex{1}$$

For around a decade starting in the early $$1990$$s, the most widely used cryptographic hash function was called md5. This algorithm was developed by Ron Rivest and published in $$1992$$. The output size of md5 is $$128$$ bits.

While md5 was thought to be flawed since the middle 1990s, a real attack was not published until 2004, when it was shown not to be collision resistant [WY05]. However, md5 is still used extensively today to verify that a large data transfer has not suffered a transmission error – i.e., it is still a useful tool to test for non-malicious data corruption. (In this context of providing evidence for data integrity against non-malicious corruption, a hash function is frequently called a fingerprint.)

Example $$\PageIndex{2}$$

The most widely used cryptographic hash function from the late $$1990$$s until recently, and one which is built into many widely accepted and standardized cryptographic protocols, is SHA-1, with an output size of $$160$$ bits.

SHA-1 was developed by US National Security Agency (NSA) in a semi-public process, and was adopted by the US National Institute of Standards and Technology (NIST) as part of several US Federal Information Processing Standards.

In $$2004$$, some work was published which indicated that SHA-1 might be vulnerable to certain kinds of attack. (See [PS04].) For this reason, NIST required in $$2010$$ many US federal data protection applications to move to another hash function.

Example $$\PageIndex{3}$$

At the time of this writing, most security conscious users and organizations recommend SHA-2, usually in its “SHA-256” variant, which has an output size of $$256$$ bits. Given recent revelations of the NSA’s involvement – and weakening of – cryptographic protocols, it might be a cause of concern that NSA participated in the development of SHA-2.

Graphically:

 Charlie on public network Bob do RSA set-up, make $$k_e=(n,e)$$ and $$d$$ download $$k_e$$ $$\leftarrowtail\; \; \;$$ verification key $$k_e\; \; \; \leftarrowtail$$ publish $$k_e$$ message $$m\in\Mm$$ compute $$s=(h(m))^d$$ receive $$(m,s)$$ $$\leftarrowtail\; \; \;$$ signed message $$(m,s)\; \; \; \leftarrowtail$$ transmit $$(m,s)$$ if $$h(m)=s^e\pmod*{n}$$ accept otherwise, reject

With this understood, we can describe digital signatures more formally.

Definition: RSA Digital Signature

Suppose Bob sets up the RSA cryptosystem, as in the definition of RSA Cryptosystem and chooses once and for all a cryptographic hash function $$h$$ which he publishes on his web page along with his public encryption key $$k_e$$.

If Bob now wants to sign a message $$m$$, he appends to $$m$$ the RSA digital signature $$s=d_{d_k}(h(m))$$ before transmitting it to any third party, say Charlie.

When Charlie receives a signed message $$(m,s)$$ which claims to be from Bob, he goes to Bob’s website and downloads the public key $$k_e$$ and description of the cryptographic hash function $$h$$. At this point, Charlie computes $$e_{k_e}(s)$$ and compares it to $$h(m)$$. If they are equal, he accepts the signature; if not, he rejects.

In this context, Bob’s private/decryption key $$k_d$$ is called the signing key and his public/encryption key $$k_e$$ is called the verification key.

Exercise $$\PageIndex{1}$$

1. Use the Pigeonhole Principle (Theorem 1.1.1) to prove that there will always be an infinite number of collisions for a cryptographic hash function [although they may not be feasibly computable].
2. Give an example of a hash function $$h$$ whose output size is one bit and a specific input $$m_1$$ for which there is no second pre-image; that is, $$\nexists m_2$$ such that $$h(m_2)=h(m_1)$$.