Talgenerator

En tilfældig talgenerator (på engelsk Random Number Generator eller RNG) er et system eller en proces, der er designet til at producere et fuldstændig uforudsigeligt tal, hver gang den aktiveres. Per definition er det umuligt at identificere et mønster eller forudsige fremtidige resultater baseret på tidligere genererede tal. Disse tilfældige værdier kan produceres ved hjælp af enten avancerede matematiske algoritmer eller specialiserede hardwareenheder.

Anvendelser af tilfældige talgeneratorer

Generering af tilfældige tal er afgørende for en lang række opgaver, lige fra hverdagens softwareapplikationer til komplekse computerspil. For eksempel bruger hjemmesider tilfældige talgeneratorer til dynamisk at vise tilfældige bannerreklamer eller blande indhold. Inden for cybersikkerhed er kryptografi stærkt afhængig af tilfældige tal for at skabe unikke og yderst sikre ciffersystemer og krypteringsnøgler.

Generelt set bruges generering af tilfældige tal til at oprette captcha'er, kryptere følsomme data, generere kryptografiske "salts" til sikker opbevaring af adgangskoder og drive tilfældige adgangskodegeneratorer. Det er også rygraden i blandingsalgoritmer til online casinokortspil, automatiseret beslutningstagning, statistisk stikprøveudtagning og computersimuleringer.

I spilindustrien spiller RNG-algoritmer en kritisk rolle i at holde spiloplevelsen frisk og uforudsigelig. Selvom du spiller den nøjagtig samme bane igen, sikrer en RNG, at oplevelsen aldrig er identisk. Mens selve kortet eller missionen måske forbliver uændret, dikterer tilfældigheder hvor og hvor ofte fjender dukker op (spawn rates), dynamiske vejrskift og fremkomsten af pludselige forhindringer. Dette lag af uforudsigelighed er det, der holder spil spændende og giver dem høj genspilningsværdi.

Forskellen mellem tilfældige og ikke-tilfældige sekvenser

Overvej følgende talsekvens: 1 , 2 , 3 , 4 , 5. Er dette virkelig tilfældigt?

I statistik antager en tilfældig variabel en specifik værdi som et resultat af et uafhængigt forsøg. Det afgørende er, at det er umuligt præcist at forudsige forekomsten af en bestemt værdi, før den faktisk vises.

Antag, at ovenstående sekvens blev genereret simpelthen ved at skrive hen over den øverste talrække på et standardtastatur. I denne kontekst er kombinationen fuldstændig ikke-tilfældig. Hvorfor? Fordi efter tallet 5 kan det efterfølgende tal, 6, forudsiges med næsten absolut sikkerhed.

En sekvens betragtes kun som ægte tilfældig, hvis der er nul afhængighed mellem dens individuelle symboler eller tal.

Den grundlæggende betingelse for en retfærdig og funktionel tilfældig talgenerator er, at alle mulige tal skal have en absolut lige stor sandsynlighed for at blive valgt. Dette garanterer fuldstændig uafhængighed; det aktuelle udfald påvirkes hverken af de tal, der blev genereret før det, eller påvirker de tal, der genereres efter det.

For eksempel, når du kaster en retfærdig sekssidet terning for første gang, har ethvert tal fra 1 til 6 lige stor sandsynlighed for at lande med forsiden opad. Uanset dit indledende resultat forbliver dine chancer for at få nøjagtig det samme tal fuldstændig uændrede, når du kaster terningen for anden, hundrede eller tusinde gang.

For mange fremstår den uendelige sekvens af cifre i den matematiske konstant Pi (π) som fuldstændig tilfældig og ikke-gentagende. Antag, at en hypotetisk generator er afhængig af bit-repræsentationen af Pi, startende fra et hemmeligholdt decimalpunkt. En sådan generator kan virke uforudsigelig for den gennemsnitlige bruger og kan endda bestå visse statistiske tests for tilfældighed. Imidlertid er det utroligt risikabelt at stole på Pi til kryptografi. Hvis en angriber opdager det specifikke segment af Pi, der bruges, kan de let forudsige alle foregående og efterfølgende cifre og øjeblikkeligt kompromittere systemets sikkerhed.

For at sikre høje sikkerhedsstandarder introducerede det amerikanske National Institute of Standards and Technology (NIST) "Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications." Denne robuste suite indeholder 15 unikke statistiske tests designet til matematisk at måle den sande tilfældighed af bits produceret af både hardware- og softwaregeneratorer.

Typer af tilfældige talgeneratorer

Generelt findes der to primære typer af tilfældige talgeneratorer: Ægte tilfældige talgeneratorer (TRNG) og Pseudotilfældige talgeneratorer (PRNG). Mens TRNG'er er afhængige af uforudsigelige fysiske fænomener til at generere tal, er PRNG'er udelukkende baseret på matematiske algoritmer.

En ægte tilfældig talgenerator (TRNG) er afhængig af specialiserede hardwareenheder, der opfanger mikroskopiske fysiske processer for at generere tilfældige tal. Denne fysiske uforudsigelighed kaldes entropi – den matematiske måleenhed for rent, ufiltreret kaos.

Ægte tilfældige talgeneratorer høster entropi fra stærkt uforudsigelige fysiske fænomener, såsom:

• radioaktivitet,
• termisk støj,
• elektromagnetisk støj,
• kvantemekanik og andre.

På grund af deres absolutte uforudsigelighed er ægte RNG'er den gyldne standard for højsikkerhedsapplikationer, sikker kommunikation og avanceret datakryptering over hele verden.

Disse hardwarebaserede systemer bruger eksterne entropikilder til at indsamle uforudsigelige data, som danner den indledende hemmelige værdi (kendt som et "seed"), der kræves for sikkert at generere sikre tilfældige tal.

Til gengæld bruges en pseudotilfældig talgenerator (PRNG) algoritme typisk i miljøer, hvor streng kryptografisk sikkerhed ikke er en primær bekymring. I stedet bruges denne type tilfældighed til at forhindre gentagelser og skabe engagerende brugeroplevelser. Implementering af PRNG-teknologi er væsentligt hurtigere og mere omkostningseffektivt, fordi det ikke kræver ekstern hardware og kan integreres problemfrit i standard programkode. Selvom outputtet er fuldstændig deterministisk og baseret på en fastsat algoritme, er det perfekt egnet til videospil, simuleringer og grundlæggende softwareapplikationer.

En PRNG er afhængig af en enkelt indledende seed-værdi for at udlede sin pseudo-tilfældige sekvens matematisk. Omvendt genererer en TRNG kontinuerligt højkvalitets tilfældige tal ved konstant at trække frisk entropi fra uforudsigelige fysiske kilder.

Generering af pseudotilfældige tal har dog markante sårbarheder. Disse algoritmer er kun effektive, fordi deres output virker tilfældige for det utrænede øje. Men hvis en person opdager den indledende seed-værdi, der bruges til en bestemt PRNG-sekvens, kan de perfekt forudsige ethvert efterfølgende tal, der vil blive genereret.

"Speedrunners" – entusiaster der har til formål at gennemføre videospil så hurtigt som muligt – udnytter ofte præcis denne sårbarhed i en teknik kendt som "RNG-manipulation." Ved at reverse-engineere seedet kan de tvinge spillet til at opføre sig forudsigeligt og derved spare værdifuld tid. Inden for gaming er denne manipulation harmløs og forårsager sjældent kritiske problemer.

I cybersikkerhedens verden er evnen til at forudsige tilfældige tal imidlertid katastrofal – især når det gælder generering af kryptografiske sikkerhedsnøgler.

Hvis en ondsindet hacker opdager den indledende seed-værdi, der bruges til at generere RSA-nøgler til TLS-certifikater, vil de potentielt kunne dekryptere sikker netværkstrafik. Det betyder, at de nemt kan opsnappe adgangskoder, finansielle data og andre stærkt følsomme personoplysninger, der transmitteres over internettet.

I disse kritiske scenarier er en usædvanlig sikker metode til at anskaffe tilfældige tal – nemlig en ægte tilfældig talgenerator – absolut essentiel.

Googles generator

Google tilbyder sit eget indbyggede værktøj til generering af tilfældige tal, som er drevet af JavaScript. Dette lettilgængelige værktøj er utrolig nyttigt til hurtige hverdagsopgaver, såsom at kaste virtuelle terninger under brætspil med venner og familie. Du kan nemt få adgang til denne indbyggede PRNG ved blot at skrive søgningen "random number generator" direkte i Google.

Den lineære kongruensmetode

En af de ældste og mest anerkendte algoritmer til pseudotilfældige talgeneratorer er den lineære kongruensmetode (LCM) eller lineære kongruensgenerator (LCG). Denne algoritme blev foreslået af Derrick Henry Lehmer i 1949 og er perfekt egnet til simple, ikke-sikkerhedskritiske applikationer, selvom den absolut ingen kryptografisk styrke har.

For med succes at generere en talsekvens ved hjælp af denne matematiske model, skal du definere fire nøgleparametre:

m > 0, modulo

0 ≤ a ≤ m, multiplikatoren

0 ≤ c ≤ m, inkrementet

0 ≤ X₀ ≤ m, det indledende tal

Selve den pseudotilfældige talsekvens beregnes rekursivt ved hjælp af følgende matematiske formel:

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

Det er meget vigtigt at bemærke, at denne metodes effektivitet og opfattede tilfældighed afhænger fuldstændigt af et omhyggeligt valg af disse indledende parametre.

For eksempel, hvis vi bruger følgende dårligt valgte parametersæt:

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

ender vi med at generere en stærkt gentagende sekvens med et kort loop, nemlig

3, 5, 1, 3, 5, 1

hvilket tydeligvis slet ikke ser tilfældigt ud.

Men hvis vi ændrer parametrene til et meget større og mere omhyggeligt udvalgt sæt:

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

Fordelingen af resultater bliver øjeblikkeligt meget mere uforudsigelig og ensartet. Dette illustrerer tydeligt, hvorfor man skal vælge seed-tallene til denne algoritmiske generator med ekstrem stor omhu:

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...

Selvom en veloptimeret lineær kongruensgenerator kan producere en statistisk acceptabel pseudotilfældig sekvens, er den fundamentalt sårbar. Fordi LCG'er i sagens natur er forudsigelige, hvis parametrene er kendte eller observeres, mangler de kryptografisk robusthed og må aldrig bruges til at sikre følsomme data.

Generatorer, der baserede sig på lineære kongruensmetoder, blev først knækket med succes af Jim Reeds i 1977, og efterfølgende af Joan Boyar i 1982 (som også formåede at kompromittere kvadratiske og kubiske generatorer). Deres forskning beviste afgørende, at kongruensalgoritmer er fundamentalt ubrugelige til moderne kryptografi. På trods af disse sikkerhedsbrister forbliver LCG'er dog yderst værdifulde til ikke-kryptografiske applikationer, såsom videnskabelige simuleringer og statistisk modellering. De er beregningsmæssigt effektive og demonstrerer fortsat fremragende statistisk ydeevne på tværs af forskellige empiriske tests.

Moderne hardware-baserede tilfældige talgeneratorer

QRBG121

QRBG121 udnytter ægte kvantetilfældighed. Enheden er fuldstændig afhængig af den kvantefysiske proces, der indebærer udsendelse af fotoner i halvledere, og den efterfølgende detektion af disse individuelle fotoner. Fordi fotoner udsendes og detekteres fuldstændig tilfældigt og uafhængigt af hinanden, kan den præcise tidsinformation fra disse mikroskopiske begivenheder pålideligt konverteres til stærkt sikre, tilfældige bits.

Lavalamper

Cloudflares hovedkvarter i San Francisco er berømt for at bruge en væg af klassiske "lavalamper" som en yderst effektiv entropikilde. En traditionel lavalampe består af en glasbeholder fyldt med gennemsigtig olie og gennemskinnelig voks (paraffin). Voksen har naturligvis en højere massefylde end olien, men når den opvarmes forsigtigt af en pære i bunden, bliver den mindre tæt, stiger op, køler af og synker ned i en kontinuerlig, fascinerende cyklus.

Fordi strømningsdynamik er utroligt kaotisk, er væskernes kontinuerlige bevægelse stort set umulig at forudsige. Flere højopløsningskameraer tager konstant billeder af denne foranderlige væg af lavalamper. Pixeldataene fra disse stærkt kaotiske snapshots fodres ind i en computer, der konverterer den visuelle støj til sikre krypteringsnøgler.

Cloudflares andre internationale kontorer anvender også geniale fysiske entropikilder. I London fanger kameraer de dybt uforudsigelige bevægelser i et kaotisk tre-pendul-system. Samtidig er kontoret i Singapore afhængig af en geigertæller til at måle det radioaktive henfald af en harmløs uranpille. Uran fungerer som en ideel "datakilde", fordi det præcise øjeblik, ethvert enkelt radioaktivt atom beslutter sig for at henfalde, grundlæggende er en tilfældig handling i kvantemekanikken.

HotBits

HotBits er en onlinetjeneste, der leverer ægte tilfældige tal, genereret af en hardware-geigertæller, der registrerer baggrunds-ioniserende stråling. Brugere kan simpelthen udfylde en anmodningsformular på HotBits' hjemmeside, angive deres ønskede antal tilfældige bytes og vælge en leveringsmetode. For at sikre maksimal kryptografisk sikkerhed bliver de anmodede tilfældige tal slettet permanent fra HotBits-systemet i det øjeblik, de leveres til brugeren.

Kvantefluktuationer i vakuum

I modsætning til dets latinske rod ("vacuus", som betyder tom), er et fysisk vakuum aldrig helt tomt. Styret af Heisenbergs ubestemthedsrelation inden for kvantemekanikken, er et vakuum et kaotisk rum, hvor subatomare "virtuelle partikler" konstant opstår og forsvinder.

Ved at udnytte dette fænomen har canadiske fysikere udviklet en lynhurtig og strukturelt elegant tilfældig talgenerator udelukkende baseret på vakuumfluktuationer. Systemet udnytter en højfrekvent pulserende laser, et tæt brydningsmedium (såsom en diamant) og en ekstremt følsom fotondetektor. Efterhånden som laserimpulserne passerer gennem diamanten, ændres de præcise karakteristika for hver puls unikt af de uforudsigelige kvantevakuumfluktuationer, som fotonerne støder på undervejs.

Efterhånden som strålingen spredes, opstår der unikke spektrallinjer. Da de underliggende vakuumfluktuationer er rodfæstet i rent kvantekaos, ændres egenskaberne af disse spektrallinjer på helt uforudsigelige og ikke-gentagbare måder hver eneste gang – hvilket resulterer i absolut tilfældighed.

Generator af kulstofnanorør

Denne banebrydende metode kombinerer elegant mikroskopisk fysisk kompakthed med uforudsigeligheden ved termisk støj.

Forskere har med succes bygget en ægte tilfældig talgenerator ved hjælp af en SRAM-celle (Static Random-Access Memory). Det revolutionerende ved dette er, at hukommelsescellen er printet ved hjælp af specialiserede elektroniske blæktyper formuleret med halvledende kulstofnanorør. Det fysiske system høster derefter termiske støjfluktuationer fra omgivelserne inden i disse nanorør for konsekvent at generere ægte tilfældige bits.

Fordi denne kulstofnanorørsgenerator kan printes direkte på fleksible plastiksubstrater, åbner det døren for massiv innovation. Det kan problemfrit integreres i miniaturiseret fleksibel elektronik, sundhedssporende wearables, billige engangssikkerhedsetiketter og endda smart tøj.

Terninger og Electronic Frontier Foundation (EFF)

Electronic Frontier Foundation (EFF) har foreslået en utrolig simpel lavteknologisk metode til at generere stærkt sikre kryptografiske adgangskoder ved hjælp af en fysisk TRNG: standard sekssidede terninger.

For eksempel kaster du fem terninger på samme tid og noterer de resulterende tal fra venstre mod højre. Hvis terningerne lander på 6, 3, 1, 3 og 1, er din endelige streng 63131. Dernæst slår du op i den officielle EFF Diceware-ordliste på deres hjemmeside for at finde det specifikke ord, der er tildelt 63131. I dette tilfælde er ordet "turbofan".

Du gentager derefter hele denne procedure flere gange – typisk fem eller seks – for at skabe en sikker "adgangssætning" (passphrase) bestående af flere tilfældige ord. Det endelige resultat kan se ud som: "turbofan purge unfitting try pruning". Fordi sætningen genereres gennem ren fysisk entropi, er den matematisk sikker mod brute force-angreb. Derudover gør grundlæggende mnemotekniske hukommelsesteknikker, at disse levende og tilfældige sætninger er overraskende nemme for mennesker at huske.

En kvantebaseret tilfældig talgenerator fra en Nokia-smartphone

I en imponerende opvisning af opfindsomhed demonstrerede forskere ved universitetet i Genève i 2014, at en almindelig forbrugerenhed kunne fungere som en kvantebaseret tilfældig talgenerator (QRNG), specifikt ved at bruge det indbyggede kamera i en standard Nokia N9-smartphone.

Konceptet var overraskende elegant: smartphonens kamerasensor blev ombygget til at tælle det nøjagtige antal lyspartikler (fotoner), der ramte hver enkelt pixel, ved hjælp af en standard LED som den primære lyskilde. På bare et mikrosekund opfangede hver eneste pixel på tværs af 8-megapixel sensoren cirka 400 fotoner. Ved at indfange denne massive mængde uforudsigelige kvantelysdata på tværs af millioner af pixels samtidigt, udtrak forskerne med succes en tæt og meget sikker sekvens af rent tilfældige tal.