EE418-Assignment 5 Solved

1.    [Com](Digital Signatures, 20 pts): Here we consider a variation of the ElGamal Signature Scheme. The key is constructed in a similar manner as in the original ElGamal Signature Scheme: “A” chooses α ∈ Z∗p to be a primitive element, 0 ≤ a ≤ p − 2 where gcd(a,p − 1) = 1, andβ = αa mod p. The key K = (α,a,β), where α and β are the public key and a is the private key. Let x ∈ Zp be a message to be signed. “A” computes the signature sig(x) = (γ,δ), where

γ = αk mod p

and

δ = (x − kγ)a−1 mod (p − 1)

The only difference from the original ElGamal Signature Scheme is in the computation of δ. Answer the following questions concerning this modified scheme.

(a)    Provide a verification equation for the modified scheme and show how a signature (γ,δ) on a message x would be verified using “A”’s public key and your suggested verification equation.

(b)   Describe a computational advantage of the modified scheme over the original scheme.

(c)    Briefly compare the security of the original and modified scheme.

2.    [Com](Digital Signatures, 10 pts × 3 = 30 pts):

(a)    Suppose “A” uses the DSA with q = 101,p = 7879,α = 170,a = 75,andβ = 4567. Determine “A” ’s signature on a message x such that SHA-1(x) = 52, using the random value k = 49, and show how the resulting signature is verified.

(b)    In Quiz 14, Question 3, we showed that using the same value k to sign two messages in the ElGamal Signature Scheme allows the scheme to be broken (i.e., an adversary can determine the secret key without solving an instance of the Discrete Logarithm problem). Show how similar attacks can be carried out for the Schnorr Signature Scheme and the DSA when the same value k is used to sign two messages.

(c)    Here, we describe a potential attack against the DSA. Suppose that the message x is given, let z = (SHA-1(x))−1 mod q, and let . Now suppose it is possible to find  such that

 

and

δ = λ(SHA-1(x)) mod q

Show that (γ,δ) is a valid signature for x.

3.    [Com](Digital Signatures, 10 pts × 2 = 20 pts): Consider the El-Gamal signature scheme. The public key is given as (p,α,β), where p is a large prime number, α is a generator of , and β = αa mod p where a is the secret signing key. Recall that in El-Gamal signature scheme, signature consists of (γ,δ) where γ = αk mod p, and δ = (m−aγ)k−1 (mod p−1), where k is a randomly chosen integer in .

(a)    Let the public key be (p,α,β) = (13,7,5). “A” signs m1 = 2, yielding (γ1,δ1) = (11,1) and signs m2 = 1, yielding (γ2,δ2) = (11,8). “E” is able to observe these two messages and the corresponding signatures. Show that “E” can recover the secret key a without solving the discrete log problem. What is a?

(b)    Suppose that “A” accidentally chooses k = a. Explain how “E” can immediately notice this and retrieve the secret key a given a single signature (m,γ,δ).

4.    [Com](Digital Signatures, 10 pts × 2 = 20 pts): This question deals with the variants of El-Gamal and Schnorr’s signature schemes.

(a)    We consider following variation of the El-Gamal signature scheme. In the modified version, the public and private keys are same as the original El-Gamal, so that the public key is given as (p,α,β), where p is a large prime number, α is a generator of  , and β = αa mod p where a is the secret signing key. Recall that in the original El-Gamal, δ = k−1(m−aγ) (mod p−1). In the modified scheme, however, we let δ = aγ + km (mod p − 1). Signature for message m is given as sig(m) = (γ,δ) = (αk (mod p),aγ+km (mod p−1)). How is a signature verified in this scheme? Draw the schematic diagram of the verification process.

(b)    We consider the following variation of the Schnorr signature scheme. In the modified version, the public and private keys are same as the original Schnorr, so that the public key is given as (p,q,α,β), where p is a large prime number, q is another prime number such that q|(p − 1). α is a generator of  , such that αq = 1 mod p. β = αa mod p where a is the secret signing key. Recall in the original Schnorr scheme, γ = h(m||αk mod p). In the modified scheme, we let γ = m−1α5k mod p. δ is same as the original Schnorr signature scheme where δ = k + aγ mod q. The signature is given as γ, δ. How is a signature verified in this scheme? Draw the schematic diagram of the verification process.

5.    [Com] : “A” wants to prove to “B” that she knows that value x such that gx = y mod p, where p is a large prime number. “B” knows values of g,y,p. However, “A” does not want to reveal the secret x to “B”. Instead, “A” and “B” do the following

(I)         “A” chooses a random integer r, and sends t = gr mod p to “B”.

(II)       “B” chooses a random integer c and sends it to “A”.

(III)     “A” computes s = r + cx (mod p − 1) and sends it to “B”.

How can “B” verify that “A” knows x such that gx = y mod p?