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). |
|
|
|
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). |
|
|
|
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.