Slumptalsgenerator
En slumptalsgenerator är en algoritm eller fysisk enhet som är avsedd att generera en sekvens av element (ofta tal) som kan användas som en slumpmässig sekvens. Det har funnits metoder för att generera slumpmässiga resultat i tusentals år, i form av tärningskast eller myntkast, blandande av spelkort, och liknande. Ett vanligt test för slumpmässighet för sådana sekvenser är att försöka förvissa sig om att sekvensen inte har några mönster, eller mindre rigoröst att sekvensen inte har några enkelt skönjbara mönster.
"Riktiga" slumptal kontra pseudoslumptal
[redigera | redigera wikitext]Det är svårt att skilja en "riktig" slumptalssekvens från något annat eftersom själva konceptet slumpmässighet är svårdefinierat. Vad som är allmänt känt är att varje "slumptalsgenerator" som enbart använder sig av deterministiska algoritmer inte kan betraktas som en "riktig" slumptalsgenerator, eftersom dess slumptalssekvens alltid är förutsägbar. John von Neumann sade "Den som använder aritmetiska metoder för att producera slumptal är en syndare"[1], vilket sammanfattar situationen koncist.
Slumptal i datorvärlden
[redigera | redigera wikitext]Mjukvarubaserade
[redigera | redigera wikitext]Operativsystem i Internets barndom som Windows 95 hade helt mjukvarubaserade slumptalsgeneratorer. Dessa funktioner initierades med datorns realtidsklocka på mikrosekundnivå. Detta var tillräckligt för datorspel, men inte för säkra slumptal. En vanlig teknik vid kryptering är att sändare och mottagare kommer överens om en hemlig krypteringsnyckel och sedan använder en slumptalsgenerator med denna nyckel som frö för att kryptera och dekryptera information. Genom att tiden för en kommunikation på Internet var känd kunde en hackare veta ungefär vad datorns klocka var och på så sätt knäcka slumpmässiga krypteringar[2].
Slumptalsalstring från fysikaliska processer
[redigera | redigera wikitext]90-talets erfarenheter hur enkelt det var att förutsäga slumpmässig kryptering på Internet gör att det råder allmän överenskommelse om att om datorer ska generera oförutsägbara slumptal måste de baseras på fysikaliska processer som är, såvitt vi vet, oförutsägbara[2].
Unix, BSD och deras efterföljare Mac OS och Android ökar entropin, dvs den samlade mängden slumpmässighet kontinuerligt. Detta sker genom att från operativsystemet installeras klockas tiden mellan mus-, tangentbords- och diskaktiviteter i /dev/random. Varje ny tidsskillnad tas med en matematisk funktion med den lagrade och sparas. Detta gör att slumpmässigheten i /dev/random ökar med datorns användning. Om fler slumptal genererats än en viss andel av antalet tidsskillnader pausas /dev/random i Linux, men inte i FreeBSD och Mac OS tills tillräckligt många nya tidsskillnader erhållits. För att undvika blockering kan man anropa /dev/urandom som med hjälp av en pseudoslumptalsgenerator och innehållet i /dev/random genererar nya slumptal[3][4][5].
Nackdelen med dessa metoder är att de bygger på interaktion med en användare, och därför fungerar dåligt i virtuella maskiner och i serverhallar. Moderna SSD har betydligt mindre tidsskillnader för åtkomst än traditionella hårddiskar. Hårdvarubaserade analoga slumptalsgeneratorer drar mycket ström. Därför började Intel 2008 producera CPU:er med inbyggd digital slumptalsgenerator. Dessa har en krets med två transistorer. Beroende på termiskt brus går strömmen den ena eller andra vägen. När tillräckligt många bitar erhållits används AES-CBC-MAC för att erhålla bättre spridning. CBC står för Chiper-Block-Counting, dvs en räknare gör att indatan krypteras på olika sätt varje gång och MAC innebär att krypteringen är unik för processorns serienummer[6].
Misstankar fanns att NSA installerat en bakdörr i Intels slumptalsgenerator, men i Linux behandlas de genererade värdena som tidsskillnader i /dev/random som i sin tur genererar slumptalet som används, så detta är inget problem[7].
Användningsområden
[redigera | redigera wikitext]Slumptalsgeneratorer förekommer i tillämpningar som hasardspel, datorsimulering, kryptografi och liknande områden där ett oförutsägbart resultat är önskvärt.
Hårdvarubaserade slumptalsgeneratorer är särskilt användbara i sammanhang där det är av stor vikt att den använda slumptalsgeneratorn producerar ett resultat som är oförutsägbart för en utomstående. Ett exempel är tillämpningar som kräver skydd mot intrång, fusk eller bedrägerier.
Pseudoslumptalsgeneratorer har, som nämnts, egenskapen att samma frö (startvärde) ger upphov till samma följd av slumptal. Detta är användbart i sammanhang där man behöver generera samma följd av tal upprepade gånger.
Kvasislumptal som alternativ
[redigera | redigera wikitext]Några beräkningar som använder sig av en slumptalsgenerator kan sammanfattas som beräkningen av ett totalvärde eller genomsnittsvärde, som till exempel integralberäkningar med hjälp av Monte Carlometoden. För sådana problem kan det vara möjligt att hitta en mer noggrann lösning genom att använda sig av så kallade lågdiskrepanssekvenser, även kallade kvasislumptal. Sådana sekvenser har tydliga mönster som fyller igen gap jämnt; en "riktig" slumptalsekvens kan lämna större gap (och gör så ofta i praktiken).
Se även
[redigera | redigera wikitext]Källor
[redigera | redigera wikitext]- ^ ”Anyone who attempts to generate random... - Quote”. AllAuthor. https://allauthor.com/quotes/26142/.
- ^ [a b] Goldberg, Ian; Wagner, David (15 August 1995). ”DDJ, Jan96: Randomness and Netscape Browser”. People @ EECS at UC Berkeley. http://people.eecs.berkeley.edu/~daw/papers/ddj-netscape.html.
- ^ ”urandom(4): kernel random number source devices”. Linux man page. https://linux.die.net/man/4/urandom.
- ^ Corrigan-Gibbs, Henry; Jana, Suman. ”Recommendations for Randomness in the Operating System or, How to Keep Evil Children Out of Your Pool and Other Random Facts”. Stanford University. https://www.cs.columbia.edu/~suman/docs/hotos15recommendations.pdf. Läst 21 december 2020.
- ^ Sarıtas, Serkan (Maj 2013). ”ANALYSIS OF ANDROID RANDOMNUMBER GENERATOR”. Bilkent University. Arkiverad från originalet den 21 oktober 2021. https://web.archive.org/web/20211021025934/http://www.thesis.bilkent.edu.tr/0006566.pdf. Läst 21 december 2020.
- ^ ”Intel® Digital Random Number Generator (DRNG) Software Implementation...”. Intel. 14 May 2014. https://www.intel.com/content/www/us/en/develop/articles/intel-digital-random-number-generator-drng-software-implementation-guide.html.
- ^ Clarke, Gavin (10 September 2013). ”Torvalds shoots down call to yank 'backdoored' Intel RdRand in Linux crypto”. The Register. https://www.theregister.com/2013/09/10/torvalds_on_rrrand_nsa_gchq/.
Externa länkar
[redigera | redigera wikitext]Slumptal tillgängliga på Internet från källor som är okända, och inte verifierade av användaren, bör aldrig används för kryptografiska syften.
- Random.org - skapa slumpmässiga bitmappar, kasta virtuella tärningar m.m. (Slumptalen alstras från atomsfäriskt brus från en radio)
- HotBits: Äkta slumpmässiga bits (slumptalen genereras från radiaktivt sönderfall)
- RandomNumbers.info (slumptalsgeneratorer som utnyttjar kvantumoptiska processer)