Manote, tai lengva? Sugalvokite atsitiktinį skaičių…

Madsas Haahras neabejoja. „Atsitiktinumų kūrimas nėra užduotis, kurią galima palikti žmonėms,“ tvirtina jis.

Nieko keista girdėti tai iš jo. Trinity koledžo Dubline kompiuterijos mokslininkas yra populiarios interneto svetainės random.org atsitiktinių skaičiaus generatoriaus kūrėjas. Bet jis teisus.

Žmonių smegenys sukurtos pastebėti ir kurti struktūras. Tai naudinga, siekiant pastebėti savanoje tykančius plėšrūnus anksčiau, nei jie pastebės jus, bet tai kliudo, kai reikia mąstyti atsitiktiniu ir nenuspėjamu būdu. Tai problema, nes tikras atsitiktinumas yra naudingas dalykas. Atsitiktiniai skaičiai naudojami kriptografijoje, kompiuterijoje, dizaine ir dar daug kur. Kadangi nesugebame atsitiktinumų generuoti patys, pavedame tai mašinoms.

Bet kliovimasis išoriniais atsitiktinumo šaltiniais irgi turi savo problemų. Pirmieji pranašavimo ir žaidimo kauliukai buvo šešiašoniai avių kojos kaulai su išdrožtais skaičiais. Dėl formos kai kurie skaičiai iškrisdavo dažniau už kitus, ir suprantantieji šias savybes galėjo panaudoti savo pranašumui.

Ir dabar išlieka įtarumas dėl modernių ekvivalentų – kazino kauliukų, ruletės ratų ar loterijos kamuoliukų. Bet iš tikrųjų atsitiktinių skaičių atsitiktinumas svarbus internete. Atsitiktinių skaičių sekų generavimas yra svarbus ne tik žaidžiant žaidimus, ar parenkat atsitiktines dainas iPode, bet ir generuojant neatspėjamus jautrią skaitmeninę informaciją koduojančius raktus. „Nemanau, kad žmonės iš tiesų supranta atsitiktinumo svarbą jų duomenų saugumui,“ sako Haahr.

Ir vien programavimo čia negana. Negalima tiesiog duoti kompiuteriui taisykles, kaip sukurti atsitiktinius skaičius; jie nebūtų atsitiktiniai. Vietoje to galima naudoti algoritmą ir atsitiktinai atrodantį rezultatą gauti iš mažesnės neatspėjamų atsitiktinių skaičių imties: pavyzdžiui, panaudoti datą ir laiką kuriuos atsitiktinius skaičius panaudoti iš atsitiktinių skaičių aibės, tarkime, π, ir toliau naudoti juos. Bėda, kad tokius „pseudoatsitiktinius“ skaičius riboja įvestis ir po tam tikro laiko jie ima kartotis tokiu būdu, kad galima nuspėti.

Galima prijungti kompiuterį prie kokio nors fizinio, „tikro“ atsitiktinumo šaltinio. XX a. šeštajame dešimtmetyje, JK Pašto tarnyba norėjo ieškojo būdo atsitiktinių skaičių generavimui pramoninėmis apimtimis, kad galėtų išrinkti Didžiojo prizo loterijos laimėtojus. Užduotis buvo paskirta pirmojo kompiuterio Colossus, skirto nacių Vokietijos Enigma kodų dešifravimui, kūrėjams. Jie sukūrė ERNIE, Electronic Random Number Indicator Equipment, naudojusį chaotiškas neono vamzdeliais sklindančių elektronų trajektorijas atsitiktinės trukmės elektronų impulsų generavimui, parinkdavusių atsitiktinius skaičius.

Dabar naudojama jau ketvirta ERNIE karta ir jis paprastesnis, ir atsitiktinių skaičių generavimui naudoja tranzistorių šiluminį triukšmą. Daug modernių įrenginių naudoja panašius šaltinius, esančius pačiame luste, pavyzdžiui, Intel RdRand ir Via Padlock. Haahro generatorius pradines sėklas ima iš atmosferos triukšmo.

Lieka dvi problemos. Pirma, turint pakankamai skaičiavimo galios, teoriškai bet kas gali rekonstruoti atsitiktinius skaičius sugeneravusius klasikinės fizikos procesus. Antra, ir labiau praktinė, vien fiziniais procesais besiremiantys atsitiktinių skaičių generatoriai dažniausiai negali sukurti atsitiktinius skaičius pakankamai greitai.

Daug sistemų, pavyzdžiui, Apple naudojama Unix pagrindo sistema, pirmąją problemą apeina, apjungdama lusto atsitiktinių skaičių generatoriaus rezultatus su „entropijos imties“ turiniu, užpildytu kitais atsitiktiniais šaltiniais. Tai gali būti viskas, nuo prie kompiuterio prijungtų įrenginių šiluminio triukšmo iki atsitiktinio laiko tarp naudotojo klaviatūros paspaudimų. Šie komponentai paskui apjungiami, panaudojant „maišos funkciją“ ir sukuriamas vienas atsitiktinis skaičius. Maišos funkcijos yra matematinis rašalo įpylimo į vandenį ekvivalentas: iš funkcijos pateikto rezultato neina nustatyti įvesties.

Tai nereiškia, kad ateityje neatsiras būdų tai atlikti – ir tebelieka spartos problema. Jai spręsti dažniausiai panaudojamas fizikiniu būdu gautas atsitiktinis skaičius, kurį programa panaudoja kaip tik sėklą pakankamo atsitiktinių skaičių srauto generavimui.

Tad grįžtame prie algoritmo problemos. Tiksli šių programų naudojamų metodų prigimtis yra slapta, bet 2013 m. saugumo analitikai išreiškė nuogąstavimus , kad JAV Nacionalinio saugumo agentūra žinojo vieno tokio generatoriaus, Dual_EC_DRBG vidinę struktūrą, kas potencialiai leido nulaužti juo paremtus kodus. Jei tiesiog žaidžiate interneto žaidimus, tai nedidelė bėda. Bet atliekant daugiamilijardinius finansinius tarptautinius pervedimus ar šifruojant svarbius dokumentus, įtarimas, kad esi stebimas yra daug svarbesnis.

Žaidimai su sistema

Dėl tokių sunkumų kai kurie tyrėjai netgi ėmė teigti, kad niekada neturėsime nenulaužiamo atsitiktinumo šaltinio tol, kol remsimės fiziniu pasauliu, kur atsitiktinumas nėra „įgimtas“, bet priklauso nuo o, kas informaciją turi (žr. „Kaip atsitiktinumai valdo pasaulį“). Norėdami saugesnio šifravimo, turime atsigręžti į kvantų fiziką, kr, regis, viskas paklūsta atsitiktinumui. Užuot metus monetą, galima pažiūrėti, ar į pusiau skaidrų veidrodį kritęs fotonas perėjo kiaurai ar atsispindėjo. Užuot ridenus kauliuką, galima panaudoti elektroną, galintį pasirinkti vieną iš šešių kelių. „Kaip matematikui, man patinka, kad mano atsitiktinumai yra tikri ir šį užtikrintumą suteikia kvantinis atsitiktinių skaičių generatorius,“ sako Carlas Milleris iš Michigano universiteto Ann Arbore. „Šiuo aspektu jis unikalus.“

Kvantų teorijos nenuspėjamumą naudojančios šifravimo sistemos saugesnei komunikacijai egzistuoja. Bet ne jos yra paskutinis saugumo žodis. Kvantų atsitiktinumų panaudojimui visada reikia, kad kas nors atliktų neatsitiktinius įrangos, matavimų, etc pasirinkimus. Kai kurių metodų naudojamas neidealus fotonų detektorių efektyvumas irgi gali suteikti „galinį įėjimą“ per kurį gali įsmukti neatsitiktinumas.

Vienas, dar tebetyrinėjamas, sprendimas galėtų būti kvantinio atsitiktinumo gausinimas, kad visada būtų daugiau, nei kas nors gali nulaužti. Yra teoriniai būdai paversti n atsitiktinių bitų į 2ⁿ bitų gryno atsitiktinumo, o taip pat išskalbti bitus ir taip pašalinti bet kokias koreliacijas su jį sukūrusiu įtaisu.

Toks nuo įrenginio nepriklausantis atsitiktinių skaičių generavimas tiesiog yra naujausias tikrojo atsitiktinumo paieškos pasiekimas. Gali būti, tai greitai taps realybe – tik tol, kol kas nors sugalvos būdą jį apeiti. Žmonės jau tokie nepasėdos, kad gal visada ieškosime tikro atsitiktinumo, kuriuo galime pasitikėti.

This article appeared in print under the headline „Think of a number“

Michael Brooks is a consultant for New Scientist

Michael Brooks
New Scientist № 3012