Hogyan generálják a számítógépek véletlen számokat

A számítógépek véletlen számot generálnak mindentől a titkosítástól a videojátékokig és a szerencsejátékokig. A véletlenszámok két kategóriája van: „valódi” véletlen számok és pszeudorandom számok - és a különbség fontos a titkosítási rendszerek biztonsága szempontjából.

A számítógépek valóban véletlenszerű számokat generálhatnak bizonyos külső adatok megfigyelésével, mint például az egérmozgások vagy a ventilátorok zajai, amelyek nem kiszámíthatóak, és adatokat hoznak létre belőle. Ezt entrópiának nevezik. Más esetekben algoritmus segítségével „pszeudorandom” számokat generálnak, így az eredmények véletlenszerűek, még akkor is, ha nem.

Ez a téma a közelmúltban ellentmondásosabbá vált, sokan megkérdőjelezték, hogy az Intel beépített hardveres véletlenszám-generátor chipje megbízható-e. Ahhoz, hogy megértsük, miért nem lehet megbízható, meg kell értened, hogy a véletlen számok hogyan kerülnek először első helyre, és mit használnak.

Milyen véletlen számokat használnak

A véletlen számokat több ezer éve használták. Függetlenül attól, hogy egy érmét forgat, vagy kockát dob, a cél az, hogy a végeredményt véletlenszerűen hagyja. A számítógép véletlenszerű számgenerátorai hasonlóak - próbálják kiszámíthatatlan, véletlenszerű eredményt elérni.

A véletlenszám-generátorok sokféle célra használhatók. Az olyan nyilvánvaló alkalmazások mellett, mint a véletlen számok létrehozása szerencsejáték céljára vagy kiszámíthatatlan eredmények létrehozása számítógépes játékban, a véletlenszerűség fontos a kriptográfia szempontjából..

A kriptográfia olyan számokat igényel, amelyeket a támadók nem tudnak kitalálni. Nem csak ugyanazokat a számokat használhatjuk újra és újra. Ezeket a számokat nagyon kiszámíthatatlan módon szeretnénk létrehozni, így a támadók nem tudják kitalálni őket. Ezek a véletlen számok elengedhetetlenek a biztonságos titkosításhoz, függetlenül attól, hogy titkosítja a saját fájljait, vagy egyszerűen csak HTTPS webhelyet használ az interneten.

Igaz véletlen számok

Lehet, hogy kíváncsi vagy, hogy egy számítógép hogyan hozhat létre véletlen számot. Honnan származik ez a „véletlenszerűség”. Ha ez csak egy darab számítógépes kód, nem lehetséges, hogy a számítógép által generált számok kiszámíthatóak legyenek?

Általában a véletlenszámú számítógépeket két csoportra csoportosítjuk, attól függően, hogy hogyan hozhatók létre: „Igaz” véletlen számok és ál-véletlen számok.

A „valódi” véletlen szám létrehozásához a számítógép valamilyen fizikai jelenséget mér, amely a számítógépen kívül történik. Például a számítógép mérheti az atom radioaktív bomlását. A kvantumelmélet szerint nem lehet biztosan tudni, mikor történik a radioaktív bomlás, így ez lényegében „univerzális véletlen”. A támadó nem tudná megjósolni, mikor következik be a radioaktív bomlás, így nem tudnák a véletlen értéket.

Egy napról-napra például a számítógép a légköri zajra támaszkodhat, vagy egyszerűen csak arra használhatja a pontos időt, amikor a billentyűzet gombjait kiszámíthatatlan adatok vagy entrópia forrásaként használja. Például a számítógép észreveheti, hogy 2 óra után pontosan 0.23423523 másodpercig nyomta meg a billentyűt… Megragadja az ezekhez a gombnyomásokhoz kapcsolódó konkrét időket, és van egy entrópiaforrása, amellyel létrehozhat egy „igaz” véletlenszerű szám. Nem egy kiszámítható gép, így a támadó nem tudja kitalálni, hogy pontosan mikor nyomja meg ezeket a gombokat. A / dev / random eszköz Linuxon, amely véletlen számokat generál, „blokkol”, és nem ad eredményt, amíg elég entrópiát nem gyűjti össze, hogy valóban véletlen számot küldjön vissza.

Pszeudorandom számok

A pszeudorandom számok az „igaz” véletlen számok alternatívája. A számítógép egy vetőmagértéket és egy algoritmust használhat számok generálására, amelyek véletlenszerűnek tűnnek, de valójában kiszámíthatóak. A számítógép nem gyűjt véletlen adatokat a környezetből.

Ez nem feltétlenül rossz helyzet minden helyzetben. Például, ha videojátékot játszik le, nem igazán számít, hogy a játékban előforduló események „igaz” véletlen számok vagy álneves számok kerülnek-e. Másrészről, ha titkosítást használ, nem akarja használni a pszeudorandum számokat, amelyeket egy támadó kitalálhat.

Tegyük fel például, hogy egy támadó ismeri az algoritmust és a magértéket egy pszeudorandom számgenerátor használatakor. Tegyük fel, hogy egy titkosítási algoritmus egy pszeudorandum számot kap az algoritmustól, és titkosítási kulcsot generál további véletlenszerűség hozzáadása nélkül. Ha egy támadó eléggé ismeri, visszafelé tudnak dolgozni, és meghatározhatják a pszeudorandum számot, amelyet a titkosítási algoritmusnak ebben az esetben kellett választania, megszakítva a titkosítást.

Az NSA és az Intel hardveres véletlenszám-generátora

Annak érdekében, hogy a dolgozók könnyebbé váljanak a fejlesztők számára, és biztonságos véletlen számokat hozzanak létre, az Intel chipek közé tartozik egy RdRand néven ismert hardver alapú véletlenszám-generátor. Ez a chip egy entrópiaforrást használ a processzoron, és véletlen számokat biztosít a szoftverhez, amikor a szoftver kéri őket.

A probléma az, hogy a véletlenszám-generátor lényegében egy fekete doboz, és nem tudjuk, mi folyik benne. Ha az RdRand NSA hátsó ajtót tartalmazott, a kormány képes lenne megtörni a titkosítási kulcsokat, amelyeket csak a véletlenszám-generátor által szolgáltatott adatokkal generáltak..

Ez komoly aggodalomra ad okot. 2013 decemberében a FreeBSD fejlesztői eltávolították az RdRand közvetlen használatát a véletlenszerűség forrásaként, mondván, hogy nem bíznak benne. [Forrás] Az RdRand eszköz kimenete egy másik algoritmusba kerülne, amely további entrópiát ad, biztosítva, hogy a véletlenszám generátor minden hátsó szabadsága nem számít. A Linux már így is dolgozott, véletlenszerűen véletlenszerűvé téve az RdRand-ból érkező véletlen adatokat, hogy ne legyen kiszámítható még akkor is, ha van hátajtó. [Forrás] Egy friss AMA-ban („Ask Me Anything”) a Reddit-en, az Intel vezérigazgatója, Brian Krzanich nem válaszolt ezekre az aggályokra vonatkozó kérdésekre. [Forrás]

Természetesen ez valószínűleg nem csak az Intel chipjeivel kapcsolatos probléma. A FreeBSD fejlesztői név szerint is felhívták a Via zsetonjait. Ez a vita azt mutatja, hogy a véletlen számok létrehozása, amelyek valóban véletlenek és nem kiszámíthatóak, olyan fontosak.

A „valódi” véletlen számok generálásához a véletlenszám-generátorok „entrópiát” vagy látszólag véletlenszerű adatokat gyűjtenek az őket körülvevő fizikai világból. Véletlen számok esetén, amelyek nem igazán véletlenszerűnek kell lenniük, csak algoritmust és magértéket használhatnak.

Kép-jóváírás: a Flickr-nél rekre89, a Flickr Lisa Brewster-en, a Flickr-nél Ryan Sommán, a Flickr-en a huangjiahui-on