Współczesna kryptologia
Kryptografia symetryczna
Termin kryptografia symetryczna odnosi się do metod, w których nadawca i odbiorca wiadomości używają tego samego klucza (rzadziej: różnych kluczy, ale łatwych do wyliczenia jeden na podstawie drugiego). Inne metody – z dwoma różnymi kluczami (tu również można obliczyć jeden na podstawie drugiego, jest to jednak bardzo trudne, a praktycznie niemożliwe) – zostały odkryte dopiero w latach 70. XX wieku (więcej w sekcji "Kryptografia asymetryczna").
W czasach współczesnych nauka o szyfrach symetrycznych koncentruje się na szyfrach blokowych, strumieniowych i ich zastosowaniach. Szyfr blokowy można uważać za nowoczesną wersję szyfru polialfabetycznego Albertiego. Służy on (szyfr blokowy) do przekształcenia – przy pomocy klucza – bloku tekstu jawnego w szyfrogram o tej samej długości. Tekst jawny jest zwykle dłuższy niż jeden blok, potrzebne są więc sposoby dzielenia tekstu na pojedyncze bloki i dalszego z nimi postępowania. Metody te są rozmaite – zapewniają różne poziomy zabezpieczenia kryptosystemu z różnych punktów widzenia użytkownika systemu – nazywa się je trybami kodowania szyfrów blokowych (zob. CBC, CFB, CTR, ECB, OFB).
Szyfry DES (ang. Data Encryption Standard) oraz AES (ang. Advanced Encryption Standard) są szyframi blokowymi, uznanymi za standardy kryptograficzne przez rząd USA (ostatecznie desygnacja szyfru DES została cofnięta). Mimo że DES nie jest już oficjalnie zalecany, pozostaje nadal w powszechnym użyciu (zwłaszcza jego bezpieczniejsza wersja 3DES) w aplikacjach oprogramowania bankomatów, zapewniania poufności poczty elektronicznej czy zdalnego dostępu do zasobów. Powstało wiele innych szyfrów blokowych o różnych stopniach złożoności i poziomie bezpieczeństwa, wiele z nich zostało jednak złamanych (zob. Kategoria:szyfry blokowe).
W szyfrach strumieniowych, w przeciwieństwie do blokowych, tworzony jest dowolnie długi klucz, który, bit po bicie lub znak po znaku, jest łączony (zwykle operacją XOR) z tekstem jawnym. Tak więc kolejny element szyfrogramu zależy nie tylko od kodowanego w danej chwili elementu tekstu jawnego i odpowiadającego mu klucza, ale również od wyniku wcześniejszych operacji. W języku teorii automatów można powiedzieć, że kolejny element szyfrogramu zależy od stanu maszyny szyfrującej. Stan zmienia się w zależności od klucza, a w niektórych szyfrach również w zależności od szyfrowanego tekstu. Przykładem szyfru strumieniowego jest RC4 (zobacz też hasła w kategorii szyfry strumieniowe).
Bezpieczne funkcje skrótu (lub kryptograficzne funkcje haszujące) to funkcje, których argumentem jest ciąg danych wejściowych (zwykle cała wiadomość), a wynikiem ciąg danych o ustalonej długości. Funkcje te w ogóle nie wymagają kluczy i właściwie nie są to szyfry, ale wzmianka o nich jest konieczna ze względu na ich pewne podobieństwa do szyfrów i w związku z tym analogiczne zastosowania (zob. przykłady: MD5, SHA-1).
Kody uwierzytelniające wiadomości (ang. message authentication code; w skrócie MAC) są nieco podobne, jednak do ich obliczenia używa się tajnego klucza.
Kryptografia asymetryczna
W kryptosystemach symetrycznych zazwyczaj używa się tego samego klucza do szyfrowania i deszyfrowania, chociaż dla pojedynczych wiadomości bądź ich grup mogą być używane różne klucze. Istotną wadą szyfrów symetrycznych są trudności z przekazywaniem kluczy i ich przechowywaniem; w szerszym ujęciu mówi się o trudnościach w zarządzaniu kluczami. W przypadku idealnym każda para komunikujących się stron do przekazania każdej wiadomości powinna użyć innego klucza. W takim wypadku liczba potrzebnych kluczy rośnie z kwadratem liczby uczestników wymiany informacji, a to kolei powoduje, że aby umożliwić wydajną i bezpieczną pracę, szybko pojawia się potrzeba zastosowania złożonych schematów zarządzania kluczami. Konieczność sekretnego przekazania klucza pomiędzy stronami, bez istniejącego wcześniej bezpiecznego kanału komunikacji pomiędzy nimi, również stanowi poważną przeszkodę dla użytkowników systemów kryptograficznych w rzeczywistych zastosowaniach praktycznych.
W przełomowym artykule z 1976 roku, Whitfield Diffie i Martin Hellman zaproponowali ideę kryptografii z kluczem publicznym (nazywaną również szerzej kryptografią z kluczem asymetrycznym), w której używa się dwóch matematycznie związanych ze sobą kluczy. Jeden z nich nazywany jest kluczem publicznym, drugi – prywatnym. System ten został skonstruowany w taki sposób, że obliczenie klucza prywatnego na podstawie klucza publicznego, mimo że możliwe, jest praktycznie niewykonalne. Zamiast tego oba klucze generowane są poufnie jako para. Historyk David Kahn opisał kryptografię z kluczem publicznym jako "najbardziej rewolucyjny pomysł w kryptografii od powstania szyfru polialfabetycznego w okresie Renesansu" (ang. "the most revolutionary new concept in the field since polyalphabetic substitution emerged in the Renaissance").
W kryptografii asymetrycznej klucz publiczny może być swobodnie rozpowszechniany, natomiast odpowiadający mu klucz prywatny musi zostać zachowany w sekrecie. W typowych zastosowaniach klucz publiczny jest używany do szyfrowania informacji, a prywatny do deszyfrowania. Diffie i Hellman pokazali, że użycie systemów z kluczem publicznym jest możliwe przez zastosowanie protokołu uzgadniania kluczy (nazwanego protokołem Diffiego-Hellmana).
W 1978 roku Ronald Rivest, Adi Shamir i Len Adleman wymyślili inny asymetryczny kryptosystem, który od pierwszych liter nazwisk jego twórców został nazwany RSA.
W roku 1997 ujawniono, że kryptografia asymetryczna była znana wcześniej, bo już we wczesnych latach siedemdziesiątych, za sprawą Jamesa H. Ellisa z brytyjskiej agencji wywiadowczej GCHQ, a oba algorytmy: Diffie-Hellmana i RSA, zostały już wcześniej odkryte – przez Malcolma Williamsona (Diffie-Hellman) i Clifforda Cocksa (RSA).
Algorytmy Diffiego-Hellmana i RSA, poza tym, że były pierwszymi opublikowanymi asymetrycznymi szyframi wysokiej jakości, to znalazły się również w szerokim użyciu. Spośród pozostałych szyfrów asymetrycznych można wymienić: szyfr Cramera-Shoupa (ang. Cramer-Shoup cryptosystem), ElGamal czy też szyfry oparte ma krzywych eliptycznych.
Ikonka z kłódką z przeglądarki internetowej Firefox jest umieszczana aby zasygnalizować, że strona została przesłana w postaci zaszyfrowanej SSL lub TLS. Nie jest to jednakże gwarancja bezpieczeństwa; zhackowana przeglądarka może zmylić użytkownika pokazując ikonkę, podczas gdy faktycznie transmisja odbywa się bez zabezpieczeń.
Poza zastosowaniami w dziedzinie szyfrowania wiadomości kryptografia z kluczem publicznym jest używana do wdrożenia podpisu cyfrowego.
Podpis cyfrowy pełni podobne funkcje do zwykłego podpisu. Obie formy powinny być łatwe w użyciu dla właściciela, ale trudne do podrobienia; powinny być na trwałe powiązane z podpisywanym dokumentem w taki sposób, aby każda próba modyfikacji treści dokumentu bądź próba przeniesienia podpisu na inny dokument mogła być łatwo wykryta. Prawidłowo stosowane podpisy: tradycyjny i cyfrowy spełniają te warunki. Zastosowanie podpisu cyfrowego wymaga dwóch algorytmów: jeden służy do podpisywania – sekretny kod właściciela jest użyty do przetwarzania wiadomości (lub jej funkcji skrótu lub obu tych elementów), drugi służy do weryfikacji – za pomocą klucza publicznego sprawdza się, czy podpis pasuje do wiadomości. Za przykład sposobów podpisywania wiadomości mogą służyć algorytmy RSA i DSA. Podpis cyfrowy jest istotnym elementem tak zwanych infrastruktur klucza publicznego oraz bezpieczeństwa sieciowego (wirtualnych sieci prywatnych, protokołów SSL/TLS i innych).
Algorytmy z kluczem publicznym najczęściej bazują na złożoności obliczeniowej "trudnych" problemów (zobacz też: problem NP-trudny) teorii liczb. Na przykład RSA opiera się na trudności rozkładu liczb na czynniki, podczas gdy Diffie-Hellman i DSA mają u podstawy trudności w obliczaniu logarytmu dyskretnego. Nowsze algorytmy kryptografii krzywych eliptycznych bazują na problemach teorii liczb związanych z krzywymi eliptycznymi. W związku z powyższym większość algorytmów kryptografii asymetrycznej wymaga wielu złożonych operacji arytmetyki modularnej, takich jak mnożenie i potęgowanie, które angażują większą ilość obliczeń niż algorytmy używane w szyfrach blokowych. W rezultacie dla zoptymalizowania stosuje się często systemy mieszane, w których do kodowania wiadomości używa się szybkiego szyfru symetrycznego, a jedynie klucz jest przesyłany jako wiadomość zaszyfrowana algorytmem asymetrycznym. Podobnie w rozwiązaniach podpisów cyfrowych – algorytmami asymetrycznymi szyfruje się jedynie skrót dokumentu.
Kryptoanaliza
Celem kryptoanalizy jest odnalezienie słabości systemu kryptograficznego, a tym samym umożliwienie jego złamania lub obejścia. Działania kryptoanalityka mogą być albo wrogie, albo przeciwnie – mogą być podejmowane w celu znalezienia słabych punktów systemu i podniesienia jego odporności na ataki. Łamiąc szyfr kryptoanalityk zazwyczaj zna algorytm kryptograficzny. Nawet jeśli algorytm ten jest tajny to odtworzenie go jest jedynie kwestią czasu. Teoretycznie każdy szyfr można złamać, w praktyce jednak zależy to głównie od mocy obliczeniowej użytej do złamania i czasu. Zazwyczaj uznaje się szyfry za bezpieczne jeśli nie da się ich złamać w stosunkowo długim czasie. A ponieważ moc obliczeniowa komputerów ciągle rośnie to w celu utrzymywania należytego poziomu bezpieczeństwa szyfrów tworzy się coraz doskonalsze (wymagające coraz dłuższego czasu na ich złamanie) algorytmy kryptograficzne. We współczesnej praktyce algorytmy i protokoły kryptograficzne muszą być dokładnie zbadane i przetestowane, aby zapewnić bezpieczeństwo systemu (przynajmniej zgodnie z wyraźnymi i – należy mieć nadzieję – rozsądnymi założeniami).
Powszechny sąd, iż każdy system szyfrowania może być złamany, jest mylący. Claude Shannon udowodnił, że w przypadku systemu szyfrowania z kluczem jednorazowym (one-time pad) nie jest to możliwe, o ile klucz jest rzeczywiście losowy, zawsze używany tylko jeden raz, utrzymany w sekrecie, a jego długość jest nie mniejsza niż długość wiadomości. Większość pozostałych szyfrów może zostać złamana atakiem brute force, ale nakład potrzebnej do tego pracy – w stosunku do wysiłku włożonego w cały proces szyfrowania – może rosnąć wykładniczo wraz ze wzrostem długości klucza. W przypadku takich szyfrów wystarczające bezpieczeństwo mogłoby zostać osiągnięte, jeśliby udowodniono, że nakład pracy potrzebny do złamania szyfru jest poza zasięgiem potencjalnego przeciwnika lub znacznie przekracza wartość chronionych szyfrem tajemnic. Należałoby więc pokazać, że nie istnieje efektywny, tj. będący przeciwieństwem zasobo- i czasochłonnej metody brute force, sposób złamania szyfru. Jak do tej pory jednak takich dowodów nie ma, co oznacza, że teoretycznie jedynym stuprocentowo bezpiecznym szyfrem jest one-time pad.
Istnieje wiele różnych ataków kryptologicznych i mogą one być sklasyfikowane na kilka sposobów. Według powszechnie przyjętego sposobu podziału, dzieli się je na podstawie wiedzy przeciwnika i jego możliwości działania. W ataku typu ciphertext-only (atak ze znanym szyfrogramem) kryptoanalityk ma do dyspozycji jedynie szyfrogram (dobre współczesne szyfry są odporne na tego rodzaju ataki). W ataku zwanym known-plaintext (atak ze znanym tekstem jawnym) kryptoanalityk ma do dyspozycji tekst jawny i odpowiadający mu tekst zaszyfrowany (może to być jedna lub wiele takich par). W ataku typu chosen-plaintext (atak z wybranym tekstem jawnym), kryptoanalityk może wybrać dowolny tekst jawny i poznać (także wielokrotnie) odpowiadający mu szyfrogram; w taki sposób postępowano na przykład w Bletchley Park w czasie drugiej wojny światowej prowokując przeciwnika do przesyłania kryptogramów o znanej treści (zob. gardening). Jeszcze jednym atakiem jest chosen-ciphertext (atak z wybranym szyfrogramem), w przypadku którego kryptoanalityk może wybrać szyfrogram i zdobyć odpowiadający mu tekst jawny. Równie istotnym aspektem są błędy w użyciu lub projekcie jednego z protokołów systemu kryptograficznego; przykładem może tu być złamanie Enigmy (zobacz też Biuro Szyfrów).
Kryptoanaliza szyfrów symetrycznych zazwyczaj wymaga bardziej wyrafinowanego podejścia niż prymitywny atak siłowy. Przykładowo dla szyfru DES metoda brute force wymaga znanego tekstu jawnego i 255 prób odkodowania, czyli około połowy wszystkich możliwych kluczy, aby szansa znalezienia poszukiwanego klucza była większa od jednej drugiej. Ten sam efekt może zostać osiągnięty przy użyciu kryptoanalizy liniowej oraz 243 znanych tekstów jawnych i około 243 operacji, co jest znaczącym ulepszeniem względem metody brute force.
Algorytmy z kluczem publicznym bazują na trudności obliczeniowej związanej z różnymi problemami. Szeroko wykorzystywanym jest problem faktoryzacji (algorytm RSA bazuje między innymi na trudności rozwiązywania tego problemu) oraz problem logarytmu dyskretnego (na nim bazuje szyfr ElGamal). Duża część kryptoanalizy szyfrów z kluczem publicznym koncentruje się na próbie znalezienia efektywnych algorytmów do rozwiązania wyżej wymienionych problemów obliczeniowych. Przykładowo, najlepsze znane algorytmy służące do rozwiązania problemu logarytmu dyskretnego w wersji opartej na krzywych eliptycznych są bardziej czasochłonne niż najlepsze znane algorytmy faktoryzacji – przynajmniej dla problemów o takiej samej, w przybliżeniu, skali. Aby zatem system oparty na faktoryzacji był odporny na ataki w stopniu porównywalnym do systemu bazującego na krzywych eliptycznych, należy w tym pierwszym użyć dłuższego klucza; te drugie, w związku z powyższym, zyskują na popularności od czasu ich odkrycia w połowie lat 90. XX wieku.
O ile czysta kryptoanaliza korzysta ze słabości algorytmów szyfrujących, to inne ataki na kryptosystem wykorzystują również słabe strony związane z użyciem rzeczywistych urządzeń (ataki typu side-channel). Przykładowo, jeśli kryptoanalityk ma dostęp do pomiaru czasu potrzebnego na zakodowanie wiadomości, to możliwe jest uzyskanie pewnych informacji, które w inny sposób byłyby trudne do wydobycia (zob. timing attack). Adwersarz może również badać strukturę i długość wiadomości i w ten sposób uzyskać cenne wskazówki (zob. traffic analysis)[21]. Do dyspozycji przeciwnika są oczywiście również i inne środki, takie jak inżynieria społeczna czy inne sposoby pozyskania personelu obsługującego kryptosystem, w tym przekupstwo, wymuszenie, szantaż i szpiegostwo.
Algorytmiczne podstawy kryptografii
Duża część teoretycznych prac w dziedzinie kryptografii dotyczy algorytmicznych podstaw kryptografii – algorytmów mających podstawowe, użyteczne w kryptografii właściwości – i ich związków z innymi problemami kryptograficznymi. Przykładowo: funkcja jednokierunkowa to funkcja, której wartości łatwo obliczyć, trudno natomiast znaleźć wartości funkcji do niej odwrotnej. Nie wiadomo jednak, czy takie funkcje w ogóle istnieją (gdyby istniały, byłoby wiadomo, że klasy problemów obliczeniowych P i NP są różne, a jest to jeden z nierozwiązanych problemów milenijnych). Za pomocą podstawowych elementów takich jak funkcje jednokierunkowe można tworzyć bardziej złożone narzędzia; gdyby istniały funkcje jednokierunkowe, istniałyby również bezpieczne generatory liczb pseudolosowych i bezpieczne funkcje pseudolosowe.
Celowo złożoną funkcjonalność konkretnych rozwiązań użytkowych osiąga się, łącząc powyższe algorytmy z odpowiednimi, różnego rodzaju protokołami. Takie kombinacje dają w efekcie coś, z czym spotykają się poszczególni użytkownicy kryptografii, a mianowicie: kryptosystemy. Ich przykładami są: PGP w różnych wariantach, SSH, SSL/TLS, różnego rodzaju PKI, podpisy cyfrowe.
Do algorytmicznych podstaw kryptografii zalicza się wszystkie algorytmy służące do szyfrowania, permutacje jednokierunkowe (funkcje jednokierunkowe będące jednocześnie permutacjami), funkcje – w tym permutacje – typu trapdoor (funkcje, których wartość jest łatwa do obliczenia, natomiast obliczenie wartości funkcji do nich odwrotnych wymaga (przynajmniej w założeniach) dodatkowej, specjalnej informacji, nazywanej trapdoor (w tłumaczeniu na polski słowo to oznacza wejście w formie klapy, zapadni)].
Protokoły kryptograficzne
W wielu przypadkach mamy do czynienia z koniecznością tajnej wymiany informacji pomiędzy dwiema lub więcej stronami znajdującymi się w różnych miejscach (na przykład w różnych odziałach firmy, w domu, w banku) lub/i w różnym czasie (na przykład wytworzenie kopii zapasowych zawierających poufne dane). Termin protokół kryptograficzny odnosi się do podobnych sytuacji.
Istnieją już protokoły kryptograficzne dla szerokiego spektrum problemów – w tym stosunkowo prostych, takich jak: dowód interaktywny, współdzielenie tajemnic czy dowód z wiedzą zerową – aż do dużo bardziej skomplikowanych, np.: pieniądz elektroniczny i bezpieczne obliczenia wielopodmiotowe.
Jeśli zabezpieczenia dobrego systemu kryptograficznego zawodzą, rzadko okazuje się, że przyczyną była jakość zastosowanego algorytmu. Najczęściej wykorzystywanymi słabościami okazują się: błędy w projektowaniu protokołu (często spowodowane niewystarczającym wyszkoleniem twórców lub stosowaniem nieodpowiednich procedur), błędy w implementacji, błędy związane z przyjęciem mylnych założeń (na przykład o dobrym wyszkoleniu obsługi) lub inne, popełnione przez człowieka. Wiele protokołów kryptograficznych było projektowanych i analizowanych metodami ad hoc; rzadko mają one dowody bezpieczeństwa. Metody formalnego analizowania bezpieczeństwa protokołów bazujące na logice matematycznej (zob. logika BAN), a ostatnio również innym podejściu nazywanym concrete security, są przedmiotem badań naukowych od kilku ostatnich dziesięcioleci. Niestety, otrzymane w ich wyniku narzędzia są niepraktyczne i nie znalazły szerokiego zastosowania w skomplikowanych przypadkach.
Nauka o sposobach zastosowania kryptografii w praktyce jest odrębną dyscypliną wiedzy; zob. cryptographic engineering i inżynieria zabezpieczeń.