Asymmetric Cryptography – Diffie-Hellman Key Exchange

In the first part of this blog series I explained the drawbacks of symmetric encryption/decryption and how asymmetric cryptography can help to overcome these deficiencies. In this blog I will explain how and why it works so well and will describe how two parties can exchange a shared secret key using the Diffie-Hellman Key Exchange algorithm.

One-Way Functions

The mechanisms of asymmetric cryptography are based on so-called one-way functions. They are defined to be very easy to compute whereas the computation of their inverse is very hard¹. Examples of one-way functions are integer factorization and the discrete logarithm. Integer factorization relies on the property of every integer that it is decomposable into a set of prime numbers. E.g. the number 444 has prime factors 2², 3 and 37 since 444 = 2² * 3 * 37. Computing the resulting number from the given prime factors is considered very easy; it’s a series of simple multiplications. On the other hand given only the resulting number, decomposing it into its prime factors takes considerably longer. Obviously it is still easy to compute for our example number, however, the same cannot be said for larger numbers with hundreds of digits. A discrete logarithm on the other hand denotes an integer x that solves the equation a^x = b. Computing b given a and x is relatively easy. Calculating x given a and b is comparatively harder.² This property is used in the Diffie-Hellman key exchange algorithm.

Diffie-Hellman Key Exchange

In 1976 Whitfield Diffie and Martin Hellman published a concept using the properties of the discrete logarithm problem that allows the creation of a shared secret for multiple parties using public key cryptography. It works as follows: Alice and Bob both agree on a common number g (called “generator“). It does not matter if Charlie knows g or not. Alice chooses a private key a. Bob does the same resulting in b. They both now compute their public key. Alice will get to A = g^a while Bob gets B = g^b. They then exchange their public keys, which again can be known to Charlie. With their own private key they can now generate the shared secret by calculating A^b = g^ab = g^ba = B^a (A^b, and B^a respectively being the shared secret). Although Charlie knows g, A and B he cannot easily compute their shared secret since he would need to solve A = g^a for a or B = g^b for b, which is very hard as we have learned in the previous paragraph.

In practice the computations are not done over all integers since exponentiation with very large exponents can take a very long time. Instead multiplicative groups of integers modulo a large prime number p (Z_p^*) are chosen. By doing this all (intermediate) results will be restricted to (p-1)². For further details, refer to 3.

Example

Lets choose p=11 to have a small enough group (Z₁₁^* = {1,2,3,4,5,6,7,8,9,10}) to do things by hand. First we need to find an appropriate generator g. Since we operate on a finite group, we want to be able to generate⁵ as many elements in our group as possible. Using 4 we can also prove that for any Z_p^* there is a g where ord(g) = |G|. With p=11 we are able to find an optimal g by using brute-force⁶ which is for example 2, since |{2¹=2, 2²=4, 2³=8, 2⁴=5, 2⁵=10, 2⁶=9, 2⁷=7, 2⁸=3, 2⁹=6, 2¹⁰=1 (mod 11)}|=|G|. Both p and g are known to Alice and Bob (and possibly even to Charlie). Alice and Bob each now choose a number in Z₁₁^*, say a=2 and b=7. These are their respective private keys. They can now easily compute their public keys. Alice will compute A = 2² = 4 (mod 11) and Bob will compute B = 2⁷ = 7 (mod 11) and exchange them. With her private key and Bob’s public key Alice can compute the shared secret as follows: B^a = 7² = 5 (mod 11). Bob will do the same with his private key and Alice’s public key: A^b = 4⁷ = 5 (mod 11). They both have arrived with the same shared secret (5) with Charlie still being ignorant of it.

In Practice

With ever-growing computing power, the key sizes used in practice are getting larger and larger to still be able to guarantee the infeasibility of brute-force (and other) attacks. With larger key sizes, storage sizes, transmission and computation times get larger too, which is bad for everyday usage of cryptography. An attractive alternative is Elliptic Curve Cryptography (ECC) which utilizes smaller keys for a comparable hardness of the inversion of the applied one-way function. I will go into ECC in the next post of this series.

Footnotes

1. “Very easy” meaning a user is able to it on his home computer in fractions of a second. “Very hard” means a user with extensive computing power will still have many years to compute it.
2. Actually there is no proof, that one-way functions even exist. It is just presumed. Proving this would at the same time prove that P≠NP.
3. Using several theorems of number theory⁴ one can find prime numbers, their associated Abelian groups Z_p^* and an appropriate generator g by using of which the Diffie-Hellman problem (a special case of the discrete logarithm problem) is very hard to solve even in the average case.
4. Keywords to look for are Lagrange’s theorem and Fermat’s little theorem
5. To “generate” in this case means creating a subgroup H = {g¹,g²,…}. |H| = ord(g) is called the “order of g” and describes the number of elements in H (which have been generated by g).
6. For the large primes that are used in practice, brute-force is not feasible anymore. Therefore one sometimes needs to settle for large subgroups of Z_p^* whose generator is easier to find.