Szyfrowanie stosowano od niepamiętnych czasów. Do najprostszych szyfrów należy tzw. szyfr Cezara. Każda litera jest w nim zastępowana literą o k pozycji dalszą. Na przykład dla k = 3 oznacza to, że literze A odpowiada litera D, literze B litera E, itd. Trzem ostatnim literom alfabetu odpowiadają litery początkowe.

A B C D E F G H ... X Y Z

D E F G H I J K .. A B C

Wówczas napis SZYFR CEZARA będzie zaszyfrowany za pomocą napisu VCBIU FHCDUD. Przy tak prostym systemie odszyfrowanie tekstu nie przedstawia trudności. Przez ostatnie kilkaset lat pojawiło się wiele bardziej wyrafinowanych systemów szyfrowania, w których odszyfrowanie tekstu jest o wiele trudniejsze. Ale wszystkie klasyczne systemy mają wspólną cechę: każdy, kto zna metodę szyfrowania potrafi też odszyfrowywać. W przypadku szyfru Cezara – kto wie, że szyfrując przesuwamy alfabet o trzy litery do przodu, wie też, że odszyfrowując trzeba alfabet przesuwać o trzy litery do tyłu.

W takim systemie poufna wymiana listów wymaga uprzedniego uzgodnienia szczegółów systemu szyfrowania. W praktyce oznaczałoby, że poufna korespondencja możliwa byłaby tylko pomiędzy nielicznymi użytkownikami sieci.

System stworzony przez Ronalda L. Rivesta, Adi Shamira i Leonarda M. Adlemana, matematyków z Massachusetts Institute of Technology (Cambridge, Mass., USA) jest jednym z pierwszych systemów, w którym możliwości szyfrowania i odszyfrowywania są oddzielone.

Oznacza to, że znajomość sposobu szyfrowania nie daje żadnej możliwości odszyfrowania tekstu. System RSA (od nazwisk twórców) pozwala zapewnić poufność wiadomości przesyłanych publicznymi kanałami.

Niemal we wszystkich zastosowaniach matematyki w kryptografii (tak nazywa się nauka o szyfrach) korzystamy z arytmetyki zegarowej, czyli działań na resztach. Oznacza to, że wynik działania zastępujemy odpowiednią resztą. Oto przykład działań arytmetycznych na resztach modulo 12, czyli resztach z dzielenia przez 12:

7 + 9 mod 12 = 16 mod 12 = 4,

3 · 7 mod 12 = 21 mod 12 = 9.

Z takim dodawaniem stykamy się przy obliczeniach godzin: dziewięć godzin po siódmej jest czwarta. W arytmetyce zegarowej na każdym etapie rachunków daną liczbę można zastąpić odpowiednią resztą. Na przykład

7⁴ mod 12 = (7²)² mod 12 = 49² mod 12 = 1² mod 12 = 1.

Aby uniknąć ciągłego powtarzania symbolu mod, zazwyczaj tylko na końcu rachunków zaznaczamy, o jakie reszty chodzi:

7⁴ = (7²)² = 49² = 1² = 1 mod 12.

Niemożliwość złamania szyfru RSA wynika z trudności rachunkowych. Praktycznie, jedyny znany dziś sposób złamania szyfru RSA wymaga rozłożenia na czynniki pierwsze dość specjalnych liczb trzystucyfrowych. Nawet najszybsze z superkomputerów używanych obecnie (tj. w roku 2003) musiałyby na to poświęcić miliony lat.

W dalszych rozważaniach zachowamy samą zasadę działania szyfru, ale dokonamy szeregu uproszczeń w zakresie szczegółów technicznych. W szczególności, rachunki będziemy prowadzić na bardzo małych liczbach. W takim przypadku złamanie szyfru nie przedstawia żadnej trudności. Rachunki, jakie pojawiają się w przykładzie wprowadzającym można prowadzić na papierze, w dalszych przykładach i zadaniach przyda się kalkulator.

Wszystkie litery będą zamieniane na układy cyfr. Przyjmijmy najprostsze kodowanie liter alfabetu łacińskiego za pomocą układu dwu cyfr. Jeśli zechcesz kodować wszystkie litery polskiego alfabetu, musisz użyć trochę większych liczb.

Opiszemy teraz zasadę działania szyfru RSA i zilustrujemy go na bardzo prostym przykładzie. Przypomnijmy, że dwie liczby nazywamy względnie pierwszymi, gdy ich największy wspólny dzielnik jest równy 1. Przypomnimy też, że ilość liczb względnie pierwszych z N oznaczamy przez j (N).

W naszym najprostszym przykładzie przyjmiemy p = 3 i q = 11. Wówczas N = 3 · 11 = 33, a j (N) = 2 · 10 = 20. Weźmy J = 3. Metodą prób i błędów znajdujemy T = 7. Rzeczywiście: liczba 7 spełnia żądany warunek, gdyż JT = 3 · 7 = 1 mod 20.

Przesyłany tekst zamieniamy najpierw na litery (w dalszych przykładach na bloki liter), po czym kodujemy, wykorzystując liczby N oraz J. Na przykład, aby przesłać tekst ANNA:

1. Zamień go na tekst kodowany cyframi, korzystając z podanej wyżej tabeli:

01 14 14 01

2. Podnieś każdą z liczb do potęgi J = 3:

1³ 14³ 14³ 1³, czyli 1 2744 2744 1

3. Oblicz reszty z dzielenia przez N = 33:

1 5 5 1

4. Wyślij przekaz, zapisując każdą z liczb za pomocą dwóch cyfr podobnie, jak w tabeli:

01050501

Odbiorca odszyfrowuje ten tekst, wykorzystując liczby N oraz T.

1. Rozbij otrzymany tekst 01050501 na bloki dwucyfrowe:

01 05 05 01

2. Podnieś każdą z liczb do potęgi T = 7:

1⁷ 5⁷ 5⁷ 1⁷, czyli 1 78125 78125 1

3. Oblicz reszty z dzielenia przez N = 33:

01 14 14 01

4. Zamień go na tekst literowy: A N N A.

W powyższym przykładzie nadawca musi znać liczby N = 33 oraz J = 3. Te dwie liczby tworzą tzw. klucz jawny, czyli publiczny. Odbiorca zna N = 33 oraz T = 7. Te dwie liczby tworzą tajny klucz prywatny. Oczywiście tajna jest tylko liczba T.

Żaden szyfr oparty na kodowaniu pojedynczych liter nie może być bezpieczny, bo można go złamać, analizując częstości występujących w nim liter. Ten problem rozwiązuje się, zastępując pojedyncze litery blokami liter. Na przykład:

AA-001 AB-002 AC-003 AD-004 ... AK-011 AL-012

AM-013 AN-014 ...NA-352 NB-353 ... ZY-675 ZZ-676

Wybierzmy liczby pierwsze p oraz q tak, aby N = pq było liczbą większą niż największy kod, czyli N > 676. Możemy wybrać na przykład p = 23, q = 31. Wówczas N = 713, j (N) = 22 · 30 = 660. Przyjmijmy J = 59, T = 179. Można sprawdzić, że 59 · 179 = 1 mod 660.

Tym razem, opisując procedurę szyfrowania i odczytywania połączymy w jeden krok potęgowanie i obliczanie reszty. Wkrótce wyjaśni się, dlaczego.

Aby przesłać tekst ANNA:

1. Zamień bloki dwuliterowe AN NA na kody cyfrowe:

014 352

2. Podnieś kody do potęgi J = 59 i oblicz resztę z dzielenia przez N = 713:

14⁵⁹ mod 713 = 454 352⁵⁹ mod 713 = 451

3. Wyślij przekaz: 454451

Aby odczytać przekaz korzystamy z tajnego klucza T = 179 oraz N = 713:

1. Rozbij otrzymany przekaz 454451 na bloki trzycyfrowe:

454 451

2. Podnieś kolejne liczby do potęgi T = 179 i znajdź resztę z dzielenia przez N = 713:

454¹⁷⁹ mod 713 = 014 451¹⁷⁹ mod 713 = 352

3. Korzystając z tabeli, zamień kod cyfrowy 014 352 na tekst jawny: AN NA.

Na płycie CD przeprowadzone są rachunki w przypadku, gdy tekst dzielony jest na bloki trzyliterowe. W rzeczywistych zastosowaniach tekst dzielony jest na bloki złożone z kilkudziesięciu liter.

Gdy przechodzimy do dużych liczb, pojawiają się techniczne problemy szyfrowania. Nawet najlepszy kalkulator nie potrafi wykonać dokładnie potęgowania, o którym mowa, gdy korzystamy z klawisza [^]. Ale reszty z dzielenia nawet bardzo dużych potęg, jak na przykład 14⁵⁹ mod 713 możemy obliczać nawet na zwykłym kalkulatorze. Zauważ, że kolejne potęgi x obliczamy albo podnosząc poprzednią potęgę do kwadratu – na przykład x⁶ = (x³)², albo mnożąc ją przez x - na przykład x³ = x²x.

Potęga x Wynik

Z kolei odbiorca w podobny sposób obliczy, że 454¹⁷⁹ mod 713 = 14.

Każde takie potęgowanie sprowadza się do podnoszenia do kwadratu lub mnożenia odpowiednich reszt dzięki czemu unikamy rachunków na bardzo dużych liczbach. Poza tym w przypadku dużych wykładników jest o wiele szybsze. Na przykład, aby obliczyć

454^1048576 mod 713

wystarczy dwadzieścia razy powtórzyć operację: podnieś do kwadratu i oblicz resztę.

Przyjrzyjmy się teraz sytuacji prawdziwej, gdy mowa jest o liczbach dużo większych.

Każdy użytkownik ma swój klucz złożony z trzech liczb: N = pq, oraz J i T spełniających warunek

JT = 1 mod (p – 1)(q –1).

Klucz ten można wygenerować za pomocą wielu programów, na przykład za pomocą przeglądarki internetowej. Klucz publiczny, tzn. liczby N oraz J można udostępnić za pośrednictwem strony internetowej. Liczba T pozostaje tajna. Zauważ, że powszechnie dostępna jest liczba N, ale nie jej rozkład na czynniki.

W zastosowaniach liczby pierwsze p, q są ogromnymi liczbami – rzędu 150 cyfr. Znane są szybkie algorytmy, które pozwalają rozstrzygnąć, czy dana liczba tej wielkości jest pierwsza czy nie.

Istnieją metody generowania liczb pierwszych żądanej wielkości. Po wygenerowaniu liczb pierwszych p, q oblicza się N = pq oraz j (N) = (p – 1)(q – 1). Następnie wybiera się losowo J względnie pierwsze z j (N) i znajduje T takie, aby JT = 1 mod j (N). Takie T można znaleźć dość szybko, korzystając z algorytmu Euklidesa.

Dłuższy tekst dzielony na bloki dwu albo trzyliterowe złamać jest bardzo łatwo. Na przykład w języku angielskim szczególnie często pojawiać się będą układy THE, AND itd. Przy podziale na bloki praktykowanym w rzeczywistych zastosowaniach tekst dzielony jest na bloki na tyle długie, iż żadna analiza częstości nie wchodzi w rachubę.

Teoretycznie szyfr ten może być złamany inaczej. Skoro liczby N oraz J są znane, to można rozłożyć N na czynniki p, q, obliczyć j (N), a następnie znaleźć T. Ale w rzeczywistości N wybierane jest tak, że rozkład na czynniki nie jest możliwy do przeprowadzenia w realistycznym czasie. A póki nie rozłożymy N na czynniki, nie znamy wartości j (N), a więc nie potrafimy znaleźć T.

Zwróć uwagę, że chociaż rozkład na czynniki pierwsze jest dla dużych liczb zadaniem bardzo trudnym, nawet dla najszybszych superkomputerów, to komputery mogą dość łatwo generować duże liczby pierwsze.

Na zakończenie zwróćmy uwagę, że nasz opis działania RSA zawiera jeszcze jedno zasadnicze uproszczenie. W praktyce długie teksty szyfrowane są za pomocą technik bardziej tradycyjnych, a RSA służy wyłącznie do zaszyfrowania informacji o tym, jak zaszyfrowano główny tekst.

Jednym z zastosowań RSA jest podpis elektroniczny, czyli taki element listu, który pozwala odbiorcy, np. bankowi być pewnym, że list pochodzi od właściwego nadawcy. Zilustrujemy to za pomocą najprostszego RSA, od którego zaczęliśmy.

Załóżmy zatem, że p = 3, q = 11, N = 33, j (N) = 20. Klucz jawny Jacka, to N = 33, J = 3, tajny T = 7. Przypuśćmy, że Jacek chce dokonać przelewu miliona ze swojego konta na konto Placka. Wyobraźmy sobie, że w tym celu wysyła do banku zwykły list zawierający to polecenie, ze zwykłym podpisem:

WYPLACIĆ PLACKOWI MILION. JACEK.

Takie polecenie musi być jakoś uwiarygodnione. Jacek może to zrobić, dołączając swój podpis zaszyfrowany jego kluczem prywatnym. Mamy: JACEK = 10 01 03 05 11. Po zakodowaniu kluczem prywatnym T=7, N=33 otrzymujemy

10⁷ mod 33 1⁷ mod 33 3⁷ mod 33 5⁷ mod 33 11⁷ mod 33

czyli 10 1 9 14 11.

Zwykły podpis JACEK mówi bankowi, kto jest nadawcą. Dodatkowy podpis zaszyfrowany

10 1 9 14 11 pozwoli sprawdzić, czy list rzeczywiście pochodzi od nadawcy. Bank znajdzie jawny klucz Jacka i odszyfruje podpis. Jeżeli otrzyma napis JACEK, to przekona się, iż nadawcą naprawdę jest Jacek. Ponieważ nikt nie może odszyfrować tajnego kodu Jacka, więc nikt też nie może się pod niego podszyć.

Okazuje się jednak, że to najprostsze rozwiązanie nie spełnia wszystkich wymogów bezpieczeństwa. Wymagany prawem podpis elektroniczny zbudowany jest na podobnej zasadzie, ale zawiera dodatkowe elementy, uniemożliwiające jego podrobienie.

Matematyczną podstawą RSA są twierdzenia teorii liczb, dyscypliny uchodzącej przez ponad 2000 lat za piękną, ale bezużyteczną. Najważniejszym wykorzystywanym tu twierdzeniem jest następujące twierdzenie Eulera:

Niech j (n) oznacza ilość liczb pierwszych mniejszych od n i względnie pierwszych z n, niech a będzie liczbą względnie pierwszą z n. Wówczas

= 1 mod n.

Dowód tego twierdzenia w zasadzie nie wykracza poza matematykę szkolną. Można go znaleźć w wielu książkach poświeconych teorii liczb.

Mnożąc obie strony tej równości przez a, otrzymujemy

(*) = a mod n.

Można wykazać, że ta równość zachodzi dla każdej liczby a, także mającej wspólne dzielniki z j (N).

Gdy N = pq, gdzie p oraz q są liczbami pierwszymi, to j (N) = (p – 1)(q – 1). Jeżeli zatem

JT = 1 mod (p – 1)(q – 1),

to JT = 1 + k(p – 1)(q – 1) dla pewnego k. A wówczas

a^JT = a^{1 + k(p – 1)(q – 1)} = a · a^k(p – 1)(q – 1) = a · (a^{(p – 1)(q – 1)})^k = a · 1^k = a · 1 = a mod N.

Z własności potęgowania wynika zatem, że dla dowolnego a (dowolnego cyfrowego kodu odpowiadającego literze czy blokowi) mamy

(a^J)^T mod N = a oraz (a^T)^J mod N = a.

Widzimy zatem, że gdy jeden klucz szyfruje, drugi odszyfrowuje.

Zadania

1. W latach trzydziestych XX wieku grupa polskich kryptologów złamała szyfr niemieckiej maszyny szyfrującej ,,Enigma". Ich osiągnięcie wpłynęło na przebieg i przyspieszyło zakończenie II wojny światowej. Nazwisko człowieka, który opracował matematyczną metodę złamania tego szyfru zapisaliśmy poniżej, stosując pewną wersję szyfru Cezara i litery alfabetu łacińskiego. Jak brzmi nazwisko tego matematyka?

JXOFXK OBGBTPHF

2. Znajdź klucz prywatny, gdy klucz publiczny stanowią liczby N= 91 oraz J = 29.

3. Przekaz 172401 to pewien tekst zaszyfrowany za pomocą klucza publicznego N=55, J=27, przy czym zastosowano kodowanie pojedynczych liter. Znajdź klucz tajny i rozszyfruj ten przekaz.

4.* Wiedząc, że N=pq jest iloczynem dwóch liczb pierwszych, znajdź p oraz q, gdy:

a) N= 7387 i j (N) = 7216; b)* N=466 883 i j (N) =465 480.