Véletlenszámok generálása

A legtöbb titkosítási rendszer csak akkor biztonságos, ha véletlenszerűen generált jelszavakkal, bitsorozatokkal titkosítunk. Ehhez viszont venni kell valahonnan a véletlen bitek sorozatát.

A véletlenszám generátor (RNG) egy olyan berendezés vagy szoftver, ami olyan számok sorozatát képes generálni, amiben nincsen semmilyen minta.

Egyszerű berendezés elvi leírása alapján azonban a gond ott kezdődik, hogy igen nehéz algoritmikusan a kritériumnak megfelelő számsorozatot generálni. Ha esetlegesen valami minta kerül a generátor által előállított számokba, akkor a mintát felhasználva kikövetkeztethető a generátor következő állapota, vagyis onnantól kezdve nem is véletlenszerű a számsorozat.

“Bárki, aki aritmetikai módszerekkel akar előállítani egy véletlen számot, a bűn állapotában leledzik.”
Neumann János

Véletlenszám generátorokból igen sokfajta létezik. Az olyan véletlenszám generátorokat (RNG későbbiekben), amelyek titkosítási és kriptográfiai célokra is alkalmasak, kriptográfiailag biztonságos pszeudó véletlenszám generátornak nevezi a szakirodalom. Angol mozaikszóval CSPRNG. Egy RNG attól lesz kriptográfiailag biztonságos, hogy átmegy a következő bit teszten és kiállja az állapot kompromittálódási tesztet.

Egy bitsorozat akkor megy át a következő bit teszten, ha a támadó a bitsorozat bármely i-edik bit előtti sorozatot ismerve matematikai számításokkal levezetve belátható időn belül nem képes megmondani  i+1 bit értékét.

Az állapot kompromittálódási teszt igen egyszerű. Ha a támadónak sikerült kitalálnia a generátor jelenlegi állapotát, és ennek ismeretében sikerül kitalálnia a következő állapotot, akkor az algoritmus megbukott az állapot kompromittálódási teszten.

A jobb érthetőség kedvéért nézzünk egy példát. Tételezzük fel, hogy a generátorunk a Pi számjegyeit számító algoritmus, aminek egy inicializációs érték alapján megadjuk, hogy melyik tizedesjegytől kezdje kifejteni a számjegyeket. Normál használat esetén az algoritmusomat mondjuk idő alapján inicializálom egy számjegyre.

Ha a támadónak sikerül kitalálnia az inicializációs értéket, akkor ugyanazt az algoritmust futtatva ugyanazzal a kezdőértékkel ugyanazokat a számjegyeket fogja kapni mint én, ezáltal megbukott a generátorom.

A példában említett Pi szám azért lenne tökéletes ilyen célokra, mivel tudjuk róla, hogy olyan mint a szerelem: irracionális és nagyon fontos 🙂 Humort mellőzve irracionális mivoltából következik, hogy végtelen és nem szakaszos, vagyis a számjegyek között nincs ismétlődő minta.

A legtöbb nem kriptográfiai RNG algoritmus hasonló elven működik. Adott egy generáló függvény, amit inicializálni kell egy kezdőértékkel és inicializálás után „véletlen” számok sorozatát fogja ontani magából az algoritmus. Azonban, ha tudom a kezdőértéket, akkor már nem is véletlen a generálás. Ideális esetben az inicializációs értéknek is véletlennek kellene lennie, de ez felveti a „tyúk vagy tojás volt előbb” klasszikus problémát.

A probléma áthidalására több módszer is létezik.

Az egyik módszer az, hogy idő alapján inicializálunk. A legtöbb számítógépben van valós idejű óra a dátum és idő tárolásához, illetve a modern (kb 10 évnél fiatalabb) pc rendszerekben van integrálva egy nagy felbontású időzítő, amely egy másodpercet legalább 10 millió részre bont. Ha az időt másodpercben számítjuk egy fix dátumhoz képest (Pl: 1970.01.01 00:00 UNIX EPOCH esetén),  akkor mindig más véletlen számot kapunk az inicializációs pillanattól függően. Ha ezt még kiegészítjük a nagy felbontású időzítő adatával, akkor jó közelítéssel kitalálhatatlan az inicializációs érték, de elméleti síkon lehetséges, mivel az idő rendszer megvalósítástól függően piszkálható .

A másik módszer az, hogy a környezetből mintavételezünk zajt. Minden analóg-digitális átalakítási módszernek a technológiából adódóan van némi hibája. Ez általában problémát jelent, de itt kifejezetten hasznos, mivel a zaj a környezet elektromágneses tulajdonságaiból származik (rádióhullámok, elektromos vezetékek, kozmikus sugárzás, stb…). Ha kifejezetten a környezeti zajt mintavételezzük, akkor használhatjuk a mintát inicializációs értéknek. A módszer problémája, hogy egyes környezetek zajosabbak, mint mások, így vannak kevésbé alkalmas és nagyon alkalmas környezetek.

A fenti két módszer a gyakorlatban jelenleg is alkalmazott. Létezik azonban egy harmadik módszer is, ami jelen pillanatban még nem mindenki által hozzáférhető hardveres kivitelben.

A harmadik módszer a kvantummechanikán alapul, méghozzá a  Heisenberg-féle határozatlansági reláció következményét használjuk. A klasszikus fizika szerint 0 Kelvin hőmérséklethez 0 energia tartozik. Ezzel szembemegy a kvantumfizika, miszerint a hely és sebesség nem mérhető tetszőleges pontossággal, mindig lesz egy kis határozatlanság, ha az egyik adatot ismerjük. Szóval, ha fixen tudjuk, hogy itt van a dolog, akkor lesz a sebességének határozatlansága, azaz lesz mozgási energiája. Nem lehet 100% pontossággal állítani, hogy nincs sebessége. Ennek a méréséből pedig véletlen számokat tudunk kapni. A probléma az, hogy közel nulla Kelvin előállítása igen nagy energiabefektetést igényel és a méréshez használt műszerek sem elhanyagolható méretűek.

Azonban az Ausztráliai Nemzeti Egyetem (ANU) üzemeltet egy ilyen generátort, aminek az adatait interneten publikálják és akár a tetszőleges programunkba is beépíthetjük ezt a fajta generátort, csupán internet kapcsolat kell a véletlen számok fogadásához 🙂

Kiegészítés: Egy nem kriprográfiai RNG-ből is kreálható kriptográfiailag biztos, csupán pár hash algoritmust kell megfelelően alkalmazni, méghozzá az inicializáció során, így lényegében a hash függvényünk számláló üzemmódban fut. A hash algoritmusokról egy későbbi írásban lesz szó.

Kiemelt kép forrása: http://dab1nmslvvntp.cloudfront.net/wp-content/uploads/2013/09/Fotolia_53649479_Subscription_XL.jpg