šŸ–Šļø
Crypto
  • Crypto
  • Fundamentals
    • Divisibility, Factors and Euclid's Algorithms
    • Modular Arithmetic
    • Rings, Fields and Euler's Totient Function
  • Further Maths
    • Continued Fractions
  • RSA
    • Overview
    • Public Exponent Attacks
      • e=1
      • Small e
      • Multi-party RSA with Small e
      • Wiener's Attack
    • Choice of Primes
      • N is prime
      • Mersenne Primes
      • P=Q
      • Fermat Factorisation
    • Factorisation Methods
      • Pollard's p-1
  • Diffie-Hellman Key Exchange
    • Overview
    • Solving the DLP
      • Baby Step, Giant Step
Powered by GitBook
On this page
  • The Key Exchange
  • The Discrete Logarithm Problem

Was this helpful?

  1. Diffie-Hellman Key Exchange

Overview

PreviousPollard's p-1NextSolving the DLP

Last updated 3 years ago

Was this helpful?

Unlike RSA, where you can send messages of your choice, the DHKE is used to generate a secret number shared between Alice and Bob. This shared secret is then used as the key for a symmetric cryptosystem like AES.

The Key Exchange

A large prime ppp and a generator g∈Fp,g≠0g \in \mathbb{F}_p, g \neq 0g∈Fp​,g=0 are made public.

Alice and Bob choose their secret integers aaa and bbb respectively. They then compute the following:

A=gamod  pB=gbmod  pA = g^a \mod p \\ B = g^b \mod pA=gamodpB=gbmodp

These numbers AAA and BBB are exchanged between Alice and Bob over a public channel. Once the other person's number is received, they then put it to the power of their secret integer, i.e. Alice computes BaB^aBa and Bob computes AbA^bAb, both modulo ppp. Note that:

Ba=(gb)a=gab=(ga)b=AbB^a = (g^b)^a = g^{ab} = (g^a)^b = A^bBa=(gb)a=gab=(ga)b=Ab

This means that once they do this, they are in possession of the same number, which they can then use as a shared secret.

The Discrete Logarithm Problem

The safety of the Diffie-Hellman Key Exchange is grounded on he difficulty of solving the discrete logarithm problem - the difficulty of computing xxx given

gx≔amod  pg^x \equiv a \mod pgx≔amodp

As you may expect from here, many attacks on Diffie-Hellman rely on situations in which you can efficiently compute the discrete logarithm.

You can see this in Overview presented above - the values gamod  pg^a \mod pgamodp and gbmod  pg^b \mod pgbmodp are sent over a public channel, but because we cannot solve the DLP efficiently an attacker is unable to retrieve aaa or bbb. We say that the DLP is DHKE's trapdoor function.