##### Reference no: EM1368506

1. Find the solution of the system

*x *1 (mod 5)

*x *3 (mod 6)

*x *2 (mod 7)

in Z_{210}, 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, e_{2}. Moreover e_{l} and e_{2} 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^{2} 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 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 = **(*_{g}*X.E3 **p*_{B}^{-}*1)RA *_{mo}d *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.