Mi az a véletlenszám-generátor?
A véletlenszám-generátor (RNG) olyan rendszer, amely véletlen vagy pszeudovéletlen számokat állít elő. Hogy a következő szám ténylegesen megjósolható-e, az a generátor típusától függ. Egyes generátorok fizikai folyamatokra támaszkodnak, mások algoritmussal számolják ki az értékeket, és léteznek olyan algoritmusok is, amelyeket úgy terveztek, hogy még a korábbi eredmények ismeretében se lehessen megjósolni a következő értéket. A véletlenszerűnek tűnő és a valóban kiszámíthatatlan működés két eltérő tulajdonság, és ez a cikk javarészt éppen erről a különbségről szól.
Hardveres véletlenszám-generátorok
A hardveres véletlenszám-generátor (HRNG), amelyet valódi véletlenszám-generátornak (TRNG) is neveznek, valamilyen fizikai folyamatból nyeri az értékeit. A legrégebbi ilyen eszközök a szemünk előtt működnek: a feldobott érme, az elgurított dobókocka vagy a rulettkerék. A mechanika törvényei mindegyiket tökéletesen leírják, egy jól megépített rulettkerék a gyakorlatban mégis kiszámíthatatlan, mivel a pörgetés kezdetének apró eltérései teljesen eltérő kimenetelekhez vezetnek.
A modern hardveres generátorok ehelyett mikroszkopikus jelenségeket mérnek: sörétzajt és termikus zajt az elektronikus áramkörökben, légköri zajt vagy kvantumhatásokat. Ezek kiváló forrásai az entrópiának — vagyis a mérhető kiszámíthatatlanságnak —, de egy fizikai forrás természeténél fogva nem tökéletes: részrehajlóvá válhat, idővel eltolódhat és meghibásodhat. Ezért minőségét folyamatosan értékelni és felügyelni kell, szükség esetén pedig a kapott értékeket tovább kell feldolgozni, ahogyan azt a NIST SP 800-90B szabvány is leírja. A hardveres forrásokat ott használják, ahol a megbízhatósági garancia a legfontosabb — mindenekelőtt a kriptográfiában, ahol a Transport Layer Security (TLS) és hasonló protokollok kulcsaihoz biztosítják a kiszámíthatatlan alapanyagot.
Pszeudovéletlen-szám generátorok
A fizikai eszköz alternatívája az algoritmus. A pszeudovéletlen-szám generátor (PRNG) olyan számsort hoz létre, amely véletlenszerűnek tűnik, de valójában teljes mértékben egy kezdőérték, az úgynevezett mag (seed) határozza meg. Ha ugyanazt a magot adjuk ugyanannak az algoritmusnak, minden alkalommal pontosan ugyanazt a számsort kapjuk. Ez hátrány minden olyan helyzetben, ahol az eredménynek kiszámíthatatlannak kell lennie, és a mag vagy a belső állapot kitalálható vagy rekonstruálható; ugyanakkor hatalmas előny ott, ahol a megismételhetőség a cél — egy szimuláció vagy teszt így hajszálpontosan újrafuttatható. A PRNG-k emellett gyorsak, olcsók és könnyen megvalósíthatók, ezért a legtöbb szoftver ezekre épül. A legismertebb algoritmusok közé tartozik a lineáris kongruenciagenerátor (LCG), a xorshift generátorok és a Mersenne Twister.
Mersenne Twister
A Makoto Matsumoto és Takuji Nishimura által 1997-ben közzétett Mersenne Twister az egyik legszélesebb körben használt pszeudovéletlen-generátor, és számos programozási nyelvben ez az alapértelmezett megoldás. Nevét a periódusáról — a számsor ismétlődés előtti hosszáról — kapta, amely a standard változatban, az MT19937-ben a 219937 − 1 Mersenne-prím. A legtöbb statisztikai véletlenségi teszten kiválóan megfelel, így szimulációkhoz kifejezetten alkalmas. Titkok megőrzésére azonban nem tervezték: 624 egymást követő 32 bites értékből bárki képes rekonstruálni a belső állapotát és megjósolni minden rákövetkező számot, ezért kulcsokhoz, jelszavakhoz vagy bármi máshoz, aminek kiszámíthatatlannak kell maradnia, tilos használni.
Kriptográfiailag biztonságos generátorok és entrópia
Számos alkalmazás egyszerre igényli mindkettőt: az algoritmusok sebességét és a fizikai források kiszámíthatatlanságát. A megoldás a kriptográfiailag biztonságos pszeudovéletlen-szám generátor (CSPRNG). Ez valójában szintén egy PRNG, de úgy van felépítve, hogy az előállított értékek egy részének ismeretében se lehessen gyakorlati módon megjósolni a folytatást, és a működését valódi entrópiaforrásból látják el, majd rendszeresen újra ellátják kezdőértékkel. A fizikai forrásból származó mag önmagában nem tesz biztonságossá egy hagyományos PRNG-t; az algoritmust eleve erre a feladatra kell megtervezni. Egy fizikai forrás, például a termikus zaj vagy a hardveresemények időzítése kis mennyiségű valódi véletlenszerűséget biztosít, a CSPRNG pedig ebből sokkal gyorsabban hosszú értéksort állít elő. Ezt a kombinációt biztosítja az operációs rendszer a rajta futó programoknak, és a gyakorlatban ma a „véletlenszám-generátor” kifejezés szinte mindig ezt jelenti. Ez hozza létre a titkosítási kulcsokat, a munkamenet-azonosítókat és a jelszavakat.
Véletlen számok a böngészőben
A JavaScript két beépített módszert kínál egy weboldalnak a véletlen értékek kérésére, és ezek két teljesen eltérő kategóriába tartoznak. A Math.random() egy közönséges PRNG: a nyelvi szabvány az algoritmus megválasztását a böngészőkre bízza, és semmiféle biztonsági garanciát nem nyújt — egy animációhoz tökéletes, de alkalmatlan egy olyan sorsoláshoz, amelynek tisztaságát valaki kétségbe vonhatja. A másik lehetőség a Web Crypto API. Ennek crypto.getRandomValues() metódusa kriptográfiailag biztonságos véletlen értékeket ad vissza, amelyeket az operációs rendszer entrópiájával inicializált CSPRNG állít elő.
A mi online véletlenszám-generátorunk a Web Crypto API-t használja minden egyes sorsoláshoz, és a számok a böngésződben készülnek el, nem pedig egy szerveren. Ugyanez a megbízható forrás vezérli az oldal többi eszközét is, akár dobókockával dobsz, pénzt dobsz fel, akár jelszót generálsz.
A véletlen bitektől a kívánt tartománybeli számig
A kriptográfiailag biztonságos generátor önmagában még csak a fele egy tisztességes sorsolásnak. Nyers biteket szolgáltat, és a programnak ezeket még át kell alakítania a megadott tartományba eső számmá — és ezen a ponton könnyen torzítás csúszhat a folyamatba. Tegyük fel, hogy a forrás a 0 és 9 közötti értékeket egyenlő eséllyel adja, és neked egy 0 és 5 közötti számra van szükséged. A 6-tal való osztás maradékának vétele magától értetődőnek tűnhet, de ekkor a 0, 1, 2 és 3 egyenként kétféleképpen jöhet ki, míg a 4 és az 5 csak egyféleképpen. Így a 0 és 3 közötti számok mindegyikének 20% esélye lesz, míg a 4-nek és az 5-nek csupán 10-10%. A torzítás kiküszöbölésének egyik bevált módja a nem illeszkedő értékek elvetése és az újrasorsolás; a véletlenszám-generátoros anyagok részletesen bemutatják ezt a logikát.
Két további dolog gyakran meglepi az embereket. Az ismétlődések teljesen természetesek: ha 1 és 10 között sorsolunk ki egy egész számot függetlenül és minden szám azonos valószínűséggel bír, a frissen kihúzott számnak pontosan ugyanúgy tízből egy az esélye az újbóli felbukkanásra, mint bármelyik másiknak. Az ismétlés nélküli sorsolás egy másfajta sorsolási eljárás, nem pedig véletlenszerűbb. Ráadásul a korrekt generátor önmagában még nem garantálja az egész folyamat korrektségét: a résztvevők listája és a próbálkozások száma legalább annyira számít, amint azt a nyertesek véletlenszerű kiválasztásáról szóló cikkünk is részletezi.