Szyfrowanie: klucz publiczny może stać się nieskuteczny

Załóżmy, że Francis Crick i James D. Watson jakimś cudem bioinżynierii zasiadają na scenie i opowiadają o tym, jak odkryli strukturę DNA. Relacja z tego wydarzenia trafia na YouTube. Albo przypuśćmy, że Thomas Edison i Nikola Tesla ożywieni magiczną iskrą stają do dyskusji o wyższości prądu zmiennego nad stałym – i zaczyna się obłęd. Licznik odsłon po godzinie wskazuje miliony, więcej nawet niż podczas premier produktów Apple’a.

A teraz weźmy tegoroczną RSA Conference, najważniejszą chyba międzynarodową imprezę kryptologiczną. W panelu udział biorą między innymi autorzy odkrycia, które pół wieku temu zmieniło bieg historii. Zrewolucjonizowało sposób, w jaki wymieniamy się informacjami. Zagwarantowało bezpieczeństwo nie tylko tajemnicom państwowym, jak wcześniej używane metody kryptograficzne, ale i naszym małym sekretom. Zapewnili prywatność przesyłu danych, symbolizowaną skrótem SSL czy HTTP, i ukryli zawartość portfeli z bitcoinami. Kryptografia klucza publicznego, bo o tym wynalazku mowa, przełączyła cywilizację globalną na wyższy bieg.

Tymczasem trud obejrzenia nagrania rozmowy Whitfielda Diffie’ego i Clifforda Cocksa z 7 czerwca podjęło niespełna pięciuset widzów, wliczając autora.

Doskonałe = niewykonalne

Wiele jest szyfrów. A wśród nich ten na pierwszy rzut oka doskonały. Opiera się na wykorzystaniu klucza jednorazowego, czyli ciągu znaków, najlepiej wygenerowanych losowo, który „dodaje się” do ciągu tworzącego treść. Nadawca wiadomości używa go do jej zakodowania, odbiorca – odkodowania (szczegóły techniczne nie są istotne dla zrozumienia zasady). Szyfrowanie z kluczem jednorazowym ma ogromną przewagę nad technikami, które kazały zastępować znaki wiadomości innymi znakami zgodnie z jakąś ściśle określoną zasadą. One pękają pod naporem matematyki, analizy częstości znaków oraz powtarzających się wzorców.

Niestety internet oparty o taką kryptografię by się nie wydarzył. Nadawca i odbiorca musieliby za każdym razem uzgadniać klucz w tajemnicy przed światem – używać specjalnego, bezpiecznego łącza albo skorzystać z usług kuriera. Gdyby taka metoda miała stać się podstawą globalnej gospodarki, oznaczałaby konieczność dystrybucji milionów kluczy i graniczące z pewnością ryzyko ich przechwytywania przez osoby trzecie.

Jako pierwsza realne kroki w celu rozwiązania tego problemu poczyniła armia brytyjska, motywowana głównie względami ekonomicznymi. Government Communications Headquarters (GCHQ) – agencja szpiegowska, której podobna do obwarzanka siedziba pod Cheltenham służy lotnikom za punkt orientacyjny – oddelegowała do tego zadania kryptologa Jamesa Ellisa. Był on genialny w stopniu porównywalnym do Alana Turinga, matematyka, który przyczynił się do złamania szyfrów Enigmy. Był także podobnie do niego idiosynkratyczny oraz introwertyczny. Nie tolerował też odgórnej kontroli. Przełożeni wybrali go jednak nie w dowód szczególnego zaufania czy szacunku, a raczej potwierdzenia niskiego priorytetu, który przypisywano temu wyzwaniu. Uważano powszechnie, że jest niewykonalne.

Niewykonalne = genialne

Wybór okazał się słuszny. Pochodzący z nieznanej innym kryptologom planety Ellis podszedł do sprawy po swojemu. W 1969 r. przypomniał sobie o pewnym anonimowym projekcie (o nazwie C-43), który Bell Telephone Company prowadziła pod koniec drugiej wojny światowej. Zakładał on przerzucanie obowiązku szyfrowania na odbiorcę wiadomości. Miał on generować szum na linii telefonicznej (bo o taką komunikację chodziło), do którego, na drugim końcu kabla, nadawca dodawał następnie własny komunikat. I tylko odbiorca, znając specyfikę zakłóceń, potrafił później taki sygnał oczyścić.

Ellis ku własnemu zaskoczeniu zauważył, że można tę metodę uogólnić – wiadomość poddać działaniu jakiejś operacji matematycznej, którą łatwo wykonać w jedną stronę, ale trudno w drugą (niezłą analogią jest mieszanie farb o różnych kolorach). Brytyjczyk nie miał jednak pojęcia, jakiej konkretnie operacji szukać, bo nie był matematykiem.

W sposób niezobowiązujący podzielił się jednak swoją refleksją z 22-letnim wówczas Cliffordem Cocksem. Ten ledwo opierzony matematyk, który dopiero co opuścił mury Oksfordu, zabrał się do poszukiwania odpowiedniej jednokierunkowej funkcji matematycznej i sprytnego sposobu jej użycia w zasadzie z braku lepszego zajęcia. Nie wiedział, że nad problemem tym łamała sobie głowy niemała część kadry GCHQ. Dla pozostałej, jeszcze większej, pomysł brzmiał jak herezja.

Ponieważ firma zabraniała wynoszenia z biura jakichkolwiek notatek, Cocks odkrycia dokonał prawie mimochodem. Pewnego wieczoru zmapował sobie – jak to określił – problem w głowie, a rano, po przebudzeniu, spisał gotowe rozwiązanie. W głównej roli obsadził funkcję uwzględniającą rozkład dużych liczb na czynniki pierwsze – proces obliczeniowo niebywale wręcz czasochłonny. Shaun Wylie, główny matematyk w Cheltenham, tak ocenił propozycję Cocksa: „Niestety, nie widzę w niej żadnego błędu”.

Skrystalizowana jesienią 1973 r. metoda Cocksa (uzupełniona przez Malcolma Williamsona, jego kolegę z GCHQ) zakładała użycia kombinacji dwóch kluczy – publicznego i prywatnego, sekretnego. Zrozumienie tej metody, choć nie wymaga doktoratu z matematyki, zmusza do długiego opisu (zgrabny przykład z mieszaniem farb można znaleźć w sieci). Dość powiedzieć, że matematyczną relację między kluczem prywatnym a publicznym określa właśnie funkcja jednokierunkowa na dużych liczbach.

Paradoksalnie ideowa prostota propozycji Cocksa wzbudziła nieufność GCHQ. Tamtejsi eksperci obawiali się, że choć wtedy – w latach 70. – nikt nie znał sposobu na szybki i łatwy rozkład dużych liczb na mniejsze, to problem ten mógł kiedyś okazać się matematycznie trywialny. A gdyby szyfrowanie z kluczem publicznym miało się stać standardem, gdyby zaczęto go powszechnie używać do utajniania korespondencji, uwierzytelniania, prowadzenia transakcji, to ta trywialność zachwiałaby stabilnością całego państwa, a może nawet cywilizacji. Poza tym w czasach komputerów wielkich jak szafa gdańska wydawało się, że wdrożenie tego systemu będzie zbyt kosztowne. Szefostwo wywiadu brytyjskiego zamknęło sprawę, a wyniki pozostały tajne – bo taki był modus operandi GCHQ. W efekcie Ellis, Cocks i Williams już kilka lat później byli świadkami ponownego odkrywania tego, co sami już wymyślili. I musieli milczeć.

Genialne = tajne

W połowie lat 70. do identycznych wniosków co Brytyjczycy doszły dwie grupy Amerykanów. Tyle że oni nie pracowali dla rządu ani korporacji, więc nie obejmowała ich klauzula tajności. Oni też przez kilkadziesiąt lat, aż do końca XX w., ogrzewali się w świetle chwały – zbierając niewymierne i wymierne owoce swojego osiągnięcia – sukces Brytyjczyków został wyróżniony przez Institute of Electrical and Electronic Engineers (IEEE), największe na świecie zrzeszenie ludzi związanych z techniką, dopiero w roku 2010.

Idea szyfrowania z kluczem publicznym przebiła się do świadomości społeczności naukowej w 1976 r., kiedy jej zasadę opublikowali działający niezależnie Whitfield Diffie, zatrudniony na Stanford University Martin Hellman i Ralph Merkle, wówczas jeszcze student University of California w Berkeley. Trzej Amerykanie poczynili krok analogiczny do wykonanego przez Jamesa Ellisa. Chwilę później Ron Rivest, Adi Shamir i Leonard Adleman, doskonale uzupełniający się kryptografowie z Massachusetts Institute of Technology, wpadli na trop odpowiedniej funkcji jednokierunkowej. Z tym że nie stało się to od razu, w chwili odprężenia po pracy, jak u Cocksa, ale po wielu miesiącach mozolnych poszukiwań. Przełom nastąpił w święto Pesach 1977 r. Spopularyzowany przez miesięcznik „Scientific American” przebił się do mediów głównego nurtu.

Zapachniało kryptologiczną wiosną, ale i czymś gorzkim. Choć algorytm zwany jako RSA (akronim nazwisk wynalazców) powstał na uczelni jako owoc swobodnej wymiany myśli, w 1983 r. został objęty amerykańskim prawem patentowym. Brytyjczycy protestowali, twierdząc, że nie można licencjonować matematyki. Bez skutku. Aż do 2000 r. korzystanie z RSA wiązało się zwykle z koniecznością wnoszenia opłat.

Tajne = groźne

Wynalazek Ellisa i Cocksa – oraz oczywiście Amerykanów – wyznacza moment przejścia fazowego w historii kryptografii. Wcześniej umiejętność szyfrowania wpływała na ludzkie losy w sposób znaczący, ale niejako uogólniony, na poziomie narodowym. Metoda klucza publicznego ujawniła nowy potencjał kryptografii, dosięgający każdego uczestnika współczesnego społeczeństwa, detalicznie. Odsłoniła też nowe obszary potencjalnych nadużyć.

Zmianie uległa dynamika zaufania obywateli do władzy. Rządy dysponujące i sankcjonujące dostęp do najbardziej zaawansowanych metod kryptograficznych zyskały nowe, fantastyczne narzędzie kontroli. GCHQ i jej amerykański odpowiednik National Security Agency (NSA) wyrosły podczas zimnej wojny na przemysłowe molochy, zatrudniające więcej matematyków niż jakiekolwiek inne instytucje na świecie.

Obawa przed potencjalnymi nadużyciami była powodem, dla którego w latach 90. XX w. programista amerykański Phil Zimmermann zaproponował algorytm Pretty Good Privacy, pozwalający na korzystanie z dobrodziejstw klucza publicznego za darmo. Atak, który przypuścił na niego rząd USA, był zapewne najbardziej dobitnym symbolem napięcia między instytucjami władzy a cyfrowymi libertarianami, głoszącymi, że swobodny dostęp do technik kryptograficznych należy do zestawu podstawowych swobód obywatelskich.

Czas jednak wrócić do pytania zasadniczego: Czy szyfrowanie z kluczem publicznym jest naprawdę bezpieczne? I tak, i nie.

Groźne = kwantowe

Gwarantem bezpieczeństwa są specyficzne, jednokierunkowe funkcje matematyczne. Szyfrowanie jest więc bezpieczne, gdy czas potrzebny komputerom do ich wykonania (w tę trudniejszą stronę) jest absurdalnie długi, a postęp w dziedzinie obliczeń – umiarkowanie szybki i linearny. Ograniczenie to dotyczy jednak tylko świata klasycznego.

Sytuacja może się zmienić z chwilą nadejścia konstruowanej mozolnie w laboratoriach maszyny liczącej nowej generacji: komputera kwantowego. Urządzenie to porusza się niejako „na skróty przez czas” (to fraza pisarza naukowego George’a Johnsona). Ścieżki obliczeń, które komputer klasyczny musi pokonywać jedna po drugiej, kwantowy obiera jednocześnie – wszystkie. Gdyby takie maszyny zaprząc do pracy, świat mógłby stanąć na krawędzi poważnego kryzysu – bo odkryte zostanie nie tylko to, co jest zakryte, czyli zaszyfrowane, w tej chwili. Komputery kwantowe odsłoniłyby wszystko to, co szyfrowaliśmy z kluczem publicznym od pół wieku. Sekrety przeszłości.

Ideę tych maszyn zasugerował w latach 80. Richard Feynman, jedna z najbardziej barwnych postaci współczesnej nauki. Zauważył, że do symulowania złożonych układów kwantowych można użyć innych, prostszych układów kwantowych. Niedługo później Brytyjczyk David Deutsch – postać także niemieszcząca się w akademickich schematach – dodał, że te proste układy ułożyć można tak sprytnie, że będą wykonywać obliczenia nieosiągalne dla tradycyjnych komputerów. W końcu, w 1994 r., Peter Shor, matematyk z Bell Labs, odkrył algorytm pozwalający maszynom kwantowym w błyskawiczny sposób rozkładać duże liczby na czynniki proste. Mówiąc inaczej – Feynman, Deutsch i Shor stworzyli narzędzie do miażdżenia kryptografii klucza publicznego.

Z przyczyn być może fundamentalnych, a na pewno wciąż niejasnych skonstruowanie użytecznego komputera kwantowego sprawia kolosalne trudności. Trzeba jednak założyć, że kiedyś w końcu zostaną one w całości lub częściowo przezwyciężone. Co się wówczas stanie?

Kwantowe = nierealne

Nic szczególnego. Otwartość i nieprzewidywalność matematyki, fakt, że w tej dziedzinie nie da się zmechanizować procesu dokonywania odkryć, ma dwojakie konsekwencje. Owszem, nie ma pewności, kto, kiedy, jak i jaką znajdzie metodę wykonywania w obie strony funkcji stojących na straży kryptografii klucza publicznego. Jak mówił Malcolm Williamson (kolega Cocksa) magazynowi „Wired”: „W całym tym szpeju może być ukryta jakaś magiczna śrubka. I jakiś student matematyki może naprawdę spowodować katastrofę”. Ale też jednocześnie jest matematyka niewyczerpywalnym źródłem pomysłów na nowe funkcje szyfrujące.

Rozproszone rozważania na ten temat rozwinęły się w całą nową, żywą dziedzinę wiedzy: kryptografię postkwantową. Kandydatki na nowe, odporne na dominację komputerów kwantowych metody kryptografii są już przygotowane (wykorzystują m.in. algorytmy kratowe, oparte na funkcjach skrótu czy kody korekcyjne). Pozostaje wybór najbardziej efektywnych i najlepiej rokujących na przyszłość.

Kryptolodzy mają więc dylemat podobny do tego, przed którym stali pół wieku temu – muszą ufać, że przez kilkadziesiąt najbliższych lat nie pojawi się szybka i łatwa metoda łamania zasugerowanych przez nich funkcji. „Stawką jest przyszłość. Trzeba ją chronić już dziś” – mówił Ali El Kaafarani, znawca kryptografii postkwantowej (w podkaście magazynu „Physics World”). To wybór, którego ostatecznie muszą dokonać narodowe, federalne, unijne agencje bezpieczeństwa.

Są skazane na kompromis, bo w pozaplatońskich kontekstach szyfr doskonały nie istnieje. Nawet kryptografia kwantowa (fascynujący, ale osobny temat), której teoria spełnia kryterium absolutnego bezpieczeństwa przesyłu informacji, wcielona w konkretne, materialne urządzenie staje się wrażliwa na podsłuch i ataki z zewnątrz. Jest więc trochę jak z kluczem jednorazowym. Artur Ekert, wybitny kryptolog częściowo polskiego pochodzenia, mawia: „Teoretycznie nie ma różnicy między teorią a praktyką, ale praktycznie jest”.