What's so special about this pseudo-random number generator?
This carefully designed PRNG utilizes more than 1536 bits of internal “state” memory. The operating parameters of the generator's algorithm were carefully chosen (it uses a “safe prime” factor) to guarantee that every possible PRNG “state” is visited before the sequence begins to repeat. The result is that the “period” of this generator will be the “Germain prime” 1,768,863 x 21535 - 1, which is approximately 2.132 x 10468. This is such a large number that it might as well be infinite. This generator effectively never repeats.
For our purposes, a “SeedKey” (such as the one above) is used to initialize the PRNG to a pseudo-randomly chosen point in this incredibly large loop of unpredictable pseudo-random numbers, from which we then pull as many pseudo-random values as we need. The 256-character “SeedKey” uses the 94 printable ASCII characters (spaces are ignored). Therefore, this yields 94256 possible seedkeys. This is 1.32 x 10505 possible strings, which is equivalent to 1,678 bits of entropy. Since this is greater than the total entropic state of the UHEPRNG, a SeedKey of this length and complexity is sufficient (and necessary) to fully initialize a PRNG of this complexity.
Where is it?
Why was this fancy PRNG developed?
Our “Off The Grid” (OTG) website password generation system is based upon Latin Squares. Latin Squares are ‘n’x‘n’ grids containing exactly one of each of ‘n’ symbols in every horizontal row and vertical column. Brute force guessing of the OTG system's grids is made effectively impossible by the large number of possible 26x26 Latin Squares. This remains true even when many pieces of a user's Latin Square have become known to an attacker due to the phenomenal number of Squares that are still possible containing what is known.
Although mathematicians have been unable to determine how many different 26x26 Squares can be created, they have been able to determine that the number is at least 9.337 x 10426, or approximately 21418. This is an incredibly large number. But for our purposes it is only meaningful if any of those many possible Latin Squares could potentially be generated by our OTG grid generator. If we were to use any traditional PRNG, even something state-of-the-art such as Fortuna, based upon a cryptographic symmetric cipher or a hash, we would be limited to generating Latin Squares from such a generator's much lower level of entropy . . . on the order of 256 or 384 bits. This would be more than sufficient for many cryptographic applications, but not for ours. Since 26x26 Latin Squares are known to have a potential entropy of at least 1418 bits, we needed a PRNG that could keep up. So an “ultra-high entropy” PRNG, having an entropy of 1536 bits, was developed to allow access to all possible Latin Squares.
What's the “SeedKey” in the form above?
Not only do we want a system that is able to select one OTG grid from among the truly incredible number of possible Latin Squares, but every user needs to be able to regenerate their own personal one out of 10427 grids if their existing paper copy should ever need to be replaced, resized, recolored, re-fonted, or reprinted for any reason.
We achieve those two goals by generating and capturing a very long 1536-bit pseudo-random number — the “SeedKey” — then using that number to set the ultra-high entropy pseudo-random number generator's 1536-bit “initial state” from which a single unique grid will be created.
Fortunately, the need to test the randomness of hopefully-random numbers is so well known that a great deal of effort has previously been expended in the creation of suites of randomness-testing tools. Using the most well known, well used, and popular of these tools, multiple researchers have independently verified that the pseudo-random numbers generated by this algorithm passes the most stringent of tests for randomness. I breathed a sigh of relief after this, since the “diehard” and “dieharder” suites of tests are considered “difficult to pass” by researchers of randomness.
Everyone is invited to test it for themselves:
Pseudo-random numbers generated by this algorithm have handily passed the “Fourmilab.ch/random” tests as well as the tried and true “diehard” and “dieharder” test suites. For individuals wishing to verify the quality of this algorithm's pseudo-random numbers for themselves, a 256-megabyte file of this algorithm's output may be downloaded from GRC, and a Microsoft Windows scripting host (WSH) version of this algorithm may be downloaded and run from the Windows command prompt to generate unique files of any size:
Gibson Research Corporation is owned and operated by Steve Gibson. The contents
of this page are Copyright (c) 2014 Gibson Research Corporation. SpinRite, ShieldsUP,
NanoProbe, and any other indicated trademarks are registered trademarks of Gibson
|Last Edit: Nov 06, 2011 at 11:50 (851.58 days ago)||Viewed 36 times per day|