# Weaknesses in Diffie-Hellman

The Diffie-Hellman Protocol is a widely used key agreement protocol, also called a key exchange protocol, used to establish a shared secret key between two parties. That secret key will then be used to encrypt the data that is to be transmitted, using a symmetric encryption algorithm like the Advanced Encryption Standard (AES). Diffie-Hellman solved one of the most significant problems with symmetric encryption: how to share the symmetric key.

In Diffie-Hellman, two parties, in this example user A and user B, agree on shared non-zero integer values*, *a prime number* (p)* and a generator *(g)* that is a prime factor of *p*. Each party then randomly selects a secret integer *(s*), which must not be shared with anyone else. Both parties then calculate a public value (*A *or *B*) to share with the other through the formula *g ^{s} mod p*.

Once each party’s public value has been shared, the secret key (*K*) can be calculated through the formula *K *= *B ^{s} mod p* for user A and

*K = A*for user B. Now both users have a shared secret key,

^{s}mod p*K*, that even an eavesdropper cannot calculate without knowing the secret integers,

*s*, which is known as the

*Computational Diffie-Hellman*assumption.

The problem with Diffie-Hellman arises when the value for *p* is not sufficiently large. With small values for *p*, it is possible to iterate through possible values for each user’s *s* until the correct values are found. This is a known weakness of Diffie-Hellman, which is addressed by extremely large values for *p.*

For demonstration purposes, I wrote a Python script that, given small values, will take in only the *public values p, g, A, and B*, and calculate each user’s secret integers, *s*, and the shared secret key, *K.*

To give an example, assume a scenario where user A and B agree on the value of *p* as 21101 and *g* as 174. User A’s public integer is 18258 and user B’s is 11535. We **do not** **know **each user’s secret integer, *s*, or the shared secret, *K.*

The script iterates through possible solutions until it finds values for each user’s *s* that create the same *K* and the correct values for *A* and *B.* In this example, the script discovered that the shared secret key is 9213. User A’s secret integer is 12 and user B’s is 37.

I hope this is a good example how it is *critical *to select sufficiently large values when using Diffie-Hellman. It is important to note that selecting a large prime for *p* does not make it *impossible* to break Diffie-Hellman, but it makes it computationally infeasible, at least with current technology.