Analys av pseudoslumptalsalgoritmer: Linjära kongruensgeneratorer, återkopplande skiftregister och AES-baserade pseudoslumptalsgeneratorer

Hannes Salin, 2011, Kungliga tekniska högskolan

Sammanfattning

Detta arbete handlar om pseudoslumptalsgenerering i ett jämförande och analyserande perspektiv. I fokus står tre olika typer av algoritmer: en linjär kongruensgenerator, ett linjärt återkopplande skiftregister samt en AES-baserad psuedoslumpgenerator. Av dessa tre har de två senare implementerats på egen hand i C++ och kongruensgeneratorn är en implementation funnen på Internet (upphovsman: Robin Whittle).
Denna jämförelse syftar till att undersöka huruvida olika pseudoslumptalsgeneratorer skiljer sig åt i prestanda och vilken grad av statistisk slumpmässighet dess utdata har. Detta för att påvisa att man bör välja rätt pseudoslumptalsgenerator till rätt sammanhang.
Prestandatestningen genomfördes genom att mäta tiden för respektive algoritm att generera 10^3, 10^6, 10^7 samt 10^9 heltal (dvs. ca 4 kB, 4 Mb, 40 Mb samt 4 Gb slumpdata) . En enklare statistisk testning gjordes med testbatteriet ENT som tillhandahåller fem olika statistiska test för mätning av slumpmässighet i tal/bit-sekvenser. Med de mätdata som följde gjordes en analys över skillnaderna algoritmerna emellan. Resultatet blev att av de tre testade algoritmerna anses AES-baserade PRNG vara den bästa algoritmen ur ett säkerhetsperspektiv då den hade bäst statistiska värden. Bortser man från säkerhetskrav krav anses det linjära återkopplande skiftregistret vara mest användbart ur ett prestandamässigt perspektiv då dess snabbhet och relativa statistiska egenskaper var mycket goda.