Crypto-IT

• bez wcześniejszego uwierzytelnienia

Algorytm Diffiego-Hellmana jest obecnie jednym z najcześciej używanych obecnie algorytmów negocjowania sekretnego klucza, używanym w wielu protokołach, w tym w SSL/TLS. Jest uważany za nieco szybszy niż RSA, który również umożliwia utworzenie sekretnego klucza.

Protokół Diffiego-Hellmana może być również wykorzystywany do szyfrowania wiadomości przy użyciu szyfrowania z kluczem publicznym.

Został po raz pierwszy opublikowany przez amerykańskich kryptologów Whitfield'a Diffie'a i Martin'a Hellman'a w roku 1976. Wiadome jest jednak, że algorytm ten został odkryty parę lat wcześniej przez pracowników brytyjskiego wywiadu (James'a Ellis'a, Clifford'a Cocks'a i Malcolm'a Williamson'a), ale pozostał utajniony.

Algorytm protokołu Diffiego-Hellmana przedstawia sposób komunikacji pomiędzy dwoma zainteresowanymi stronami, która umożliwia ustalenie współdzielonego sekretnego klucza. Następnie klucz ten może być używany podczas dalszej komunikacji, chronionej przy użyciu szyfrowania symetrycznego.

Algorytm ten wykorzystuje teorię logarytmów dyskretnych w ciałach skończonych.

Poniżej przedstawiono protokół wymiany informacji pomiędzy dwoma użytkownikami, nazwanymi zwyczajowo Alice i Bob. Aby wynegocjować wspólny sekretny klucz za pomocą protokołu Diffiego-Hellmana, należy wykonać poniższe kroki:

1. Alice i Bob uzgadniają liczbę pierwszą p i bazę g.
2. Alice wybiera sekretną liczbę całkowitą a, a następnie wysyła Bobowi liczbę A = g^a mod p.
3. Bob wybiera sekretną liczbę całkowitą b, a następnie wysyła Alice liczbę B = g^b mod p.
4. Alice oblicza liczbę k = B^a mod p.
5. Bob oblicza tę samą liczbę k = A^b mod p.
6. Od tego momentu Alice i Bob współdzielą sekretną liczbę k.

Otrzymana przez obie strony liczba k jest bardzo duża - wykorzystywane w algorytmie liczby a i b mają przynajmniej po 100 cyfr, natomiast liczba pierwsza p ma przynajmniej 300 cyfr. Wartość k może być następnie zmieniona na klucz symetryczny za pomocą funkcji haszującej. Klucz symetryczny jest stosowany do szyfrowania całej dalszej komunikacji.

Możliwe jest wykorzystanie protokołu Diffiego-Hellmana do szyfrowania wiadomości przy użyciu kluczy publicznego i prywatnego.

W takim przypadku, Bob mógłby wysłać wiadomość do Alice, szyfrując ją za klucza publicznego Alice, którym są trzy liczby: g, p, g^a mod p. W celu przesłania Alice sekretnej wiadomości, Bob musi wylosować liczbę b, a następnie wysłać niezaszyfrowaną liczbę g^b mod p do Alice. Wreszcie przychodzi czas na wysłanie właściwej wiadomości, zaszyfrowanej za pomocą klucza symetrycznego (g^a)^b mod p.

Jedynie Alice będzie w stanie określić wartość b i odszyfrować wiadomość. Zastosowanie klucza publicznego zapobiega również atakom man-in-the-middle.

Przytoczony algorytm umożliwia szyfrowanie danych za pomocą szyfrów asymetrycznych. Obecnie jednak, dużo bardziej popularnym sposobem szyfrowania z kluczem publicznym jest RSA.

Można udowodnić, że dobranie przez zainteresowane strony odpowiednio dużych i losowych liczb początkowych, zapewnia bezpieczeństwo algorytmu. Napastnik musiałby rozwiązać problem obliczania dyskretnych logarytmów w ciele skończonym (czyli w przedziale ograniczonym przez pewną duża liczbę). Obecnie nie są znane wydajne algorytmy, które pozwoliłyby na obliczenie dyskretnych logarytmów w efektywny sposób.

Po ustaleniu klucza symetrycznego, strony porzucają wartości a i b. Uniemożliwia to wykradnięcie jednej z tych liczb przez inną osobę.

Ze względu na brak uwierzytelnienia uczestników, protokół ten jest podatny na ataki typu man-in-the-middle. Napastnik może rozpocząć dwie sesje protokołu (z Alice i z Bobem) i podając się za przeciwne strony, ustalić dwa klucze symetryczne wykorzystywane potem w komunikacji z nimi za pomocą szyfrowania symetrycznego.

Podnoszenie do potęgi liczby naturalnej modulo liczba pierwsza jest jedną z podstawowych operacji w kryptografii. Podlega ono ogólnym prawom rządzącym arytmetyką modulo. Wykładnik, podobnie jak podstawa, jest dodatnią liczbą całkowitą. Dodatnią liczbą całkowitą jest również wynik działania.

Działanie podnoszenia do potęgi modulo liczba pierwsza można przedstawić jako szereg działań polegających na podnoszeniu do kwadratu i dzieleniu kolejnych wyników przez ustaloną liczbę pierwszą.

Przykładowo podniesienie czterech do potęgi 9 modulo 7 można obliczyć w następujący sposób:
    4⁹ mod 7:
    4² mod 7 = 16 mod 7 = 2
    4⁴ mod 7 = 2² mod 7 = 4 mod 7 = 4
    4⁸ mod 7 = 4² mod 7 = 16 mod 7 = 2
    4⁹ mod 7 = (4¹ mod 7 * 4⁸ mod 7) mod 7 = 4 * 2 mod 7 = 1