DIVIDE AND CONQUER MODIFICATION OF THE BLUM-MICALI PSEUDORANDOM NUMBER GENERATOR

Authors
Gillespie, Daniel K.
Subjects
Blum
Micali
Blum-Micali
pseudorandom
generator
cryptography
PRNG
pseudorandom number generator
Advisors
Stanica, Pantelimon
Date of Issue
2023-06
Date
Publisher
Monterey, CA; Naval Postgraduate School
Language
Abstract
The Blum-Micali pseudorandom number generator (PRNG) outputs cryptographically secure sequences of pseudorandom bits. One of the primary drawbacks of the Blum-Micali PRNG is that it can be computationally expensive and slow to run. This thesis proposes a modification to the Blum-Micali PRNG that allows for more pseudorandom bits to be extracted per iteration of the algorithm while retaining cryptographic security. We use the National Institute of Standards and Technology (NIST) Statistical Test Suite for PRNGs to evaluate the performance of sequences produced using this modification. In addition we compare the computational run time of our modification with that of the original Blum-Micali PRNG. Previous research indicates that there is an upper limit on the number of bits that may be extracted per iteration while retaining cryptographic security. Our test data suggest that our modification to the Blum-Micali PRNG performs just as well as the original version when extracting up to 11 bits per iteration. Furthermore, our data suggest that our modification can speed up computational run times in direct proportion to the number of bits extracted per iteration. We consider additional possible extensions that could further increase the speed of computation while still retaining randomness and cryptographic security.
Type
Thesis
Description
URI
https://hdl.handle.net/10945/72175
Series/Report No
Department
Applied Mathematics (MA)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Approved for public release. Distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections
Theses
Load more