Kaip kompiuteriai generuoja atsitiktinius skaičius

Kompiuteriai sukuria atsitiktinį skaičių viskam, pradedant kriptografija, baigiant vaizdo žaidimais ir lošimais. Yra dvi atsitiktinių skaičių kategorijos - „tikri“ atsitiktiniai skaičiai ir pseudopatybiniai skaičiai - ir skirtumas yra svarbus šifravimo sistemų saugumui.

Kompiuteriai gali generuoti tikrai atsitiktinius skaičius, stebėdami kai kuriuos išorinius duomenis, pvz., Pelės judesius ar ventiliatoriaus triukšmą, kuris nėra numatomas, ir kurdami iš jų duomenis. Tai vadinama entropija. Kitu metu jie sukuria „pseudoatsitiktinius“ skaičius naudodami algoritmą, kad rezultatai pasirodytų atsitiktiniai, nors ir nėra.

Ši tema pastaruoju metu tampa vis prieštaringesnė, nes daugelis žmonių abejoja, ar „Intel“ įmontuota aparatinės įrangos atsitiktinių skaičių generatoriaus lustas yra patikimas. Norėdami suprasti, kodėl tai gali būti nepatikima, turite suprasti, kaip pirmiausia generuojami atsitiktiniai skaičiai ir kam jie naudojami.

Kam naudojami atsitiktiniai skaičiai

Atsitiktiniai skaičiai buvo naudojami daugelį tūkstančių metų. Nesvarbu, ar tai būtų monetos vartymas, ar kauliukų metimas, tikslas yra palikti galutinį rezultatą atsitiktinai. Atsitiktinių skaičių generatoriai kompiuteryje yra panašūs - jie bando pasiekti nenuspėjamą, atsitiktinį rezultatą.

SUSIJEDS: Kas yra šifravimas ir kaip jis veikia?

Atsitiktinių skaičių generatoriai yra naudingi įvairiems tikslams. Be akivaizdžių programų, tokių kaip atsitiktinių skaičių generavimas lošimo tikslais ar nenuspėjamų rezultatų sukūrimas kompiuteriniame žaidime, kriptografijai yra svarbus atsitiktinumas.

Kriptografijai reikalingi skaičiai, kurių užpuolikai negali atspėti. Mes negalime tik tuos pačius skaičius naudoti vėl ir vėl. Norime sugeneruoti šiuos skaičius labai nenuspėjamai, kad užpuolikai negalėtų jų atspėti. Šie atsitiktiniai skaičiai yra būtini saugiam šifravimui, nesvarbu, ar šifruojate savo failus, ar tiesiog naudojate HTTPS svetainę internete.

Tikrieji atsitiktiniai skaičiai

Jums gali kilti klausimas, kaip kompiuteris iš tikrųjų gali sugeneruoti atsitiktinį skaičių. Iš kur šis „atsitiktinumas“. Jei tai tik kompiuterio kodo dalis, ar neįmanoma nuspėti kompiuterio sukurtų skaičių?

Mes paprastai suskirstome atsitiktinius skaičius, kuriuos generuoja kompiuteriai, į du tipus, priklausomai nuo to, kaip jie generuojami: „Tikrieji“ atsitiktiniai skaičiai ir pseudoatsitiktiniai skaičiai.

Norėdamas sugeneruoti „tikrąjį“ atsitiktinį skaičių, kompiuteris išmatuoja tam tikro tipo fizinius reiškinius, vykstančius už kompiuterio ribų. Pavyzdžiui, kompiuteris galėjo išmatuoti radioaktyvų atomo skilimą. Remiantis kvantine teorija, negalima tiksliai žinoti, kada įvyks radioaktyvus skilimas, todėl tai iš esmės yra „grynas atsitiktinumas“ iš visatos. Užpuolikas negalėtų numatyti, kada įvyks radioaktyvus skilimas, todėl jie nežinotų atsitiktinės vertės.

Kasdieniškesnio pavyzdžio atveju kompiuteris gali pasikliauti atmosferos triukšmu arba tiesiog naudoti tikslų laiką, kurį paspaudžiate klaviatūros klavišus, kaip nenuspėjamų duomenų šaltinį arba entropiją. Pavyzdžiui, jūsų kompiuteris gali pastebėti, kad paspaudėte klavišą tiksliai 0,23423523 sekundėmis po 14 val. Paimkite pakankamai konkretaus laiko, susijusio su šiais klavišų paspaudimais, ir turėsite entropijos šaltinį, kurį galėsite naudoti „tikram“ atsitiktiniam skaičiui sugeneruoti. Jūs nesate nuspėjama mašina, todėl užpuolikas negali atspėti tikslaus momento, kai paspausite šiuos klavišus. „Linux“ įrenginys / dev / random, generuojantis atsitiktinius skaičius, „užblokuoja“ ir negrąžina rezultato, kol nesurenka pakankamai entropijos, kad būtų grąžintas tikrai atsitiktinis skaičius.

Pseudonuotiniai skaičiai

Pseudonuotiniai skaičiai yra alternatyva „tikriesiems“ atsitiktiniams skaičiams. Kompiuteris galėtų naudoti pradinę vertę ir algoritmą, kad sugeneruotų skaičius, kurie atrodo atsitiktiniai, bet iš tikrųjų yra nuspėjami. Kompiuteris nerenka jokių atsitiktinių duomenų iš aplinkos.

Tai nebūtinai yra blogas dalykas kiekvienoje situacijoje. Pvz., Jei žaidžiate vaizdo žaidimą, visiškai nesvarbu, ar tame žaidime vykstančius įvykius sukėlė „tikri“ atsitiktiniai skaičiai, ar pseudoatsitiktiniai skaičiai. Kita vertus, jei naudojate šifravimą, nenorite naudoti pseudopatybinių skaičių, kuriuos užpuolikas galėjo atspėti.

Pavyzdžiui, tarkime, kad užpuolikas žino algoritmą ir pradinę vertę, kurią naudoja pseudo atsitiktinių skaičių generatorius. Tarkime, kad šifravimo algoritmas iš šio algoritmo gauna pseudo atsitiktinį skaičių ir naudoja jį šifravimo raktui generuoti, nepridėdamas jokio papildomo atsitiktinumo. Jei užpuolikas žino pakankamai, jis galėtų dirbti atgal ir nustatyti pseudopatybinį numerį, kurį tokiu atveju turėjo pasirinkti šifravimo algoritmas, sugadindamas šifravimą.

NSA ir „Intel“ aparatinės įrangos atsitiktinių skaičių generatorius

Kad kūrėjams būtų lengviau ir būtų lengviau generuoti saugius atsitiktinius skaičius, „Intel“ lustuose yra aparatinės įrangos atsitiktinių skaičių generatorius, žinomas kaip „RdRand“. Ši lustas naudoja procesoriaus entropijos šaltinį ir pateikia programinei įrangai atsitiktinius skaičius, kai programinė įranga jų reikalauja.

Čia problema ta, kad atsitiktinių skaičių generatorius iš esmės yra juodas langelis ir mes nežinome, kas vyksta jo viduje. Jei „RdRand“ būtų NSA užpakalinė duris, vyriausybė galėtų nutraukti šifravimo raktus, kurie buvo sukurti naudojant tik to atsitiktinių skaičių generatoriaus pateiktus duomenis.

Tai kelia rimtą susirūpinimą. 2013 m. Gruodžio mėn. „FreeBSD“ kūrėjai pašalino palaikymą naudoti „RdRand“ tiesiogiai kaip atsitiktinumo šaltinį, sakydami, kad negali tuo pasitikėti. [Šaltinis] „RdRand“ įrenginio išvestis bus įtraukta į kitą algoritmą, kuris prideda papildomą entropiją, užtikrindamas, kad jokios atsitiktinių skaičių generatoriaus užpakalinės durys nebūtų svarbios. „Linux“ jau dirbo tokiu būdu, dar labiau atsitiktinai parinkdamas atsitiktinius duomenis, gautus iš „RdRand“, kad jų nebūtų galima nuspėti, net jei būtų užpakalinės durys. [Šaltinis] Neseniai „Reddit“ atliktame AMA („Ask Me Anything“) „Intel“ generalinis direktorius Brianas Krzanichas neatsakė į klausimus apie šiuos susirūpinimą keliančius klausimus. [Šaltinis]

Žinoma, tai greičiausiai nėra tik „Intel“ lustų problema. „FreeBSD“ kūrėjai taip pat pavadino „Via“ žetonus. Ši diskusija parodo, kodėl taip svarbu generuoti atsitiktinius ir tikrai nenuspėjamus atsitiktinius skaičius.

Norėdami sukurti „tikrus“ atsitiktinius skaičius, atsitiktinių skaičių generatoriai renka „entropiją“ arba, atrodo, atsitiktinius duomenis iš juos supančio fizinio pasaulio. Atsitiktiniams skaičiams, kurie iš tikrųjų neturi būti atsitiktiniai, jie gali naudoti tik algoritmą ir pradinę vertę.

Vaizdo kreditas: rekre89 „Flickr“, Lisa Brewster „Flickr“, Ryanas Somma „Flickr“, „huangjiahui“ „Flickr“