Hvordan datamaskiner genererer tilfeldige tall

Datamaskiner genererer tilfeldig tall for alt fra kryptering til videospill og gambling. Det er to kategorier av tilfeldige tall - "ekte" tilfeldige tall og pseudorandom tall - og forskjellen er viktig for sikkerheten til krypteringssystemer.

Datamaskiner kan generere virkelig tilfeldige tall ved å observere noen utvendige data, som musebevegelser eller fanestøy, som ikke er forutsigbar, og skaper data fra den. Dette er kjent som entropi. Andre ganger genererer de "pseudorandom" tall ved å bruke en algoritme slik at resultatene vises tilfeldig, selv om de ikke er.

Dette emnet har blitt mer kontroversielt nylig, med mange som stiller spørsmål om hvorvidt Intels innebygde maskinvare-tilfeldig talgeneratorbrikke er troverdig. For å forstå hvorfor det kanskje ikke er troverdig, må du forstå hvordan tilfeldige tall er genreated i utgangspunktet, og hva de er vant til.

Hvilke tilfeldige tall er brukt til

Tilfeldige tall har blitt brukt i mange tusen år. Enten det vinner en mynt eller ruller en terning, er målet å legge sluttresultatet opp til tilfeldig tilfeldighet. Tilfeldige nummergeneratorer i en datamaskin er like - de er et forsøk på å oppnå et uforutsigbart, tilfeldig resultat.

Tilfeldige nummergeneratorer er nyttige for mange forskjellige formål. Bortsett fra åpenbare applikasjoner som å generere tilfeldige tall for gambling eller å skape uforutsigbare resultater i et dataspill, er tilfeldighet viktig for kryptografi.

Kryptografi krever tall som angriperne ikke kan gjette. Vi kan ikke bare bruke de samme tallene om og om igjen. Vi ønsker å generere disse tallene på en svært uforutsigbar måte, slik at angripere ikke kan gjette dem. Disse tilfeldige tallene er avgjørende for sikker kryptering, enten du krypterer dine egne filer eller bare bruker et HTTPS-nettsted på Internett.

Ekte tilfeldige tall

Du lurer kanskje på hvordan en datamaskin faktisk kan generere et tilfeldig tall. Hvor kommer denne "tilfeldigheten" fra. Hvis det bare er et stykke datakode, er det ikke mulig at tallene datamaskinen genererer kan være forutsigbar?

Vi grupperer vanligvis de tilfeldige tallene datamaskiner genererer i to typer, avhengig av hvordan de genereres: "Sann" tilfeldige tall og pseudo-tilfeldige tall.

For å generere et "ekte" tilfeldig tall måler datamaskinen en type fysisk fenomen som foregår utenfor datamaskinen. For eksempel kan datamaskinen måle radioaktivt forfall av et atom. Ifølge kvanteteori er det ingen måte å vite sikkert når radioaktivt henfall vil forekomme, så dette er egentlig "ren tilfeldighet" fra universet. En angriper ville ikke kunne forutsi når radioaktivt henfall ville forekomme, så de ville ikke vite tilfeldig verdi.

For et mer daglig eksempel kan datamaskinen stole på atmosfærisk støy eller bare bruke den nøyaktige tiden du trykker på tastene på tastaturet som kilde til uforutsigbar data eller entropi. For eksempel kan datamaskinen merke til at du trykket på en nøkkel på nøyaktig 0,233423523 sekunder etter klokken 14.00. Ta tak i de spesifikke tider som er knyttet til disse tastene, og du vil få en entropi som du kan bruke til å generere en "sann" tilfeldig Nummer. Du er ikke en forutsigbar maskin, så en angriper kan ikke gjette det nøyaktige øyeblikket når du trykker på disse tastene. Den / dev / random-enheten på Linux, som genererer tilfeldige tall, "blokker" og gir ikke et resultat før det samler nok entropi til å returnere et virkelig tilfeldig tall.

Pseudorandomnumre

Pseudorandom tall er et alternativ til "ekte" tilfeldige tall. En datamaskin kan bruke en frøverdi og en algoritme for å generere tall som ser ut til å være tilfeldig, men det er faktisk forutsigbar. Datamaskinen samler ikke tilfeldige data fra miljøet.

Dette er ikke nødvendigvis en dårlig ting i enhver situasjon. For eksempel, hvis du spiller et videospill, spiller det ingen rolle om hendelsene som forekommer i det spillet er cased av "ekte" tilfeldige tall eller pseudorandom tall. På den annen side, hvis du bruker kryptering, vil du ikke bruke pseudorandom tall som en angriper kan gjette.

For eksempel, la oss si at en angriper vet at algoritmen og frøverdien bruker en pseudorandom-nummergenerator. Og la oss si at en krypteringsalgoritme får et pseudorandomnummer fra denne algoritmen og bruker den til å generere en krypteringsnøkkel uten å legge til noen tilfeldig tilfeldighet. Hvis en angriper vet nok, kan de jobbe bakover og bestemme det pseudorandomnummeret som krypteringsalgoritmen må ha valgt i det tilfellet, bryte krypteringen.

NSA og Intels maskinvare Random Number Generator

For å gjøre det enklere for utviklere og bidra til å generere sikre tilfeldige tall, inkluderer Intel-sjetonger en maskinvarebasert tilfeldig talgenerator kjent som RdRand. Denne brikken bruker en entropi kilde på prosessoren og gir tilfeldige tall til programvare når programvaren ber om dem.

Problemet her er at tilfeldig talgeneratoren egentlig er en svart boks, og vi vet ikke hva som skjer i den. Hvis RdRand inneholdt en NSA bakdør, ville regjeringen kunne bryte krypteringsnøkler som ble generert med bare data som ble levert av den tilfeldige nummergeneratoren.

Dette er en alvorlig bekymring. I desember 2013 fjernet FreeBSDs utviklere støtte for å bruke RdRand direkte som en kilde til tilfeldighet, og sa at de ikke kunne stole på det. [Kilde] Utgangen av RdRand-enheten vil bli matet inn i en annen algoritme som legger til ekstra entropi, slik at eventuelle bakdører i tilfeldige tallgeneratoren ikke vil gjøre noe. Linux har allerede jobbet på denne måten, og randomiserer random dataene fra RdRand slik at det ikke ville være forutsigbart, selv om det var en bakdør. [Kilde] I en nylig AMA ("Ask Me Anything") på Reddit, svarte Intels administrerende direktør Brian Krzanich ikke spørsmål om disse bekymringene. [Kilde]

Selvfølgelig er dette sannsynligvis ikke bare et problem med Intel-chips. FreeBSDs utviklere kalt ut Via's chips ved navn også. Denne kontroversen viser hvorfor å generere tilfeldige tall som er virkelig tilfeldig og ikke er forutsigbar, er så viktig.

For å generere "ekte" tilfeldige tall, samler tilfeldige nummergeneratorer "entropi" eller tilsynelatende tilfeldige data fra den fysiske verden rundt dem. For tilfeldige tall som ikke gjør det egentlig må være tilfeldig, de kan bare bruke en algoritme og en frøverdi.

Image Credit: rekre89 på Flickr, Lisa Brewster på Flickr, Ryan Somma på Flickr, Huangjiahui på Flickr