Losowość w informatyce

Czy zastanawiałeś się kiedyś, co wspólnego mają: zegar, lampa i rozpad promieniotwórczy pierwiastków? Cóż zapewne nie, yyyy…. Tak czy inaczej, w tym wpisie odpowiem między innymi na to pytanie.

Prawdziwy generator liczb losowych.

Zapewne zdarzyło ci się kiedyś rozwiązać konflikt za pomocą rzutu monetą. Metoda ta wydaje się sprawiedliwa, każdy ma w niej 50% szans na wygraną, akceptujemy to, że los ma zdecydować o naszej przyszłości. Ale czy rzut monetą naprawdę możemy nazwać losowym?

Zgodnie z mechaniką klasyczną wszystko jest przyczynowo-skutkowe, jeżeli bylibyśmy w stanie przeanalizować całe otoczenie, to zdołalibyśmy przewidzieć przyszłość. Mechanika kwantowa jest jednak innego zdania, zakłada ona, że znając stan początkowy danego układu, możemy przewidzieć jego zachowanie tylko z pewnym prawdopodobieństwem.

Bez względu na to, jaka jest prawda, monetę możemy uznać za generator liczb prawdziwie losowych, gdyż wyniki przez nią generowane, na dzień dzisiejszy nie sposób odgadnąć.

Generator liczb prawdziwie losowych działa w oparciu o pomiary zewnętrzne procesów których nie jesteśmy w stanie przewidzieć, przykładowo wykorzystywane są pomiary szumów elektrycznych lub rozpad promieniotwórczy pierwiastków. Odczytane stany zamieniane są na liczby.

W informatyce liczby losowe mają zastosowanie między innymi w kryptografii. Klucz służący do zaszyfrowania wiadomości powinien być nieprzewidywalny inaczej szyfr może zostać złamany.

Generator liczb pseudolosowych

Wyobraź sobie, że próbujesz rozstrzygnąć kolejną sprawę rzutem monetą, otwierasz portfel a tam pustka. Na szczęście masz smartfona, wpisujesz w Google “rzut monetą” pojawia się animacja monety, po czym dostajemy wynik “reszka”.

Skąd Google wziął ten wynik? Komputery są maszynami logicznymi, jak miałyby wykonać tak nielogiczne zadanie polegające na podaniu losowej wartości.

Cóż, Google mógł być w posiadaniu generatora liczb prawdziwie losowych i zwyczajnie odczytać z niego wyniki. Generator taki ma jednak ograniczenia, istnieje nieduży limit liczb, jakie może on wygenerować w danym czasie, a zapotrzebowanie na liczby losowe jest ogromne.

W tym momencie do gry wchodzi matematyka. Korzystając z odpowiednich równań, jesteśmy w stanie wygenerować liczby, które będą wyglądać na losowe. Często stosowanym do mniej wymagających zastosowań algorytmem jest ulepszona wersja Liniowego Generatora Kongruentnego,  zaproponowanego przez D. H. Lehmera. Opisany jest on wzorem

W tym momencie powinienem opisać, co oznaczają litery we wzorze, ale tego nie zrobię, żeby wszystkich nie zanudzić, zamiast tego bez słowa wyjaśnienia skorzystamy z przykładowych wartości dostępnych w sieci. 

(dla zainteresowanych tematem: https://en.wikipedia.org/wiki/Linear_congruential_generator ) )

a=75, c=74, m=65537

Mamy już prawie wszystkie potrzebne nam wartości oprócz tak zwanego ziarna (seed).

Jest to pewna początkowa wartość, która wymagana jest do rozpoczęcia algorytmu i od której zależeć będą następne wyniki.

Załóżmy że przykładowym ziarnem będzie liczba 2137. Zapiszmy więc obliczenia.

(75*2137+74) mod 65537

Wrzucamy całość do Google i dostajemy wartość 29275. Jest to pierwsza liczba, zapiszmy ją sobie i powtórzmy obliczenia, zamieniając 2137 we wzorze na wynik, czyli na 29275.

(75*29275+74) mod 65537

Otrzymaliśmy 2 liczbę, teraz zamieńmy poprzednią wartość 29275 na nową 32978 itd.

(75*2137+74) mod 65537= 29275

(75*29275+74) mod 65537= 32978

(75*32978+74) mod 65537= 48555

(75*48555+74) mod 65537= 37164

(75*37164+74) mod 65537= 34820

Dobra otrzymaliśmy 5 wartości pseudolosowych, żeby zasymulować rzut monetą wystarczy, że sprawdzimy, które wartości są parzyste a które nieparzyste. Inaczej mówiąc sprawdzimy, czy liczba dzieli się przez 2 bez reszty, czy z resztą. W przypadku parzystej liczby wynik interpretujemy jako orzeł a w przypadku nieparzystej jako reszka.

Wyniki więc wyglądają następująco: reszka, orzeł, reszka, orzeł, orzeł. 

Algorytm tu użyty nie jest uznawany za bezpieczny do zastosowań w kryptografii, ale nic nie stoi na przeszkodzie, by użyć go przykładowo w grach komputerowych. Istnieją algorytmy dużo bardziej nieprzewidywalne i trudniejsze do złamania, również one potrzebują jednak wartości początkowej (ziarna), którą nie sposób będzie odgadnąć lub wydedukować. Wartość ta musi zostać pozyskana na naszym komputerze, inaczej nie mielibyśmy pewności co do jej bezpieczeństwa.

Czy oznacza to, że musimy trzymać w domu radioaktywny pierwiastek i pobierać z niego losowe liczby? Na szczęście nie, wartość ziarna komputer może obliczyć analizując nasze zachowanie, mierząc: aktualną godzinę, czas między naciśnięciami klawiszy lub ruchy myszką.

Wartości te mogą być również pobierane z otoczenia poprzez sprawdzenie choćby temperatury podzespołów. Zazwyczaj stosowany jest miks różnych zewnętrznych źródeł nieprzewidywalnych danych.

Istnieją także bardziej oryginalne rozwiązania, słyszeliście o lampach lawa? Wzory i kolory powstają na tyle nieprzewidywalnie, że firma Cloudflare postanowiła wykorzystać je do pozyskania losowych liczb, wykonują im zdjęcia i na ich podstawie obliczając nieprzewidywalną wartość, która wraz z innymi źródłami danych tworzy ziarno.