Hvad er en tilfældig talgenerator?
En tilfældig talgenerator (RNG) er et system, der producerer tilfældige eller pseudotilfældige tal. Hvorvidt det næste tal reelt kan forudsiges, afhænger af generatorens type. Nogle generatorer trækker på en fysisk proces, nogle beregner deres tal ved hjælp af en algoritme, og nogle algoritmer er bygget således, at selv en person, der har set deres hidtidige resultater, ikke kan forudsige, hvad der kommer næste gang. At se tilfældig ud og at være uforudsigelig er to vidt forskellige egenskaber, og det meste af denne artikel handler netop om denne forskel.
Hardware-baserede tilfældige talgeneratorer
En hardware-baseret tilfældig talgenerator (HRNG), også kaldet en ægte tilfældig talgenerator (TRNG), henter sine tal fra en fysisk proces. De ældste foregår for øjnene af en: en kastet mønt, en rullet terning, et roulettehjul. Mekanikken beskriver hver af dem fuldstændigt, men et velkonstrueret hjul er i praksis stadig uforudsigeligt, fordi bittesmå forskelle i, hvordan hvert spin starter, vokser sig til helt forskellige udfald.
Moderne hardware-generatorer måler i stedet mikroskopiske fænomener: shot noise og termisk støj i elektroniske kredsløb, atmosfærisk støj, kvanteeffekter. Disse er fremragende kilder til entropi — uforudsigelighed, der kan måles — men en fysisk kilde er i sin natur ikke fejlfri: den kan have skævheder, den kan drive over tid, og den kan svigte, så dens kvalitet skal vurderes og overvåges, og dens værdier skal om nødvendigt efterbehandles, hvilket standarder som NIST SP 800-90B beskriver. Hardware-kilder anvendes, hvor garantien betyder mest — frem for alt i kryptografi, hvor de leverer det uforudsigelige udgangsmateriale til nøglerne bag protokoller som Transport Layer Security (TLS).
Pseudotilfældige talgeneratorer
Alternativet til en fysisk enhed er en algoritme. En pseudotilfældig talgenerator (PRNG) producerer en sekvens, der ser tilfældig ud, men som er fuldstændig bestemt af en startværdi (seed). Giver du den samme startværdi til den samme algoritme, får du nøjagtig den samme sekvens hver gang. Det er en svaghed i alle situationer, hvor et resultat skal være uforudsigeligt, og startværdien eller den interne tilstand kan gættes eller rekonstrueres, og en styrke, hvor et resultat skal kunne genskabes — en simulation eller en test kan køres igen på præcis samme måde. PRNG'er er desuden hurtige, billige og nemme at implementere, hvorfor det meste software forlader sig på dem. Kendte algoritmer omfatter den lineære kongruensgenerator (LCG), xorshift-generatorer og Mersenne Twister.
Mersenne Twister
Mersenne Twister, offentliggjort i 1997 af Makoto Matsumoto og Takuji Nishimura, er en af de mest udbredte pseudotilfældige talgeneratorer og standarden i mange programmeringssprog. Dens navn stammer fra dens periode — længden af sekvensen, før den gentager sig — som i standardvarianten MT19937 er Mersenne-primtallet 219937 − 1. Den består de fleste statistiske tests for tilfældighed og egner sig glimrende til simulationer. Den er imidlertid ikke designet til at bevare hemmeligheder: ud fra 624 på hinanden følgende 32-bit værdier kan enhver rekonstruere dens interne tilstand og forudsige enhver efterfølgende værdi, så den må ikke bruges til nøgler, adgangskoder eller andet, der skal forblive uforudsigeligt.
Kryptografisk sikre generatorer og entropi
Mange anvendelser har brug for begge dele på én gang: en algoritmes hastighed og en fysisk kildes uforudsigelighed. Svaret er en kryptografisk sikker pseudotilfældig talgenerator (CSPRNG). Det er stadig en PRNG, men en, der er bygget således, at kendskab til en del af dens resultater ikke giver nogen praktisk mulighed for at forudsige resten, og den forsynes med og genopfriskes løbende fra en kilde til ægte entropi. En startværdi fra en fysisk kilde gør ikke en almindelig PRNG sikker; selve algoritmen skal være designet til det. En fysisk kilde som termisk støj eller timing af hardwarehændelser leverer en lille mængde ægte tilfældighed, og CSPRNG'en danner ud fra den en lang række værdier med langt højere hastighed. Denne kombination er, hvad et operativsystem stiller til rådighed for programmerne, og det er, hvad man i praksis forstår ved en "tilfældig talgenerator" i dag. Den danner krypteringsnøgler, sessionstokens og adgangskoder.
Tilfældige tal i browseren
JavaScript giver en webside to indbyggede måder at hente tilfældige værdier på, og de tilhører vidt forskellige klasser. Math.random() er en almindelig PRNG: sprogstandarden overlader algoritmen til den enkelte browser og lover intet om sikkerhed — udmærket til en animation, uegnet til en lodtrækning, som nogen måtte anfægte. Den anden er Web Crypto API. Dets metode crypto.getRandomValues() returnerer kryptografisk sikre tilfældige værdier, dannet af en CSPRNG, der forsynes med entropi fra operativsystemet.
Vores online generator til tilfældige tal anvender Web Crypto API til hver eneste trækning, og tallene genereres i din browser frem for på en server. Den samme kilde driver de andre generatorer på dette websted, uanset om du slår med terninger, slår plat og krone eller genererer en adgangskode.
Fra tilfældige bits til et tal i dit interval
En kryptografisk sikker generator er kun halvdelen af en retfærdig lodtrækning. Den leverer rå bits, og programmet skal stadig omsætte dem til et tal i dit interval — og det er her, der kan snige sig ulighed ind. Forestil dig, at kilden giver værdierne 0 til 9 med lige store chancer, og du har brug for et tal fra 0 til 5. At tage resten efter division med 6 virker oplagt, men 0, 1, 2 og 3 kan så hver forekomme på to måder, mens 4 og 5 kun kan på én måde, så tallene 0 til 3 hver har 20 % chance, og 4 og 5 kun 10 % hver. En måde at fjerne denne ulighed på er at kassere de værdier, der falder udenfor, og trække igen; artiklerne om tilfældige talgeneratorer går i dybden med dette.
Yderligere to ting overrasker ofte folk. Gentagelser er helt normale: når et heltal fra 1 til 10 trækkes uafhængigt, og hvert tal er lige sandsynligt, har det netop udtrukne tal nøjagtig samme chance på 1 ud af 10 for at blive trukket igen som ethvert andet tal. En lodtrækning uden gentagelser er en anden form for trækning, ikke en mere tilfældig en. Og en retfærdig generator alene gør ikke hele proceduren retfærdig: deltagerlisten og antallet af forsøg betyder lige så meget, som vores artikel om, hvordan man vælger en tilfældig vinder af konkurrencen, forklarer.