Czym jest generator liczb losowych?

  Generator liczb losowych (ang. random number generator, RNG) — jest to system przeznaczony do generowania sekwencji liczb lub symboli których znaczenia nie można z góry przewidzieć. Określona sekwencja wygenerowanych wyników może zawierać pewną wzór, który zostanie wyśledzony po procesie generowania, ale którego nie można było przewidzieć z góry.

  Sprzętowy generator liczb losowych

  Aby wygenerować prawdziwe liczby losowe, sprzętowy generator liczb losowych (ang. hardware random number generator, HRNG) jest używany lub jest również nazywany prawdziwym generatorem liczb losowych (ang. true random number generator, TRNG) — to urządzenie, które generuje liczby losowe z fizycznego procesu, który stale się zmienia w sposób, który jest praktycznie niemożliwe do wymodelowania. Takie generatory mogą opierać się na wykorzystaniu makroskopowych procesów losowych, czyli w skali umożliwiającej pomiary i obserwacje gołym okiem, np. rzucanie monetą, kostką lub koła ruletki. Chociaż proces makroskopowy można w pełni określić zgodnie z mechaniką Newtona, dobrze zaprojektowany mechanizm, taki jak koło ruletki, da nieprzewidywalny wynik, który można wytłumaczyć przez teorię chaosu i niestabilność układów dynamicznych ze względu na różnicę w warunkach początkowych każdego z nich nowa próba zakręcenia kołem ruletki. Główna wada generatorów wykorzystujących procesy makroskopowe zawsze była niska prędkość, a co za tym idzie, brak możliwości wygenerowania dużej liczby wartości w krótkim czasie.
  Obecnie sprzętowe generatory liczb losowych zwykle wykorzystują urządzenia oparte na zjawiskach mikroskopowych generujące niskopoziomowe, statystycznie losowe sygnały „szumu”, takie jak różnego rodzaju odgłosy (strzałowe, termiczne, atmosferyczne), efekt fotoelektryczny, obejmujący rozdzielacz wiązki i inne zjawiska kwantowe. Takie procesy są dobrym źródłem entropii, ponieważ ich wynik jest absolutnie niemożliwy do przewidzenia w teorii, ale ze względu na złożoność wdrożenie i względna powolność pracy, zakres wykorzystania takich generatorów jest ograniczony do obszarów tematycznych z pewnymi wymaganiami dla generowanych wartości.
  Zasadniczo elektroniczne generatory liczb losowych są używane w kryptografii do generowania losowych kryptograficznie klucze zapewniające bezpieczny transfer danych, na przykład w internetowych protokołach szyfrowania, takich jak protokół TLS (ang. Transport Layer Security).

Generator liczb pseudolosowych

  Alternatywą dla generatorów sprzętowych (fizycznych) są generatory oparte na algorytmach — generatory liczb pseudolosowych (ang. pseudorandom number generator, PRNG), które tworzą ciąg liczb, który wygląda jak losowy, ale w rzeczywistości tak nie jest. Liczby generowane przez PRNG nie mogą być uważane za naprawdę losowe, ponieważ są całkowicie określone przez wartość początkową, zwaną ziarnem PRNG. Mimo że sekwencja liczb generowanych przez sprzętowe generatory liczb losowych jest bliższa prawdziwie losowej, pseudolosowej generatory liczb są często stosowane w praktyce w wielu dziedzinach ze względu na ich szybkość w generowaniu liczb, łatwość wdrożenie i względną taniość. Istnieje wiele metod tworzenia pseudolosowych ciągów liczb, wśród nich Mersenne Twister, liniowy generator kongruencjalny (ang.linear congruential generator, LCG), generatory liczb losowych Xorshift, a także zwane generatorami rejestru przesuwnego, Well Equidistributed Long-period Linear (WELL), który jest formą Rejestr przesuwny z liniowym sprzężeniem zwrotnym zoptymalizowany pod kątem implementacji oprogramowania i innych metod opartych na algorytmach.

Mersenne Twister

  Mersenne Twister to jeden z najpopularniejszych generatorów liczb pseudolosowych opracowany w 1997 roku przez Makoto Matsumoto (松本 眞) i Takuji Nishimura (西村 拓士). Jego nazwa pochodzi od tego, że jego długość okresu jest wybierana jako liczba pierwsza Mersenne'a, jest to liczba pierwsza postaci dla pewnej liczby całkowitej n. Ten PRNG został zaprojektowany specjalnie w celu rozwiązania większości niedociągnięć stwierdzonych w poprzednich PRNG. Główne zalety Twistera Mersenne:

• Bardzo długi okres 2¹⁹⁹³⁷ — 1
• Przechodzi wiele statystycznych testów losowości, w tym testy Dieharda i większość, ale nie wszystkie testy TestU01
• Ma liberalną licencję na wolne oprogramowanie i wolne od patentów dla wszystkich wariantów z wyjątkiem CryptMT
• k-rozprowadzane do 32-bitowej dokładności dla każdego 1 ≤ k ≤ 623
• Implementacje generalnie generują liczby losowe szybciej niż prawdziwe (sprzętowe) metody generowania

  Mersenne Twister jest używany jako domyślny PRNG w wielu językach programowania, oprogramowaniu i zasobach internetowych, na przykład nasz generator liczb losowych online, ale ta metoda nie jest silna kryptograficznie, co nie pozwala na jej zastosowanie w kryptografii.

PRNG ze źródłem entropii

  Wraz z koniecznością szybkiego generowania łatwych do odtworzenia ciągów liczb losowych istnieje również potrzeba generować zupełnie nieprzewidywalne lub po prostu całkowicie losowe liczby. Aby spełnić oba warunki, najczęściej stosuje się kombinacje PRNG odpornego na krypto i zewnętrznego źródła entropii i to właśnie one kombinacje generatorów, które są obecnie powszechnie nazywane generatorami liczb losowych (RNG). Takie generatory są najbardziej często używane do generowania unikalnych kluczy symetrycznych i asymetrycznych do szyfrowania, przemysłu gier i innych obszarów. Przykład działania generatora kombinowanego jest następujący: urządzenie fizyczne, korzystające z niezawodnego źródła entropii (takiej jak szum termiczny), generuje „ziarno” dla szybszego kryptograficznie bezpiecznego generator liczb pseudolosowych, który następnie generuje pseudolosową sekwencję wyjściową ze znacznie większą szybkością transmisji danych.