Do spisu treści tematu 5

5.3.2 Kryptografia a generator liczb losowych w systemie Linux




Spis treści:

W tym tekście opisuję generator liczb losowych w Linuxie oraz cele do jakich może zostać wykorzystany. Generator ten jest dość skomplikowany, dlatego uznałem, że warto przedstawić najpierw przyczyny, dla których jest w ogóle potrzebny oraz pewne techniki stosowane nie tylko w jego kodzie. Tak więc strona ta dzieli się na dwie części: ogólną, dotyczącą kryptografii i jej związku z generatorami liczb losowych, oraz bardziej szczegółową, dotyczącą budowy podprogramu obsługi urządzenia random.c.


Kryptografia

Obecnie technik kryptograficznych używa się głównie do dwóch celów:

Do realizacji obu tych celów stosuje się podobne metody, często korzystając z tzw. kluczy publicznych. Niegdyś używano jedynie kluczy tajnych - obecnie nie zarzuca się tego zupełnie, jednak łączy się tę metodę z metodą kluczy publicznych.

Klucz - publiczny lub tajny

Mówiąc o szyfrowaniu mamy na myśli parę funkcji: f i g, przy czym f będzie szyfrować, a g odszyfrowywać. Nadawca komunikatu K przekazuje odbiorcy f(K), odbiorca zaś obliczy g(f(K))=K. Jeżeli by się używało zawsze tych samych funkcji f i g, to groziłoby, że ktoś wreszcie złamie nasz szyfr. Co więcej, nie wiadomo, jak przekazać sobie opis tych funkcji. Pamiętajmy, że coś takiego, jak np. "zamiast litery 'a' wstaw 'b', zamiast 'b' wstaw 'c'..." jest banalne do złamania. Zachodzi więc potrzeba jakiegoś sparametryzowania funkcji f i g. Wtedy nadawca, mając komunikat K i parametr KLn, wysyła odbiorcy f(K, KLn). Natomiast odbiorca posiada swój parametr KLo i oblicza K=g(f(K, KLn), KLo). Parametry KLn i KLo nazywa się kluczami.

Powyższe postępowanie ma sens wtedy, gdy wielkość KLn i KLo nie jest przesadna - nadawca i odbiorca muszą się bowiem jakoś umówić co do wartości tych parametrów. Zwykle też funkcje f i g nie są utrzymywane w tajemnicy: ich kod jest dostępny publicznie. Natomiast klucze są zwykle sekretne. Typowy jest przypadek, gdy KLn=KLo jest liczbą o długości kilkudziesięciu (lub kilkuset) bitów. Jeżeli KLn=KLo, to odbiorca i nadawca muszą się jakoś umówić, jaki klucz wybrać. Nie mogą też nigdy zdradzić tego klucza, gdyż każdy mógłby wtedy mieć dostęp do ich tajemnic. Taka metoda szyfrowania nazywa się szyfrowaniem z kluczem tajnym. Kłopot, jaki powstaje przy używaniu tej metody, to konieczność uzgodnienia klucza przez obie strony "na boku", co często nie jest możliwe.

Inaczej jest przy tak zwanym szyfrowaniu z kluczem publicznym. Wówczas KLn!=KLo, co pozwala na to, by klucz KLn był ogólnie znany. Klucz KLo musi oczywiście być tajny niezależnie od przyjętej metody szyfrowania. W takiej sytuacji KLn nazywa się kluczem publicznym, a KLo kluczem prywatnym.

Idea szyfrowania z kluczem publicznym

Szyfrowanie z kluczem publicznym zostało po raz pierwszy zaproponowane przez Diffiego i Hellmana jako rozwiązanie problemu przekazywania zwykłych kluczy tajnych. Każdy, kto chce szyfrować swoje komunikaty, wybiera sobie parę kluczy: klucz publiczny (KLn) oraz klucz prywatny (KLo), które mają tę własność, że g(f(K, KLn), KLo)=K dla każdego komunikatu K. Następnie informuje wszystkich o wartości swojego klucza publicznego (KLo).

Jeżeli Prosiaczek chce nadać komunikat K do Puchatka, to korzysta jedynie z kluczy Puchatka (a nie ze swoich). Po prostu odczytuje z jakiegoś miejsca publiczny klucz Puchatka (KLn) i oblicza SZ=f(K, KLn). Następnie wysyła do Puchatka komunikat SZ. Puchatek po otrzymaniu komunikatu SZ bierze swój klucz tajny (KLo) i oblicza g(SZ, KLo)=K. Widzimy zatem, że Prosiaczek zdołał poinformować Puchatka o czymś, o czym Kłapouchy nigdy się nie dowie (o ile nie zgadnie prywatnego klucza Puchatka).

Metoda kluczy publicznych w prosty sposób rozwiązuje też drugi poważny problem kryptograficzny - problem weryfikacji tożsamości. O tym jednak napiszę nieco dalej.

Oczywiście zasadniczym problem implementacji szyfrowania z kluczem publicznym jest zapewnienie, że, znając funkcje f i g oraz wartość klucza publicznego KLn, nie da się obliczyć w rozsądnym czasie wartości klucza prywatnego KLo. A przecież jest to tylko problem rozwiązania pewnego równania: g(f(K, KLn), X)=K dla każdego K. Wystarczy z tego równania obliczyć X, by nic już nie było dla nas tajemnicą.

Z tej właśnie przyczyny funkcje f i g nie mogą być całkiem dowolne - muszą mieć specjalne własności kryptograficzne. Stąd pochodzi dodatkowy kłopot z szyfrowaniem kluczem publicznym - jest ono dużo wolniejsze niż szyfrowanie z kluczem tajnym. Dlatego często łączy się obie metody, szyfrując komunikat losowym kluczem tajnym, który to klucz szyfruje się następnie kluczem publicznym odbiorcy. Odbiorca najpierw odszyfrowuje klucz tajny za pomocą swojego klucza prywatnego, a następnie odszyfrowuje wiadomość za pomocą odzyskanego klucza tajnego. Tak utworzone komunikaty nazywamy kopertami cyfrowymi (digital envelopes).

Szyfr RSA

Nazwa RSA pochodzi od twórców szyfru: Rivest, Shamir, Adleman. Jest to metoda z kluczem publicznym. Metoda ta działa następująco:

Dlaczego odszyfrowany przez Puchatka komunikat jest tym samym komunikatem, które nadał Prosiaczek? W tym celu rozumujemy następująco:

  1. FI(n)=(p-1)*(q-1) jest to liczba liczb względnie pierwszych z n=p*q i mniejszych od tej liczby.
  2. Obliczony przez Puchatka komunikat to (Ke mod n)d mod n, czyli po prostu Ke*d mod n.
  3. Korzystając z tego, że e*d=1 mod FI(n), otrzymujemy, że wynik Puchatka to (KFI(n))a*K mod n.
  4. Twierdzenie Eulera mówi, że jeżeli K jest względnie pierwsze z n, to KFI(n)=1 mod n.
  5. Jeżeli K było względnie pierwsze z n, to z twierdzenia Eulera mamy taki wynik Puchatka: K mod n, czyli po prostu K (zawsze zakładamy, że K < n), zatem jest OK.
  6. Jeżeli K nie jest względnie pierwsze z n, to albo K dzieli p, albo K dzieli q.
  7. Rozważmy przypadek K=b*p (b jest względnie pierwsze z q). Drugi przypadek jest analogiczny.
  8. Chcemy udowodnić, że (b*p)e*d=b*p mod p*q, czyli: be*d*pe*d-1=b mod q.
  9. Po skróceniu przez b dostajemy: (b*p)a*(p-1)*(q-1)=1 mod q (to pozostaje do udowodnienia).
  10. Twierdzenie Fermata mówi: jeżeli q jest pierwsze, a x jest względnie pierwsze z q, to zachodzi równość xq-1=1 mod q (wniosek z twierdzenia Eulera)
  11. W twierdzeniu Fermata używamy x=b*p (to jest względnie pierwsze z q). Otrzymujemy 1a*(p-1)=1 mod q, co jest niewątpliwie prawdą.
  12. Zatem w obu (właściwie trzech) przypadkach Puchatek dostaje od Prosiaczka poprawny komunikat.

Udowodniliśmy, że RSA jest poprawny. Ale dlaczego jest to algorytm zapewniający bezpieczeństwo? Innymi słowy, dlaczego z klucza publicznego (n, e) nie da się obliczyć klucza prywatnego (n, d)? Zakłada się, że takie obliczenie byłoby zbyt kosztowne, ale tego nie udowodniono. W rzeczywistości nie udowodniono istnienia żadnej bezpiecznej metody szyfrowania z kluczem publicznym. Zauważmy, że gdybyśmy znali rozkład n na czynniki pierwsze, to nie mielibyśmy kłopotu z odnalezieniem klucza prywatnego. Również umiejętność liczenia pierwiastków w arytmetyce modularnej pozwoliłaby złamać RSA.

Jaka jest pożądana wielkość liczby n w algorytmie RSA? Obecnie używa się zwykle liczb o 128 lub 512 bitach. Można przeczytać, że koszt złamania klucza 512-bitowego to około $1,000,000 i osiem miesięcy pracy. W związku z tym uważa się, że za jakiś czas będzie trzeba przejść do kluczy większych rozmiarów.

Liczby p i q zwykle się losuje, sprawdzając następnie, czy są pierwsze. Często nie wykonuje się dokładnego sprawdzenia, a jedynie zapewnia się, że są one pierwsze z bardzo dużym prawdopodobieństwem.

Inne szyfry z kluczem publicznym

Inaczej niż RSA wygląda metoda zaproponowana przez Diffiego i Hellmana. Służy ona do uzgodnienia wspólnego tajnego klucza. Opiera się ona na tym, że obliczenie dyskretnego logarytmu jest zapewne bardzo trudne. Wygląda to następująco:

  1. Korzysta się z dwóch publicznych wartości: n i g. Będziemy liczyć modulo n, więc g należy do Zn.
  2. Prosiaczek wybiera losową liczbą a należącą do Zn.
  3. Puchatek wybiera losową liczbą b należącą do Zn.
  4. Liczby a i b są tajne.
  5. Prosiaczek oblicza A=ga mod n i wysyła A do Puchatka.
  6. Puchatek oblicza B=gb mod n i wysyła B do Prosiaczka.
  7. Prosiaczek oblicza C=Ba mod n.
  8. Puchatek oblicza C=Ab mod n.
  9. Zarówno Puchatek, jak i Prosiaczek, otrzymują tę samą liczbę C. Ta liczba jest uzgodnionym tajnym kluczem.
  10. Osoba podsłuchująca nie jest w stanie wydobyć wartości C, o ile nie umie obliczyć dyskretnego logarytmu. Uznaje się, że ten problem jest wystarczająco trudny.

Szyfry z kluczem tajnym

Ponieważ RSA i inne szyfry z kluczem publicznym nie są wystarczająco szybkie, więc zwykle korzysta się z klucza tajnego do szyfrowania komunikatu, by następnie klucz tajny zaszyfrować kluczem publicznym. Jak dotychczas przedstawione algortymy szyfrowały liczby. Powstaje problem, jak szyfrować dużo dłuższe komunikaty. Ten problem dotyczy sytuacji, gdy mamy już dany klucz (tajny), i chcemy zaszyfrować długą wiadomość tak, żeby analiza kryptograficzna nie pozwoliła z szyfrogramu uzyskać tekst oryginalny nie posiadając klucza. Będziemy rozpatrywać przypadki, gdy klucz odbiorcy jest równy kluczowi nadawcy.

Zakładamy, że wiadomość do zaszyfrowania jest podzielona na bloki ustalonej długości (np. 64 bity). Długość tych bloków będzie zależała od rodzaju szyfru. Najprostsza metoda polega na szyfrowaniu każdego bloku z osobna (szyfr prosty). Bardziej skomplikowana metoda polega na wykonaniu szyfrowania w paru kolejkach (szyfr iterowany). Najpierw szyfrujemy tekst kluczem K1, następnie kluczem K2, it. Często klucze następne pochodzą w jakiś sposób od klucza pierwszego.

Przykładem szyfru iterowanego jest tzw. szyfr Feistela. W tym szyfrze najpierw dzielimy tekst na połowy. Następnie szyfrujemy lewą połowę za pomocą K1. Nową lewą połową będzie stara prawa połowa, natomiast nową prawą połową będzie wykonanie operacji XOR na starej prawej połowie oraz zaszyfrowanej starej lewej połowie. W następnej kolejce robimy to samo używają innego klucza K2, itd. Zaletą tego systemu jest fakt, że do odkodowania wiadomości używa się tego samego algorytmu, tylko klucze trzeba brać w odwrotnej kolejności.

Łamanie szyfrów z kluczem tajnym

Zanim opiszę bardziej szczegółowo metody szyfrowania z kluczem tajnym, przedstawię możliwe rodzaje ataków na te szyfry. Im lepszy szyfr, tym trudniej będzie wykonać na niego atak i osiągnąć sukces. Ataki mogą być m.in. następujących rodzajów:

Metody badania szyfrów i szyfrogramów mogą być różnorodne. Najprostsza polega po prostu na przejrzeniu wszystkich możliwych kluczy. Nie jest to już takie całkiem niemożliwe, o ile np. będziemy mieli specjalny rodzaj komputera do tego przeznaczony. Inna metoda działa na szyfry iterowane. Stosuje się tu tak zwaną analizę różnicową (ang. differential analysis). Polega ona na analizie różnic między podanym tekstem a szyfrogramem. Każdemu kluczowi przypisuje się prawdopodobieństwo, że jest poprawny i wybiera najprawdopodobniejszy klucz. Jedną z ciekawszych metod jest metoda algebraiczna, która wykorzystuje pewne matematyczne własności danego szyfru. Jeżeli na przykład zbiór wszystkich tekstów wraz z szyfrem jako operacją ma strukturę grupy, to atak jest ułatwiony. Wynika stąd na przykład, że wielokrotne szyfrowanie paroma kluczami daje ten sam rezultat, co szyfrowanie jakimś jednym innym kluczem.

DES

Najpopularniejszym szyfrem stosowanym obecnie jest szyfr DES (Data Encryption Standard), który jest oficjalnym standardem szyfrowania przyjętym przez rząd USA. Jest to szyfr z kluczem tajnym (klucz nadawcy=klucz odbiorcy), który łączy się często z RSA (tzn. klucz przekazuje się za pomocą RSA).

DES jest szyfrem typu Feistela. Wykonuje się w 16 kolejkach, korzystając z 56-bitowego klucza. W każdej kolejce używa się innego 48-bitowego klucza wyliczonego z głównego klucza 56-bitowego. Oryginał jest dzielony na bloki wielkości 64 bitów. Jak dotychczas jedyna udana próba złamania DES polegała na "nakarmieniu" go 243 oryginałami i analizie pochodzących stąd szyfrogramów. Kosztowało to 50 dni pracy 12 stacji roboczych HP 9735. Wykonanie takiego ataku w praktyce wydaje się niemożliwe. DES jest powszechnie uważany za bezpieczny, choć dużo mówi się o konieczności zwiększenia rozmiaru klucza (w obawie przed atakiem "na chama").

Istnieje kilka trybów działania DES:

Często stosowanym sposobem szyfrowania jest tzw. potrójny DES, który polega na trzykrotnym zastosowaniu DES z trzema różnymi kluczami. Udowodniono, że DES nie ma struktury grupowej, zatem potrójne szyfrowanie ma szanse rzeczywiście być lepsze niż szyfrowanie pojedyncze. Często stosuje się szyfrowanie całych tekstów pojedynczym DES w trybie CBC, natomiast jeżeli konieczne jest zaszyfrowanie klucza, to używa się potrójnego DES w trybie EBC.

Funkcje mieszające - wstęp

Kryptograficzną funkcją mieszającą nazywamy taką funkcję H, że:

H nazywa się "w jedną stronę", jeśli mając dane y nie da się w rozsądnym czasie znaleźć takiego x, by y=H(x). Funkcja H nazywa się "słabo bezkolizyjna", jeśli dla danego yekstu x nie da się w rozsądnym czasie znaleźć takiego tekstu y, by H(x)=H(y). Funkcja H nazywa się "silnie bezkolizyjna", jeśli w ogóle nie da się w rozsądnym czasie znaleźć takich x, y, by H(x)=H(y).

Kryptograficzne funkcje mieszające znajdują zastosowanie m.in. w tworzeniu elektronicznych podpisów oraz w generatorach liczb losowych. Również jeżeli chcemy uzyskać stempel czasowy, tzn. dać komuś tekst i uzyskać u niego potwierdzenie, że danego dnia ten tekst daliśmy, to funkcje mieszające się przydają. Jeżeli bowiem nie chcemy ujawnić tego tekstu, to stemplujemy tylko wartość otrzymaną z funkcji mieszającej. Zauważmy tu, że istota funkcji mieszającej polega na dwóch rzeczach:

Do funkcji mieszających jeszcze powrócę po omówieniu metod potwierdzania tożsamości komunikatów.

Weryfikacja tożsamości

Funkcje mieszające wraz z szyframi typu RSA pozwalają na elektronicznę kontrolę tożsamości nadawcy komunikatu. Przypuśćmy, że Puchatek chce wysłać do Prosiaczka komunikat K (niezaszyfrowany), ale nie jest pewien, czy Prosiaczek uwierzy, że to on napisał. Żeby udowodnić swoją tożsamość skorzysta z wersji RSA. Zachowujemy wszystkie oznaczenia z opisu algorytmu RSA - (n, e) to klucz publiczny, (n, d) to klucz prywatny (oba należą do Prosiaczka). Kontrola tożsamości wygląda następująco:

  1. Prosiaczek wysyła K do Puchatka
  2. Prosiaczek oblicza H(K), a następnie P=(H(K))d mod n i wysyła P jako swój podpis do Puchatka
  3. Puchatek odbiera K i P
  4. Puchatek rówmież oblicza H(K), a następnie sprawdza, czy P=(H(K))d mod n. Jeżeli ta zależność jest spełniona, to K zostanie uznany za komunikat od Prosiaczka
Jeżeli dodatkowo chce się zapewnić, że komunikat przekazywany jest tajnie, to wystarczy go najpierw zaszyfrować (np. przez RSA: zaszyfrować go kluczem publicznym Puchatka). Jak widać jest ważne, żeby funkcja H była "bezkolizyjna". Inaczej ktoś mógłby się podszyć pod Prosiaczka.

Istnieją jeszcze nieco inne metody weryfikacji tożsamości, ale wszystkie działają według podobnego schematu (użycie tu funkcji mieszającej jest związane z efektywnością - kodowanie całego komunikatu byłoby zbyt kosztowne).

Funkcje mieszające - cd

Funkcje mieszające buduje się zwykle na fundamencie tzw. funkcji kompresujących. Funkcja kompresująca pobiera dane ustalonej długości i jakoś je skraca. Funkcję mieszającą tworzy się przez iterowane obliczanie funkcji kompresujących, tzn. H(a1,...,an)=C(C(..(C(s,a1),a2)..),an), gdzie C jest funkcją kompresującą dwukrotnie, a s jest wektorem startowym. Jeżeli funkcja C ma kolizje, to nazywamy je pseudokolizjami. Istnienie pseudokolizji nie jest uważane za dowód bezużyteczności funkcji, np. funkcja MD5 (opisana dalej), ma odkryte pseudokolizje, a mimo to jest uważana za bezpieczną.

Najpopularniejsze obecnie funkcje mieszające to MD4, MD5 oraz SHA i SHA-1. Spośród nich MD4 nie jest uważana za bezpieczną, a SHA-1, która jest modyfikacją SHA (Secure Hash Algorithm), jest uważana za najbezpieczniejszą z nich (choć jest nieco wolniejsza niż MD5).


Generatory liczb losowych

Problematyka generatorów liczb losowych jest dość skomplikowana - trudno tu nawet o dokładną definicję. Często mówi się, że ciąg bitów jest losowy, jeżeli na podstawie wszystkich poza jednym nie da się przewidzieć wartości tego jednego (tzn. są one niezależne). Liczby losowe są potrzebne m.in. do generowania kluczy w kryptografii, ale przydają się też do symulacji, do randomizowanych algrytmów itp. Sławny Donald E. Knuth pisze: There are reports that many executives make their decisions by flipping a coin or by throwing darts, etc. It is also rumored that some college professors prepare their grades on such a basis. Jak widzimy, istnieje konieczność znalezienia dobrej metody obliczania liczb losowych. Ponieważ "wyliczanie liczb losowych" brzmi brzydko dla niektórych uszu, więc takie liczby nazywa się pseudolosowymi.

John von Neumann zaproponował jako pierwszy metodę uzyskiwania liczb pseudolosowych - tzw. middle-square method. Była ona bardzo prosta - brało się liczbę 10-cyfrową, liczyło jej kwadrat i następnie brało 10 jego środkowych cyfr w zapisie dziesiętnym. W ten sposób otrzymywało się kolejne liczby "losowe". Niestety okazało się, że liczby tak uzyskane nie są tak bardzo losowe, jak można by się było spodziewać. Okazuje się niestety, że liczby losowe trudno uzyskać za pomocą tworzenia przypadkowych i skomplikowanych algorytmów - bardzo często takie algorytmy szybko się degenerują i przechodzą w ciąg o krótkim okresie.

Jest oczywiste, że jeżeli stosujemy deterministyczny algorytm i mamy ograniczoną ilość pamięci, to nasz ciąg musi być okresowy. Jedną z cech dobrego generatora jest długi okres w porównaniu z zajętością pamięci. Inną cechą powinien być rozkład możliwie bliski jednostajnemu.

Bardzo popularnym generatorem liczb pseudolosowych jest tzw. generator liniowy. Kolejna liczba zależy tam tylko od poprzedniej, zgodnie ze wzorem:
Xn+1=(a*Xn+c) mod m
Wspomnę jeszcze o pewnym uogólnieniu generatora liniowego, którego wersja jest używana w systemie Linux. Zakładamy tam, że mamy liczbę pierwszą p, a pamiętamy ciąg długości k. Wzór na kolejny element jest następujący:
Xn=(a1Xn-1+...+akXn-k) mod p
Otóż można udowodnić (coś podobnego dowodził niegdyś Bogdan Chlebus na EMD), że istnieją takie współczynniki a1...ak, że jeżeli wartości X zainicjalizujemy dowolnie (ale nie wszystkie na zero), to ciąg liczb otrzymanych stąd będzie miał okres pk-1. Jest tak wtedy, gdy wielomian z tymi współczynnikami ma pewne specjalne własności (problematyka ta ma związek z ciałami o pk elementach). Na komputerach dobrze się to implementuje dla p=2 - wtedy X-y są po prostu bitami, a dodawanie wykonuje się za pomocą operacji XOR.

Generatory prawdziwie losowe

Generatory liczb losowych, a nie tylko pseudolosowych, próbuje się tworzyć korzystając z losowych zdarzeń w komputerze. Zdarzenia losowe w komputerze pochodzą z jego urządzeń zewnętrznych, w szczególności z klawiatury, myszy itp. Idea jest taka, żeby te losowe zdarzenia jakoś gromadzić, uzyskując coraz więcej losowych bitów. Jest istotne, że tylko bardzo mała część otrzymanych od urządzeń danych można uznać za losową. Np. naciśnięcie klawisza o danym kodzie jest bardzo mało losowym zdarzeniem: zwykle są to kody ASCII małych liter, a korelacja między nimi jest bardzo duża. Tworząc generator liczb losowych buduje się go tak, żeby dodanie całkowicie deterministycznych ciągów, np. 1000000 bajtów o tej samej wartości, nie zmniejszyło losowości zawartej w generatorze (choć oczywiście nie zwiększy się też ona specjalnie).

Generator liczb losowych może utrzymywać specjalny licznik, który liczyłby, ile jest jeszcze losowych bitów w generatorze. Implementacja takiego licznika jest bardzo trudna, dlatego stosuje się raczej liczenie "na oko" i trudno powiedzieć, czy z tych obliczeń otrzymuje się sensowne wyniki.

Dodatkową cechą generatora służącego do celów kryptogrficznych powinno być, że nawet znając kod generatora i odczytując z niego kolejne tworzone przez niego liczby losowe, nawet jeżeli nie dostaje on żadnych kolejnych losowych bitów, nie powinno się dać przewidzieć, jaka jest następna liczba (ta cecha odnosi się również do generatorów pseudolosowych).

Generator liczb losowych random.c

Działanie generatora liczb losowych w Linuxie jest następujące:
Generator utrzymuje 512 bajtowy "pojemnik losowości". Początkowo pojemnik jest inicjalizowany wartościami opisującymi system, czas itp. Istnieje procedura, która umieszcza w pojemniku nową wartość losową. Teoretycznie procedura ta powinna zapewniać, że "losowość" pojemnika się nie zmniejszy, nawet jeśli otrzymana liczba nie będzie zbyt losowa. Głównym źródłem losowości dla generatora jest wartość zmiennej jiffies w momencie wystąpienia jakiegoś zdarzenia (np. przerwania, ruchu myszą...). Poza tym wszystkie te sytuacje dostarczają jeszcze dodatkowych informacji, np. kod naciśniętego klawisza. Generator próbuje obliczać, ile bitów prawdziwie losowych jeszcze jest w jego pojemniku. Kody klawiszy, numery wywołanych przerwań itp. są dodawana do pojemnika, ale entropii (tak w kodzie generatora nazywa się liczba losowych bitów) nie zwiększają. Jedynie umieszczenie wartości jiffies może zmienić entropię (można jeszcze ręcznie zwiększyć entropię za pomocą ioctl). Jeżeli ktoś chce otrzymać nową liczbę losową, to generator oblicza wartość mieszającą całego pojemnika za pomocą funkcji mieszającej MD5 lub SHA. Ta wartość jest zwracana, a generator dokonuje jeszcze pewnych zmian w pojemniku, żeby następna liczba nie była taka sama jak poprzednio.

Użytkowanie generatora

Z punktu widzenia użytkownika generator są to dwa urządzenia znakowe: /dev/random i /dev/urandom. Różnią się one jedynie tym, że /dev/random blokuje proces do momentu znalezienia przynajmniej bajtu entropii i zwraca mu tylko bajty naprawdę losowe, natomiast /dev/urandom zawsze daje tyle "losowych" bajtów, ile żąda proces. Urządzenia te korzystają z jednego pojemnika i różnią się jedynie implementacją funkcji read oraz brakiem dla /dev/urandom funkcji select.

Na obu urządzeniach można wykonywać następujące operacje:

Implementacja generatora

Implementacja podprogramu obsługi to sprawa dość skomplikowana. Wydaje się, że najgorsza w niej jest funkcja dodawania słowa (32-bitowego) do pojemnika. Wygląda to następująco:

  1. Generator pamięta pewną liczbę całkowitą < 32 zwaną obrotem. Jeżeli mamy wstawić słowo w do pojemnika, to najpierw obracamy je cyklicznie o tyle bitów, ile wynosi wartość tej liczby.
  2. Generator pamięta też pozycję, pod którą poprzednio wstawialiśmy. Umieszcza na zmiennej i pozycję o 1 mniejszą (modulo 128).
  3. Jeżeli i różne od 0, to zwiększamy obrót o 7 (mod 32), jeśli i==0, to zwiększamy obrót o 14 (mod 32).
  4. Obliczamy sumę po współrzędnych (tzn. po bitach) słów pod numerami: i, i+7, i+9, i+31, i+59, i+99 (numery są modulo 128).
  5. Powyższe stałe są takie, że dają ciąg długości 2128-1 zgodnie z opisem generatorów liczb pseudolosowych.
  6. Do uzyskanej sumy dodajemy po współrzędnych nasze słowo w.
  7. Otrzymaną liczbę obracamy w lewo cyklicznie o jeden bit (po co?) i zapisujemy pod pozycję i w pojemniku
Wydaje się, że funkcja dodawania słowa do pojemnika powinna być w miarę możliwości dobrą funkcją mieszającą. Nie może to jednak być MD5 lub SHA, ze względu na zbyt wielki koszt obliczeniowy (to jest wywoływane przy każdym przerwaniu). Osobiście nie potrafiłbym wyjaśnić, dlaczego ta funkcja wygląda tak, jak wygląda - w szczególności nie jestem pewien, jaki jest związek tego rozwiązania z generatorami liniowymi (pseudolosowymi).

Dla każdego źródła losowości w systemie urządzenie utrzymuje specjalną strukturę informacyjną. Źródłami losowości są mysz, klawiatura, linie przerwań IRQ oznaczone flagą SA_SAMPLE_RANDOM, urządzenia blokowe (wysyłają coś w związku z obsługą żądania zapisu/odczytu) oraz sam generator liczb losowych, który uważa wywołanie swoich funkcji przez kogoś z zewnątrz za wydarzenie losowe. Po otrzymaniu losowego słowa z jakiegoś z tych źródeł losowości, dzieje się co następuje:

  1. słowo jest dodawane do pojemnika
  2. zapisywany jest czas tego zdarzenia i też dopisywany do pojemnika
  3. szacowany jest wzrost entropii związanej z dopisaniem czasu do pojemnika:
    1. liczona jest różnica między tym czasem, a ostatnio wpisanym czasem z tego samego źródła - oznaczamy ją przez delta
    2. liczona jest różnica między wyliczoną deltą, a deltą poprzednią - oznaczamy ją przez delta2
    3. liczona jest różnica między deltą2, a deltą2 poprzednią - oznaczamy ją przez delta3
    4. bitów losowości dodaliśmy nie więcej niż log2(min(delta, delta2, delta3))
    5. dodajemy tak wyliczoną nadwyżkę do licznika, dzieląc ją wscześniej przez 2
Algorytm powyższy stara się odrzucić te bity, które niewątpliwie nie są losowe. Delta odrzuca bity, które nie zmieniły się od poprzedniego razu (nie są losowe na pewno), delta2 zaś odrzuca rzekomą losowość tego, że różnica między kolejnymi wywołaniami jest przypadkowa (a nie jest). Delta3 odrzuca to samo w kolejnym rzędzie, ale nie wiem, jak to intuicyjnie wytłumaczyć.

Jeżeli ktoś pobiera losowy bajt z pojemnika, to nie dajemy mu bezpośrednio bajtów z pojemnika, tylko bajty przekształcone przez SHA lub MD5. Dzięki temu nie zgadnie, co my mamy w pojemniku, a poza tym wynik będzie może jeszcze bardziej losowy. Po wydaniu takiego bajtu mieszamy w pojemniku jeszcze raz za pomocą MD5 lub SHA, żeby następnym razem nie dać tej samej liczby (można więc powiedzieć, że w istocie jest to generator pseudolosowy opraty o MD5 lub SHA).

Funkcja mieszająca MD5

Na koniec chciałbym mniej więcej opisać działanie funkcji mieszającej MD5. Jej kod można znaleźć w random.c oraz w dokumencie RFC1321 (napisanym przez autora algorytmu - Ronalda Rivesta). Opiszę tę funkcję w przybliżeniu, gdyż wydaje się, że szczegóły nic a nic nie wyjaśniają.

Algorytm MD5 pobiera komunikat dowolnej długości i zwraca pewną wartość 128-bitową. Zakłada się, że MD5 jest kryptograficzną funkcją mieszającą (patrz).

Pierwszy krok algorytmu polega na dopisaniu bitów do komunikatu, by miał on długość 448 bitów modulo 512. W wypadku gdy jego długość w bitach dzieli się przez 512 z resztą 448 dodaje się jeszcze 512 bitów (tzn. zawsze się coś dodaje). Najpierw dodajemy bit 1, następnie same zera.

Następnie dodajemy długość komunikatu, zapisaną jako liczba 64-bitowa. Od tego momentu nasz komunikat ma długość w słowach (32-bitowych) podzielną przez 16.

Będziemy korzystać z czterech specjalnych funkcji (X, Y, Z - słowa 32-bitowe):

Funkcja F(X,Y,Z) oznacza "jeśli X to Y, wpp. Z". Podobnie G(X,Y,Z) oznacza "jeśli Z, to X, wpp. Y". Jeżeli bity w X, Y, Z były wszystkie nawzajem niezależne, to bity w F lub G też takie będą.

Będziemy korzystać z rejestrów A, B, C, D i tablicy T, w której pod indeksem i znajduje się część całkowita liczby 4294967296*abs(sin(i)) (???). Rejestry A, B, C, D inicjalizujemy tajemniczymi liczbami, a następnie dla każdego 16-słowowego bloku wykonujemy:

  1. AA=A, BB=B, CC=C, DD=D
  2. Wykonujemy po 4 operacje dla każdego rejestru, które zmieniają ten rejestr w zależności od: pozostałych rejestrów, wartości w oryginalnym komunikacie oraz tablicy T. Tych 16 operacji używa wszędzie funkcji F
  3. Wykonujemy po 4 operacje dla każdego rejestru, które zmieniają ten rejestr w zależności od: pozostałych rejestrów, wartości w oryginalnym komunikacie oraz tablicy T. Tych 16 operacji używa wszędzie funkcji G
  4. Wykonujemy po 4 operacje dla każdego rejestru, które zmieniają ten rejestr w zależności od: pozostałych rejestrów, wartości w oryginalnym komunikacie oraz tablicy T. Tych 16 operacji używa wszędzie funkcji H
  5. Wykonujemy po 4 operacje dla każdego rejestru, które zmieniają ten rejestr w zależności od: pozostałych rejestrów, wartości w oryginalnym komunikacie oraz tablicy T. Tych 16 operacji używa wszędzie funkcji I
  6. A+=AA, B+=BB, C+=CC, D+=DD
Wynikiem zwracanym przez algorytm po wykonaniu powyższego dla każdego bloku jest 128-bitowa liczba (A,B,C,D).

Jak widać istotnie trudno jest coś sensownego wykombinować z tego algorytmu. Wygląda na to, że jego wyniki muszą być losowe, że aż strach.


Bibliografia


Autor: Piotr Hoffman