Historia



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 nie mające klucza do odszyfrowania, a które mogłyby tę wiadomość przechwycić lub podsłuchać.

Błąd! 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 ze swoimi generałami 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[4]. 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 Vigenere'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.

Błąd! 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 (zob. bezpieczeństwo teleinformatyczne); 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).