CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page

Was this helpful?

Export as PDF

Diffie-Hellman

Overview

We need to make some changes: separate the explanation from the code, add a subpart about the MITM and maybe to develop more the instructions

Let's say Alice and Bob want to exchange a secret over an insecure channel. In other words, anyone can read the messages they send, but the goal is to ensure that only Alice and Bob can calculate the secret key.

Diffie-Hellman key exchange provides a solution to this seemingly impossible task. Since code may be easier to understand than a detailed explanation, I'll provide it first:

import Crypto.Util.number as cun
import Crypto.Random.random as crr


class DiffieHellman:
    def __init__(self, p: int):
        self.p = p
        self.g = 5
        self.private_key = crr.randrange(2, p-1)

    def public_key(self) -> int:
        return pow(self.g, self.private_key, self.p)

    def shared_key(self, other_public_key: int) -> int:
        return pow(other_public_key, self.private_key, self.p)


p = cun.getPrime(512)
alice = DiffieHellman(p)
bob = DiffieHellman(p)

shared_key = bob.shared_key(alice.public_key())
assert shared_key == alice.shared_key(bob.public_key())

Here's a brief explanation of the code:

  • We choose a prime ppp and a generator g∈Fpg \in \mathbb{F}_pg∈Fp​

  • Alice picks a private key a∈Zp−1a \in \mathbb{Z}_{p-1}a∈Zp−1​

  • Bob picks a private key b∈Zp−1b \in \mathbb{Z}_{p-1}b∈Zp−1​

  • Alice's public key is gamod  pg^a \mod pgamodp

  • Bob's public key is gbmod  pg^b \mod pgbmodp

  • Their shared key is gab≡(ga)b≡(gb)a(modp)g^{ab} \equiv (g^a)^b \equiv (g^b)^a \pmod pgab≡(ga)b≡(gb)a(modp)

So anybody observing the messages sent between Alice and Bob would see p,g,ga,gbp, g, g^a, g^bp,g,ga,gb, but they wouldn't be able to calculate the shared key gabg^{ab}gab.

PreviousRecovering the ModulusNextMITM

Last updated 4 years ago

Was this helpful?

This is because given ggg and gag^aga, it should be infeasible to calculate aaa. If this sounds familiar, that's because it's the .

The original paper can be found . It uses the group of integers modulo a prime to perform the key exchange. In practice however, any group with a hard discrete log problem can be used.

Discrete Log Problem
here