RSA for dummies

02.02.2012 - Jakub Łopuszański
Trudność

 

RSA dla początkujących.
 
RSA to z jednej strony bardzo prosty algorytm, a z drugiej strony dość złożony świat algebry za nim stojący. Wydaje mi się dość ładną ilustracją tego do czego przydaje się algebra w informatyce. Postaram się opowiedzieć wszystko od początku do końca zaczynając od poziomu podstawówki. Zakładam jednak pewną dozę zainteresowania informatyką.
 
Dla osób niecierpliwych, bądź przerażonych tym co je czeka, pragnę uspokoić, że RSA jest naprawdę proste i sprowadza się w zasadzie do paru wzorów:
n=p*q
e*d = 1 modulo (p-1)*(q-1)
(x^e)^d = x modulo n
to co te wzory oznaczają, też jakoś specjalnie nie powala, ale niezbędne jest wyjaśnienie wielu bardzo prostych pojęć, które z jakiegoś powodu nie są nauczane w podstawówce, mimo, że nie odbiegają trudnością od powiedzmy trygonometrii.

Zacznijmy może od motywacji, bo fajnie jest zaczynać z wizją końca. Dla kogoś kto jeszcze nie słyszał o szyfrowaniu asymetrycznym, idea może z początku wydawać się dość absurdalna i ciężko ją przełknąć. Pomysł polega na tym, żeby stworzyć taki sposób szyfrowania i deszyfrowania informacji, że osoba potrafiąca szyfrować, nie będzie umiała deszyfrować. Przykładowo, żołnierz będzie w stanie wysłać raport do sztabu, ale nawet torturowany nie będzie umiał rozkodować raportów innych żołnierzy. Albo np. bank będzie mógł umieścić na swojej stronie formularz do robienia przelewów i każdy klient będzie mógł wysłać do banku dane do przelewu, bez ryzyka, że jakiś inny klient go podsłucha. Asymetria polega więc na tym, że jedna osoba umie coś czego nie umie robić inna osoba - proces deszyfrowania nie jest symetrycznym odbiciem szyfrowania. Wymaga znajomości innych sekretów i o ile pozostaną one ukryte w tajemnicy, to mamy pewność, że jest tylko jedna osoba, która umie zdeszyfrować wiadomość. M-I6 mogłoby więc rozkazy do jamesa bonda umieszczać zupełnie publicznie na swojej stronie internetowej, bo i tak nikt prócz niego by nie umiał jej odczytać. Co więcej jego francuski łącznik mógłby zweryfikować tożsamość bonda po prostu zapisując sobie na kartce jakiś losowy ciąg znaków, szyfrując go w sposób zrozumiały tylko dla prawdziwego bonda i każąc mu zdeszyfrować tak zaszyfrowaną wiadomość. RSA jest więc jednym z podstawowych narzędzi w ręku kryptografa, pozwalającym wprowadzać pewną asymetrię między osobami biorącymi udział w protokole -- symetria oznacza pewną nierozróżnialność, podczas gdy asymetria pomaga rozróżnić ludzi/strony.

Źródłem asymetrii w RSA jest różnica między w trudności wykonywania dwóch przeciwnych działań. Z grubsza sprowadza się to do tego, że łatwiej pomnożyć przez siebie dwie liczby, niż mając jakąś liczbę rozłożyć ją na czynniki i chociaż algorytm RSA wydaję się znacznie bardziej skomplikowany niż mnożenie dwóch liczb i być może nie uda mi się go Wam w pełni wytłumaczyć, to warto mieć świadomość, że wszystko to (bankowość elektroniczna, SSH, itd) legnie w gruzach, jeśli komuś z Was uda się wymyśleć wydajny algorytm faktoryzacji.


Będę używał w paru miejscach gdzie mowa o złożoności pamięciowej czy obliczeniowej używał notacji O, Theta i Omega -- fragmenty te można pewnie pominąć, jeśli to kogoś przeraża, ale sądzę, że większość osób zainteresowanych informatyką, albo je zna, albo sobie doczyta z wikipedii. Dla przypomnienia, duże O to jakby ograniczenie z góry, Omega, to jakby z dołu, zaś Theta to połączenie Omega i O na raz.

Zacznijmy od zupełnych podstaw.

Liczby naturalne, N, to 0,1,2,3,..., jest ich nieskończenie wiele i to na co dzień trochę komplikuje życie informatykom (komputery nie są nieskończenie duże), dlatego często ograniczają się do pewnego początkowego fragmentu liczb naturalnych, Z_n = {0,1,2,...,n-1}.

Liczby naturalne można do siebie dodawać i mnożyć. Trochę ciężej idzie z odejmowaniem (2-7 nie jest naturalne), czy dzieleniem (2/7 nie jest naturalne).

Dodawanie i mnożenie, to znaczki, które od dziecka są nam wpajane i kojarzone z tymi naturalnymi działaniami, do tego stopnia, że wiele osób ma problem z uświadomieniem sobie, że to tylko znaczki, które mogłobyby w sumie znaczyć zupełnie co innego, a dodawanie i mnożenie mogłyby pewnie wyglądać zupełnie inaczej. Różne aksjomaty dotyczące dodawania czy mnożenia (np. przemienność dodawania, czy rozdzielność mnożenia względem dodawania) traktujemy bardziej jak odkrycia naukowe na temat obserwowanych na sawannie zwierząt, niż jak przepis na ciasto. Bardziej widzimy w nich zauważone prawidła, niż definicję tego co chcemy uzyskać.
Co więcej edukacja szkolna na temat tych działań buduje nieco mylne wrażenie, że dodawanie jest jakimś absolutem istniejącym w oderwaniu od liczb, którego ziemskimi manifestacjami są dodawanie liczb naturalnych, dodawanie liczb całkowitych, dodawanie liczb rzeczywistych, dodawanie liczb zespolonych, wszystkie jednak działające w ten sam, jedynie słuszny sposób, w którym 1+1=2 niezależnie od tego, czy chodzi nam o 1 będące naturalną liczbą, czy zespoloną, czy może całkowitą. To bardzo uspokajający i wygodny sposób myślenia, spójny z tym, że liczby naturalne są podzbiorem liczb całkowitych, a one rzeczywistych, które są z kolei zespolonymi.

Spróbujcie jednak -- jeśli jeszcze tego nie robiliście -- wyobrazić sobie jakiś inny świat, w którym dodawanie i mnożenie działałyby inaczej.

Zaczniemy od Z_n, o którym wiemy już z jakich elementów się składa ({0,1,...,n-1}), ale nie powiedzieliśmy sobie jeszcze jak będzie w nim zdefiniowane dodawanie. Zapewne wielu z nas chciałoby, żeby dodawanie spełniało lubiane przez nas aksjomaty, np., że 0+x = x, albo, że x+y=y+x, czy (x+y)+z=x+(y+z). Chociaż nie jest to aksjomatem, to pewnie wielu czułoby się bardziej komfortowo gdyby 1+1=2, a ogólniej: czujemy się tym bezpieczniej im bardziej dodawanie przypomina to dla liczb naturalnych. Jeśli zastanawiacie się, “ale w czym tu w ogóle problem, przecież to są liczby naturalne, więc to chyba oczywiste, że możemy je dodawać jak liczby naturalne?”, to zastanówcie się ile powinno być równe 3+4 w Z_5? Liczba 7 nie należy w ogóle do świata Z_5 = {0,1,2,3,4}.

Zanim doprecyzujemy jak ma działać dodawanie, popatrzmy na moment na odejmowanie.
Jak już widzieliśmy, w liczbach naturalnych odejmowanie nie zawsze działa. Jeśli założyć, że Z_n jest informatykom potrzebne do tego by uprościć sobie życie z liczbami naturalnymi, to niewątpliwie prościej by było, gdyby każde dwie liczby dało się odejmować. Odejmowanie to działanie przeciwne do dodawania, tzn chciałoby się, by a+b=c ⇔ c-b = a. Potraktujmy to jako aksjomat świata który chcemy stworzyć i zobaczmy jak musiałoby działać odejmowanie w Z_n, by go spełnić.

Skupmy się na naszym Z_5 i zastanówmy się ile powinno być równe 1+1+1+1+1?
Nie mamy zbyt wielkiego wyboru, bo Z_5 ma tylko 5 elementów, a więc musi to być 0,1,2,3 albo 4.
Ja wiem, że to powinno być 0, żeby wszystko działało jak należy, ale przekonam Was do tego niewprost. Powiedzmy, że 1+1+1+1+1 będzie równe jakiejś innej liczbie niż 0, np. 3.
Z aksjomatów wynika, że 1+1+1+1+1 = (1+1+1)+1+1 = 3+(1+1).
Mamy zatem, że 3+2 = 3 = 3+0, czyli dwa różne sposoby uzyskania tej samej liczby jako sumy 3 i czegoś jeszcze. Pewnie cześć z Was już przeczuwa, że nie rokuje to najlepiej jeśli chodzi o sprawnie działające odejmowanie.
No bo teraz zastanówmy się ile powinno być równe 3-3 ?
Wg definicji c-b = a ⇔ a+b=c.  Czyli jeśli weźmiemy c=3 i b=3, to mamy sprostać wymogowi 3-3 = a ⇔ a+3 = 3. No ale my znamy dwa różne a, dla których a+3=3, jednym jest 0 a drugim 2. W takim razie 3-3 musi być jednocześnie równe 2 i 0.
Ale te dwie liczby są różne, więc nie mogą być tą samą liczbą.

Powyższe rozumowanie da się powtórzyć dla każdej liczby innej niż 0 dochodząc do podobnej sprzeczności, więc 1+1+1+1+1 drogą eliminacji musi być równe 0 w Z_5.

Jeśli się zgodzimy, że 1+1=2, 1+1+1=3, … , 1+1+..+1=n-1, (mi to pasuje i wygląda sensownie), to ta jedna mała decyzja na temat tego ile ma być równa suma n jedynek, którą właśnie podjęliśmy, jest jedyną jaką trzeba w zasadzie podjąć, by zdefiniować dodawanie dla wszystkich par liczb w Z_n: gdy chcemy dodać a+b, to jeśli któraś z tych liczb jest zerem, to wiadomo jaki jest wynik. Jeśli obie nie są zerami, to wiemy jak rozbić je na jedynki. Dodawanie jedynek jest łączne, więc możemy sobie nawiasy wstawić tak by pogrupować po n jedynek w jednym nawiasie, a potem skorzystać z tego, że każdy nawias jest równy zero. Wracając do naszego przykładu 3+4 = (1+1+1) + (1+1+1+1) = (1+1+1+1+1)+(1+1) = 0 + 2 = 2.

Z_n z dodawaniem i odejmowaniem jest bardzo przyjaznym tworem i część z Was pewnie już z niego korzystało : unsigned int, to nic innego jak Z_{2^32}. Jeśli tego jeszcze nie widzicie, to spokojnie, zaraz do tego dojdziemy. Dodawanie dwóch liczb w Z_n można wyrazić jako (a+b) mod n. Odejmowanie to (a-b+n) mod n. To +n jest po to by nie martwić się o liczby ujemne, które mogą się pojawić przy odejmowaniu a-b. Powyższe wzorki nie biorą się z kosmosu, tylko z tego grupowania jedynek opisanego powyżej. Operacja modulo, zwana “resztą z dzielenia”, jest dostępna w C++ jako %.

Gdy ktoś pyta Was o resztę z dzielenia przez 10 jakiejś liczby, to na pewno umiecie odpowiedzieć szybciej, niż wykonując dzielenie pisemne i patrząc na otrzymaną resztę: wystarczy zerknąć na ostatnią cyfrę. Podobnie gdy chodzi o resztę z dzielenia przez 10^6, to wystarczy zobaczyć 6 ostatnich cyfr. Jak wiadomo komputer używa systemu dwójkowego, więc sprawdzenie reszty z dzielenia przez 2^k, jest dla niego czymś podobnie prostym: wystarczy wziąć k ostatnich bitów, czyli (x & ((1<<k)-1)). Dla k=32, chodzi nam o wszystkie bity i właśnie dlatego Z_{2^32} to unsigned int.

Mimo, że nie powiedzieliśmy sobie jeszcze nic mądrego, to mam nadzieję, że już widać, że podstawowe koncepty z algebry są dla informatyka mniej abstrakcyjne niż mogłoby się z początku wydawać.

Poradziliśmy sobie z dodawaniem i odejmowaniem, to poradzimy sobie także z mnożeniem, o ile tylko zgodzimy się przyjąć parę lubianych aksjomatów: 1*x = x,  (a+b)*c = a*c + b*c.
Korzystając z nich, powinniśmy być w stanie pomnożyć dowolne dwie liczby. Przykładowo, żeby ustalić ile jest równe 0*3 w Z_5:
0*3 =  (1+1+1+1+1)*3 = 1*3+1*3+1*3+1*3+1*3 = 3+3+3+3+3 = (1+1+1)+(1+1+1)+(1+1+1)+(1+1+1)+(1+1+1) = (1+1+1+1+1)+(1+1+1+1+1)+(1+1+1+1+1) = 0.

Mnożenie (no surpise here) w Z_n to po prostu (a*b)%n.

Pamiętamy, że liczby naturalne miały poważne problemy z dzieleniem. Niestety choroba ta jest nieuleczalna w przypadku Z_n, w których n nie jest liczbą pierwszą. Postaram sie wyjaśnić dlaczego, ale, najpierw “krótka” dygresja o tym, co to są liczby pierwsze, jak się ich szuka i po co.

Powiemy, że liczba naturalna x dzieli liczbę naturalną y, jeśli istnieje liczba naturalna z, taka, że x*z = y.
Liczby x i z będziemy wtedy nazywali dzielnikami liczby y. Liczbę y nazywamy wielokrotnością x.
Jak widać, liczba 0 ma nieskończenie wiele dzielników i jest dzielnikiem samej siebie, ale nie będziemy jej poświęcać jakoś szczególnie wiele uwagi, więc jeśli czyjeś przekonania karzą mu uważać, że 0 nie dzieli żadnej liczby, to proszę bardzo.

Liczbami pierwszymi będę nazywał liczby naturalne mające dokładnie dwa dzielniki. Albo mówiąc bardziej łopatologicznie: liczby większe od 1 niedzielące się przez nic oprócz nich samych i 1. Przykłady na pewno znacie i sądzę, że jakąś definicje też znaliście już wcześniej, ale trzymajmy się tej. W szczególności 1 czy 0 nie są liczbami pierwszymi, ok?

Wszystkie liczby naturalne niebędące pierwszymi nazwę złożonymi.

Jak szukać liczb pierwszych? Jednym ze znanych sposobów jest sito Erastotenesa: nazwa nawiązuje chyba do sposóbu w jaki szukało się złota przepuszczając muł przez sito, choć wątpię by on się czymś takim parał. Najpierw ustalmy rozmiar sita, czyli zakres od 2 do n w którym będziemy szukać liczb pierwszych. Następnie bierzemy najmniejsza liczbę, która jeszcze została na sitku, chowamy do sakiewki jako cenne znalezisko i skreślamy wszystkie jej wielokrotności znajdujące się na sitku.
Metodę tę dla odpowiednio małych n da się z powodzeniem zaimplementować przy użyciu bitvectora i paru pętli:
vector<bool> composite(n+1,false);
vector<int> primes;
for(int p=2;p<n;++p){
 if(!composite[p]){
   primes.push_back(p);
   for(int x=p;x<n;x+=p){
      composite[x]=true;
   }
 }
}
Skreślanie wielokrotności liczby p w powyższy (niezbyt optymalny sposób) wymaga n/p kroków.
Gdyby (co oczywiście nie jest możliwe) za każdym razem trzeba było wchodzić do “ifa” i wykonywać to skreślanie, to algorytm miałby złożoność sum(p=2;p<=n)n/p  =  n * H_n = Omega(nlogn).
Chyba powinienem wyjaśnić, że
H_n = 1/1 + ½ + ⅓ + … + 1/n czyli liczby harmoniczne są rzędu Theta(log n), o czym można się przekonać pewnie na kilka sposobów, ale mój ulubiony to popatrzeć sobie na wykres funkcji f(x)=1/x i narysować pod nim prostokąty niczym wieżowce na linii horyzontu (osi OX). Suma pól prostokątów to właśnie H_n, a linia nad nimi to funkcja której całka (czyli pole pod wykresem) to ln x. Oczywiście całkowanie jest poza zakresem podstawówki, więc to trochę nie fair wyjaśnienie. Popatrzmy jednak na ciąg 1/1 + ½ + ⅓ + … + 1/n i pogrupujmy te ułamki w taki sposób: (1/1) + (1/2+1/3) + (1/4+1/5+ … + 1/7) + … + 1/n, tzn każdy nawias zaczynając od 1/(2^k). W każdym nawiasie suma jest nie większa niż 1. Nawiasów jest nie więcej niż log(n)+1. A zatem H_n jest nie większe niż O(log(n)). Każdy z tych nawiasów jest też nie mniejszy niż ½, a jest ich nie mniej niż floor(log(n)). A zatem H_n jest też nie mniejsze niż Omega(log(n)).

A zatem sito Erastotenesa (o ile liczby są na tyle małe by mieściły się w rejestrach!) działa nie wolniej niż w nlogn. W praktyce jednak jest prawie liniowe, bo liczb pierwszych jest znacznie mniej niż n więc nie wchodzimy do ifa aż tak często. Empiryczna obserwacja głosi, że wśród liczb od 1 do n jest ich Omega(n / lg n), czyli tylko jedna na Omega(lg n) z liczb okazuje się być pierwsza. Oczywiście nie są one rozmieszczone po równo. Znane Wam pewnie twierdzenie, głosi, że dla dowolnie dużej liczby jaką sobie zażyczycie (nazwijmy ją g) może się zdarzyć się, że na odcinku g kolenych liczb naturalnych żadna nie będzie pierwsza. Przykładowo jest tak na odcinku od (g+1)!+2,(g+1)!+3,...(g+1)!+g+1. Ten wykrzyknik to “silnia”, n silnia to 1*2*3*..*n. Z drugiej zaś strony wydaje się, że nieskończenie wiele liczb pierwszych występuje w parach (tzw. bliźniacze liczby pierwsze), np. 5i7 czy 17i19. Obrazuje to chyba dość dobrze bałagan w rozmieszczeniu liczb pierwszych.

Sito można usprawniać na wiele sposobów, np. pomijając liczby parzyste (zamieniając x+=p na x+=2*p), lub zaczynając od x=p*p (wszystkie mniejsze wielkortoności x i tak już musiały zostać skreślone wcześniej).

Sito pomaga znaleźć _wszystkie_ liczby pierwsze z jakiegoś odcinka, ale nie jest zbyt efektywnym sposobem sprawdzania czy jedna konkretna liczba jest pierwsza czy nie. Oczywiście sito często wykorzystywane jest jako preprocesing (przetwarzanie wstępne) by móc potem szybciej odpowiadać na pytanie czy dana liczba jest pierwsza czy nie, ale jeśli mamy tylko jedno takie pytanie do odpowiedzenia, to da się znacznie prościej.

Najprostsze nawet podejście (sprawdzić podzielność przez wszystkie liczby z przedziału od 2 do x-1) ma złożoność liniową względem x, a więc nie gorszą niż sito.

Nieco więcej finezji wymaga zauważenie, że jeśli nawet x ma jakiś dzielnik z większy niż sqrt(x) to musi mieć też (do pary) jakiś dzielnik y mniejszy od sqrt(x), bo jeśli z*y=x, to nie możliwe jest by obie liczby z i y były większe od sqrt(x). Stąd prosty pomysł, by sprawdzać tylko dzielniki z zakresu od 2 do sqrt(x), co daje algorytm o złożoności O(sqrt(n)).

Co więcej jeśli x ma jakiś dzielnik y będacy liczbą złożoną, to musi mieć też dzielnik będący liczbą pierwszą. Można to pokazać przez indukcję: zakładając że y ma dzielnik będący liczbą pierwszą, to dokładnie ten sam dzielnik jest też dzielnikiem x. Ta obserwacja pozwala się skupić podczas poszukiwań dzielnika liczby x, tylko na liczbach pierwszych z zakresu 2 do sqrt(x) (tutaj może się nam przydać stablicowana lista liczb pierwszych uzyskana przez sito).

Powyższymy metodami, na zwykłej maszynie, możemy bawić się w szukanie liczb pierwszych nie większych niż 2^64. Niby dużo, bo to liczba większa niż kiedykolwiek zobaczycie na rachunku bankowym, ale w informatyce często zajmujemy się liczbami znacznie większymi niż liczba atomów we wszechświecie i to nie dlatego, że chcemy policzyć elektorny we wszechświecie, tylko dlatego, że liczby w informatyce oznaczają nie tylko ilości przedmiotów, ale też reprezentują same te przedmioty. Pomyślcie np. o zdjęciach w formacie JPG. Na dysku mają postać ciagu bitów. Ciąg bitów, to liczba w systemie binarnym. Jest to strasznie duża liczba i trzeba się nią umieć zająć.

W informatyce często opisujemy złożoność obliczeniową czy pamięciową danego algorytmu w odniesieniu do liczby n zwanej rozmiarem problemu. Powyżej, mówiąc, że O(sqrt(n)) kroków wystarczy by sprawdzić pierwszość liczby miałem na myśli n równe liczbie, którą testujemy. Czyli np. jeśli testujemy n=100, to potrzebujemy około 10 sprawdzeń.
Często jednak, przyjmujemy, że rozmiar problemu powinien mieć jakiś związek z rozmiarem danych na wejściu. Np. w problemach grafowych, mówimy, że rozmiarem jest liczba krawędzi, która odpowiada przecież długości opisu grafu na wejściu.
Jeśli popatrzeć na długość jakiejś liczby, to z grubsza odpowiada ona logarytmowi z tej liczby.
A w drugą stronę: jeśli popatrzeć na największą możliwą liczbę o danej długości, to jest ona wykładniczo wielka w stosunku do jej długości.
Przykładowo, jeśli interesują nas liczby o długości 100 bitów, to największa z nich to 2^100 - 1 czyli baaardzo dużo. Co gorsza nasz algorytm sprawdzania czy jest ona pierwsza, może potrzebować czasu około sqrt(2^100) = 2^50, czyli również kosmicznie dużo.
Patrząc tymi kategoriami, czyli, że n to długość liczby, to nasz algorytm ma złożoność 2^(n/2) czyli jest wykładniczy.

Żeby nie stracić kontaktu z tematem przewodnim (czyli RSA), warto zobaczyć tutaj pewną asymetrię. To nie jest tak, że wszystko co dotyczy 100-bitowych liczb jest kosmicznie trudne. Np. dodanie dwóch takich liczb do siebie, to jedno z prostszych zadań jakie może pojawić się na zawodach: zwykłe dodawanie pisemne wymaga raptem około 200 operacji dodawań pojedynczych bitów. Ogólnie dodawanie dwóch n-bitowych liczb wymaga tylko O(n) czasu.
Mnożenie jest ciutkę trudniejsze i zaraz sobie o nim opowiemy, ale nadal wymaga tylko wielomianowego czasu. Tymczasem jak na razie nasze “proste” sposoby sprawdzania czy coś jest liczbą pierwszą wymagają wykładniczego czasu. Jak się okazuje, da się to zrobić znacznie szybciej, ale nie będzie to proste. Powinniście w tym momencie zacząć czuć nasilające się uczucie, że są operacje, które dla dużych liczb robią się bardziej skomplikowane niż nam się to wydawało dla małych.

Zanim pokażę, jak szybko sprawdzać czy liczba jest pierwsza, popatrzmy na to jak szybko mnożyć dwie duże liczby.

Zacznijmy od metody, którą na pewno znacie: mnożenie pisemne. Potrzebna jest do tego kartka w kratkę, piszemy dwie liczby a i b jedna pod drugą, a nastepnie poniżej nich, wpisujemy w “równoległobok” wyniki mnożenia a przez kolejne cyfry b. Coś co robimy na codzień w systemie dziesiętnym, można też z powodzeniem zastosować w systemie binarnym: kolejne wiersze równoległoboka będą wynikiem mnożenia a przez kolejne bity b. Co miłe: bit może być równy tylko 0 lub 1. Mnożenie przez 0 zawsze daje 0, a mnożenie przez 1 zawsze daje a. W efekcie musimy tylko umieć do siebie dodać kilka poprzesuwanych kopii liczby a. Najprostszy sposób to po prostu dopisać do nich na ich końcu zera i użyć dodawania dużych liczb. Dodawanie działa w O(n), dodawań do wykonania mamy O(n), więc całość działa w O(n^2). Lekkim usprawnieniem może być nie dopisywanie zer tylko napisanie procedury dodawania w taki sposób by od razu zaczynała od przesuniętej odpowiednio pozycji.

Znacznie więcej finezji wymaga metoda “dziel i zwyciężaj”. Osobiście lubię myśleć, że wymyślił ją jakiś haker który potrzebował w asemblerze napisać mnożenie dwóch long longów przez siebie i nie mieściły mu się w rejestrach. Wyobraźcie to sobie: macie dwie liczby a i b, ale obie są tak długie, że nie mieszczą się w jednym rejestrze. W AH (czytaj: A high) trzymacie więc “górne” bity liczby a, zaś w AL trzymacie dolne. Czyli np. mając 64-bitową maszynę mamy AH*2^64+AL = a. Podobnie b rozbite zostało na BH i BL. To co chcecie policzyć to a*b, czyli :
AH*BH * 2^128 + (AH*BL+AL*BH)*2^64 + AL*BL.  Jak mi się udało to tak szybko ustalić? Bo to nic innego jak mnożenie pisemne dwóch liczb dwucyfrowych przez siebie, tylko z baaardzo dużymi cyframi (AH,AL razy BH,BL) a to akurat umiem robić. Jak się popatrzy co dokładnie robimy w mnożeniu pisemnym, to widać, że właśnie to co napisałem.
Czytając powyższy zapis wprost, widać, że da się wykonać to mnożenie wykonując 4 mniejsze mnożenia a potem parę dodawań i przesunięć.
Prawdziwy hakerski trick polega jednak na tym, by wykonać tylko 3 mnożenia, zamiast 4.
Przyjrzyjcie się najbardziej problematycznemu do policzenia nawiasowi, czyli:
(AH*BL+AL*BH)
W jaki sposób można uzyskać jednym mnożeniem coś podobnego do tego napisu?
Można np. pomnożyć (AH+AL)*(BL+BH) = (AH*BL + AH*BH + AL*BL+AL*BH).
Co prawda dostaliśmy oprócz tego co chcieliśmy jeszcze trochę śmiecia po środku, ale...tak tak, te śmieci, to są dokładnie te same wyrażenia, których i tak potrzebujemy w najstarszej i najmłodszej z trzech części ukłdanki.
Cały algorytm mnożenia wygląda więc tak:
X = AH*BH
Y = (AH+AL)*(BL+BH)
Z = AL*BL
return (X << 128) + ((Y-X-Z)<<64) + Z;
Wygląda może przekomplikowanie, ale udało nam sie zamiast 4 mnożeń zrobić 3. Czemu się tak cieszymy optymalizacją o 25%? Bo to co opisałem powyżej to tylko ilustracja jednego poziomu algorytmu dziel i zwyciężaj. Tak naprawdę należy sobie wyobrazić wielką rekurencyjną procedurę, w której mnożymy dwie baaardzo długie liczby. Dzielimy każdą z nich na pół, wykonujemy kilka (4 lub 3) pomocniczych mnożeń a potem raptem parę prostych dodawań i przesunięć. Te pomocnicze mnożenia również wykonujemy rekurencyjnie tą samą metodą, itd itd. aż dochodzimy do tak małych liczb, że mieszczą się w rejestrach i można je pomnożyć bez trudu. Różnica między 4 a 3 mnożeniami jest więc potęgowana przez to, że wykonujemy je na wielu poziomach rekursji. Popatrzmy osobno na analizę czasu działania przy 4 mnożeniach, a potem dla 3 mnożeń a poczujemy ogrom różnicy:
Zaczynamy od tego, że każą nam pomnożyć dwie liczby o długości n każda.
Mamy więc 1 problem o wielkości n.
Rozbijamy go na 4 mnożenia liczb o wielkości n/2. Mamy więc 4 problemy wielkości n/2.
Rozbijając dalej mamy kolejno:
16 problemów o wielkośc n/4
64 problemów wielkości n/8

4^k problemów wielkości n/(2^k).
Przy pewnej wielkości k (gdzieś w okolicach k = log n) problemy będą już tak małe, że zmieszczą się w rejestrach i będzie je można rozwiązać w jednym kroku bez rekursji.
Będziemy wtedy mieli 4^lg n = (2^2)^logn = (2^logn)^2 = n^2 problemów wymagających po jednym kroku, czyli co najmniej Omega(n^2) jednostek czasu.

Teraz popatrzmy co się dzieje przy 3 mnożeniach:
Mamy 1 problem o wielkości n.
Rozbijamy go na 3 mnożenia liczb o wielkości n/2. Mamy więc 3 problemy wielkości n/2.
Rozbijając dalej mamy kolejno:
9 problemów o wielkośc n/4
27 problemów wielkości n/8

3^k problemów wielkości n/(2^k).
Ich rozwiązanie dla k=lg n, wymaga tylko 3^lg n = (2^lg3)^lgn = n ^ (lg 3) = n ^ 1.58 kroków.

Co to oznacza w praktyce? Różnica między 100^2 = 10 000 a 100^1.58 ~= 1 478 jest kilkukrotna!
A my zamierzamy zająć się n=1024. Ale powoli.

Najbardziej wyrafinowaną znaną mi metodą mnożenia dwóch liczb jest użycie FFT. Niestety FFT sam ledwie rozumiem i nie jestem w stanie przystępnie wytłumaczyć go w ramach tego opowiadanka, ale naszkicuję ideę. FFT to sposób na radzenie sobie z mnożeniem wielomianów. Mnożenie wielomianów pod wieloma względami przypomina mnożenie liczb, chociaż jest nieco prostsze, bo nie występują w nim problemy z przenoszeniem podczas dodawania. Rozwiązanie polega więc na tym, by potraktować mnożone liczby jako wielomiany i potem sprytnie wykryć miejsca, w których powinno było zajść przenoszenie i wykonać je ręcznie w O(n). Samo FFT pozwala mnożyć wielomiany w czasie O(nlgn).

Do mnożenia liczb można też użyć macierzy Teoplitza i innych fascynujących metod, ale grunt, że da się to robić w czasie niewiele gorszym niż liniowy.

Obiecałem pokazać szybki sposób sprawdzania czy liczba jest pierwsza, ale zanim to nastąpi, musimy nauczyć się nie tylko dodawać i mnożyć, ale też potęgować. Podobnie jak mnożenie daje się sprowadzić do serii dodawań, podobnie potęgowanie da się zamienić na serię mnożeń. Co więcej, metoda z mnożeniem pisemnym pokazuje nam, że można tę radę traktować w bardziej wyrafinowany sposób, niż rozbijać 3*14 na 3*(1+1+1+1+1+1+1+1+1+1+1+1+1+1) i dodawać 3 do siebie 14 razy. Mnożenie pisemne podpowiada nam mądrzejszy sposób: zapisz sobie 14 jako 10+4 i osobno pomnóż 3 przez 4 a osobno przez 10 zapisz te liczby jedna pod drugą i dodaj do siebie. Warto zrozumieć mnożenie pisemne, bo nie jest to tylko “głupia sztuczka dla ludzi, żeby nie czuli się bezużyteczni bez kalkulatora”, tylko całkiem sprytny algorytm, który bazuje na rozdzielności mnożenia względem dodawania: 3*14 = 3*(10+4).
Podobne prawidła zachodzą dla potęgowania: 3^14 = 3^(10+4) = 3^10 * 3^4.
Można więc potęgować w sposób ślamazarny i naiwny 3^14 = 3*3*3...*3*3, co wymaga kosmicznie dużo czasu, lub spróbować jakoś sprytniej rozbić sobię pracę na mniejszą liczbę mnożeń.
Cześć z Was być może zna algorytm szybkiego potęgowania:
pow(x,k) =   k=0 ? 1 :  sqr( pow(x,k/2) ) * ( k%1 ? x : 1)
Kiedy algorytm - tak jak powyższy - jest rekurencyjny i dobrze się go rozumie, to warto spróbować zmienić optykę i zastanowić się jak wyglądałby on w wersji iteracyjnej. Pogłebia to zrozumienie tematu:)
Algorytm iteracyjny (który wcale nie odpowiada temu powyższemu) mógłby wyglądać tak:
for(i=0; (1<<i) <= k; ++i){
  if( k & (1<<i) ){
    result *= x;
  }
  x*=x;
}
Jeśli znaliście oba algorytmy, to super, jeśli nie, to poświęćcie chwilę by samemu ogarnąć czemu to działa. Pierwszy algorytm odpowiada algorytmowi mnożenia zwanego algorytmem “po rusku”, a drugi odpowiada mnożeniu pisemnemu. Tyle, że nie są to algorytmy mnożenia tylko potęgowania.

Oba algorytmy wykonują w najgorszym razie liczbę mnożeń proporcjonalną do długości wykładnika. Same mnożenia trwają jednak co raz wolniej, w miarę jak do wyniku domnażane są co raz większe liczby. W zasadzie to powżysze algorytmy nie mają zbyt wielkiego sensu w liczbach naturalnych, bo bardzo szybko skończy nam sie pamięć. Jeśli jednak umówimy się, że znaczek mnożenia oznacza mnożenie w Z_n, to dostajemy algorytmy działające w wielomianowym względem długości n czasie. (Tutaj pozwolę sobie lekko prześlizgnąć się nad kwestią jak szybko liczyć x%n, ale na odczepnego powiem, że algorytm dzielenia pisemnego does the trick).

Żeby sprawdzić czy liczba jest pierwsza, można (choć nie wiem czy ktoś miał odwagę spróbować) użyć algorytmu AKS. Jest to pierwszy znany ludzkości algorytm o złożoności wielomianowej (bodaj n^6 czy n^12) sprawdający pierwszość liczby n. Dokładniej: pierwszy deterministyczny, czyli nie używający rzutów monetą by sobie pomagać.

Algorytmy niedeterministyczne posiłkują się losowością (mówiąc obrazowo) gdy mają do wyboru jedną z dwóch opcji i spodziewają się, że jedna może doprowadzić do wyniku szybciej niż druga, ale nie wiedzą która z nich. Dokonują wtedy rzutu monetą i w 50% przypadków trafiają w dobrą drogę. Można to wykorzystać na wiele sposobów: np. do uśrednienia czasu działania pomiędzy tymi dwoma przypadkami, poświęcenia poprawności (mylenia się czasem) na rzecz szybkości, itp. Pewnie część z Was wie jak losowanie pivotu wpływa na skuteczność quicksorta. Algorytmu AKS nie rozumiem i z pewnością nie umiem wytłumaczyć nawet sobie. Rozumiem za to pewien algorytm zrandomizowany i wierzę, że nadaje się on do praktycznych zastosowań.

Algorytm Millera-Rabina z grubsza bazuje na pewnej koncepcji, którą można zilustrować na problemie ustalania czy zwierze jest kaczką czy psem (tak, wiem, że to głupi problem, ale wróćmy do koncepcji), że jeśli coś szczeka, to nie jest kaczką, a główny problem, to zmusić kaczkę podjerzaną o bycie psem, by zaszczekała. Jeśli coś nie szczeka, to nie wiadomo, czy jest kaczką czy psem, ale pewność, że jest kaczką rośnie, im dłużej szturchamy to coś, gwiżdżemy na nie, próbujemy częstować kiełbasą, a ono nadal nie szczeka.
Oczywiście w prawdziwym świecie możemy mieć też fuksa i zwierze wyda z siebie kwakanie, co ponad wszelką wątpliwość dowiedzie bycia kaczką, niestety jak się zaraz okaże, jedyny test jaki będziemy umieli przeprowadzać dotyczy szczekania:)

Aby móc użyć powyższej metodologii, trzeba znaleźć pewien odpowiednik szczekania, czyli zachowania zupełnie nie podobnego do kaczki, wśród zachowań liczb złożonych, zupełnie niepasujacych do liczb pierwszych. Jeśli liczba przejawi takie zachowanie, to będziemy wiedzieli, że jest złożona. Jeśli go nie przejawi, to … trudno, niewiele się dowiemy. Jeśli jednak sytuacja będzie się notorycznie powtarzać, to będzie rosła nasza pewność, co do tego, że jest to jednak liczba pierwsza.

Wyobraźmy sobie, że każdy pies lubi 75% rodzajów kiełbas, ale nie wiemy jakich, bo to sprawa indywidualna dla każdego psa. Jeden eksperyment polega na położeniu przed zwierzęciem kiełbaski jakiegoś typu i zobaczeniu czy zaszczeka. Jeśli jest to kaczka, to na pewno nie zaszczeka. Jeśli jest to pies, to to czy zaszczeka zależy od tego czy lubi daną kiełbasę czy nie. Gusta psa nie są losowe -- są ukształtowane deterministycznie przez jego wychowanie, geny i naturę. Gdyby tylko umiał mówić, to jutro powiedziałby, że lubi te same kiełbasy co lubił wczoraj -- pełny determinizm. Natomiast to co w tym eksperymencie może (i powinno być) losowe, to nasz wybór kiełbasy do ekseperymentu. Jeśli będziemy wybierali ją zupełnie losowo spośród wszystkich dostępnych gatunków, to z ppb 75% pies zdradzi się szczeknięciem. W pozostałych 25% przypadków, nie będziemy wiedzieli czy to pies czy kaczka. Po przeprowadzaniu dwóch ekseprymentów, jeśli zwierze nadal milczy, to prawdopodobieństwo, że jest psem spadnie do 25% z 25% czyli poniżej 6%. Po dziesięciu takich eksperymentach będziemy już prawie pewni (chociaż nigdy nie na 100%), że mamy do czynienia z kaczką.

Jak możemy mówić o zachowaniach liczb? Co odróznia liczbę pierwszą od złożonej? Zaczniemy od opisania paru zachowań typowych dla liczb pierwszych. Zachowania przeciwne do nich zdradzają bycie liczbą złożoną.

Zacznijmy od tego, że jeśli liczba p jest liczbą pierwszą, to dla każdej liczby a, zachodzi:
a^p = a  modulo p
Jest to tzw. małe twierdzenie fermata.

Pomyślmy o p jako o zwierzaczku, zaś o a jako o pewnym gatunku kiełbasy. Jeśli a^p =/= a modulo p, to pomyślmy : “zaszczekał!”, bo to zachowanie niepodobne do liczby pierwszej. Ten prosty test leży u podstaw algorytmu, który jest równie prosty, co błędny i polega na tym, by losować różne wartości a i sprawdzać, czy zachowana zostanie dla nich równość fermata.
Niestety istnieją kontrprzykłady, czyli liczby, które są złożone, a mimo to, dla każdego a jakiego byśmy nie próbowali, przechodzą one test fermata. Przykładowo: n=561, które dzieli się np. przez 3, ale dla każdego a zachodz a^561 = a modulo 561. To trochę taki pies co nie lubi żadnej kiełbasy.
Celowo nie wyjaśniam małego twierdzenia fermata, bo zaraz będziemy udowadniali sobie coś znacznie ciekawszego (twierdzenie Eulera i jeszcze ogólniejsze twierdzenie Lagrangea). Brzmi strasznie, ale to w zasadzie nic trudnego i w kółko o tym samym.
Co do tego czemu w zasadzie n=561 jest takie wyjątkowe, to zapiszę poniżej parę faktów, które to wyjaśniają, pod warunkiem, że zrozumie się cały ten wywód a zwłaszcza kawałek o twierdzeniu Lagrangea, więc jak kogoś to intryguje to może do tego potem wrócić:
561 = 3 * 11 * 17
zaś 560 dzieli się przez 2, 10 i 16, czyli (560-1) dzieli się przez (3-1), (11-1) i (17-1), czyli 560-1 dzieli się przez phi(561).

Test Millera-Rabina jest bardziej finezyjny od testu Fermata w zmuszaniu psa do szczekania. Oprócz małego twierdzenia Fermata, bazuje na jeszcze jednej właściwości liczb pierwszych: jeśli p jest liczbą pierwszą, to x*x = 1 modulo p, tylko wtedy gdy x=1 lub x = p-1.
Używając nieco zgrabniejszego języka: w Z_p są tylko dwa pierwiastki z jedynki: 1 i -1.

To, że 1 i -1 są pierwiastkami z jedynki jest oczywiste -- trudne jest to, że nie ma innych.

Gdyby istniał inny pierwiastek z jedynki (nazwijmy go x) to musiałoby być prawdą, że 0 = x*x-1 = (x-1)*(x+1) modulo p, czyli że p dzieli (x-1)*(x+1). Ale p jest liczbą pierwszą, więc dzieli iloczyn dwóch liczb tylko wtedy, gdy dzieli jedną z nich. Ale nie może dzielić ani x-1 ani x+1. Sprzeczność kończy dowód.

Warunek, że a^p = a, można inaczej zapisać jako a^(p-1) = 1 (bo i tak nie będziemy się bawili zerem). Możemy też śmiało założyć, że p jest nieparzyste, bo dla parzystych liczb sprawdzanie czy p jest parzyste, jest za proste:) A zatem p-1 jest parzyste. Liczby parzyste da się zawsze przedstawić w jednoznaczny sposób jako d*2^s , gdzie d jest nieparzyste (z resztą nieparzyste też, ale nimi się już nie zajmujmy). Żeby to zobaczyć, wyobraźcie sobie zapis binarny liczby: na końcu ma s zer, a na początku jakąś liczbę d kończacą się jedynką. Wiemy zatem, że dla p będącego liczbą pierwszą i każdego a powinno być a^(d*2^s) = 1 modulo p.

Ile może być w takim razie równe x=a^(d*2^(s-1)) ?
Zauważmy, że x*x = x^2 = a^(d*2^(s-1)) ^2 = a^(2*d*2^(s-1)) = a^(d*2^s)  = 1, a dla liczb pierwszych oznacza, to, że x=1 lub -1.
Idąc dalej tym tropem, widzimy, że a^(d*2^(s-i)) dla kolejnych i=0,1,2,... będzie przez pewien czas równe 1, a potem będzie -1, chyba, że dojdziemy do a^d i nadal będziemy mieli 1.

Z powyższych obserwacji wyłania się taki o to test dla losowego a:
Policz x=a^d, jeśli jest równe 1 lub -1, to koniec ekseprymentu i niczego się nie dowiedzieliśmy.
W pozostałych przypadkach podnieś x do kwadratu i sprawdź ile wyszło. Jeśli 1 to p nie jest liczbą pierwszą. Jeśli -1 to koniec eksperymentu. W pozostałych przypadkach podnieś x znowu do kwadartu itd, aż dojdziesz do a^(p-1) -- jeśli nadal nie uzyskałeś 1, to nie jest to liczba pierwsza.

Niestety nie umiem pokazać dowodu, ale podobno jeśli p nie jest liczbą pierwszą, to aż dla 75% wartości a powyższyszy test kończy się wykryciem, że p jest złożona.
Czas działania tego algorytmu zależy tylko od operacji potęgowania i paru mnożeń, jest więc wielomianowy względem długości p oraz liczby eksperymentów (liczb a), które chcemy przeprowadzić. Mamy więc algorytm, którego czas działania jest deterministyczny, ale może się mylić. Algorytmy zrandomizowane, które mogą się mylić, ale działają szybko nazywamy Monte Carlo, zaś algorytmy które nie mylą się, ale ich czas działania jest niedeterministyczny nazywamy Las Vegas. Nazwy oczywiście pochodzą od dwóch światowych centrów hazardu.

Gdy już umiemy szybko sprawdzać czy liczba jest liczbą pierwszą, to możemy z tego skonstruować algorytm znajdujący liczby pierwsze o zadanej długości -- wiemy, że stosunkowo wiele z liczb na świecie jest liczbami pierwszymi, więc wystarczy losowo wybierać sobie liczby o odpowiedniej długości i za którymś razem uda nam się trafić w liczbę, która okaże się być pierwsza. Tym razem mamy przykład algorytmu z klasy Las Vegas -- kiedyś nam się musi udać, ale nie wiadomo ile dokładnie to potrwa.

Pokazaliśmy sobie kilka algorytmów sprawdzających czy n jest liczbą pierwszą, ale co ciekawe, te z nich, które były szybkie umiały tylko udzielić odpowiedzi TAK/NIE, za to nie zdradzały nawet jednego dzielnika liczby n, w przypadku gdy okazywała się ona złożona. Ot, trzeba uwierzyć im na słowo, że “nie jest liczbą pierwszą, bo nie zachowuje się jak liczba pierwsza”.

Problem faktoryzacji, czyli poznania czynników pierwszych liczby n w czasie wielomianowym od jej długości jest do dzisiaj nierozwiązany i to nawet w najprostszym przypadku, gdy n ma tylko dwa dzielniki: n=p*q. Tzn. jeśli ktoś w tajemnicy wybierze jakieś dwie liczby pierwsze i zdradzi nam tylko ich iloczyn, to nie jest znany szybki sposób na ich odgadnięcie.
Właśnie ta asymetria między mnożeniem a faktoryzacją leży u podstaw RSA jak się niedługo przekonamy.

Najpierw musimy jednak wrócić do tematu mnożenia i dzielenia w Z_n.
Miałem opowiedzieć o tym jak powinno być zdefiniowane dzielenie w Z_n, żeby dobrze współgrało z mnożeniem, oraz wyjaśnić czemu dla n niebędących liczbą pierwszą sprawa się komplikuje.

Zamiast próbować zdefiniować dwuargumentową funkcję jaką powinno być dzielenie, zacznę od uproszczenia sobie sprawy, wprowadzając pojęcie odwrotności: odwrotność x, oznaczana x^-1, to ma być odpowiednik 1/x, czyli taka liczba, która przemnożona przez x da 1. Nie zawsze taka liczba istnieje i wtedy x nie ma odwrotności. Czasem (w jakichś dziwnych algebrach) może być kilka takich liczb i wtedy też ciężko mówić o odwrotności. Po co jednak w ogóle komu takie pojęcie? Okazuje się, że jeśli ustalimy dla każdego x jego odwrotność x^-1, to wystarczy nam to, by opisać dzielenie dowolnych dwóch liczb przez siebie. Mianowicie wystarczy się umówić, że x/y = x*(1/y) = x*(y^-1). Zauważmy, że tak zdefiniowane dzielenie zachowuje się tak jakbyśmy chcieli, czyli jeśli x/y = z to y*z=x -- oto dowód:
x / y = z  mnożymy obustronnie przez y :
y * (x / y) = y *z
y * x * (y^-1) = y * z
x * 1 = y*z
(W powyższym rozumowaniu korzystałem z przemienności)

Okazuje się, że jeśli p jest liczbą pierwszą, to w Z_p każda liczba oprócz 0 ma swoją odwrotność. Pokazał to Euklides, w swoim twierdzeniu, że dla każdych liczb x i y istnieją takie a i b, że:
x*a + y*b = gcd(x,y).
Jeśli w tym twierdzeniu za y podstawimy p, zaś x będzie liczbą ze zbioru {1,...,p-1}, to mamy:
x*a + p*b = gcd(x,p) = 1, czyli x*a = 1 modulo p, więc a jest tą szukaną odwrotnością x.
Oczywiście 0*x = 0, więc nie może nigdy istnieć odwrotność 0.

Korzystając z powyższego twierdzenia dla n nie będących liczbą pierwszą, widzimy, że na pewno odwrotność w Z_n istnieje dla tych x, które są względnie pierwsze z n.

A co jeśli x i n nie są względnie pierwsze? Czy może istnieć y, takie, że:
x* y = 1 modulo n? Czyli inaczej mówiąc:  x*y = 1 + kn ? Niestety lewa strona dzieli się przez gcd(x,n) podczas gdy prawa nie, więc to równanie nie może mieć rozwiązania.
A zatem odwrotność mają tylko te liczby, które są względnie pierwsze z n... musimy tylko jeszcze pokazać, że nie istnieją dwie różne liczby, będące odwrotnością x.
Pokażę to niewprost. Powiedzmy, że x jest względnie pierwsze z n i znaleźliśmy dwie różne liczby a i b, takie, że x*a = 1 = x*b.
Popatrzmy sobie na napis a*x*b. Ile on jest równy? Z jednej strony patrząc (a*x)*b=1*b = b (skorzystałem z przemienności). Z innej a*(x*b)=a*1=a. Czyli musi być a=b .

Twierdzenie Euklidesa jest wnioskiem z analizy algorytmu Euklidesa.
Jest to algorytm znajdujący gcd(a,b) według następującego schematu: bez straty ogólności załóżmy, że a<=b. Jeśli a = 0, to gcd(a,b)=b, bo zero dzieli się przez każdą liczbę, zaś największa liczba przez jaką dzieli się b, to b. Jeśli zaś a > 0, to szukany największy wspólny dzielnik dzieli nie tylko a i b, ale także ich różnicę: b-a. Co więcej jeśli jakaś liczba dzieli b-a, oraz a, to dzieli też b. Stąd gcd(a,b)=gcd(b-a,a). Możemy więc rekurencyjnie znaleźć gcd dla dwóch innych liczb, których suma jest mniejsza niż oryginalnie, więc nieuchronnie zbliżamy się do rozwiązania, bo nie istnieje nieskończenie długi ciąg malejący liczb naturalnych.

Gdzie tutaj widać to twierdzenie? Jeśli przypatrzymy się kolejnym wywołaniom rekurencyjnym, algorytmu Euklidesa, to zauważymy, że dwa argumenty z jakimi wywoływana jest funkcja gcd są tzw. kombinacjami liniowymi oryginalnych a i b, od których wszystko się zaczeło: algorytm tylko zamienia je miejscami lub odejmuje jednen z argumentów od drugiego. Jeśli więc na wejściu dostał jakieś dwie liczby postaci xa+yb oraz ua+vb (oczywiście na samym początku tak właśnie jest jeśli przyjać x=1,y=0,u=0,v=1), to albo się zakończy (gdy xa+yb = 0 i ua+vb = gcd(a,b)) albo wywoła się rekurencyjnie zamieniając je miejscami, lub odejmując jedną od drugiej czyli z (x-u)a+(y-v)*b, a więc także kombinacją liniową.

Algorytm Euklidesa wzbogacony o przekazywanie współczyników x,y,u,v nazywa się czasem “rozszerzonym”. W praktyce przydaje się on do znajdywania odwrotności liczb modulo n. Co ciekawe okazuje się, że z powyższych 4 argumentów po optymalizacjach wystarczy przekazywać tylko dwa.

W oryginale algorytm Euklidesa używa tylko operacji odejmowania, co w skrajnych przypadkach może oznaczać strasznie dużo wywołań rekurencyjnych (np. dla gcd(n,1) może ich być n). Jedną z popularnych optymalizacji jest zastąpienie odejmowania operacją modulo (czyli jakby robieniem wielu odejmowań na raz). W wersji rozszerzonej trzeba też pamiętać by odejmować wielokrotność współczyników a nie tylko raz. Po takiej poprawce algorytm Euklidesa działa w czasie logarytmicznym względem sumy argumentów, czyli liniowym względem ich długości. Żeby to zobaczyć, wystarczy zauważyć, że a%(b%a) <= a/2, czyli po dwóch krokach algorytmu długość liczby zmniejsza sie o co najmniej jeden bit. Jednym z trudniejszych przykładów dla algorytmu Euklidesa są dwie kolejne liczby Fibonacciego (czemuż?).

Gdy mamy do czynienia z długimi liczbami, nie można jednak zakładać, że operacja modulo będzie działała szybko. Warto więc znać inny algorytm na obliczanie gcd :
Jeśli a i b są parzyste, to gcd(a,b) = 2*gcd(a/2,b/2).
Jeśli tylko a jest parzyste, to gcd(a,b) = gcd(a/2,b).
Jeśli tylko b jest parzyste, to gcd(a,b) = gcd(a,b/2).
Jeśli obie są nieparzyste, to gcd(a,b) = gcd(a,(b-a)/2).
Warunek stopu możemy dać podobny jak poprzednio (gdy a = 0 zwróć b).
Jak widać, w tym algorytmie za każdym razem odcinamy co najmniej jeden bit od danych wejściowych, a przy tym nigdzie nie używamy niczego bardziej skomplikowanego niż odejmowanie.
Trochę więcej finezji wymaga tutaj odtworzenie współczyników kombinacji liniowej o których mowa w twierdzeniu Euklidesa. Jeśli jednak chcemy użyć tego algorytmu tylko po to by policzyć odwrotność z jakiejś liczby, czyli wywołujemy go z gcd(x,p)=1, to wiemy, że przypadek pierwszy nigdy nie zajdzie, a w pozostałych trzeba czasem coś tam pomnożyć przez (b+1)/2 lub (a+1)/2, albo jeszcze coś innego zachachmęcić, ale ogólnie da się jakoś sobie poradzić.

W przypadku, gdy p jest liczbą pierwszą, to każda liczba w Z_p inna niż 0, jest względnie pierwsza z p, więc ma odwrotność, dlatego da się zdefiniować w Z_p dzielenie. Oczywiście przez 0 nie będzie można dzielić. Taki twór, w którym da się dodawać, mnożyć i dzielić przez wszystko prócz zera nazywa się ciałem (jest jeszcze parę innych warunków, np. rozdzielność mnożenia względem dodawania). Przykładem ciała są liczby rzeczywiste, ale też liczby wymierne.

Twór, w którym istnieje mnożenie (działanie łączne) i operacja odwrotności nazywa się grupą. Z_p^* czyli {1,...,p-1} z mnożeniem modulo p jest grupą.

Grupą jest też Z_n^* = { a |  gcd(a,n) = 1} z mnożeniem modulo n -- wystarczy tylko zauważyć, że mnożenie dwóch liczb względnie pierwszych z n, musi dać liczbę względnie pierwszą z n.

Jeśli jakiś niepusty podzbiór elementów grupy jest zamknięty ze względu na mnożenie, to nazywamy go podgrupą. Np. {1} jest zawsze podgrupą Z_p^*. Dokładniej, to oficjalna definicja wymaga, by był też domknięty na branie odwrotności oraz żeby zawierał jedynkę, ale dla grup skończonych (a innymi nie będziemy się zajmować) te warunki spełniają się same. Żeby się o tym przekonać, zacznijmy od dowolnego elementu podgrupy x i patrzmy na jego kolejne potęgi: x, x*x, x*x*x, … Jako, że mamy coś zamkniętego na mnożenie, to wszystkie te liczby należą do tego czegoś. Ale to coś jest skończone, więc w końcu musi się coś powtórzyć, np. x^i = x^j.
Czyli x^i = x^i * x^(j-i). Mnożąc obustronnie przez (x^i)^(-1) dostaniemy, że 1 = x^(j-i). Czyli gdzieś w tym ciągu musiała się pojawić jedynka. Co więcej, x^(j-i-1) jest odwrotnością x.

Okazuje się, że liczba elementów w podgrupie musi dzielić liczbę elementów w grupie. Pokażę to dzieląc wszystkie elementy w grupie na równoliczne podzbiory, z których jednym będzie dowolnie zadana podgrupa. Powiedzmy, że interesująca nas grupa to G, a jej podgrupą to H. Podzielę teraz wszystkie elementy grupy G na zbiory wg następującej zasady: a i b będą w tym samym zbiorze, wtedy i tylko wtedy, gdy istnieje element h należący do h, taki, że a*h = b.
Twierdzę, że wszystkie zbiory będą miały tyle samo elementów co H i że jeden z nich będzie po prostu zbiorem H.
Zanim jednak udowodnie to twierdzenie, muszę wyjaśnić, że zaproponowany przeze mnie sposób dzielenia elementów na tzw. warstwy, w ogóle jest poprawnie zdefiniowany, tzn. że nie ma w nim jakichś paradoksów, w stylu “no przecież się nie rozerwę”.
Tak naprawdę, to muszę pokazać, że opisana przeze mnie relacja bycia w tym samym zbiorze jest relacją równoważności, czyli jest zwrotna, symetryczna i przechodnia, czyli mówiąc po ludzku: reguły podziału są zgodne ze zdrowym rozsądkiem tj.:
1. każdy element ma prawo (i obowiązek) przebywać ze samym sobą w jednym zbiorze
2. jeśli a ma być z b w jednym zbiorze, to b ma być z a
3. jeśli a ma być z b, b ma być z c, to a ma być z c
Warunki te są spełnione bo:
1. liczba 1 należy do H, zaś a*1=a, więc udało nam się znaleźć odpowiednie h = 1.
2. jeśli do H należy h, takie, że a*h = b, to należy też odwrotność h. Mnożąc obustronnie przez nią mamy a*h*h^-1 = a = b*h^-1, czyli znaleźliśmy świadka dla pary b,a
3. jeśli a*h = b, oraz b*h’ = c, to a*(h*h’) = c, zaś h*h’ musi należeć do H, bo jest zamknięte na mnożenie
Jeden ze zbiorów (ten zawierający 1) to po prostu H.
By się o tym przekonać zauważmy, że 1*h=h, więc każdy element z H musi należeć do tego samego zbioru co 1. Zauważmy też, że jeśli b należy do tego samego zbioru co 1, to musi istnieć h, takie, że 1*h = b. Ale to znaczy, ze h=b, czyli b należy do H.
Wszystkie zbiory mają tyle samo elementów, o czym najłatwiej się przekonać pokazując bijekcję między zbiorem H a dowolnym innym. Bijekcja to funkcja różnowartościowa i “na”, czyli taka co łączy w pary elementy dwóch zbiorów. Istnienie bijekcji oznacza, że elementów jest tyle samo w dwóch zbiorach. Weźmy sobie jakikolwiek inny zbiór K oraz jakiegoś reprezentanta k należącego do K. Bijekcja między H i K, to po prostu mnożenie przez k. Czyli f(x) = x*k. Zauważmy, że ta funkcja jest różnowartościowa, bo f(x)=f(y) oznacza x*k = y*k, a to po pomnożeniu stronami przez k^-1 oznacza x=y. Zauważmy, że funkcja jest w zbiór K, bo f(h) = h*k, czyli f(h) i k muszą być w tym samym zbiorze wg moich reguł. Zauważmy wreszcie, że funkcja jest “na”, tzn. dla każdego elementu w zbiorze K, jest coś co na niego przechodzi. Przykładowo jeśli x należy do K, to musi istnieć h takie, że k*h = x. Ale to oznacza, że f(h) = x.
Skoro każda warstwa ma tyle samo elementów co H, a każdy element G należy do dokładnie jednej warstwy, to liczba elementów w H, czyli |H| musi dzielić |G|.

To było twierdzenie Lagrangea : liczba elementów w podgrupie musi dzielić liczbę elementów w grupie.

Szczególnym wnioskiem z twierdzenia Lagrangea jest małe twierdzenie fermata. Widzieliśmy już, że zaczynając od dowolnego x i biorąc kolejne jego potęgi: x, xx, xxx, … modulo p uzyskamy coś co jest zamknięte na mnożenie, a zatem jest podgrupą Z_p^*. Liczba różnych liczb w tym ciągu musi być zatem dzielnikiem p-1, bo tyle elementów ma Z_p^*. Ale to oznacza, że p-ty element tego ciągu się zapętlił, tj. x^p = x (no dobra, to nie dokońca to znaczy, ale tak właśnie jest).

Tę zabawę z mnożeniem przez siebie x możemy też przeprowadzić w Z_n, dla n nie będącego liczbą pierwszą i wtedy też dostaniemy jakąś podgrupę _wygenerowaną_ przez x. Tym razem będzie to podgrupa Z_n^*, więc liczba jej elementów będzie musiała dzielić liczbę elementów Z_n^*. Ile elementów ma Z_n^*? Euler nazwał tę liczbę phi(n). Twierdzenie Eulera brzmi, że x^phi(n) = 1 modulo n. Teraz widzimy, że jest to szczególny przypadek twierdzenia Lagrangea i uogólnienie małego twierdzenia fermata.

Liczbę phi(n) można dość prosto wyliczyć, jeśli się zna rozkład liczby n na czynniki pierwsze.
Przykładowo, wiemy już, że jeśli p jest liczbą pierwszą, to phi(p) = p-1.
A co jeśli n = p^k dla k>1? Innymi słowy, ile jest liczb naturalnych względnie pierwszych z p^k, mniejszych od p^k ? W zasadzie każda, która nie dzieli się przez p. A zatem p^k - p^(k-1).
Jeśli n rozkłada się na różne liczby pierwsze, to do policzenia phi(n) przyda się znać rozkład n na dwie względnie pierwsze liczby, czyli n=a*b, gdzie gcd(a,b)=1. Wtedy phi(n) = phi(a)*phi(b). Ta równość jest prostą konsekwencją chińskiego twierdzenia o resztach.
Chińskie twierdzenie o resztach wg anegdoty pochodzi od sposobu w jaki robiono przegląd wojsk. Żeby policzyć szybko ilu jest żołnierzy, kazano się im ustawić w 2 szeregu, potem w 3 szeregu, potem w 5 szeregu itd, za każdym razem notując tylko ile osób stało w ostatniej kolumnie, tj. jaki był wynik z dzielenia liczby żołnierzy przez kolejne liczby pierwsze. Znając te reszty nadworny matematyk dokonywał paru kluczowych obliczeń i ustalał bezbłędnie liczbę żołnierzy.

Chińskie twierdzenie o resztach, głosi bowiem, że jeśli mamy ciąg k liczb które są ze sobą względnie pierwsze: m[1],...,m[k], to dla każdej kombinacji reszt z dzielenia przez nie: r[1],..,r[k] istnieje dokładnie jedna liczba naturalna, mniejsza niż m[1]*...*m[k] która daje takie właśnie reszty.

Dowód twierdzenia zacznijmy od zauważenia, że możliwych kombinacji reszt jest własnie m[1]*..*m[k], jeśli więc pokażemy, że żadne dwie liczby w podanym zakresie nie dają dokładnie tej samej kombinacji reszt, to twierdzenie będzie udowodnione. Załóżmy zatem niewprost, że jakieś dwie liczby mniejsze niż m[1]*...*m[k] dają tę samą kombinację reszt z dzielenia przez m[1],...,m[k]. Odejmując te dwie liczby od siebie, dostaniemy liczbę podzielną przez m[1],...,m[k]. Ale te liczby są względnie pierwsze więc najmniejsza liczba podzielna przez nie wszystkie to m[1]*...*m[k]. Ale różnica dwóch liczb z tego zakresu nie może być tak wielgachna.

Chińskie twierdzenie o resztach pokazuje nam bijekcje między liczbami {0,..,a*b-1} a parami reszt ze zbioru {0,..,a-1} x {0,...,b-1}, o ile tylko a i b są względnie pierwsze. Jeśli więc chcemy policzyć phi(a*b), czyli liczbę liczb względnie pierwszych z a*b, to wystarczy zauważyć, że każda taka liczba x musi mieć gcd(x,a)=1 oraz gcd(x,b)=1 a to (po wykonaniu jednego kroku algorytmu Euklidesa) oznacza tyle, że gcd(x%a,a) = 1 oraz gcd(x%b,b)=1. Jak wiadomo x%a to jakaś liczba mniejsza niż a. Ile jest takich liczb względnie pierwszych z a? Dokładnie phi(a). Podobnie dobrych reszt z dzielenia przez b jest dokładnie phi(b). Jeśli obie reszty są dobre, to cała liczba x też jest dobra. Czyli musimy policzyć ile jest par dobrych reszt. A jest ich oczywiście dokładnie phi(a)*phi(b) i każda para reszt odpowiada dokładnie jednemu x, które jest dobre. A zatem dobrych x, jest phi(a)*phi(b).

Mamy zatem całkiem niezły algorytm na obliczanie phi(n) o ile znamy faktoryzację n = p[1]^k[1] *...*p[s]^k[s] . Mianowicie phi(n) = phi(p[1]^k[1]) * … * phi(p[s]^k[s]) = (1-1/p[1])*(p[1]^k[1])...*(1-1/p[s])*(p[s]^k[s]) =  (1-1/p[1])*..*(1-1/p[s])*n.

W szczególności jeśli n=p*q, gdzie p i q są liczbami pierwszymi to phi(n)= (p-1)*(q-1).

Teraz możemy w reszcie zacząć gadać o RSA.

Zaczynamy od tego, że w sekrecie przed resztą świata znajdujemy dwie duże (około 1024 bitów) liczby pierwsze: p i q. Niech n=p*q. Mnożenie jest proste, a faktoryzacja trudna, więc możemy śmiało wyliczyć n i opublikować je na cały świat, a i tak nikt nie odgadnie jakie było p i q.
Z twierdzenia Eulera wynika, że dla każdego x względnie pierwszego z n (a jest ich kosmiczna większość) zachodzi: x^((p-1)*(q-1)) = 1. Szczerze mówiąc, to nawet x^lcm(p-1,q-1) musi być równe 1 o czym można się przekonać patrząc osobno na x modulo p, a osobno na x modulo q i patrząc co sie dzieje gdy podniesiemy je do potęgi podzielnej jednocześnie przez p-1 jak i q-1.
W każdym razie grunt, że znamy pewną liczbę M, taką, że dla każdego x, x^M = 1. Co więcej póki co znamy ją tylko my, bo tylko my znamy dokładne wartości p i q.
Teraz wybieramy sobie (najlepiej losowo, ale jeśli jesteśmy uprzejmi dla świata, to wybierzemy raczej dość krótkie) e będące liczbą względnie pierwszą z M.
Owo e nazywamy wykładnikiem szyfrowania (e jak encryption) i ogłaszamy całemu światu jako publiczny klucz do szyfrowania wiadomości dla nas.
Skoro e jest względnie pierwsze z M, to znaczy, że należy do Z_M^*. A skoro tak, to musi istnieć w Z_M^* jego odwrotność d, czyli liczba taka, że e*d = 1 modulo M. Wiemy nawet jak znaleźć takie d przy pomocy algorytmu Euklidesa.
Owo d póki co umiemy policzyć tylko my, bo tylko my znamy wartość M.
Liczbę d trzymamy w sekrecie. To będzie nasz klucz deszyfrujący (d jak decryption).

Algorytm szyfrowania zakłada, że dane do szyfrowania potrafimy zapisać w postaci liczby nie większej niż n. Jeśli np. nasze p i q miały około 1024 bitów, to n ma około 2048 bitów, więc wiadomość nie może być dłuższa niż ćwierć kilobajta. Jeśli jest dłuższa, to tniemy ją na krótsze kawałki i każdy szyfrujemy osobno. Tak więc do zaszyfrowania mamy liczbę x nie większą niż n.
Szyfrowanie polega po prostu na podniesieniu x^e modulo n.
Deszyfrowanie jest równie proste. Wystarczy zaszyfrowaną wiadomość podnieść do potęgi d.
Zauważmy, że (x^e)^d = x^(e*d).
Istnieje maleńka szansa, że pechowo x nie jest względnie pierwsze z n, czyli, że x dzieli się przez p lub przez q. Jest to szansa rzędu 1 do 2^1024 czyli możemy ją zaniedbać. Załóżmy więc, że x należy do Z_n^*, czyli, że x^M = 1. Wiemy, że e*d = 1 modulo M. Łącząc te dwa fakty, mamy, że x^(e*d) = x^(1+kM) = x^1 * x^(kM) = x * (x^M)^k = x * 1^k = x * 1 = x.
Czyli deszyfrowanie działa.

 

0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com