Diffie–Hellman

Diffie-Hellmanův algoritmus slouží k ustanovení společného symetrického klíče pro dva a více uživatelů. Klíč nelze odposlechnout. Jeho bezpečnost je postavená na principu na problému diskrétního logaritmu.

Na počátku známe modul m, prvek a a hodnotu |a^x|_m. Proto hledáme x. Aby x existovalo, tak musí diskrétní logaritmus existovat - jeho existenci taky neumím efektivně výpočetně zjistit.

Diffie–Hellman pro 2 uživatele

• m je velké prvočíslo, a je celé číslo, které je generátorem násobící grupy mod m.
• Alice a Bob se dohodnou na a , m
• Alice si zvolí k_a tak, že gcd(k_a,m-1)=1.
  • Vypočte y_a = |a^k_a|_m a pošle to Bobovi
• Bob si zvolí k_b tak, že gcd(k_b,m-1)=1.
  • Vypočte y_b |a^k_n|_m a pošle to Alici
• Alice spočítá K=|y_b^k_a|_m.
• Bob spočítá K=|y_a^k_b|_m.
• Oba spočetli stejné číslo, protože K=|y_b^k_a|_m =
  ||a^k_b|_m^k_a|_m = ||a^{k_a · k_b}|_m = ||a^k_a|_m^k_b|_m = |y_a^k_b|_m
• Bezpečnost: Útočník může znát :[a,m,y_a,y_b], ale je pro něj výpočetně nemožné zjistit k_a nebo k_b.

Diffie–Hellman pro více uživatelů

• Slouží ke zřízení společného klíče pro 2+ uživatelů se sdíleným médiem
• Klíč nelze odposlechnout (viz dále)
• Algoritmus:
  • m je velké prvočíslo a je celé číslo. gcd(m,a)=1
  • čísla m, a se rozešlou se všem subjektům
  • každý subjekt si zvolí k_i tak, že gcd(k_i,m-1)=1.
  • každý subjekt vypočte yi=|a^k_i|_m:
    • odešle po sdíleném kanálu všem ostatním stem:[a,m,y_i]
    • příjemci spočítají z_j=|y_i^k_j|_m.
    • rozešlou a takhle se to točí dokud...
    • ...není spočteno K=|y_l^k_n|_m, kde n je počet subjektů.