šŸ–Šļø
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

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

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.

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

PreviousPollard's p-1NextSolving the DLP

Last updated 3 years ago

Was this helpful?