Key Exchange Solutions

Diffie-Hellman Key Exchange
The Diffie-Hellman protocol allows 2 people to use random values and yet each generate the same symmetric key without transmitting the value of the key.
The security of the protocol lies in the discrete log problem:
given y, g and p find x such that
y = gx mod p

Alice and Bob need to agree on a key to use in a symmetric key cryptosystem. They choose a large prime number p and generator g.
Alice
Generates random number a,
Computes x=ga mod p
Sends x to Bob
Receives y from Bob
Computes k=ya mod p
Bob
Generates random number b,
Computes y=gb mod p
Sends y to Alice
Receives x from Alice
Computes k=xb mod p

Why Diffie-Hellman works
Alice has computed
k = ya mod p
= (gb)a mod p
= gba mod p
= gab mod p
Bob has computed
k = xb mod p
= (ga)b mod p
= gab mod p
So Alice and Bob both have the same value of k.

How secure is it?
We assume that cryptanalyst Charles knows the values of p and g and that he eavesdrops on the exchange between Alice and Bob so that he also knows x and y.
However, unless Charles can solve a DLP, he is unable to find a or b.
It is believed that it is just as hard to find k from x and y without finding a or b.

The Needham-Schroeder Protocol
This is another protocol for exchanging keys between Alice and Bob.
This time they use only symmetric key cryptography
But
They need a trusted third party (TTP) or Server (S).

Alice and the server have a key KAS
Bob and the server have a key KBS
Alice and Bob want to establish a shared key KAB so that Alice can send Bob a message.
They communicate with each other and the server as follows:

Alice sends the server S the names of Alice and Bob to request that a session key be generated.
The server sends to Alice:
The name of Bob
A session key for Alice and Bob to share
The name of Alice and the session key both encrypted using KBS
All 3 items above are encrypted using key KAS

Alice uses key KAS to decrypt the items sent to her in step 2. Alice now knows the session key KAB.
Alice sends Bob the value of 2c) which is the name of Alice and the session key KAB encrypted with KBS
Bob decrypts the name of Alice and the session key using his key KBS. Now Bob knows the session key KAB which he uses to communicate with Alice.

Needham-Schroeder
A S: A,B
2. S A: eKAS(B, KAB, eKBS(A, KAB))
Alice decrypts to get B, KAB, eKBS(A, KAB)
A B: eKBS(A, KAB)
Bob decrypts to get A, KAB

Needham-Schroeder 2
A S: A,B,NA
2. S A: eKAS(B,NA, KAB, eKBS(A, KAB))
3. A B: eKBS(A, KAB)
B A: eKAB(NB)
A B:eKAB(NB -1 )

Certificates
A certificate consists of a public key together with an identification of the key user. The certificate is issued by a trusted third party(TTP) called a
certification agency (CA)
The certification agency might be a government agency or financial institution.

The CA guarantees the link between the user and the public key by digitally signing a document which contains the user name, the public key, the name of the CA, the expiry date of the certificate and perhaps other information such as access rights.

X.509 Standard
Bob generates a document containing his relevant information and presents himself with this document to the CA.
The CA confirm Bob’s identity.
The CA hash the document using SHA-1 and encrypt it using their own private key.
This is the certificate.