Chapter 4.6, Problem 33E

We describe a basis key exchange protocol using private key cryptography upon which more sophisticated protocols for key exchange are based. Encryption with protocol is done using a private key cryptosystem (such as AES) that is considered secure. The Protocol involves there parties, Alice and Bob, who wish to exchange a key, and a trusted third party Cathy. Assume that Alice has a secret key k_Alicethat only she and Cathy know, and Bob has a secret key k_Bobwhich only he and Cathy know. The protocal has there steps:

1. Alice sends the trusted third party Cathy the meassage “request a shared key with Bob” encrypted using Alice’s key k_Alice.
2. Cathy send back to Alice a key k_Alice,Bob, which she generates, encrypted using the key k_Alice,followed by this same key k_Alice,Bob, encrypted using Bob’s key, k_Bob
3. Alice sends to Bob the key k_Alice,Bob,encrypted using k_Bob, known only to bob and to cathy

Explain why this protocol allows Alice and Bob to share the secret key k_Alice,Bob,known only to them and to Cathy.

The Paillier cryptosystem is a public key cryptosystem described in 1999 by P. Paillier, used in some electronic voting systems. A public key (n,g) and a corresponding private key (pq) are created by randomly selecting primes p and q so that $\gcd (pq,)=1$ , where $=(p-1)(q-1)$ , and a nonzero element g of $z_m$ with $\gcd ((g^{�}-1)/n,n)=1$ . To encrypt a message $m\in z_n$ a random nonzero element r of $z_n$ is first selected, then used to find $c=g^m{r}^n\mathrm{mod}{n}^2$ .