AKE Protocols Based on Diffie-Hellman

Although the basic Diffie-Hellman protocol we described doesn’t provide authentication, there are many different ways in which it can be adapted to do so.

We now describe one way of building authentication. The station-to-station (STS) protocol makes an additional assumption that Alice and Bob have each established a long-term signature/verification key pair and have had their verification keys certified. A simplified STS protocol proceeds as follows (where all calculations are modulo $p$):

1. Alice randomly generates a positive integer $a$ and calculates $g^a$. Alice sends $g^a$ to Bob along with the certificate $CertA$ for her verification key.

2. Bob verifies $CertA$. If he is satisfied with the result, then Bob randomly generates a positive integer $b$ and calculates $g^b$. Next, Bob signs a message consisting of Alice’s name, $g^a$ and $g^b$. Bob then sends $g^b$ to Alice along with the certificate $CertB$ for his verification key and the signed message.

3. Alice verifies $CertB$. If she is satisfied with the result, then she uses Bob’s verification key to verify the signed message. If she is satisfied with this too, she signs a message consisting of Bob’s name, $g^a$, and $g^b$, which she then sends back to Bob. Finally, Alice uses $g^b$ and her private key $a$ to compute $(g^b)^a$.

4. Bob uses Alice’s verification key to verify the signed message he has just received. If he is satisfied with the result, then Bob uses $g^a$ and his private key $b$ to compute $(g^a) ^b$.

This protocol is shown in the illustration below: