Cryptographically
Secure Pseudo Random Number Generator
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, xn+1=FRAC(xn(xn+bn)+c) with xo=[0,1] bo=1-xo c=(.5+xo)/2. See a PowerBASIC implementation on the next lines, that
generate 2^24 pseudo random characters in a binary file.
|
SCREEN 0 CLS CLEAR OPEN “TEST.TXT” FOR BINARY AS #1 DEFQUD n, t DEFEXT x, b, c t = 2^24 IF (LOF(1)-t) <> 0 THEN CLOSE #1 KILL “TEST.TXT” OPEN “TEST.TXT” FOR BINARY AS #1 END IF x=FRAC(TIMER) b=1-x c=(.5+x)/2 p%=16384 t2=INT(t/p%)*p% f%=t-t2 c$=SPACE$(p%) FOR n=1 TO t2-1 STEP p% FOR
m%=1 TO p% STEP 10 x=FRAC(x*(x+b)+c) MID$(c$, m%, 5)=MKD$(x*x) b=c+b*x MID$(c$,m%+5,5)=MKD$(b) NEXT PUT$ #1, c$ NEXT IF f% > 0 THEN c$="" FOR m%=1 TO f%
x=.999*FRAC(x*(x+b)+c)
c$=c$+CHR$(INT(x*256)) NEXT PUT$ #1, c$ END IF CLOSE #1 PRINT “Done” END |
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 xo=0, bo=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 in assembly language. An advantage of this algorithm, is no need to
scale the numbers to (0,1) like as the algorithms that uses the function MOD n.
This algorithm works in MOD 1.0 but using the INT or FLOOR function, instead of
the MOD.
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 Xm-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.
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 xo, b and c. To encrypt a file, the algorithm starts with x1=FRAC(xo(xo+n+b)+c) with n=[0,n]. If we know x1, we need to find, xo, b and c. Using exhaustive
search on i.e. 2^64 possibilities for one key, and processing 2^30 numbers per
second in one machine, we need 2^64/(2^30*3600*24*365)=544.77 years to find one
of the tree keys. See Alvo a small application that encrypt/decrypt
any kind of files. Next is the source code in PowerBasic.
|
SCREEN 0 CLS COLOR 11,3 FOR i%=1 to 3 LOCATE i%,1:PRINT SPACE$(80); LOCATE 22+i%,1:PRINT SPACE$(80); NEXT LOCATE 2,3:print LEFT$(CURDIR$,78) LOCATE 24,75:print
"ALVO"; DEFQUD n, s DEFEXT x,c,b mt%=4000 DIM nomefich$(mt%),w%(mt%),nomefich2$(mt%),size(mt%) ph%=16384 FINDFILES:
'----------------------------------------------------------- pf%=1:pa%=1 LOCATE 24,3,0:PRINT "Reading files..."; COLOR 7,0 fa$=DIR$ ("*.*") DO WHILE NOT fa$="" OPEN fa$ FOR BINARY AS #1 IF LOF(1)>7 THEN INCR mf% nomefich$(mf%)=fa$ size(mf%)=LOF(1) pn%=0 SEEK #1,LOF(1)-4 GET$ #1,4,ww$ IF ww$="Alvo" THEN w%(mf%)=1:DECR size(mf%),4 pn%=INSTR(fa$,".")-1 IF pn%>0 THEN ex$=RIGHT$(fa$,LEN(fa$)-pn%-1) nm%=3-LEN(ex$) ex$=ex$+SPACE$(nm%) END IF IF pn%>0 THEN
nomefich2$(mf%)=LEFT$(fa$,pn%)+SPACE$(10-LEN(LEFT$(fa$,pn%)))+ex$ ELSE
nomefich2$(mf%)=fa$+SPACE$(13-LEN(fa$)) nomefich2$(mf%)=nomefich2$(mf%)+USING$("#,###,###,###,###",size(mf%)) IF mf%<19 THEN lim%=mf%-1 ELSE lim%=18 IF mf%<20 THEN COLOR ,0:GOSUB lista END IF CLOSE #1 fa$=DIR$ COLOR ,3:LOCATE 24,3,0:PRINT SPACE$(17); pf%=1:pa%=1 NOVO:
'-------------------------------------------------------------------- COLOR ,0 IF mf%=0 THEN nofiles GOSUB LISTA DO DO K$=UCASE$(INKEY$) LOOP UNTIL K$<>"" IF K$=CHR$(27) THEN CLS:COLOR 15,0:LOCATE ,,0:END COLOR ,3:LOCATE 24,3:PRINT SPACE$(20);:COLOR,0 IF LEN(k$)=2 THEN ky$=RIGHT$(k$,1) IF Ky$="S" THEN GOSUB DELETA IF Ky$="H" THEN decr pa% IF Ky$="P" THEN incr pa% if pa%>lim%+1 then pa%=lim%+1:incr pf% if pa%<1 then pa%=1:decr pf% IF Ky$="G" THEN pf%=1:pa%=1 IF Ky$="O" THEN pf%=mf%-lim%:pa%=lim%+1 IF Ky$="I" THEN DECR pf%,lim%+1 IF Ky$="Q" THEN INCR pf%,lim%+1 IF pf%>mf%-lim%-1 THEN pf%=mf%-lim% IF pf%<1 THEN pf%=1 'IF ky$="S" THEN NOVO END IF IF ASC(k$)>13 AND ASC(k$)<123 THEN GOSUB ALFA GOSUB LISTA IF k$=CHR$(13) THEN CLOSE #1 OPEN nomefich$(pf%+pa%-1) FOR BINARY AS #1 GOSUB VALOR GOTO CHAVE END IF CHAVE:
'------------------------------------------------------------------- pc%=0 keyy$="" keyys$="" mostra%=-1 CHAV: COLOR cor1%:LOCATE
PA%+3,34,1:PRINT keyys$; DO DO K$=INKEY$ LOOP UNTIL K$<>"" IF LEN(K$)=2 THEN IF RIGHT$(K$,1)="R" THEN
mostra%=mostra%*-1 GOTO MOSTRAR END IF COLOR ,3:LOCATE 24,3:PRINT SPACE$(20); COLOR ,0:LOCATE PA%+3,34,1:PRINT keyys$; IF K$=CHR$(27) THEN novo IF K$=CHR$(13) AND pc%<18 THEN men$="Short key" IF pc%=0 THEN men$="No key" LOCATE 24,3,0:COLOR 11,3:PRINT men$;:COLOR ,0:GOTO
CHAV END IF IF K$=CHR$(13) THEN c=(CVQ(LEFT$(keyy$,8))+9223372036854775808)/2^64 x=(CVQ(MID$(keyy$,9,8))+9223372036854775808)/2^64 b=(CVQ(RIGHT$(keyy$,8))+9223372036854775808)/2^64 keyy$=SPACE$(24):keyy$="" GOTO crypta END IF IF ASC(K$)>31 AND ASC(K$)<127 AND pc%<24
THEN keyy$=keyy$+k$ IF ASC(K$)=8 AND pc%>0 THEN
keyy$=LEFT$(keyy$,pc%-1) MOSTRAR:'---------------------------------------------------------- pc%=LEN(keyy$) IF mostra%=-1 then keyys$=STRING$(pc%,"*")
ELSE keyys$=keyy$ LOCATE ,34,1:PRINT keyys$;" "; LOCATE ,34,1: PRINT keyys$; CRYPTA:'----------------------------------------------------------- COLOR cor1% LOCATE ,34,0 PRINT SPACE$(45); FOR n=0 TO tf2-1 STEP ph% LOCATE ,34:PRINT STRING$(INT(n/q),"|"); GET$ #1,ph%,z$ FOR m%=1 to ph% STEP 8 x=.9999*FRAC(x*(x+m%+b)+c) MID$(z$,m%,8)=MKQ$(CVQ(MID$(z$,m%,8)) XOR
INT(x*18446744073709551616-9223372036854775808)) NEXT ON ERROR RESUME NEXT SEEK #1,n PUT$ #1, z$ IF ERR=75 THEN GOSUB ERRO NEXT GET$ #1,f%+1,z$ FOR m%=1 TO f%+1 LOCATE ,34:PRINT
STRING$(INT((n+m%)/q),"|"); x=.9999*FRAC(x*(x+m%+b)+c) MID$(z$,m%,1)=CHR$(ASC(MID$(z$,m%,1)) XOR
INT(x*256)) NEXT SEEK #1,tf2 PUT$ #1,z$ IF w%(pf%+pa%-1)=0 THEN PUT$
#1,"Alvo":w%(pf%+pa%-1)=1:GOTO sai FOR i%=1 TO 4 PUT$ #1,"" NEXT w%(pf%+pa%-1)=0 SAI: CLOSE #1 GOTO novo: ALFA:
'----------------------------------------------------------------- FOR ial%=1 TO mf% IF LEFT$(nomefich$(ial%),1)=k$ THEN IF ial%<=lim% THEN pf%=1:pa%=ial%:RETURN IF ial%>lim% THEN pf%=ial%-lim%:pa%=lim%+1:RETURN END IF NEXT RETURN LISTA: '
---------------------------------------------------------------- FOR i%=0 TO lim% IF w%(pf%+i%)=1 THEN cor%=4 ELSE cor%=8 IF i%+1=pa% THEN cor%=15:cor1%=15:IF w%(pf%+i%)=1
THEN cor%=12:cor1%=12 LOCATE i%+4,2,0:PRINT SPACE$(78); COLOR cor%:LOCATE i%+4,3:PRINT nomefich2$(pf%+i%); NEXT IF lim%<18 THEN FOR i%=lim%+5 TO 22 LOCATE i%,2:PRINT SPACE$(50); NEXT END IF RETURN DELETA: '
---------------------------------------------------------------- IF mf%=0 THEN NOFILES CLOSE #1 OPEN nomefich$(pf%+pa%-1) FOR BINARY AS #1 GOSUB VALOR LOCATE ,35:PRINT
"Del"; DO K$=RIGHT$(UCASE$(INKEY$),1) IF K$="S" THEN EXIT LOOP IF k$<>"" THEN RETURN IF f%>0 THEN FOR n=0 TO tf2-1 STEP ph% LOCATE ,35+INT(n/q):PRINT "|"; ON ERROR RESUME NEXT PUT$ #1,SPACE$(ph%) IF ERR=75 THEN GOSUB ERRO NEXT END IF PUT$ #1,SPACE$(ph%) CLOSE #1 KILL nomefich$(pf%+pa%-1) LOCATE ,3:PRINT SPACE$(77); DECR mf% IF mf%=0 THEN NOFILES FOR i%=pf%+pa%-1 TO mf% nomefich$(i%)=nomefich$(i%+1) nomefich2$(i%)=nomefich2$(i%+1) size(i%)=size(i%+1) w%(i%)=w%(i%+1) NEXT IF mf%<lim%+1 THEN DECR lim% IF pf%+pa%=mf%+2 THEN DECR pf% RETURN novo VALOR:
'------------------------------------------------------------------- LOCATE pa%+3,,0 COLOR cor1% nfl=size(pf%+pa%-1) tf=nfl-1 tf2=INT(tf/ph%)*ph% f%=tf-tf2 q=tf/45 RETURN NOFILES:
'--------------------------------------------------------------- COLOR ,3 LOCATE 24,2,0:PRINT " No files. Esc to
exit"; DO K$=INKEY$ LOOP UNTIL K$=CHR$(27) COLOR 15,0 CLS END ERRO:’--------------------------------------------------------------------- IF ERR=75 THEN men$="File already open" LOCATE 24,3,0:COLOR 11,3:PRINT men$;:COLOR ,0:GOTO
novo END IF RETURN |
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.
© Ribeiro Alvo