A pszeudovéletlen szám egy speciális generátor által generált speciális szám. A Determinisztikus Véletlen Bit Generátor (PRNG), más néven Determinisztikus Véletlen Bit Generátor (DRBG), egy olyan számsorozat generálására szolgáló algoritmus, amelynek tulajdonságai megközelítik a véletlenszám-sorozatok jellemzőit. A generált PRNG-szekvencia nem igazán véletlenszerű, mivel teljes egészében egy PRNG-magnak nevezett magérték határozza meg, amely valóban véletlenszerű értékeket is tartalmazhat. Bár a véletlenszerűséghez közelebb álló sorozatok generálhatók hardveres véletlenszám-generátorokkal, az álvé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 töltenek be az olyan alkalmazásokban, mint a szimuláció (pl. Monte Carlo esetében), az elektronikus játékok (pl. az eljárási generáláshoz) és a kriptográfia. A kriptográfiai alkalmazások megkövetelik a kimenetetaz adatok nem voltak előre láthatók a korábbi információk alapján. Bonyolultabb algoritmusokra van szükség, amelyek nem öröklik az egyszerű PRNG-k linearitását.
Általános Szerződési Feltételek
A jó statisztikai tulajdonságok központi feltétele a PRNG megszerzésének. Általánosságban elmondható, hogy gondos matematikai elemzésre van szükség, hogy megbizonyosodjunk arról, hogy az RNG olyan számokat generál, amelyek elég közel állnak a véletlenszerűséghez ahhoz, hogy megfeleljenek a tervezett felhasználásnak.
John von Neumann óva intett attól, hogy a PRNG-t valóban véletlenszerű generátorként értelmezzék, és azzal viccelődött, hogy "Bárki, aki számtani módszereket fontolgat véletlenszámok generálására, minden bizonnyal bűnben van."
Használja
PRNG tetszőleges kezdeti állapotból indítható. Mindig ugyanazt a sorozatot generálja, amikor ezzel az állapottal inicializálja. A PRNG periódus a következőképpen definiálható: maximum a nem ismétlődő sorozat előtag hosszának minden kezdeti állapotában. Az időszakot az állapotok száma korlátozza, általában bitekben mérve. Mivel a periódus hossza potenciálisan megduplázódik minden egyes hozzáadott "állapot" bittel, könnyű létrehozni PRNG-ket sok gyakorlati alkalmazáshoz elég nagy periódusokkal.
Ha a PRNG belső állapota n bitet tartalmaz, a periódusa nem lehet több 2n eredménynél, ez sokkal rövidebb. Egyes PRNG-k esetében az időtartam a teljes időszak megkerülése nélkül is kiszámítható. A lineáris visszacsatolási eltolási regiszterek (LFSR) jellemzőenúgy vannak megválasztva, hogy periódusuk 2n − 1 legyen.
A lineáris kongruenciális generátoroknak vannak periódusai, amelyeket faktoring segítségével lehet kiszámítani. Bár a PPP megismétli eredményeit, miután azok elérik a periódus végét, az ismételt eredmény nem jelenti azt, hogy az időszak végét elérték, mivel a belső állapota nagyobb lehet, mint a kimenet; ez különösen nyilvánvaló az egybites kimenetű PRNG-k esetében.
Lehetséges hibák
A hibás PRNG-k által talált hibák a finom (és ismeretlen) a nyilvánvaló hibákig terjednek. Példa erre a RANDU véletlenszám-algoritmus, amelyet évtizedek óta használnak nagyszámítógépeken. Komoly hiányosság volt, de elégtelenségét sokáig nem vették észre.
Sok területen a véletlenszerű szelekciót, Monte Carlo-szimulációkat vagy más, RNG-n alapuló módszereket alkalmazó kutatások sokkal kevésbé megbízhatóak, mint a rossz minőségű GNPG eredménye. Még ma is óvatosságra van szükség, amint azt a Nemzetközi Statisztikai Enciklopédia (2010) figyelmeztetése is bizonyítja.
Sikeres esettanulmány
Például nézze meg a széles körben használt Java programozási nyelvet. 2017-ben a Java továbbra is a lineáris kongruenciális generátorra (LCG) támaszkodik a PRNG-hez.
Előzmények
Az első PRNG, amely elkerüli a komoly problémákat, és még mindig elég gyorsan fut,a Mersenne Twister volt (lásd alább), amely 1998-ban jelent meg. Azóta más kiváló minőségű PRNG-ket fejlesztettek ki.
A pszeudo-véletlen számok története azonban ezzel nem ér véget. A 20. század második felében a PRNG-ekhez használt standard algoritmusok közé a lineáris kongruenciális generátorok tartoztak. Az LCG minőségéről ismert volt, hogy nem megfelelő, de jobb módszerek nem álltak rendelkezésre. Press és mtsai (2007) a következőképpen írták le az eredményt: "Ha minden olyan tudományos közlemény, amelynek eredményei kétségesek [LCG-k és kapcsolódó] miatt, eltűnnének a könyvtárak polcairól, akkor minden polcon egy ökölnyi rés lenne."
A pszeudo-véletlen generátorok létrehozásának fő eredménye a lineáris rekurencián alapuló módszerek bevezetése volt egy kételemes mezőben; az ilyen oszcillátorok lineáris visszacsatolásos eltolási regiszterekhez vannak kapcsolva. Ezek szolgáltak alapul az álvéletlenszám-érzékelők feltalálásához.
Különösen a Mersen Twister 1997-es találmánya elkerülte a korábbi generátorokkal kapcsolatos számos problémát. A Mersenne Twister periódusa 219937–1 iteráció (≈4,3 × 106001). Bebizonyosodott, hogy egyenletesen oszlik el (legfeljebb) 623 dimenzióban (32 bites értékek esetén), és bevezetése idején gyorsabb volt, mint más, pszeudo-véletlen számsorozatokat előállító statisztikailag megbízható generátorok.
2003-ban George Marsaglia bemutatta a szintén lineáris ismétlésen alapuló xorshift generátor családot. Ezek a generátorok rendkívülgyorsak és – nemlineáris művelettel kombinálva – szigorú statisztikai teszteken mennek keresztül.
2006-ban fejlesztették ki a WELL generátorcsaládot. A WELL generátorok bizonyos értelemben javítják a Twister Mersenne minőségét, amelynek túlságosan nagy az állapottere és nagyon lassú a helyreállításuk, sok nullával álvéletlen számokat generálva.
Rejtjelezés
A kriptográfiai alkalmazásokhoz alkalmas PRNG-t kriptográfiailag biztonságos PRNG-nek (CSPRNG) nevezik. A CSPRNG követelménye, hogy egy támadó, aki nem ismeri a magot, csak csekély előnnyel rendelkezik a generátor kimeneti sorozatának a véletlen sorozattól való megkülönböztetésében. Más szavakkal, míg a PRNG-nek csak bizonyos statisztikai teszteken kell megfelelnie, a CSPRNG-nek minden olyan statisztikai teszten át kell mennie, amelyek polinomiális időre korlátozódnak magméretben.
Bár ennek a tulajdonságnak a bizonyítása meghaladja a számítási komplexitáselmélet jelenlegi szintjét, erős bizonyítékok szolgálhatnak a CSPRNG olyan nehéznek tartott problémára való redukálásával, mint például az egész számok faktorizálása. Általánosságban elmondható, hogy az algoritmus CSPRNG-tanúsításához évekig tartó felülvizsgálatra lehet szükség.
Bebizonyosodott, hogy valószínű, hogy az NSA aszimmetrikus hátsó ajtót helyezett be a NIST-tanúsítvánnyal rendelkező Dual_EC_DRBG pszeudo-véletlenszám-generátorba.
Álvéletlen algoritmusokszámok
A legtöbb PRNG-algoritmus olyan sorozatokat hoz létre, amelyek egyenletes eloszlásúak több teszt bármelyikével. Ez egy nyitott kérdés. Ez az egyik központi elem a kriptográfia elméletében és gyakorlatában: van-e mód a kiváló minőségű PRNG kimenetének megkülönböztetésére egy valóban véletlenszerű sorozattól? Ebben a beállításban a feloldó tudja, hogy vagy egy ismert PRNG-algoritmust használtak (de nem azt az állapotot, amellyel inicializálták), vagy egy valóban véletlenszerű algoritmust használtak. Különbséget kell tennie köztük.
A legtöbb PRNG-t használó kriptográfiai algoritmus és protokoll biztonsága azon a feltételezésen alapul, hogy lehetetlen különbséget tenni egy megfelelő PRNG és egy valóban véletlenszerű sorozat használata között. Ennek a függőségnek a legegyszerűbb példái a stream titkosítások, amelyek leggyakrabban úgy működnek, hogy kihagyják vagy elküldik az egyszerű szöveges üzenetet PRNG kimenettel, létrehozva a titkosított szöveget. A kriptográfiailag megfelelő PRNG-k tervezése rendkívül nehéz, mivel további kritériumoknak kell megfelelniük. A periódus mérete fontos tényező a PRNG kriptográfiai alkalmasságában, de nem az egyetlen.
Egy korai számítógépes PRNG, amelyet Neumann János javasolt 1946-ban, az átlagos négyzetek módszereként ismert. Az algoritmus a következő: vegyünk tetszőleges számot, négyzetezzük, a kapott szám középső számjegyeit távolítsuk el „véletlen számként”, majd ezt a számot használjuk kezdő számként a következő iterációhoz. Például az 1111 szám négyzetre emelése azt eredményezi1234321, amely 01234321-ként írható fel, egy 8 jegyű szám egy 4 jegyű szám négyzete. Ez a 2343-at adja "véletlen" számnak. Az eljárás megismétlésének eredménye 4896 és így tovább. Von Neumann 10 jegyű számokat használt, de a folyamat ugyanaz.
A "középső négyzet" hátrányai
Az "átlagnégyzet" módszerrel az a probléma, hogy végül minden sorozat ismétlődik, némelyik nagyon gyorsan, például: 0000. Von Neumann tudott erről, de talált egy megközelítést, amely elegendő a céljaihoz, és aggódott amiatt, hogy a matematikai "javítások" csak elrejtik a hibákat, ahelyett, hogy eltávolítanák őket.
Von Neumann alkalmatlannak találta a hardveres véletlen- és pszeudovéletlenszám-generátorokat: ha nem rögzítik a generált kimenetet, később nem lehet ellenőrizni, hogy vannak-e hibák. Ha leírnák eredményeiket, kimerítenék a számítógép korlátozott szabad memóriáját, és így 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 írni és olvasni. Az általa használt ENIAC számítógépen a "középső négyzet" módszert alkalmazta, és több százszor gyorsabban hajtott végre pszeudovéletlen számokat, mint a lyukkártyákról leolvasott számokat.
Az átlagos négyzetet azóta összetettebb generátorok váltották fel.
Innovatív módszer
A közelmúltban megjelent újítás az átlagos négyzet és a Weil sorozat kombinálása. Ez a módszer biztosítja a termékek kiváló minőségéthosszú időszak. Segít megtalálni a legjobb pszeudo-véletlen számképleteket.
