13.1 List two disputes that can arise in the context of message authentication. Get solution
13.2 What are the properties a digital signature should have? Get solution
13.3 What requirements should a digital signature scheme satisfy? Get solution
13.4 What is the difference between direct and arbitrated digital signature? Get solution
13.5 In what order should the signature function and the confidentiality function be applied to a message, and why? Get solution
13.6 What are some threats associated with a direct digital signature scheme? Get solution
13.7 Give examples of replay attacks. Get solution
13.8 List three general approaches to dealing with replay attacks. Get solution
13.9 What is a suppress-replay attack? Get solution
Problems
13.1 Modify the digital signature techniques of Table 13.1a and b to enable the receiver to verify the signature. Get solution
13.2 Modify the digital signature technique of Table 13.1c to avoid triple encryption of the entire message. Get solution
13.3 In discussing Table 13.1c, it was stated that alliances to defraud were impossible. In fact, there is one possibility. Describe it and explain why it would have so little credibility that we can safely ignore it. Get solution
13.4 In Section 13.2, we outlined the public-key scheme proposed in [WOO92a] for the distribution of secret keys.
The revised version includes IDA in steps 5 and 6. What attack, specifically, is countered by this revision? Get solution
13.5 The protocol referred to in Problem 13.1 can be reduced from seven steps to five, having the following sequence:
(1) A --> B:
(2) B -->KDC:
(3) KDC -->B:
(4) B--> A:
(5) A--> B:
Show the message transmitted at each step. Hint: The final message in this protocol is the same as the final message in the original protocol. Get solution
13.6 With reference to the suppress-replay attack described in Section 13.2:
a. Give an example of an attack when a party's clock is ahead of that of the KDC.
b. Give an example of an attack when a party's clock is ahead of that of another party. Get solution
13.7 There are three typical ways to use nonces as challenges. Suppose Na is a nonce generated by A, A and B
share key K, and f() is a function such as increment. The three usages are
13.8 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 so that
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 step (1); 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 solution
13.9 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 solution
13.10 What happens if a k value used in creating a DSA signature is compromised? Get solution
13.11 The DSS document includes a recommended algorithm for testing a number for primality, as follows:
1. [Choose w] Let w be a random odd integer. Then (w 1) is even and can be expressed in the form
2a m 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 <b < w.
3. [Exponentiate] Set j = 0 and z = bm mod w.
4. [Done?] If j = 0 and z = 1, or if z = w 1, thenw passes the test and may be prime; go to step 8.
5. [Terminate?] If j > 0 and z = 1, then w is not prime; terminate algorithm for thisw .
[Increase j] Set j = j + 1. If j < a, set z = z2
6. mod w and go to step 4.
7. [Terminate]w is not prime; terminate algorithm for thisw .
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 inC hapter 8. Get solution
13.12 With DSS, 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 solution
13.13 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 findg Zp with g of order q mod p. Consider the following two algorithms:
a. Prove that the value returned by Algorithm 1 has orderq .
b. Prove that the value returned by Algorithm 1 has orderq .
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 findg ? 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
13.14 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 = a
X mod q
To sign a message M, compute h = H(M), 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 calculateZ to satisfy Z x h X(mod q 1). The signature of the message is a Z. To verify the signature, a user verifies thaYt = (aZ)h= aX mod 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 solution
13.15 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,..., kn, Kn which are kept secret. The sender prepares in advance two sets of corresponding nonsecret 64-bit validation parameters, which are made public:
u1, V1, u2, V2,..., un, Vn and v1, V1, v2, V2,..., vn, Vn
where
vi = E(ki, ui), Vi = E(ki, Ui)
The message M is signed as follows. For the i th 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 solution
