HTG legt uit: hoe computers het genereren van willekeurige getallen

Computers genereren van willekeurige getallen voor alles van cryptografie tot videogames en gokken. Er zijn twee categorieën toevalsgetallen – “true” pseudo willekeurige cijfers en getallen – en het verschil is belangrijk voor de beveiliging versleutelingssystemen.

Dit onderwerp is onlangs controversiëler geworden, met veel mensen vragen of Intel’s ingebouwde hardware random number generator chip betrouwbaar is. Om te begrijpen waarom het niet betrouwbaar zou zijn, zul je moeten begrijpen hoe willekeurige getallen worden genreated.

Willekeurige getallen zijn gebruikt voor vele duizenden jaren. Of het nu het opgooien van een munt of het werpen van een dobbelsteen, het doel is om te vertrekken het eindresultaat tot toeval. Random number generators in een computer zijn vergelijkbaar – ze een poging een onvoorspelbare, willekeurige resultaat.

Random number generators zijn nuttig voor vele verschillende doeleinden. Naast duidelijke toepassingen zoals het genereren van willekeurige getallen in het kader van gokken of creëren onvoorspelbare resultaten in een computerspel, willekeurigheid is belangrijk voor cryptografie.

Cryptografie vereist nummers die aanvallers niet kan raden. We kunnen niet zomaar gebruik maken van dezelfde nummers over en voorbij. We willen deze getallen te genereren in een zeer onvoorspelbare manier, zodat aanvallers ze niet kunnen raden. Deze willekeurige getallen zijn essentieel voor veilige versleuteling, of u uw eigen bestanden versleutelen bent of gewoon met behulp van een HTTPS-website op het internet.

Je kunt je afvragen hoe een computer eigenlijk een willekeurig getal kan genereren. Waar komt deze “willekeur” vandaan komen. Als het is gewoon een stukje van de computer code, is het niet mogelijk de nummers de computer genereert voorspelbaar zou kunnen zijn?

We gewoonlijk groep de willekeurige getallen genereren computers in twee types, afhankelijk van hoe ze gebaseerd: “Waar” willekeurige getallen en pseudo-willekeurige getallen.

Een “echte” willekeurige getallen genereren, de computer meet een soort fysieke fenomenen die buiten de computer plaatsvindt. Zo kan de computer het radioactieve verval van een atoom meten. Volgens de kwantumtheorie, is er geen manier om zeker te weten wanneer radioactief verval zal optreden, dus dit is in wezen “pure willekeur” van het universum. Een aanvaller zou niet in staat zijn om te voorspellen wanneer radioactief verval zou plaatsvinden, zodat ze niet weten wat de willekeurige waarde.

Voor een dag-tot-dag kan bijvoorbeeld de computer een beroep doen op de atmosferische ruis of gewoon gebruik maken van de exacte tijd dat u op de toetsen op het toetsenbord als een bron van onvoorspelbare gegevens of entropie. Bijvoorbeeld, kan uw computer merken dat je een toets ingedrukt op precies 0.23423523 seconden na 14:00. Pak genoeg van de specifieke tijden in verband met deze toetsaanslagen en je zult een bron van entropie hebben u kunt gebruiken om een ​​”echte” random genereren aantal. Je bent geen voorspelbaar machine, zodat een aanvaller kan het precieze moment niet raden wanneer u op deze toetsen. De / dev / random-apparaat op Linux, die willekeurige getallen genereert, “blokken”, en niet een resultaat terug tot het verzamelt genoeg entropie om een ​​echt willekeurig getal terug.

Pseudo-nummers zijn een alternatief voor de “echte” willekeurige getallen. Een computer kan een zaadgetal en een algoritme om nummers die lijken te zijn willekeurig genereren, maar die in feite voorspelbaar. De computer heeft geen willekeurige gegevens te verzamelen uit de omgeving.

Dit is niet noodzakelijk een slechte zaak in elke situatie. Bijvoorbeeld, als je het afspelen van een video game, het maakt niet echt uit of de gebeurtenissen die zich voordoen in dat spel zijn ingesloten door “echte” willekeurige getallen of pseudo-willekeurige getallen. Aan de andere kant, als je gebruik maakt van encryptie, je wilt niet pseudo-nummers die een aanvaller kon raden gebruiken.

Bijvoorbeeld, laten we zeggen een aanvaller kent het algoritme en het zaad waarde een pseudotoevalsgenerator gebruikt. En laten we zeggen een encryptie-algoritme krijgt een pseudo-nummer van dit algoritme en gebruikt het om een ​​coderingssleutel te genereren zonder toevoeging van extra willekeur. Als een aanvaller weet genoeg, dan kan ze terug te werken en bepalen pseudorandomgetal het coderingsalgoritme moet gekozen dat geval, het breken van de codering.

Om dingen makkelijker voor ontwikkelaars te maken en helpen bij het genereren van veilige willekeurige getallen, Intel-chips zijn voorzien van een op hardware gebaseerde random number generator bekend als RdRand. Deze chip maakt gebruik van een entropie bron op de processor en biedt willekeurige getallen om software als de software daarom verzoekt.

Het probleem hierbij is dat de random number generator is in wezen een black box en we weten niet wat er aan de hand erin. Als RdRand een NSA backdoor bevatte, zou de overheid in staat zijn om encryptiesleutels die werden gegenereerd met alleen gegevens door die random number generator geleverd breken.

Dit is een ernstig probleem. In december 2013, FreeBSD ontwikkelaars verwijderd ondersteuning voor het gebruik RdRand direct als een bron van willekeur, zeggen dat ze niet konden vertrouwen. [Bron] De uitgang van de RdRand apparaat zou worden ingevoerd in een algoritme dat extra entropie toevoegt, zodat achterdeuren in de random number generator niet van belang zou zijn. Linux reeds werkzaam op deze wijze verder randomizing de willekeurige gegevens uit RdRand zodat het niet voorspelbaar zou zijn, zelfs als er een achterdeur was. [Bron] In een recent AMA ( “Ask Me Anything”) op Reddit, heeft Intel CEO Brian Krzanich niet vragen over deze zorgen te beantwoorden. [Bron]

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

“True” random getallen te genereren, random number generators te verzamelen “entropie”, of schijnbaar willekeurige gegevens uit de fysieke wereld om hen heen. Voor willekeurige nummers die niet echt nodig te zijn willekeurig, kunnen ze gewoon gebruik maken van een algoritme en een zaadje waarde.

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

De perfecte random number generatie algoritme

Thanks, xkcd!

Vele jaren geleden in een van mijn eerste computer cursussen (rond 1978) Eén opdracht omvatte een random number generator in FORTRAN. De instructeur was van plan om cijfer gedeeltelijk gebaseerd op het aantal iteraties het zou gaan voordat u begint te herhalen. gebruikt De meeste studenten een variatie op een groot priemgetal voor hun zaad want dat was wat het boek zien als de manier om het te doen. Voor mijn zaad, gebruikte ik de systeemklok. Telkens wanneer nodig een willekeurig getal, deed een oproep aan de klok voor een nieuw zaad. Mijn generator was nog steeds lang na elke niemand anders was in het herhalen. De instructeur eindelijk gestopt en het was nog steeds niet te herhalen. Het volgende jaar, gebruikte hij mijn oplossing te laten zien hoe een pseudo-random number generator kan worden gemaakt in een echte random number generator.

De instructeur eindelijk gestopt en het was nog steeds niet te herhalen. Het volgende jaar, gebruikte hij mijn oplossing te laten zien hoe een pseudo-random number generator kan worden gemaakt in een echte random number generator.

Met behulp van het systeem tijd is altijd een manier om een ​​meer random seed te creëren, werden we leren dat terug in de jaren ’80. Het probleem is dat de sequentie nog niet echt willekeurig. Dit is “pseudo-random”, omdat het resultaat is nog steeds deterministisch. Het is mogelijk om de uitkomst van uw random number roll voorspellen als je weet dat de systeemtijd.

Als u wilt een echt willekeurig getal, moet je om te communiceren met iets buiten de computer. Een manier om dit te doen is met de microfoon van de geluidskaart. Zelfs als je niet beschikt over een microfoon aangesloten hebben, is het nog steeds mogelijk om witte ruis te krijgen door middel van de microfoon voorversterker. Je neemt een paar voorbeelden van de microfoon haven en die te gebruiken als onderdeel van uw zaad. Of een persoon die druk op een toets op het toetsenbord als een symbool knippert op het scherm. Het maakt niet uit hoe goed ze zijn, zal er een non-deterministische vertraging tussen het moment dat het symbool verschijnt en het moment dat de sleutel is volledig worden ingedrukt.

Er zijn andere manieren worden gekoppeld aan de echte wereld, maar ook: radio-ontvangers, videocamera’s, ook sensoren die radioactief verval kan detecteren. Je kon muisbewegingen opnemen op het scherm of gebruik maken van de locatie van een GPS-apparaat op hij netwerk APRS

De sleutel krijgt buiten de processor en de echte wereld. Zodra u het digitale domein te verlaten, willekeur in overvloed.

Hoe zit het systeem genereert willekeurige getallen op basis van de eigenschappen (het aantal, grootte, machtigingen en bestandsnaam extensie) van alle bestanden in alle schijven aangesloten op de computer? Dat zou pseudo-random zijn ook (aanvaller zou een gekloonde kopie van uw harde schijf hebt), maar waarschijnlijk niet waarschijnlijk te vinden om in een patroon gemakkelijk.

Als alternatief, wanneer / dev / random runs uit dingen, start de timing van de tijd tot het meer spullen krijgt. Die tijden niet altijd hetzelfde zijn.

Met de time sharing we moesten werken op die oude Data General Eclipse, zal het programma worden onderbroken om de paar seconden voor een hogere prioriteit programma te draaien – dit het effect van het veranderen van het zaad in de tijd gehad. Ook was er een klok drift dat hielp houden het willekeurig. Dit was in 1978 – computer klokken waren niet zo stabiel. Vooral in ongeveer 8 cijfers achter de komma. Je moet echt niet veel drift nodig om een ​​daadwerkelijke willekeurige output. Ik hou van het idee van het gebruik van witte ruis met een zaadje genereren ook. Maar dat zou een aantal externe input die wij geen toegang hebben tot op dat moment had geëist. Er was geen audio daarbij betrokken computer. Later, na schooltijd, haakte ik allerlei apparaten tot verschillende computers, De enige keer dat ik nodig had een random number generator was voor een D & D dobbelstenen rollen prog schreef ik in Basic op een december VT78 had ik thuis. Zoals het liep in real time, en niet de klok niet lezen totdat er een toets wordt ingedrukt het werkte prima voor mijn toepassing. Je moet 2D7 rollen? We kunnen dat doen.

@bben eigenlijk, ik miste het deel waar je dat deden in 1978.

Ik had dezelfde ervaring in mijn eerste computer klasse in 1982. We waren het coderen van een hi-low spel, en ik merkte dat er geen enkel deed ik dezelfde volgorde elke keer, maar dat de sequentie was hetzelfde op alle computers in het lab. Sindsdien heb ik altijd op zoek naar een betere random number-algoritme, en dat is waarom ik geïnteresseerd in het idee van het gebruik van real-world data om het algoritme zaad werd.

In een ideale wereld, zou een computer een ingebouwde analoge component die een echt willekeurig waarde genereert, dan maakt dat wanneer iemand de functie Rand () oproepen. Ik ben een beetje verbaasd dat, met meer dan 50 jaar van de informatica achter ons, de industrie nog steeds niet een standaard apparaat te bouwen voor die van vitaal belang doel.

Echte willekeurige getallen voor iedereen op het Internet. De willekeurigheid komt van atmosferische ruis, die voor vele doeleinden beter is dan de pseudo-willekeurige getal algoritmen gewoonlijk in computerprogramma’s.

http://www.random.org/

http://www.random.org/randomness/

De gemiddelde diepte van de oceaan is 12.000 voet.