Diffie-Hellman Key Exchange

• 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
• $‘\alpha ‘$ primitive root of $‘q‘$

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

Algorithm

To realize DH we need:

1. efficient algorithm for $‘a^b\mathrm{mod}q‘$
2. efficient algorithm for generating a prime $‘q‘$
3. efficient algorithm for generating a primitive root for this $‘q‘$

1.

int expmod_r (int a, int b, int q) {
    if (b == 0) return 1;
    if (b%2 == 0)
        return ((expmod_r(a,b/2,q))^2) % q;
    else
        return (a*expmod_r(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;
}

2. Probabilistic approach is best: Miller Rabin primality test

int generate_prime(int k) { // k rounds of testing to perform
    bool probablyPrime = false;
    while (!probablyPrime) {
        int n = getRandomInt();
        probablyPrime = miller_rabin(n,k);
    }
    return n;
}

For full algorithm in C see here.

3.

1. generate $‘j‘$ factors $‘f‘$, multiply them, add 1, result is $‘\alpha ‘$, test primality
   • do until you have a prime $‘\alpha ‘$
2. loop factors, test if there is $‘f_i\mid {\alpha }^{q-1/f_i}\equiv 1‘$, in modulo $‘q‘$
   • if true go back to step 1.
3. return $‘\alpha ‘$

Complexity

For $‘a^b\mathrm{mod}q‘$, with $‘n‘$ as the bit-length of $‘b‘$

• recursive algorithm: $‘O(2{\log }_2(b))=O(2{\log }_2(2^n))=O(2n)=O(n)‘$
• iterative algorithm: $‘O(n)‘$

Miller Rabin

• $‘O(k{\log }^{3}n)‘$
  • polynomial

Primitive Root

• complexity is in step 2. meaning complexity of modulo exponent $‘O(n)‘$

Security

By the rules of modular arithmetics:

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‘$
• $‘\alpha ‘$
• $‘Y_A‘$
• $‘Y_B‘$

But for larger primes discrete logarithms are considered infeasible.