CSPRNG/\|_\/()

INTRODUCTION

Here is proposed a floating point cryptographically secure pseudo random number generator on uniform values distributed between zero and one. It’s safe, fast, with a large period and good statistical randomness quality. Algorithm, randomness, performance, periodicity, cryptography and other issues, are explained forward.

ALGORITHM

Bellow is the code that describe the algorithm, generating 134217728 (2^13*2^14=2^27) pseudo random numbers uniformly distributed between zero and one, with 64 bit precision.

LOCAL m AS QUAD LOCAL n AS LONG LOCAL a, b, x AS EXT x=TIMER MOD 1 b=x^2 FOR m=2 TO 8193 a=b+1/m FOR n=1 TO 16384 a+=x x=(a*x+a) MOD 1 NEXT NEXT

Define m as 64 bit integer Define n as 32 bit integer Define a, b and x as 80 bit floating point Start x in (0,1) Let b in (0,1) First loop from 2 to 2^13+1 (Can be from 1 to 2^64-1 iterations) Let a a fraction from b and m Second loop from 1 to 2^14 (Is ever 2^14 iterations) Increment a with x Let x in (0,1) Go to next n Go to next m

RANDOMNESS

Several statistical tests done with George Marsaglia’s Diehard battery of tests, was not find any 0.00000 or 1.00000, p-values. Comparative tests done with binary files containing true random numbers generated by physical sources, such as atmospheric noise from RANDOM.ORG, atomic radiation from HotBits, and chaotic source from LAVArnd, given good results. Also it passes all tests done with TESTU01-1.2.3 ( Small Crush, Crush and Big Crush ).

PERFORMANCE

Running the above code on Windows XP/SP3/PowerBasic CC5/Intel Centrino 2.0 GHz processor, the performance rounds the 563 MBytes/second at 3.53 cycles/Byte, to process the 134217728 Bytes. This value can be improved if optimized and/or implemented in assembly language.

PERIODICITY

As an is incremented by xn-1, then xn must be different from xn-1. To explain that, see this simple example: Take two different small sets from the whole sequence with one repeated number on each set, and n<m, as follows: Let R the repeated number on the two different sub-sequences, xn=(an*R+an) MOD 1 the next number after R on the first sub-sequence, xm=(am*R+am) MOD 1, the next number after R on the second sub-sequence. To do xn=xm, must be an=am, and that is impossible, because an<am. In other words, If two random numbers at different points in a long sequence were identical, then the preceding and succeeding random numbers will be different. For a 64 bit precision, and n=1 we have a period of 2^64. For n=2, a period of (2^64)*((2^64)-1). For n=3, a period of (2^64)*((2^64)-1)^2. So, for b=bit precision and n=outcomes, the period is P=(2^b)*((2^b)-1)^(n-1) ~ 2^(bn). For example, for a precision b=64 bit and n=1000, we have a period P=(2^64)*((2^64)-1)^999 ~ 2^64000.

APPLICATION

We can apply this algorithm to encrypt files on disks hiding sensitive information. Or send encrypted files to others who have the same program to decrypt. Because it’s high performance, it’s recommended for Monte Carlo simulations or uses in computer games. Get 10000 decimal pseudo random numbers ( floats with csprngAlvo - integers with Adhcifar ), or pick a bet on Euromillions game. In both, use the refresh button on your web browser, to give new values. The generated sequence numbers, can be worked with spreadsheets to do statistical works, i.e. genetics, engineering, bioscience, etc.

CRYPTOGRAPHY

Combined with XOR function, this algorithm is safe for cryptography. If you want to try it, go to Alvo a small application that encrypt/decrypt any kind of file. Or if you prefer to work with integers, go to Adhcifar.

CONCLUSION

Simple and elegant, tiny and fast this algorithm offers no difficulties on implementation, in any system/platform or programming language. I believe it can be used with various applications, for its statistical quality and encryption safety. Criticism or suggestions, contact me.

Ribeiro Alvo