Applied Cryptography

Any language like

2 ElGamal Consider the Elgamal signature scheme, as described in the lecture notes, where the hash function is the identity function e., H(m)-m) a) Consider an instance with public key pk -(p,g,y)-(65537,3, 20031). Suppose you are given the following two message-signature pairs (mi, 1) = 31415, (40071 , 17134)) (m,2) (32768, (40071, 22525)) Notice that the value of r gk is the same for both. (That is, both signatures were generated with the same k value. First, outline a method (algorithm) to recover both k and the private key r in this situation. Provide the equations needed to solve for k and x. Then, compute the value of k used and compute the private key r using this method