Abstract/Details

A cryptographically secure pseudorandom number generator


2003 2003

Other formats: Order a copy

Abstract (summary)

We investigate a cryptographically secure pseudorandom number generator based on a Linear Feedback Shift Register (LFSR). The statistical properties of the generator are examined, as well as its resistance to cryptographic analysis.

LFSRs are known to produce bit streams that have excellent statistical properties. However, they can be predicted by monitoring their outputs briefly. Many approaches have been tried to modify an LFSR output to preserve its statistical properties but make it unpredictable. These techniques work in a "stream-wise" manner; for each bit output from the LFSR, one bit is output from the composite generator. All of these approaches have fallen to cryptanalysis.

The technique used in this project processes the output of an LFSR with a hash function, converting blocks of M bits into smaller blocks of N bits. Since the hash function maps many input blocks into any given output block, there is no way of determining the LFSR state by knowing the value of an output block.

The resulting generator was analyzed using standard statistical tests for randomness, such as chi-square tests on the distribution of blocks of bits, autocovariance of the output bit stream, and the Marsaglia "Die-Hard Battery" of statistical tests. The Lempel-Ziv data-compression algorithm was used on the output stream to try to discover any structure. In addition, a cryptographic analysis technique, the Berlekamp-Massey algorithm, was used to determine the difficulty of predicting the generator's output.

Indexing (details)


Subject
Electrical engineering
Classification
0544: Electrical engineering
Identifier / keyword
Applied sciences; Cryptography; Number generator; Pseudorandom
Title
A cryptographically secure pseudorandom number generator
Author
Aamodt, Ken S.
Number of pages
147
Publication year
2003
Degree date
2003
School code
0183
Source
DAI-B 66/09, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
9780542332166, 0542332167
Advisor
Bell, Mark R.
University/institution
Purdue University
University location
United States -- Indiana
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
3190781
ProQuest document ID
305316022
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
http://search.proquest.com/docview/305316022
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.