Jak komputer losuje “losowe liczby”? O sztuczkach wokół RNG

Jeżeli potrzebujesz losowej liczby, możesz rzucić kością o odpowiedniej liczbie ścianek. Możesz też zapisać karteczki numerami i wylosować jedną z całego stosu. Komputer nie może tego zrobić, a jednak w jakiś sposób generuje on liczby losowe. Przyjrzyjmy się temu.

  • Komputery są sprzętem, który działa w oparciu o mocno deterministyczne oprogramowanie, uniemożliwiając mu wykonanie czegoś takie jak “wylosowanie” liczby
  • Istnieją jednak sposoby, by komputer wybrał nam liczbę pseudolosową, albo wykorzystał nieprzewidywalne zjawiska do wygenerowania liczby, którą możemy określić losową
  • Generator liczb pseudolosowych to prosty program, który do działania wykorzystuje jedno matematyczne działanie

Po co komputerowi losowe liczby? Na pewno spotkaliście się z losowością, gdy graliście w jakieś gry komputerowe. Szansa na trafienie, zadawanie obrażeń w zakresie od-do, możliwość wypadnięcia losowych przedmiotów, zachowanie przeciwników i wybór ich ataków, a nawet proceduralnie generowane światy – to wszystko wymaga jakiejś losowości, by gracz był stale zaskakiwany.

Z drugiej strony mamy znacznie bardziej skomplikowane zadania, jak kryptografia i szyfrowanie danych, w tym generowanie kluczy do tworzenia bezpiecznych połączeń w sieci. Nie chcemy przecież, by ktoś przewidział, jaki klucz szyfrujący nasz komputer wygeneruje za chwilę. Mógłby wtedy bez problemu odczytać naszą korespondencję.

Niezależnie od tego czy gramy, czy właśnie wymieniamy poufne informacje w sieci, potrzebujemy liczb losowych. Problem w tym, że komputer sam sobie tych liczb wylosować nie może. Jest to bowiem maszyna działająca na ściśle ustalonych procesach, która może wykonywać obliczenia, porównywać je, ale nie ma możliwości, by jakikolwiek program komputerowy “wymyślił sobie” losową liczbę. Stosuje do tego pewne pomoce.

Generatory liczb pseudolosowych i generatory liczb losowych

Obecnie wyróżnia się dwie metody pozyskiwania liczb, które użytkownik uznaje za losowe. Pierwsze z nich to generatory liczb pseudolosowych i są… cóż… nie-do-końca-losowe. To znaczy ich odkrywaniu wciąż towarzyszą obliczenia i algorytmy z bardzo charakterystycznymi zmiennymi, które gwarantują nam nieprzewidywalność i losowość do tego stopnia, że na potrzeby gier komputerowych nadają się one wyśmienicie.

Generatory liczb prawdziwie losowych to z kolei narzędzia, które nie działają wewnątrz programu komputerowego, a czerpią informacje spoza środowiska programistycznego, gdzie chaos i entropia są na porządku dziennym. Brzmi skomplikowanie? Do tego przejdziemy za chwilę.

Odczytaj mi liczbę (pseudo)losową

Pierwsza metoda na tworzenie liczb pseudolosowych, a więc na tyle różnorodnych, by się w tym nie połapać, ale jednocześnie zbyt mało nieprzewidywalnych, by zastosować je np. do zabezpieczeń kont bankowych i kart kredytowych, jest relatywnie prosta. Nawet dla kogoś, kto nigdy nie programował, a edukację matematyczną zakończył na podstawówce.

Powszechną wiedzą matematyczną jest chociażby to, że wynik dzielenia – iloraz – nie zawsze jest liczbą całkowitą bez reszty. Równie oczywistym jest fakt, że reszta z dzielenia nigdy nie będzie większa od dzielnika, a więc tej liczby “przez którą dzielimy”. Jakiejkolwiek liczby nie podzielimy przez 10 – czy będzie to 2, 13 czy 2137, reszta zawsze będzie mniejsza niż 10 i mieściła się w zakresie od 0 do 9, a więc może przyjąć 10 różnych wartości. W powyższych przykładach resztą z dzielenia będzie kolejno 2 (10*0+2), 3 (10*1+3) i 7 (10*213+7).

Mamy więc już dosyć prosty wzór na generowanie wyników, które będą mieścić się w jakimś konkretnym zakresie. Chcąc generować liczby od 0 do 6 musimy za dzielnik podstawić 6. Jeżeli będziemy chcieli znaleźć pseudolosową liczbę od 0 do 100 mln… dzielnikiem musi być liczba 100000000. Taki wzór, wykorzystując funkcję modulo, której wynikiem jest reszta z dzielenia, można zapisać następująco: X mod Y, gdzie X jest wartością zmienną (za chwilę określimy ją sobie mianem “ziarna”), a Y to zakres poszukiwanych liczb.

Co jednak, gdy zakres będzie wynosił np. od 35 do 50, bo takie obrażenia zadaje nasza broń? Łatwo policzyć, że wtedy musimy wyliczyć 16 różnych wartości, a więc dzielnikiem będzie 16, a do ostatecznego wyniku należy dodać dolną wartość graniczną – 35. W ten sposób uzyskamy wyniki od 0 do 15, co po dodaniu nam dolnej granicy – 35 – zamknie wyniki w zakresie od 35 do 50.

Skąd jednak wziąć X? Wiemy już, że X nie może być losowy, bo… dopiero tworzymy liczby “losowe”. Musimy więc znaleźć wartości, które są relatywnie duże, nie powtarzają się często, a jednocześnie da się je łatwo odczytać. Okazuje się, że takich wartości jest w komputerze całkiem dużo. Za X można więc podstawić np:

  • liczbę milisekund od włączenia systemu
  • liczbę naciśnięć przycisków na klawiaturze od włączenia systemu
  • liczbę kliknięć myszy
  • dystans przejechany kursorem myszy
  • liczbę wyświetlonych klatek animacji w grze

Załóżmy, że od włączenia systemu kliknałęm myszą 374 razy. W momencie ataku mojej postaci w grze bronią o obrażeniach 35-50, wartość 374 podstawiona jest jako ziarno (ang. seed) do naszego generatora liczb pseudolosowych. W takiej sytuacji gra obliczy ze wzoru 373 mod 16+35, że zadam… 40 pkt obrażeń. 373 dzielone przez 16 daje nam bowiem wynik 23 i 5 reszty (373=16*23+5).

Jest to system oparty na prostym działaniu, a jednocześnie mocno nieprzewidywalny. Zmienną są bowiem wartości, których w większości przypadków nie da się w prosty sposób obliczyć. Z drugiej jednak strony mając odpowiednią wiedzę, można “złamać” dany algorytm i przewidzieć wynik w zależności od wartości ziarna. Dlatego też ten prosty sposób ogranicza się do domowych zastosowań.

Moc chaosu

Czy da się jednak wygenerować coś, co zostanie określone jako liczba prawdziwie losowa, której nie generuje algorytm i przewidywanie wyników będzie prawdziwie niemożliwe? W przypadku wcześniejszego przykładu ziarno zawsze było wartością bardzo trudną do ustalenia, ale nie niemożliwą.

Inżynierowie i naukowcy opracowali jednak metody, które służą do generowania zupełnie nieprzewidywalnych wartości ziaren, a co za tym idzie – także wyników w generatorze liczb losowych. Za przykład takich zjawisk w wyspecjalizowanych maszynach podać można mierzenie czasu do rozpadu radioaktywnego pierwiastka. Jest to bowiem wartość zgodnie z teorią kwantową nieprzewidywalna co do najmniejszych części sekundy.

W przypadku procesorów domowych przykładem generatora uznanego za losowy jest technologia wykorzystująca instrukcje RDRAND, która korzysta z entropii, wpływającej na warunki wewnątrz chipu. Mowa tu o zjawiskach takich jak szum termiczny, a więc zakłócenia wszelkich sygnałów elektrycznych wywoływane zjawiskami termicznymi w ciałach stałych i gazach, bądź szum atmosferyczny, a więc zakłócenia sygnałów wywołane m.in. przez wyładowania atmosferyczne i inne zjawiska pogodowe.

Mierząc wpływ tych szumów na sygnał, można w każdym ułamku sekundy odnajdywać niewielkie różnice np. w czasie przepływu dwóch równocześnie nadawanych sygnałów. Ze względu na zakłócenia w otoczeniu, będą one w stanie się zdesynchronizować i jeden z nich dotrze do odbiornika jako pierwszy, czym można – w dużym uproszczeniu – zasymulować rzut monetą.

Tagi:

Podziel się postem :)

Najnowsze:

Bezpieczeństwo

Poradnik: Zabezpiecz swój dom – masz w nim masę urządzeń podatnych na ataki cyberprzestępców

Polacy mają w swoich gospodarstwach domowych coraz więcej urządzeń elektronicznych podłączonych do internetu. Choć wciąż mówimy o kilkunastu lub kilkudziesięciu sprzętach – a nie kilkuset, jak to przewidywano w pewnych badaniach – niekwestionowanie zauważalny jest wzrost ich liczby. Z tego względu należy podjąć wszelkie kroki, by zabezpieczyć swoją domową sieć.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *