Kryptografia – Diffie-Hellman Protocol

Przedmowa

Z góry chciałbym cię uprzedzić, że nie jestem super znawcą tematu kryptografii, więc mogą się pojawić jakieś błędy o wytknięcie których proszę w komentarzu, kryptografią interesuję się czysto hobbistycznie i dlatego starałem się napisać ten artykuł w sposób rzetelny i ciekawy.


Kryptografia

Większość artykułów odnośnie kryptografii (ogólnie) we wstępie zaznacza jak to w dzisiejszych czasach rozwinęło się szyfrowanie danych, a także zwiększyło się zapotrzebowanie na bardziej zaawansowane na ich szyfrowanie, w moim artykule nie będzie inaczej.

Nie chcę tutaj przytaczać tutaj całej historii powstawania szyfrów, jednak co nieco o tym wspomnę. Jednym z pierwszych znanych nam szyfrów, a także jednym z prostszych jest szyfr Cezara, który polega na „przesunięciu” o określoną wartość, co może wyglądać mniej więcej w ten sposób:

Widzimy tutaj alfabet w wersji, gdzie przesunęliśmy wszystkie wartości o 1, więc możemy uznać, że klucz tego szyfru ma wartość 1.

key = 1;

Szyfrowanie polega na podmianie liter z naszego „normalnego” alfabetu na literę, z przesuniętego alfabetu znajdującą się bezpośrednio pod jej poprawnym miejscem w alfabecie, tzn. zamiast litery ‚A’ zapiszemy ‚Z’, dla przykładu zaszyfrujmy sobie słowo „CRYPT”:

Zamiast C wstawiamy literę B, R: Q, itd, wtedy otrzymamy: „CQXPS”. To szyfrowanie jest stosunkowo proste w implementacji, ale jednocześnie bardzo łatwo jest tutaj znaleźć klucz, ponieważ możemy przesunąć w ten sposób o maksymalną wartość 25 (o większe np o 100, ale można bez problemu napisać program, który zamiast przesuwać cały alfabet o 100 razy przesunie go jedynie o potrzebną wartość w przedziale [0-25]).

Kontynuując moją historię o kryptografii to potrzeba szyfrowania informacji wzrosła podczas okresów wojny światowej, gdzie jak powszechnie wiadomo wynaleziono takie cudo jak internet, który następnie oddano szerszej publiczności, gdzie został dość mocno udoskonalony i w ten sposób dotarliśmy do naszych czasów, gdzie w sposób całkowicie nieświadomy korzystamy z szyfrowania, bo właśnie w naszych czasach kryptografia rozwinęła się najbardziej.

Najpopularniejszym i najtrudniejszym szyfrem do złamania jest RSA, z którego korzystamy przy każdym logowaniu się do dowolnego banku, jest wiele implementacji tego algorytmu ponieważ oryginalna wersja tego algorytmu została utajniona zaraz po jego opatentowaniu, lecz mimo to kilka lat później została odnaleziona jedna z jego wersji.

O samym algorytmie RSA dokładniej opowiemy sobie innym razem, jednak wspominam o nim dlatego, że na podstawie protokołu Diffiego-Hellmana, a raczej na problemie jaki przedstawił powstał tak dobry szyfr jak RSA.


Diffie-Hellman Protocol

Czy też protokół Diffiego-Hellmana w naszym języku bazuje na dość ciekawym zjawisku, jakim są działania na grupach konkretnie dzielenie modulo. (nie będę tutaj przytaczał czym są grupy, bo to jest temat na przynajmniej 2h wykładu z algebry na informatyce). Kolejną rzecz, która sprawia, że ten protokół jest dość przydatny jest fakt, że zaleca używanie się w nim dużych liczb pierwszych (i mówiąc „dużych” mam na myśli bardzo dużych) co sprawia, że znalezienia klucza przy najszybszych komputerach jest procesem zajmującym wiele lat (o problemie liczb pierwszych możecie posłuchać na kanale Mirosława Zelenta, który wyjaśnia to w sposób bardzo przystępny).

Znowu wróćmy nieco do historii, mianowicie jak powstał ten protokół? Autorowi bardzo zależało na stworzeniu jakiegoś schematu, który byłby łatwy do zrobienia w jedną stronę ( -> ), ale trudny do odwrócenia ( <- ), tutaj własnie zostało wykorzystane dzielenie modulo, które jak się okazuje nie jest takie proste w odtworzeniu w „drugą stronę” ( <- ).

Jednak zanim przejdziemy dalej, przyjrzyjmy się ogólnemu obrazowi tego protokołu, przytoczę tutaj dość popularny przykład na kolorach, gdzie Alicja i Bob mają przekazać sobie kolor, tak aby nie podsłuchała go Ewa.

Przejdźmy przez ten proces razem:

  1. W pierwszym kroku Alicja i Bob wybierają ogólnie wszystkim znany kolor (Ewa też go zna).
  2. Następnie do tego koloru dodają losowo wybrany inny kolor (klucz prywatny).
  3. Oba kolory mieszają razem ze sobą i przekazują te kolory do siebie nawzajem, operacja odseparowania tych kolorów przez osobę trzecią (Ewę, która zna zmieszany kolor i wspólny kolor) jest już na tym etapie dość trudne i czasochłonne.
  4. W kolejnym kroku następuje połączenie odebranego koloru i wcześniej wylosowanego przez siebie koloru.
  5. I ta dam! Powstaje kolor znany tylko Alicji i Bobowi.

Ewa na końcu tego zostaje ze wspólnie znanym wszystkim kolorem i wymienionymi kolorami. Może próbować odnaleźć wspólnie uzgodniony tajny kolor przez Boba i Alicję, lecz bez któregoś klucza prywatnego jest to niezwykle trudne.

Pewnie już oczekujesz najważniejszego, więc samych obliczeń, a więc let’s do some math!

Podczas powyższego przykładu udało mi się przemycić 2 pojęcia: klucz prywatny i klucz publiczny, z tych pojęć będziemy zaraz korzystać, więc aby nie było niejasności:

  • klucz prywatny, to klucz który znamy tylko my, nie dzielimy się nim z nikim;
  • klucz publiczny, to klucz powszechnie znany, możemy się nim dzielić ponieważ jego znajomość nie jest aż tak bardzo kluczowa jak znajomość klucza prywatnego.

Jak protokół wygląda w praktyce? (operator ^ oznacza potęgę, a mod dzielenie modulo)

  1. Ustalamy wspólną liczbę pierwszą i generator: p, g.
  2. Następnie wybieramy losowo liczbę prywatną: private_key.
  3. Krok „mieszania kolorów”, gdzie liczymy klucz publiczny ze wzoru: public_key = g^private_key mod p. Następnie wysyłamy wynik publicznie drugiej osobie.
  4. Kolejnym krokiem jest otrzymanie sekretnego klucza: secret_key = public_key (drugiej osoby) ^ private_key (nasz) mod p.
  5. Obliczony klucz, jest znany tylko dwóm osobom.

To z czym musiałaby się zmagać osoba trzecia nazywa się logarytmem dyskretnym i przy odpowiednio dużych liczbach jest trudne do obliczenia. Dla lepszego pokazania sposoby działania zróbmy to na przykładzie na liczbach:

  1. Ustalamy wspólne p = 17 i g = 3.
  2. Wybieramy losowo liczbę prywatną (weźmy private_key1 = 15, private_key2 = 13).
  3. Liczymy klucz publiczny public_key1 = 3^15 mod 17 = 6, public_key2 = 3^13 mod 17 = 12 i wysyłamy go.
  4. Otrzymujemy sekretny klucz: secret_key1 = 12^15 mod 17 = 10, secret_key2 = 6^13 mod 17 = 10.
  5. Z radością stwierdzamy fakt, że secret_key1 <=> secret_key2 i możemy przystąpić do szyfrowania/deszyfrowania danych.

Połączenie tego algorytmu z generatorem dużych liczb pierwszych sprawia, że złamanie tego algorytmu jest niemal niemożliwe (dopóki ktoś nie wymyśli jak w szybszy sposób generować kolejne liczby pierwsze).


Mowa końcowa

Jak łatwo zauważyć sama idea tego protokołu jest dość prosta, a implementacja nie powinna stwarzać jakiegoś problemu, lecz mimo to umieszczam prosty kod na samym dole strony, co warto zauważyć aby używać w pełni ten algorytm trzeba dołączyć dodatkowe biblioteki, któe pozwalają na przetrzymywanie w pamięci większe liczby niż te w standardzie.

Jak już wspominałem ten algorytm jest dość ciężki do złamania w przypadku dużych liczb pierwszych, jednak ma swoje wady mianowicie genialnie nadaje się w przypadku wymianie danych pomiędzy 2-3 osobami (na 3 osoby jest nieco inna implementacja), ale jest mało poręczny  w przypadku większej ilości osób, do tego powstało RSA (o którym może też nieco kiedyś opowiem).

Moim zdaniem ten algorytm fajnie się może sprawdzać w grach multiplayer 2 osobowych, czy też programach w których nawiązuje się jedynie połączenie pomiędzy dwoma urządzeniami.


Bibliografia

Ten artykuł oczywiście by nie mógł powstać gdyby nie (moja skromna osoba) kilka fajnych źródeł (w tym osób) skąd czerpałem swoją wiedzę


Dajcie znać, czy ten artykuł Wam się spodobał, czy zbyt nie przynudzałem, czegoś nie wyjaśniłem (albo zrobiłem to zbyt powierzchownie), coś pominąłem, albo gdy po prostu chcecie się podzielić swoim zdaniem z innymi to napiszcie o tym w komentarzu.

Jestem ciekawy czy chcielibyście jakiś kolejny artykuł o kryptografii (np. o RSA). I tak na marginesie, prawdopodobnie napiszę jakąś prostą implementację tego programu i pojawi się ten kod/program poniżej.


  • Lukas

    Bardzo fajnie wyjaśnione 🙂 Będą jeszcze jakieś kursy/posty odnośnie tego zagadnienia?;)

    • Tak jak wspominałem najprawdopodobniej pojawi się coś o RSA, może też coś wrzucę o generowaniu dużych liczb pierwszych bo właśnie na tym opiera się siła zarówno protokołu jak i RSA.

      • Lukas

        Okej 🙂 Btw. może napomkniesz coś gdzieś kiedyś o bibliotece Thor? Bo wydaje się bardzo przydatna ;p

        ( http://www.bromeon.ch/libraries/thor/ )

        • Kiedyś z tego co mi się wydaje wspominałem gdzieś, że istnieje takie coś, ale nie zagłębiałem się w to bardziej, ale jeżeli jest taka potrzeba to prawdopodobnie coś się pojawi na ten temat.

  • Robson

    Bardzo przejrzyscie wyjasniony mechanizm. Chetnie poczytalbym Panski artykol o RSA. Pozdrawiam

    • RSA to kolejny artykuł z serii kryptografii, jednak jego moc leży głównie w dużych liczbach pierwszych, o których opowiem za 1-2 tygodnie.