Overview of the ECDH Algorithm (CNG Example)
The Elliptic Curve Diffie-Hellman (ECDH) key agreement protocol enables two users to create a shared secret agreement. They can do this over a nonsecure, public medium, without having previously exchanged any private information. The shared secret agreement is typically used to derive key material. A symmetric algorithm such as the Advanced Encryption Standard (AES) algorithm can use the key material to encrypt subsequent messages.
The Cryptography Next Generation (CNG) secure communication example demonstrates the CNG implementations of both ECDH and AES algorithms. Alice, Bob, and Mallory create cryptographic keys in their Run methods when they create Communicator objects.
ECDH Mathematics
The ECDH protocol relies on two public parameters: p and g. Parameter p is a large prime number, and parameter g is an integer that is less than p. These two parameters are exchanged over a nonsecure line. After both Alice and Bob receive the two public parameters, they select private integers. Alice chooses a, and Bob chooses b. These values are referred to as private keys.
Alice and Bob then create public keys by using the public parameters and their private keys. Alice uses (g^a) mod p, and Bob uses (g^b) mod p. These are asymmetric keys because they do not match.
Alice and Bob exchange these public keys and use them to compute their shared secret agreement. ECDH mathematics guarantees that both Alice and Bob will compute the same shared secret agreement, although they do not know each other's private keys.
Note
Only a, b and g^ab = g^ba are kept secret. All the other values are public.
Anyone who intercepts the exchange will be able to copy p, g, and both public keys. However, it is computationally infeasible to generate a shared secret agreement from the four publicly shared values without knowing Alice and Bob's private keys.
Decrypting an ECDH-encrypted message by using brute force (that is, by trying all possible keys) is of the same order of difficulty as the discrete logarithm problem. However, the ECDH algorithm achieves the same degree of security with shorter key lengths because it relies on elliptic curves instead of logarithmic curves.
ECDH Example
The following example uses small integers to demonstrate the ECDH algorithm.
Alice and Bob agree on a prime number p and a base integer g:
p = 83, g = 8
Alice chooses a secret integer a = 9, and then sends Bob (g^a) mod p:
(8^9) mod 83 = 5
Bob chooses a secret integer b = 21, and then sends Alice (g^b) mod p:
(8^21) mod 83 = 18
Alice computes ( ( (g^b) mod p)^a) mod p:
(18^9) mod 83 = 24
Bob computes ( ( (g^a) mod p)^b) mod p:
(5^21) mod 83 = 24
Alice and Bob compute the same value (24), because g^(ab) = g^(ba). This value is the shared secret agreement. Alice and Bob use this value to derive the key material that is used by the AES algorithm to encrypt their messages.
This example generates a shared secret agreement with a value of 24. Because this is a small value, it would produce an encrypted message that could easily be broken by a brute-force attack. In a real scenario, p, g, a, and b would be much larger numbers, and a computer would be required to generate the corresponding shared secret agreement.
The CNG classes used in the secure communications example abstract the complex mathematics. They enable you to concentrate on implementing security solutions instead of worrying about multiplying large numbers.
Protocol Limitations
The ECDH key exchange protocol does not prevent man-in-the-middle attacks, because it does not authenticate the senders of the public keys. If an eavesdropper, Mallory, intercepts Alice's public key, he can substitute his own public key and send it to Bob. Mallory can also intercept Bob's public key, substitute his own, and send it to Alice. Mallory can then easily decrypt any messages sent between Alice and Bob. He can change the messages, re-encrypt them with his own keys, and then send them to the recipients.
To solve this problem, Alice and Bob can use digital signatures to sign the public keys before exchanging them. There are two ways to do this:
Use a secure medium, such as voice communication or trusted courier, to transmit a digital signature key between the two parties.
Use a public certification authority (CA) to provide a trusted digital signature key to both parties.
In both cases, an external authentication scheme must be used to verify the identity of the public key senders. The CNG example illustrates what can happen if the key senders are not authenticated. It is written specifically to enable a security exploit.
Symmetric and Asymmetric Keys
Asymmetric systems such as ECDH are very slow. Therefore, they are not used to encrypt large messages. Symmetric systems such as AES, which are many times faster, are used instead.
A typical cryptographic solution uses an asymmetric system to derive a symmetric shared secret agreement. The shared secret agreement is then used to derive key material that is used by a symmetric algorithm to encrypt a message.
The CNG secure communication example models this behavior as follows:
It uses an asymmetric algorithm, the CNG implementation of the ECDH algorithm (the ECDiffieHellmanCng class), to derive a symmetric encryption key (the shared secret agreement).
This key is then used by the CNG ECDiffieHellmanCng.DeriveKeyMaterial method to derive key material. The CNG implementation of the symmetric AES algorithm (the Aes class) uses the key material to encrypt the messages.
See Also
Concepts
Cryptography Next Generation (CNG) Secure Communication Example