1. Consider ElGamal public key cryptosystem with public key (p,,) and private key a where = a. The ElGamal Signature Scheme works as follows: picks k at random from Zp1 and computes the signature for message m as sig(m) = (,) where = k and = k1(ma) mod

(p1).

Prove that such a signature scheme is not allowed to have =0. That is: if a message were signed with a signature in which =0, then it would be easy for an adversary to compute the private key a. Show how?

2. Suppose Elliptic curve E is defined by y2=x3+x+6 over Z1039. Since Z1039 is small, you can program to solve all the following problems.

How many points are over E. What is the lexically largest point over E. Here lexically larger point

means to order the points by the first coordination first and then the

second coordination, E.g., (320,100) > (319,500) and (320,100) < (320, 101).

Does point (1014, 291) belong to E?

Suppose = (799,790) is a generator and = (385,749). (E, , ) is the ElGamal public key. Given the plaintext value (575,419) and random K=100, what is the ciphertext value? Given the ciphertext value ((873,233), (234,14)), what is the plaintext value (Please note: if you re-encrypt the resulting plaintext value with K=100, you may not get back ((873,233), (234,14)), that is correct. As you recall, for whatever K is selected for encryption, the decrypted value is the same.)

Suppose E and a generator = (818, 121) are public. Alice and Bob achieve a shared secret by doing Diffie-hellman key exchange. Alice sends Bob a value (199,72), and Bob sends Alice a value (815,519), what is the secret they achieve?