Techniki i metody szyfrowania tekstu – poradnik szkolny

W poprzednim artykule poruszyliśmy tematykę szyfru Cezara oraz wprowadziliśmy podstawowe definicje, dotyczące kryptologii. Jeżeli nie miałeś(aś) okazji jeszcze z nimi się zapoznać, to odsyłam do poprzedniej publikacji. Osoby, które już przyswoiły zawartą tam wiedzę, mogą bez większych przeszkód zgłębić dalszą tematykę.

Szyfrowanie informacji w świecie IT

W nawiązaniu do poprzedniego poradnika, bez szyfrowania nasze dane byłyby narażone na ich przejęcie i/lub modyfikację. Każda wiadomość, przelew, logowanie do aplikacji, czy przesłanie formularza – wszystko to byłoby widoczne dla każdego „zainteresowanego”. W celu ochrony naszych danych stosujemy (najczęściej poprzez zabezpieczenia firm trzecich) odpowiednie szyfrowanie. Jak to działa? W dużym uproszczeniu – przesyłane dane są kodowane (zniekształcane) w taki sposób, by tylko nadawca i odbiorca informacji wiedzieli, w jaki sposób odczytać wiadomość. A skąd oni mają wiedzieć, w jaki sposób to zrobić? Otóż dana usługa/aplikacja korzysta z odpowiedniej metody szyfrowania tychże danych, generując przy tym „klucz” deszyfrujący. Co zawiera w sobie wspominany „klucz”? Schemat i zasady kodowania i dekodowania informacji (za pomocą złożonych operacji matematycznych). W związku z powyższym możemy wyróżnić dwa typy szyfrowania:

Szyfry symetryczne i asymetryczne

Zacznijmy od tych prostszych i łatwiejszych do implementacji i „złamania”. Szyfry symetryczne to takie, w których stosujemy ten sam klucz do szyfrowania i deszyfrowania danych. Zanim prześlemy zaszyfrowaną informację do odbiorcy, należy przekazać mu za pośrednictwem bezpiecznego połączenia wygenerowany wcześniej klucz. Z tej techniki korzystało się przy metodach zabezpieczania typu AES, 3DES lub kodu Cezara. Są one stosunkowo proste w implementacji i co najważniejsze, pozwalają na szybkie odczytanie i zabezpieczanie danych. Z drugiej strony tego typu szyfrowania są obarczone sporym ryzykiem, wynikającym z możliwości włamania się na kanał transmisyjny i przechwycenia poufnego klucza. Wówczas każda przesyłana na późniejszym etapie paczka danych będzie w pełni narażona na ataki.

Odpowiedzią na te bolączki jest szyfrowanie asymetryczne. W tej technice podstawą komunikacji jest wygenerowanie nie jednego, a dwóch kluczy (pary). Jeden z nich nazywany jest kluczem publicznym (jawnym), jest on udostępniony dla każdego i ma za zadanie szyfrować dane utworzone przez nadawcę. Drugi natomiast jest tzw. kluczem prywatnym (tajnym), który na podstawie klucza publicznego, pozwala na odszyfrowanie przesłanych informacji. Kluczowy (hehe) jest fakt, że klucz publiczny i prywatny tworzą nierozerwalną całość – klucz tajny pracuje tylko na podstawie danych z klucza jawnego. Co ważne, sam klucz publiczny w żaden sposób nie pozwala na identyfikację, czy złamanie klucza prywatnego. Dlatego istotnym jest, by klucz tajny nie był udostępniamy osobom trzecim. Oczywiście „nie ma róży bez kolców”, więc i ta technika jest obarczona pewnymi wadami. Szyfrowanie asymetryczne wymaga więcej czasu oraz ma niższą wydajność w stosunku do rozwiązania symetrycznego.

Przykłady szyfrów asymetrycznych

Do ciekawszych metod szyfrowania asymetrycznego należą:

1. RSA
2. DSA
3. Puzzle Merkle’a
4. Algorytm Diffiego-Hellmana
5. Algorytm ElGamala

Co ważne, opiszę je tutaj bardzo skrótowo, gdyż na podstawie każdej z nich można by napisać całkiem sporą pracę naukową. W związku z tym będę się skupiał na samej „esencji”.

RSA

RSA jest aktualnie jednym z najczęściej wykorzystywanych algorytmów szyfrowania z zastosowaniem klucza publicznego. Metoda ta stosowana jest najczęściej do szyfrowania wiadomości, jak również do podpisów cyfrowych. Metoda ta została stworzona pod koniec lat siedemdziesiątych XX wieku za sprawą trzech Panów – Ron'a Rivesta, Adi Shamira i Leonard'a Adlemana (stąd również wzięła się nazwa szyfrowania – od pierwszych liter nazwisk jego twórców). Algorytm ten pozwala ustawić dowolną długość klucza (najczęściej stosuje się wartość w granicach 128 – 1024 bitów) i wymaga do jego stworzenia użycia dwóch dużych liczb pierwszych. To właśnie w tej cesze tkwi bezpieczeństwo algorytmu RSA – jest ono oparte na trudności rozkładu dużych liczb na czynniki pierwsze. Nie ma ani żadnej prostej metody na wykonanie tego zadania, ani żadnego wzoru, który by ułatwił ten proces. Także jedyną możliwą metodą jest testowanie po kolei podzielności kolejnych liczb.

Nie chcąc wchodzić w zbyt obszerną matematykę będziemy musieli zrobić kilka założeń. Bierzemy „najsłabsze” szyfrowanie RSA (128 bitów) i mamy do dyspozycji superkomputer, który potrafi sprawdzić podzielność biliona (10¹²) dużych liczb pierwszych w ciągu jednej sekundy. Klucz jest 128 bitowy, ale w przypadku dwóch różnych dzielników pierwszych, jeden musi leżeć poniżej wartości pierwiastka z danej liczby, a drugi powyżej. Zatem, aby go znaleźć musimy wyliczyć pierwiastek z rozkładanej liczby, a następnie testować podzielność przez liczby nieparzyste leżące poniżej tego pierwiastka. Również spróbujmy sobie „ułatwić” zadanie i załóżmy, że statystycznie poszukiwana wartość powinna znajdować się w górnej połówce zakresu od 2 do pierwiastka z n. Czyli 2¹²⁸ zmniejsza najpierw wartość swojej potęgi o połowę (dwa dzielniki) i jeszcze od tej wartości odejmiemy dwa (bo co druga liczba jest nieparzysta oraz interesuje nas tylko górna połówka wyników). Przejdźmy zatem do obliczeń:

2(64-2) / 1012 = 4 611 686 sekund = 76 861 minut = 1281 godzin ≈ 53 dni

Zobaczcie o jakiej abstrakcji mówimy – bilion (!) liczb pierwszych rozkładanych na sekundę, a i tak komputer by potrzebował prawie dwóch miesięcy (!), by złamać zabezpieczenie. Dlatego metoda szyfrowania RSA jest do teraz bardzo popularna i chętnie wykorzystywana do zabezpieczania informacji.

DSA

Digital Signature Algorithm powstał w National Institute of Standards and Technology (Narodowym Instytucie Norm i Techniki) na początku lat dziewięćdziesiątych, jako odpowiedź na RSA (które wtedy było algorytmem opatentowanym i płatnym). DSA został upowszechniony na licencji Open Source, przez co zyskał na popularności i do teraz jest wykorzystywany chociażby w OpenSSL, OpenSSH, czy GnuPG. Metoda ta oferuje zbliżony poziom bezpieczeństwa dla kluczy o podobnej wielkości co w szyfrowaniu RSA, jednak używa innych algorytmów matematycznych do podpisywania i szyfrowania. Co istotne, Digital Signature Algorithm jest od swojego starszego brata szybszy w generowaniu kluczy oraz w deszyfrowaniu, natomiast wolniejszy w szyfrowaniu. Dodatkowo DSA jest częściej stosowany do generowania cyfrowych sygnatur (podpisów).

Puzzle Merkle’a

Jest to jeden z pierwszych algorytmów szyfrowania za pomocą klucza publicznego. Został odkryty przez Ralph'a Merkle'a w roku 1974 i opublikowany cztery lata później. Algorytm ten opisuje komunikację pomiędzy dwoma zainteresowanymi stronami, która umożliwia ustalenie wspólnego, sekretnego klucza w taki sposób, aby nie było możliwe jego podsłuchanie przez osoby postronne. Następnie klucz ten można stosować podczas dalszej komunikacji, chronionej przy użyciu szyfrowania symetrycznego.

Cały schemat wymiany wiadomości opiera się na poniższym schemacie:

• nadawca generuje liczbę wiadomości liczoną w milionach o treści analogicznej do następującej: "Wiadomość nr A : Tajny klucz nr Z". Wartość A w tym momencie jest losowo wybraną liczbą, natomiast Z jest losowym kluczem tajnym. A i Z muszą być niepowtarzalne w zbiorze wygenerowanych wiadomości.
• nadawca szyfruje każdą wiadomość za pomocą unikalnego, krótkiego klucza (np. 20-bitowym) i przesyła całość do odbiorcy.
• odbiorca wybiera jedną z otrzymanych (zaszyfrowanych) wiadomości i dokonuje próby jej odszyfrowania metodą brute force (siłową).
• uzyskany w ten sposób klucz zostaje wykorzystany do zaszyfrowania wiadomości
• zaszyfrowany tekst jest odsyłany do nadawcy wraz z wartością A złamanej wiadomości
• nadawca wyszukuje klucz wykorzystany do zaszyfrowania wiadomości (na podstawie przesłanej wartości A) i ją odszyfrowuje

Metoda ta cechuje się tym, że potencjalny napastnik musi poświęcić masę czasu i mocy obliczeniowej do odszyfrowania wiadomości, gdyż nie wie na podstawie której wiadomości został wygenerowany klucz szyfrujący.

Algorytm Diffiego-Hellmana

Protokół uzgadniania kluczy szyfrujących został opracowany w 1976 roku przez dwóch Panów – Witfielda Diffiego oraz Martina Hellmana. Obecnie jest to jeden z popularniejszych algorytmów negocjowania sekretnego klucza. Stosowany jest on w wielu protokołach, m.in. w SSL/TLS i jest uważany za nieco szybszy, niż RSA. Algorytm ten wykorzystuje teorię logarytmów dyskretnych w ciałach skończonych. Aby to zrozumieć i nie zagłębiać się w poważną matematykę, zachęcam do obejrzenia poniższego filmu:

Obejrzyj w

Wykorzystanie algorytmu Diffiego-Hellmana do szyfrowania asymetrycznego prezentuje się następująco:

Nadawca wysyła wiadomość do odbiorcy, wcześniej szyfrując ją za pomocą klucza publicznego odbiorcy, którym są trzy liczby: g, p, ga mod p. W celu przesłania odbiorcy sekretnej wiadomości, nadawca musi wylosować liczbę b, a następnie wysłać niezaszyfrowaną liczbę gb mod p do odbiorcy. Wreszcie przychodzi czas na wysłanie właściwej wiadomości, zaszyfrowanej za pomocą klucza symetrycznego (ga)b mod p. Jedynie odbiorca będzie w stanie określić wartość b i odszyfrować tę wiadomość.

Algorytm ElGamal’a

Ostatnim algorytmem, który omówimy będzie „dziecko” Egipcjanina – Tahera ElGamal’a. Algorytm ten powstał w połowie lat 80. XX wieku, a jego bezpieczeństwo opiera się na trudności rozwiązania logarytmu dyskretnego (podobnie jak w algorytmie Diffiego-Hellmana, choć opiera się na innych zasadach). Bardzo ciężko znaleźć „łatwe” wytłumaczenie tej metody szyfrowania i deszyfrowania, dlatego przedstawię typowo matematyczne wyjaśnienie.

1. Generowanie klucza:

• wybieramy losowo liczbę pierwszą p taką, że (p-1)/2 jest liczbą pierwszą a następnie wybieramy pierwiastek pierwotny g (mod p)
• losujemy wykładnik a ∈ {0,..., p − 2} i obliczamy A = ga (mod p)
• kluczem publicznym jest (p, g, A), a kluczem prywatnym wartość a

2. Szyfrowanie:

• Σ={0, 1, ..., n-1} - przestrzeń tekstów otwartych
• wybieramy losowo liczbę b ∈ {0,..., p − 2} i obliczamy B = gb (mod p)
• wyznaczamy c = Abm(mod p), gdzie m ∈ Σ
• kryptogramem jest para (B,c)

3. Deszyfrowanie:

• dzielimy c przez Ba (mod p)
• obliczamy wykładnik x = p-1-a
• ponieważ 1 ≤ a ≤ p − 2 , więc 1 ≤ x ≤ p − 2
• obliczamy m = Bxc(mod p)

Podsumowanie – szyfrowanie danych

Ufff! Trochę dużo tych informacji, prawda? Pisząc już drugi felieton z tej tematyki dochodzę do wniosku, że kryptografia to niesamowicie ciekawy i szeroki temat – Człowiek ruszy jedno zagadnienie, które odwołuje się do kolejnego i tak coraz dalej i dalej… Jeżeli jednak podoba się Wam ta tematyka, to dajcie znać w komentarzach. Postaram się wtedy poszerzać tę sekcję o kolejne informacje. Na pożegnanie załączam kolejny materiał, który uzupełni przedstawione tutaj informacje:

Obejrzyj w

Źródła: kryptografia.wixsite.com, crypto-it.net, wikiwand.com, cyberwiedza.pl, wikipedia.org, wazniak.mimuw.edu.pl, eduinf.waw.pl, hydrus.et.put.poznan.pl, home.agh.edu.pl, aragorn.pb.bialystok.pl