Key Exchange and Diffie-Hellman
Kristian Gjøsteen · 2022
This chapter shows how Alice and Bob can establish a shared secret that is safe against Eve eavesdropping, using the famous Diffie-Hellman protocol. Eve can find the shared secret by computing discrete logarithms. It is conjectured that this is the only way, so this chapter first discusses how to compute discrete logarithms in any finite cyclic group. This discussion establishes requirements on the group order. Alice and Bob need to decide on a group to use. One possibility is the multiplicative subgroup of a finite field. The chapter discusses how to find suitable primes, including primality testing, and how to use index calculus methods to compute discrete logarithms in the finite field. The chapter also develops arithmetic on elliptic curves and briefly discusses how to find suitable elliptic curves as well as how to compute discrete logarithms on various elliptic curves.