Poznański Portal Matematyczny

Symetryczne protokoły szyfrowania

Autor: Maciej Grześkowiak Redaktor: Bartłomiej Przybylski

Protokoły kryptograficzne

Być może nie każdy z nas się nad tym zastanawiał, ale w codziennych sytuacjach postępujemy zgodnie z pewnymi protokołami, gdy chcemy zrealizować określone zadanie. W celu wysłania kartki pocztowej nadawca powinien wykonać następujące kroki: zaadresować ją, nakleić znaczek pocztowy i wrzucić kartkę do skrzynki pocztowej. Dodajmy, że nadawca, jeśli ma na to ochotę, może napisać kilka słów skierowanych do adresata. Adresat, po kilku dniach, znajdzie kartkę w swojej skrzynce na listy i odczyta wiadomość.

Podobnie, do nawiązania kontaktu telefonicznego pomiędzy dwoma stronami potrzebne są odpowiednie do tego celu urządzenia. Załóżmy, że Alice i Bob są posiadaczami telefonów. Jeśli Alice ma ochotę zadzwonić do Boba, to wybiera jego numer i oczekuje na połączenie. Natomiast Bob, jeśli jest zainteresowany rozmową z Alice, akceptuje połączenie i prowadzi z nią rozmowę. Po zakończeniu konwersacji obie strony zawieszają nawiązane połączenie.

W obu powyższych przykładach zostały zrealizowane konkretne protokoły, to znaczy wykonano określoną sekwencję kroków obejmujących co najmniej dwie strony, w celu realizacji określonego zadania. Czytelnik z łatwością poda więcej przykładów protokołów, które związane są z funkcjonowaniem dzisiejszego społeczeństwa: zamawianie towarów przez telefon, głosowanie w wyborach, gra w pokera itd. Niektóre z nich realizowane są za pomocą sieci komputerowych, ale istnieją też takie protokoły, których przeprowadzenie trudno sobie wyobrazić na pierwszy rzut oka. Wyobraźmy sobie, że Alice jest na wakacjach w Australii, a Bob w tym samym czasie znajduje się w Krakowie. Przypuśćmy, że pragną oni wykonać uczciwy rzut monetą za pośrednictwem swoich telefonów komórkowych bądź komputerów. Alice zaproponowała następujący sposób rzutu monetą: Najpierw ty wybierz sobie losowy bit i prześlij go do mnie, a potem ja zrobię to samo. Na końcu obliczmy resztę z dzielenia przez dwa sumy naszych bitów. Jeśli otrzymamy zero, to wynikiem rzutu monetą jest orzeł. W przeciwnym wypadku wynikiem rzutu jest reszka.

Czytelnik z łatwością zauważy, że przedstawiony protokół rzutu monetą ma poważny błąd. Osoba, która jako druga przesyła swój bit może decydować o ostatecznym wyniku. W konsekwencji taka sekwencja kroków nie zapewnia uczciwego rzutu monetą. Czy można przeprowadzić uczciwy protokół rzutu monetą? Czy można za pomocą urządzeń teleinformatycznych oddawać anonimowe głosy wyborcze lub uczciwie zagrać w pokera na odległość? Odpowiedź na te pytania jest twierdząca i o tym jest niniejszy tekst.

Urządzenia teleinformatyczne, aby wykonywać analogiczne zadania do tych, które wykonywane są przez człowieka w obecności innych ludzi, w celu zapewnienia uczciwości i jego bezpieczeństwa stosują protokoły wykorzystujące kryptografię. Tego typu protokoły nazywamy protokołami kryptograficznymi. Często działają one przy założeniu, że strony, które ich używają, nie ufają sobie wzajemnie. W niektórych protokołach kryptograficznych zakładamy dodatkowo, że istnieje trzecia strona (zwana arbitrem), która jest obdarzona całkowitym zaufaniem pozostałych stron protokołu i nie jest z żadną z nich związana. Arbiter często pomaga ukończyć protokół uczestnikom nie ufającym sobie nawzajem. Protokoły kryptograficzne wykorzystują całą maszynerię kryptograficzną, między innymi: algorytmy szyfrujące i deszyfrujące, algorytmy generowania i weryfikacji podpisu elektronicznego, jednokierunkowe funkcje skrótu i wiele innych.

Projektowanie protokołów kryptograficznych

Projektowaniem protokołów i algorytmów kryptograficznych zajmują się kryptografowie. Aby ujednolicić i łatwiej opisywać konstruowane protokoły ustalono, że uczestnikami (stronami) każdego protokołu kryptograficznego są Alice i Bob. Przyjęto regułę, że Alice inicjuje wszystkie protokoły, a Bob wykonuje kroki zdefiniowane przez drugą stronę. Wprowadzimy teraz kilka oznaczeń i pojęć, które wykorzystywane są do opisu protokołów kryptograficznych. Jak powszechnie wiadomo, dane w pamięci urządzeń teleinformatycznych oraz pakiety przesyłane podczas wykonywania protokołów teleinformatycznych możemy interpretować jako ciąg bitów o skończonej długości. Kryptografia najczęściej kojarzona jest z szyfrowaniem określonej porcji danych (skończonego ciągu bitów). Tego typu dane bitowe nazywamy wiadomością lub tekstem jawnym i oznaczamy przez $M$. Szyfrogram wiadomości $M$ (a więc ciąg bitów reprezentujący zaszyfrowaną wiadomość) oznaczamy literą $C$. Istotnym komponentem w procesie szyfrowania jest algorytm szyfrujący, oznaczany przez $E$, i deszyfrujący, oznaczany przez $D$. Te oba algorytmy powszechnie nazywamy szyfrem lub systemem szyfrującym i są one ze sobą ściśle związane.

Bezpieczeństwo współcześnie stosowanych systemów szyfrujących osiągane jest poprzez zastosowanie klucza (szyfrującego i deszyfrującego), oznaczanego literą $K$. Budowa i zasada działania szyfru powinna być jawna, a bezpieczeństwo oparte na utrzymaniu w tajemnicy metody szyfrowania często świadczy o słabości takiego algorytmu. Proces szyfrowania tekstu jawnego $M$ przy pomocy klucza $K$, w wyniku którego dostajemy szyfrogram $C$ zapisujemy jako
\[
E_K(M)=C.
\]
Deszyfrowanie jest procesem odwrotnym do szyfrowania, ale wykonywane jest z wykorzystaniem klucza $K’$. A więc wynikiem deszyfrowania $C$ kluczem $K’$ jest wiadomość $M$, co zapisujemy jako
\[
D_{K’}(C)=M.
\]
Ze względu na własności kluczy szyfrujących i deszyfrujących rozróżniamy dwa główne systemy szyfrowania:

  • algorytmy symetryczne, w których klucz do szyfrowania i deszyfrowania jest ten sam, bądź jeden może być łatwo wyprowadzony z drugiego;
  • algorytmy asymetryczne, zwane algorytmami z kluczem jawnym lub publicznym, w których klucze do szyfrowania i deszyfrowania są różne; ponadto, nie jest w praktyce możliwe na podstawie jednego nich wyznaczenie drugiego.

Zbiór wszystkich możliwych wartości klucza nazywamy przestrzenią klucza. Współczesne metody szyfrowania dostarczają algorytmów, w których przestrzeń klucza jest na tyle duża,
aby komputery nie mogły jej w praktyce wygenerować. Własność ta ma ogromne znaczenie dla bezpieczeństwa algorytmu szyfrującego.

Jak rozumieć bezpieczeństwo szyfru?

Kryptoanalitycy zajmują się znajdowaniem słabych miejsc w protokołach i algorytmach kryptograficznych. Działanie kryptoanalityka nazywamy atakiem bądź łamaniem konkretnego rozwiązania zaproponowanego przez kryptografów. Zakłada się, że kryptoanalityk dysponuje pełną wiedzą o budowie i zasadzie działania protokołu bądź algorytmu kryptograficznego. Jest to rozsądne i powszechnie akceptowalne założenie. Bezpieczeństwo dowolnego systemu kryptograficznego nie może być oparte w tym, że nie jest znana nikomu jego budowa. Naiwnością jest myślenie, że nikt nie odtworzy kodu źródłowego takiego algorytmu bądź zasady jego działania. Doskonałym przykładem na to, że jest to możliwe jest rozpracowanie (złamanie) przez polskich kryptoanalityków zasady działania maszyny szyfrującej Enigma, której budowa w wersji wojskowej była tajna.

Bezpieczeństwo systemu szyfrującego powinno zależeć od dwóch czynników: długości klucza i mocy wykorzystanych algorytmów. Mocny algorytm to taki, który opierał się przez długie lata rozmaitym atakom zawodowych kryptoanalityków. Aby zobrazować zależność pomiędzy długością klucza i bezpieczeństwem gwarantowanym przez system szyfrujący przyjmijmy, że jedyną metodą złamania tego systemu jest spróbowanie każdego możliwego klucza. Taką technikę łamania szyfrów nazywamy atakiem siłowym (brutalnym). Jeżeli klucz składa się z 8 bitów, to przestrzeń kluczy ma $2^8=256$ elementów. Zatem atak siłowy wymaga co najwyżej 256 prób. W przypadku klucza 56 bitowego występuje $2^{56}$ możliwych kluczy. Jeśli założymy, że komputer potrafi sprawdzić milion kluczy na sekundę, to złamanie szyfru atakiem brutalnym wymaga 2000 lat jego pracy. Gdy klucz ma 128 bitów, taki sam atak zajmie
komputerowi już $10^{25}$ lat. Pamiętajmy, że wszechświat ma dopiero około $10^{10}$ lat. W przypadku 256-bitowego klucza komputer musi przetestować aż $2^{256}$ możliwych kluczy. W tym przypadku liczba możliwych prób jest zdecydowanie większa niż liczba atomów w galaktyce (ok. $2^{233}$), ale znacznie mniejsza niż liczba atomów we Wszechświecie (ok. $2^{265}$).

Symetryczny protokół szyfrowania

Alice i Bob chcą się porozumiewać w sieci teleinformatycznej w taki sposób, aby wysyłane przez nich wiadomości nie mogły być przez nikogo innego odczytane. Krótko mówiąc, pragną, by ich rozmowa miała charakter poufny. W tym celu powinni wykonać następujący protokół

  1. Alice i Bob w jawny sposób uzgadniają system szyfrujący z algorytmem symetrycznym, który będą wykorzystywać w celu bezpiecznego przesyłania wiadomości. W szczególności ustalają algorytm szyfrowania $E$ oraz metodę deszyfrowania $D$.
  2. Alice i Bob w bezpieczny sposób uzgadniają klucz szyfrujący $K$ do algorytmu $E$. Klucz $K$ jest tajny i musi być utrzymany w sekrecie.
  3. Alice ustala wiadomość $M$ oraz szyfruje ją za pomocą algorytmu szyfrującego $E$ i klucza tajnego $K$. W ten sposób Alice oblicza $C=E_K(M)$, a następnie wysyła $C$ do Boba.
  4. Bob wyznacza z klucza szyfrującego $K$ klucz do deszyfrowania $K’$ i deszyfruje $C$ za pomocą algorytmu $D$ i klucza $K’$. W tem sposób Bob uzyskuje wiadomość $M=D_{K’}(C)$.

Powyższy protokół kryptograficzny zwany jest symetrycznym protokołem szyfrowania. Załóżmy, że jesteśmy kryptoanalitykami i dokonajmy teraz analizy bezpieczeństwa tego protokołu. Pomocne będą nam w tym dwie osoby: Eve – osoba podsłuchująca – oraz Mallet – złośliwy, aktywny napastnik. W kroku pierwszym Eve dowiaduje się jakie algorytmy szyfrowania i deszyfrowania będą wykorzystywane podczas wzajemnej komunikacji. Jeśli Alice i Bob ustalą algorytm, który nie jest mocny lub wymaga się do niego krótkiego klucza, to Eve z łatwością będzie mogła podsłuchiwać ich konwersację. Z drugiej strony, gdy świadomie wybiorą oni odporny na ataki system szyfrowy, to uzyskane przez Eve informacje będą bezużyteczne. Krok drugi daje największe możliwości ataku Eve. Jej celem będzie poznanie klucza tajnego $K$. Przedstawiony protokół, zakłada jedynie, że krok 2 jest wykonany bezpiecznie, a klucz $K$ jest utajniony. Istnieją protokoły kryptograficzne, które realizują postulaty z kroku drugiego i w praktyce tego typu uzgodnienia kluczy są realizowane. Załóżmy, że Alice i Bob, jako świadomi użytkownicy sieci teleinformatycznych, wykorzystali taki protokół. Zatem krok drugi jest bezpieczny.

Mallet, będący aktywnym napastnikiem, może przechwycić pakiety wysyłane przez Alice w kroku trzecim. W ten sposób uniemożliwi on rozmowę Alice z Bobem. Mallet może również podmienić szyfrogram $C$ wysyłany kroku trzecim, ale wtedy odszyfrowana przez Boba wiadomość będzie losowym ciągiem bitów. Jednak gdyby Mallet, w jakiś znany tylko sobie sposób, zdobył klucz tajny $K$, to nie tylko pozna on treść wiadomości wysyłanych przez obie strony protokołu, ale może on również wszczepiać fałszywe wiadomości w kanał komunikacyjny Alice i Bob.

Co może uczynić Alice w celu zniszczenia protokołu? Wystarczy, że wyśle ona kopię klucza tajnego $K$ do Eve. Bob przekonany o nawiązaniu bezpiecznego kanału z Alice, jest nieświadomy tego, że Eve będzie znała treść wszystkich przesłanych wiadomości. Jest to poważny problem – nie jest znany mechanizm kryptograficzny, który powstrzyma Alice od przekazania kopii klucza tajnego. Bob może postąpić równie nieetycznie, jak to uczyniła Alice. Z tego powodu protokół jest bezpieczny jeśli obie strony ufają sobie wzajemnie.

Zalety i wady systemów symetrycznych

Na początku przyjrzyjmy się słabościom protokołów i szyfrów symetrycznych. Skompromitowanie klucza tajnego może mieć kolosalne konsekwencje. Przeciwnik posiadający klucz tajny może odszyfrować wszystkie wymienione wiadomości, które były szyfrowane przy użyciu tego klucza. Z tego powodu klucz tajny powinien być często zmieniany, ale również
powinien być przechowywany w taki sposób, aby nie wycikeły na jego temat żadne informacje. Ujawnienie kilku bitów klucza może w istotny sposób ułatwić kryptoanalizę mocnego algorytmu.

Zakładając, że każda para uczniów pewnej $n$ osobowej klasy ponadgimazjalnej stosuje odrębne klucze tajne w symetrycznej metodzie szyfrowania, każdy uczeń musi przechowywać $n-1$ różnych kluczy tajnych. Problemem jest również wzajemne uzgodnienie klucza tajnego. Często protokoły kryptograficzne, które realizują takie zadanie, bazują na założeniu, że obie strony protokołu ufają (kolejnej) trzeciej stronie. Taka konieczność może zostać wykorzystana przez Malleta do potencjalnego ataku.

Zaletą stosowania symetrycznych algorytmów szyfrowania jest to, że działają one bardzo szybko. Z tego powodu doskonale nadają się do szyfrowania dużej porcji danych, nawet całych dysków komputerowych. Ta zaleta też ma swoją ciemną stronę. Coraz częściej zdarzają się ataki na komputery użytkowników, które powodują zaszyfrowanie całego dysku. Dopiero po wpłaceniu okupu ofiara ataku może otrzymać klucz tajny służący do odszyfrowania jego zawartości.

Do góry