1.    Find the solution of the system

x              1 (mod 5)

x              3 (mod 6)

x              2 (mod 7)

in Z₂₁₀, using the Chinese Remainder Theorem and the extended Eu­clid's algorithm. Show all your work.

2.    Compare the RSA and EIGamal signature schemes' performance in terms of efficiency of the verification operation, ability to pre-compute most of the signature operation in advance.

Which scheme should be preferred for an SSL certificate? Which scheme should be preferred for a real-time authentication protocol on a restricted device - e.g., an RFID tag on an electronic passport? Explain why.

3.       Alice and Bob are very good friends and don't mind sharing the same RSA modulus n. Of course, to have their own different private keys, they use different public exponents, el, e₂. Moreover e_l and e₂ are relatively prime. A common friend Charlie sends a message x to both, encrypting it with their respective RSA keys, yi = x" mod n, y2 = xe² mod n. Show how Eve, who knows the public keys of Alice and Bob and observes the ciphertexts yi and y2, can find out the message x. Describe explicitly how you use Extended Euclidean Algorithm in your solution.

4.       On EIGamal signatures. (You can assume that g has a prime order q instead of p - 1, if you like.)

(a)    Show that if Eve can learn the value of k Alice used in an EIGamal signature, she can compute Alice's private key.

(b)    Suppose Alice's random number generator is broken and it always produces the same k value. How can Eve detect this from the signatures Alice issues?

(c) Knowing that Alice used the same k value in two different signa­tures, describe how Eve can compute that k value used, and then Alice's private key a.

5. A protocol to establish a fresh session key using long-term, certified Diffie-Hellman public keys is as follows:

            The system has a common prime modulus p and a generator g. Each party i has a long-term private key a_i E Z_p__i and a public key P_i = gai mod p.

        To establish a session key between A and B, party A generates a random RA E 4_1, computes XA = aA ± RA mod p - 1, and sends XA to B. Similarly, B computes a random RB E Zp-1 ) XB = aB + RB mod p - 1, and sends XB to A.

       A computes the session key as KA,B = (_gX.E3 p_B^-1)RA _mod p

and B computes

KB,A = (gX A p_A^-1)RB mod _p.

(a)  Show that the protocol is correct (i.e., KA_,B = KB_,A).

(b)  Show that a passive attacker Trudy who has broken a session key KA_,B between Alice and Bob can compute any future session keys between these two parties.

(c)  Describe a simple addition to the session key computation which will preclude this and any similar attacks on this protocol.