Czym jest generator liczb losowych?
Generator liczb losowych (RNG) to system, który wytwarza liczby losowe lub pseudolosowe. To, czy następną liczbę da się rzeczywiście przewidzieć, zależy od rodzaju generatora. Jedne generatory korzystają z procesu fizycznego, inne obliczają liczby za pomocą algorytmu, a niektóre algorytmy są zbudowane tak, że nawet ktoś, kto widział ich wcześniejsze wyniki, nie potrafi przewidzieć, co będzie dalej. Wyglądać losowo i być nieprzewidywalnym to dwie różne właściwości i właśnie o tej różnicy jest większość tego artykułu.
Sprzętowe generatory liczb losowych
Sprzętowy generator liczb losowych (HRNG), nazywany też generatorem liczb prawdziwie losowych (TRNG), generuje liczby na podstawie pomiarów procesu fizycznego. Najstarsze takie generatory można zobaczyć gołym okiem: rzucona moneta, kość do gry, koło ruletki. Mechanika opisuje każde z nich w pełni, a mimo to dobrze wykonane koło jest w praktyce nieprzewidywalne, bo drobne różnice na początku każdego obrotu prowadzą do zupełnie różnych wyników.
Współczesne generatory sprzętowe mierzą zjawiska mikroskopowe: szum śrutowy i szum termiczny w układach elektronicznych, szum atmosferyczny, efekty kwantowe. To dobre źródła entropii – nieprzewidywalności, którą da się zmierzyć – ale źródło fizyczne nie jest doskonałe z natury: może faworyzować niektóre wyniki, zmieniać się z czasem i ulegać awariom. Dlatego jego jakość trzeba oceniać i monitorować, a wyniki w razie potrzeby dodatkowo przetwarzać – właśnie to opisują normy takie jak NIST SP 800-90B. Źródeł sprzętowych używa się tam, gdzie jakość źródła losowości ma szczególne znaczenie – przede wszystkim w kryptografii, gdzie dostarczają nieprzewidywalnego materiału wyjściowego dla kluczy, na których opierają się protokoły takie jak Transport Layer Security (TLS).
Generatory liczb pseudolosowych
Alternatywą dla urządzenia fizycznego jest algorytm. Generator liczb pseudolosowych (PRNG) wytwarza ciąg, który wygląda na losowy, ale jest w pełni wyznaczony przez wartość początkową nazywaną ziarnem (seed). Podaj temu samemu algorytmowi to samo ziarno, a za każdym razem dostaniesz ten sam ciąg. To słabość wszędzie tam, gdzie wynik musi być nieprzewidywalny, a ziarno lub stan wewnętrzny da się odgadnąć albo odtworzyć, i zaleta wszędzie tam, gdzie wynik musi być powtarzalny – symulację lub test można dokładnie powtórzyć. PRNG są też szybkie, tanie i łatwe do zaimplementowania, dlatego opiera się na nich większość oprogramowania. Do znanych algorytmów należą liniowy generator kongruentny (LCG), generatory xorshift i Mersenne Twister.
Mersenne Twister
Mersenne Twister, opublikowany w 1997 roku przez Makoto Matsumoto i Takujiego Nishimurę, to jeden z najczęściej używanych generatorów liczb pseudolosowych i domyślny generator w wielu językach programowania. Jego nazwa pochodzi od okresu – długości ciągu, po której zaczyna się on powtarzać – który w wariancie standardowym, MT19937, jest liczbą pierwszą Mersenne'a 219937 − 1. Przechodzi większość statystycznych testów losowości i dobrze nadaje się do symulacji. Nie zaprojektowano go jednak do strzeżenia tajemnic: na podstawie 624 kolejnych 32-bitowych wartości każdy może odtworzyć jego stan wewnętrzny i przewidzieć wszystkie następne wartości, dlatego nie wolno go używać do kluczy, haseł ani niczego innego, co musi pozostać nieprzewidywalne.
Kryptograficznie bezpieczne generatory i entropia
W wielu zastosowaniach potrzebne są zarówno szybkość algorytmu, jak i nieprzewidywalność źródła fizycznego. Odpowiedzią jest kryptograficznie bezpieczny generator liczb pseudolosowych (CSPRNG). To nadal PRNG, ale zbudowany tak, że znajomość części jego wyników nie daje praktycznej możliwości przewidzenia reszty; ziarno pobiera i regularnie odnawia ze źródła prawdziwej entropii. Ziarno ze źródła fizycznego nie czyni zwykłego PRNG bezpiecznym; algorytm musi być do tego zaprojektowany. Źródło fizyczne, na przykład szum termiczny albo czasy zdarzeń sprzętowych, dostarcza niewielką ilość prawdziwej losowości, a CSPRNG zamienia ją w długi ciąg wartości i dostarcza je znacznie szybciej. Właśnie takie połączenie system operacyjny udostępnia działającym w nim programom i to je zwykle ma się dziś w praktyce na myśli, mówiąc „generator liczb losowych”. Taki generator wytwarza klucze szyfrujące, tokeny sesji i hasła.
Liczby losowe w przeglądarce
JavaScript daje stronie internetowej dwa wbudowane sposoby uzyskania wartości losowych i należą one do różnych klas. Math.random() to zwykły PRNG: standard języka JavaScript pozostawia wybór algorytmu każdej przeglądarce i nie gwarantuje bezpieczeństwa kryptograficznego – wystarczy do animacji, nie nadaje się do losowania, które ktoś mógłby zakwestionować. Drugi sposób to Web Crypto API. Jego metoda crypto.getRandomValues() zwraca kryptograficznie silne wartości losowe, wytwarzane przez CSPRNG, którego ziarno pochodzi z entropii systemu operacyjnego.
Nasz generator liczb losowych online używa Web Crypto API przy każdym losowaniu, a liczby powstają w Twojej przeglądarce, nie na serwerze. Z tego samego źródła losowości korzystają pozostałe generatory na tej stronie, niezależnie od tego, czy rzucasz kośćmi, rzucasz monetą, czy generujesz hasło.
Od losowych bitów do liczby z wybranego zakresu
Kryptograficznie bezpieczny generator to dopiero połowa uczciwego losowania. Dostarcza on surowe bity, a program musi jeszcze zamienić je na liczbę z Twojego zakresu – i na tym etapie niektóre liczby mogą dostać większą szansę niż inne. Załóżmy, że źródło daje wartości od 0 do 9 z równymi szansami, a potrzebujesz liczby od 0 do 5. Wzięcie reszty z dzielenia przez 6 wydaje się naturalne, ale wtedy 0, 1, 2 i 3 mogą wypaść każda na dwa sposoby, a 4 i 5 tylko na jeden, więc każda z liczb od 0 do 3 ma prawdopodobieństwo 20%, a 4 i 5 – tylko po 10%. Jednym ze sposobów zapewnienia równych szans jest odrzucanie wartości, które nie pasują, i losowanie od nowa; szczegółowo opisują to materiały o generatorze liczb losowych.
W wygenerowanych wartościach ludzi często zaskakują jeszcze dwie rzeczy. Powtórzenia są normalne: gdy liczbę całkowitą od 1 do 10 losuje się niezależnie i każda liczba jest jednakowo prawdopodobna, dopiero co wylosowana liczba ma taką samą szansę 1 na 10 wypaść ponownie jak każda inna. Losowanie bez powtórzeń to inny rodzaj losowania, a nie bardziej losowy. A sam uczciwy generator nie czyni uczciwą całej procedury: lista uczestników i liczba prób są równie ważne – więcej wyjaśniamy w artykule o tym, jak wybrać losowego zwycięzcę konkursu.