772955442   623281635   379279823    352653218   71829568   466566719   545870045    363842058

Powyższy ciąg liczbowy, to zaszyfrowany tytuł niniejszej lekcji. Jeśli pod koniec lekcji będziesz potrafił go odszyfrować, to znaczy, że jesteś mistrzem szyfrowania.

Szyfrowanie jest dzisiaj niezbędnie, ponieważ coraz więcej osób korzysta z sieci komputerowych, szczególnie z Internetu. Tą drogą przekazywana jest bardzo duża liczba informacji dotyczących zakupów, operacji finansowych, decyzji menadżerskich, a nawet spraw prywatnych. Informacje te, aby dotrzeć do adresata, muszą w postaci plików krążyć w sieci i w związku z tym mogą zostać przechwycone i skopiowane, ale nie powinny dać się odczytać.

Sposobów szyfrowania jest bardzo dużo, jednak trudno wymyśleć miliony nowych sposobów dla wszystkich osób i instytucji, które chcą bezpiecznie korzystać z sieci. Przydałby się uniwersalny sposób szyfrowania, który byłby jednakowy dla wszystkich użytkowników, ale taki, aby dawał gwarancję bezpieczeństwa. I tu jest właśnie problem, jeśli bowiem sposób kodowania będzie wszystkim znany to, wydawałoby się, że zakodowaną informację będzie można, jakimś odwrotnym sposobem, odkodować.  Powstaje więc problem: czy jest możliwe, aby zaszyfrowana informacja była tajna, jeśli sposób szyfrowania jest wszystkim znany?

Odpowiedź jest pozytywna. Grupa uczonych - Ronald Rivest, Adi Shamir i Leonard Adleman z MIT (Massachusetts Institute of Technology) w Bostonie - wymyśliła taki właśnie sposób szyfrowania. W sposobie tym, nazywanym obecnie RSA (od pierwszych liter nazwisk tych uczonych), można ogłosić publicznie sposób szyfrowania i podać liczby zastosowane do szyfrowania, tzw. klucz publiczny, ale zaszyfrowanej informacji nikt nie potrafi odczytać. Do odszyfrowania potrzebny jest bowiem klucz prywatny, który każdy legalny użytkownik systemu otrzymuje tylko dla siebie i oczywiście nie powinien go nikomu udostępniać. 

Na końcu rozdziału podajemy teoretyczne podstawy szyfrowania metodą RSA.

Szyfrowanie

Wykonajmy szyfrowanie tekstu: Komputery i Matematyka.

Kodowanie pojedynczych liter K,o,m,p,u,t,e,r,y,i,M,a,t,e,m,a,t,y,k,a nie ma jednak sensu, ponieważ, przy ogłoszonym publicznie sposobie kodowania, łatwo dopasować kody do odpowiednich liter. Również kodowanie po dwie litery Ko,mp,ut,er,yi,Ma,te,ma,ty,ka , daje małą ilość różnych kombinacji kodów i również łatwo przygotować sobie tablicę deszyfrującą. Omówimy zatem szyfrowanie trzyliterowe, za pomocą tablicy kodów ASCII. W tym sposobie możemy otrzymać 255*255*255=16581375 różnych kodów. Prawdziwe szyfrowanie odbywa się segmentami dużo dłuższymi, dającymi tyle różnych kodów, że łamanie kodu, nawet za pomocą komputera, bez znajomości sposobu deszyfrowania, trwałoby lata.

Aby zaszyfrować dany tekst, najpierw należy zamienić trzyliterowe segmenty tekstu na liczby. Można to robić w dowolny sposób, np. zgodnie z tablicą ASCII. Program wykorzystuje tablicę bez polskich liter, więc zamiast ą, wpisuj a, zamiast ę, wpisuj e, itp.

Wpisz tekst: Komputery i Matematyka i naciśnij "Zamień na kody ASCII".

Kolejne, trzyliterowe segmenty tekstu zostały zamienione na następujące liczby:

Kom = 7116105, put = 7572847, ery = 7897196, _i_ = 6204245, Mat = 7567712, ema = 6335321, tyk = 6988646, a__ = 6201697.

Teraz następuje najważniejsza część kodowania. Załóżmy, że zostały ogłoszone dwie liczby szyfrujące: k  i   s. Sposób kodowania jest następujący: Kodem liczby N jest reszta z dzielenia potęgi N^s przez k, czyli wynik działania N^s mod k.

Wpisz do programu liczby szyfrujące: k = 948581743 i s = 4321 i naciśnij "Szyfruj".

Otrzymałeś następujące kody: 197807624, 726972629, 915338110, 934183720, 373901663, 499101762, 706315196, 119568560.

I to koniec, otrzymane liczby, to zaszyfrowany tekst Komputery i Matematyka.

Jak widać z powyższego opisu, proces szyfrowania jest bardzo łatwy i szybki, chociaż liczby kodowane, np. 4905289⁴³²¹ są niewyobrażalnie duże.

Deszyfrowywanie

Przejdźmy teraz do omówienia techniki deszyfrowania metodą RSA. Potrzebna jest do tego liczba deszyfrująca d. Jeśli jesteśmy legalnymi użytkownikami jakiegoś systemu szyfrującego, to otrzymujemy tę liczbę jako klucz prywatny. W tym przypadku, tzn. dla liczb szyfrujących: k = 948581743 i s = 4321 i jest to liczba d = 158050081 (Panel "Liczba deszyfrująca" nie jest więc w tej sytuacji potrzebny, wykorzystamy go do próby łamania szyfru, gdy nie będziemy znali liczby d).

Mając liczbę d, odszyfrujmy tekst kryjący się pod kodem 197807624 (pamiętamy, że powinno wyjść trzyliterowe słowo Kom). W tym celu obliczamy resztę z dzielenia potęgi kod^d przez k, czyli w naszym przypadku 197807624^158050081 mod 948581743.

Wpisz do dolnego panelu:
odpowiednie liczby i naciśnij "Oblicz".

Otrzymałeś 7116105. Jest to kod ASCII szukanego słowa. Aby wiedzieć, jakie reprezentuje on słowo, wpisz ten kod do panelu
i naciśnij "Zamień".

Otrzymałeś słowo Kom. Tym sposobem można odszyfrować pozostały tekst. Program nie zawiera mechanizmu automatycznego odszyfrowywania całego zdania, więc trzeba to robić ręcznie dla każdej liczby. Sprawdź, że przedostatni kod 706315196, to słowo tyk.

Z powyższego opisu widać, że odszyfrowywanie jest również bardzo łatwe, a w dodatku wszystko to robią programy komputerowe. Twoim zadaniem jest zrozumieć ten sposób i świadomie go stosować.

Łamanie szyfru

Spróbuj odszyfrować, jaki tekst kryje się pod ciągiem liczb w tytule lekcji. Liczbami szyfrującymi są k=936915803 i s = 3571.
Oczywiście, nie znasz klucza prywatnego, czyli liczby deszyfrującej d. Z teoretycznych podstaw szyfrowania wynika jednak wzór na jej obliczenie: ; gdzie liczby p i q są to dwie różne liczby pierwsze dające w iloczynie liczbę szyfrującą k, zaś a, to tak dobrana liczba, aby d było całkowite. Trzeba więc liczbę kodującą k=936915803 rozłożyć na czynniki pierwsze. Zrób to,  korzystając z apletu "Liczby pierwsze i złożone", a następnie wróć tutaj i skorzystaj z panelu "Liczba deszyfrująca".

Z apletu "Liczby pierwsze i złożone" otrzymujemy rozkład liczby 936915803 na czynniki 29879 i 31357. Wstawiając te liczby oraz liczbę s=3571 do panelu "Liczba deszyfrująca", otrzymujemy d = 500827603. Zatem dla pierwszej liczby 772955442 widniejącej w temacie lekcji, korzystając z dolnego panelu, otrzymujemy: 772955442^5008276003 mod 936915803 = 7247434. Zamieniając tę liczbę na tekst, za pomocą lewego dolnego panelu, otrzymujemy słowo Oto. Postępując analogicznie z pozostałymi kodami 623281635   379279823   352653218   71829568    466566719   545870045   363842058 otrzymujemy tekst: Oto ja, Twój szyfr RSA.

Tak więc, można złamać szyfr, jeśli da się liczbę szyfrującą k rozłożyć na czynniki. Można też łamanie szyfru przeprowadzić w inny sposób, mianowicie utworzyć za pomocą komputera wszystkie możliwe kody ASCII słów trzyliterowych i odszukać w nich poszczególne kody. Jest ich tylko 255*255*255=16581375 i nie powinno to trwać długo.

Zadanie 1.
Odszyfruj imię i nazwisko ukryte pod kodem 661667530, 392467335, 360399651, 320896296, wiedząc, że do szyfrowania użyto liczb k = 720879421 i s = 1234567.

Bezpieczeństwo szyfru RSA

Co gwarantuje bezpieczeństwo szyfru RSA?

Przekonaj się sam. Spróbuj obliczyć liczbę deszyfrującą d dla liczb szyfrujących: k= 944874500279959 i s = 35753.

Aplet "Liczby pierwsze i złożone" nie potrafi rozłożyć liczby 944874500279959 na czynniki. Bardziej zaawansowane programy potrafią to zrobić, ale na pewno nie poradzą sobie z liczbami stosowanymi w prawdziwych systemach szyfrujących. Są tam bowiem liczby ponad dwustucyfrowe i rozkład na czynniki praktycznie jest niemożliwy. Nawet najszybszy na świecie komputer robiłby to setki lat. To zapewnia bezpieczeństwo szyfrów RSA. Zatem nie nieznajomość sposobu szyfrowania, lecz trudność w rozkładzie na czynniki jest gwarancją bezpieczeństwa szyfru. Jeśli ktoś wymyśli szybki sposób rozkładu liczby na czynniki lub zbuduje komputer działający niewyobrażalnie szybko, np. komputer kwantowy, to spowoduje rewolucję w technikach informatycznych.

Projekt

Zbuduj własny system szyfrujący oparty o metodę RSA. I tu bardzo ważna uwaga: gdy będziesz ustalał własne liczby kodujące k i s, to liczba s i później obliczana liczba d muszą być względnie pierwsze z liczbami p-1 i q-1 (wymagają tego teoretyczne podstawy szyfrowania). Należy również pamiętać, że nie można używać małych liczb k. Dla trzyliterowych słów muszą one być większe od 16581375, czyli od 255^.255^.255 - jest to ostatni kod ASCII dla trzyliterowych słów.

Teoretyczne podstawy szyfrowania metodą RSA

A oto dwa twierdzenia z teorii liczb, które są podstawą sposobu szyfrowania metodą RSA.
Twierdzenie 1. Niech x mod y oznacza resztę z dzielenia x przez y (np. 11 mod 3 = 2).
a) (a+b) mod c = ((a mod c) + (b mod c)) mod c.
Przykład: (35 + 87) mod 18 = ((35 mod 18) + (87 mod 18)) mod 18 = (17 + 15) mod 18 = 32 mod 18 = 14.
(Sprawdzenie: (35 + 87) mod 18 = 122 mod 18 = 14).

b) (a*b) mod c = ((a mod c) * (b mod c)) mod c.
Przykład: (39*123) mod 11 = ((39 mod 11) * (123 mod 11)) mod 11 = (6*2) mod 11 = 12 mod 11 = 1.
(Sprawdzenie: (39*123) mod 11 = 4797 mod 11 = 1).

c) a^b mod c = (a mod c)^b mod c.
Przykład: 122³ mod 6 = (122 mod 6)³ mod 6 = 2³ mod 6 = 8 mod 6 = 2.
(Sprawdzenie: 122³ mod 6 = 1815848 mod 6 = 2).

Przykład c) pokazuje, jak można obliczyć a^b mod c, unikając działań na dużych liczbach. Jednak w wielu przykładach nie wystarczy takie proste zastosowanie tego wzoru. Np. 123⁴⁵⁶ mod 789 = (123 mod 789)⁴⁵⁶ mod 789 = 123⁴⁵⁶ mod 789 i otrzymaliśmy tę samą postać, która była na początku. W takim przypadku należy rozpisać potęgę według znanego wzoru a^mn = (a^m)ⁿ i dopiero wtedy zastosować wzór c).
Mamy: 123⁴⁵⁶ mod 789 = (123²)²²⁸ mod 789 = 15129²²⁸ mod 789 = (15129 mod 789)²²⁸ mod 789 = 138²²⁸ mod 789 = (138²)¹¹⁴ mod 789 = 19044¹¹⁴ mod 789 = (19004 mod 789)¹¹⁴ mod 789 =108¹¹⁴ mod 789 = (108²)⁵⁷ mod 789 = 11664⁵⁷ mod 789 = 618⁵⁷ mod 789.
Dalej nie możemy postępować tak samo, ponieważ 57 nie jest parzyste. Ale możemy zastosować inny znany wzór na potęgi: a^m+n = a^maⁿ. Otrzymujemy: 618⁵⁷ mod 789 =(618*618⁵⁶) mod 789.
Teraz stosujemy wzór b) z twierdzenia 1 oraz wzory na zamianę potęg:
(618*618⁵⁶) mod 789 = ((618 mod 789)*(618⁵⁶ mod 789)) mod 789 =
= (618*((618²)²⁸ mod 789)) mod 789 = (618*(381924²⁸ mod 789)) mod 789 =
= (618*(48²⁸ mod 789)) mod 789 = (618*((48²)¹⁴ mod 789)) mod 789 =
= (618*(2304¹⁴ mod 789)) mod 789 = (618*(726¹⁴ mod 789)) mod 789 =
= (618*((726²)⁷ mod 789)) mod 789 = (618*(527076⁷ mod 789)) mod 789 =
= (618*(24⁷ mod 789)) mod 789 = (618*((24*24⁶) mod 789)) mod 789 =
= (618*24*((24²)³ mod 789)) mod 789 = ((14832 mod 789)*(576³ mod 789)) mod 789 =
= (630*((576*576²) mod 789)) mod 789 = (630*576*(331776 mod 789)) mod 789 =
= (362880*396) mod 789 = ((362880 mod 789)*369) mod 789 = (729*369) mod 789 =
= 288684 mod 789 = 699.
Zatem 123⁴⁵⁶ mod 789 = 699. Obliczyliśmy tę resztę, działając cały czas na małych liczbach, chociaż liczba 123⁴⁵⁶ jest około pięciusetcyfrowa.

Wszystkie czynności, które wykonywaliśmy w czasie obliczeń, może oczywiście wykonać komputer. W programie jest opcja pozwalająca wykonywać działanie a^b mod c według sposobu podanego wyżej.

A oto prosty program w Pascalu, który wykonuje działanie a^b mod c, według sposobu podanego wyżej (program ten i pozostałe programy znajdują się w katalogu "Programy-PASCAL").

program Reszta;
{$N+}
uses crt;
var a:extended;
function potegaModulo(a,b,c:extended):extended;
var reszta:extended;
begin
reszta:=1;
while b>0 do
begin
if int(b/2)<>b/2 then reszta:=reszta*a-int(reszta/c*a)*c;
a:=a*a-int(a/c*a)*c;
b:=int(b/2);
end;
potegaModulo:=reszta;
end;
begin
clrScr;
a:=123;
writeLn(a:1:0,' -> ',potegaModulo(a,456,789):1:0);
readLn;
end.

Funkcja potegaModulo(a,b,c:extended):extended oblicza a^b mod c w sposób identyczny, jak to pokazaliśmy w przykładzie, tzn. zamienia potęgę a^b na postać (a²)^b/2, jeśli b jest parzyste, lub na postać a*a^b-1, jeśli b jest nieparzyste, a następnie oblicza resztę z dzielenia tego wyrażenia przez c, stosując wzory c) i b) z twierdzenia 1.
Po uruchomieniu programu otrzymujemy wynik w postaci: 123 ® 699, co dla dla a=123, b=456 i c=789 należy rozumieć jako: 123⁴⁵⁶ mod 789 = 699.

Drugie twierdzenie stosowane w technice szyfrowania ma postać:
Twierdzenie 2. Jeżeli liczby p i q są pierwsze i różne, to dla dowolnej liczby naturalnej N<p*q zachodzi równość:
N^{(p-1)*(q-1)+1} mod (p*q) = N.
Przykład: p=2, q=11, p*q=22, N=3, (p-1)*(q-1)+1=11, 3¹¹ mod 22 = 3.
Uogólnienie:
Jeżeli liczby p i q są pierwsze i różne, to dla dowolnej liczby naturalnej N<p*q i dowolnej liczby naturalnej a zachodzi równość:
N^{a*(p-1)*(q-1)+1} mod (p*q) = N.
Przykłady:
a=1, p=2, q=11, p*q=22, N=3, a*(p-1)*(q-1)+1=11, 3¹¹ mod 22 = 3,
a=2, p=2, q=11, p*q=22, N=3, a*(p-1)*(q-1)+1=21, 3²¹ mod 22 = 3,
a=3, p=2, q=11, p*q=22, N=3, a*(p-1)*(q-1)+1=31, 3³¹ mod 22 = 3.
Zastosowanie twierdzenia 2.
Niech p, q będą dwiema, różnymi liczbami pierwszymi. Dobieramy taką liczbę całkowitą a, aby wyrażenie M = a*(p-1)*(q-1)+1 było iloczynem dwóch liczb całkowitych s* d, gdzie s, d są względnie pierwsze z p-1 i q-1.
Stąd, dla dowolnej liczby naturalnej N<p*q zachodzą równości:
N^M mod k = (N^s)^d mod k = (N^s mod k)^d mod k = X^d mod k = N.
Z liczby N otrzymaliśmy liczbę X = N^s mod k. Liczba X jest kodem liczby N. Z liczby X łatwo uzyskać na powrót liczbę N, obliczając X^d mod k. Jest to idea szyfrowania metodą RSA.
Przykład: a=2, p=2, q=11, e=3, d=7, M=21, k=22, N = 3,
3²¹ mod 22 = (3³ mod 22)⁷ mod 22 = 5⁷ mod 22 = 78125 mod 22 = 3. Liczba 5 jest kodem liczby 3. Z liczby 5 otrzymujemy na powrót liczbę 3.

Odpowiedzi

1. Jan Kowalski.