Kryptologia

Kryptologia (z gr. κρυπτός kryptos, „ukryty”, i λόγος logos, „rozum”, „słowo”) – dziedzina wiedzy o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym.

Kryptologię dzieli się na:
 kryptografię (z gr. κρυπτός oraz γράφω gráfo „pisać”), czyli gałąź wiedzy o utajnianiu wiadomości
 kryptoanalizę (gr. kryptós oraz analýein – rozluźnić), czyli gałąź wiedzy o przełamywaniu zabezpieczeń oraz o deszyfrowaniu wiadomości przy braku klucza lub innego wymaganego elementu schematu szyfrowania (szyfru).

Kryptologia ma szerokie zastosowanie w społeczeństwach rozwiniętych technicznie; wykorzystuje się ją np. w rozwiązaniach zapewniających bezpieczeństwo kart bankomatowych, haseł komputerowych i handlu elektronicznego.

Jednak za najważniejsze zastosowania kryptologii uznaje się utajnianie informacji w wojskowości i dyplomacji. W tych zastosowaniach używa się najbardziej zaawansowanych funkcji i protokołów kryptograficznych. Zasadą ich implementacji są specjalnie opracowane, unikatowe urządzenia kryptograficzne, które wraz z funkcjami i protokołami poddawane są procedurze certyfikacji przez właściwe instytucje, odpowiedzialne za bezpieczeństwo teleinformatyczne danego państwa (w Polsce Agencję Bezpieczeństwa Wewnętrznego i Służbę Kontrwywiadu Wojskowego).

Terminologia 
Istotnym elementem technik kryptograficznych jest proces zamiany tekstu jawnego w szyfrogram (inaczej kryptogram); proces ten nazywany jest szyfrowaniem, a proces odwrotny, czyli zamiany tekstu zaszyfrowanego na powrót w możliwy do odczytania, deszyfrowaniem.

Przez szyfr rozumiana jest para algorytmów służących do przeprowadzenia obu procesów.
Wraz z algorytmami dodatkowo używa się kluczy, czyli pewnych niezbędnych parametrów, od których zależy wynik obu procesów. Innymi słowy: znajomość algorytmu i szyfrogramu bez dostępu do klucza nie pozwoli na odtworzenie tekstu jawnego.

Kryptografia nie zajmuje się jednak wyłącznie szyfrowaniem i deszyfrowaniem tekstów. Po pierwsze, dane przekazywane są najczęściej w postaci binarnej, co umożliwia również obróbkę takich danych jak dźwięk czy obraz; po drugie, równie ważne jak zapewnianie poufności danych jest ich integralność (niezmienność danych w czasie procesu), uwierzytelnianie (pewność co do ich pochodzenia) oraz niezaprzeczalność (nadawca nie może wyprzeć się faktu, że był nadawcą wiadomości). Ponadto kryptografia zajmuje się takimi zagadnieniami, jak: podpis cyfrowy, głosowanie elektroniczne (e-voting), dowód z wiedzą zerową, współdzielenie tajemnic, obliczenia wielopodmiotowe i inne.

Ważnym terminem używanym w kryptografii jest „kryptosystem”, a więc system obejmujący zastosowane w danym wypadku szyfry, metody generowania kluczy, urządzenia wraz z oprogramowaniem oraz procedury ich użycia. Istotnym aspektem kryptosystemu jest jego bezpieczeństwo – odporność na ataki kryptologiczne.

W języku potocznym słowo „kodowanie” określa wszelkie metody szyfrowania lub ukrywania znaczenia. W kryptografii jednak określenie to ma nieco inne znaczenie. Podstawowa różnica polega na zastosowaniu odmiennych narzędzi podczas zamiany tekstu otwartego na utajniony przy pomocy obu tych sposobów działania; o ile w procesie szyfrowania istotnym jego elementem jest klucz, to kodowanie obywa się bez tego składnika systemu – odbywa się ono przy pomocy książki kodowej – rodzaju słownika wiążącego słowa i wyrażenia języka tekstu jawnego z odpowiadającymi im „słowami” kodu. Następuje zamiana jednostek tekstu jawnego (tzn. znaczących słów lub zdań) na słowa kodowe (np. Atak o świcie zostaje zastąpiony słowem Szarlotka).

Z kodów tego typu w obecnej kryptografii się nie korzysta, z wyjątkiem ich zastosowania jako kryptonimów operacji wojskowych (np. Operacja Overlord czy Akcja „Burza”), ze względu na fakt, że dobrze dobrany szyfr jest zarówno praktyczniejszy, jak i bardziej bezpieczny niż jakikolwiek kod. Ponadto szyfry są lepiej dopasowane do wykorzystania za pomocą sprzętu komputerowego.

Kryptologia i kryptografia 
W sensie ścisłym określenia „kryptografia” i „kryptologia”, jako opisujące pewne dziedziny nauki, mają znaczenie podane we wstępie; kryptografia jest pojęciem węższym. Jednak w praktycznym stosowaniu technik kryptologicznych zwykle używane jest słowo „kryptografia”. Dla przykładu: mówi się o protokołach, systemach, technikach czy zabezpieczeniach kryptograficznych (nie kryptologicznych).
Można więc mówić o drugim znaczeniu słowa „kryptografia”, którym jest praktyczne wykorzystanie technik z dziedziny nauki – kryptologii.

Historia kryptografii i kryptoanalizy 

Do czasów nowożytnych kryptografia była związana wyłącznie z tajnością przekazywanych informacji (tzn. z ich szyfrowaniem) – przekształcaniem wiadomości z formy zrozumiałej w niezrozumiałą i z powrotem – w celu wykluczenia jej odczytania przez osoby niemające klucza do odszyfrowania, a które mogłyby tę wiadomość przechwycić lub podsłuchać.

Najwcześniejsze formy utajniania pisemnych wiadomości – z uwagi na fakt, że większość ludzi i tak nie umiała czytać – wymagały niewiele więcej niż ówczesnego odpowiednika pióra i papieru. Zwiększenie się umiejętności czytania i pisania, szczególnie u przeciwnika, przyczyniło się do powstania rzeczywistej kryptografii.

Szyfry antyczne dzieli się na dwie główne grupy: szyfry przestawieniowe, za pomocą których zmieniano kolejność liter w wiadomości (przykład najprostszego przestawienia – „pomóż mi” staje się „opómż im”) oraz szyfry podstawieniowe, które polegały na zastępowaniu pojedynczych liter lub ich grup, odpowiednio: innymi literami lub ich grupami (np. „natychmiastowy wylot” staje się „obuzdinjvbtupxz xzmpu” w najprostszym podstawieniu za daną literę – następnej litery alfabetu łacińskiego). W prostych wersjach obydwa szyfry oferują niewielki stopień utajnienia przed przeciwnikiem.

Jednym z najwcześniejszych szyfrów podstawieniowych był szyfr Cezara, w którym każda litera tekstu jawnego zastępowana była literą oddaloną o pewną ustaloną liczbę pozycji w alfabecie. Szyfr ten został nazwany na cześć Juliusza Cezara, który używał go (z przesunięciem o 3) do komunikacji podczas kampanii wojskowych; jest on podobny do kodu Excess-3 w Algebrze Boole’a.

Szyfrowanie miało za zadanie zapewnić tajność w komunikacji na przykład pomiędzy szpiegami, dowódcami wojskowymi, dyplomatami; miało też zastosowanie wśród wyznawców religii – wcześni chrześcijanie wykorzystywali kryptografię do ukrycia niektórych aspektów ich pism religijnych w celu uniknięcia oskarżeń, które – gdyby nie zachowali ostrożności – z pewnością by się pojawiły. Sławna liczba 666 (lub w niektórych wczesnych pismach – 616), czyli liczba Bestii z Apokalipsy św. Jana, księgi chrześcijańskiego Nowego Testamentu, uważana jest czasem za zaszyfrowane odniesienie do rzymskiego cesarza Nerona, który prowadził politykę prześladowania chrześcijan. Istnieją również zapisy kilku innych, wcześniejszych szyfrów hebrajskich. Stosowanie kryptografii zalecała też Kamasutra kochankom chcącym się komunikować bez ryzyka wykrycia.

Steganografia, wynaleziona również w starożytności, była rodzajem szyfrowania polegającym na ukryciu – w celu zachowania tajności – samego faktu istnienia przekazu. Wczesnego przykładu dostarcza Herodot, który opisał z własnego doświadczenia ukrycie wiadomości – tatuażu na ogolonej głowie niewolnika – pod nowo wyrosłymi włosami. Wśród bliższych współczesności przykładów steganografii są takie techniki jak atramenty sympatyczne, mikrokropki oraz cyfrowe znaki wodne.

Szyfrogram wygenerowany przy użyciu klasycznego szyfru (i niektórych rodzajów szyfrów nowoczesnych) zawsze niesie ze sobą pewne statystyczne informacje związane z wyjściowym tekstem jawnym, które mogą posłużyć do złamania szyfru. Po odkryciu metod kryptoanalizy statystycznej przez arabskiego uczonego Al-Kindiego w IX wieku n.e. stało się możliwe, z mniejszymi lub większymi trudnościami, złamanie prawie każdego z takich szyfrów przez kogoś, kto ma odpowiednią wiedzę właśnie w dziedzinie odkrytej przez Al-Kindiego.

Sytuacja bezbronności szyfrów wobec kryptoanalizy panowała do momentu opracowania przez Leona Battistę Albertiego szyfrów polialfabetycznych około roku 1467 (choć istnieją też przypuszczenia, że wcześniej odkryli je Arabowie). Jego pomysł polegał na użyciu różnych szyfrów (np. szyfrów podstawieniowych) dla różnych części wiadomości – często innego szyfru dla każdej z osobna litery tekstu jawnego. Od niego wyszła też konstrukcja urządzenia będącego prawdopodobnie pierwszą maszyną do szyfrowania; było to koło, które po części realizowało jego pomysł szyfrowania. W XIX-wiecznym polialfabetycznym szyfrze Vigenère’a do zaszyfrowania wiadomości używa się klucza, który określa w jaki sposób ma być szyfrowany kolejny znak. W połowie XIX wieku Charles Babbage pokazał, że szyfry polialfabetyczne tego typu są partiami podatne na kryptoanalizę statystyczną.

Chociaż kryptoanaliza statystyczna jest techniką potężną i uniwersalną, wielu rzekomych kryptoanalityków nie było świadomych jej istnienia – kodowanie było w praktyce często nadal skuteczne. Złamanie jakiejś wiadomości bez analizy statystycznej wymagało przede wszystkim znajomości samego sposobu użytego do zaszyfrowania, stąd – dla jego zdobycia – popierano w stosunku do strony przeciwnej takie metody jak szpiegostwo, przekupstwo, dokonywanie włamań, nakłanianie do zdrady itp.

Ostatecznie w XIX wieku uznano, że ochrona tajemnicy algorytmu szyfrowania nie jest rozsądna ani praktyczna; odpowiedni schemat krypograficzny (w tym szyfr) powinien pozostać bezpieczny nawet wtedy, gdy przeciwnik zna algorytm szyfrowania. Tajemnica klucza sama w sobie powinna wystarczyć do dobrego zaszyfrowania i przekazania – w razie ataku – poufnej informacji. Inaczej mówiąc: kryptosystem powinien być bezpieczny nawet w przypadku, gdy jego całość – z wyjątkiem klucza – jest publicznie znana. Ta fundamentalna zasada została po raz pierwszy wyrażona wprost w 1883 roku przez Augusta Kerckhoffsa i jest na ogół nazywana zasadą jego imienia. Bardziej otwarcie, choć w nieco innej formie, wyraził ją (prawdopodobnie niezależnie od Kerckhoffsa) Claude Shannon: „nasz wróg zna nasz system” (maksyma Shannona).

Dla ułatwienia szyfrowania wykorzystywano w ciągu wieków różnego rodzaju urządzenia i pomoce. Prawdopodobnie do najwcześniej używanych – w starożytnej Grecji – należały skytale (patrz zdjęcie), stosowane ponoć przez Spartan jako pomoc przy szyfrowaniu przestawieniowym. W średniowieczu wynaleziono inne pomoce, np. matrycę szyfrującą (ang. cipher grille) – używaną do kodowania będącego rodzajem steganografii.

Wraz z wynalezieniem szyfrowania polialfabetycznego pojawiły się bardziej zaawansowane pomoce, takie jak: tarcza szyfrująca samego Albertiego, schemat tabula recta Johannesa Trithemiusa czy walec szyfrujący Thomasa Jeffersona (wynaleziony ponownie przez Bazeriesa około roku 1900).  W początkach XX wieku wynaleziono kilkanaście mechanicznych urządzeń szyfrująco-deszyfrujących (i wiele opatentowano). Były wśród nich wirnikowe maszyny szyfrujące, z najsłynniejszą Enigmą używaną przez Niemcy podczas II wojny światowej. Szyfrowanie zastosowane dzięki tym lepszej jakości modelom spowodowało znaczny wzrost trudności analiz kryptoanalitycznych po I wojnie światowej.

Odkrycia, jakie miały miejsce po II wojnie światowej w zakresie elektroniki i wynalezienie cyfrowych maszyn liczących, umożliwiły wykorzystanie szyfrów bardziej skomplikowanych. Ponadto w przeciwieństwie do klasycznych szyfrów (za pomocą których szyfrowano jedynie tekst pisany w języku naturalnym, co w wielu wypadkach pozwalało stosować cechy szyfrowanego języka do kryptoanalizy), użycie komputerów umożliwiło szyfrowanie wszelkich danych wyrażonych w postaci binarnej. Wiele szyfrów komputerowych można opisać poprzez operacje na sekwencjach bitów (czasem ich grupach lub blokach), w przeciwieństwie do metod klasycznych i mechanicznych, które na ogół operują bezpośrednio na tradycyjnych znakach (np. literach i cyfrach).

Komputery okazały się także pomocne w kryptoanalizie, co do pewnego stopnia zrekompensowało zwiększenie skomplikowania szyfrów – tylko do pewnego stopnia, jako że dobre nowoczesne algorytmy szyfrujące zdecydowanie wyprzedzają kryptoanalizę; normalna jest sytuacja, w której użycie skutecznego szyfru jest wydajne (np. szybkie i wymagające niewielkich zasobów), podczas gdy próba złamania tego szyfru wymaga nakładów o wiele rzędów większych – czyni to kryptoanalizę tak nieefektywną i niepraktyczną, że w takich wypadkach faktycznie niemożliwą.

Otwarte rozległe badania akademickie mają miejsce w dziedzinie kryptografii od stosunkowo niedawna; rozpoczęły się w połowie lat 70. XX wieku wraz z publikacją przez ówczesny NBS (odpowiednik dzisiejszego NIST) specyfikacji algorytmu DES (Data Encryption Standard), a także ukazaniem się pracy Diffiego-Hellmana oraz publicznym przedstawieniem algorytmu RSA. Od tego czasu kryptografia stała się narzędziem powszechnie używanym w komunikacji, sieciach komputerowych i ogólnie – bezpieczeństwie komputerowym.

Poziom bezpieczeństwa wielu współczesnych technik kryptograficznych bazuje na złożoności obliczeniowej niektórych działań matematycznych, jak rozkład na czynniki czy logarytm dyskretny. W wielu przypadkach istnieją dowody, że dane techniki kryptograficzne są bezpieczne, jeśli pewien problem obliczeniowy nie ma efektywnego rozwiązania. Z wyjątkiem one-time pad dowody te są warunkowe, a przez to nieostateczne, ale w obecnym stanie wiedzy są dowodami najlepszymi dostępnymi dla algorytmów i protokołów kryptograficznych.

Twórcy algorytmów i systemów kryptograficznych nie dość, że powinni znać dotychczasowe osiągnięcia i historię kryptografii, to w swoich projektach muszą również brać pod uwagę możliwy przyszły rozwój wypadków. Przykładowo – ciągły wzrost mocy obliczeniowej komputerów zwiększa długość klucza, przy której atak typu brute-force może się powieść. Przedmiotem troski niektórych kryptografów są ewentualne efekty potencjalnego rozwoju obliczeń przy pomocy komputerów kwantowych, a zapowiedzi dotyczące nieuchronnego wdrożenia w niewielkim stopniu urządzeń tego typu czynią te głosy wyraźnie słyszalnymi.

W zasadzie do wczesnych lat XX wieku kryptografia skupiała się na wzorcach językowych. Od tego czasu główny nacisk w kryptografii przeniósł się w kierunku nauk ścisłych – kryptografowie korzystają obecnie w dużym stopniu z matematyki, w tym różnych aspektów teorii informacji, teorii złożoności obliczeniowej, statystyki, kombinatoryki, algebry abstrakcyjnej i teorii liczb.

Kryptografia jest także dziedziną inżynierii, ale dość nietypową, gdyż musi zmagać się z czynnym inteligentnym wrogim oporem; większość innych rodzajów inżynierii ma do czynienia jedynie z neutralnymi siłami natury. Prowadzone są również badania mające na celu rozwiązanie problemów kryptograficznych z wykorzystaniem fizyki kwantowej (zob. komputer kwantowy i kryptografia kwantowa).

Na marginesie można dodać, że klasyczne szyfry wciąż są popularne, chyba najbardziej w dziedzinie rozrywek umysłowych (zob. puzzle i szyfrogram).

Współczesna kryptologia 
Współcześnie wyróżnia się dwa główne nurty kryptografii: kryptografię symetryczną i asymetryczną.

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. 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 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 klucza publicznego 

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 Szamir 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 klucza publicznego 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 na krzywych eliptycznych.

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 prawie  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ż 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).

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 oddziałach firmy, w domu, w banku) lub 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.

Uregulowania prawne dotyczące kryptografii

Zakazy 
Kryptografia od dawna pozostawała w kręgu zainteresowań służb wywiadowczych i policyjnych. Ze względu na fakt, że jest ona pomocna w utrzymywaniu prywatności, a ewentualne prawne jej ograniczenia wiążą się z umniejszeniem możliwości zachowania prywatności, kryptografia przyciąga też uwagę obrońców praw człowieka.
W związku z powyższym, można znaleźć we współczesnej historii kontrowersyjne przepisy prawne dotyczące kryptografii, szczególnie od momentu pojawienia się niedrogich komputerów, dzięki którym dostęp do kryptografii na zaawansowanym poziomie stał się powszechny.

W niektórych państwach nawet wewnątrzkrajowe użycie technik kryptograficznych podlega ograniczeniom. We Francji było ono w znacznym stopniu ograniczone do 1999 roku; w Chinach w dalszym ciągu wymagana jest licencja. Wśród krajów z najbardziej restrykcyjnymi uregulowaniami są: Białoruś, Kazachstan, Mongolia, Pakistan, Rosja, Singapur, Tunezja, Wenezuela i Wietnam.

W Stanach Zjednoczonych kryptografia w zastosowaniach wewnętrznych jest legalna, ale wokół uregulowań prawnych wiążących się z kryptografią było wiele konfliktów. Jedną ze szczególnie istotnych kwestii był eksport kryptografii, oprogramowania i urządzeń kryptograficznych. Ze względu na znaczenie kryptoanalizy podczas II wojny światowej i prognoz, że kryptografia pozostanie istotna dla bezpieczeństwa narodowego, wiele państw zachodnich w pewnym momencie ustanowiło rygorystyczne rozwiązania prawne związane z eksportem technologii kryptograficznych.
W Stanach Zjednoczonych po II wojnie światowej za nielegalne uznawane były sprzedaż lub rozpowszechnianie technologii szyfrujących poza granice państwa; szyfrowanie było traktowane jako uzbrojenie, tak jak czołgi czy broń jądrowa.

Przed nastaniem ery komputerów osobistych i Internetu było to rozwiązanie zupełnie nieproblematyczne; dla większości użytkowników różnica między dobrą i złą kryptografią jest niedostrzegalna, a w owym czasie dodatkowo zdecydowana większość ogólnie dostępnych technik kryptograficznych była powolna i podatna na błędy. Jednakże wraz z rozbudową sieci Internet i upowszechnieniem komputerów, techniki szyfrujące wysokiej jakości stały się dobrze znane na całym świecie. W rezultacie postępu technologicznego, kontrola eksportu zaczęła być postrzegana jako bariera dla handlu i nauki.

Ograniczenia eksportu 
W latach 90. XX wieku w Stanach Zjednoczonych doszło do kilku prób sił odnośnie do regulacji prawnych dotyczących kryptografii. Jedna z nich miała miejsce w związku z programem szyfrującym PGP (Pretty Good Privacy) Philipa Zimmermanna. Program ten, razem z kodem źródłowym, został wydany w USA i w czerwcu 1991 roku trafił do Internetu. Wskutek skargi złożonej przez RSA Security (występujące wówczas pod nazwą RSA Data Security Inc lub RSADSI), w sprawie Zimmermanna toczyło się kilkuletnie dochodzenie służb celnych i FBI; nie wniesiono jednak żadnego oskarżenia.

Podobnie Daniel J. Bernstein, wówczas student uniwersytetu w Berkeley, na podstawie prawa do wolności wypowiedzi, wytoczył sprawę amerykańskiemu rządowi, podważając kilka przepisów w ograniczeniach w stosowaniu kryptografii; sprawa sądowa z 1995 roku – Bernstein przeciwko USA – zakończyła się w roku 1999 orzeczeniem sądu stwierdzającym, że wydrukowanie kodu źródłowego algorytmów i systemów kryptograficznych jest chronione prawem do wolności słowa zawartym w konstytucji USA.

W 1996 roku trzydzieści dziewięć krajów, w tym Polska, podpisało porozumienie Wassenaar (ang. The Wassenaar Arrangement on Export Controls for Conventional Arms and Dual-Use Goods and Technologies) – traktat o eksporcie uzbrojenia i technologii podwójnego zastosowania (czyli technologii mogących mieć zastosowanie cywilne i wojskowe), w tym kryptografii. Uzgodniono, że technologie szyfrowania oparte na krótkich kluczach (56-bitowych dla szyfrów symetrycznych i 512-bitowych dla RSA) nie podlegają ograniczeniom eksportowym.

Eksport kryptografii ze Stanów Zjednoczonych, w konsekwencji znacznego złagodzenia prawa w roku 2000, jest obecnie znacznie mniej restrykcyjnie regulowany niż w przeszłości; nie ma już wielu obostrzeń w zakresie długości kluczy stosowanych w popularnym oprogramowaniu importowanym z USA.

Dzięki temu, że prawie wszystkie komputery osobiste podłączone do Internetu zawierają oparte na amerykańskich kodach źródłowych przeglądarki jak Mozilla Firefox czy Microsoft Internet Explorer, prawie każdy użytkownik Internetu ma dostęp do wysokiej jakości kryptografii w swojej przeglądarce, np. w postaci dostatecznie długich kluczy, ochrony przed szkodliwym oprogramowaniem, zastosowania bezpiecznych protokołów; przykładami mogą być protokoły Transport Layer Security i SSL. Podobnie klienty e-mail, jak Mozilla Thunderbird czy Microsoft Outlook, mogą łączyć się z serwerami poczty IMAP i POP poprzez TLS, a także wysyłać i przyjmować e-maile zaszyfrowane z użyciem S/MIME.

Wielu użytkowników Internetu nie jest nawet świadomych zastosowania tak zaawansowanych kryptosystemów w programach codziennego użytku. Wymienione przeglądarki i programy pocztowe są tak wszechobecne, że nawet władza, która zmierzałaby do regulacji osobistego używania kryptografii, raczej nie uzna tego za praktyczne, a nawet gdyby takie prawo miało obowiązywać, jego skuteczna egzekucja byłaby często niemożliwa.

Rola NSA 
Innym kontrowersyjnym zagadnieniem związanym z kryptografią w Stanach Zjednoczonych jest wpływ NSA (National Security Agency) – amerykańskiej Agencji Bezpieczeństwa Narodowego na zasady szyfrowania i jego rozwój.

NSA była zaangażowana w rozwój szyfru DES podczas jego konstruowania w IBM i rozważania przez NBS jako możliwy rządowy standard w kryptografii.
DES został tak zaprojektowany, aby oprzeć się kryptoanalizie różnicowej, skutecznej ogólnej technice kryptoanalitycznej znanej agencji NSA i firmie IBM, a która została przedstawiona do wiadomości publicznej dopiero wtedy, gdy została odkryta na nowo w latach 80. XX wieku. Według Stevena Levy’ego, IBM niezależnie od NSA wynalazł kryptoanalizę różnicową, ale zachował ją w tajemnicy na wniosek NSA. Technika ta stała się publicznie znana dopiero wtedy, kiedy E. Biham i A. Shamir odkryli ją kilka lat później. Cała sprawa ilustruje trudność oceny, jakie zasoby i wiedzę może posiadać oponent chcący przeprowadzić atak.

Kolejnym przykładem uwikłania NSA była w 1993 roku sprawa układu Clipper – układu scalonego mającego być częścią przedsięwzięcia zmierzającego do kontrolowania kryptografii – rządowego projektu o nazwie Capstone. Clipper był szeroko krytykowany przez kryptologów z dwóch przyczyn: użyty szyfr był tajny (algorytm o nazwie Skipjack został odtajniony dopiero w roku 1998, długo po wygaśnięciu projektu), co prowokowało obawy, że NSA celowo uczynił go słabym, aby wspomóc działania wywiadowcze.

Cały projekt Capstone był także krytykowany ponieważ łamał kryptograficzną zasadę Kerckhoffsa, która mówi, że kryptosystem powinien być bezpieczny, nawet jeśli szczegóły systemu, oprócz klucza, są publicznie znane – klucz używany przez wspomniany układ Clipper miał być deponowany przez administrację państwową i używany przez organy porządkowe np. do podsłuchu telefonicznego.

Digital Rights Management 

Kryptografia stanowi podstawę cyfrowych systemów zarządzania uprawnieniami (DRM) – zespołu technik służących technologicznej kontroli użycia materiałów licencjonowanych – technik stosowanych na żądanie posiadaczy praw autorskich, a wdrażanych na szeroką skalę.

W 1998 prezydent Bill Clinton podpisał Digital Millennium Copyright Act (DMCA), ustawę penalizującą wytwarzanie, rozpowszechnianie i używanie niektórych technik i technologii kryptograficznych (znanych w chwili podpisywania ustawy, ewentualnie wynalezionych w przyszłości), szczególnie takich, które mogą być użyte w celu ominięcia schematów DRM (nawet gdy nie są naruszane prawa autorskie).

Prawo to od chwili jego uchwalenia miało w sobie potencjał bardzo poważnego wpływu na społeczność szukających nowych rozwiązań kryptologów, jako że w przypadku dowolnego odkrycia kryptoanalitycznego można podnieść argument, że narusza ono – lub może naruszać – DMCA. FBI i Departament Sprawiedliwości postanowiły nie egzekwować prawa aż tak rygorystycznie, jak obawiali się niektórzy, jednak prawo samo w sobie pozostaje kontrowersyjne.

Jeden z powszechnie szanowanych badaczy, Niels Ferguson, publicznie ujawnił, że nie zastosuje niektórych wyników badań w konstrukcji procesorów Intel z obawy przed oskarżeniem na mocy aktu DMCA. Alan Cox (przez długi czas człowiek numer dwa, jeśli chodzi o rozwój jądra systemu Linux) i profesor Edward Felten (wraz z częścią swoich studentów z Uniwersytetu w Princeton) spotkali się z problemami związanymi z restrykcjami DMCA.

Dymitr Sklarow został podczas wizyty w Stanach Zjednoczonych aresztowany i osadzony na kilka miesięcy w więzieniu za naruszenie DMCA, które rzekomo miało miejsce w Rosji, gdzie wykonywana przez niego praca była, także w czasie jego aresztowania, legalna.

Podobne przepisy przyjęto po pewnym czasie w niektórych innych państwach – na przykład w 2001 roku w krajach Unii Europejskiej, pod postacią EU Copyright Directive.

W 2007 odkryto i ujawniono w Internecie klucze kryptograficzne, za pomocą których kodowane były materiały na DVD i HD DVD. W przypadkach obu systemów zapisu organizacja MPAA, walcząca w interesie amerykańskich producentów filmowych, wielokrotnie informowała o naruszaniu DMCA, co spotkało się masowym sprzeciwem internautów, którzy powoływali się na prawo do wolności wypowiedzi i zasadę fair use.

We wrześniu 2010 ujawniono w Internecie główny klucz HDCP umożliwiający nielegalne kopiowanie materiałów. Twórca klucza – Intel potwierdził autentyczność klucza.

Zobacz też 

 Chaos Computer Club
 materiały kryptograficzne

Przypisy

Linki zewnętrzne 
  Cryptology , Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].

 
Prywatność