cryptographically secure pseudo random number generator

Introduction

Here is proposed a floating point cryptographically secure pseudo random number generator (csprng) on uniform distribution with the x values 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

The algorithm is: an=an-1-xn-1 and xn=FRAC(anxn-1+.5) better explained with a PowerBASIC CC5 implementation on the next lines, that generate 16777216 pseudo random numbers (80bit).

FUNCTION PBMAIN

LOCAL m, n AS LONG, a, x AS EXT

FOR n=1 TO 134217728 STEP 262144

FOR m=1 TO 262144 STEP 8

a=a+x

x=FRAC(a*x+.5)

NEXT

a=a*x

NEXT

END FUNCTION

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.

performance

The performance depends on hardware, software, optimization, et al. Running the code above on Windows XP/SP3 / Intel Centrino processor at 2.0 GHz, the algorithm generates 277000000 Bytes/sec or 7.22 cycles/Byte. 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:

xn-2 0.234546748574634 xn-1 0.783564763234561 xn 0.674863564797320

xm-2 0.356464763212724 xm-1 0.783564763234561 xm 0.098743643223776

Let R the repeated number (Red) on the sets. xn=FRAC(an*R+.5) the next number after R on the first set (green), xm=FRAC(am*R+.5), the next number after R on the second set (blue). To do xn=xm, must be an=am, and that is impossible, because an<am. In another way, 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^(64n). For example, for a precision b=64 bit and n=1000, we have a period P=(2^64)*((2^64)-1)^999 ~ 2^64000.

Precision

This algorithm can run in any floating point precision (IEEE 754), like Single (32 bit), Double (64 bit), Long double (80 bit), Quadruple (128 bit), or High up to precision(33219280 bit), if necessary.

Application

You can i.e. get 10.000 decimal pseudo random numbers or i.e. pick a bet on Euromillions game. In both, use the refresh button on your web browser, to give new values. Bellow is showed a little example in JavaScript language, that it’s the same code used in this site, to generate 10.000 pseudo random numbers, with the initial seeds extracted from the new Date () function

<SCRIPT LANGUAGE="JavaScript">

var seed=new Date ()

var seed= seed.getTime ()

var seed=seed.toString();

var s=seed.length;

var r=""

for (u=0; u<s; u++) {

var r=r+seed.charAt(s-u)

}

var x=eval( "." + r )

var a=x/3

for (n=1; n<10001; n++) {

var a=a+x

var x=a*x+.5-Math.floor(a*x+.5)

document.write(x + "<BR>")

}

</SCRIPT>

Cryptography

Combined with (XOR), 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.

/\|_\/()

KEYNOTE.PS

KODAKGALLERY_COMáSLIDESHOW.MHT

LIVRO1.XLS

LIVRO2.XLS

MAKE.TXT

MAKEWHAT.EXE

MDYANKSE-1-06.2-TT.ZIP

MELD.EXE

MONKEY.PS

MUNDIAL.XLS

MWC1.PS

O MEU TEMA FAVORITO.THEME

OGALLERY_SLIDESHOW.MHT

PERCENTAGENS DE PONTOS.XLS

PONTO E BANCA.XLS

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.

RibeiroAlvo