Tallgenerator

En tilfeldig tallgenerator (RNG - Random Number Generator) er et system eller en prosess designet for å produsere et fullstendig uforutsigbart tall hver gang den utløses. Per definisjon er det umulig å identifisere et mønster eller forutsi fremtidige utdata basert på tidligere genererte tall. Disse tilfeldige verdiene kan produseres ved hjelp av enten avanserte matematiske algoritmer eller spesialiserte maskinvareenheter.

Bruksområder for tilfeldige tallgeneratorer

Å generere tilfeldige tall er essensielt for en lang rekke oppgaver, alt fra hverdagslige programvareapplikasjoner til komplekse dataspill. For eksempel bruker nettsider tilfeldige tallgeneratorer for å dynamisk vise tilfeldige bannerannonser eller blande innhold. Innen cybersikkerhet er kryptografi sterkt avhengig av tilfeldige tall for å lage unike og svært sikre chiffer og krypteringsnøkler.

Generelt sett brukes generering av tilfeldige tall til å lage captcha-er, kryptere sensitiv data, generere kryptografiske "salts" for sikker lagring av passord, og drive tilfeldige passordgeneratorer. Det er også ryggraden i stokkealgoritmer for kortspill på nettkasinoer, automatiserte beslutningsprosesser, statistisk prøvetaking og datasimuleringer.

I spillindustrien spiller algoritmer for tilfeldige tallgeneratorer en kritisk rolle i å holde spillopplevelsen frisk og uforutsigbar. Selv om du spiller nøyaktig samme nivå på nytt, sørger en RNG for at opplevelsen aldri blir identisk. Mens selve kartet eller oppdraget kanskje forblir uendret, dikterer tilfeldighetene hvor ofte og hvor fiender dukker opp, dynamiske værendringer og fremkomsten av plutselige hindringer. Dette laget av uforutsigbarhet er det som gjør spill spennende og gir dem høy gjenspillingsverdi.

Forskjellen mellom tilfeldige og ikke-tilfeldige sekvenser

Tenk over følgende tallsekvens: 1 , 2 , 3 , 4 , 5. Er denne virkelig tilfeldig?

I statistikk antar en tilfeldig variabel en spesifikk verdi som et resultat av et uavhengig forsøk. Det avgjørende er at det er umulig å forutsi med nøyaktighet når en bestemt verdi vil opptre før den faktisk dukker opp.

Anta at sekvensen ovenfor ble generert rett og slett ved å skrive bortover den øverste tallraden på et standard tastatur. I denne sammenhengen er kombinasjonen overhodet ikke tilfeldig. Hvorfor? Fordi etter tallet 5 kan det påfølgende tallet, 6, forutsies med nesten absolutt sikkerhet.

En sekvens regnes bare som virkelig tilfeldig dersom det er null avhengighet mellom de individuelle symbolene eller tallene.

Den grunnleggende forutsetningen for en rettferdig og funksjonell tilfeldig tallgenerator, er at alle mulige tall må ha nøyaktig like stor sannsynlighet for å bli valgt. Dette garanterer fullstendig uavhengighet; det nåværende utfallet påvirkes ikke av tallene som ble generert før det, og det vil heller ikke påvirke tallene som genereres etterpå.

For eksempel, når du kaster en rettferdig sekssidet terning for første gang, har alle tall fra 1 til 6 like stor sannsynlighet for å lande med forsiden opp. Uavhengig av det første resultatet, vil sjansene for å få nøyaktig det samme tallet forbli helt uendret når du kaster terningen for andre, hundrede eller tusende gang.

For mange fremstår den uendelige sekvensen av sifre i den matematiske konstanten Pi (π) som fullstendig tilfeldig og ikke-repeterende. Anta at en hypotetisk generator baserer seg på bit-representasjonen av Pi, fra og med et hemmelig desimalpunkt. En slik generator kan virke uforutsigbar for den gjennomsnittlige brukeren og kan til og med bestå visse statistiske tilfeldighetstester. Imidlertid er det utrolig risikabelt å stole på Pi for kryptografi. Hvis en angriper oppdager akkurat det segmentet av Pi som brukes, kan de enkelt forutsi alle foregående og etterfølgende sifre, og dermed kompromittere systemets sikkerhet umiddelbart.

For å sikre høye sikkerhetsstandarder, introduserte U.S. National Institute of Standards and Technology (NIST) "Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications". Denne robuste pakken inneholder 15 unike statistiske tester designet for å matematisk måle den sanne tilfeldigheten til bits produsert av både maskinvare- og programvaregeneratorer.

Typer tilfeldige tallgeneratorer

Generelt finnes det to hovedtyper av tilfeldige tallgeneratorer: Sanne tilfeldige tallgeneratorer (TRNG) og Pseudotilfeldige tallgeneratorer (PRNG). Mens TRNG-er lener seg på uforutsigbare fysiske fenomener for å generere tall, er PRNG-er utelukkende basert på matematiske algoritmer.

En sann tilfeldig tallgenerator (TRNG - True Random Number Generator) benytter seg av spesialiserte maskinvareenheter som fanger opp mikroskopiske fysiske prosesser for å generere tilfeldige tall. Denne fysiske uforutsigbarheten kalles entropi – det matematiske målet på rent, ufiltrert kaos.

Sanne tilfeldige tallgeneratorer høster entropi fra svært uforutsigbare fysiske fenomener, slik som:

• radioaktivitet,
• termisk støy,
• elektromagnetisk støy,
• kvantemekanikk og annet.

På grunn av deres absolutte uforutsigbarhet, er sanne RNG-er selve gullstandarden for høysikkerhetsapplikasjoner, sikker kommunikasjon og avansert datakryptering over hele verden.

Disse maskinvarebaserte systemene bruker eksterne entropikilder for å samle inn uforutsigbar data, som danner den initielle hemmelige verdien (kjent som en "seed" eller et frø) som kreves for å trygt generere sikre, tilfeldige tall.

I kontrast brukes en pseudotilfeldig tallgenerator-algoritme (PRNG - Pseudorandom Number Generator) vanligvis i miljøer der streng kryptografisk sikkerhet ikke er førsteprioritet. I stedet brukes denne typen tilfeldighet til å forhindre repetisjon og skape engasjerende brukeropplevelser. Å implementere PRNG-teknologi er betydelig raskere og mer kostnadseffektivt fordi det ikke krever ekstern maskinvare og sømløst kan integreres i standard programkode. Selv om utdataen er fullstendig deterministisk og basert på en bestemt algoritme, er den perfekt egnet for videospill, simuleringer og grunnleggende programvareapplikasjoner.

En PRNG er avhengig av en enkelt initiell frøverdi for matematisk å utlede sin pseudo-tilfeldige sekvens. En TRNG, derimot, genererer kontinuerlig høykvalitets tilfeldige tall ved hele tiden å hente fersk entropi fra uforutsigbare fysiske kilder.

Pseudotilfeldig tallgenerering har imidlertid klare sårbarheter. Disse algoritmene er effektive kun fordi utdataene deres ser tilfeldige ut for det utrente øyet. Men hvis en person oppdager den initielle frøverdien som ble brukt for en spesifikk PRNG-sekvens, kan de forutsi med perfeksjon hvert eneste påfølgende tall som vil bli generert.

"Speedrunnere" – entusiaster som har som mål å fullføre videospill så raskt som mulig – utnytter ofte akkurat denne sårbarheten i en teknikk kjent som "RNG-manipulasjon". Ved å dekonstruere frøverdien, kan de tvinge spillet til å oppføre seg forutsigbart og dermed spare verdifull tid. I spillverdenen er denne manipulasjonen ufarlig og forårsaker sjelden kritiske problemer.

I cybersikkerhetsverdenen er imidlertid evnen til å forutsi tilfeldige tall katastrofal – spesielt når det gjelder generering av kryptografiske sikkerhetsnøkler.

Hvis en ondsinnet angriper oppdager den initielle frøverdien som brukes til å generere RSA-nøkler for TLS-sertifikater, kan de potensielt dekryptere sikker nettverkstrafikk. Dette betyr at de enkelt kan fange opp passord, finansielle data og annen svært sensitiv personlig informasjon som overføres via internett.

I slike kritiske scenarioer er en eksepsjonelt sikker metode for å skaffe tilfeldige tall – nemlig en sann tilfeldig tallgenerator – helt avgjørende.

Googles generator

Google tilbyr sitt eget innebygde verktøy for generering av tilfeldige tall, drevet av JavaScript. Dette lett tilgjengelige verktøyet er utrolig nyttig for raske, hverdagslige oppgaver, som for eksempel å kaste virtuelle terninger under brettspill med venner og familie. Du får enkelt tilgang til denne integrerte PRNG-en bare ved å skrive inn søkeordet "random number generator" (eller "tilfeldig tallgenerator") direkte i Google.

Den lineære kongruente metoden

En av de eldste og mest anerkjente algoritmene for pseudotilfeldige tallgeneratorer er den lineære kongruente metoden (LCM) eller den lineære kongruente generatoren (LCG). Denne algoritmen ble foreslått av Derrick Henry Lehmer i 1949, og er perfekt egnet for enkle applikasjoner uten kritiske sikkerhetskrav, selv om den ikke har noen form for kryptografisk styrke.

For å kunne generere en sekvens av tall med denne matematiske modellen, må du definere fire nøkkelparametere:

m > 0, modulo

0 ≤ a ≤ m, multiplikatoren

0 ≤ c ≤ m, inkrementet

0 ≤ X₀ ≤ m, det initielle tallet

Selve den pseudotilfeldige tallsekvensen beregnes rekursivt ved hjelp av følgende matematiske formel:

Xₙ₊₁ = (aXₙ + c) mod m

Det er svært viktig å merke seg at effektiviteten og den oppfattede tilfeldigheten av denne metoden avhenger helt og holdent av et nøye utvalg av disse startparameterne.

For eksempel, hvis vi bruker følgende dårlig valgte parametersett:

X₀ = 3, a = 4, c = 5, m = 6

ender vi opp med å generere en svært repeterende sekvens med kort sløyfe bestående av:

3, 5, 1, 3, 5, 1

noe som åpenbart ikke ser tilfeldig ut i det hele tatt.

Hvis vi imidlertid endrer parameterne til et mye større og mer nøye utvalgt sett:

X₀ = 2, a = 85, c = 507, m = 1356

Blir fordelingen av resultatene umiddelbart mye mer uforutsigbar og jevn. Dette illustrerer tydelig hvorfor du må velge frø-tallene for denne algoritmiske generatoren med ekstrem forsiktighet:

2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365...

Selv om en godt optimalisert lineær kongruent generator kan produsere en statistisk akseptabel pseudotilfeldig sekvens, er den fundamentalt sårbar. Fordi LCG-er i seg selv er forutsigbare hvis parameterne er kjente eller kan observeres, mangler de kryptografisk robusthet og må aldri brukes til å sikre sensitiv data.

Generatorer basert på lineære kongruente metoder ble først vellykket knekt av Jim Reeds i 1977, og deretter av Joan Boyar i 1982 (som også klarte å kompromittere kvadratiske og kubiske generatorer). Deres forskning beviste utvetydig at kongruente algoritmer er fundamentalt ubrukelige for moderne kryptografi. Til tross for disse sikkerhetsfeilene, forblir imidlertid LCG-er svært verdifulle for ikke-kryptografiske applikasjoner som vitenskapelige simuleringer og statistisk modellering. De er beregningsmessig effektive og fortsetter å vise utmerket statistisk ytelse på tvers av ulike empiriske tester.

Moderne maskinvarebaserte tilfeldige tallgeneratorer

QRBG121

QRBG121 utnytter sann kvantetilfeldighet. Enheten er utelukkende avhengig av den kvantefysiske prosessen med fotonutslipp i halvledere og den påfølgende deteksjonen av disse individuelle fotonene. Fordi fotoner slippes ut og oppdages helt tilfeldig og uavhengig av hverandre, kan den nøyaktige tidsinformasjonen til disse mikroskopiske hendelsene pålitelig konverteres til svært sikre tilfeldige bits.

Lavalamper

Cloudflares hovedkvarter i San Francisco er berømt for å bruke en vegg av klassiske "lavalamper" som en svært effektiv entropikilde. En tradisjonell lavalampe består av en glassbeholder fylt med gjennomsiktig olje og gjennomsiktig voks (parafin). Voksen er naturlig tykkere enn oljen, men etter hvert som den varmes forsiktig opp av en lyspære i bunnen, blir den mindre tett, stiger, kjøles ned og synker igjen i en kontinuerlig, fascinerende syklus.

Fordi fluiddynamikk er utrolig kaotisk, er den kontinuerlige bevegelsen til væskene praktisk talt umulig å forutsi. Flere høyoppløselige kameraer tar kontinuerlig øyeblikksbilder av denne skiftende veggen av lavalamper. Pikseldataene fra disse høyst kaotiske bildene mates inn i en datamaskin som konverterer den visuelle støyen til sikre krypteringsnøkler.

Cloudflares andre internasjonale kontorer benytter også geniale fysiske entropikilder. I London fanger kameraer opp de dypt uforutsigbare bevegelsene til et kaotisk system bestående av tre pendler. Samtidig stoler kontoret i Singapore på en geigerteller for å måle det radioaktive henfallet til en ufarlig uranklump. Uran fungerer som en ideell "datakilde" fordi det nøyaktige øyeblikket et enkelt radioaktivt atom bestemmer seg for å henfalle, fundamentalt sett er en tilfeldig kvantemekanisk handling.

HotBits

HotBits er en nettbasert tjeneste som tilbyr sanne tilfeldige tall generert av en maskinvarebasert geigerteller som registrerer ioniserende bakgrunnsstråling. Brukere kan ganske enkelt fylle ut et forespørselsskjema på HotBits-nettsiden, spesifisere ønsket antall tilfeldige bytes og velge en leveringsmetode. For å sikre maksimal kryptografisk sikkerhet, blir de forespurte tilfeldige tallene permanent slettet fra HotBits-systemet i det øyeblikket de leveres til brukeren.

Vakuum-kvantefluktuasjoner

I motsetning til sitt latinske opphav ("vacuus" som betyr tom), er et fysisk vakuum aldri helt tomt. Styrt av Heisenbergs uskarphetsrelasjon i kvantemekanikken, er et vakuum et kaotisk rom der subatomære "virtuelle partikler" konstant spretter ut og inn av eksistens.

Ved å utnytte dette fenomenet har kanadiske fysikere konstruert en lynrask, strukturelt elegant tilfeldig tallgenerator utelukkende basert på vakuumfluktuasjoner. Systemet benytter en høyfrekvent pulserende laser, et tett brytende medium (for eksempel en diamant), og en ekstremt sensitiv fotondetektor. Mens laserpulsene passerer gjennom diamanten, blir de presise egenskapene til hver puls unikt endret av de uforutsigbare kvantemekaniske vakuumfluktuasjonene som oppstår langs fotonenes bane.

Etter hvert som strålingen spres, dukker det opp unike spektrallinjer. Siden de underliggende vakuumfluktuasjonene er forankret i rent kvantekaos, endres egenskapene til disse spektrallinjene på helt uforutsigbare og urepeterbare måter hver eneste gang – noe som resulterer i absolutt tilfeldighet.

Karbonnanorør-generator

Denne banebrytende metoden kombinerer elegant mikroskopisk fysisk kompakthet med uforutsigbarheten til termisk støy.

Forskere har lykkes med å bygge en sann tilfeldig tallgenerator ved hjelp av en statisk RAM-celle (SRAM). Det som gjør dette revolusjonerende, er at minnecellen er trykt med spesialisert elektronisk blekk formulert med halvledende karbonnanorør. Det fysiske systemet høster deretter fluktuasjoner fra omgivende termisk støy i disse nanorørene for konsekvent å generere sanne tilfeldige bits.

Fordi denne karbonnanorør-generatoren kan trykkes direkte på fleksible plastunderlag, åpner den døren for massiv innovasjon. Den kan sømløst integreres i miniatyrisert fleksibel elektronikk, kroppsbårne sensorer for helseovervåking, billige engangs sikkerhetsetiketter og til og med smarte klesplagg.

Terninger og Electronic Frontier Foundation (EFF)

The Electronic Frontier Foundation (EFF) har foreslått en utrolig enkel og lavteknologisk måte å generere svært sikre kryptografiske passord på ved å bruke en fysisk TRNG: standard sekssidige terninger.

Du kaster for eksempel fem terninger samtidig og noterer resultatene fra venstre til høyre. Hvis terningene lander på 6, 3, 1, 3 og 1, blir den endelige tallrekken din 63131. Deretter slår du opp i den offisielle EFF Diceware-ordlisten på nettsidene deres for å finne det spesifikke ordet som er tildelt 63131. I dette tilfellet er ordet "turbofan".

Deretter gjentar du hele prosedyren flere ganger – vanligvis fem eller seks – for å lage en sikker "passordfrase" bestående av flere tilfeldige ord. Det endelige resultatet kan se omtrent slik ut: "turbofan purge unfitting try pruning". Fordi frasen er generert av ren fysisk entropi, er den matematisk sikker mot "brute-force"-angrep. Videre gjør enkle mnemotekniske hukommelsesteknikker disse levende, tilfeldige frasene overraskende enkle for mennesker å huske.

En kvantebasert tilfeldig tallgenerator fra en Nokia-smarttelefon

I en imponerende oppvisning av oppfinnsomhet demonstrerte forskere ved Universitetet i Genève i 2014 at en vanlig forbrukerenhet kunne fungere som en kvantebasert tilfeldig tallgenerator (QRNG), spesifikt ved å utnytte det innebygde kameraet på en standard Nokia N9-smarttelefon.

Konseptet var overraskende elegant: Kamerasensoren i smarttelefonen fikk et nytt formål: å telle det nøyaktige antallet lyspartikler (fotoner) som traff hver enkelt piksel, ved å bruke en standard LED som primær lyskilde. På bare ett mikrosekund oppdaget hver eneste piksel over 8-megapiksel sensoren omtrent 400 fotoner. Ved å fange inn disse massive, uforutsigbare kvante-lysdataene på tvers av millioner av piksler samtidig, klarte forskerne å trekke ut en tett, høyst sikker sekvens av rene, tilfeldige tall.