Räknarbaserad slumptalsgenerator (CBRNG)

En motbaserad generering av slumptal ( CBRNG , även känd som en motbaserad pseudoslumptalsgenerator, eller CBPRNG) är en slags pseudoslumptalsgenerator som endast använder en heltalsräknare som sitt interna tillstånd.

Bakgrund

Vi kan tänka på en pseudoslumptalsgenerator (PRNG) som en funktion som omvandlar en serie bitar som kallas tillståndet till ett nytt tillstånd och ett slumptal.

Det vill säga, givet en PRNG-funktion och ett initialtillstånd $\mathrm {state} _{0}$ , kan vi upprepade gånger använda PRNG för att generera en sekvens av tillstånd och slumptal.

$${\begin{aligned}\mathrm {PRNG} ( \mathrm {tillstånd} _{0})&=\mathrm {tillstånd} _{1},\ \mathrm {num} _{1}\\\mathrm {PRNG} (\mathrm {tillstånd} _{1}) &=\mathrm {tillstånd} _{2},\ \mathrm {num} _{2}\\\mathrm {PRNG} (\mathrm {tillstånd} _{2})&=\mathrm {tillstånd} _{3 },\ \mathrm {num} _{3}\\\mathrm {PRNG} (\mathrm {tillstånd} _{3})&=\ldots \end{aligned}}$$

I vissa PRNGs, som Mersenne Twister , är staten stor, mer än 2048 byte. I andra PRNGs, såsom xorshift , $\mathrm {state} _{i}$ och $\mathrm {num} _{i}$ en och samma (och så tillståndet är litet, bara 4, 8 eller 16 byte, beroende på storleken på talen som genereras). Men i båda fallen, och faktiskt i de flesta traditionella PRNG:er, utvecklas tillståndet oförutsägbart, så om du vill beräkna ett visst s t a t e ${tillstånd} _{i}}$ givet ett initialt tillstånd $\mathrm {state} _{0}$ , du måste beräkna $\mathrm {state} _{1}$ , $\mathrm {state} _{2}$ och så vidare, kör PRNG $i$ gånger.

Sådana algoritmer är i sig sekventiella och kan inte köras på parallella maskiner som flerkärniga processorer och GPU :er .

Däremot är en motbaserad slumptalsgenerator (CBRNG) en PRNG där tillståndet "utvecklas" på ett särskilt enkelt sätt: s t a t $mathrm {state} _{i}=i }$ . På så sätt kan du generera varje nummer oberoende av varandra, utan att veta resultatet av det föregående anropet till PRNG.

Den här egenskapen gör det enkelt att köra en CBRNG på flera CPU-trådar eller en GPU. Till exempel, för att generera $n$ slumptal på en GPU, kan du skapa $n$ trådar och låta den ${\displaystyle i}:$ e tråden beräkna $\ mathrm {PRNG} (i)$ .

CBRNGs baserade på blockchiffer

blockchiffer med reducerad styrka . Nedan förklarar vi hur detta fungerar.

När du använder ett kryptografiskt blockchiffer i räknarläge genererar du en serie block med slumpmässiga bitar. Det $i$ :e blocket beräknas genom att kryptera talet $i$ med krypteringsnyckeln $k$ : $\mathrm {Block} _{i}=E(i,k)$ .

Detta liknar en CBRNG, där du beräknar $i$ :e slumptalet som $\mathrm {PRNG} (i)$ . Alla blockchiffer kan faktiskt användas som en CBRNG; låt helt enkelt $\mathrm {PRNG} (i)=E(i,\mathrm {frö} )$ !

Detta ger en stark, kryptografiskt säker källa till slumpmässighet . Men kryptografiskt säkra pseudoslumptalsgeneratorer tenderar att vara långsamma jämfört med osäkra PRNG:er, och i praktiken kräver många användningar av slumptal inte denna grad av säkerhet.

2011, Salmon et al. vid DE Shaw Research introducerade två CBRNGs baserade på versioner av blockchiffer med reducerad styrka.

• Threefry använder en version med reducerad styrka av blockchifferet Threefish . (Juvenil fisk är känd som " yngel ".)

• ARS använder en version med reducerad styrka av AES- blockchifferet. ("ARS" är en ordlek på "AES", "AES" står för "avancerad krypteringsstandard" och "ARS" står för "avancerat randomiseringssystem").

ARS används i nyare versioner av Intels Math Kernel Library och får bra prestanda genom att använda instruktioner från AES-NI- instruktionsuppsättningen, som specifikt accelererar AES-kryptering.

Kod som implementerar Threefry, ARS och Philox (se nedan) är tillgänglig från författarna.

CBRNGs baserade på multiplikation

Förutom Threefry och ARS har Salmon et al. beskrev en tredje motbaserad PRNG, Philox, baserad på breda multiplikationer; t.ex. multiplicera två 32-bitars tal och producera ett 64-bitars tal, eller multiplicera två 64-bitars tal och producera ett 128-bitars tal.

Från och med 2020 är Philox populärt på CPU:er och GPU:er. På GPU: er tillhandahåller nVidias cuRAND-bibliotek och TensorFlow implementeringar av Philox. På CPU:er tillhandahåller Intels MKL en implementering.