9346692690

Jednakże należy również nie zapominać, że są one pomocne w szeregu pośrednich działań związanych z tą nauką (chociażby znajdowanie i testowanie liczb pseudopierwszych).

1.3 Generatory liczby losowych vs. pseudlosowych

Do tworzenia liczb losowych służą generatory, które możemy podzielić z grubsza na losowe i pseudolosowe. Przy czym generatory liczb losowych możemy dodatkowo podzielić na sprzętowe i programowe. Te pierwsze wykorzystują procesy fizyczne do generacji losowych bitów, jednakże mogą one tworzyć ciągi zależne od poprzednich wyników lub o rozkładzie prawdopodobieństwa innym od normalnego i jest dość trudno takowe stworzyć. Na szczęście istnieją techniki „naprawiające” te błędy¹ tzw. de-skewing technics. Przykłady takich generatorów można znaleźć poniżej:

—    szumy termiczne rezystorów lub diod,

—    wejście audio lub video w komputerze,

—    turbulencje powietrza wewnątrz dysku twardego powodujące losowe opóźnienia w odczycie danych,

Programowe generatory z kolei wykorzystują informacje w komputerze, które są podejrzewane o losowość np.: zegar systemowy, odstępy czasu między uderzeniami w klawisze klawiatury, ruchy myszki, obciążenie systemu czy sieci — im algorytm więcej wykorzystuje danych tym bardziej losowe liczby generuje. Do miksowania danych wejściowych używane są funkcje hashujące takie jak MD5 — „poprawiające” losowość.

Czemu w ogóle stosujemy w takim bądź razie generatory pseudolosowe? Odpowiedź jest prosta — szybkość generacji liczb. Generatory liczb losowych są zbyt wolne dla procedur kryptograficznych w których zależy nam na szybkim kodowaniu dużych ilości informacji. Poniżej zamieszczamy za [1] czym jest generator bitów^{2 3} pseudolosowych:

Definition 1. Generatorem bitów pseudolosowych nazywamy deterministyczni algorytm dzięki któremu, podając prawdziwie losowy ciąg bitów o długości k, uzyskujemy sekwencję binarną o długości l k o własnościach „wydających się” losowymi, k-elementową sekwencję nazywamy ziarnem (ang. seed), natomiast wynik działania generatora — pseudolosowym ciągiem bitów.

Czy dany algorytm możemy uważać za generator liczb pseudolosowych decydują testy statystyczne (przedstawione dalej). Należy jednak pamiętać, że jeśli procedura przejdzie poprawnie wszystkie testy to wcale nie oznacza prawdziwie losowej natury jej wyników i na odwrót — jeśli generator nie przejdzie jednego z testów to nie oznacza, że w jakimś zadanym problemie numerycznym nie

1

   często używane do tego celu są funkcje hashujące typu MD5 lub SHA-1 choć ich użyteczność w tym celu nie została matematycznie potwierdzona.

2

   Generator losowych bitów może służyć do generowania liczb pseudolosowych.

3

   Tzn. to samo ziarno inicjujące procedurę daje zawsze to samo na wyjściu.