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.