Pszeudorandom szám: a megszerzés módszerei, előnyei és hátrányai

A pszeudorandom szám egy speciális generátor által létrehozott speciális számjegy. Az ilyen számok generátora (PRNG), más néven a determinisztikus véletlen bitgenerátor (DRBG), egy algoritmus olyan számsorozat létrehozására, amelynek tulajdonságai megközelítik a véletlen számok szekvenciáinak jellemzőit. A PRNG által generált szekvencia nem igazán véletlenszerű, mivel teljesen meghatározza a kezdeti érték, amelyet a PRNG kezdeti számának neveznek, amely valóban véletlenszerű értékeket tartalmazhat. Bár a véletlenszerűhez közelebb álló szekvenciák hardveres véletlenszám-generátorokkal hozhatók létre, az ál-véletlenszám-generátorok a gyakorlatban fontosak a számgenerálás sebessége és reprodukálhatósága szempontjából.

Alkalmazás

A PRNG-k központi szerepet játszanak az olyan alkalmazásokban, mint a modellezés (például a Monte Carlo-módszer esetében), az elektronikus játékok (például az eljárási generáláshoz) és a kriptográfia. A kriptográfiai alkalmazások megkövetelik, hogy a kimenet ne legyen kiszámítható a korábbi információkból. Bonyolultabb algoritmusokra van szükség, amelyek nem öröklik az egyszerű PRNG-k linearitását.

Követelmények és feltételek

A jó statisztikai tulajdonságok központi követelmény a PRNG megszerzéséhez. Általában alapos matematikai elemzésre van szükség annak biztosításához, hogy az RNG olyan számokat generáljon, amelyek elég közel vannak a véletlenszerűhez, hogy megfeleljenek a rendeltetésszerű használatnak.

Neumann János figyelmeztetett a PRNG téves értelmezésére, mint valódi véletlengenerátorra, és viccelődött, hogy " bárki, aki számtani módszereket fontolgat a véletlenszerű számjegyek megszerzésére, természetesen bűn állapotban van.".

Használata

A PRNG tetszőleges kezdeti állapotból indítható. Mindig ugyanazt a szekvenciát generálja, ha ezzel az állapottal inicializálják. A PRNG periódust a következőképpen határozzuk meg: a szekvencia nem ismétlődő előtagjának hossza minden kezdeti állapotának maximuma. Az időszakot az állapotok száma korlátozza, általában bitekben mérve. Mivel az időszak hossza potenciálisan megduplázódik az egyes hozzáadott "állapot" bitekkel, könnyű olyan PRNG-ket létrehozni, amelyek periódusai elég nagyok sok gyakorlati alkalmazáshoz.

Ha a PRNG belső állapota n bitet tartalmaz, periódusa nem lehet több, mint 2n eredmény, sokkal rövidebb. Egyes PRNG-k esetében az időtartam kiszámítható anélkül, hogy áthaladna a teljes időszakon. A lineáris visszacsatolási eltolódási regisztereket (lfsr) általában úgy választják meg, hogy periódusaik egyenlőek legyenek 2n − 1.

A lineáris kongruens generátoroknak vannak periódusai, amelyeket faktoring segítségével lehet kiszámítani. Bár az RNG-K megismétlik eredményeiket, miután elérték az időszak végét, az ismételt eredmény nem jelenti azt, hogy elérték az időszak végét, mivel belső állapota nagyobb lehet, mint a kimenet; ez különösen nyilvánvaló egy egybites kimenettel rendelkező PRNG esetében.

Lehetséges hibák

A hibás PRNG-k által észlelt hibák az észrevétlentől (és ismeretlentől) a nyilvánvalóig terjednek. Példa erre a RANDU véletlenszám-algoritmus, amelyet évtizedek óta használnak a nagyszámítógépeken. Ez komoly hiba volt, de elégtelensége hosszú ideig észrevétlen maradt.

Sok területen a véletlenszerű kiválasztást, a Monte Carlo szimulációt vagy a PPP-n alapuló egyéb módszereket alkalmazó kutatási munkák sokkal kevésbé megbízhatóak, mint az alacsony minőségű GNPG használatának eredményeként. Néha még ma is óvatosságra van szükség, amint azt a statisztikai tudomány nemzetközi enciklopédiájában (2010)adott figyelmeztetés is bizonyítja.

Példa a sikeres alkalmazásra

Illusztrációként vegye figyelembe a széles körben használt programozási nyelv Java. 2017-től a Java továbbra is a lineáris kongruens generátor (LCG) PRNG-jéhez.

Történelem

Az első PRNG, amely elkerülte a súlyos problémákat, és még mindig meglehetősen gyorsan működött, a Mersenne Twister volt (az alábbiakban tárgyaljuk), amelyről 1998-ban tettek közzé információkat. Azóta más kiváló minőségű PRNG-ket fejlesztettek ki.

De a pszeudorandom számok története nem korlátozódik erre. A 20. század második felében a PRNG-hez használt algoritmusok standard osztálya lineáris kongruens generátorokat tartalmazott. Ismert volt, hogy az LCG minősége nem megfelelő, de a legjobb módszerek nem álltak rendelkezésre. Press et al (2007) az eredményt a következőképpen írta le: "ha minden olyan tudományos cikk, amelynek eredményei megkérdőjelezhetők az [LCG és a kapcsolódó] miatt, eltűnnek a könyvtár polcairól, minden polcon ökölnyi rés lenne".

A pszeudorandom generátorok létrehozásának fő eredménye a lineáris visszatéréseken alapuló módszerek bevezetése volt egy kételemes mezőben; az ilyen generátorok visszacsatolással rendelkező lineáris eltolódási regiszterekhez kapcsolódnak. Szolgáltak , az alapja álvéletlenszám-érzékelők találmányai.

Különösen a Mersen Twister 1997-es találmánya elkerülte a korábbi generátorok sok problémáját. A Mersenne Twister időszaka 219937−1 iteráció (≈4.3×106001). Bizonyított, hogy egyenletesen oszlik el (legfeljebb) 623 dimenzióban (32 bites értékeknél), megvalósításának idején gyorsabban működött, mint más statisztikailag hanggenerátorok, amelyek pszeudo-véletlenszerű számsorozatokat hoznak létre.

2003-ban George Marsaglia bemutatta a xorshift generátorok családját, amely szintén lineáris ismétlésen alapul. Az ilyen generátorok rendkívül gyorsak és — nemlineáris művelettel kombinálva-szigorú statisztikai teszteken mennek keresztül.

2006-ban kifejlesztették a well generátorok családját. A jól generátorok bizonyos értelemben javítják a Twister Mersenne minőségét, amely túl nagy állapottérrel és nagyon lassú helyreállítással rendelkezik, nagyszámú nullával pszeudo-véletlen számokat generálva.

Kriptográfia

A kriptográfiai alkalmazásokhoz alkalmas PRNG-t kriptográfiailag biztonságos PRNG-nek (CSPRNG)hívják. A CSPRNG követelménye az, hogy egy támadó, aki nem ismeri a kezdeti számot, csak kis előnnyel rendelkezik a generátor kimeneti sorrendjének megkülönböztetésében a véletlen sorrendtől. Más szavakkal, míg a PRNG-nek csak bizonyos statisztikai tesztek átadásához van szüksége, a CSPRNG-nek át kell adnia az összes statisztikai tesztet, amelyet a magméret polinom ideje korlátoz.

Bár ennek a tulajdonságnak a bizonyítása meghaladja a számítási komplexitás elméletének jelenlegi szintjét, meggyőző igazolások nyújthatók azáltal, hogy a CSPRNG-t komplexnek tekintett problémára redukáljuk, mint például az egész faktorizálás. Általában, évekbe telhet a felülvizsgálat, mire egy algoritmus csprng-ként tanúsítható.

Kimutatták, hogy valószínű, hogy az NSA aszimmetrikus hátsó ajtót helyezett be a NIST által tanúsított álvéletlenszám-generátorba Dual_EC_DRBG.

Álvéletlenszám algoritmusok

A legtöbb PRNG algoritmus olyan szekvenciákat állít elő, amelyek egyenletesen oszlanak el a több teszt bármelyikével. Ez egy nyitott kérdés. Ez a kriptográfia elméletének és gyakorlatának egyik központi eleme: van-e mód arra, hogy megkülönböztessük a kiváló minőségű PRNG kimenetét egy valóban véletlenszerű szekvenciától? Ebben a beállításban a felismerő tudja, hogy vagy egy jól ismert PRNG algoritmust használtak (de nem azt az állapotot, amellyel inicializálták), vagy egy valóban véletlenszerű algoritmust használtak. Meg kell különböztetni őket.

A legtöbb PRNG-t használó kriptográfiai algoritmus és protokoll biztonsága azon a feltételezésen alapul, hogy lehetetlen megkülönböztetni a megfelelő PRNG használatát a valóban véletlen sorrend használatától. Ennek a függőségnek a legegyszerűbb példái a stream titkosítók, amelyek leggyakrabban úgy működnek, hogy kizárják vagy elküldik a sima szöveges üzenetet PRNG kimenettel, titkosított szöveget hozva létre. A kriptográfiailag megfelelő PRNG-k fejlesztése rendkívül nehéz, mivel további kritériumoknak kell megfelelniük. Időszakának mérete fontos tényező a PRNG kriptográfiai alkalmasságában, de nem az egyetlen.

Egy korai számítógépes PRNG által javasolt Neumann János 1946-ban az úgynevezett átlagos négyzetek módszer. Az algoritmus a következő: vegyen bármilyen számot, négyzetelje ki, távolítsa el a kapott szám középső számjegyeit "véletlen számként", majd használja ezt a számot a következő iteráció kezdőszámaként. Például az 1111 szám négyszögesítése 1234321-et ad, amelyet 01234321-ként lehet írni, egy 8 jegyű szám egy 4 jegyű négyzet. Ez a 2343-at "véletlenszerű" számként adja meg. Az eljárás megismétlésének eredménye 4896 stb. Von Neumann 10 jegyű számokat használt, de a folyamat ugyanaz volt.

A "középső négyzet"hátrányai

A "középső négyzet" módszer problémája az, hogy minden szekvencia végül megismétlődik, néhány nagyon gyorsan, például: 0000. Von Neumann tudott erről, de a céljainak megfelelő megközelítést talált, és attól tartott, hogy a matematikai "korrekciók" egyszerűen elrejtik a hibákat, nem pedig eltávolítják őket.

Von Neumann alkalmatlannak tartotta a hardveres véletlenszám-és álvéletlenszám-generátorokat: ha nem rögzítik a generált kimenetet, akkor később nem ellenőrizhetők hibák. Ha rögzítenék eredményeiket, kimerítenék a korlátozott rendelkezésre álló számítógépes memóriát, és ennek megfelelően a számítógép számolvasási és-írási képességét. Ha a számokat a kártyákra írnák, sokkal tovább tartana nekik írni és olvasni. Az általa használt ENIAC számítógépen a" középső négyzet " módszer több százszor gyorsabban végezte el az ál-véletlen számok megszerzésének folyamatát, mint a lyukasztott kártyákból származó számok olvasása.

Az átlagos négyzet módszert azóta bonyolultabb generátorok váltották fel.

Innovatív módszer

Egy újabb újítás a középső négyzet kombinálása a Weyl-szekvenciával. Ez a módszer hosszú ideig biztosítja a kiváló minőségű termékeket. Segít a legjobb ál-véletlenszám-képletek megszerzésében.