13Jul
Komputery generują losową liczbę dla wszystkiego, od kryptografii po gry wideo i hazard. Istnieją dwie kategorie liczb losowych - "prawdziwe" liczby losowe i liczby pseudolosowe - a różnica jest ważna dla bezpieczeństwa systemów szyfrowania.
Komputery mogą generować prawdziwie losowe liczby, obserwując niektóre zewnętrzne dane, takie jak ruchy myszy lub szum wentylatora, które nie są przewidywalne, i tworzenie z nich danych. Jest to znane jako entropia. Innym razem generują liczby "pseudolosowe" za pomocą algorytmu, dzięki czemu wyniki są przypadkowe, nawet jeśli nie są.
W ostatnim czasie temat ten stał się bardziej kontrowersyjny, a wielu ludzi kwestionuje, czy wbudowany w Intel układ liczb losowych jest niezawodny. Aby zrozumieć, dlaczego nie jest to wiarygodne, musisz zrozumieć, w jaki sposób losowe liczby są generowane w pierwszej kolejności i do czego są wykorzystywane.
Jakich liczb losowych używa się w
Losowe liczby 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, przypadkowego 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, przypadkowość jest ważna dla kryptografii.
Kryptografia wymaga numerów, 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 po prostu używasz strony internetowej 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, czy liczby generowane przez komputer nie są przewidywalne?
Generalnie grupy komputerów liczb losowych generujemy na dwa typy, 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 zasadniczo "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 szumie 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. Zdobądź wystarczającą liczbę 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" losowegonumer. Nie jesteś maszyną przewidywalną, więc osoba atakująca nie może odgadnąć dokładnego momentu naciśnięcia tych klawiszy. Urządzenie losowe /dev/ 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 liczb pseudolosowych. Z drugiej strony, jeśli używasz szyfrowania, nie chcesz używać liczb pseudolosowych, które atakujący może odgadnąć.
Na przykład, powiedzmy, ż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 żadnej 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, łamiąc szyfrowanie.
NSA i sprzętowy generator liczb losowych Intela
Aby ułatwić programistom tworzenie bezpiecznych liczb losowych, chipy Intela zawierają sprzętowy generator liczb losowych znany jako RdRand. Układ ten 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 backdoor NSA, rząd będzie mógł złamać klucze szyfrujące, które zostały wygenerowane tylko z danymi dostarczonymi przez generator liczb losowych.
Jest to poważny problem. W grudniu 2013 r. Programiści FreeBSD usunęli wsparcie dla używania RdRand bezpośrednio jako źródła losowoś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 losowo losując dane pochodzące z RdRand, tak aby nie można było przewidzieć, nawet jeśli był backdoor.[Źródło] W niedawnym AMA( "Ask Me Anything") na Reddicie, CEO Intela, 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ż nazywali chipy Via po imieniu. Ta kontrowersja pokazuje, dlaczego tak ważne jest generowanie losowych liczb, które są naprawdę losowe i nie są przewidywalne.
Aby generować "prawdziwe" liczby losowe, generatory liczb losowych gromadzą "entropię" lub pozornie losowe dane z otaczającego świata fizycznego. 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