Skąd komputer bierze losowość?

Maszyna, która nie umie zgadywać

Komputer jest z natury przewidywalny: ten sam program z tymi samymi danymi zawsze da ten sam wynik. Żeby cokolwiek wylosować, potrzebuje czegoś spoza siebie – zjawisk fizycznych, których nie da się przewidzieć. Tę nieprzewidywalność nazywamy entropią i mierzymy w bitach: uczciwy rzut monetą to 1 bit, a 256-bitowy klucz to 2²⁵⁶ równie prawdopodobnych możliwości.

Źródłem entropii są m.in. dokładne czasy przerwań sprzętowych, szum urządzeń, sprzętowe generatory losowości wbudowane w procesory i ruchy użytkownika. System operacyjny zbiera je w puli, miesza funkcjami kryptograficznymi i zasila nimi generator, z którego korzystają programy – także przeglądarka.

Entropia z Twoich ruchów

Ruch ręki jest trudny do powtórzenia co do piksela i milisekundy. Generator haseł korzysta z tego: z każdego ruchu bierze dwa najniższe bity zmiany położenia w poziomie, w pionie i w czasie. Te najniższe bity zależą od drobnych drgnięć, nad którymi nikt nie panuje. Sześć bitów na ruch to szacunek, a nie pomiar – dlatego generator nie polega na nich sam, tylko łączy je z generatorem przeglądarki i rundą drand.

Surowe bity bywają nierówne: ruch po prostej daje inne wzory niż kółka. Dlatego pula przechodzi przez funkcję skrótu SHA-256, która wygładza ją w ciąg nieodróżnialny od losowego (więcej w artykule o funkcji skrótu i efekcie lawiny). Spróbuj sam:

Generatory pseudolosowe: wzór udający przypadek

Entropii jest mało i zbiera się powoli, a programy potrzebują milionów losowych liczb. Dlatego używa się generatorów pseudolosowych (PRNG): algorytmów, które z krótkiego ziarna wyliczają długi ciąg liczb wyglądających na losowe. Ten sam start daje zawsze ten sam ciąg – to zaleta w symulacjach i grach, ale też słabość.

Najstarszy i najprostszy jest generator liniowy kongruencyjny (LCG): następna liczba to (a · x + c) mod m. Jego wady widać gołym okiem:

• Najniższe bity powtarzają się. Przy module będącym potęgą dwójki najniższy bit na zmianę wynosi 0 i 1, dwa najniższe powtarzają się co 4 liczby i tak dalej. Przykładowa funkcja rand() z normy języka C zwraca więc tylko wyższe bity stanu, a dolne 16 odrzuca.
• Kolejne liczby leżą na prostych. Pary kolejnych wyników układają się na kilku równoległych liniach, a w większej liczbie wymiarów – na płaszczyznach. George Marsaglia opisał to w 1968 roku w pracy o wymownym tytule „Random numbers fall mainly in the planes”.

Współczesne generatory, takie jak te stojące za Math.random() w przeglądarkach, są dużo lepsze statystycznie i na takich obrazkach nie pokazałyby wzoru. Nadal jednak nie są kryptograficzne: z kilku kolejnych wyników da się odtworzyć ich stan i przewidzieć następne. W grze to bez znaczenia, przy haśle albo losowaniu nagród – dyskwalifikuje.

CSPRNG: generator, którego nie da się przewidzieć

Kryptograficznie bezpieczny generator pseudolosowy (CSPRNG) też rozciąga ziarno, ale z gwarancją, której zwykłe PRNG nie dają: nawet ktoś, kto zna dowolnie wiele wcześniejszych wyników, nie potrafi przewidzieć następnego lepiej niż zgadując. Do tego jest regularnie dosiewany świeżą entropią z systemu.

W przeglądarce taki generator udostępnia crypto.getRandomValues. Korzystają z niego wszystkie narzędzia losowaliczba.pl – od generatora liczb po generator haseł – a tryb weryfikowalny dokłada do tego publiczną losowość, którą każdy może sprawdzić.