Multiprime Blum-Blum-Shub Pseudorandom Number Generator
Abstract
Blum-Blum-Shub (BBS) is a (probabilistically) secure pseudorandom bit/number generator which outputs a sequence by repeatedly reducing squares modulo the product of two Blum-primes. Our goal for this thesis is to modify the algorithm by using a modulus which is the product of three Blum-primes. We evaluate the effect of this modification using the suite of tests from National Institute of Standards and Technology (NIST). Previous research has evaluated the limit on the number of least important bits that can be extracted per iteration of the BBS algorithm while still maintaining the pseudorandom properties. In this paper, we go beyond the proposedlimit and compare the modified BBS with the original BBS using the NIST tests. This paper also discusses the cryptosystem based on the modified BBS as well as the original BBS. We use three metrics for the comparison of performance: the type of tests, the overall performance of sequences against NIST tests, and the time to generate sequences. Our test data shows that both versions performed ina similar manner when subjected to NIST tests. Furthermore, bit generation is significantly faster for sequences generated by taking the last 50 bits or more, while still maintaining pseudorandom properties.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 2016
- Accession Number
- AD1030047
Entities
People
- Bijesh Shrestha
Organizations
- Naval Postgraduate School