Ogólny podział algorytmów kryptograficznych

Opublikowany: 07-11-2012 21:59 przez Krystian

 

Niniejszy tekst jest fragmentem mojej pracy dyplomowej. Podczas seminarium padło stwierdzenie, że warto by było upublicznić całość. Ponieważ byłaby to ilość trudna do przełknięcia - praca dyplomowa trafi tutaj w formie spójnych kawałków.

 

Na pierwszy ogień idzie przegląd algorytmów kryptograficzny. Mocno ogólny, za to pozwalający odnaleźć się osobom, które dopiero zaczynają przygodę z "krypto". Za miej więcej dwa tygodnie pojawi się fragment bardzo dokładnie opisujący algorytm AES/Rijndael.

 

Algorytmy kryptograficzne podzielić możemy na kilka rodzajów. Każdy typ oferuje inne możliwości. Współdziałając ze sobą mogą stworzyć spójny systemy kryptograficzny o najwyższej odporności na ataki.


Szyfry symetryczne

Szyfrowanie symetryczne, zwane jest również szyfrowaniem konwencjonalnym. W przypadku tego kryptosystemu mamy do czynienia z szyfrowaniem oraz deszyfrowaniem danych przy pomocy takiego samego klucza. Na rysunku 1 przedstawiony jest model poglądowy procesu szyfrowania symetrycznego. Algorytm szyfrujący E zgodnie ze swą charakterystyką przekształca oryginalny tekst jawny X na szyfrogram Y przy użyciu tajnego klucza K. Algorytm deszyfrujący D jest odwrotny do wcześniej zastosowanego i przy użyciu klucza K na szyfrogramie Y otrzymamy ponownie tekst jawny X.



Rysunek 1. Model poglądowy szyfrowania symetrycznego

Historyczne szyfrowanie symetryczne opiera się na dwóch technikach: podstawieniowych oraz przestawieniowych. Metody podstawieniowe (np. monoalfabetyczne, polialfabetyczne czy homofoniczne) odwzorowują elementy tekstu jawnego na elementy szyfrogramu, zaś przestawieniowe (np. Greckie Skytale) opierają się na uporządkowanych zamianach pozycji elementów tekstu jawnego.

 

Współcześnie używane szyfry symetryczne to: Twofish, Serpent, AES, Blowfish, RC4, 3DES czy IDEA.


Szyfry asymetryczne

Szyfrowanie asymetryczne znane szerzej jako szyfrowanie z użyciem kluczy publicznych to forma kryptosystemu, w którym procesy szyfrowania i deszyfrowania wykonywane są przy użyciu dwóch różnych kluczy - publicznego i prywatnego.



Rysunek 2. Model poglądowy szyfrowania asymetrycznego z użyciem klucza publicznego

Rysunek 2 przedstawia uproszczony model szyfrowania asymetrycznego z użyciem klucza publicznego. Podczas ustanawiania komunikacji generowane są zależne od siebie pary kluczy - publiczny K oraz prywatny P. Nadawca komunikatu przekształca oryginalny tekst jawny X przy użyciu algorytmu szyfrującego E na szyfrogram Y z wykorzystaniem klucza publicznego K odbiorcy wiadomości. Odbiorca chcąc poznać treść komunikatu używa algorytmu deszyfrującego D oraz klucza prywatnego P (tworzącego parę z udostępnionym nadawcy kluczem publicznym K) na szyfrogramie Y. W wyniku tego przekształcenia otrzymuje odtworzony tekst jawny X.

 

W przypadku tego scenariusza zapewniona jest przede wszystkim poufność, ponieważ tylko posiadacz klucza prywatnego jest w stanie odszyfrować wiadomość zaszyfrowaną kluczem publicznym. Proces może przebiegać odwrotnie - nadawca może zaszyfrować wiadomość swoim kluczem prywatnym. Wtedy posiadacze jego klucza publicznego mogą odczytać wiadomość, co jest jednoznaczne z tym, że wiadomość pochodzi z wiarygodnego źródła (uwierzytelnienie), ponieważ musiała zostać zaszyfrowana kluczem prywatnym. Ten scenariusz wykorzystywany jest w podpisach cyfrowych. Kryptografia asymetryczna jest wynalazkiem stosunkowo młodym. Oficjalnie wynalazcami tej metody szyfrowania są cywilni badacze Martin Hellman i Whitfield Diffie, którzy wyniki swoich prac opublikowali w roku 1976. Dwa lata wcześniej Ralph Merkle zaproponował algorytm wymiany kluczy, chociaż historia szyfrów asymetrycznych sięga jeszcze wcześniej. NSA zainteresowało się tego rodzaju koncepcją już w latach 60.

 

Obecnie najpowszechniej używanym kryptosystemem z kluczem publicznym jest RSA (nazwa pochodząca od nazwisk jego autorów - Rona Rivesta, Adiego Shamira i Leonarda Adlemana). Jego bezpieczeństwo wynika z trudności rozkładu dużej liczby złożonej na czynniki pierwsze. Warto też wspomnieć o nieco mniej popularnej od RSA, Kryptografii krzywych eliptycznych - ECC (Elliptic Curve Cryptography), której bezpieczeństwo opiera się na złożoności obliczeniowej dyskretnych logarytmów na krzywych eliptycznych. ECC oferuje bezpieczeństwo podobne do RSA przy użyciu znacznie krótszych kluczy i wyższej wydajności.

 

Współcześnie używane szyfry asymetryczne to: RSA, ElGamal czy ECDH.


Szyfry strumieniowe

Proces szyfrowania strumieniowego odbywa się bit po bicie lub bajt po bajcie. Kolejne bity wejściowego strumienia tekstu jawnego Pi przekształcane są przez algorytm szyfrujący (może to być po prostu operacja XOR) w oparciu o kolejne bity strumienia klucza Ki na strumień bitów szyfrogramu Ci. Podczas deszyfrowania to strumień bitów szyfrogramu Ci przechodzi przez algorytm deszyfrujący, który korzystając z kolejnych bitów strumienia klucza Ki odtwarza pierwotną wiadomość Pi.



Rysunek 3. Model poglądowy szyfrowania strumieniowego z użyciem algorytmu generującego strumień bitowy przy użyciu klucza

Najsłabszym punktem modelu szyfrowania strumieniowego jest algorytm generujący strumień klucza Ki na podstawie wartości początkowej będącej kluczem K. Tego typu algorytmy muszą się pojawić, jeśli szyfr strumieniowy ma mieć praktyczne zastosowanie. W idealnym przypadku teoretycznym można z niego zrezygnować, co oznacza jednak, że klucz musi mieć długość równą wiadomości. Jest to poważne ograniczenie, mamy jednak do czynienia z idealnym bezpieczeństwem tak długo jak klucz pozostaje tajny. Taki model znany jest jako One-time pad (oryginalny pomysł wyszedł od Gilberta Vernama).

 

W praktyce stosuje się generatory liczb pseudolosowych, które na podstawie stosunkowo krótkiego klucza K (pełniącego rolę tzw. ziarna) generują znacznie dłuższy strumień bitów klucza Ki, który służy do zaszyfrowania wiadomości. Tego typu algorytmy muszą spełniać szereg kryteriów, jeśli oparte o nie szyfry strumieniowe mają być bezpieczne. Przede wszystkim generowany strumień powinien mieć możliwie najbardziej zbliżony do losowego rozkład. Strumień nie powinien również zdradzać żadnych informacji na temat klucza K, który posłużył jako ziarno do generowania strumienia Ki, oraz być możliwie nieprzewidywalny. Klasycznymi przykładami szyfrów strumieniowych są szyfry Vigenere’a z autokluczem oraz wspomniany One-time pad Vernama.

 

Współcześnie używane szyfry strumieniowe to: RC4, Salsa20, SNOW czy SOSEMANUK.


Szyfry blokowe

Jak widać na rysunku 4 szyfr blokowy traktuje poszczególne bloki tekstu jawnego M jak odrębne całości i dla każdego z nich w drodze przekształceń produkuje szyfrogram C tej samej długości n bitów co oryginalny tekst jawny M. Przeważnie stosowane bloki o długości 64 lub 128 bitów, Podobnie jak w przypadku szyfru strumieniowego obaj uczestnicy komunikacji współdzielą ten sam klucz K. Proces deszyfrowania to po prostu odwrotność szyfrowania - na wejście algorytmu podajemy szyfrogram C oraz klucz K, a na jego wyjściu otrzymujemy tekst jawny M. Przy wykorzystaniu różnych trybów operacyjnych (łańcuchowanie bloków szyfrogramu - CBC, sprzężenie zwrotne szyfrogramu - CFB, sprzężenie wyjściowe - OFB) za pomocą szyfru blokowego można osiągnąć efekty podobne do tych, jakie dają szyfry strumieniowe.

 

Wiele wysiłku poświęcono zbadaniu właściwości szyfrów blokowych. Generalnie znajdują one znacznie szersze zastosowanie niż szyfry strumieniowe: większość aplikacji sieciowych realizujących szyfrowanie symetryczne wykorzystuje właśnie szyfry blokowe, a nie strumieniowe.



Rysunek 4. Model poglądowy szyfrowania blokowego.

Współcześnie używane szyfry blokowe to: AES, Blowfish, DES, 3DES, Serpent czy Twofish.


Jednokierunkowe funkcje skrótu (funkcje haszujące)

Funkcja haszująca H przekształca komunikat lub blok danych M o dowolnej długości na wartość h zwaną haszem o ustalonej długości. Tego rodzaju algorytm kryptograficzny musi być przede wszystkim deterministyczny - dla konkretnego wejścia zawsze musimy otrzymać ten konkretny wynik. Funkcja haszująca musi spełniać szereg kryteriów, żeby mogła zostać uznaną za dobrą i przydatną w zastosowaniach kryptograficznych.



Rysunek 5. Model poglądowy jednokierunkowej funkcji skrótu

Po pierwsze zgodnie ze swą nazwą musi być jednokierunkowa (nieodwracalna), czyli z hasza h nie możemy uzyskać oryginalnych danych wejściowych M. Najdrobniejsza zmiana w danych wejściowych M musi skutkować zauważalną różnicą w wynikowej funkcji h. Istnienie dwóch różnych danych wejściowych M o tej samej funkcji wynikowej h (tzw. kolizja) musi być możliwie najmniej prawdopodobne.

 

Współcześnie używane funkcje haszujące to: MD5, SHA-1 czy Whirlpool


Podpisy cyfrowe

Podpis cyfrowy nie jest algorytmem samym w sobie, warto jednak zdać sobie sprawę z jego szerokich możliwości. Podpis cyfrowy to mechanizm uwierzytelniania, który umożliwia autorowi wiadomości dołączenie do tej wiadomości danych pełniących funkcję podpisu będącego świadectwem jej autentyczności. Pracę z podpisem cyfrowym możemy podzielić na dwie części. Pierwsza z nich to proces generowania podpisu przez autora wiadomości, zaś druga to proces weryfikacji autentyczności podpisu przez zainteresowane podmioty.

 

Rysunek 6 przedstawia pierwszy z wymienionych wcześniej procesów. Nadawca wiadomości M na samym początku generuje za pomocą funkcji haszującej H, skrót (hasz) h. Potem używa swojego klucza prywatnego K w asymetrycznym algorytmie szyfrującym S, który tworzy zaszyfrowaną wersję hasza, czyli podpis cyfrowy O. Podpis ten dołączany jest do do wiadomości M.



Rysunek 6. Model poglądowy schematu generowania podpisu cyfrowego

Na rysunku 7 zaprezentowany jest proces weryfikacji autentyczności podpisu cyfrowego. W pierwszej kolejności wiadomość M oraz jej podpis O zostają od siebie oddzielone. Wiadomość M zostaje przetworzona przez funkcję haszującą H będącą dokładnie tym samym algorytmem co funkcja użyta podczas generowania podpisu. W efekcie otrzymujemy skrót (hasz) h. Podpis O zostaje odczytany przy użyciu funkcji deszyfrującej algorytmu asymetrycznego D i przy użyciu klucza publicznego nadawcy P. Otrzymujemy dzięki temu hasz h'. Jeśli h jest różne od h' to oznacza to, że doszło do manipulacji albo treścią wiadomości, albo podpisem cyfrowym.



Rysunek 7. Model poglądowy schematu weryfikacji autentyczności podpisu cyfrowego

Algorytm DSS (Digital Signature Standard) jest zaakceptowanym przez NIST standardem podpisu cyfrowego, wykorzystującym funkcje haszujące SHA-1 lub SHA-2.

 

Z góry dziękuję za wszelkie merytoryczne uwagi. Wszystkie ilustracje towarzyszące temu tekstowi są mojego autorstwa.



b

Brak komentarzy