Floating Point

Cryptographically Safe

Pseudo Random

Number Generator

© Ribeiro Alvo

 

Introduction

Here is proposed a floating point cryptographically secure pseudorandom number generator with the outcomes distributed uniformly between zero and one [0,1). It’s safe and fast, with a large period and a good statistical randomness quality. Algorithm, randomness, Speed performance, periodicity, cryptography, and other issues, are explained forward. Based on a quadratic function, the algorithm is: xn+1=frac(xn(xn+bn)+c) with x0=]0;1[, b0=[0;1], c=]0;1[ and n=0; 1; 2; 3;… See a BASIC implementation on the next lines, that generate 100000000 double precision pseudorandom numbers.

 

 

 

DEFDBL x, b, c

defines (x) (b) and (c) as double precision

x=0.2353

e.g. x0=0.2353

b0=0.5673

e.g. b0=0.5673

c=0.5

e.g. c=0.5

FOR b=b0 TO b0+100000000

begin the loop from (b0) to (b0)+100000000

  x=x*(x+b)+c–INT(x*(x+b)+c)

calculate (x) from frac(x(x+b)+c)

NEXT

go to next (b)

END

code finish

 

 

Randomness

Several statistical tests done with George Marsaglia’s Diehard battery of tests, was not find any 0.00000 or 1.00000, p-values. See the results on the example test here. 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. Below are the test results, among many others, done with the ENT program on two binary files, one with 134217728 Bytes, and another with 1073741824 Bytes randomly generated by this algorithm, both starting with x0=0, b0=1 and c=0.5.

 

 

Value Char Occurrences Fraction

 0        536874766   0.500004

 1        536867058   0.499996

Total: 1073741824   1.000000

Entropy = 1.000000 bits per bit.

Optimum compression would reduce the size of this 1073741824 bit file by 0 percent.

Chi square distribution for 1073741824 samples is 0.06, and randomly would exceed this value 81.40 percent of the times.

Arithmetic mean value of data bits is 0.5000 (0.5 = random).

Monte Carlo value for Pi is 3.141313123 (error 0.01 percent).

Serial correlation coefficient is -0.000008 (totally uncorrelated = 0.0).

 

Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size of this 1073741824 byte file by 0 percent.

Chi square distribution for 1073741824 samples is 248.49, and randomly would exceed this value 60.30 percent of the times.

Arithmetic mean value of data bytes is 127.5008 (127.5 = random).

Monte Carlo value for Pi is 3.141515393 (error 0.00 percent).

Serial correlation coefficient is 0.000003 (totally uncorrelated = 0.0).

 

 

Speed performance

The speed performance depends on hardware, software, optimization, et al. Running a simple program compiled with Fortran90, on Intel Core Q6600 at 2.4GHz, the algorithm generates around 72.000.000 double precision (64 bit) pseudo-random numbers per second, or 576 Mbytes/sec. This value can be improved if optimized and implemented on assembly.

 

Periodicity

As (n) is constantly incremented, 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

xn-2

0.356464763212724

xm-1

0.783564763234561

xm

0.098743643223776

 

 

R is the repeated number (red) on the sets. xn=frac(R(R+n)+c), the next number after R on the first set (green), xm=frac(R(R+m)+c), the next number after R on the second set (blue). To do xn=xm, must be R(R+n)+c=R(R+m)+c, or R+n=R+m, or n=m, and that is impossible, because n<m. 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 53 bit precision, and n=1 we have a period of 2^53. For n=2, a period of (2^53)*((2^53)-1). For n=3, a period of (2^53)*((2^53)-1)^2. So, for (b)=bit precision and (n) outcomes, the period is P=(2^b)*((2^b)-1)^(n-1). For example, for a precision b=53 bit and n=1000, we have a period P=(2^53)*((2^53)-1)^999=2^53000. This means, the period grows significantly with (n).

 

Precision and implementation

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. It can be easily implemented in any system. Is portable from platform to platform. Bellow is showed a little example of the source code for a small routine made in JavaScript language. It’s the same code used in this site (see applications bellow), to generate 1000 pseudo random numbers, with x0, b0 and c extracted from the new Date () function in JavaScript. Two small applications then you can use it, with this prong algorithm. In both, use the refresh button on your web browser, to give new values. Get 1000 decimal pseudorandom numbers or Pick Euro millions pseudo-random bets.

 

 

<SCRIPT LANGUAGE="JavaScript">

vary seed=new Date ()

vary seed= seed.getTime ()

vary seed=seed.toString();

var l=seed.length;

var r=""

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

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

}

var seed=eval( "." + r )

var c=seed

var x = 1-c

var b0=c*1000

for (b=b0; b<b0+1000; b++) {

  vary x=x*(x+b)+c-Math.floor(x*(x+b)+c)

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

}

</SCRIPT>

 

 

Cryptography

Combined with exclusive or function (XOR), this algorithm is safe for cryptography. It’s very difficult, if not impossible, to find the tree keys x0, b0 and c. To encrypt a file, the algorithm starts with x1=x0(x0+b0)+c with four variables. If we know x1, we need to find the tree keys, x0, b0 and c. Using exhaustive search on i.e. 2^64 possibilities for one key, and processing 2^30 numbers per second, we need 2^64/(2^30*3600*24*365)=544.77 years to find one of the tree keys. See this simple example to encrypt a binary file:

 

 

 

DEFLNG n, L

Defines (n) and (L)as long integer

DEFDBL x, b, c

Defines (x), (b) and (c) as double precision

OPEN “file.txt” FOR BINARY AS #1

Open file.txt to encrypt

L=LOF(1)-1

Let L=size of the file-1

x=0.2353

Key 1 – e.g. x0 = 0.2353

b0=0.438965

Key 2 – e.g. b0 = 0.438965

c=0.5

Key 3 – e.g. c = 0.5

FOR n=0 TO L

Begin the loop from (n) to (L)

  x=x*(x+n+b0)+c–INT(x*(x+n+b0)+c)

Calculate (x) with franc(x(x+b)+c)

  SEEK #1,n

Put the pointer on (n) position

  GET$ #1,1,y$

Get one character at (n) position

  av$=CHR$(ASC(y$) XOR INT(256*x))

Encrypt the character

  SEEK #1, n

Put again the pointer on (n) position

  PUT$ #1, av$

Put the encrypted character on (av$)

NEXT

Go to next (n)

CLOSE #1

Close the file

END

Finish the code

 

 

If you want to do some encryption/decryption experience with files, see this page that brings a small program based on the this algorithm. Download and save the program on the directory that contains the files to encrypt/decrypt.

 

Conclusion

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