Czym jest szyfrowanie

---

W dzisiejszym świecie przesyłanie informacji to kluczowa forma naszej aktywności. Informacje możemy kodować po to, żeby nikt postronny nie miał do nich dostępu.

---

Bartosz Naskręcki

---

Wiek XXI to era informacji. Zalewa nas strumień danych, który jest nieporównywalny do czegokolwiek widzianego wcześniej w historii. Żeby skutecznie i bezpiecznie przesyłać te dane, używamy niezwykle wyrafinowanych metod szyfrowania, których podstawowe idee sięgają czasów starożytnych.

Żeby zilustrować idee szyfrowania, posłużmy się przykładem. Chcemy przekazać komunikat osobie znajdującej się w innym pomieszczeniu, jedno krótkie zdanie, np. „Jestem w drugim pokoju”. Ta informacja ma trafić tylko do jednej osoby. Każdy posługujący się językiem polskim bez trudu zrozumie sens tego zdania i wyciągnie oczywiste wnioski. Potrzebujemy pewnego sposobu zapisania tekstu w inny sposób, który w dodatku pozwala się odwrócić, czyli z kodu odzyskać wiadomość oryginalną. Zastosowanie prostej metody pozwala na zaszyfrowanie wiadomości.

Literę A zastępujemy literą B, literę B literą C itd. Załóżmy dla uproszczenia, że mamy alfabet łaciński, który składa się tylko z 26 wielkich liter. Litera Z przejdzie na literę A. Usunięcie spacji nie stanowi dużego wyzwania przy czytaniu. W efekcie uzyskamy tekst: „KFTUFNXESVHJNQPLPKV”.

Nie wygląda zrozumiale, prawda? Jeśli przekażemy tekst, w obecności osób postronnych w pokoju, wówczas nikt nie będzie w stanie szybko tej wiadomości odczytać bez zanotowania jej na papierze. Jak nasz rozmówca odkoduje wiadomość? Po prostu przesunie litery o jedną pozycję w lewo. Otrzyma informacje: „JESTEMWDRUGIMPOKOJU”.

Taki sposób zakodowania informacji nazywamy szyfrem Cezara. Rzymski przywódca Juliusz Cezar stosował ten prosty zabieg do ukrywania informacji przed osobami postronnymi. Najważniejsze cechy, które posiada ta metoda, to: szybkość zakodowania wiadomości, odwracalność procesu, ukrycie informacji przed osobą postronną, niewielka ilość informacji potrzebna do jej zakodowania.

Te cztery cechy to postulaty naszego bezpieczeństwa informacyjnego. Istotą współczesnej kryptologii, czyli nauki o tworzeniu i łamaniu szyfrów, jest dostarczanie procedur, które spełniają te wymagania i gwarantują nam wysoki poziom bezpieczeństwa – odczytanie oryginalnej wiadomości bez znajomości sekretnego klucza jest w praktyce niemożliwe. W internecie nikt z nas nie wysyła pasków papieru, na których odnotowujemy niezrozumiałe symbole, lecz przesyłanie danych musi spełniać opisane wyżej postulaty.

Procedury przetwarzania danych tak samo jak wymieniony wcześniej szyfr Cezara pozwalają wysyłać ogromną liczbę „pasków z wiadomościami”. Informacji jest tak dużo, że możemy je mierzyć liczbą symboli sięgającą 1020 elementów. To trudna do wyobrażenia ilość informacji. Zwykły szyfr Cezara jest za prosty, by zakodować bezpiecznie taką ilość danych.

Kodowanie wiadomości

W sukurs przychodzi nam idea, którą przypisuje się Blaise’owi de Vigenóre, francuskiemu uczonemu żyjącemu w XVI wieku. Szyfr Cezara, polegający na przesunięciu liter, jest bardzo prosty do złamania. Mając dany ustalony język, wystarczy zrobić tabelę występowania częstości liter i porównując w oryginalnym alfabecie i zakodowanym, zestawić najczęściej występujące litery.

Takie działanie bardzo często da nam prawidłową informację o przesunięciach potrzebnych do rozkodowania wiadomości. Nowy pomysł Vigenóre’a polegał na tym, że możemy ustalić nieznanej długości słowo kodowe – klucz, którego litery będą decydować, o ile pozycji przesuwamy dany znak.

Na przykład używamy klucza:

ABC (zamieniamy litery na przesunięcia);

A –> 0; B –> 1; C –> 2.

Tekst jawny: ALAMAKOTA.

Używamy klucza: ABCABCABC, otrzymujemy w ten sposób szyfrogram: AMCMBMOUC.

Mając dostatecznie długie słowo kodowe, możemy spowodować, że złamanie takiego szyfru stanie się bardzo trudne. Gdy długość klucza jest równa długości wiadomości, otrzymujemy szyfr doskonały, zwany one-time pad.

Tak trudne, że w praktyce niemożliwe bez specjalnych metod. Takim szyfrem Vigenóre’a „do potęgi” była maszyna szyfrująca Enigma, w której praktycznie każda litera jest szyfrowana innym alfabetem. Jednakże ten kod po raz pierwszy złamał w 1932 roku Marian Rejewski, absolwent Uniwersytetu Poznańskiego. Istotną rolę w tym przełomie odegrali również Jerzy Różycki i Henryk Zygalski, koledzy Rejewskiego z Biura Szyfrów. Zidentyfikowali i wykorzystali pewne regularności w sposobie szyfrowania Enigmy.

Wyrafinowane szyfry blokowe

Lata I i II wojny światowej oraz powojenne to stopniowa transformacja szyfrowania z klasycznej domeny lingwistyki w to, co dziś nazywamy nowoczesną kryptografią. Ogromny rozwój nastąpił w latach 70., gdy zastąpiono tradycyjne szyfrowanie znakowe bardziej wyrafinowanymi szyframi blokowymi.

Szyfry blokowe można porównać do tasowania kart. W każdej rundzie wykonujemy operacje, które są z pozoru trywialne: konfuzja, maska z klucza, dyfuzja (rys. 3). Powtarzane wielokrotnie powodują olbrzymie skomplikowanie szyfru. Wymyślony w 1975 roku system Data Encryption Standard i jego następca Advanced Encryption Standard z 2001 roku jest obecnie używanym podstawowym szyfrem do bezpiecznego kodowania wiadomości o bardzo dużych rozmiarach. Praktycznie cały ruch w internecie jest szyfrowany standardem AES.

Co ciekawe, ten szyfr opiera się w swej istocie na jednej nieskomplikowanej obliczeniowo operacji, obliczania odwrotności elementu w ciele skończonym (tu konkretnie – 256-elementowym). A zatem mamy nasz ulepszony szyfr Cezara, który idealnie nadaje się do zaszyfrowania filmu lub innego olbrzymiego zbioru danych.

Żeby szyfry mogły być używane z sukcesem, nadawca i odbiorca wiadomości muszą znać klucz do szyfrowania. W połowie lat 70. w kryptografii pojawiły się dwa rozwiązania tego problemu. Pierwszy pomysł polega na generowaniu wspólnej tajemnicy tzw. protokołem Diffiego-Hellmana.

Drugi pomysł polegał na stworzeniu procedury, w której mamy dwa klucze (rys. 4): publiczny, służący tylko do szyfrowania wiadomości, i prywatny, służący tylko do ich dekodowania. Potrzebujemy jeszcze procedury, która wytworzy taką parę kluczy i pozwoli nam udostępnić publicznie tylko klucz oznaczony jako „publiczny”. W ten sposób każda osoba może nam wysłać sekret, ale nikt niepowołany nie może go odczytać bez klucza prywatnego. W konkretny sposób pomysł ten został wcielony w życie przez Rona Rivesta, Adiego Shamira i Leonarda Adlemana i jest znany jako algorytm RSA.

Tajemnicze splątanie kwantowe

Stopniowo od lat 90. kryptografia stała się absolutną domeną matematyków zajmujących się liczbami i algebrą. Największymi zdobyczami ostatnich lat jest zastąpienie poczciwego podnoszenia liczb do potęg bardziej wyrafinowaną operacją algebraiczną zwaną dodawaniem na krzywej eliptycznej. Krzywe eliptyczne są obiektami z zakresu algebry i geometrii, który niezwykle przysłużył się nauce w dziedzinach tak różnorodnych jak fizyka wysokich energii, geometria różniczkowa, analiza czy teoria liczb. Słynne wielkie twierdzenie Fermata udowodnione w 1994 roku przez Andrew Wilesa wykorzystuje w kluczowych miejscach argumentu właśnie krzywe eliptyczne. Kryptografowie odkryli dla siebie te obiekty dość późno, ale z wielkim skutkiem. Każdy aspekt naszego życia „internetowego” wykorzystuje krzywe eliptyczne dla zagwarantowania wysokiego poziomu bezpieczeństwa przed złamaniem haseł.

W latach 80. XX wieku pojawiło się zagrożenie dla bezpieczeństwa algorytmu RSA i protokołu Diffiego- -Hellmana w związku z użyciem algorytmu faktoryzacji Petera Shora. Przy obecności dużego komputera kwantowego algorytm ten łamałby bez trudu kody oparte na mnożeniu.

Coraz prężniejszy rozwój komputerów kwantowych i teorii informacji kwantowej spowodował pewną ucieczkę do przodu kryptografów zajmujących się RSA, krzywymi eliptycznymi i faktoryzacją. W ostatnich latach jesteśmy świadkami narodzin zupełnie nowej, tzw. postkwantowej kryptografii. O palmę pierwszeństwa obecnie walczy kilka algorytmów szyfrowania, mających zastąpić protokoły, które w przyszłości przy użyciu dużych komputerów kwantowych będziemy łamać bez trudu. Rozwój jest bardzo dynamiczny i dramatyczny. Spośród kilkudziesięciu kandydatów zgłoszonych do konkursu Post-Quantum Cryptography, ogłoszonego w 2016 roku przez amerykański National Institute of Standards and Technology, zostało już złamanych większość szyfrów i wyścig trwa dalej ze zwycięzcami czwartej rundy konkursu, ogłoszonymi w 2022 roku: CRYSTALS-Kyber – do generowania wspólnego sekretu, CRYSTALS-Dilithium, FALCON i SPHINCS+ – algorytmami do uzyskania podpisu elektronicznego.

Alternatywą jest również tzw. kryptografia kwantowa. Niezwykle prężnie rozwijający się dział fizyki i teorii obliczeń kwantowych, który pozwala zbudować oparte na laserach układy do bezpiecznego – na poziomie praw fizyki – przesyłania informacji na duże odległości. Podstawową ideą, którą się tu wykorzystuje, jest możliwość wygenerowania wspólnego sekretu, stosując tajemnicze splątanie kwantowe cząstek. W rozwoju tej technologii ponownie swój wkład mają Polacy, m.in. w osobie prof. Artura Ekerta, fizyka teoretycznego, który za swój wkład w tę dziedzinę otrzymał niedawno Nagrodę Milnera. Współczesna cywilizacja jest oparta na informacji i wymaga silnych certyfikatów bezpieczeństwa przesyłania danych. Postulaty bezpieczeństwa są tak wyśrubowane, że aby im sprostać, wykorzystuje się niezwykle zaawansowany aparat matematyczny algebry, teorii liczb, kombinatoryki i statystyki. Można więc z pełnym przekonaniem powiedzieć, że matematyka pojawiła się już praktycznie wszędzie dzięki globalnej sieci internetowej. Jest ona cichym i dobrze naoliwionym, tajemniczym mechanizmem, który w ukryty sposób, jak w książce Umberto Eco „Wahadło Foucaulta”, rządzi naszym światem i pozwala nam spać spokojnie, w czasie gdy maszyny obliczeniowe pracują na nasze bezpieczeństwo i dobrobyt (rys. 2). ■

---

Wersja drukowana tego artykułu ukazała się w numerze 4/2023 (76) popularnonaukowego kwartalnika „Academia: Magazyn Polskiej Akademii Nauk” [ściągnij pdf].

---