13.1 List two disputes that can arise in the context of message authentication.
Get 13.1 exercise solution
13.2 What are the properties a digital signature should have?
Get 13.2 exercise solution
13.3 What requirements should a digital signature scheme satisfy?
Get 13.3 exercise solution
13.4 What is the difference between direct and arbitrated digital signature?
Get 13.4 exercise solution
13.5 In what order should the signature function and the confidentiality function be applied to a message, and why?
Get 13.5 exercise solution
13.6 What are some threats associated with a direct digital signature scheme?
Get 13.6 exercise solution
Problems
13.1 Dr. Watson patiently waited until Sherlock Holmes finished. “Some interesting problem to solve, Holmes?” he asked when Holmes finally logged out. “Oh, not exactly. I merely checked my e-mail and then made a couple of network experiments instead of my usual chemical ones. I have only one client now and I have already solved his problem. If I remember correctly, you once mentioned cryptology among your other hobbies, so it may interest you.” “Well, I am only an amateur cryptologist, Holmes. But of course I am interested in the problem. What is it about?” “My client is Mr. Hosgrave, director of a small but progressive bank. The bank is fully computerized and of course uses network communications extensively. The bank already uses RSA to protect its data and to digitally sign documents that are communicated. Now the bank wants to introduce some changes in its procedures; in particular, it needs to digitally sign some documents by two signatories. 1. The first signatory prepares the document, forms its signature, and passes the document to the second signatory. 2. The second signatory as a first step must verify that the document was really signed by the first signatory. She then incorporates her signature into the document’s signature so that the recipient, as well as any member of the public, may verify that the document was indeed signed by both signatories. In addition, only the second signatory has to be able to verify the document’s signature after the first step; that is, the recipient (or any member of the public) should be able to verify only the complete document with signatures of both signatories, but not the document in its intermediate form where only one signatory has signed it. Moreover, the bank would like to make use of its existing modules that support RSA-style digital signatures.” “Hm, I understand how RSA can be used to digitally sign documents by one signatory, Holmes. I guess you have solved the problem of Mr. Hosgrave by appropriate generalization of RSA digital signatures.” “Exactly, Watson,” nodded Sherlock Holmes. “Originally, the RSA digital signature was formed by encrypting the document by the signatory’s private decryption key ‘d’, and the signature could be verified by anyone through its decryption using publicly known encryption key ‘e’. One can verify that the signature S was formed by the person who knows d, which is supposed to be the only signatory. Now the problem of Mr. Hosgrave can be solved in the same way by slight generalization of the process, that is …” Finish the explanation.
Get 13.1 exercise solution
13.2 DSA specifies that if the signature generation process results in a value of s = 0, a new value of k should be generated and the signature should be recalculated. Why?
Get 13.2 exercise solution
13.3 What happens if a k value used in creating a DSA signature is compromised?
Get 13.3 exercise solution
13.4 The DSA document includes a recommended algorithm for testing a number for primality. 1. [Choose w] Let w be a random odd integer. Then (w - 1) is even and can be expressed in the form 2am with m odd. That is, 2a is the largest power of 2 that divides (w - 1). 2. [Generate b] Let b be a random integer in the range 1 6 b 6 w. 3. [Exponentiate] Set j = 0 and z = bm mod w. 4. [Done?] If j = 0 and z = 1, or if z = w - 1, then w passes the test and may be prime; go to step 8. 5. [Terminate?] If j 7 0 and z = 1, then w is not prime; terminate algorithm for this w. 6. [Increase j] Set j = j + 1. If j 6 a, set z = z2mod w and go to step 4. 7. [Terminate] w is not prime; terminate algorithm for this w. 8. [Test again?] If enough random values of b have been tested, then accept w as prime and terminate algorithm; otherwise, go to step 2. a. Explain how the algorithm works. b. Show that it is equivalent to the Miller-Rabin test described in Chapter 8.
Get 13.4 exercise solution
13.5 With DSA, because the value of k is generated for each signature, even if the same message is signed twice on different occasions, the signatures will differ. This is not true of RSA signatures. What is the practical implication of this difference?
Get 13.5 exercise solution
13.6 Consider the problem of creating domain parameters for DSA. Suppose we have already found primes p and q such that q|(p - 1). Now we need to find g E Zp with g of order q mod p. Consider the following two algorithms:
a. Prove that the value returned by Algorithm 1 has order q. b. Prove that the value returned by Algorithm 2 has order q. c. Suppose p = 40193 and q = 157. How many loop iterations do you expect Algorithm 1 to make before it finds a generator? d. If p is 1024 bits and q is 160 bits, would you recommend using Algorithm 1 to find g? Explain. e. Suppose p = 40193 and q = 157. What is the probability that Algorithm 2 computes a generator in its very first loop iteration? (If it is helpful, you may use the fact that
when answering this question.)
Get 13.6 exercise solution
13.7 It is tempting to try to develop a variation on Diffie-Hellman that could be used as a digital signature. Here is one that is simpler than DSA and that does not require a secret random number in addition to the private key. Public elements: q prime number a a < q and a is a primitive root of q Private key: X X < q Public key: Y = aX mod q To sign a message M, compute h = H(M), which is the hash code of the message. We require that gcd(h, q - 1) = 1. If not, append the hash to the message and calculate a new hash. Continue this process until a hash code is produced that is relatively prime to (q - 1). Then calculate Z to satisfy Z * h K X(mod q - 1). The signature of the message is aZ. To verify the signature, a user verifies that Y = (aZ)h = aXmod q. a. Show that this scheme works. That is, show that the verification process produces an equality if the signature is valid. b. Show that the scheme is unacceptable by describing a simple technique for forging a user’s signature on an arbitrary message.
Get 13.7 exercise solution
13.8 An early proposal for a digital signature scheme using symmetric encryption is based on the following. To sign an n-bit message, the sender randomly generates in advance 2n 56-bit cryptographic keys: k1, K1, k2, K2,c,... kn, Kn which are kept private. The sender prepares in advance two sets of corresponding non-secret 64-bit validation parameters, which are made public: u1, U1, u2, U2,c, un, Un and v1, V1, v2, V2,c, vn, Vn where vi = E(ki, ui), Vi = E(ki, Ui) The message M is signed as follows. For the ith bit of the message, either ki or Ki is attached to the message, depending on whether the message bit is 0 or 1. For example, if the first three bits of the message are 011, then the first three keys of the signature are k1, K2, K3. a. How does the receiver validate the message? b. Is the technique secure? c. How many times can the same set of secret keys be safely used for different messages? d. What, if any, practical problems does this scheme present?
Get 13.8 exercise solution
