Generator Liczb

Generator liczb losowych (RNG – Random Number Generator) to zaawansowane narzędzie lub algorytm służący do generowania całkowicie przypadkowych wartości za każdym razem, gdy zajdzie taka potrzeba. Jego kluczową cechą jest brak możliwości przewidzenia wzorca na podstawie wcześniej wygenerowanych liczb. Taka wartość może być losowana zarówno przez odpowiedni algorytm programistyczny, jak i dedykowane urządzenie sprzętowe.

Zastosowanie Generatorów Liczb Losowych

Generowanie losowych liczb jest niezbędne do realizacji wielu różnorodnych zadań – od mechaniki w grach komputerowych po zaawansowane aplikacje codziennego użytku. Przykładowo, systemy internetowe wykorzystują generator liczb losowych do wyświetlania rotacyjnych banerów lub przypadkowych jednostek reklamowych na stronach WWW. Z kolei w kryptografii liczby losowe stanowią fundament tworzenia unikalnych szyfrów oraz bezpiecznych kluczy dostępu.

Technologia generowania liczb losowych jest szeroko wykorzystywana do: tworzenia kodów CAPTCHA, zaawansowanego szyfrowania danych, generowania tzw. "soli" (ang. salt) do bezpiecznego przechowywania haseł, w generatorach silnych haseł, do tasowania kart w kasynach online, a także w procesach decyzyjnych, próbkowaniu statystycznym oraz symulacjach naukowych.

Algorytm generatora liczb losowych jest również sercem większości gier wideo. Nawet jeśli powtarzasz ten sam poziom w grze, rozgrywka nigdy nie będzie w stu procentach identyczna. Różnice mogą nie być zauważalne w samej konstrukcji misji czy układzie mapy, ale wpłyną na liczbę nacierających wrogów, miejsca ich odrodzenia (tzw. spawny), zmienne warunki pogodowe czy ułożenie przeszkód. To właśnie ta nieprzewidywalność sprawia, że gry są tak ekscytujące i oferują wysoką regrywalność.

Różnica między Sekwencją Losową a Nielosową

Weźmy pod uwagę następującą sekwencję liczb: 1, 2, 3, 4, 5. Czy jest ona losowa?

Zmienna losowa to w matematyce taka zmienna, która w wyniku próby (doświadczenia) przyjmuje jedną z możliwych wartości, przy czym przed jej wystąpieniem nie da się ze stuprocentową pewnością przewidzieć, jaka to będzie wartość.

Załóżmy, że powyższy ciąg liczb powstał poprzez wpisywanie po kolei klawiszy z górnego rzędu klawiatury. W takim przypadku jasne staje się, że ta kombinacja nie jest losowa. Po cyfrze 5, kolejną liczbę (czyli 6) można przewidzieć z niezwykle dużym prawdopodobieństwem.

Sekwencja będzie uznana za losową tylko i wyłącznie wtedy, gdy nie istnieje absolutnie żadna zależność między jej poszczególnymi symbolami.

Podstawowym warunkiem, który jest wręcz krytyczny dla poprawnego i uczciwego działania generatora liczb losowych, są absolutnie równe szanse na wylosowanie każdej możliwej liczby w danym systemie. Oznacza to całkowitą niezależność czynnika losowości – to, jaka liczba wypadnie, nie zależy w żaden sposób od tego, jakie liczby zostały wylosowane wcześniej ani od tego, jakie wypadną później.

Aby to zobrazować: wyobraź sobie pierwszy rzut standardową, sześciościenną kostką. Masz dokładnie takie same szanse na uzyskanie dowolnej liczby od 1 do 6. Niezależnie od wyniku, przy kolejnym rzucie – czy będzie to drugi, setny, czy tysięczny rzut – prawdopodobieństwo wylosowania tej samej wartości pozostaje niezmiennie równe.

Rozwinięcie dziesiętne liczby Pi wydaje się unikalne i dla wielu osób może uchodzić za ciąg całkowicie losowy. Załóżmy, że nasz hipotetyczny generator opiera się na reprezentacji bitowej liczby Pi, zaczynając od pewnego utajnionego punktu. Taki generator rzeczywiście mógłby być nieprzewidywalny w wielu powszechnych zastosowaniach i potencjalnie pomyślnie przeszedłby niektóre testy na losowość. Jednak opieranie się na liczbie Pi w celach kryptograficznych to ogromne ryzyko. Jeśli haker odgadnie konkretny segment liczby Pi, który posłużył jako baza, bez problemu przewidzi zarówno poprzednie, jak i kolejne segmenty, całkowicie kompromitując bezpieczeństwo systemu.

Amerykański Narodowy Instytut Standaryzacji i Technologii (NIST) opracował "Pakiet Testów Statystycznych dla Generatorów Liczb Losowych i Pseudolosowych dla Zastosowań Kryptograficznych". Zestaw ten zawiera 15 rygorystycznych testów, których celem jest weryfikacja poziomu losowości ciągów bitów generowanych przez rozwiązania sprzętowe lub programowe.

Rodzaje Generatorów Liczb Losowych

W świecie technologii wyróżniamy dwa główne rodzaje generatorów: sprzętowe generatory liczb prawdziwie losowych (TRNG – True Random Number Generator) oraz generatory liczb pseudolosowych (PRNG – Pseudorandom Number Generator). TRNG wykorzystują do losowania zjawiska fizyczne, podczas gdy PRNG opierają się na zaawansowanych algorytmach matematycznych.

Prawdziwy generator liczb losowych to zazwyczaj fizyczne urządzenie sprzętowe, które wykorzystuje mikroskopijne zjawiska fizyczne do generowania liczb, a dokładniej – entropię. W tym kontekście entropia oznacza czysty, niefiltrowany chaos.

Prawdziwe generatory liczb losowych bazują na takich zjawiskach jak:

• radioaktywność,
• szum termiczny,
• szum elektromagnetyczny,
• procesy fizyki kwantowej i inne.

Systemy klasy TRNG są globalnie wykorzystywane w środowiskach, gdzie najwyższe bezpieczeństwo jest priorytetem, a także w zaawansowanych metodach szyfrowania danych.

Takie generatory czerpią z różnych źródeł entropii, aby ją skumulować i wygenerować tzw. ziarno (wartość początkową), które jest niezbędne do prawidłowego zainicjowania procesu losowania.

Algorytmy pseudolosowe (PRNG) znajdują zastosowanie tam, gdzie rygorystyczne bezpieczeństwo kryptograficzne nie jest wymagane. Ich celem jest zapobieganie powtarzalności i sprawienie, by proces był atrakcyjny oraz nieprzewidywalny dla przeciętnego użytkownika. Wdrożenie technologii PRNG jest znacznie tańsze i szybsze, ponieważ nie wymaga specjalistycznego sprzętu i może być łatwo zaimplementowane bezpośrednio w kodzie programu. Choć generowane sekwencje nie są prawdziwie losowe (są zdeterminowane przez matematyczny algorytm), sprawdzają się idealnie w grach wideo czy oprogramowaniu użytkowym.

Generatory PRNG do działania potrzebują tylko jednej wartości początkowej (ziarna), od której zależy cały późniejszy pseudolosowy ciąg. Z kolei TRNG przy każdym żądaniu generuje autentycznie losową liczbę, stale korzystając z wysokiej jakości zmiennych dostarczanych przez źródła entropii.

Generowanie pseudolosowe ma jednak swoje luki. Działa świetnie, ponieważ dla niewprawnego oka wygląda na czystą losowość. Jeśli jednak ktokolwiek poznałby wartość ziarna dla konkretnego ciągu PRNG, byłby w stanie dokładnie przewidzieć wszystkie kolejne liczby.

Błąd ten często wykorzystują entuzjaści speedrunningu (szybkiego przechodzenia gier wideo). Zjawisko to znane jest w społeczności jako manipulacja RNG. Dzięki niej gracze sprawiają, że mechanika gry zachowuje się w sposób w pełni przewidywalny, co pozwala im ukończyć tytuł w rekordowo krótkim czasie. W tym kontekście nie jest to jednak krytyczna wada bezpieczeństwa.

Sytuacja zmienia się diametralnie, gdy przewidywalność generatora może prowadzić do poważnych konsekwencji – na przykład podczas generowania kluczy bezpieczeństwa.

Gdyby cyberprzestępca odkrył ziarno użyte do wygenerowania kluczy RSA w certyfikatach TLS, mógłby z łatwością rozszyfrować przechwycony ruch sieciowy. W praktyce oznaczałoby to dostęp do haseł, danych finansowych i innych poufnych informacji przesyłanych przez internet.

Dlatego w kryptografii absolutnie konieczne jest stosowanie bezpieczniejszych metod – czyli sprzętowych generatorów liczb prawdziwie losowych (TRNG).

Generator Google'a

Warto wiedzieć, że wyszukiwarka Google posiada wbudowane narzędzie do generowania liczb losowych oparte na języku JavaScript. To proste w obsłudze rozwiązanie świetnie sprawdza się podczas gier planszowych w gronie rodziny czy znajomych. Aby z niego skorzystać, wystarczy wpisać w pasku wyszukiwania Google frazę "generator liczb losowych".

Liniowa Metoda Kongruencyjna (LCG)

Jednym z najstarszych i najpopularniejszych algorytmów stosowanych w generatorach pseudolosowych (PRNG) jest Liniowa Metoda Kongruencyjna (LCG - Linear Congruential Generator). Używa się jej do prostych zadań, ponieważ nie posiada odporności kryptograficznej. Algorytm ten został po raz pierwszy zaproponowany przez amerykańskiego matematyka, Derricka Henry'ego Lehmera, w 1949 roku.

Aby zaimplementować tę metodę generowania ciągów, konieczne jest dobranie czterech parametrów:

m > 0, modulo

0 ≤ a ≤ m, mnożnik

0 ≤ c ≤ m, przyrost

0 ≤ X₀ ≤ m, liczba początkowa

Kolejne liczby w sekwencji pseudolosowej generowane są na podstawie następującego wzoru matematycznego:

Xₙ₊₁ = (aXₙ + c) mod m

Warto pamiętać, że jakość tego generatora drastycznie zależy od doboru parametrów startowych.

Dla przykładu, jeśli użyjemy poniższego zestawu:

X₀ = 3, a = 4, c = 5, m = 6

w rezultacie otrzymamy krótką, szybko zapętlającą się sekwencję:

3, 5, 1, 3, 5, 1

Taki ciąg gołym okiem nie wygląda na losowy.

Wystarczy jednak nieznacznie zmodyfikować parametry algorytmu:

X₀ = 2, a = 85, c = 507, m = 1356

Aby rozkład wyników stał się znacznie bardziej nieprzewidywalny. Pokazuje to, jak kluczowy dla tego algorytmu jest staranny dobór liczb początkowych:

2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365...

Mimo że liniowy generator kongruencyjny przy dobrych parametrach może wyprodukować statystycznie poprawną sekwencję pseudolosową, jest on całkowicie bezużyteczny z punktu widzenia bezpieczeństwa. Generatory oparte na metodzie kongruentnej liniowej są w pełni przewidywalne po zebraniu odpowiedniej próbki danych, przez co absolutnie nie wolno ich używać w kryptografii.

Słabość LCG została udowodniona w praktyce. Został on po raz pierwszy złamany przez Jima Reedsa w 1977 roku, a następnie przez kryptolog Joan Boyar w 1982 roku (której udało się również złamać generatory kwadratowe i sześcienne). Ich badania ostatecznie potwierdziły bezużyteczność metod kongruencyjnych w zabezpieczeniach. Mimo to, generatory LCG nadal świetnie sprawdzają się w zastosowaniach niekryptograficznych – na przykład w prostych symulacjach lub starszych grach. Są niezwykle szybkie, zoptymalizowane wydajnościowo i osiągają dobre wyniki w większości podstawowych testów empirycznych.

Nowoczesne Generatory Liczb Losowych w Sprzęcie Komputerowym

QRBG121

Ten sprzętowy generator opiera swoją losowość na fizyce kwantowej. Wykorzystuje proces emisji fotonów w półprzewodnikach i precyzyjną detekcję pojedynczych cząstek światła. W tym układzie fotony są rejestrowane w całkowicie losowych odstępach czasu, niezależnie od siebie. To właśnie informacje o ułamkach sekund, w których foton trafia w detektor, służą jako idealne źródło entropii do generowania czystych, losowych bitów.

Lampy Lawowe (Ściana Entropii Cloudflare)

W głównej siedzibie firmy Cloudflare w San Francisco znajduje się słynna ściana generatorów liczb losowych złożona ze zwykłych "lamp lawowych". Każda taka lampa to szklane naczynie wypełnione przezroczystym olejem i zabarwionym woskiem (parafiną). Wosk jest w normalnych warunkach cięższy od oleju, ale po podgrzaniu przez żarówkę na dnie lampy staje się lżejszy, przez co w sposób chaotyczny unosi się i opada.

Cały ten nieprzewidywalny taniec cieczy jest na bieżąco monitorowany przez system kamer robiących zdjęcia. Te z kolei przetwarzane są na ciągi liczb, które na końcu stają się kluczami szyfrującymi chroniącymi ogromną część globalnego ruchu w internecie.

Co ciekawe, pozostałe biura Cloudflare stosują równie kreatywne metody. W biurze w Londynie system kamer rejestruje nieprzewidywalne ruchy trzech wahadeł chaotycznych. Z kolei w Singapurze firma używa licznika Geigera do pomiaru rozpadu promieniotwórczego małej grudki uranu. Rozpad izotopów jest zjawiskiem w pełni losowym, co czyni z niego idealne i bezpieczne "źródło danych" kryptograficznych.

HotBits

HotBits to intrygujący serwis internetowy dostarczający prawdziwe liczby losowe, które generowane są na żywo przez czuły licznik Geigera rejestrujący tło promieniowania jonizującego w środowisku. Użytkownik wypełnia formularz na stronie, podając pożądaną liczbę losowych bajtów oraz preferowaną metodę odbioru. Co ważne z punktu widzenia prywatności, po dostarczeniu danych do klienta, liczby te są natychmiast i bezpowrotnie kasowane z serwerów HotBits.

Kwantowe Fluktuacje Próżni

Wbrew powszechnemu wyobrażeniu o absolutnej pustce, z fizycznego punktu widzenia próżnia wcale nie jest "pusta". Zgodnie z fundamentalną dla mechaniki kwantowej zasadą nieoznaczoności Heisenberga, w przestrzeni nieustannie powstają i znikają tzw. cząstki wirtualne.

Kanadyjscy fizycy wykorzystali to zjawisko, projektując niezwykle szybki i konstrukcyjnie genialny generator liczb losowych oparty właśnie na fluktuacjach próżni. Składa się on z lasera impulsowego o bardzo wysokiej częstotliwości promieniowania, nośnika o wysokim współczynniku załamania światła (w tym wypadku diamentu) oraz precyzyjnego detektora. Podczas przechodzenia przez strukturę diamentu każdy z impulsów laserowych zmienia swoje parametry w zależności od tego, na jakie mikroskopijne fluktuacje próżni natrafi na swojej drodze.

Przez te interakcje w widmie rozproszonego promieniowania pojawiają się specyficzne linie spektralne. Ponieważ fluktuacje kwantowe są z natury całkowicie nieprzewidywalne, linie te różnią się od siebie przy każdym pomiarze, stanowiąc nieskazitelne źródło entropii dla RNG.

Generator z Nanorurek Węglowych

Ta nowatorska technologia łączy niesamowitą miniaturyzację z losowością opartą na szumie termicznym.

Inżynierowie skonstruowali generator liczb losowych z wykorzystaniem statycznej pamięci RAM, która została wydrukowana przy pomocy specjalnych tuszów zawierających półprzewodnikowe nanorurki węglowe. Tak zmodyfikowana komórka pamięci wykorzystuje mikroskopijne fluktuacje szumu termicznego układu do ciągłego generowania losowych bitów.

Dzięki swojej elastyczności, układ z nanorurek węglowych może być drukowany bezpośrednio na plastikowych podłożach. Otwiera to drogę do wbudowywania bezpiecznych generatorów kryptograficznych w miniaturowe i elastyczne urządzenia ubieralne (wearables), jednorazowe etykiety RFID czy nawet inteligentną odzież.

Kostki do gry i Fundacja Electronic Frontier (EFF)

Organizacja EFF udostępniła genialny w swojej prostocie (i w 100% bezpieczny) sposób na tworzenie silnych haseł bez użycia komputera. Metoda ta (często nazywana Diceware) opiera się na fizycznym sprzęcie, który każdy z nas ma w domu – sześciościennych kostkach do gry.

Proces wygląda następująco: rzucasz pięcioma kostkami naraz i po kolei, od lewej do prawej, zapisujesz wylosowane cyfry. Załóżmy, że otrzymałeś ciąg: 63131. Następnie otwierasz specjalną, zweryfikowaną listę słów (dostępną na stronie EFF) i odszukujesz hasło przypisane do numeru 63131. W tym przypadku będzie to angielskie słowo "turbofan" (silnik turbowentylatorowy).

Powtarzając tę czynność kilka razy – na przykład pięciokrotnie – stworzysz tzw. passphrase (frazę hasłową) składającą się z pięciu losowych słów. Może to być na przykład: "turbofan purge unfitting try pruning" (turbofan, oczyszczać, niepasujący, próbować, przycinanie). Dzięki wykorzystaniu mnemotechniki zapamiętanie takiego ciągu słów jest znacznie łatwiejsze dla człowieka niż zapamiętanie skomplikowanego ciągu znaków (np. Xq$8v!pL), a pod względem siły kryptograficznej taka fraza jest praktycznie niemożliwa do złamania.

Kwantowy Generator Liczb Losowych ze Smartfona Nokia

W 2014 roku naukowcy z Uniwersytetu w Genewie udowodnili, że zaawansowaną kryptografię kwantową można realizować na sprzęcie codziennego użytku. Opracowali oni urządzenie klasy QRNG (Quantum Random Number Generator), wykorzystując do tego jedynie matrycę aparatu z popularnego smartfona Nokia N9.

Mechanizm działania opierał się na zliczaniu poszczególnych fotonów uderzających w każdy pojedynczy piksel matrycy aparatu. Jako źródło światła wykorzystano standardową zieloną diodę LED. W bardzo krótkim okienku czasowym, każdy piksel z 8-megapikselowego aparatu smartfona detekował średnio około 400 fotonów. Niewielkie kwantowe wahania w liczbie odebranych fotonów przez poszczególne piksele były następnie agregowane i skutecznie przekształcane w bezpieczny ciąg prawdziwie losowych liczb.