628812058 249246440

92750784 367915951 724451625 417050775 552242313 855301561 442290327 583800293

Powyższy ciąg liczbowy, to zaszyfrowany tytuł tego artykułu. Temat szyfrowania jest dzisiaj bardzo aktualny, ponieważ coraz więcej osób korzysta z sieci komputerowych, szczególnie z Internetu, i tą drogą przekazywana jest bardzo duża ilość informacji, a ostatnio dokonywane są nawet zakupy i wykonywane różnego rodzaju operacje finansowe. Wiele z tych informacji, jak np. polecenia przelewu bankowego, ważne informacje gospodarcze i biznesowe, a nawet prywatne listy, powinny być utajnione. Informacje te mogą w postaci plików liczbowych krążyć w sieci i mogą dać się kopiować, ale nie powinny dać się odszyfrować.

Weźmy przykładową sytuację. Bank obsługuje kilka tysięcy klientów i przyjmuje od nich zlecenia finansowe poprzez Internet. Gdyby klienci przesyłali je normalnym, nie zakodowanym sposobem to mogłyby znaleźć się osoby potrafiące przechwycić informacje z sieci i wykorzystać je do własnych celów. Sposób kodowania musi być jednakowy dla wszystkich klientów, ponieważ bank nie może wymyśleć i obsługiwać kilku tysięcy sposobów kodowania. Ale jeśli sposób kodowania będzie wszystkim znany to, wydawałoby się, że zakodowaną informację będzie można, jakimś odwrotnym sposobem, odkodować i sytuacja pozostanie taka sama, jakby kodowania nie było. Powstaje więc problem: czy jest możliwe, aby zaszyfrowana informacja była tajna, jeśli sposób szyfrowania jest wszystkim znany?

Odpowiedź na ten problem jest pozytywna. Trzech uczonych - Rivest, Shamir i Adleman z MIT (Massachusetts Institute of Technology) w Bostonie, wymyśliło taki właśnie sposób kodowania, używając do tego tylko dwóch liczb. W sposobie tym, nazywanym obecnie RSA, można ogłosić publicznie sposób szyfrowania, ale zaszyfrowanej informacji nikt nie potrafi odczytać, oprócz osób znających dodatkowo jeszcze trzecią liczbę deszyfrującą. Ten sposób jest tak pewny, że jeśli ktoś utraci orginał tekstu który zaszyfrował, to sam go już nie odszyfruje.

Na czym to wszystko polega? Oczywiście na prawach matematyki i informatyki. Teoretyczną podbudowę tego sposobu dają dwa twierdzenia z teorii liczb.

Tw.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) ab mod c = (a mod c)b mod c

Przykład: 1223 mod 6 = (122 mod 6)3 mod 6 = 263 mod 6 = 8 mod 6 = 2
(Sprawdzenie: 1223 mod 6 = 1815848 mod 6 = 2)

Przykład c) pokazuje, jak można obliczyć ab mod c, unikając działań na dużych liczbach. Jednak w wielu przykładach nie wystarczy takie proste zastosowanie tego wzoru. Np. 123456 mod 789 = (123 mod 789)456 mod 789 = 123456 mod 789 i jest to samo co było na początku. W takim przypadku należy rozpisać potęgę według znanego wzoru amn = (am)n i dopiero wtedy zastosować wzór c).

Mamy: 123456 mod 789 = (1232)228 mod 789 = 15129228 mod 789 = (15129 mod 789)228 mod 789 = 138228 mod 789 = (1382)114 mod 789 = 19044114 mod 789 = 108114 mod 789 = (1082)57 mod 789 = 1166457 mod 789 = 61857 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: am+n = aman Otrzymujemy: 61857 mod 789 =(618*61856) mod 789.

Teraz stosujemy wzór b) tw.1 oraz znowu wzory na zamianę potęg:

(618*61856) mod 789 = ((618 mod 789)*(61856 mod 789)) mod 789 =
= (618*((6182)28 mod 789)) mod 789 = (618*(38192428 mod 789)) mod 789 =
= (618*(4828 mod 789)) mod 789 = (618*((482)14 mod 789)) mod 789 =
= (618*(230414 mod 789)) mod 789 = (618*(72614 mod 789)) mod 789 =
= (618*((7262)7 mod 789)) mod 789 = (618*(5270767 mod 789)) mod 789 =
= (618*(247 mod 789)) mod 789 = (618*((24*246) mod 789)) mod 789 =
= (618*24*((242)3 mod 789)) mod 789 = ((14832 mod 789)*(5763 mod 789)) mod 789 =
= (630*((576*5762) 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 123456 mod 789 = 699. Obliczyliśmy tę resztę, działając cały czas na małych liczbach, chociaż liczba 123456 jest około 500-cyfrowa.

Wszystkie czynności, które wykonywaliśmy w czasie obliczeń, może oczywiście wykonać komputer. Prosty program Reszta, realizuje działanie ab mod c według sposobu podanego wyżej (program ten i pozostałe programy znajdują się w pliku szyfr.zip).

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 ab mod c w sposób identyczny jak to pokazaliśmy w przykładzie, tzn. zamienia potęgę ab na postać (a2)b/2 jeśli b jest parzyste lub na postać a*ab-1, jeśli b jest nieparzyste, a następnie oblicza resztę z dzielenia tego wyrażenia przez c stosując wzory c) i b) tw.1.

Po uruchomieniu programu otrzymujemy wynik w postaci: 123 -> 699, co dla dla a=123, b=456 i c=789 należy rozumieć jako: 123456 mod 789 = 699.

Program Reszta będzie głównym programem stosowanym do szyfrowania i deszyfrowania metodą RSA.

Drugie twierdzenie stosowane w technice szyfrowania ma postać:

Tw.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, 311 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ść:

Na*(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, 311 mod 22 = 3

a=2, p=2, q=11, p*q=22, N=3, a*(p-1)*(q-1)+1=21, 321 mod 22 = 3

a=3, p=2, q=11, p*q=22, N=3, a*(p-1)*(q-1)+1=31, 331 mod 22 = 3

Zastosowanie tw.2:

Niech p, q będą dwoma, 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 e* d, gdzie e,d są względnie pierwsze z p-1 i q-1.

Stąd, dla dowolnej liczby naturalnej N<p*q zachodzą równości:

NM mod k = (Ne)d mod k = (Ne mod k)d mod k = Xd mod k = N

Z liczby N otrzymaliśmy liczbę X = Ne mod k. Liczba X jest kodem liczby N. Z liczby X łatwo uzyskać na powrót liczbę N obliczając Xd 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,

321 mod 22 = (33 mod 22)7 mod 22 = 57 mod 22 = 78125 mod 22 = 3. Liczba 5 jest kodem liczby 3. Z liczby 5 otrzymujemy na powrót liczbę 3.

Zastosujemy ten sposób do kodowania i dekodowania tekstów. Weźmy jakiś tekst do zaszyfrowania, np. hasło "Komputery i Matematyka".

Powiedzmy od razu, że kodowanie kolejno, pojedynczych liter K,o,m,p,u,t,e,r,y, ,i, ,M,a,t,e,m.,a,t,y,k,a nie ma sensu, ponieważ, przy ogłoszonym publicznie sposobie kodowania, każdy może przygotować sobie klucz deszyfrowania i dopasować kody do odpowiednich liter. Również kodowanie po dwie litery Ko,mp,ut,er,y ,i ,Ma,te,ma,ty,ka , daje małą ilość różnych kombinacji kodów i również łatwo przygotować sobie tablicę deszyfrującą. Omówimy tutaj szyfrowanie 3-literowe, przy pomocy 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 przy pomocy komputera, bez znajomości sposobu deszyfrowania, trwałoby lata.

Aby zaszyfrować dany tekst, najpierw należy zamienić 3-literowe segmenty tekstu na liczby całkowite zgodnie z tablicą ASCII. Będziemy wykorzystywać stronę kodową 852, czyli stronę z polskimi literami, więc ktoś nie ma zainstalowanej tej strony na swoim komputerze i będzie wykorzystywał programy podane w tym artykule, to w miejscu polskich liter będzie otrzymywał "robaczki".

Program realizujący zamianę 3-literowego segmentu tekstu na liczbę całkowitą, wg tablicy ASCII wygląda następująco:

program Zamiana_tekstu_na_liczbe;
{$N+} uses crt;
var n:integer; liczba,potega255:extended; tekst:string;
procedure zamienTekstNaLiczbe(tekst:string);
begin
liczba:=0;
potega255:=1;
for n:=length(tekst) downto 1 do
begin
liczba:=liczba+ord(tekst[n])*potega255;
potega255:=potega255*255;
end;
end;
begin
clrScr;
tekst:='Kom';
zamienTekstNaLiczbe(tekst);
writeLn(tekst,'=',liczba:1:0);
readLn;
end.

Procedura "zamienTekstNaLiczbe(tekst:string);"jest procedurą jednoparametrową. Parametr tekst oznacza segment tekstu, który ma być zamieniony na liczbę. Procedura buduje tę liczbę poprzez odczytanie kodu ASCII każdej litery segmentu tekstu (licząc od końca tekstu) i pomnożenie jej przez kolejną potęgę liczby 255 (ord(tekst[n])*potega255) oraz przez dodanie liczby obliczonej w poprzednim kroku. Np. tekst Kom zostanie zamieniony na liczbę

109*2550+111*2551+75*2552 = 4905289.

Dla poszczególnych, 3-literowych segmentów tekstu (odstępy między wyrazami wpisujemy jako spację), otrzymujemy następujące liczby:

Kom=4905289, put=7312751, ery=6596716, _i_=6204245,

Mat=5031776, ema =6595417, tyk=7573862, a__=6331745

Teraz następuje najważniejsza część kodowania. Załóżmy, że zostały ogłoszone dwie liczby kodujące: k = 948581743 i e = 4321. Sposób kodowania jest następujący: Kodem liczby N jest reszta z dzielenia potęgi Ne przez k, czyli wynik działania Ne mod k. (Należy pamiętać, aby liczba N była mniejsza od k.)

Zatem kodem liczby 4905289, oznaczającej segment tekstu Kom, jest reszta z dzielenia potęgi 49052894321 przez 948581743. Funkcja potegaMod, w programie Reszta, realizuje to działanie i daje w wyniku kod równy 417540425.

Po uruchomieniu programu dla poszczególnych liczb otrzymujemy odpowiednie kody:

4905289 -> 417540425
7312751 -> 26437255
6596716 -> 839231545
6204245 -> 934183720
5031776 -> 366369271
6595417 -> 260593359
7573862 -> 726483077
6331745 -> 638943823

Pogrubione liczby to zaszyfrowany tekst "Komputery i Matematyka".

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

Zajmiemy się teraz omówieniem techniki deszyfrowania metodą RSA. Potrzebna jest do tego liczba deszyfrująca d, którą obliczamy na podstawie tw.2 ze wzoru

gdzie liczby p i q są to dwie różne liczby pierwsze dające w iloczynie liczbę kodującą k, zaś a to specjalnie dobrana, taka liczba, aby d było całkowite. Jeśli sami ogłosiliśmy liczby kodujące k i e, to oczywiście znamy liczby p i q. Jeśli jednak chcemy złamać czyjś szyfr to musimy liczbę k rozłożyć na czynniki. W tym wypadku da się to zrobić, ponieważ liczba k = 948581743 jest mała. W prawdziwym szyfrowaniu nie da się tego dokonać, chyba, że włączymy komputer na kilka lat i cały czas będzie on pracował nad rozkładem jednej liczby k. Czytelnik zapewne ma pod ręką jakiś program do rozkładu liczb na czynniki i zechce sprawdzić, że w naszym przypadku k = 948581743 = 28751*32993, czyli p = 28751, q = 32993. Wstawiamy te liczby, oraz e=4321 do wzoru i dobieramy kolejno a=1, a=2, ... aż do momentu, gdy liczba d będzie całkowita. Oczywiście można do tego napisać prościutki program i już po chwili otrzymujemy a = 720 i d = 158050081.

Jest jednak bardzo ważna uwaga, gdyby ktoś zechciał ustalić własne liczby kodujące e i k, liczba e, i później obliczona liczba d, muszą być względnie pierwsze z liczbami p-1 i q-1 (wymaga tego tw.2).

Mając liczbę d odszyfrowujmy liczbę, której kod wynosi 417540425. W tym celu obliczamy resztę z dzielenia potęgi kodd przez k, czyli w naszym przypadku 417540425158050081 mod 948581743. Czynność tę wykona program "Reszta" jeśli wpiszemy do niego odpowiednie wartości liczbowe.

Po uruchomieniu programu otrzymujemy wyniki w postaci:

417540425 -> 4905289
26437255 -> 7312751
839231545 -> 6596716
934183720 -> 6204245
366369271 -> 5031776
260593359 -> 6595417
726483077 -> 7573862
638943823 -> 6331745

Do zakończenia procesu deszyfrowania pozostało zamienić otrzymane liczby na tekst. Służy do tego program:

program Zamiana_liczby_na_tekst;
{$N+} uses crt;
var blad:integer; liczba:extended; tekst,liczbaS:string;
procedure zamienLiczbeNaTekst(liczba:extended);
begin
tekst:='';
repeat
tekst:=char(round(liczba-int(liczba/255)*255))+tekst;
liczba:=int(liczba/255);
until liczba=0;
end;
begin
clrScr;
liczbaS:='4905289';
val(liczbaS,liczba,blad);
zamienLiczbeNaTekst(liczba);
writeLn(liczbaS,'=',tekst);
readLn;
end.

Procedura zamienLiczbeNaTekst(liczba:extended) działa odwrotnie do procedury zamienTekstNaLiczbe(tekst:string). Oblicza ona, przy pomocy wzoru liczba-int(liczba/255)*255, kod ASCII i zamienia go przy pomocy instrukcji char na odpowiednią literę. Po uruchomieniu programu otrzymujemy wyniki w postaci:

4905289=Kom, 7312751=put, 6596716=ery, 6204245=_i_,

5031776=Mat, 6595417=ema, 7573862=tyk, 6331745=a__

Składając otrzymane 3-literowe segmenty w jedno zdanie otrzymujemy tekst: "Komputery i Matematyka". Tym sposobem zakończyliśmy proces deszyfrowania.

Z powyższego omówienia wynika, że deszyfrowanie jest równie łatwe i szybkie jak szyfrowanie, ale niestety, może dokonać tego tylko ten, kto zna liczbę deszyfrującą d lub potrafi ją wyznaczyć, rozkładając liczbę k na czynniki pierwsze p i q i podstawiając je do wyżej podanego wzoru. Liczby p i q nie są ogłaszane publicznie, a jedynie podawany jest ich iloczyn k. Teraz więc wiadomo, dlaczego na świecie trwa wyścig w znajdowaniu dużych liczb pierwszych. Są one odkrywane przez wyspecjalizowane grupy programistów i sprzedawane bankom, wojsku i innym instytucjom, które wykorzystują je do szyfrowania. (Kto by przypuszczał, że liczby mogą być sprzedawane i że można być właścicielem jakiejś liczby?)

Zachęcam Czytelników do spróbowania odczytania zaszyfrowanego tytułu artykułu. Do kodowania użyto liczb: k=936915803 i e = 3571. Należy samemu wyznaczyć liczbę dekodującą d , aby się przekonać jaka jest skala trudności przy łamaniu szyfrów. Jeśli to komuś się nie uda to podaję: d = 500827603.

Dla ambitnych Czytelników pozostawiam zadanie odczytania tekstu ukrytego pod następującymi liczbami:

717402675966612 62660288556658 337603446986424 265359905017610 734623157641714

Szyfr ten został utworzony przy pomocy liczb kodujących k= 944874500279959 i e = 35753. Liczbę dekodującą należy samemu wyznaczyć (dla leniwych podaję: d=42918805249945). Aby wykorzystać program "Reszta" do dekodowania tego szyfru, należy program tak zmodyfikować, aby działał on na dużych liczbach, co najmniej 30-cyfrowych. Jest to konieczne ponieważ w programie występuje iloczyn "a*a", który dla liczb 15-cyfrowych jest ponad 30-cyfrowy, zaś zmienne typu extended, występujące w programie, działają tylko na liczbach co najwyżej 17-cyfrowych i dla liczb 30-cyfrowych dadzą błędne wyniki.

Życzę powodzenia w deszyfrowaniu.

Eugeniusz Jakubas
Zamośc, 1996r.

Literatura:

1.W.Guzicki - "Arytmetyka liczb naturalnych" - Wydawnictwo CODN, 1992 r.
2.M.Szurek - "Z komputerem przez matematykę" - Oficyna "ADAM", 1995 r.