| Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
Exercises
- 6.1 Suppose Bob is using the ElGamal Signature Scheme, and he signs two messages x1 and x2 with signatures (γ, δ1) and (γ, δ2), respectively. (The same value for γ occurs in both signatures.) Suppose also that gcd(δ1 - δ2, p - 1) = 1.
- (a) Describe how k can be computed efficiently given this information.
- (b) Describe how the signature scheme can then be broken.
- (c) Suppose p = 31847, α = 5 and β = 25703. Perform the computation of k and a, given the signature (23972, 31396) for the message x = 8990 and the signature (23972, 20481) for the message x = 31415.
- 6.2 Suppose I implement the ElGamal Signature Scheme with p = 31847, α = 5 and β = 26379. Write a computer program which does the following.
- (a) Verify the signature (20679, 11082) on the message x = 20543.
- (b) Determine my secret exponent, a, using the Shanks time-memory tradeoff. Then determine the random value k used in signing the message x.
- 6.3 Suppose Bob is using the ElGamal Signature Scheme as implemented in Example 6.1: p = 467, α = 2 and β = 132. Suppose Bob has signed the message x = 100 with the signature (29, 51). Compute the forged signature that Oscar can then form by using h = 102, i = 45 and j = 293. Check that the resulting signature satisfies the verification condition.
- 6.4 Prove that the second method of forgery on the ElGamal Signature Scheme, described in Section 6.2, also yields a signature that satisfies the verification condition.
- 6.5 Here is a variation of the ElGamal Signature Scheme. The key is constructed in a similar manner as before: Bob chooses to be a primitive element, a is a secret exponent (0 ≤ a ≤ p - 2) such that gcd (a, p - 1) = 1, and β = αa mod p. The key K = (α, a, β), where α and β are public and a is secret. Let be a message to be signed. Bob computes the signature sig(x) = (γ, δ), where
and
The only difference from the original ElGamal Scheme is in the computation of δ. Answer the following questions concerning this modified scheme.
- (a) Describe how a signature (γ, δ) on a message x would be verified using Bobs public key.
- (b) Describe a computational advantage of the modified scheme over the original scheme.
- (c) Briefly compare the security of the original and modified scheme.
- 6.6 Suppose Bob uses the DSS with q = 101, p = 7879, α = 170, a = 75 and β = 4567, as in Example 6.3. Determine Bobs signature on the message x = 52 using the random value k = 49, and show how the resulting signature is verified.
- 6.7 In the Lamport Scheme, suppose that two k-tuples, x and x′, are signed by Bob. Let denote the number of coordinates in which x and x′ differ. Show at Oscar can now sign new messages.
- 6.8 In the Bos-Chaum Scheme with k = 6 and n = 4, suppose that the messages x = (0, 1, 0, 0, 1, 1) and x′ = (1, 1, 0, 1, 1, 1) are signed. Determine the new messages that be signed by Oscar, knowing the signatures on x and x′.
- 6.9 In the Bos-Chaum Scheme, suppose that two k-tuples x and x′ are signed by Bob. Let Show that Oscar can now sign new messages.
- 6.10 Suppose Bob is using the Chaum-van Antwerpen Undeniable Signature Scheme as in Example 6.5. That is, p = 467, α = 4, a = 101 and β = 449. Suppose Bob is presented with a signature y = 25 on the message x = 157 and he wishes to prove it is a forgery. Suppose Alices random numbers are e1 = 46, e2 = 123, f1 = 198 and f2 = 11 in the disavowal protocol. Compute Alices challenges, c and d, and Bobs responses, C and D, and show that Alices consistency check will succeed.
- 6.11 Prove that each equivalence class of keys in the Pedersen-van Heyst Fail-stop Signature Scheme contains q2 keys.
- 6.12 Suppose Bob is using the Pedersen-van Heyst Fail-stop Signature Scheme, where p = 3467, α = 4, a0 = 1567 and β = 514 (of course, the value of a0 is not known to Bob).
- (a) Using the fact that a0 = 1567, determine all possible keys
such that sigK(42) = (1118, 1449).
- (b) Suppose that sigK(42) = (1118, 1449) and sigK(969) = (899, 471). Without using the fact that a0 = 1567, determine the value of K (this shows that the scheme is a one-time scheme).
- 6.13 Suppose Bob is using the Pedersen-van Heyst Fail-Stop Signature Scheme with p = 5087, α = 25 and β = 1866. Suppose the key is
Now, suppose Bob finds the signature (2219, 458) has been forged on the message 4785.
- (a) Prove that this forgery satisfies the verification condition, so it is a valid signature.
- (b) Show how Bob will compute the proof of forgery, a0, given this forged signature.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC