13.3: Digital Signatures

MACs are a cryptographic primitive that provide authenticity. A valid MAC tag on \(m\) is "proof" that someone who knows the key has vouched for \(m\). MACs are a symmetric-key primitive, in the sense that generating a MAC tag and verifying a MAC tag both require the same key (in fact, a tag is verified by re-computing it).

Digital signatures are similar to MACs, but with separate keys for signing and verification. A digital signature scheme consists of the following algorithms:

• KeyGen: outputs a pair of keys \((s k, v k)\), where \(s k\) is the signing key and \(v k\) is the verification key.
• Sign: takes the signing key \(s k\) and a message \(m\) as input, and outputs a signature \(\sigma\).
• Ver: takes the verification key \(v k\), message \(m\), and a potential signature \(\sigma\) as input; outputs a boolean.

If indeed \(\sigma\) is an output of \(\operatorname{Sign}(s k, m)\), then \(\operatorname{Ver}(v k, m, \sigma)\) should output true. Intuitively, it should be hard for an attacker to find any other \((m, \sigma)\) pairs that cause Ver to output true.

The idea behind digital signatures is to make \(v k\) public. In other words, anyone (even the attacker) should be able to verify signatures. But only the holder of \(s k\) (the person who generated \(v k\) and \(s k\) ) should be able to generate valid signatures. Furthermore, this guarantee should hold even against an attacker who sees many examples of valid signatures. The attacker should not be able to generate new valid signatures.

We formalize this security property in a similar way that we formalized the security of MACs: "only the secret-key holder can generate valid tags, even after seeing chosen examples of valid tags."

Definition 13.6

Let \(\Sigma\) be a signature scheme. We say that \(\Sigma\) is a secure signature if \(\mathcal{L}_{\text {sig-real }}^{\Sigma} \approx \mathcal{L}_{\text {sig-fake' }}^{\Sigma}\) where:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

Similar to the security definition for MACs, the libraries differ only in how they verify signatures provided by the attacker (VERSIG). If the attacker can generate a message-signature pair \((m, \sigma)\) that (1) verifies correctly, but (2) was not generated previously by the library itself, then versig from the \(\mathcal{L}_{\text {sig-real }}\) library will return true, while the \(\mathcal{L}_{\text {sig-fake }}\) library would return false. By asking for the libraries to be indistinguishable, we are really asking that the attacker cannot find any such message-signature pair (forgery).

The main difference to the MAC definition is that, unlike for the MAC setting, we intend to make a verification key public. The library can run \((v k, s k) \leftarrow\) KeyGen, but these values remain private by default. To make \(v k\) public, we explicitly provide an accessor GETVK to the attacker.

"Textbook" RSA Signatures

Signatures have an asymmetry: everyone should be able to verify a signature, but only the holder of the signing key should be able to generate a valid signature. The RSA function has a similar asymmetry: if \(N\) and \(e\) are public, then anyone can raise things to the \(e\) power, but only someone with \(d\) can raise things to the \(d\) power.

This similarity suggests that we can use RSA for signatures in the following way:

• The verification key is \((N, e)\) and the signing key is \((N, d)\), where these values have the appropriate \(\mathrm{RSA}\) relationship.
• A signature of message \(m\) (here \(m\) is an element of \(\mathbb{Z}_{N}\) ) is the value \(\sigma=m^{d} \% N\). Intuitively, only someone with the signing key can generate this value for a given \(m\).
• To verify a signature \(\sigma\) on a message \(m\), our goal is to check whether \(\sigma \equiv_{N} m^{d}\). However, we are given only \(N\) and \(e\), not \(d\). Consider raising both sides of this equation to the \(e\) power:\[\sigma^{e} \equiv_{N}\left(m^{d}\right)^{e} \equiv_{N} m\] The second equality is from the standard RSA property. Now this check can be done given only the public information \(N\) and \(e\).

A formal description of this scheme is given below:

Construction \(13.7\)

The key generation algorithm is not listed here, but \(N\), e, \(d\) are generated in the usual way for (Textbook RSA) RSA. The signing key is \(s k=(N, d)\) and the verification key is \(v k=(N, e)\).

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

Unfortunately, textbook RSA signatures are useful only as a first intuition. They are not secure! A simple attack is the following:

Suppose an attacker knows the verification key \((N, e)\) and sees a valid signature \(\sigma \equiv_{N}\) \(m^{d}\) for some message \(m\). Then \(\sigma^{2}\) is also a valid signature for the message \(m^{2}\), since: \[\sigma^{2} \equiv_{n}\left(m^{d}\right)^{2}=\left(m^{2}\right)^{d}\] The attacker can easily generate a forged signature on a new message \(m^{2}\), making the scheme insecure.

Hashed RSA Signatures

The problem with textbook RSA signatures is that the signatures and plaintexts had a very strong algebraic relationship. Squaring the signature had the effect of squaring the underlying message. One way to fix the problem is to "break" this algebraic relationship. Hashed RSA signatures break the algebraic structure by applying the RSA function not to \(m\) directly, but to \(H(m)\), where \(H\) is a suitable hash function (with outputs interpreted as elements of \(\left.\mathbb{Z}_{N}\right)\)

Construction \(13.8\) (Textbook RSA)

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

Let’s see how this change thwarts the attack on textbook signatures. If \(\sigma\) is a valid signature of \(m\), we have \(\sigma \equiv_{N} H(m)^{d}\). Squaring both sides leads to \(\sigma^{2} \equiv_{N}\left(H(m)^{2}\right)^{d}\). Is this the valid signature of any \(m^{\prime}\) ? An attacker would have to identify some \(m^{\prime}\) that has \(H\left(m^{\prime}\right)=H(m)^{2}\). If the hash function is a good one, then this should be hard.

Of course, this is not a formal proof. It is possible to formally prove the security of hashed RSA signatures. The precise statement of security is: "if RSA is a secure trapdoor function and \(H\) is modeled as a random oracle, then hashed RSA signatures are a secure signature scheme" Since we have not given formal definitions for either trapdoor functions or random oracles, we won’t see the proof in this book.

to-do

Write a chapter on random oracle and other idealized models.