Hogy lehet csinálni véletlenszám generátort?

[link]

Azért nem hamar ismétlődnek...

Ezt mondjuk szorozd meg a hömérséklettel meg egy timestamppel, esetleg egy másik generált véletlenszámmal.

Ami teljesen véletlenszerű, azt pszeudorandom generátornak hívják.

Vesznek valami tényezőt, például háttérsugárzás mértékének változásai, vagy a zener dióda zaját.

#2

A pszeudorandom pont az, ami valójában nem véletlenszerű. Álrandom.

Van egy oldal, a random.org, ők valós véletlen számokat generálnak pár darab, atmoszférikus zajra hangolt (szóval nem rádióadóra) rádióvevő segítségével.

Pár "csináld magad" megvalósítása a Realtek RTL2832U (RTL-SDR) segítségével:

* [link]

* [link]

De vannak más lehetőségek is:

* [link]

pár nyílt forrású megvalósítás:

* [link]

* [link]

Geiger-Müller számlálóval:

* [link]

több forrásból dolgozó kereskedelmi termék:

* [link]

#2 vagyok.

A pszeudorandom kifejezést rosszul használtam, de a többit jól írtam, ezért kár volt a szinte 0%-os lepontozás.

Akár a dióda zaja, akár a háttérsugárzás változásaiból generált szám valós.

Pedig aki ilyen szinten hülye az angolhoz, az megérdemli, hogy lepontozzák.

Amúgy is, nem a háttérsugárzás hanem általában rádióhullámú zajsugárzás, vagy kevert módusú adásjel szokott az alapja lenni efféle random generátoroknak.

Ezek valódi véletlenszámokat képesek szolgáltatni.

Előző:

Igen, az Internet-en is nagy haszna van ennek.

Itt a cikk, amely ismerteti:

[link]

Sok féle véletlenszám generátor van, de alapvetően két fele csoportosítható:

Egyik esetben van egy kezdeti seed érték melyet inicializálnak timestamp alapján vagy más alapján,( vagy pedig direktbe megadják a generátor belső állapotát). A generátor kezdetén megadott seed érték avagy a kezdeti belső állapota meghatározza az összes számot amit generáltatnak vele.

Amit első hozzászóló írt az a Mersenne Twister MT19937 pszeudorandom generátor algoritmus, igen hosszú periódushosszal.

"Ezt mondjuk szorozd meg a hömérséklettel meg egy timestamppel, esetleg egy másik generált véletlenszámmal."

Jó eséllyel nem lesz attól jobb, ha hasraütésre szorozgatjuk. Egyébként ennél a pythonos randomgenerátor implementációjánál a MT19937 ismétlési periódushosszal összemérhető kezdeti seed értékkel inicializája, ha nem rendelkezünk máshogy. A seed értéket pedig az operációs rendszer általi randomgenerátorból veszi, ami kriptográfia random, cpu hőmérséglet, felhasználói interakciók (egérkattintások,billetyűzetleütés) stb.-ből veszi az oprendszer.

Persze amit említettem a két eset keveréke is lehet. Azaz ha nem elég olyan jön külső forrásból, mint ahogy fogasszuk, akkor azzal számol tovább, de ha menet közben termelődik a külső forrásból akkor belekeveri.

A másik esetben pedig lényegében ugyanaz mint az első esetben, csak folyamatosan újra kell táplálni a random generátort külső forrásból, így nem a csak a kezdeti seed értékétől, állapotától függ.

Biztonsági szempontból az a jó, ha a külső forrás előre nem számítható / jósolható. Pontosabban legyen ilyen tulajdonsága, hogy pontosan ne legyen előre meghatározható. Az hogy hány bitet sajtol ki belőle a generátor optimális az lenne, ha pont annyit mint a bemenet Kolmogorov-komplexitása. Azaz annyi amennyi a lehető legjobb tömörítéssel vesztességmentesen elérhető lenne, ez azonban (általában) nem számítható függvény, csak becsülni tudjuk.

"Ami mindig véletlen számokat ad ki, valójában is, tehát független a számítógép számolásától."

Valahogy bitekké kell gyúrni, amit említettem második eset ez, persze vannak erre célhardverek is. Akár ha egy kvantummechanikán alapuló célhardver is van, ha az input adatok bitekre leképezésénél nem érték el a maximális entrópiát, akkor ezt is át kell dolgozni, persze ezt tudja már maga a célhardver.

A feltétel az többek között, hogy a leképezőfüggvénynek teljesíteni kell a lavina effektust. Azaz ha elindítjuk a generátort két gépen és ha csak 1 bit eltérés van az inputban akkor a leképezőfüggény egyes bitjei 50% valószínűséggel fognak egyezni. Ennél jobb nem is lehet, hiszen ha több mint 50% valószínűséggel egyezne akkor rosszabb, mert az egyik ismeretében a negáltjának a bitjeit találnák el jobban, ha 50% alatt van akkor meg a sorozat bitjeit.

No meg minden féle statisztikiai teszteken át kell mennie a leképezőfüggvénynek, meg minden féle próbákon. Ne is menjünk bele, használjuk például az SHA3-256 kiriptográfiai hasító függvényt hozzá, ezt már csomó matematikus professzor tudós, informatikus, programozó, bizotság stb. megvizsgált, átment csomó teszten.

Az input forrásnak a jellegét ismerni kell, erre kell a megfelelő vesztességmentes tömörítés. Például ha az input egy mikrofonból érkező jel ami a bementet egy hangforrásból kapja akkor a jeled komplexitásának elég jó mérőszáma az audió tömöríthetőségi rátája, aminek az optimalizálásába bőven elég mérnök-órát ölt már az emberiség. Fogod a jeledet, átküldöd FLAC-on tömörítve a kimenet méretéből kivonsz egy overhead konstanst (megnézed, hogy egy ismert alacsony entrópiájú jelre, pl tiszta szinuszhullámra mekkora outputot produkál, hogy az output blokkok inputfüggetlen fix részét ne számold és ne tekintsd entrópiának, csak az afeletti tartalmat) és elosztod mondjuk még 4-el. Ha a mikrofonodon nem jön érdemi jel, csak hálózati zümmögés, akkor a tömörítés-kivonás-osztás után nulla közeli értéket kapsz, és tudod, hogy a generátorodat arányosan be kell lassítanod. Ehhez jön még az említett SHA3-256. Ezt pedig úgy alkalmazod, hogy adott blokméretenként számolod hozzá az SHA3-256-ot, az SHA3-256 belső állapotát elejétől fogva megtartva mindvégig. Az SHA3-256 által kapott kimenet lesz a random generátorod kimenete.

Ha más bemeneti jelforrást alkalmazol akkor annak megfelelően a bemenet jellegére szabott tömörítéssel előtte szintén tömöríted, majd belső állapot megtartással és megfelelő blokkméretenként SHA3-256-ot számolsz ami lesz a random generátorod kimenete.

Persze nem kötelező a SHA3-256, lehet másik SHA3 is, meg nem kötelező SHA3, de ez egy jó hasító függvény (illetve ha SHA3 akkor hasító függvény család) erre a célra.