Ultrafast pseudorandom number generation using pseudorandom permutations and mappings.

摘要

Pseudorandom numbers have broad applications in science, technology, entertainment, etc. So far many pseudorandom number generators (PRNGs) have been developed, but dedicated high performance high quality PRNGs are still in demand. In light of this, we propose a new design approach which combines byte-oriented pseudorandom permutations and integer-oriented pseudorandom mappings. Pseudorandom permutations are used for state initialization and reseeding. Pseudorandom mappings are used for state transition and pseudorandom number generation. Several PRNGs are designed using this approach. The performance tests show they surpass the existing pseudorandom number generators in both non-cryptographic category and cryptographic category. The proposed non-cryptographic PRNG reaches a generation speed of half clock cycle per byte on an Intel Core i3 processor, and the cryptographically secure PRNG also runs into one clock cycle per byte. They demonstrate excellent randomness properties as attested by the NIST statistical tests, the new Diehard battery of tests, and the TestU01 batteries of tests. The non-cryptographic PRNG is also designed to meet a couple of other requirements, including long period, high-dimensional equidistribution, quick recovery from biased states, and ease of use. For the cryptographically secure PRNG, security has been taken into account throughout the design. Besides the key scheduling algorithm, which has an avalanche effect comparable to that of standard hash functions, a new two-layer design paradigm is adopted, which functionally divides the internal state into two parts, with the first part serving as a source of entropy and periodically reseeding the second part. The generator has a huge internal state and employs a high quality state update function, which renders a very long expected period. The overall security of the generator is carefully analyzed in the context of various known cryptanalytic attacks, state compromise extension attacks, and next-bit test. Besides deterministic pseudorandom number generation, the proposed PRNGs can also work in a non-deterministic mode. In this mode, the generators behave like a true random number generator by periodically querying some non-deterministic random sources and using them as unpredictable sources of entropies. Running in this mode has virtually no impact on the cost, performance, availability, or usability of the generators.