Diffie-Hellman Key Exchange
security- 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 \(\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{align*}
K &= (Y_{B} )^{X_{A}}_{} \text{mod } q \\
&= ( \alpha^{X_{B}} \text{mod } q)^{X_{A}} \text{mod } q \\
&= ( \alpha^{X_{B}} )^{X_{A}} \text{mod } q \\
&= \alpha^{X_{B} X_{A}} \text{mod } q \\
&= ( \alpha^{X_{A}} )^{X_{B}} \text{mod } q \\
&= ( \alpha^{X_{A}} \text{mod } q)^{X_{B}} \text{mod } q \\
K &= (Y_{A} )^{X_{B}}_{} \text{mod } q \\
\end{align*}
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}\)
\begin{center}
\begin{align*}
X_{B} &= \text{dlog}_{\alpha,q}(Y_{B}) \\
K &= (Y_{A})^{X_{B}} \text{mod }q
\end{align*}
\end{center}
But for langer primes discrete logarithms are considered infeasible.