Jak komputery generują losowe liczby

Komputery generują losową liczbę dla wszystkiego, od kryptografii po gry wideo i hazard. Istnieją dwie kategorie liczb losowych - "prawdziwe" liczby losowe i numery pseudolosowe - a różnica jest ważna dla bezpieczeństwa systemów szyfrowania.

Komputery mogą generować prawdziwie losowe liczby, obserwując niektóre dane zewnętrzne, takie jak ruchy myszy lub szum wentylatora, który nie jest przewidywalny, i tworzenie z niego danych. Jest to znane jako entropia. Innym razem generują liczby "pseudolosowe" za pomocą algorytmu, więc wyniki są przypadkowe, nawet jeśli nie są.

Temat ten stał się ostatnio bardziej kontrowersyjny, a wielu ludzi kwestionuje, czy wbudowany w Intel układ liczb losowych generatorów liczbowych jest godny zaufania. Aby zrozumieć, dlaczego nie jest to wiarygodne, musisz najpierw zrozumieć, w jaki sposób losowe liczby są generowane i do czego są wykorzystywane.

Jakie są używane liczby losowe

Liczby losowe były używane przez wiele tysięcy lat. Niezależnie od tego, czy chodzi o rzucanie monetą czy rzucanie kostką, celem jest pozostawienie wyniku końcowego losową szansą. Generatory liczb losowych w komputerze są podobne - są próbą uzyskania nieprzewidywalnego, losowego wyniku.

Generatory liczb losowych są przydatne do wielu różnych celów. Oprócz oczywistych aplikacji, takich jak generowanie liczb losowych w celach hazardowych lub tworzenie nieprzewidywalnych wyników w grze komputerowej, losowość jest ważna dla kryptografii.

Kryptografia wymaga liczb, których atakujący nie mogą odgadnąć. Nie możemy po prostu używać tych samych liczb w kółko. Chcemy generować te liczby w bardzo nieprzewidywalny sposób, aby napastnicy nie mogli ich odgadnąć. Te losowe liczby są niezbędne do bezpiecznego szyfrowania, niezależnie od tego, czy szyfrujesz własne pliki, czy tylko używasz strony HTTPS w Internecie.

Prawdziwe liczby losowe

Być może zastanawiasz się, w jaki sposób komputer może wygenerować losową liczbę. Skąd bierze się ta "przypadkowość". Jeśli to tylko kawałek kodu komputerowego, nie jest możliwe, że liczby generowane przez komputer mogą być przewidywalne?

Generalnie grupujemy komputery losowe na dwa rodzaje, w zależności od tego, jak są generowane: "Prawdziwe" liczby losowe i liczby pseudolosowe.

Aby wygenerować "prawdziwą" liczbę losową, komputer mierzy pewien typ fizycznego zjawiska, które ma miejsce poza komputerem. Na przykład komputer może zmierzyć rozpad radioaktywny atomu. Zgodnie z teorią kwantową, nie ma sposobu, aby wiedzieć na pewno, kiedy nastąpi rozpad radioaktywny, więc jest to w gruncie rzeczy "czysta przypadkowość" ze wszechświata. Atakujący nie byłby w stanie przewidzieć, kiedy nastąpi rozpad radioaktywny, więc nie będą znać wartości losowej.

Aby uzyskać bardziej codzienny przykład, komputer może polegać na hałasie atmosferycznym lub po prostu użyć dokładnego czasu naciśnięcia klawiszy na klawiaturze jako źródła nieprzewidywalnych danych lub entropii. Na przykład Twój komputer może zauważyć, że naciśniesz klawisz dokładnie o 0.23423523 sekundy po godzinie 14.00 ... Weź wystarczająco dużo konkretnych czasów związanych z tymi naciśnięciami klawiszy, a będziesz miał źródło entropii, której możesz użyć do wygenerowania "prawdziwego" losowego numer. Nie jesteś maszyną przewidywalną, więc osoba atakująca nie może odgadnąć dokładnego momentu naciśnięcia tych klawiszy. Urządzenie / dev / random w systemie Linux, które generuje liczby losowe, "blokuje" i nie zwraca wyniku, dopóki nie zgromadzi wystarczającej entropii, aby zwrócić prawdziwie losową liczbę.

Numery pseudolosowe

Numery pseudolosowe są alternatywą dla "prawdziwych" liczb losowych. Komputer może użyć wartości początkowej i algorytmu do generowania liczb, które wydają się losowe, ale w rzeczywistości są przewidywalne. Komputer nie zbiera żadnych przypadkowych danych ze środowiska.

To nie musi być złe w każdej sytuacji. Na przykład, jeśli grasz w grę wideo, nie ma znaczenia, czy zdarzenia występujące w tej grze są uporządkowane według "prawdziwych" liczb losowych lub numerów pseudolosowych. Z drugiej strony, jeśli używasz szyfrowania, nie chcesz używać liczb pseudolosowych, które atakujący może odgadnąć.

Załóżmy na przykład, że atakujący zna algorytm i wartość początkową, którą wykorzystuje generator liczb pseudolosowych. Powiedzmy, że algorytm szyfrowania otrzymuje liczbę pseudolosową z tego algorytmu i używa go do generowania klucza szyfrowania bez dodawania dodatkowej losowości. Jeśli atakujący wie wystarczająco dużo, mogą pracować wstecz i określić liczbę pseudolosową, którą algorytm szyfrowania musiał wybrać w tym przypadku, przełamując szyfrowanie.

NSA i generator liczb losowych sprzętu Intela

Aby ułatwić programistom i pomóc w generowaniu bezpiecznych liczb losowych, chipy Intela zawierają sprzętowy generator liczb losowych znany jako RdRand. Ten układ wykorzystuje źródło entropii na procesorze i dostarcza losowe numery do oprogramowania, gdy oprogramowanie ich zażąda.

Problem polega na tym, że generator liczb losowych jest w zasadzie czarną skrzynką i nie wiemy, co się w nim dzieje. Jeśli RdRand zawiera backdoora NSA, rząd będzie w stanie złamać klucze szyfrujące, które zostały wygenerowane tylko z danymi dostarczonymi przez ten generator liczb losowych.

To poważny problem. W grudniu 2013 r. Twórcy FreeBSD usunęli wsparcie dla używania RdRand bezpośrednio jako źródła przypadkowości, mówiąc, że nie mogli mu ufać. [Źródło] Dane wyjściowe urządzenia RdRand zostaną wprowadzone do innego algorytmu, który doda dodatkową entropię, zapewniając, że wszelkie backdoory w generatorze liczb losowych nie będą miały znaczenia. Linux działał już w ten sposób, dalej losując losowe dane pochodzące z RdRand, aby nie można było przewidzieć, nawet gdyby istniało backdoor. [Źródło] W niedawnym AMA ("Ask Me Anything") na Reddit, CEO Intel Brian Krzanich nie odpowiedział na pytania dotyczące tych obaw. [Źródło]

Oczywiście nie jest to tylko problem z układami Intela. Twórcy FreeBSD również nazwali chipy Via po imieniu. Ta kontrowersja pokazuje, dlaczego generowanie losowych liczb, które są naprawdę losowe i nie są przewidywalne, jest tak ważne.

Aby generować "prawdziwe" liczby losowe, generatory liczb losowych gromadzą "entropię" lub pozornie losowe dane ze świata fizycznego wokół nich. Dla liczb losowych, które nie naprawdę muszą być losowe, mogą po prostu użyć algorytmu i wartości początkowej.

Image Credit: rekre89 na Flickr, Lisa Brewster na Flickr, Ryan Somma na Flickr, huangjiahui na Flickr