March 17th, 2011, 06:17 PM
K key dependent upon previous values in el gamal signature
please explain how we can solve the following problem:
Suppose that Alice is using the ElGamal Signature scheme. In order to save time in generating the random numbers k that are used to sign messages, Alice chooses an initial random value k0, and then signs the ith message using the value ki = k0 + 2i (mod p) (therefore ki = ki-1 + 2 (mod p)) for all i 1).
Suppose that Bob observes two consecutive signed messages, say (xi, sign(xi)) and (xi+1, sign(xi+1)). Describe how Bob can compute Alice’s secret key, a, given this information, without solving an instance of the discrete logarithm problem. (Note that the value of i does not have to be known for the attack to succeed.)
please help, thanks a lot