1. Find the solution of the system
x 1 (mod 5)
x 3 (mod 6)
x 2 (mod 7)
in Z210, using the Chinese Remainder Theorem and the extended Euclid'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, e2. Moreover el and e2 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 = xe2 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 signatures, 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 ai E Zp_i and a public key Pi = 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 pB-1)RA mod p
and B computes
KB,A = (gX A pA-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.