[Course home page] [Course lectures]
YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
CPSC 467b: Cryptography and Computer Security
Week 8 (rev. 2)

Professor M. J. Fischer March 1 & 3, 2005
 
Lecture Notes, Week 8

1  Digital Signatures

1.1  Definition

A digital signature is a string attached to a message that is used to guarantee the integrity and authenticity of the message. It is very much like the message authentication codes (MACs) discussed in lecture notes week 4. Recall that Alice can protect a message m (encrypted or not) by attaching a MAC ξ = Ck(m) to the message m. The pair (m, ξ) is an authenticated message. To produce a MAC requires possession of the secret key k. To verify the integrity and authenticity of m, Bob, who also must know k, checks a received pair (m′, ξ′) by verifying that ξ = Ck(m). Assuming Alice and Bob are the only parties who share k, then Bob knows that either he or Alice must have sent the message.
A digital signature can be viewed as a 2-key MAC, just as a public key cryptosystem is a 2-key version of a classical cryptosystem. The basic idea is the same. Let M be a message space and S a signature space. A signature scheme consists of a private signing key d, a public verification key e, a signature function Sd: M → S, and a verification predicate Ve ⊆ M×S.1 A signed message is a pair (m, s) ∈ M×S. A signed message is valid if Ve(m, s) holds, and we say that (m, s) is signed with e.
The basic property of a signature scheme is that the signing function always produces valid signatures, that is,
Ve(m, Sd(m))
(1)
always holds. Assuming d is Alice's private signing key, and only Alice knows d, then a valid message signed with Alice's key d identifies her with m (possibly erroneously, as we shall see).

1.2  RSA digital signature scheme

1.2.1  Commutative cryptosystems

RSA can be used for digital signatures as follows: Alice generates an RSA modulus n and key pair (e,d), where e is public and d private as usual. Let Sd(m) = Dd(m), and let Ve(m, s) hold iff m = Ee(s). To see that (1) holds, we must verify that m = Ee(Dd(m)) for all messages m. This is the reverse of the condition we required for RSA to be a valid cryptosystem, viz.  Dd(Ee(m)) for all m ∈ Zm. However, RSA satisfies both conditions since
Dd(Ee(m)) ≡ (me)d ≡ med ≡ (md)e ≡ Ee(Dd(m)) ≡ m mod n.
A cryptosystem with this property that Dd°Ee = Ee °Dd is said to be commutative, where "°" denotes functional composition. Indeed, any commutative public key cryptosystem can be used for digital signatures in exactly this same way.

1.2.2  Signatures from non-commutative cryptosystems

We digress slightly and ask what we could do in case Ee and Dd did not commute. One possibility would be to define Se(m) = Ee(m) and Ve(m, s) to hold iff m = Dd(s). Now indeed every validly-signed message (m, Se(m)) would verify since Ee(Dd(m)) = m is the basic property of a cryptosystem. To make use of this scheme, Alice would have to keep e private and make d public. Assuming Alice generated the key pair in the first place, there is nothing preventing her from doing this. However, the resulting system might not be secure, for even if it is hard for Eve to find d from e, it might not be hard to find e from d. For RSA, it is just as hard, but then that's because RSA is completely symmetric in e and d. Other cryptosystems do not necessarily enjoy this symmetry property, e.g., ElGamal (discussed in lecture notes week 6). In that scheme, we have the equation b = gy mod p. Finding y from b is the discrete log problem and is believed to be hard. But going the other way, finding b from y, is straightforward, so the roles of public and private key cannot be interchanged while preserving security.2

1.3  Security of digital signatures

For digital signatures to be of any use, they must be difficult to forge. Just as there are different notions of security of a cryptosystem, there are different notions of valid signatures being hard to forge. Below are some increasingly stringent notions of forgery-resistance:
RSA signatures are indeed vulnerable to the latter kind of attack. It is easy for an attacker to generate valid random signed messages (m′,s′). He merely chooses s′ at random and computes m′ = Ee(s′).
One often wants to sign random strings, so this is a real drawback for certain practical applications. For example, in the Diffie-Hellman key exchange protocol discussed in lecture notes week 6, Alice and Bob exchange random-looking numbers a=gx mod p and b=gy mod p. In order to discourage man-in-the-middle attacks, they may wish to sign these strings. (This assumes that they already have each other's public signature verification keys.) However, Mallory could feed bogus signed values a′ and b′ to Bob and Alice, respectively. The signatures would check, and both would think they had successfully established a shared key k when in fact they had not.
One way to get around the adversary's ability to generate valid random signed messages is to put redundancy into the message, for example, by prefixing a fixed string σ to the front of each message before signing it. Instead of taking Sd(m) = Dd(m), one could take Sd(m) = Dd(σm). The corresponding verification predicate Ve(m, s) would then check that σm = Ee(s).
The security of this scheme depends on the mixing properties of the encryption and decryption functions, that is, each output bit depends on all of the input bits. Not all cryptosystems have this property. For example, a block cipher used in ECB mode (see lecture notes week 2) encrypts a block at a time, so each block of output bits depends only on the corresponding block of input bits. With such a cipher, it could well happen that Sd(m) = Dd(σm) = Dd(σ)·Dd(m). This would allow Mallory to forge random messages assuming he knows just one valid signed message (m0, s0). Here's how. He knows that s0 = Dd(σ)·Dd(m), so from s0 he extracts the prefix s00 = Dd(σ). He now generates a valid signed message by choosing a ransom s′01 and computing m′ = Ee(s′01) and s′ = s00·s′01. The signed message (m′, s′) is valid since Ee(s′) = Ee(s00·s′01) = Ee(s00)·Ee(s′01) = σm′.
A better way to eliminate Mallory's ability to generate valid signed messages is to sign a message digest of the message rather than signing m itself. A message digest function h, also called a cryptographic hash function, maps long strings to short random-looking strings. To sign a message m, Alice computes Sd(m) = Dd(h(m)). To verify the signature s, Bob checks that h(m) = Ee(s). For Mallory to generate a forged signed message (m′, s′) he must somehow come up with m′ and s′ satisfying
h(m′) = Ee(s′)
That is, he must find m′ and s′ that both map to the same string, where m′ is mapped by h and s′ by Ee. Alice can invert Ee by computing Dd, which is what enables her to sign messages. But Mallory presumably cannot compute Dd. The defining property of a cryptographic hash function implies that he also can't "invert" h. h is not one-to-one, so it doesn't have an inverse in the usual sense. What we mean here is that, given y, Mallory cannot feasibly find any m′ such that h(m′) = y.
A second advantage of signing message digests rather than signing messages directly is that the resulting signed messages are shorter. If one uses RSA in the way described to sign m, the signature is same length as m, so the signed message is twice as long as m. But a message digest is a fixed length, for example, 160 bits, so the signed version of m is only 160 bits longer than m itself. For both reasons of security and efficiency, signed message digests are what is used in practice.
We'll talk more about message digests in section 3.

2  Implications of Digital Signatures

We like to think of a digital signature as a digital analog to a conventional signature. However, there is an important difference. A conventional signature binds a person to a document. Barring forgery, a valid signature indicates that a particular individual performed the action of signing the document. Similarly, a digital signature binds a signing key to a document. Barring forgery, a valid digital signature indicates that a particular signing key was used to sign the document. However, it does not directly bind an individual to the document the way a conventional signature does. Rather, the binding of an individual to a document is indirect. The signature binds the signing key to the document, but other considerations must be used to bind the individual to the signing key.
An individual can always disavow a signature on the grounds that the private signing key has become compromised. There are many ways that this can happen. Since signing keys must be quite long for security (768, 1024, or even 2048 bits are common), Alice can't be expected to memorize the key; it must be written down somewhere. Whereever it resides, there is the possibility of it being copied, or the physical device containing it being stolen. Even if she were able to memorize it, she would have to type it into her computer in order to use it, exposing it to keystroke monitors or other spyware that might have been surreptitiously installed on her computer. Indeed, she might deliberately publish her signing key for the express purpose of relinquishing responsibility for documents signed by her key. For all of these reasons, one cannot conclude "without a reasonable doubt" that a digitally signed document was indeed signed by the purported holder of the signing key.
This isn't to say that digital signatures aren't useful; only that they have significantly different properties than conventional signatures. In particular, they are subject to disavowal by the signer in a way that conventional signatures are not. Nevertheless, they are still very useful in situations where disavowal is not a problem.

3  Message Digest Functions

Recall that a message digest or cryptographic one-way hash function h maps M → H, where M is the message space and H the hash value space. A collision is a pair of messages m1 and m2 such that h(m1) = h(m2), and we say that m1 and m2 collide. We generally assume |M| >> |H|, in which case h is very far from being one-to-one, and there are many colliding pairs. Nevertheless, we want it to be hard for an adversary to find collisions. We consider three increasingly strong versions of this property:
One-way property:
Given y ∈ H, it is "hard" to "find" m ∈ M such that h(m) = y.
Weak collision-free property:
Given m ∈ M, it is "hard" to "find" m′ ∈ M such that m′ ≠ m and h(m′) = h(m).
Strong collision-free property:
It is "hard" to "find" colliding pairs (m, m′). (What does this mean in a complexity-theoretic sense?)
These definitions as I have stated them are rather vague, for they ignore issues of what we mean by "hard" and "find". Intuitively, "hard" means that Mallory cannot carry out the computation in a feasible amount of time on a realistic computer, but this just raises the question with what do we mean by "feasible time" and "realistic computer"? The term "find" has several reasonable interpretations. It may mean "always produces a correct answer", or "produces a correct answer with high probability", or "produces a correct answer on a significant number of possible inputs with non-negligible probability". The latter notion of "find" is rather weak; it just says that Mallory every now and then can break the system. For any given application, there is a maximum acceptable rate of error, and we must be sure that our cryptographic system meets that requirement.
Let me say a little more about what it means for h to be one-way. Intuitively, this means that no probabilistic polynomial time algorithm A(y) produces a pre-image m of y under h with more than negligable probability of success. However, this probability of success need not be negligable for all y. We only require that the expected probability of success be negligable when y itself is chosen according to a particular probability distribution. The distribution we have in mind is the one induced by h applied to uniformly distributed m ∈ M. That is, the probability of y is proportional to the number of values m ∈ M such that h(m) = y. This means that h can be considered one-way even though algorithms do exist that succeed on low-probability subsets of H.
The following example might help clarify these ideas. Let h(m) be a cryptographic hash function that produces hash values of length n. Define a new hash function H(m) as follows:
H(m) =



0·m
if |m| = n
1·h(m)
otherwise.
Thus, H produces hash values of length n+1. H(m) is clearly collision-free since the only possible collisions are for m's of lengths different from n. Any such colliding pair (m, m′) for H is also a colliding pair for h. Since h is collision-free, then so is H.
Not so obvious is that H is one-way, even though H can be inverted for 1/2 of all possible hash values y, namely, those which begin with 0. The reason this doesn't violate the definition of one-wayness is that only 2n values of m map to hash values that begin with 0, and all the rest map to values that begin with 1. Since we are assuming |M| >> |H|, the probability that a uniformly sampled m ∈ M has length exactly n is small.
With these caveats, there are some obvious relationships between these definitions that can be made precise once the definitions are made similarly precise.
If h is strong collision-free, then h is weak collision-free.
(Sketch)  Suppose h is not weak collision-free. We show that it is not strong collision-free by showing how to enumerate colliding message pairs. The method is straightforward: Pick a random message m ∈ M. Try to find a colliding message m′. If we succeed in finding such an m′, then output the colliding pair (m, m′). If not, try again with another randomly-chosen message. Since h is not weak collision-free, we will succeed on a significant number of the messages, so we will succeed in generating a succession of colliding pairs. How fast the pairs are enumerated depends on how often the algorithm for finding a colliding message succeeds and how fast it is.
These parameters in turn may depend on how large M is relative to H. It is always possible that h is one-to-one on some subset U of elements in M, so not every message even necessarily has a colliding partner. However, an easy counting argument shows that U has size at most |H|−1. Since we assume |M| >> |H|, the probability that a randomly-chosen message from M lies in U is correspondingly small.
In a similar vein, we argue that strong collision-free also implies one-way. If h is strong collision-free, then h is one-way.
(Sketch)  Suppose h is not one-way. Then there is an algorithm A(y) for finding m such that h(m) = y, and A(y) succeeds with significant probability when y is chosen randomly with probability proportional to the size of its preimage. Assume that A(y) returns ⊥ to indicate failure.
The following randomized algorithm enumerates a sequence of colliding pairs:
1. Choose random m.
2. Compute y = h(m).
3. Compute m′ = A(y).
4. If m′ ≠ ⊥ and m ≠ m′ then output (m, m′).
5. Start over at step 1.
Each iteration of this algorithm succeeds with significant probability ε that is the product of the probability that A(y) succeeds on y and the probability that m′ ≠ m. The latter probability is at least 1/2 except for those values m which lie in the set of U of messages on which h is one-to-one (defined in the proof of claim 1). Thus, assuming |M| >> |H|, the algorithm outputs each colliding pair in expected number of iterations that is at most only slightly larger than 1/ε.
These same ideas can be used to show that weak collision-free implies one-way, but now one has to be more careful with the precise definitions. If h is weak collision-free, then h is one-way.
(Sketch)  Suppose as before that h is not one-way, so there is an algorithm A(y) for finding m such that h(m) = y, and A(y) succeeds with significant probability when y is chosen randomly with probability proportional to the size of its preimage. Assume that A(y) returns ⊥ to indicate failure. We want to show this implies that the weak collision-free property does not hold, that is, there is an algorithm that, for a significant number of m ∈ M, succeeds with non-negligible probability in finding a colliding m′. We claim the following algorithm works:
Given input m:
1. Compute y = h(m).
2. Compute m′ = A(y).
3. If m′ ≠ ⊥ and m ≠ m′ then output (m, m′) and halt.
4. Otherwise, start over at step 1.
This algorithm fails to halt for m ∈ U, but we have argued above that the number of such m is small (= insignificant) when |M| >> |H|. It may also fail even when a colliding partner m′ exists if it happens that the value returned by A(y) is m. (Remember, A(y) is only required to return some preimage of y; we can't say which.) However, corresponding to each such bad case is another one in which the input to the algorithm is m′ instead of m. In this latter case, the algorithm succeeds, since y is the same in both cases. With this idea, we can show that the algorithm succeeds in finding a colliding partner on at least half of the messages in M−U.

4  Combining Signatures with Encryption

One often wants to encrypt messages for privacy and sign them for integrity and authenticity. Suppose Alice has a cryptosystem (E, D) and a signature system (S, V). Three possibilities come to mind for encrypting and signing a message m:
  1. Alice signs the encrypted message, that is, she sends (E(m), S(E(m))).
  2. Alice encrypts the signed message, that is, she sends E(m °S(m)). Here we assume a standard way of representing the ordered pair (m, S(m)) as a string, which we denote by m °S(m).
  3. Alice encrypts only the first component of the signed message, that is, she sends (E(m), S(m)).
Think about the pros and cons of each of these three possibilities.

5  ElGamal Signatures

The ElGamal signature scheme uses ideas similar to those of his encryption system, which we have already seen. The private signing key consists of a primitive root g of a prime p and an exponent x. The public verification key consists of g, p, and the number a = gx mod p. The signing and verification algorithms are given below:
To sign m:
1. Choose random y ∈ \Zstarφ(p). 
2. Compute b = gy mod p.
3. Compute c = (m − xb) y−1 mod φ(p).
4. Output signature s = (b,c).
To verify (m, s), where s = (b, c):
1. Check that ab bc ≡ gm mod p.
Why does this work? Plugging in for a and b, we see that
ab bc ≡ (gx)b (gy)c ≡ gxb+yc ≡ gm mod p
since xb + yc ≡ m mod φ(p).

6  Digital Signature Algorithm (DSA)

The commonly-used Digital Signature Algorithm (DSA) is a variant of ElGamal signatures. Also called the Digital Signature Standard (DSS), it is described in U.S. Federal Information Processing Standard (FIPS 186-2). (See http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-change1.pdf.) It uses two primes: p, which is 1024 bits long,3 and q, which is 160 bits long and satisfies q \divides (p−1). Here's how to find them: Choose q first, then search for z such that zq+1 is prime and of the right length. Choose p = zq+1 for such a z.
Now let g = h(p−1)/q mod p for any h ∈ \Zstarp for which g > 1. This ensures that g ∈ \Zstarp is a non-trivial q th root of unity modulo p. Let x ∈ \Zstarq and compute a = gx mod p. The parameters p, q, and g are common to the public and private keys. In addition, the private signing key contains x and the public verification key contains a.
Here's how signing and verification work:
To sign m:
1. Choose random y ∈ \Zstarq.
2. Compute b = (gy mod p) mod q.
3. Compute c = (m + xb) y−1 mod q.
4. Output signature s = (b, c).
To verify (m, s), where s = (b, c):
1. Verify that b,c ∈ \Zstarq; reject if not.
2. Compute u1 = mc−1 mod q.
3. Compute u2 = bc−1 mod q.
4. Compute v = (gu1 au2 mod p) mod q.
5. Check v = b.
To see why this works, note that since gq ≡ 1 mod p, then
r ≡ s mod q     implies    gr ≡ gs mod p.
This follows from the fact that g is a qth root of unity modulo p, so gr+uq ≡ gr (gq)u ≡ gr mod p for any u. Hence,
gu1 au2 ≡ gmc−1 + x b c−1 ≡ gy mod p.
It follows that
gu1 au2 mod p = gy mod p
and hence
v = (gu1 au2 mod p) mod q = (gy mod p) mod q = b,
as desired. (Notice the shift between equivalence modulo p and equality of remainders modulo p.)

Remarks

DSA introduces this new element of computing a number modulo p and then modulo q. Call this function fp,q(n) = (n mod p) mod q. This is not the same as n mod r for any number r, nor is it the same as (n mod q) mod p.
To understand better what's going on, let's look at an example. Take p=29 and q=7. Then 7|(29−1), so this is a valid DSA prime pair. The table below lists the first 29 values of y = f29,7(n):
n  0  1  2  3  4  5  6  7  8  9101112131415 16171819202122232425262728
y01234560123456012345601234560
The sequence of function values repeats after this point with a period of length 29. Note that it both begins and ends with 0, so there is a double 0 every 29 values. That behavior cannot occur modulo any number r. That behavior is also different from f7,29(n), which is equal to n mod 7 and has period 7. (Why?)

Footnotes:

1As with RSA, we denote the private component of the key pair by the letter d and the public component by the letter e, although they no longer have same same mnemonic significance.
2However, ElGamal found a different way to use the ideas of discrete logarithm to build a signature scheme, which we will discuss later.
3The original standard specified that the length L of p should be a multiple of 64 lying between 512 and 1024. However, Change Notice 1 of FIPS 186-2 requires L = 1024.

File translated from TEX by TTH, version 3.66.
On 2 Mar 2005, 22:12.