Kryptografia
Kryptografia lub kryptologia (ze starożytnej greki: „ukryty, tajny”; i odpowiednio „pisać” lub „studiować”[1]) to praktyka i badanie technik bezpiecznej komunikacji w obecności osób trzecich zwanych przeciwnikami[2]. Mówiąc bardziej ogólnie, kryptografia polega na konstruowaniu i analizowaniu protokołów, które uniemożliwiają osobom trzecim lub opinii publicznej odczytywanie prywatnych wiadomości;[3] różne aspekty bezpieczeństwa informacji, takie jak poufność danych, integralność danych, uwierzytelnianie i niezaprzeczalność[4], mają kluczowe znaczenie dla nowoczesnej kryptografii. Nowoczesna kryptografia istnieje na przecięciu dyscyplin matematyki, informatyki, inżynierii elektrycznej, nauki o komunikacji i fizyki. Zastosowania kryptografii obejmują handel elektroniczny, karty płatnicze oparte na chipach, waluty cyfrowe, hasła komputerowe i komunikację wojskową.
Kryptografia przed erą nowoczesności była w rzeczywistości synonimem szyfrowania, konwersji informacji ze stanu czytelnego do pozornego nonsensu. Twórca zaszyfrowanej wiadomości udostępnia technikę dekodowania tylko zamierzonym odbiorcom, aby uniemożliwić dostęp przeciwnikom. W literaturze kryptograficznej często używa się imion Alice („A”) dla nadawcy, Bob („B”) dla zamierzonego odbiorcy i Eve („podsłuchiwacz”) dla przeciwnika[5]. Od czasu opracowania wirnikowych maszyn szyfrujących w czasie I wojny światowej i pojawienia się komputerów w czasie II wojny światowej, metody stosowane w kryptologii stały się coraz bardziej złożone, a jej zastosowanie coraz bardziej powszechne.
Nowoczesna kryptografia opiera się w dużej mierze na teorii matematycznej i praktyce informatycznej; algorytmy kryptograficzne są projektowane w oparciu o założenia dotyczące twardości obliczeniowej, dzięki czemu takie algorytmy są trudne do złamania w praktyce przez dowolnego przeciwnika. Teoretycznie możliwe jest złamanie takiego systemu, ale jest to niewykonalne przy użyciu jakichkolwiek znanych praktycznych środków. Schematy te są zatem określane jako bezpieczne obliczeniowo; postępy teoretyczne, np. ulepszenia algorytmów faktoryzacji liczb całkowitych, oraz szybsza technologia obliczeniowa wymagają ciągłego dostosowywania tych rozwiązań. Istnieją teoretycznie bezpieczne schematy informacyjne, których nie można złamać nawet przy nieograniczonej mocy obliczeniowej – przykładem jest jednorazowa podkładka – ale schematy te są trudniejsze do zastosowania w praktyce niż najlepsze teoretycznie łamliwe, ale bezpieczne obliczeniowo mechanizmy.
Rozwój technologii kryptograficznej wywołał szereg kwestii prawnych w erze informacji. Potencjał kryptografii do wykorzystania jako narzędzie szpiegostwa i podburzania doprowadził wiele rządów do sklasyfikowania jej jako broni i ograniczenia lub nawet zakazania jej używania i eksportu.[6] W niektórych jurysdykcjach, w których korzystanie z kryptografii jest legalne, przepisy zezwalają śledczym na zmuszenie do ujawnienia kluczy szyfrowania dokumentów istotnych dla dochodzenia.[7][8] Kryptografia odgrywa również ważną rolę w zarządzaniu prawami cyfrowymi i naruszaniu praw autorskich do mediów cyfrowych.[9]
Terminologia
Pierwsze użycie terminu kryptograf (w przeciwieństwie do kryptogramu) datuje się na XIX wiek – wywodzi się z powieści The Gold-Bug autorstwa Edgara Allana Poe.[10]
Do czasów współczesnych kryptografia odnosiła się niemal wyłącznie do szyfrowania, które jest procesem przekształcania zwykłych informacji (zwanych zwykłym tekstem) w niezrozumiałą formę (zwaną szyfrogramem).[11] Deszyfrowanie jest procesem odwrotnym, innymi słowy, przejściem od niezrozumiałego szyfrogramu z powrotem do tekstu jawnego. Szyfr (lub cypher) to para algorytmów, które tworzą szyfrowanie i odwrotne deszyfrowanie. Szczegółowe działanie szyfru jest kontrolowane zarówno przez algorytm, jak i w każdym przypadku przez „klucz”. Klucz jest tajemnicą (najlepiej znaną tylko osobom komunikującym się), zwykle krótkim ciągiem znaków, który jest potrzebny do odszyfrowania szyfrogramu. Formalnie „kryptosystem” jest uporządkowaną listą elementów skończonych możliwych tekstów jawnych, skończonych możliwych szyfrogramów, skończonych możliwych kluczy oraz algorytmów szyfrowania i deszyfrowania, które odpowiadają każdemu kluczowi. Klucze są ważne zarówno formalnie, jak i w praktyce, ponieważ szyfry bez zmiennych kluczy mogą być trywialnie złamane przy użyciu jedynie wiedzy o zastosowanym szyfrze, a zatem są bezużyteczne (lub nawet przynoszą efekt przeciwny do zamierzonego) dla większości celów.
W przeszłości szyfry były często używane bezpośrednio do szyfrowania lub deszyfrowania bez dodatkowych procedur, takich jak uwierzytelnianie lub sprawdzanie integralności. Istnieją dwa rodzaje kryptosystemów: symetryczne i asymetryczne. W systemach symetrycznych ten sam klucz (klucz tajny) jest używany do szyfrowania i odszyfrowywania wiadomości. Manipulowanie danymi w systemach symetrycznych jest szybsze niż w systemach asymetrycznych, ponieważ zazwyczaj używają one krótszych kluczy. Systemy asymetryczne wykorzystują klucz publiczny do szyfrowania wiadomości i klucz prywatny do jej odszyfrowania. Wykorzystanie systemów asymetrycznych zwiększa bezpieczeństwo komunikacji.[12] Przykładami systemów asymetrycznych są RSA (Rivest-Shamir-Adleman) i ECC (Elliptic Curve Cryptography). Modele symetryczne obejmują powszechnie stosowany AES (Advanced Encryption Standard), który zastąpił starszy DES (Data Encryption Standard).[13]
W potocznym użyciu termin „kod” jest często używany do określenia dowolnej metody szyfrowania lub ukrywania znaczenia. Jednak w kryptografii kod ma bardziej specyficzne znaczenie. Oznacza to zastąpienie jednostki tekstu jawnego (tj. znaczącego słowa lub frazy) słowem kodowym (na przykład „wallaby” zastępuje „atak o świcie”).
Kryptoanaliza to termin używany do badania metod uzyskiwania znaczenia zaszyfrowanych informacji bez dostępu do klucza zwykle wymaganego do tego celu; tj. jest to badanie sposobu łamania algorytmów szyfrowania lub ich implementacji.
Niektórzy używają terminów kryptografia i kryptologia zamiennie w języku angielskim, podczas gdy inni (w tym ogólnie praktyka wojskowa USA) używają kryptografii, aby odnieść się konkretnie do wykorzystania i praktyki technik kryptograficznych, a kryptologii, aby odnieść się do połączonego badania kryptografii i kryptoanalizy.[14][15] Angielski jest bardziej elastyczny niż kilka innych języków, w których kryptologia (wykonywana przez kryptologów) jest zawsze używana w drugim z powyższych znaczeń.
RFC 2828 zaleca, aby steganografia była czasami włączana do kryptologii.[16]
Badanie cech języków, które mają pewne zastosowanie w kryptografii lub kryptologii (np. dane częstotliwości, kombinacje liter, uniwersalne wzorce itp.) nazywane jest kryptolingwistyką.
Historia kryptografii
Przed erą nowożytną kryptografia koncentrowała się na poufności wiadomości (tj. szyfrowaniu) – przekształcaniu wiadomości ze zrozumiałej formy w niezrozumiałą i z powrotem na drugim końcu, czyniąc ją nieczytelną dla przechwytujących lub podsłuchujących bez tajnej wiedzy (a mianowicie klucza potrzebnego do odszyfrowania tej wiadomości). Szyfrowanie było próbą zapewnienia tajemnicy w komunikacji, na przykład szpiegów, przywódców wojskowych i dyplomatów. W ostatnich dziesięcioleciach dziedzina ta rozszerzyła się poza kwestie poufności, obejmując między innymi techniki sprawdzania integralności wiadomości, uwierzytelniania tożsamości nadawcy/odbiorcy, podpisów cyfrowych, interaktywnych dowodów i bezpiecznych obliczeń.
Era komputerów
Przed początkiem XX wieku kryptografia zajmowała się głównie wzorcami językowymi i leksykograficznymi. Od tego czasu nacisk został przesunięty, a kryptografia obecnie szeroko wykorzystuje matematykę, w tym aspekty teorii informacji, złożoności obliczeniowej, statystyki, kombinatoryki, algebry abstrakcyjnej, teorii liczb i ogólnie matematyki skończonej. Kryptografia jest również gałęzią inżynierii, ale nietypową, ponieważ zajmuje się aktywną, inteligentną i złośliwą opozycją (patrz inżynieria kryptograficzna i inżynieria bezpieczeństwa); inne rodzaje inżynierii (np. inżynieria lądowa lub chemiczna) muszą zajmować się tylko neutralnymi siłami naturalnymi. Prowadzone są również aktywne badania nad związkiem między problemami kryptograficznymi a fizyką kwantową (patrz kryptografia kwantowa i komputer kwantowy).
Tak jak rozwój komputerów cyfrowych i elektroniki pomógł w kryptoanalizie, umożliwił znacznie bardziej złożone szyfry. Co więcej, komputery pozwalały na szyfrowanie dowolnego rodzaju danych reprezentowanych w dowolnym formacie binarnym, w przeciwieństwie do klasycznych szyfrów, które szyfrowały tylko teksty pisane; było to nowe i znaczące. Wykorzystanie komputerów wyparło zatem kryptografię językową, zarówno w zakresie projektowania szyfrów, jak i kryptoanalizy. Wiele szyfrów komputerowych można scharakteryzować poprzez ich działanie na sekwencjach bitów binarnych (czasami w grupach lub blokach), w przeciwieństwie do klasycznych i mechanicznych schematów, które zazwyczaj bezpośrednio manipulują tradycyjnymi znakami (tj. literami i cyframi). Jednak komputery wspomogły również kryptoanalizę, co w pewnym stopniu zrekompensowało zwiększoną złożoność szyfrów. Niemniej jednak, dobre współczesne szyfry wyprzedziły kryptoanalizę; zazwyczaj jest tak, że użycie wysokiej jakości szyfru jest bardzo wydajne (tj. szybkie i wymagające niewielu zasobów, takich jak pamięć lub możliwości procesora), podczas gdy złamanie go wymaga wysiłku o wiele rzędów wielkości większego i znacznie większego niż wymagany dla jakiegokolwiek klasycznego szyfru, co czyni kryptoanalizę tak nieefektywną i niepraktyczną, że w rzeczywistości niemożliwą.
Nadejście nowoczesnej kryptografii
Kryptoanaliza nowych urządzeń mechanicznych okazała się zarówno trudna, jak i pracochłonna. W Wielkiej Brytanii wysiłki kryptoanalityczne w Bletchley Park podczas II wojny światowej pobudziły rozwój bardziej wydajnych środków do wykonywania powtarzalnych zadań. Kulminacją tych prac było opracowanie Colossusa, pierwszego na świecie w pełni elektronicznego, cyfrowego, programowalnego komputera, który pomógł w odszyfrowaniu szyfrów wygenerowanych przez maszynę Lorenz SZ40/42 niemieckiej armii.
Szeroko zakrojone otwarte badania akademickie nad kryptografią rozpoczęły się stosunkowo niedawno, bo dopiero w połowie lat 70. ubiegłego wieku. W ostatnich czasach pracownicy IBM zaprojektowali algorytm, który stał się federalnym (tj. amerykańskim) standardem szyfrowania danych; Whitfield Diffie i Martin Hellman opublikowali swój algorytm uzgadniania klucza;[30] i algorytm RSA zostały opublikowane w kolumnie Martina Gardnera w Scientific American. Po ich pracy w 1976 roku popularne stało się rozważanie systemów kryptograficznych opartych na problemach matematycznych, które są łatwe do określenia, ale okazały się trudne do rozwiązania.[31] Od tego czasu kryptografia stała się szeroko stosowanym narzędziem w komunikacji, sieciach komputerowych i ogólnie w bezpieczeństwie komputerowym. Niektóre nowoczesne techniki kryptograficzne mogą utrzymać swoje klucze w tajemnicy tylko wtedy, gdy pewne problemy matematyczne są niewykonalne, takie jak faktoryzacja liczb całkowitych lub dyskretne problemy logarytmiczne, więc istnieją głębokie powiązania z matematyką abstrakcyjną. Istnieje bardzo niewiele kryptosystemów, które są bezwarunkowo bezpieczne. Jednorazowy pad jest jeden i został udowodniony przez Claude’a Shannona. Istnieje kilka ważnych algorytmów, które okazały się bezpieczne przy pewnych założeniach. Na przykład niewykonalność faktoryzacji ekstremalnie dużych liczb całkowitych jest podstawą przekonania o bezpieczeństwie RSA i niektórych innych systemów, ale nawet w tym przypadku dowód na niezniszczalność jest niedostępny, ponieważ podstawowy problem matematyczny pozostaje otwarty. W praktyce są one powszechnie stosowane i większość kompetentnych obserwatorów uważa je za niemożliwe do złamania. Istnieją systemy podobne do RSA, takie jak ten autorstwa Michaela O. Rabina, które są bezpieczne pod warunkiem, że faktoryzacja n = pq jest niemożliwa; w praktyce jest to dość bezużyteczne. Problem logarytmów dyskretnych jest podstawą przekonania, że niektóre inne kryptosystemy są bezpieczne, a ponadto istnieją pokrewne, mniej praktyczne systemy, które są bezpieczne w odniesieniu do rozwiązywalności lub nierozstrzygalności problemu logów dyskretnych.[32]
Oprócz znajomości historii kryptografii, projektanci algorytmów i systemów kryptograficznych muszą również rozsądnie rozważyć prawdopodobne przyszłe zmiany podczas pracy nad swoimi projektami. Na przykład, ciągła poprawa mocy obliczeniowej komputerów zwiększyła zakres ataków typu brute-force, więc przy określaniu długości kluczy, wymagane długości kluczy również rosną.[33] Potencjalne skutki obliczeń kwantowych są już rozważane przez niektórych projektantów systemów kryptograficznych opracowujących kryptografię post-kwantową; zapowiadana bliskość niewielkich implementacji tych maszyn może sprawić, że potrzeba wyprzedzającej ostrożności stanie się czymś więcej niż tylko spekulacją[4].
Kryptografia z kluczem symetrycznym
Główny artykuł: Algorytm klucza symetrycznego
diagram przedstawiający proces szyfrowania z kluczem i deszyfrowania
Kryptografia z kluczem symetrycznym, w której do szyfrowania i deszyfrowania używany jest jeden klucz.
Kryptografia z kluczem symetrycznym odnosi się do metod szyfrowania, w których zarówno nadawca, jak i odbiorca dzielą ten sam klucz (lub, rzadziej, w których ich klucze są różne, ale powiązane w łatwy do obliczenia sposób). Był to jedyny rodzaj szyfrowania znany publicznie do czerwca 1976 roku.[30]
Schemat logiczny przedstawiający proces szyfrowania Międzynarodowego Algorytmu Szyfrowania Danych
Jedna runda (z 8,5) szyfru IDEA, używanego w większości wersji PGP i oprogramowania kompatybilnego z OpenPGP do efektywnego czasowo szyfrowania wiadomości.
Szyfry symetryczne są implementowane jako szyfry blokowe lub szyfry strumieniowe. Szyfr blokowy szyfruje dane wejściowe w blokach tekstu jawnego, w przeciwieństwie do pojedynczych znaków, formy wejściowej używanej przez szyfr strumieniowy.
Data Encryption Standard (DES) i Advanced Encryption Standard (AES) to szyfry blokowe, które zostały uznane za standardy kryptograficzne przez rząd Stanów Zjednoczonych (choć oznaczenie DES zostało ostatecznie wycofane po przyjęciu AES).[34] Pomimo wycofania DES jako oficjalnego standardu, DES (zwłaszcza jego wciąż zatwierdzony i znacznie bezpieczniejszy wariant triple-DES) pozostaje dość popularny; jest używany w szerokim zakresie zastosowań, od szyfrowania ATM[35] do prywatności poczty elektronicznej[36] i bezpieczny zdalny dostęp.[37] Zaprojektowano i wydano wiele innych szyfrów blokowych, różniących się znacznie pod względem jakości. Wiele z nich, nawet tych zaprojektowanych przez zdolnych praktyków, zostało całkowicie złamanych, jak na przykład FEAL[4].[38]
Szyfry strumieniowe, w przeciwieństwie do szyfrów blokowych, tworzą dowolnie długi strumień materiału klucza, który jest łączony z tekstem jawnym bit po bicie lub znak po znaku, podobnie jak w przypadku szyfrów jednorazowych. W szyfrze strumieniowym strumień wyjściowy jest tworzony na podstawie ukrytego stanu wewnętrznego, który zmienia się podczas działania szyfru. Ten stan wewnętrzny jest początkowo konfigurowany przy użyciu materiału tajnego klucza. RC4 jest szeroko stosowanym szyfrem strumieniowym; patrz Kategoria:Szyfry strumieniowe[4]. Szyfry blokowe mogą być używane jako szyfry strumieniowe; patrz Tryby działania szyfrów blokowych.
Kryptograficzne funkcje skrótu to trzeci rodzaj algorytmów kryptograficznych. Przyjmują one wiadomość o dowolnej długości jako dane wejściowe i wyprowadzają krótki hash o stałej długości, który może być użyty (na przykład) w podpisie cyfrowym. W przypadku dobrych funkcji skrótu atakujący nie może znaleźć dwóch wiadomości, które generują ten sam skrót. MD4 to od dawna używana funkcja skrótu, która jest obecnie uszkodzona; MD5, wzmocniony wariant MD4, jest również szeroko stosowany, ale uszkodzony w praktyce. Amerykańska Agencja Bezpieczeństwa Narodowego opracowała serię funkcji skrótu Secure Hash Algorithm podobnych do MD5: SHA-0 był wadliwym algorytmem, który agencja wycofała; SHA-1 jest szeroko stosowany i bezpieczniejszy niż MD5, ale kryptoanalitycy zidentyfikowali ataki na niego; rodzina SHA-2 ulepsza SHA-1, ale jest podatna na kolizje od 2011 roku; a amerykański organ normalizacyjny uznał za „rozsądne” z punktu widzenia bezpieczeństwa opracowanie nowego standardu w celu „znacznej poprawy solidności ogólnego zestawu narzędzi algorytmów hashujących NIST”.[39] W związku z tym konkurs na projekt funkcji skrótu miał na celu wyłonienie do 2012 r. nowego amerykańskiego standardu krajowego o nazwie SHA-3. Konkurs zakończył się 2 października 2012 r., kiedy to NIST ogłosił, że Keccak będzie nowym algorytmem skrótu SHA-3.[40] W przeciwieństwie do szyfrów blokowych i strumieniowych, które są odwracalne, kryptograficzne funkcje skrótu generują zaszyfrowane dane wyjściowe, których nie można użyć do odzyskania oryginalnych danych wejściowych. Kryptograficzne funkcje skrótu są używane do weryfikacji autentyczności danych pobranych z niezaufanego źródła lub w celu dodania warstwy zabezpieczeń.
Kody uwierzytelniania wiadomości (MAC) są bardzo podobne do kryptograficznych funkcji skrótu, z wyjątkiem tego, że tajny klucz może być użyty do uwierzytelnienia wartości skrótu po jej otrzymaniu;[4] ta dodatkowa komplikacja blokuje schemat ataku przeciwko algorytmom skrótów, więc uznano, że jest to warte wysiłku.
Nowoczesna kryptografia
Współczesną dziedzinę kryptografii można podzielić na kilka obszarów badań. Najważniejsze z nich zostały omówione tutaj; więcej informacji można znaleźć w sekcji Tematy w kryptografii.
Kryptografia klucza publicznego
Schemat kryptografii klucza publicznego przedstawiający klucz publiczny i klucz prywatny
Kryptografia klucza publicznego, w której do szyfrowania i deszyfrowania używane są różne klucze.
Kryptosystemy z kluczem symetrycznym używają tego samego klucza do szyfrowania i deszyfrowania wiadomości, chociaż wiadomość lub grupa wiadomości może mieć inny klucz niż pozostałe. Istotną wadą szyfrów symetrycznych jest konieczność zarządzania kluczami w celu ich bezpiecznego stosowania. Każda odrębna para komunikujących się stron musi, w idealnej sytuacji, współdzielić inny klucz, a być może także dla każdego wymienianego szyfrogramu. Liczba wymaganych kluczy rośnie wraz z kwadratem liczby członków sieci, co bardzo szybko wymaga złożonych schematów zarządzania kluczami, aby utrzymać je wszystkie w spójności i tajemnicy.
zdjęcia Whitfielda Diffie i Martina Hellmana
