Diffie-Hellman Key Exchange

security
22.03.2022 - 14:42

1976
One of first public key protocols in Cryptography
specifics at ibm.com

Its main use is the exchange of symmetric keys over a non-secure channel. It functions using module arithmetics.

$q$ prime
$α$ primitive root of $q$

Let $n$ be a positive integer. A primitive root $\mod n$ is an integer $g$ such that every integer relatively prime to $n$ is congruent to a power of $g \mod n$ . That is, the integer $g$ is a primitive root ( $\mod n$ ) if for every number $a$ relatively prime to $n$ there is an integer $z$ such that $a \equiv (g^{z} \mod n)$

Algorithm

To realize DH we need:

efficient algorithm for $a^{b} \mod q$
efficient algorithm for generating a prime $q$
efficient algorithm for generating a primitive root for this $q$

int expmod_r (int a, int b, int q) {
    if (b == 0) return 1;
    if (b%2 == 0)
        return ((expmod(a,b/2,q))^2) % q;
    else
        return (a*expmod(a,b-1,q)) % q;
}

int expmod_i (int a, int[] b, int q) { // here b is encoded in binary
    int c = 0, d = 1;
    for (i = b.length-1; i >= 0; i--) {
        c = c*2; // c is used to prove correctness
        d = (d*d)%q;
        if (b[i] == 1) {
            c++;
            d = (d*a)%q;
        }
    }
    return d;
}

Security

By the rules of modular arithmetics:

$\begin{aligned} K & = (Y_{B})_{}^{X_{A}} mod q \\ = (α^{X_{B}} mod q)^{X_{A}} mod q \\ = (α^{X_{B}})^{X_{A}} mod q \\ = α^{X_{B} X_{A}} mod q \\ = (α^{X_{A}})^{X_{B}} mod q \\ = (α^{X_{A}} mod q)^{X_{B}} mod q \\ K & = (Y_{A})_{}^{X_{B}} mod q \end{aligned}$

This way the two sides exchanged the secret value using the private keys $X_{A}, X_{B}$ . The only way the adversary can solve this knowing:

$q$
$α$
$Y_{A}$
$Y_{B}$

$Unknown environment 'center'$

But for langer primes discrete logarithms are considered infeasible.

Dan's Brain

Diffie-Hellman Key Exchange

Algorithm

Security

Links to this note