Hvordan computere genererer tilfældige tal

Computers genererer tilfældigt tal for alt fra kryptografi til videospil og gambling. Der er to kategorier af tilfældige tal - "sande" tilfældige tal og pseudorandom tal - og forskellen er vigtig for sikkerheden for krypteringssystemer.

Computere kan generere virkelig tilfældige tal ved at observere nogle eksterne data, som musebevægelser eller fanestøj, hvilket ikke er forudsigeligt og skaber data fra det. Dette er kendt som entropi. Andre gange genererer de "pseudorandom" tal ved at bruge en algoritme, så resultaterne vises tilfældigt, selvom de ikke er.

Dette emne er blevet mere kontroversielt for nylig, hvor mange mennesker stiller spørgsmålstegn ved, om Intels indbyggede hardware random generator generator chip er troværdigt. For at forstå, hvorfor det måske ikke er troværdigt, skal du forstå, hvordan tilfældige tal er genreeret i første omgang, og hvad de er vant til.

Hvilke tilfældige tal bruges til

Tilfældige tal er blevet brugt i mange tusind år. Uanset om det drejer en mønt eller ruller en terning, er målet at give slutresultatet op til tilfældig chance. Tilfældige talgeneratorer i en computer er ens, de er et forsøg på at opnå et uforudsigeligt, tilfældigt resultat.

Tilfældige talgeneratorer er nyttige til mange forskellige formål. Bortset fra indlysende applikationer som at generere tilfældige tal til gambling eller skabe uforudsigelige resultater i et computerspil, er tilfældighed vigtig for kryptografi.

-kryptering kræver tal, som angriberne ikke kan gætte. Vi kan ikke bare bruge de samme numre igen og igen. Vi ønsker at generere disse tal på en meget uforudsigelig måde, så angriberne ikke kan gætte dem. Disse tilfældige tal er afgørende for sikker kryptering, uanset om du krypterer dine egne filer eller bare bruger en HTTPS hjemmeside på internettet.

True Random Numbers

Du kan undre sig over, hvordan en computer faktisk kan generere et tilfældigt tal. Hvor kommer denne "tilfældighed" fra. Hvis det kun er et stykke computer kode, er det ikke muligt, at de tal, som computeren genererer kunne være forudsigelig?

Vi grupperer generelt de tilfældige tal computere genererer i to typer, afhængigt af hvordan de genereres: "True" tilfældige tal og pseudo-tilfældige tal.

For at generere et "sandt" tilfældigt tal måler computeren en form for fysisk fænomen, der finder sted uden for computeren. For eksempel kunne computeren måle det radioaktive forfald af et atom. Ifølge kvantteori er der ingen måde at vide sikkert, når radioaktivt henfald vil forekomme, så dette er i det væsentlige "ren tilfældighed" fra universet. En angriber ville ikke kunne forudsige, hvornår radioaktivt henfald ville forekomme, så de ikke ville vide tilfældig værdi.

For et mere dagligt eksempel kan computeren stole på atmosfærisk støj eller bare bruge den nøjagtige tid, du trykker på taster på tastaturet som kilde til uforudsigelige data eller entropi. For eksempel kan din computer bemærke, at du trykker på en nøgle på præcis 0.23423523 sekunder efter klokken 2. Tag fat i nok af de specifikke tider, der er forbundet med disse nøglepresser, og du vil have en entropi-kilde, du kan bruge til at generere en "sand" tilfældignummer. Du er ikke en forudsigelig maskine, så en angriber kan ikke gætte det præcise øjeblik, når du trykker på disse taster. /dev/ tilfældig enhed på Linux, som genererer tilfældige tal, "blokke" og ikke returnerer et resultat, før det samler nok entropi til at returnere et virkelig tilfældigt tal.

Pseudorandom Numbers

Pseudorandom tal er et alternativ til "ægte" tilfældige tal. En computer kan bruge en frøværdi og en algoritme til at generere tal, der synes at være tilfældige, men det er faktisk forudsigeligt. Computeren indsamler ikke tilfældige data fra miljøet.

Dette er ikke nødvendigvis en dårlig ting i enhver situation. Hvis du for eksempel spiller et videospil, betyder det ikke noget, om de hændelser, der opstår i det pågældende spil, er cased af "sande" tilfældige tal eller pseudorandom tal. På den anden side, hvis du bruger kryptering, vil du ikke bruge pseudorandomnumre, som en angriber kan gætte.

Lad os sige, at en angriber ved, at algoritmen og frøværdien bruger en pseudorandom-nummergenerator. Og lad os sige, at en krypteringsalgoritme får et pseudorandom nummer fra denne algoritme og bruger det til at generere en krypteringsnøgle uden at tilføje yderligere tilfældighed. Hvis en angriber ved nok, kan de arbejde baglæns og bestemme det pseudorandomnummer, som krypteringsalgoritmen skal have valgt i så fald, bryde krypteringen.

NSA og Intels Hardware Random Number Generator

For at gøre tingene nemmere for udviklere og medvirke til at generere sikre tilfældige tal, inkluderer Intel chips en hardwarebaseret tilfældig talegenerator kendt som RdRand. Denne chip bruger en entropy kilde på processoren og giver tilfældige tal til software, når softwaren anmoder dem.

Problemet her er, at tilfældig talgeneratoren er i det væsentlige en sort boks, og vi ved ikke, hvad der foregår indeni det. Hvis RdRand indeholdt en NSA bagdør, ville regeringen kunne bryde krypteringsnøgler, der blev genereret med kun data, der blev leveret af den tilfældige talgenerator.

Dette er et alvorligt problem. I december 2013 fjernede FreeBSDs udviklere support til at bruge RdRand direkte som en kilde til tilfældighed, idet de sagde, at de ikke kunne stole på det.[Kilde] Outputen fra RdRand-enheden ville blive fodret ind i en anden algoritme, der tilføjer yderligere entropi, hvilket sikrer, at enhver bagdør i tilfældig talgeneratoren ikke ville have betydning. Linux har allerede arbejdet på denne måde og yderligere randomiserer de tilfældige data, der kommer fra RdRand, så det ikke ville være forudsigeligt, selvom der var en bagdør.[Kilde] I en nylig AMA( "Spørg mig noget") på Reddit svarede Intel CEO Brian Krzanich ikke spørgsmål om disse bekymringer.[Kilde]

Selvfølgelig er dette sandsynligvis ikke kun et problem med Intel chips. FreeBSDs udviklere kaldte også Via's chips ved navn. Denne kontrovers viser, hvorfor generering af tilfældige tal, der er virkelig tilfældige og ikke er forudsigelige, er så vigtigt.

For at generere "sande" tilfældige tal, samler tilfældige talgeneratorer "entropi" eller tilsyneladende tilfældige data fra den fysiske verden omkring dem. For tilfældige tal, der ikke virkelig skal være tilfældige, kan de bare bruge en algoritme og en frøværdi.

Billedkredit: rekre89 på Flickr, Lisa Brewster på Flickr, Ryan Somma på Flickr, Huangjiahui på Flickr