Generator liczb losowych oparty na licznikach (CBRNG)

Generowanie liczb losowych opartych na licznikach ( CBRNG , znane również jako generator liczb pseudolosowych oparty na licznikach lub CBPRNG) jest rodzajem generatora liczb pseudolosowych , który jako stan wewnętrzny wykorzystuje tylko licznik całkowity.

Tło

Możemy myśleć o generatorze liczb pseudolosowych (PRNG) jako o funkcji, która przekształca serię bitów zwaną stanem w nowy stan i liczbę losową.

$Oznacza to,$ funkcję PRNG i stan początkowy wielokrotnie używać PRNG do generowania sekwencji stanów i liczb losowych.

{\ Displaystyle {\ rozpocząć {wyrównane} \ operatorname {PRNG} ( \mathrm {stan} _{0})&=\mathrm {stan} _{1},\ \mathrm {liczba} _{1}\\\mathrm {PRNG} (\mathrm {stan} _{1}) &=\mathrm {stan} _{2},\ \mathrm {liczba} _{2}\\\mathrm {PRNG} (\mathrm {stan} _{2})&=\mathrm {stan} _{3 },\ \mathrm {liczba} _{3}\\\mathrm {PRNG} (\mathrm {stan} _{3})&=\ldots \end{wyrównane}}}

W niektórych PRNG, takich jak Mersenne Twister , stan jest duży, ponad 2048 bajtów. W innych $\ Displaystyle \ operatorname$ $_ {i}}$ takich jak , i u są jednym i tym samym (więc stan jest mały, tylko 4, 8 lub 16 bajtów, w zależności od wielkości generowanych liczb). Ale w obu przypadkach, a nawet w większości tradycyjnych PRNG, stan ewoluuje w nieprzewidywalny sposób, więc jeśli chcesz obliczyć konkretny stan, $} _ {i}}$ dany stan początkowy, ${\ Displaystyle \ operatorname {stan} _ {0}}$ , musisz obliczyć $\ operatorname {stan} _ {1}}$ , ${\ Displaystyle \mathrm {state} _ {2}}$ i tak dalej, uruchamiając PRNG ${\ displaystyle i}$ razy.

Takie algorytmy są z natury sekwencyjne i nie nadają się do uruchamiania na maszynach równoległych, takich jak wielordzeniowe procesory i karty graficzne .

Natomiast generator liczb losowych oparty na licznikach (CBRNG) to PRNG, w którym stan „ewoluuje” w szczególnie prosty sposób: $stan} _ {i} = i }$ . W ten sposób możesz wygenerować każdy numer niezależnie, nie znając wyniku poprzedniego połączenia z PRNG.

Ta właściwość ułatwia uruchamianie CBRNG na wielu wątkach procesora lub GPU. ${\ displaystyle$ , aby wygenerować $losowe$ $na GPU$ możesz odrodzić poprosić ten obliczenie $}$ .

Implementacje

CBRNG oparte na szyfrach blokowych

szyfrów blokowych o zmniejszonej sile . Poniżej wyjaśniamy, jak to działa.

Używając kryptograficznego szyfru blokowego w trybie licznika , generujesz serię bloków losowych bitów. ja $displaystyle \ operatorname {Blok} _{i}=E(i,k)}$ $\ displaystyle i}$ th blok jest obliczany przez zaszyfrowanie liczby przy użyciu klucza szyfrującego $:$ ${\ displaystyle k}$ b .

${\ Displaystyle \ operatorname {PRNG} (i)}$ do CBRNG, w którym obliczasz $sol$ losową jako . . Rzeczywiście, każdy szyfr blokowy może być użyty jako CBRNG; ${\ Displaystyle \ operatorname {PRNG} (i) = E (i, \ operatorname {ziarno})$ sol !

Daje to silne, kryptograficznie bezpieczne źródło losowości . Ale kryptograficznie bezpieczne generatory liczb pseudolosowych są zwykle powolne w porównaniu z niezabezpieczonymi PRNG, aw praktyce wiele zastosowań liczb losowych nie wymaga takiego stopnia bezpieczeństwa.

W 2011 roku Łosoś i in. w DE Shaw Research wprowadził dwa CBRNG oparte na wersjach szyfrów blokowych o zmniejszonej sile.

Threefry używa wersji szyfru blokowego Threefish o zmniejszonej sile . (Młode ryby są znane jako „ narybek ”).

ARS używa wersji szyfru blokowego AES o zmniejszonej sile . („ARS” to gra słów „AES”; „AES” oznacza „zaawansowany standard szyfrowania”, a „ARS” oznacza „zaawansowany system randomizacji”).

ARS jest używany w najnowszych wersjach Intel Math Kernel Library i uzyskuje dobrą wydajność dzięki wykorzystaniu instrukcji z zestawu instrukcji AES-NI , które w szczególności przyspieszają szyfrowanie AES.

Kod implementujący Threefry, ARS i Philox (patrz poniżej) jest dostępny u autorów.

CBRNG oparte na mnożeniu

Oprócz Threefry i ARS, Salmon i in. opisał trzeci PRNG oparty na licznikach, Philox, oparty na szerokich mnożnikach; np. pomnożenie dwóch liczb 32-bitowych i utworzenie liczby 64-bitowej lub pomnożenie dwóch liczb 64-bitowych i utworzenie liczby 128-bitowej.

Od 2020 roku Philox jest popularny w procesorach i procesorach graficznych. Na procesorach graficznych nVidia cuRAND i TensorFlow zapewniają implementacje Philox. Na procesorach MKL firmy Intel zapewnia implementację.