Generator Liczb

Generator liczb losowych to proces generowania losowej liczby za każdym razem, gdy jest to potrzebne, bez możliwości zdefiniowania wzorca z wcześniej wygenerowanych liczb. Liczba ta może być generowana zarówno przez algorytm, jak i urządzenie sprzętowe.

Zastosowanie Generatorów Liczb Losowych

Generowanie losowych liczb jest potrzebne do różnych zadań, od gier komputerowych po powszechne aplikacje. Na przykład system używa generatora liczb losowych do wyświetlania losowego banera lub losowej jednostki reklamowej na stronie internetowej. W kryptografii losowe liczby są również używane do tworzenia unikalnego szyfru lub klucza.

Generowanie liczb losowych jest używane do generowania liczb lub tekstu dla captcha, szyfrowania, generowania soli do przechowywania haseł, generatora haseł, kolejności kart w kasynie online, podejmowania decyzji, próbkowania i symulacji.

Algorytm generatora liczb losowych jest często używany w grach wideo. Nawet jeśli grasz na tym samym poziomie w grze, nie będzie dokładnie tak samo za każdym razem, gdy próbujesz ukończyć misję. Może różnice nie będą widoczne w lokalizacji czy misji. Jednak będą widoczne w liczbie nadchodzących wrogów i miejscach, w których się pojawiają, zmianach klimatu oraz różnych napotkanych przeszkodach. To sprawia, że gra jest bardziej ekscytująca.

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

Niech będzie sekwencja liczb: 1, 2, 3, 4, 5. Czy jest losowa?

Zmienna losowa to zmienna, która przyjmuje jedną z pewnych wartości w wyniku próby. I nie możesz dokładnie przewidzieć wystąpienia konkretnej wartości przed jej pojawieniem się.

Załóżmy, że podane liczby zostały uzyskane przez wpisywanie na jednym z górnych rzędów klawiatury. W takim przypadku okazuje się, że ta kombinacja nie jest losowa, ponieważ po 5, następną liczbę, 6, można przewidzieć z dużym prawdopodobieństwem.

Sekwencja będzie losowa tylko wtedy, gdy nie ma zależności między symbolami.

Podstawowym warunkiem, który jest niezwykle ważny dla poprawnej i uczciwej zasady działania generatora liczb losowych, jest absolutnie równa szansa na każdą możliwą liczbę, która mogłaby wypaść w tym systemie. Wskazuje to na całkowitą niezależność czynnika losowości i niezależność od tego, jakie inne liczby wypadły wcześniej lub później.

Na przykład, załóżmy, że rzucasz sześciościenną kostką po raz pierwszy. W takim przypadku możesz uzyskać absolutnie dowolną liczbę od 1 do 6 z takim samym prawdopodobieństwem. Bez względu na twoją liczbę, możesz rzucić kostką ponownie z taką samą szansą na uzyskanie tej samej liczby w drugim, setnym lub tysięcznym rzucie.

Sekwencja cyfr w liczbie Pi wydaje się niepowtarzalna i dla wielu może wydawać się losowa. Załóżmy, że nasz hipotetyczny generator opiera się na reprezentacji bitowej Pi, zaczynając od nieujawnionego punktu. Taki generator może być nieprzewidywalny w wielu kontekstach, potencjalnie przechodząc pewne testy na losowość. Jednak opieranie się na Pi do celów kryptograficznych niesie ze sobą ryzyko. Jeśli przeciwnik określi konkretny segment Pi, który jest używany, może przewidzieć zarówno poprzednie, jak i następujące segmenty, kompromitując bezpieczeństwo systemu.

Amerykański Narodowy Instytut Standaryzacji i Technologii zaproponował "Pakiet Testów Statystycznych dla Generatorów Liczb Losowych i Pseudolosowych dla Zastosowań Kryptograficznych". Zawiera on 15 testów statystycznych, których celem jest określenie miary losowości bitów generowanych przez generatory sprzętowe lub programowe.

Rodzaje Generatorów Liczb Losowych

Istnieją dwa rodzaje generatorów liczb losowych (RNG): prawdziwe generatory liczb losowych (TRNG) oraz pseudolosowe generatory liczb losowych (PRNG). TRNG używają zjawisk fizycznych do generowania liczb, podczas gdy PRNG wykorzystują algorytmy matematyczne.

Prawdziwy algorytm generatora liczb losowych jest tworzony za pomocą urządzenia sprzętowego, które wykorzystuje drobne procesy fizyczne do generowania losowych liczb, a mianowicie entropię. Entropia to czysty, niefiltrowany chaos.

Prawdziwe generatory liczb losowych wykorzystują zjawiska fizyczne, takie jak:

• radioaktywność,
• szum termiczny,
• szum elektromagnetyczny,
• mechanika kwantowa i inne.

Prawdziwy RNG jest powszechnie używany w systemach zorientowanych na bezpieczeństwo na całym świecie oraz w niektórych formach szyfrowania.

Generatory liczb losowych wykorzystują źródła entropii do akumulacji entropii i uzyskania początkowej wartości (ziarna) potrzebnej generatorom liczb losowych.

Algorytm pseudolosowego generatora liczb jest używany w obszarach bez obaw o bezpieczeństwo. Losowość pomaga unikać powtórzeń i sprawia, że proces jest bardziej atrakcyjny dla końcowego użytkownika. Implementacja technologii pseudolosowych generatorów liczb jest tańsza i szybsza, ponieważ nie wymaga sprzętu i może być łatwo wbudowana w kod programu. Chociaż proces nie jest całkowicie losowy i jest określony na podstawie algorytmu, jest bardziej odpowiedni do gier i programów.

PRNG używa pojedynczej początkowej wartości, od której zależy jego pseudolosowość. Tymczasem prawdziwy generator liczb losowych zawsze generuje losową liczbę, mając na początku zapewnioną wysokiej jakości wartość losową przez różne źródła entropii.

Generacja pseudolosowa ma swoje wady. Działa, ponieważ jest losowa dla niewprawnego oka. Jednak, gdybyś znał początkową wartość dla konkretnej sekwencji PRNG, mógłbyś przewidzieć, jakie liczby będą następne.

Entuzjaści szybkiego przechodzenia gier wideo często wykorzystują tę lukę - nazywają to manipulacją PRNG. Sprawiają, że gra przebiega przewidywalnie, aby mogli ją przejść jak najszybciej. Na szczęście nie wiąże się to z krytycznymi problemami.

Ale są sytuacje, gdy przewidywanie losowych liczb jest znacznie bardziej krytyczne. Na przykład podczas tworzenia kluczy bezpieczeństwa.

Jeśli atakujący odkryje początkową wartość używaną do tworzenia kluczy RSA w certyfikatach TLS, mógłby potencjalnie odszyfrować ruch sieciowy. Oznacza to, że może uzyskać hasła i inne osobiste informacje wysyłane przez Internet.

W tych sytuacjach potrzebny jest bardziej bezpieczny sposób uzyskiwania losowych liczb, czyli prawdziwy generator liczb losowych.

Generator Google'a

Google posiada własne narzędzie do generowania losowych liczb oparte na JavaScript. To narzędzie może być przydatne podczas gier z przyjaciółmi i rodziną. Można znaleźć ten generator, wpisując w wyszukiwarkę Google frazę "generator liczb losowych".

Metoda Kongruentna Liniowa

Jednym z najpopularniejszych algorytmów dla pseudolosowych generatorów liczb jest Metoda Kongruentna Liniowa. Jest używana w prostych przypadkach i nie ma kryptograficznej siły. Derrick Henry Lehmer zaproponował metodę kongruentną liniową w 1949 roku.

Aby zaimplementować generowanie liczb tą metodą, musimy wybrać cztery liczby:

m > 0, modulo

0 ≤ a ≤ m, mnożnik

0 ≤ c ≤ m, przyrost

0 ≤ X₀ ≤ m, liczba początkowa

Sekwencja losowych liczb jest generowana przy użyciu wzoru:

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

Warto zauważyć, że ta metoda zależy od wyboru parametrów.

Na przykład, dla następującego zestawu:

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

otrzymujemy krótką powtarzalną sekwencję

3, 5, 1, 3, 5, 1

która nie wygląda na losową.

Ale warto zmienić parametry na coś innego:

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

I rozmieszczenie wyników staje się bardziej nieprzewidywalne. Należy starannie wybrać liczby dla tego algorytmu.

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...

Chociaż metoda kongruentna liniowa generuje statystycznie dobrą sekwencję pseudolosowych liczb, nie jest ona kryptograficznie solidna. Generatory oparte na metodzie kongruentnej liniowej są przewidywalne, więc nie można ich używać w kryptografii.

Generatory oparte na metodzie kongruentnej liniowej zostały po raz pierwszy złamane przez Jima Reedsa w 1977 roku, a następnie przez Joan Boyar w 1982 roku. Udało jej się również złamać generatory kwadratowe i sześcienne. W ten sposób udowodnili bezużyteczność generatorów opartych na metodach kongruentnych dla kryptografii. Jednak generatory oparte na metodzie kongruentnej liniowej zachowują swoją użyteczność w zastosowaniach niekryptograficznych, na przykład w symulacjach. Są wydajne i wykazują dobre wyniki statystyczne w większości testów empirycznych.

Nowoczesne Generatory Liczb Losowych w Sprzęcie Komputerowym

QRBG121

Efekt losowości w urządzeniu zależy od kwantowego procesu fizycznego emisji fotonów w półprzewodnikach i następującej po tym detekcji poszczególnych fotonów. W tym procesie fotony są wykrywane losowo, niezależnie od siebie, a informacje o czasie wykrycia fotonów są używane do generowania bitów.

Lampy lawowe

W biurze CloudFlare w San Francisco znajdują się generatory liczb losowych zwane "lampami lawowymi". Taka lampa to szklane naczynie wypełnione przezroczystym olejem i półprzezroczystym parafinem. Parafina jest nieco cięższa niż olej, ale gdy jest lekko podgrzewana, staje się lżejsza i unosi się do góry.

Ruch cieczy jest monitorowany przez kilka kamer, które robią zdjęcia. Zdjęcia są przekształcane w liczby, z których następnie generowane są klucze szyfrujące.

Pozostałe dwa biura CloudFlare korzystają z innych metod uzyskiwania losowych wartości. W Londynie kamera rejestruje ruchy trzech chaotycznych wahadeł. W Singapurze używany jest licznik Geigera mierzący rozpad promieniotwórczy małego kawałka uranu. W tym ostatnim przypadku uran jest używany jako "źródło danych", ponieważ promieniowanie radioaktywne charakteryzuje się losowością każdego aktu rozpadu.

HotBits

HotBits to strona, która udostępnia prawdziwe liczby losowe generowane przez licznik Geigera, który rejestruje promieniowanie jonizujące. Wypełniasz formularz na stronie, określając liczbę losowych bajtów i wybierasz preferowaną metodę uzyskania danych. Gdy liczby losowe są dostarczone klientowi, są natychmiast usuwane z systemu.

Kwantowe Fluktuacje Próżni

Wbrew swojej nazwie ("vacuus"-pusty), próżni nie można uznać za pustą. Zgodnie z zasadą nieoznaczoności Heisenberga, wirtualne cząstki nieustannie powstają i umierają.

Kanadyjscy fizycy zaprojektowali szybki i konstrukcyjnie prosty generator liczb losowych oparty na fluktuacjach próżni. Generator składa się z impulsowego lasera o wysokiej częstotliwości promieniowania, medium o wysokim współczynniku załamania (diament) i detektora. Przechodząc przez diament, każdy impuls na czujniku wykazuje różne cechy w zależności od napotkanych fluktuacji pola próżni na ścieżce fotonów.

W widmie rozproszonego promieniowania pojawiają się linie spektralne. Ze względu na nieprzewidywalność fluktuacji próżni, te linie różnią się w nieprzewidywalny sposób za każdym razem.

Generator z Nanorurek Węglowych

Ta metoda łączy kompaktowość z generowanym szumem termicznym.

Naukowcy zbudowali generator liczb losowych z komórki pamięci statycznej dostępu losowego, wydrukowanej specjalnymi tuszami zawierającymi półprzewodnikowe nanorurki węglowe. Komórka pamięci wykorzystuje fluktuacje szumu termicznego do generowania losowych bitów.

Generator z nanorurek węglowych może być drukowany na elastycznych podłożach plastikowych, co pozwala na jego integrację z miniaturowymi, elastycznymi urządzeniami elektronicznymi, noszonymi sensorami, jednorazowymi etykietami i inteligentną odzieżą.

Kostki do gry i Fundacja Electronic Frontier (EFF)

Firma zaproponowała prosty sposób na tworzenie bezpiecznych haseł, korzystając z fizycznego generatora liczb losowych. Opiera się on na kostkach do gry.

Na przykład, rzucasz pięcioma kostkami jednocześnie i zapisujesz uzyskane numery. Kostki układasz od lewej do prawej w następującej kolejności: 63131. Następnie otwierasz długą listę słów na stronie EFF, aby znaleźć odpowiadające słowo obok 63131. Tym słowem jest "turbofan".

Możesz powtórzyć tę procedurę kilka razy. Na przykład pięć razy. Możesz skończyć z frazą składającą się z pięciu słów. Powiedzmy, "turbofan purge unfitting try pruning" (turbofan wyrzucić niepasujące próbować przycinać). Jeśli wiesz, jak używać zasad mnemotechniki, możesz zapamiętać takie frazy.

Kwantowy Generator Liczb Losowych z Smartfona Nokia

W 2014 roku Uniwersytet Genewski stworzył urządzenie QRNG, które wykorzystywało aparat smartfona Nokia N9.

Aparat smartfona liczył liczbę fotonów uderzających w każdy piksel. Źródłem światła była standardowa dioda LED. Każdy piksel w 8-megapikselowym aparacie wykrywał około 400 fotonów w krótkim czasie. Całkowita liczba fotonów we wszystkich pikselach była następnie przekształcana w sekwencję losowych liczb.