Hoe Computers willekeurige getallen genereren

Computers genereren een willekeurig nummer voor alles, van cryptografie tot videogames en gokken. Er zijn twee categorieën van willekeurige getallen - "echte" willekeurige getallen en pseudowillekeurige getallen - en het verschil is belangrijk voor de beveiliging van versleutelingssystemen.

Computers kunnen echt willekeurige getallen genereren door sommige externe gegevens te observeren, zoals muisbewegingen of ventilatorruis, die niet voorspelbaar is, en er gegevens van te maken. Dit staat bekend als entropie. Op andere momenten genereren ze "pseudorandom" -nummers door een algoritme te gebruiken, zodat de resultaten willekeurig lijken, ook al zijn ze niet.

Dit onderwerp is recent controversiëler geworden, waarbij veel mensen zich afvroegen of Intel's ingebouwde hardware-generator voor willekeurige getallen betrouwbaar is. Om te begrijpen waarom het misschien niet betrouwbaar is, moet je begrijpen hoe willekeurige getallen in de eerste plaats worden genereeerd en waarvoor ze worden gebruikt.

Welke willekeurige nummers worden gebruikt voor

Willekeurige getallen worden al vele duizenden jaren gebruikt. Of het nu gaat om een ​​munt slaan of een dobbelsteen gooien, het doel is om het eindresultaat willekeurig te laten. Willekeurige nummergeneratoren in een computer zijn vergelijkbaar - ze zijn een poging om een ​​onvoorspelbaar, willekeurig resultaat te bereiken.

Willekeurige nummergeneratoren zijn nuttig voor veel verschillende doeleinden. Afgezien van voor de hand liggende toepassingen, zoals het genereren van willekeurige getallen met het oog op gokken of het creëren van onvoorspelbare resultaten in een computerspel, is willekeur belangrijk voor cryptografie.

Cryptografie vereist getallen die aanvallers niet kunnen raden. We kunnen niet dezelfde nummers steeds opnieuw gebruiken. We willen deze nummers op een zeer onvoorspelbare manier genereren, dus aanvallers kunnen ze niet raden. Deze willekeurige getallen zijn essentieel voor veilige codering, of u nu uw eigen bestanden codeert of alleen een HTTPS-website op internet gebruikt.

True Random Numbers

U vraagt ​​zich misschien af ​​hoe een computer daadwerkelijk een willekeurig nummer kan genereren. Waar komt deze "willekeur" vandaan? Als het gewoon een stukje computercode is, is het niet mogelijk dat de cijfers die de computer genereert, voorspelbaar zijn?

Over het algemeen groeperen we de computers met willekeurige getallen in twee typen, afhankelijk van hoe ze worden gegenereerd: "Ware" willekeurige getallen en pseudo-willekeurige getallen.

Om een ​​"echt" willekeurig getal te genereren, meet de computer een soort fysiek fenomeen dat buiten de computer plaatsvindt. De computer kan bijvoorbeeld het radioactieve verval van een atoom meten. Volgens de kwantumtheorie is er geen manier om zeker te weten wanneer radioactief verval zal plaatsvinden, dus dit is in wezen "pure willekeur" van het universum. Een aanvaller zou niet kunnen voorspellen wanneer radioactief verval zou plaatsvinden, dus zij zouden de willekeurige waarde niet weten.

Voor een meer alledaags voorbeeld kan de computer vertrouwen op atmosferische ruis of gewoon de exacte tijd gebruiken dat u toetsen op uw toetsenbord indrukt als een bron van onvoorspelbare gegevens of entropie. Uw computer kan bijvoorbeeld merken dat u na 2 uur op een toets drukt op exact 0,23423523 seconden ... Grijp genoeg van de specifieke tijden die zijn gekoppeld aan deze toetsaanslagen en u hebt een entropiebron die u kunt gebruiken om een ​​"echte" willekeurige te genereren aantal. Je bent geen voorspelbare machine, dus een aanvaller kan het precieze moment waarop je op deze toetsen drukt niet raden. Het / dev / random-apparaat op Linux, dat willekeurige getallen genereert, "blokkeert" en retourneert geen resultaat totdat het genoeg entropie heeft verzameld om een ​​echt willekeurig getal te retourneren.

Pseudorandom Numbers

Pseudorandom-getallen zijn een alternatief voor "echte" willekeurige getallen. Een computer kan een seed-waarde en een algoritme gebruiken om getallen te genereren die willekeurig lijken, maar die in feite voorspelbaar zijn. De computer verzamelt geen willekeurige gegevens uit de omgeving.

Dit is niet per se een slechte zaak in elke situatie. Als u bijvoorbeeld een videogame speelt, maakt het niet echt uit of de gebeurtenissen die in die game plaatsvinden worden gevat door 'echte' willekeurige getallen of pseudo-willekeurige nummers. Aan de andere kant, als u codering gebruikt, wilt u geen pseudowillekeurige nummers gebruiken die een aanvaller kan raden.

Laten we bijvoorbeeld zeggen dat een aanvaller het algoritme en de seed-waarde kent die een pseudorandom-nummergenerator gebruikt. En laten we zeggen dat een coderingsalgoritme een pseudowillekeurig nummer krijgt van dit algoritme en het gebruikt om een ​​coderingssleutel te genereren zonder extra willekeur toe te voegen. Als een aanvaller voldoende weet, kunnen ze achterwaarts werken en het pseudo-willekeurige nummer bepalen dat het coderingsalgoritme in dat geval moet hebben gekozen, waarbij de codering is verbroken.

De NSA en de Hardware Random Number Generator van Intel

Om het voor ontwikkelaars gemakkelijker te maken en veilige, willekeurige nummers te genereren, bevatten Intel-chips een op hardware gebaseerde willekeurige nummergenerator die bekend staat als RdRand. Deze chip maakt gebruik van een entropiebron op de processor en geeft willekeurige nummers aan software wanneer de software daarom vraagt.

Het probleem hier is dat de generator van willekeurige getallen in wezen een zwarte doos is en we weten niet wat erin gebeurt. Als RdRand een achterdeur van NSA bevatte, zou de overheid coderingssleutels kunnen breken die werden gegenereerd met alleen gegevens die door die generator voor willekeurige getallen waren geleverd.

Dit is een ernstige zorg. In december 2013 hebben de ontwikkelaars van FreeBSD de ondersteuning voor het gebruik van RdRand direct verwijderd als een bron van willekeur, waarbij ze zeiden dat ze het niet konden vertrouwen. [Bron] De uitvoer van het RdRand-apparaat zou worden ingevoerd in een ander algoritme dat extra entropie toevoegt, waarbij ervoor wordt gezorgd dat eventuele achterdeuren in de generator voor willekeurige getallen er niet toe doen. Linux werkte al op deze manier, verder randomiseren van de willekeurige gegevens afkomstig van RdRand zodat het niet voorspelbaar zou zijn, zelfs als er een achterdeur was. [Bron] In een recente AMA ("Ask Me Anything") op Reddit heeft Intel CEO Brian Krzanich geen vragen over deze zorgen beantwoord. [Bron]

Natuurlijk is dit waarschijnlijk niet alleen een probleem met Intel-chips. De ontwikkelaars van FreeBSD hebben ook de naam van Via's chips bij naam genoemd. Deze controverse laat zien waarom het genereren van willekeurige getallen die echt willekeurig zijn en niet voorspelbaar zijn, zo belangrijk is.

Voor het genereren van "echte" willekeurige getallen verzamelen willekeurige nummergeneratoren "entropie" of schijnbaar willekeurige gegevens uit de fysieke wereld om hen heen. Voor willekeurige getallen die dat niet doen werkelijk moeten willekeurig zijn, ze kunnen alleen een algoritme en een seed-waarde gebruiken.

Image Credit: rekre89 op Flickr, Lisa Brewster op Flickr, Ryan Somma op Flickr, huangjiahui op Flickr