Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Analys av pseudoslumptalsalgoritmer – Linjära kongruensgeneratorer, återkopplande skiftregister och AES-baserade pseudoslumptalsgeneratorer.
KTH, School of Computer Science and Communication (CSC).
2011 (Swedish)Independent thesis Advanced level (professional degree), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

This essay deals with pseudorandom number generation in a comparative and analytical perspective. The focus is on three different types of algorithms: a linear congruence generator, a linear feedback shift register and an AES-based psuedosrandom generator. Of these three, the latter two are implemented in C++ by the author and the linear congruence generator is an implementation found on the Internet (author: [1]Robin Whittle) This comparison aims to investigate whether different pseudorandom number generators differ in performance and the degree of statistical randomness of its output. This is to demonstrate that one should choose the right pseudorandom number generator to the right context. Performance testing was conducted by measuring the time for each algorithm to generate 10^3, 10^6, 10^7 and 10^9 integers (around 4 kB, 4 Mb, 40 Mb and 4 Gb random data). A simple statistical testing was done with the test battery ENT which provides five different statistical tests to measure the randomness of integer/bit-sequences. With the test result that followed, an analysis over the differences between the algorithms could be done. The result was that of the three tested algorithms the AES-based PRNG was considered to be the best algorithm from a security perspective when it had the best statistical values. If you disregard safety requirements the linear feedback shift register was considered to be the most useful algorithm from a performance perspective, because its speed and relative statistical properties were very good..

Abstract [sv]

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: [1]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.

Place, publisher, year, edition, pages
2011.
Series
Kandidatexjobb CSC, K11089
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-130858OAI: oai:DiVA.org:kth-130858DiVA: diva2:654303
Educational program
Master of Science in Engineering - Computer Science and Technology
Uppsok
Technology
Supervisors
Examiners
Available from: 2013-10-07 Created: 2013-10-07

Open Access in DiVA

No full text

Other links

http://www.csc.kth.se/utbildning/kandidatexjobb/datateknik/2011/rapport/salin_hannes_K11089.pdf
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 35 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf