naszych tajemnic
Witold Kraśkiewicz, Andrzej Sendlewski
1. Szyfr Cezara
Już w czasach starożytnych próbowano zapisywać ważne informacje
w taki sposób, aby były nieczytelne dla osób, które nie powinny ich po-
znać (np. wrogowie). Do historii przeszedł sposób szyfrowania tekstów
pochodzący od Juliusza Cezara wykorzystujący arytmetykę „zegaro-
wą”. Wyobraźmy sobie, że wszystkie litery alfabetu umieszczono na
tarczy zegara. Szyfrowanie polega na zastąpieniu każdej litery wystę-
pującej w przesyłanej informacji literą znajdującą się dalej na zegarze
o pewną z góry ustaloną liczbę miejsc (wtedy litery z końca alfabetu
zastępowane są odpowiednimi literami z początku alfabetu). Zilustruj-
my tę metodę nieco zmodyfikowaną o szyfrowanie także znaku odstępu
między wyrazami.
Przykład 1. Dla prostoty załóżmy, że informacje będziemy zapi-
sywali tylko dużymi literami alfabetu łacińskiego bez polskich znaków
takich jak: Ą, Ł, Ś, itp., a słowa będziemy oddzielali znakiem odstę-
pu (spacji). Rozmieśćmy wszystkie znaki na tarczy zegara (rysunek 1).
Szyfrując sposobem Cezara tekst
WAKACJE Z KANGUREM
ze skokiem 16 otrzymujemy następującą zaszyfrowaną postać
LQ QSZUPOP QCWJGUB
1
2
A
Y Z
B
X
C
W
D
V
E
U
F
T
G
S
H
R
I
Q
J
K
P O
L
N M
Rysunek 1. „Zegar znaków”.
Oczywiście, aby odszyfrować ten tekst wystarczy w nim każdy znak za-
stąpić odczytanym z tarczy zegara znakiem stojącym 16 pozycji wcze-
śniej (cofnąć się o 16 pozycji).
Jeżeli ponumeryjemy nasze znaki zgodnie z poniższą tabelką
numer 0 1 2 3 4 5 6 7 8 9 10 . . . 24 25 26
znak
A B C D E F G H I J . . . X Y Z
to problem szyfrowania i odszyfrowywania sprowadza się do określenia
dwóch funkcji liczbowych o dobrych własnościach przekształcających
zbiór reszt Z27 = { 0 , 1 , 2 , 3 , . . . 26 } w siebie: funkcji szyfrującej C i funkcji deszyfrującej D, takich aby dla każdego x ∈ Z27 zachodziła konieczna do prawidłowego odszyfrowania równość
D( C( x)) = x.
W naszym przykładzie funkcje te zadane są wzorami:
C( x) = ( x + 16) mod 27
i
D( x) = ( x − 16) mod 27 .
Użyty w powyższym wzorze symbol „ b mod n” oznacza resztę z dzielenia liczby całkowitej b przez liczbę naturalną n, tj. jedyną liczbę a taką, że 0 6 a < n i b = k · n + a dla pewnego całkowitego k . Funkcje C i D
spełniają dla każdego x ∈ Z27 dwie równości
D( C( x)) = x i C( D( x)) = x, czyli są wzajemnie odwrotne.
Pomijając oczywistą prostotę przedstawionego sposobu szyfrowania
(łatwo go złamać) zauważmy, że ma on jeszcze następującą cechę: jeśli
wiemy z jakim skokiem zaszyfrowaliśmy tekst (jak obliczamy wartości
funkcji C), to natychmiast wiemy, jak go odszyfrować (jak obliczać war-tości funkcji D). W epoce elektronicznych informacji przesyłanych na
odległość jest to duża wada, gdyż nie można tą drogą przekazać żadnej
informacji o sposobie szyfrowania, pozostaje przekazywać tego typu in-
formacje innym tajnym kanałem, np. za pomocą kuriera. Problem ten
znalazł rozwiązanie w systemach szyfrowania z kluczem publicznym.
2. System kryptograficzny z kluczem publicznym
Aby zrozumieć ideę kryptografii z kluczem publicznym, wyobraźmy
sobie szyfrowanie jako zamykanie wiadomości w pewnym bezpiecznym
opakowaniu. W kryptografii tradycyjnej rzecz wygląda mniej więcej
tak. Nadawca i odbiorca wiadomości mają klucze do pewnej szkatuł-
ki (systemu szyfrowania). Nadawca umieszcza wiadomość w szkatułce
i zamyka swoim kluczem. Odbiorca po otrzymaniu szkatułki otwiera
ją swoim kluczem, wyjmuje wiadomość i odczytuje. Jeżeli nikt poza
tymi dwoma osobami nie ma klucza do szkatułki, to w drodze mię-
dzy nadawcą a odbiorcą wiadomość jest bezpieczna. Nikt nie może jej
niepostrzeżenie przeczytać. Takie podejście wymaga, aby ktoś zawcza-
su dostarczył obu zainteresowanym stronom identycznych kluczy. Obie
strony muszą przechowywać swoje klucze aż do chwili, gdy zechcą wy-
mienić między sobą wiadomość. Co więcej, muszą w tym czasie chronić
klucze, aby nikt nie mógł ich ukraść lub skopiować. Jeśli spodziewamy
się wymieniać w przyszłości wiadomości z wieloma respondentami, pęk
potrzebnych nam kluczy może być całkiem spory.
Zupełnie inaczej wyglądałaby sytuacja, gdyby szkatułki zabezpie-
czające wiadomości miały zamki zatrzaskowe: nadawca wkładałby swo-
ją wiadomość do odpowiedniej skrzynki i zatrzaskiwał wieczko. Odbior-
ca otwierałby szkatułkę swoim kluczem. W ten sposób każdy musiałby
chronić jedynie swój własny klucz.
Niestety takiego systemu nie da się zbudować. Dlaczego? Przypo-
mnijmy, że w naszym modelu klucz reprezentuje informację potrzebną
do zaszyfrowania lub odszyfrowania wiadomości. Aby wiadomość za-
szyfrować, musimy wiedzieć, jak to zrobić.
Wyobraźmy sobie jednak, że do zamykania szkatułki służy inny
klucz niźli do otwierania i mając jeden z tych kluczy nie można od-
tworzyć drugiego (w dawnych wiekach tego typu zamki rzeczywiście
wytwarzano). Gdyby udało się taki system zrealizować, można by klucz
do zamykania przechowywać w ogólnie dostępnym miejscu, tak by każ-
dy zainteresowany mógł go użyć do zamknięcia szkatułki.
Czy taki model można zrealizować? Jeżeli odbiorca ma odczytać
wiadomość, to operacja szyfrowania musi być odwracalna, a skoro wie-
my jak szyfrować, to wystarczy odwrócić ten proces, by mieć procedurę
deszyfrowania. Jest jednak zasadnicza różnica pomiędzy wiedzą, że coś
istnieje, a praktyczną umiejętnością znalezienia tego! Przyjrzyjmy się
następującemu przykładowi. Liczby p = 2011 i q = 3761 są pierwsze.
Weźmy liczbę n = pq. Oczywiście liczba p jest mniejszym czynnikiem pierwszym liczby n, a q jest większym czynnikiem pierwszym tej liczby.
Czy jednak wiedząc, że n = 7563371 jesteśmy w stanie efektywnie wy-
znaczyć p i q? Dysproporcja pomiędzy nakładem pracy potrzebnym do wymnożenia dwóch liczb i rozłożenia liczby na czynniki pierwsze stała
się podstawą bezpieczeństwa jednego z najbardziej rozpowszechnionych
kryptosystemów z kluczem publicznym – systemu RSA.
3. System RSA
Twórcami kryptosystemu RSA są Ronald L. Rivest, Adi Shamir i
Leonard Adleman (zobacz [2]). Nazwa systemu powstała z pierwszych
liter ich nazwisk. Na czym cały pomysł polega? Załóżmy, że elemen-
tami, które mają być szyfrowane są liczby ze zbioru Z . Możemy tak
n
uczynić, gdyż jak to już wcześniej zauważyliśmy, znaki albo lepiej całe
układy znaków dopuszczalnych (występujących w informacjach) może-
my ponumerować.
Postąpmy według następującej procedury.
1. Wybierzmy (najlepiej losowo) dwie duże liczby pierwsze p i q.
2. Obliczmy n = pq.
3. Wybierzmy liczbę e względnie pierwszą z ( p − 1)( q − 1).
4. Wyznaczmy liczbę całkowitą d, 0 6 d < ( p − 1)( q − 1) taką, że ed mod ( p − 1)( q − 1) = 1.
5. Udostępnijmy parę ( n, e) jako nasz klucz publiczny RSA.
6. Zachowajmy w tajemnicy parę ( n, d) jako nasz klucz tajny
RSA.
Funkcję szyfrującą odpowiadającą kluczowi publicznemu ( n, e) określa-
my wzorem
(1)
C( x) = xe mod n,
a funkcję deszyfrującą odpowiadającą kluczowi tajnemu ( n, d) – wzo-
rem
(2)
D( x) = xd mod n.
Ze względu na te wzory liczby e i d nazywa się odpowiednio wykładni-kiem publicznym i prywatnym.
Próbę uzasadnienia, że opisana procedura da się zrealizować, a otrzy-
mane funkcje C i D są wzajemnie odwrotne, chwilowo odłóżmy. Spró-
bujmy przekonać się na przykładzie z paragrafu pierwszego, że wszystko
działa jak należy.
Przykład 2. Posłużmy się opisaną procedurą dla liczb p = 5 i
q = 11. Wtedy n = pq = 55 i ( p − 1)( q − 1) = 4 · 10 = 40. Za e weźmy liczbę 7. Oznacza to, że kluczem publicznym w tym przykładzie jest
para (55 , 7). Zaszyfrujmy nasz tekst
WAKACJE Z KANGUREM
Po uwzględnieniu przyjętej przez nas numeracji znaków zadanie to jest
równoznaczne z zakodowaniem ciągu liczb (liczby oddzielamy dwukrop-
kiem)
23:01:11:01:03:10:05:00:26:00:11:01:14:07:21:18:05:13.
Wykonujemy niezbędne obliczenia, które będą niestety wymagały od
nas trochę sprytu i wysiłku. Aby obliczyć C(23) = 237 mod 55, może-
my oczywiście wykonać działania w zapisanej kolejności czyli obliczyć
najpierw potęgę, a następnie znaleźć resztę z dzielenia. Takie postępo-
wanie prowadzi jednak do dużych wyników pośrednich i w przypadku
dużych argumentów może okazać się zbyt kłopotliwym nawet dla kom-
putera. Możemy tego uniknąć, korzystając z następującego, łatwego do
udowodnienia wzoru:
ab mod n = (( a mod n) · ( b mod n)) mod n, czyli zamiast liczyć resztę z dzielenia iloczynu ab przez n, możemy najpierw obliczyć reszty z dzielenia poszczególnych czynników przez n,
następnie obliczyć ich iloczyn i wziąć jego resztę. Na pierwszy rzut oka
prawa strona wzoru może wydawać się bardziej skomplikowana niż le-
wa strona, ale w rzeczywistości pozwala uprościć rachunki. Przyjrzyjmy
się, jak to działa w interesującym nas przypadku.
Obliczamy najpierw
232 mod 55 = 529 mod 55 = 34
oraz
234 mod 55 = (232 · 232) mod 55 =
= ((232 mod 55) · (232 mod 55)) mod 55 =
= 342 mod 55 = 1156 mod 55 = 1 ,
a następnie
237 mod 55 = 234+2+1 mod 55 =
= ((234 mod 55) · (232 mod 55) · 23) mod 55 =
= (1 · 34 · 23) mod 55 = 782 mod 55 = 12 .
W ten sposób do obliczenia siódmej potęgi modularnej wystarczają
nam cztery mnożenia, w których wszystkie czynniki są resztami i cztery
operacje znajdowania reszty.
Obliczając w ten sposób pozostałe potęgi, mamy:
C(23) = 237 mod 55 = 12 ,
C(01) = 17 mod 55 = 1 ,
C(11) = 117 mod 55 = 11 ,
C(03) = 37 mod 55 = 42 ,
C(10) = 107 mod 55 = 10 ,
C(05) = 57 mod 55 = 25 ,
C(00) = 07 mod 55 = 0 ,
C(26) = 267 mod 55 = 16 ,
C(14) = 147 mod 55 = 9 ,
C(07) = 77 mod 55 = 28 ,
C(21) = 217 mod 55 = 21 ,
C(18) = 187 mod 55 = 17 ,
C(13) = 137 mod 55 = 7 .
Zatem ciąg po zakodowaniu (szyfrogram) wygląda następująco:
12:01:11:01:42:10:25:00:16:00:11:01:09:28:21:17:25:07 .
Naszym kluczem tajnym jest para (55 , 23), gdyż
7 · 23 = 161 = 4 · 40 + 1 = 1 .
Zdekodujmy otrzymany ciąg. Tym razem musimy obliczać potęgi o wy-
kładniku 23. Jeśli użyjemy poprzedniej metody, to rachunki będą nie-
wiele trudniejsze. Metodę zilustrujemy na przykładzie piątej liczby w
szyfrogramie.
Aby obliczyć 4223 mod 55, liczymy pomocniczo:
422 mod 55 = 1764 mod 55 = 4 ,
424 mod 55 = (422 mod 55)2 mod 55 =
= 42 mod 55 = 16 mod 55 = 16 ,
428 mod 55 = (424 mod 55)2 mod 55 =
= 162 mod 55 = 256 mod 55 = 36 ,
4216 mod 55 = (428 mod 55)2 mod 55 =
= 362 mod 55 = 1296 mod 55 = 31 .
Mamy teraz
4223 mod 55 =
= 4216+4+2+1 mod 55 =
= ((4216 mod 55) · (424 mod 55) · (422 mod 55) · 42) mod 55 =
= (31 · 16 · 4 · 42) mod 55 =
= ((31 · 16) mod 55) · ((4 · 42) mod 55) mod 55 =
= ((496 mod 55) · (168 mod 55)) mod 55 = 3 ,
co odpowiada literze C ze słowa WAKACJE. Jeśli wykonasz podobny
rachunek dla pozostałych liczb tworzących szyfrogram, to przekonasz
się, że opisana metoda deszyfrowania faktycznie prowadzi do odczytania
zaszyfrowanej wiadomości.
Wykonajmy jeszcze raz to samo zadanie za pomocą systemu wyko-
rzystującego znacznie większe liczby pierwsze.
Przykład 3. Niech p = 521 i q = 1031. Wtedy n = pq = 537151
i ( p − 1)( q − 1) = 520 · 1031 = 535600. Za e weźmy ponownie liczbę 7, która jest względnie pierwsza z 535600. Kluczem publicznym jest
więc para (537151 , 7). Aby obliczyć klucz tajny, musimy znaleźć licz-bę d taką że reszta z dzielenia iloczynu 7 d przez 535600 jest równa 1. Problem jak efektywnie obliczyć d odłóżmy do następnego rozdzia-
łu. Tu zanotujmy jedynie, że za d można przyjąć liczbę 229543, gdyż
7 · 229543 = 1606801 = 3 · 535600 + 1. Oznacza to, że kluczem tajnym jest para (537151 , 229543). Ponieważ dysponujemy znacznie większy-mi liczbami, będziemy szyfrować nie numery poszczególnych znaków, a
numery grup liter utworzonych z trzech kolejnych znaków. Dla naszego
napisu musimy zatem zakodować następujący ciąg liczb:
230111:010310:050026:001101:140721:180513.
Wykonując odpowiednie obliczenia przy pomocy komputera, otrzymu-
jemy taki oto ciąg liczb:
286010:071139:150495:115929:017055:391587.
Jego dekodowanie według opisanej wyżej procedury także prowadzi do
ciągu wyjściowego.
4. Poprawność RSA
Światem matematycznym, w którym funkcjonuje system RSA jest
arytmetyka modularna czyli arytmetyka reszt. Pewne jej własności mie-
liśmy okazję poznać już wcześniej, teraz zbadamy je bardziej systema-
tycznie. Naszym celem będzie pokazanie, że przedstawiona konstrukcja
systemu jest wykonalna i poprawna. Jedynym punktem konstrukcji,
którego wykonalność może budzić wątpliwości jest problem znalezienia
prywatnego wykładnika d „pasującego” do obranego klucza publiczne-
go.
Zadanie to można postawić w nieco ogólniejszej postaci. Załóżmy, że
mamy daną liczbę m oraz liczbę e względnie pierwszą z n. Szukamy liczby d takiej, że iloczyn ed przy dzieleniu przez m daje resztę 1. Szybkim i prostym sposobem obliczenia d jest tak zwany rozszerzony algorytm
Euklidesa. Przypomnijmy, że algorytm Euklidesa jest efektywnym spo-
sobem na wyliczenie największego wspólnego dzielnika dwóch liczb a
i b i sprowadza się do obliczania kolejnych reszt z dzielenia. Największym wspólnym dzielnikiem jest ostatnia niezerowa reszta. Na przykład
obliczenie NWD(5133 , 944) przebiega następująco:
5133 = 5 · 944 + 413 ,
944 = 2 · 413 + 118 ,
413 = 3 · 118 + 59 ,
118 = 2 · 59 + 0 ,
co daje nam NWD(5133 , 944) = 59. Ten sposób obliczenia NWD można
z powodzeniem zastosować do nawet bardzo dużych liczb. Jego główną
zaletą jest to, że nie musimy znać rozkładu liczb na czynniki pierwsze.
Jest jeszcze jedna zaleta: za jego pomocą możemy udowodnić następu-
jące ważne twierdzenie.
Twierdzenie 1. Jeśli d = NWD( a, b) , to istnieją liczby całkowite k i ℓ takie że d = ka + ℓb.
Liczby k i ℓ, o których mowa w twierdzeniu, można znaleźć, odwra-cając rachunki wykonane do obliczenia NWD. Zilustrujmy to na po-
przednim przykładzie. Zacznijmy od przekształcenia powyższych rów-
ności tak, aby po lewej stronie znalazły się kolejne reszty:
413 = 1 · 5133 + ( − 5) · 944 ,
118 = 1 · 944 + ( − 2) · 413 ,
59 = 1 · 413 + ( − 3) · 118 ,
a następnie rozpoczynając od ostatniej równości cofajmy się w rachun-
kach, podstawiając kolejne reszty. Pamiętajmy przy tym, że nie chodzi
nam o wartość liczbową, a o przedstawienie znanej liczby w pewnej
specjalnej postaci (rachunek wygląda tak, jakbyśmy traktowali reszty
jako symbole algebraiczne i interesowali się jedynie stojącymi przy nich
współczynnikami):
59 = 1 · 413 + ( − 3) · 118 =
= 1 · 413 + ( − 3)(1 · 944 + ( − 2) · 413) =
= ( − 3) · 944 + 7 · 413 =
= ( − 3) · 944 + 7 · (1 · 5133 + ( − 5) · 944) =
= ( − 38) · 944 + 7 · 5133 .
Jeśli więc a = 944 i b = 5133, to za liczby k i ℓ, o których mowa w twierdzeniu, można wziąć odpowiednio − 38 i 7. Zapewne teraz do-myślasz się już, jak znaleźć wykładnik prywatny d: należy po prostu
zastosować rozszerzony algorytm Euklidesa do liczb e i ( p − 1) ∗ ( q − 1).
Powróćmy do przykładu 3. Mamy tu e = 7 i ( p − 1)( q − 1) = 535600.
Sprawdźmy najpierw, że liczby te rzeczywiście są względnie pierwsze,
obliczając NWD(535600 , 7). Mamy
535600 = 76514 · 7 + 2 ,
7 = 3 · 2 + 1 ,
2 = 2 · 1 + 0 ,
co dowodzi względnej pierwszości, a jednocześnie pozwala obliczyć licz-
bę d. Mamy bowiem
1 = 1 · 7 + ( − 3) · 2 =
= 1 · 7 + ( − 3) (1 · 535600 + ( − 76514) · 7) =
= ( − 3) · 535600 + 229543 · 7 ,
co daje
7 · 229543 = 1 + 3 · 535600 .
Skoro wykonalność konstrukcji już nie budzi zastrzeżeń, możemy
przystąpić do dowodu jej poprawności, tj. wykazania, że dla wszelkich
układów liczb spełniających założenia procedury, wzory (1) i (2) rzeczy-
wiście definiują funkcje wzajemnie odwrotne. W tym miejscu wygodnie
będzie nam posłużyć się pojęciem relacji kongruencji liczb całkowitych i pewnymi jej własnościami. Dowody potrzebnych faktów nie są zbyt
skomplikowane ale wymagają dłuższego wywodu (można je znaleźć w
dowolnej monografii z teorii liczb, zobacz np. [3]).
Mówimy, że liczba całkowita a przystaje do liczby całkowitej b modulo liczba naturalna m, jeśli reszty z dzielenia tych liczb przez m są równe (równoważnie różnica a − b jest podzielna przez m). Zależność tę zapisujemy symbolicznie
a ≡ b (mod m) .
Zauważmy, że każda liczba całkowita a przystaje modulo m do jednej i tylko jednej liczby x ∈ Z (swojej reszty z dzielenia przez
m
m) i wła-
śnie wtedy piszemy x = a mod m. Ponadto, natychmiast z określenia wynika, że dla wszelkich liczb całkowitych a, b, c i d zachodzą: a ≡ a (mod m) ,
jeśli a ≡ b (mod m) , to b ≡ a (mod m) , jeśli a ≡ b (mod m) i b ≡ c (mod m) , to a ≡ c (mod m) , jeśli a ≡ b (mod m) i c ≡ d (mod m) , to a + c ≡ b + d (mod m) , jeśli a ≡ b (mod m) i c ≡ d (mod m) , to ac ≡ bd (mod m) .
Wyliczanie niezbędnych faktów zacznijmy od następującego twier-
dzenia, które jest prostą konsekwencją jednoznaczności rozkładu na
czynniki pierwsze.
Twierdzenie 2. Jeżeli p i q są różnymi liczbami pierwszymi, to dla dowolnych liczb całkowitych a i b
a ≡ b (mod pq)
wtedy i tylko wtedy, gdy
a ≡ b (mod p)
i
a ≡ b (mod q) .
Podstawowe znaczenie dla konstrukcji systemu RSA ma następne
twierdzenie zwane małym twierdzeniem Fermata.
Twierdzenie 3. Dla dowolnej liczby pierwszej p i dowolnej liczby
całkowitej a, jeżeli p nie dzieli a, to
ap− 1 ≡ 1 (mod p) .
Te dwa twierdzenia pozwalają udowodnić poprawność algorytmu
RSA.
Twierdzenie 4. Funkcje C i D określone wzorami (1) i (2) są wzajemnie odwrotne.
Dowód. Z wzorów (1) i (2) wynika, że dla dowolnego x ∈ Z za-
n
chodzą równości
D( C( x)) = C( D( x)) = xed mod n.
Ponieważ ed przy dzieleniu przez ( p − 1)( q − 1)) daje resztę 1, więc ed = 1 + k( p − 1)( q − 1)
dla pewnego całkowitego k.
Załóżmy na początek, że p nie dzieli x. Wówczas na mocy twierdzenia Fermata
xp− 1 ≡ 1 (mod p) .
Podnosząc kongruencję stronami do odpowiedniej potęgi, mamy
xp− 1 k( q− 1) ≡ 1 (mod p) ,
co po przemnożeniu przez x daje
x xp− 1 k( q− 1) ≡ x (mod p) .
Ale
x xp− 1 k( q− 1) = x 1+ k( p− 1)( q− 1) = xed.
Stąd otrzymujemy
xed ≡ x (mod p) .
Ostatnia kongruencja pozostaje prawdziwa także wtedy, gdy p dzieli x, bo wówczas przez p podzielne są obie jej strony. Udowodniliśmy więc, że dla każdego x ∈ Z zachodzi
n
xed ≡ x (mod p) .
Analogicznie wykazujemy, że
xed ≡ x (mod q)
(role p i q są symetryczne). Warunki te na mocy twierdzenia 2 są równoważne warunkowi
xed ≡ x (mod n) ,
co dowodzi, że xed mod n = x.
5. Bezpieczeństwo
Spróbujmy na zakończenie zastanowić się, jak duże jest bezpieczeń-
stwo szyfrowania z użyciem systemu RSA – jak dobrymi strażnikami są
liczby pierwsze? Oczywiście każdy system można złamać, jest to jedy-
nie kwestia czasu i poniesionych nakładów. Jeśli nakłady potrzebne do
złamania wielokrotnie przewyższają wartość chronionych tajemnic, to
system uważamy za bezpieczny. Bezpieczeństwo systemu RSA opiera się
na trudności rozkładania na czynniki dużych liczb. Jeśli nasz przeciw-
nik (haker) potrafi rozłożyć na czynniki liczbę n, to może na podstawie znajomości wykładnika publicznego e i czynników p i q wyliczyć wy-kładnik prywatny d, dokładnie tak samo jak zrobiliśmy to w trakcie
tworzenia naszego systemu. Wniosek z tego płynie taki, że trudność
złamania kryptosystemu jest nie większa niż trudność rozkładu liczby
na czynniki pierwsze.
Czy można złamać system bez rozkładania modułu n na czynniki?
Na razie nikomu się to nie udało, mimo że wielu próbowało. Panuje
więc przekonanie, że nie da się tego zrobić, choć nikomu nie udało się
też udowodnić, że jest to niemożliwe.
Pozostaje więc kwestia trudności zadania rozkładu liczby na czyn-
niki pierwsze. Intuicyjnie rozumiemy, że im większe liczby pierwsze p
i q tym trudniej rozłożyć liczbę n na czynniki, a co za tym idzie, tym większe bezpieczeństwo systemu. Dokładniej zależność tę bada teoria
matematyczna zwana teorią złożoności obliczeń. Z drugiej strony im
większe parametry systemu, tym większych nakładów pracy wymaga
szyfrowanie i deszyfrowanie. Teoria złożoności pozwala nam osiągnąć
rozsądny kompromis pomiędzy tymi wielkościami. Obecnie uważa się,
że jako p i q należy wybierać liczby piersze o setkach cyfr dziesiętnych.
Na koniec należy podkreślić, że w powyższym artykule byliśmy w
stanie nakreślić jedynie ogólną ideę kryptosystemu RSA. Aby cały sys-
tem był bezpieczny, musimy zadbać o całą masę szczegółów. Okazuje się
na przykład, że wykładniki d i e muszą być dostatecznie duże, a nawet sposób przekształcania wiadomości w liczbę musi być dobrany bardzo
starannie. Wszystko to jest owocem blisko trzydziestoletniego badania
systemu przez matematyków i praktyków. To że system przetrwał ten
zmasowany atak jest najlepszą rękojmią jego bezpieczeństwa.
Literatura
[1] R. L. Graham, D. E. Knuth, O. Ptashnik, Matematyka konkretna, PWN Warszawa, 2002.
[2] R. L. Rivest, A. Shamir, L. M. Adleman, A method for obtaining digital signa-tures and public-key cryptosystems, Communications of the ACM, 21(1978), str 120-126.
[3] W. Sierpiński, Arytmetyka teoretyczna, BM tom 7, PWN Warszawa, 1969.