Kryptografia a generator liczb losowych w systemie Linux


Do spisu treści tematu 5
5.3.2 Kryptografia a generator liczb losowych w systemie Linux
Spis treści:

Kryptografia

Klucz - publiczny lub tajny
Idea szyfrowania z kluczem publicznym
Szyfr RSA
Inne szyfry z kluczem publicznym
Szyfry z kluczem tajnym
Łamanie szyfrów z kluczem tajnym
DES
Funkcje mieszające - wstęp
Weryfikacja tożsamości
Funkcje mieszające - cd

Generatory liczb losowych

Generatory prawdziwie losowe
Generator liczb losowych random.c
Użytkowanie generatora
Implementacja generatora
Funkcja mieszająca MD5

Bibliografia





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:

szyfrowania komunikatów
uwierzytelniania komunikató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:

Jeśli Puchatek chce otrzymywać tajne komunikaty, to:

Wybiera sobie dwie liczby pierwsze p i q.
Puchatek oblicza n=p*q.
Puchatek wybiera liczbę e < n i względnie pierwszą z
(p-1)*(q-1).
Puchatek znajduje taką liczbę d, że (p-1)*(q-1)
dzieli e*d-1.
Prywatnym kluczem Puchatka jest KLo=(n, d).
Publicznym kluczem Puchatka jest KLn=(n, e).
Liczby p i q można zniszczyć.

Jeśli Prosiaczek chce wysłać do Puchatka tajny komunikat, to:

Przedstawia ten komunikat w postaci liczby K.
Sprawdza, jaki jest publiczny klucz Puchatka KLn=(n,e).
Oblicza SZ=Ke mod n.
Wysyła Puchatkowi komunikat (liczbę) SZ.

Jeśli Puchatek otrzymał od Prosiaczka zaszyfrowany komunikat (liczbę) SZ, to:

Bierze swój klucz prywatny KLo=(n, d).
Oblicza K=(SZ)d mod n.
Czyta K, wiedząc, że Kłapouchy na pewno nie ma do tego
dostępu.




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

FI(n)=(p-1)*(q-1) jest to liczba liczb względnie pierwszych z
n=p*q i mniejszych od tej liczby.
Obliczony przez Puchatka komunikat to
(Ke mod n)d mod n, czyli po prostu
Ke*d mod n.
Korzystając z tego, że e*d=1 mod FI(n), otrzymujemy, że wynik
Puchatka to (KFI(n))a*K mod n.
Twierdzenie Eulera mówi, że jeżeli K jest względnie pierwsze
z n, to KFI(n)=1 mod n.
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.
Jeżeli K nie jest względnie pierwsze z n, to
albo K dzieli p, albo K dzieli q.
Rozważmy przypadek K=b*p (b jest względnie pierwsze
z q). Drugi przypadek jest analogiczny.
Chcemy udowodnić, że (b*p)e*d=b*p mod p*q, czyli:
be*d*pe*d-1=b mod q.
Po skróceniu przez b dostajemy:
(b*p)a*(p-1)*(q-1)=1 mod q (to pozostaje do udowodnienia).
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)
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ą.
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:

Korzysta się z dwóch publicznych wartości: n i g.
Będziemy liczyć modulo n, więc g należy do Zn.
Prosiaczek wybiera losową liczbą a należącą do Zn.
Puchatek wybiera losową liczbą b należącą do Zn.
Liczby a i b są tajne.
Prosiaczek oblicza A=ga mod n i wysyła A do Puchatka.
Puchatek oblicza B=gb mod n i wysyła B do Prosiaczka.
Prosiaczek oblicza C=Ba mod n.
Puchatek oblicza C=Ab mod n.
Zarówno Puchatek, jak i Prosiaczek, otrzymują tę samą liczbę C.
Ta liczba jest uzgodnionym tajnym kluczem.
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:

Napastnik wybiera sobie tekst i czyta jego zaszyfrowaną wersję. Jest
to najtrudniejszy od odparcia rodzaj ataku. Dość trudno go jednak
wykonać w praktyce (trzeba zmusić szyfrującego do zaszyfrowania naszego
tekstu).
Napastnik zna tekst i jego zaszyfrowaną wersję, ale nie może sobie
sam tekstu wybrać. Oznacza to, że ma on do dyspozycji jakąś próbkę
tekstów i szyfrogramów, której nie może sobie wybrać.
Napastnik zna tylko szyfrogram. Odgadnięcie oryginału z szyfrogramu
wymaga w sposób konieczny jakiejś wiedzy o typie oryginału - w jakim
jest języku itp. Takie ataki są bardzo trudne do wykonania.

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:

EBC (Electronic Codebook) - każdy 64-bitowy blok koduje się osobno,
CBC (Cipher Block Chaining) - przed zakodowaniem kolejnego
64-bitowego bloku wykonuje się XOR tego bloku z wynikiem kodowania
poprzedniego,
CFB (Cipher Feedback) - używany do kodowania tekstów z
inną wielkością bloku niż 64 bity.
OFB (Output Feedback) - kolejna modyfikacja - błędy w czasie
transmisji nie uniemożliwiają odczytania tekstu.

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:

Dziedziną H jest zbiór wszystkich możliwych tekstów
(dowolnej długości)
H(x) jest zawsze tej samej długości
H(x) jest proste do wyliczenia na komputerze
H jest funkcją "w jedną stronę"
H jest funkcją "bezkolizyjną"

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:

z wartości funkcji na tekście nie da się w żadnym wypadku odzyskać
informacji o tekście
nie da się znaleźć tekstu, który dawałby zamówioną z góry wartość
mieszającą

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:

Prosiaczek wysyła K do Puchatka
Prosiaczek oblicza H(K), a następnie P=(H(K))d mod n i
wysyła P jako swój podpis do Puchatka
Puchatek odbiera K i P
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:

read - czyta bajty losowe.
write - dopisuje bajty jako losowe do pojemnika. Podkreślam, że teoretycznie
pisanie do pojemnika nie może zmniejszyć jego entropii (czy tak jest naprawdę - nie wiem).
select - dla urządzenia blokującego - zwraca czy są już wolne bajty
(przy czekaniu na operację wejścia) lub czy też nie ma wolnych bajtów (przy czekaniu na operację wyjścia).
ioctl - wiele możliwości:

RNDGETENTCNT - zwraca wartość licznika entropii
RNDADDTOENTCNT - dodaje argument do licznika entropii (tylko nadzorca)
RNDGETPOOL - zwraca zawartość pojemnika (tylko nadzorca)
RNDADDENTROPY - atomowo dopisuje bajty do pojemnika i zwiększa licznik entropii.
Musi to być zrobione atomowo, bo inaczej może się zdarzyć, że najpierw dopiszemy
losowe bajty, potem ktoś je zabierze, a potem zwiększymy entropię (choć ona powinna być zero).
Jeżeli z kolei najpierw zwiększymy licznik, to ktoś zabierze bajty, które nie są losowe zanim my zdołamy
dopisać losowe bajty (tylko nadzorca)
ZAPENTCNT - zeruje licznik entropii (tylko nadzorca)
RNDCLEARPOOL - zeruje pojemnik (tylko nadzorca)



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:

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.
Generator pamięta też pozycję, pod którą poprzednio wstawialiśmy. Umieszcza
na zmiennej i pozycję o 1 mniejszą (modulo 128).
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).
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).
Powyższe stałe są takie, że dają ciąg długości 2128-1
zgodnie z opisem generatorów liczb pseudolosowych.
Do uzyskanej sumy dodajemy po współrzędnych nasze słowo w.
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:

słowo jest dodawane do pojemnika
zapisywany jest czas tego zdarzenia i też dopisywany do pojemnika
szacowany jest wzrost entropii związanej z dopisaniem czasu do pojemnika:

liczona jest różnica między tym czasem, a ostatnio wpisanym czasem z tego
samego źródła - oznaczamy ją przez delta
liczona jest różnica między wyliczoną deltą, a deltą poprzednią - oznaczamy
ją przez delta2
liczona jest różnica między deltą2, a deltą2 poprzednią - oznaczamy ją przez
delta3
bitów losowości dodaliśmy nie więcej niż log2(min(delta, delta2, delta3))
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):

F(X,Y,Z)= (X&Y) | ((~X)&Z)
G(X,Y,Z) = (X&Z) | (Y&(~Z))
H(X,Y,Z) = x^y^z
I(X,Y,Z) = Y ^ (X | (~Z))

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:

AA=A, BB=B, CC=C, DD=D
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
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
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
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
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

RFC1321, RFC1320, RFC2104, RFC1186
FAQ about Today's Cryptography (RSA)
random.c
Donald E. Knuth, The Art of Computer Programming, vol.2, Seminumerical
Algorithms


Autor: Piotr Hoffman