Diffie–Hellmanův protokol pro výměnu klíčů

Diffie–Hellmanův protokol pro výměnu klíčů není standardní šifra. Účelem tohoto protokolu je přenést klíč, který bude při komunikaci využíván některou symetrickou šifrou (nejčastěji AES). Výhoda tohoto postupu je, že symetrické šifry pracují výrazně rychleji a jsou obecně považovány za bezpečnější. Protokol byl představen v roce 1976, jeho bezpečnost je postavena výhradně na problému řešení diskrétního logaritmu. Protokol Diffie–Hellman je nejčastěji kombinován s eliptickými křivkami, vzniká ECDH.

Princip

Předpokládejme, že máme velké číslo p (nejlépe prvočíslo o minimálně 512 bitech), které určuje tzv. řád multiplikativní cyklické grupy. Číslo p musí navíc splňovat požadavek, že u čísla (p-1) jsou prvočísla v kanonickém rozkladu na prvočísla relativně velká. Dále máme číslo g, které je tzv. generátorem multiplikativní cyklické grupy. Aby tak bylo, musí číslo g z matematického hlediska splňovat tuto podmínku (pokud je p prvočíslo):

g ∈ {2, 3, ..., p-2}, ∀q ∈ P, q∣(p-1) platí g^(p-1)/q mod p ≠ 1

Přenos

Alice si chce s Bobem vyměnit soukromý klíč, k tomu musí provést:

1. Alice s Bobem si vymění dvojici p a g (řád a generátor cyklické grupy), toto je veřejná část protokolu (de facto veřejný klíč).

2. Alice vygeneruje tajné přirozené číslo a, kde 1 < a < (p-1). Bobovi zašle číslo c_a, což je výsledek výpočtu:

   c_a = g^a mod p

   (Zde je pointa bezpečnosti protokolu, vyčíslení diskrétního logaritmu, který by určil tajné a, je extrémně časově náročný)

3. Bob udělá totéž, vygeneruje tajné přirozené číslo b, kde 1 < b < (p-1). Alici zašle výsledek výpočtu:

   c_b = g^b mod p

4. Alice určí společný klíč vypočtením:

   k = c_b^a mod p

   Bob určí společný klíč vypočtením:

   k = c_a^b mod p

Tato čísla jsou stejná, představují tajný společný klíč, který se dále může využívat při symetrickém šifrování. Důvod proč jsou čísla stejná si můžeme uvědomit při dosazení:

k ≡ c_a^b ≡ (g_a)^b ≡ (g_b)^a ≡ c_b^a ≡ k (mod p)

Tento zápis využívá základů modulární aritmetiky, v podstatě je to stejné, jako by byla místo ≡ rovnítka, ale zároveň za každým výrazem mezi rovnítky přidáno mod p

Programování

Následuje ukázka v jazyce Java pro generování klíčů jedné ze stran:

import java.math.BigInteger;
import java.security.SecureRandom;

public class DiffieHellman {
    private BigInteger g, p, k, myPrivateKey;
    private int bitLength;
    public BigInteger getG() { return g; }
    public BigInteger getP() { return g; }
    public BigInteger getMyPublicKey() { return g.modPow(myPrivateKey, p); }
    public DiffieHellman() {
        this.bitLength = 512;
        this.initialize();
    }
    private void initialize() {
        //Generates p, such that p-1 has large prime factors:
        SecureRandom rand = new SecureRandom();
        BigInteger pFactor = BigInteger.probablePrime(bitLength - 1, rand);
        BigInteger two = new BigInteger("2");
        while( !((pFactor.multiply(two)).add(BigInteger.ONE)).isProbablePrime(100) ) {
            pFactor = BigInteger.probablePrime(bitLength, rand);
        }
        this.p = (pFactor.multiply(two)).add(BigInteger.ONE);
        //---------------------------------------------------
        
        //Generates g, such that g is primitive root mod p:
        this.g = new BigInteger(bitLength/2, rand);
        BigInteger phiP = p.subtract(BigInteger.ONE);
        while(g.modPow(phiP.divide(two), p).equals(BigInteger.ONE) || g.modPow(phiP.divide(pFactor), p).equals(BigInteger.ONE)) {
            this.g = new BigInteger(bitLength/2, rand);
        }
        //-------------------------------------------------
        
        //Generate Alice's private key (the private key of one communication side):
        this.myPrivateKey = new BigInteger(bitLength/2, rand);
    }
    private BigInteger generateCommonPrivateKey(BigInteger otherSidePublicKey) {
        return otherSidePublicKey.modPow(this.myPrivateKey, p);
    }
}