A Pseudo-Random Bit Generator Using Three Chaotic

Logistic Maps
Mickael Francois, David Defour

To cite this version:

Mickael Francois, David Defour. A Pseudo-Random Bit Generator Using Three Chaotic Logistic Maps. hal-00785380, 2013. <hal-00785380>

HAL Id: hal-00785380

https://hal.archives-ouvertes.fr/hal-00785380
Submitted on 6 Feb 2013

HAL is a multi-disciplinary open access

archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

Larchive ouverte pluridisciplinaire HAL, est

destinee au depot et `a la diffusion de documents
scientifiques de niveau recherche, publies ou non,
emanant des etablissements denseignement et de
recherche francais ou etrangers, des laboratoires
publics ou prives.

A Pseudo-Random Bit Generator Using Three

Chaotic Logistic Maps
Michael FRANC
OIS and David DEFOUR
Univ. Perpignan Via Domitia, DALI F-66860, Perpignan, France
Univ. Montpellier II, LIRMM, UMR 5506, F-34095, Montpellier,
France
CNRS, LIRMM, UMR 5506, F-34095, Montpellier, France
Dated: February 6, 2013

Abstract
A novel pseudo-random bit generator (PRBG) using three chaotic
logistic maps is proposed. The algorithm generates at each iteration
sequences of 32 bit-blocks by starting from randomly chosen initial
seeds. The impact of relying on IEEE 754-2008 floating-point representation format for the generator is also taken into account. The
performance of the generator is evaluated through various statistical
analyses. The results show that the produced sequences possess high
randomness statistical properties and good security level which make
it suitable for cryptographic applications.

Introduction.

The generation of pseudo-random bits (or numbers) plays a critical role in a

large number of applications such as statistical mechanics, numerical simulations, gaming industry, communication or cryptography [Sun, 2009]. The
term pseudo-random is used to indicate that the bits (or numbers) appear to be random and are generated from an algorithmic process so-called
generator. From a single initial parameter (or seed), the generator will always produce the same pseudo-random sequence. The main advantages of
such generators are the rapidity and the repeatability of the sequences and
require less memory for algorithm storage. One interesting way to design
such generators is connected to chaos theory [Alvarez, 2006]. That theory

Electronic address: michael.francois@univ-perp.fr;

Electronic address: david.defour@univ-perp.fr; Corresponding author

focuses primarily on the description of these systems that are often very
simple to define, but whose dynamics appears to be very confused. Indeed,
chaotic systems are characterized by their high sensitivity to initial conditions and some properties like ergodicity, pseudo-random behaviour and high
complexity [Alvarez, 2006]. The extreme sensitivity to the initial conditions
(i.e. a small deviation in the input can cause a large variation in the output)
makes chaotic system very attractive for pseudo-random number generators.
Moreover, during this last decade several pseudo-random number generators
have been successfully developed [Guyeux, 2010, Zheng, 2008, Pareek, 2010,
Patidar, 2009a, Or
ue, 2010]. However, a rigorous analysis is necessary to
evaluate the randomness level and the global security of the generator.
In this paper, a new PRBG using a standard chaotic logistic map is
presented. It combines three logistic maps involving binary64 floating-point
arithmetic and generates block of 32 random bits at each iteration. An efficient process based on permutations among values produced by the three
logistic maps and xor operation anyhilate the collision problem that may
appear while using several logistic map based on the same function. The
produced pseudo-random sequences have successfully passed the various statistical tests. The assets of the generator are: high sensitivity to initial seed
values, high level of randomness and good throughput. The paper is structured as follows, a brief introduction of floating-point arithmetic and the
used chaotic logistic map is given in Sec. 2. Section 3, presents a detailed
description of the algorithm. The statistical analysis applied on two groups
of generated pseudo-random sequences is given in Sec. 4. The global security
analysis of the PRBG is achieved in Sec. 5, before concluding.

2
2.1

Background
IEEE 754-2008 standard.

Digital computers represent numbers in sets of binary digits. For real numbers, two formats of representations can be distinguished : fixed-point format and floating-point format. The fixed-point format is designed to represent and manipulate integers or real numbers with a fixed precision. In
the case of real numbers with variable precision, the representation is made
through the floating-point format. There exists a standard that defines the
arithmetic formats, the rounding rules, the operations and the exception
handling for floating-point arithmetic.
The IEEE 754-2008 [IEEE, 2008] is the current version of the technical
standard used by hardware manufacturer to implement floating-point arithmetic. Among them, binary32 and binary64 which correspond to single and
double precision format are the two most widely used and implemented formats. As the generator described herein relies exclusively on binary64, we
will only consider this format in the rest of this article.
2

Binary64 comprises two infinities, two kinds of NaN (Not a Number) and
the set of finite numbers. Each finite number is uniquely described by three
integers: s a sign represented on 1 bit, e a biased exponent represented on
11 bits and m a mantissa represented on 52 bits where the leading bit of
the significand is implicitly encoded in the biased exponent (see figure 1).
To make the encoding unique, the value of the significand m is maximized
by decreasing e until either e = emin or m 1. After this process is
done, if e = emin and 0 < m < 1, the floating-point number is subnormal.
Subnormal numbers (and zero) are encoded with a reserved biased exponent
value. Interested readers will find a good introduction to floating point
arithmetic and issues that arise while using it in [Goldberg, 1991]
sign

exponent

mantissa
mantissa0

63

62

52

mantissa1

51

32 31

Figure 1: Floating-point representation in double precision format (64 bits).

2.2

The chaotic logistic map.

The PRBG uses the chaotic logistic map given by:

F (X) = X(1 X),

(1)

with between 3.57 and 4.0 [Bose, 1999]. This function have been widely
studied [Weisstein, Eric W.] and several pseudo-random number generators
have already used this logistic map [Bose, 1999, Baptista, 1998, Patidar, 2009a,
Cecen, 2009, Xuan, 2011]. To avoid non-chaotic behavior (island of stability, oscillations, ...), the value of is fixed to 3.9999 which corresponds to a
highly chaotic case [Pareek, 2006]. The chaotic logistic map is used under
the iterative form:
Xn+1 = 3.9999Xn (1 Xn ), n 0,

(2)

where the initial seed X0 is a real number belonging to the interval ]0, 1[.
All the output elements Xn are also real numbers in the interval ]0, 1[.

The proposed generator.

The main idea of the proposed PRBG is to combine several chaotic logistic
maps and carefully arrange them in the same algorithm in order to increase
the security level compared to others PRBG such as [Patidar, 2009a]. It
generates a block of 32 random bits per iteration using the following three

logistic maps :
Xn+1 = 3.9999Xn (1 Xn ), n 0,

(3)

Yn+1 = 3.9999Yn (1 Yn ), n 0,

(4)

Zn+1 = 3.9999Zn (1 Zn ), n 0.

(5)

For the three chaotic maps, the same value of is chosen to maintain its
surjectivity in the same interval. For each computed value Xn , Yn and Zn ,
we used binary64 floating-point representation format as in Fig. 1.
The technical details of the implementation in C using definitions from
the file ieee754.h are given in Algorithm 1. The algorithmic principle of the
PRBG consists in three steps:
1. Line 2; Three different starting seed values X0 , Y0 and Z0 are carefully
chosen to avoid colision (see section 3.1).
2. Line 3-8; The results of the 30 first iterations of the three chaotic
logistic maps are discared to have sufficient chaotic behavior among
them (see section 3.2).
3. Line 9-50; Iterate N times, N being the length of the output sequence
in blocks of 32 bits to:
(a) Line 10-12; Compute the three logistic maps.
(b) Line 13-21; For each logistic map, save the bits of mantissa0 and
mantissa1 in two different variables.
(c) Line 23-48; Start another loop of length 32 on the bits of mantissa1
and in each case, select one bit at a time using the value of
mantissa0. For more security, the value of the mantissa0 of the
element Zn is used to index the bits of the mantissa1 of Xn , the
value of the mantissa0 of Xn to index the bits of mantissa1 of Yn
and the value of mantissa0 of Yn to index those of the mantissa1
in Zn . The three selected bits are combined by a xor operator
to give the output bit (Line 35-46). The selected bit is then permuted with the bit at the end of chain to not be used again. At
the end of the last loop, a 32-bit bloc is generated.

3.1

Seeds selection.

The choice of the starting seed values should not be neglected. We are using
a logistic map where input and ouput value belong to the interval ]0, 1[. The
main idea of this article is to use three identical logistic maps in order to
increased the robustness of the generator. To preserve such robustness, we
have to avoid collision that may occur with incorrect initial values that will
leads to identical series of numbers.
4

To understand the collision mecanism, we have to understand how a

difference between two computed value Xn and Yn at a given iteration n
will propage to the next iteration. Without loss of generality, we can assume
that:
Yn = Xn (1 + ).
Out of equation 2 we know that:
Xn+1 = Xn (1 Xn ),

(6)

Yn+1 = Yn (1 Yn ),

(7)

which is equivalent to
Yn+1



2Xn 2 Xn
= Xn+1 1 +
.
(1 Xn )

By evaluating the partial derivative in of the previous equation, we can

deduce that the smallest difference between Xn+1 and Yn+1 is reached when
=

1 2Xn
,
Xn

which means that when = X1n 2, then at the next iteration we will have
Yn+1 = Xn+1 corresponding to a collision. To avoid this case the selection
of the three seeds has to be done in the interval ]0, 21 [.
The difference at the next iteration is minimal when Xn is close to 21 .
In this case, the difference between Xn+1 and Yn+1 is :
Yn+1 Xn+1 = Xn (1 Xn 2Xn ),
and its limit as Xn approaches 21 is
lim (Yn+1 Xn+1 ) =

Xn 21

2
.
4

In order to avoid collision this difference has to be representable in binary64,

which means:
2
> 253 .
4
By hyphothesis, we set = 3.9999, then has to be such that > 226 in
order to avoid collision.
Lack of chaos may arises when dealing with floating-point arithmetic due
to the effect of rounding error. In binary64 floating-point arithmetic, the
computed value (1 x) is equal to 1.0 for any x ]0, 253 [. This means that
for an initial seed selected in the interval ]0, 253 [, the computed value of
equation 2 is equivalent to Xn . To avoid this problem, initial seeds have
to be taken in the interval ]253 , 21 [.
5

To sumarize, collisions are avoided by choosing for the first seed X0

a random floating-point number representable in binary64 in the interval
]253 , 21 [. The two other seeds Y0 and Z0 are constructed by randomly
choosing two binary64 floating-point numbers a and b such that :
a and b are different and not equal to 0.
|a| > 226 and |b| > 226 .
Y0 = X0 (1 + a) and Z0 = X0 (1 + b) belong to the interval ]253 , 21 [.

3.2

Initial chaotic behaviour

We have plotted in figure 2 the obtained trajectory of the logistic map with a
small seed (X0 = 1015 ). One can observe that for the first iterations of the
process, the trajectory is not chaotic. This is because, the initial difference
between two successive values, spreads slowly toward the leading bit of the
mantissa. Thus, to decorrelate the beginning of the output sequences among
the three logistic maps, it is necessary to discard the first iterations before
starting the generation.
We have exhaustively tested for each input values X0 in the interval
53
]2 , 21 [ and Y0 = X0 (1+225 ), the minimum
number
of iterations k which


|Xk Yk |
is necessary to reach the condition log2
> 1. This condition
Xk
corresponds to loose all the initial leading bits of correlation between X0 and
Y0 . We measured that on average 25.4 iterations are required. Therefore,
to decorrelate the beginning of the considered sequences and increase the
security level of the PRBG, we choose that the generation will start from
the 31st iteration.

Statistical analysis.

For any secure PRBG, the output sequences must have a high level of randomness and be completely decorrelated from each other. Therefore, a statistical analysis based on the randomness level and correlation should be
carefully conducted to prove the quality of the sequences.

4.1

Randomness evaluation.

This analysis consists in evaluating the randomness quality of the sequences

produced by the algorithm. Therefore, the sequences are evaluated through
statistical tests suite NIST (National Institute of Standards and Technology
of the U.S. Government). Such suite consists in a statistical package of fifteen tests developed to quantify and to evaluate the randomness of binary
sequences produced by cryptographic random or pseudo-random number

Evolution of positions X n

1
0.8
0.6
0.4
0.2
0
0

20

40

60

80

100

120

140

160

180

200

Iteration n
Figure 2: Trajectory of the chaotic logistic map given in Eq. 2 for n = 200
and X0 = 1015 .

generators [Rukhin, 2010]. For each statistical test, a set of pvalue is produced and is compared to a fixed significance level = 0.01. A pvalue of
zero indicates that, the tested sequence appears to be not random. A pvalue
larger than means that, the tested sequence is considered to be random
with a confidence level of 99%. Therefore, a sequence passes a statistical
test for pvalue and fails otherwise. If at the same time more than one sequence is tested, each statistical test defines a proportion as the ratio of sequences passing successfully the test relatively to the total number of tested
sequences T (i.e. = n[pvalue 0.01]/T ). The proportion is compared to
an acceptable proportion accept which corresponds to the ratio of sequences
that should pass the test. The range of acceptable proportions, excepted
for the tests Random Excursion-(Variant)
p is determined by using the confidence interval defined as (1 0.01) 3 0.01(1 0.01)/T [Rukhin, 2010].
To analyse several aspects of the sequences, the NIST tests are applied on:
individual sequences, concatenated sequence and resulting sequences.
1. Individual sequences: all the produced sequences are individually tested
and the results are given as ratio of success relatively to the threshold
accept . Such test indicates the global randomness level of generated
sequences.
2. Concatenated sequence: a new sequence of binary size 32 N T is
constructed by concatenating all the individual sequences. The randomness level of the constructed sequence is also analysed with the
NIST tests. In the case of truly decorrelated random sequences, the
7

concatenated sequence should also be random.

3. Resulting sequences: are the sequences obtained from the columns, if
the tested sequences are superimposed on each other. Thus, N resulting sequences of binary size 32 T are constructed, by collecting
for each position 1 j N , the 32-bit bloc of each sequence.
The NIST tests are used to analyse such resulting sequences. If truly
random sequences are superimposed on each other, the resulting sequences should also be random (with T as large as N ). This approach
is interesting especially for sequences generated with successive seed
values and can show if there is some hidden linear structures between
the original sequences.

4.2

Correlation evaluation.

The correlation evaluation is done in two different ways. Firstly, the correlation between generated sequences is analysed globally by computing the
Pearsons correlation coefficient of each pair of sequences [Patidar, 2011].
Consider a pair of sequences given by: S1 = [x0 , . . . , xN 1 ] and S2 =
[y0 , . . . , yN 1 ]. Therefore, the corresponding correlation coefficient is:
NP
1

(xi x) (yi y)

CS1 ,S2 = 
NP
1

i=0

1/2 N 1
1/2 ,
P
(xi x)2

(yi y)2

i=0

(8)

i=0

where xi and yi are 32-bit integers, x =

NP
1

xi /N and y =

i=0

NP
1

yi /N the

i=0

mean values of S1 and S2 , respectively. For two uncorrelated sequences,

CS1 ,S2 = 0. A strong correlation occurs for CS1 ,S2 ' 1. The coefficients
CS1 ,S2 are computed for each pair of produced sequences and the distribution
of the values is presented by a histogram.
In the second approach, a correlation based directly on the bits of sequences is analysed. The Hamming distance between two binary sequences
(of the same length M ) is the number of places where they differ, i.e., the
number of positions where one has a 0 and the other a 1. Thus, for two
binary sequences S1b and S2b , the Hamming distance is given by:
d(S1b , S2b )

M
1
X

(xj yj ),

(9)

j=0

where xj (resp. yj ) are the elements of S1b (resp. S2b ). In the case of truly
random binary sequences, such distance is typically around M/2, which gives
a proportion (i.e. d(S1b , S2b )/M ) of about 0.50. For each pair of produced sequences, this proportion is determined and all values are represented through
8

a histogram. The interest of both approaches is to check the correlation for

generated sequences mainly from nearby or successive seed values.

4.3

Analysis of pseudo-random sequences.

In the case of very distant seed values, the chaotic trajectories are very
different, which usually allows to obtain good pseudo-random sequences.
That is why the analysis is achieved on sequences produced from nearby or
successive seed values. Here, two groups of pseudo-random sequences are
considered. The binary length of each sequence is 32 N with N = 1024
and the total number of sequences per group is T = 15000. The first group
(GRP1) is generated from the seed values X0 = 11015 , Y0 = 21015 and
Z0 = 3 1015 where each new sequence is obtained with the same values of
X0 , Y0 and by incrementing of 1015 the last seed value Z0 . For the second
group (GRP2), the same strategy is applied to the starting seeds X00 =
0.325873724698325, Y00 = 0.325873724698326 and Z00 = 0.325873724698327.
A simple loop on the latest seed values Z0 and Z00 allows to generate the
two groups of sequences GRP1 and GRP2. The aim is to show whatever the
structure of the initial seeds, the PRBG produces sequences of high quality.
4.3.1

Results of randomness evaluation.

The results of NIST tests obtained on the two groups of 15000 sequences
are presented in Table 1 and Table 2, respectively. For individual sequences
(resp. resulting sequences), the acceptable proportion should lie above
0
accept = 98.75% (resp. accept
= 98.04% ). For the tests Non-Overlapping
and Random Excursions-(Variant), only the smallest percentage of all under
tests is presented. In the case of individual sequences, the Universal test is
not applicable due to the size of sequences. One can remark that for the
two groups GRP1 and GRP2, all the tested sequences pass successfully the
NIST tests. These results show clearly the quality of the produced sequences
from successive seed values.
4.3.2

Results of correlation evaluation.

Concerning the correlation analysis, the Pearsons correlation coefficient between each pair of the 15000 produced sequences is computed. For each
group, the corresponding histogram is presented in Fig. 3. One can see
that, the two histograms have the same shape and show that the computed
coefficients are very close to 0. For the group GRP1 (resp. GRP2), around
99.02% (resp. 99.00%) of the coefficients have an absolute value smaller
than 0.08. The histograms show that the correlation between the produced
sequences is very small.
About the correlation analysis using the Hamming distance, for each pair
of the 15000 produced sequences, the proportion of places where the bits
9

Table 1: Results of the NIST tests on the 15000 generated sequences of

GRP1. The ratio (resp. 0 ) of pvalue passing the tests are given for individual (resp. resulting) sequences and the pvalue is given for the concatenated
sequence.
Test Name
Frequency
Block-Frequency
Cumulative Sums (1)
Cumulative Sums (2)
Runs
Longest Run
Rank
FFT
Non-Overlapping
Overlapping
Universal
Approximate Entropy
Random Excursions
Random Ex-Variant
Serial (1)
Serial (2)
Linear Complexity

Indiv. Seq.

Result
99.06 Success
99.11 Success
99.08 Success
99.00 Success
98.93 Success
98.99 Success
98.86 Success
98.90 Success
99.26 Success
99.00 Success
98.93 Success
98.75 Success
98.75 Success
98.91 Success
99.06 Success
98.98 Success

10

Concat.
pvalue
0.338497
0.673515
0.589087
0.408891
0.343876
0.417880
0.788352
0.609162
0.012083
0.175000
0.366163
0.138980
0.100729
0.043821
0.158943
0.367717
0.975515

Seq.
Result
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success

Result. Seq.
0
Result
99.31 Success
98.92 Success
99.21 Success
99.21 Success
99.02 Success
99.02 Success
98.63 Success
98.24 Success
98.04 Success
98.92 Success
98.43 Success
98.14 Success
98.12 Success
97.71 Success
99.12 Success
98.92 Success
98.73 Success

Table 2: Results of the NIST tests on the 15000 produced sequences of

GRP2. The ratio (resp. 0 ) of pvalue passing the tests are given for
individual (resp. resulting) sequences and the pvalue for the concatenated
sequence is also given.
Test Name
Frequency
Block-Frequency
Cumulative Sums (1)
Cumulative Sums (2)
Runs
Longest Run
Rank
FFT
Non-Overlapping
Overlapping
Universal
Approximate Entropy
Random Excursions
Random Ex-Variant
Serial (1)
Serial (2)
Linear Complexity

Indiv. Seq.

Result
99.09 Success
99.14 Success
99.16 Success
99.00 Success
98.99 Success
98.92 Success
99.01 Success
98.75 Success
99.27 Success
99.02 Success
99.02 Success
96.29 Success
97.53 Success
98.92 Success
99.04 Success
98.99 Success

11

Concat.
pvalue
0.408718
0.458897
0.239274
0.494016
0.025894
0.281249
0.806842
0.673608
0.012472
0.711625
0.149652
0.532585
0.060350
0.134550
0.291906
0.196383
0.215418

Seq.
Result
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success
Success

Result. Seq.
0
Result
98.73 Success
98.63 Success
98.63 Success
99.02 Success
98.82 Success
99.12 Success
99.12 Success
98.73 Success
98.04 Success
99.12 Success
98.53 Success
98.33 Success
98.52 Success
98.73 Success
99.60 Success
99.51 Success
99.60 Success

12

GRP1
GRP2

Frequency (in %)

10
8
6

4
2
0

0.05

0.1

0.05

0.1

Correlation coefficient value

Figure 3: Histogram of Pearsons correlation coefficient values on interval

[0.1, 0.1] for the group GRP1 (resp. GRP2).

differ is computed. The histograms are presented in Fig. 4. The distribu14

GRP1
GRP2

Frequency (in %)

12
10
8
6
4
2
0

0.485

0.49

0.495

0.5

0.505

0.51

0.515

Hamming distance

Figure 4: Histogram of Hamming distance on interval [0.485, 0.515] for the

group GRP1 (resp. GRP2).

tions show that all the proportions are around 50%. For the group GRP1
(resp. GRP2), around 98.45% (resp. 99.98%) of the coefficients belong to
]0.488, 0.512[. The values for GRP2 are better, because of the entropy of seed
values. Such analysis provides another indication about the decorrelation
between the generated sequences.

12

Security analysis.

A global security analysis of the generator must be carefully conducted. The

analysis is based on all the critical points allowing to detect weaknesses in
the generator. The investigated points are: the size of the key space, the key
sensitivity, the randomness quality of the outputs, weak or degenerate keys
and speed performance. Even if all the existing attacks can not be tested,
the PRBG must resist to some basic-known attacks. In the present case,
three basic attacks are evaluated: brute-force attack, differential attack and
guess-and-determine attack.

5.1

Key space.

It is generally accepted that, today a key space of size smaller than 2128 is
not secure enough. A good generator should have a large key space, to have
a high diversity of choices in the generation of the pseudo-random sequence.
The proposed PRBG combines three chaotic logistic maps.
We have set the conditions for seeds selection in section 3.1. The seed
X0 is a binary64 floating-point number selected from the interval ]253 , 21 [.
This corresponds to 252 different combinations of mantissa times 51 different
values for the exponent, which gives 51 252 different seeds. The seeds Y0
and Z0 are selected such that there is a relative difference of 226 among
each seeds. This means that Y0 is selected in a space of 51252 226 possible
seeds and Z0 in a space of 51 252 227 different numbers. The total space
of seeds is approximately 2173 .

5.2

Key sensitivity.

The sensitivity related to the key (here the seed values) is an essential aspect
for chaos-based PRBG. Indeed, a small deviation in the starting seeds should
cause a large change in the pseudo-random sequences. In other words, even
with a small difference on seed values, the output sequences should be completely uncorrelated. Actually in the test of correlation (Sec. 4.3.2), the seed
sensitivity was already tested due to the successive seed values. To bring an
additional analysis, a large pseudo-random sequences of size N = 5000000
(i.e. 160000000 in binary) are considered. A sequence S1 is produced by
using the seed values X0 = 1 1015 , Y0 = 2 1015 and Z0 = 4 1015 .
Two others sequences S2 and S3 are produced with X00 = X0 , Y00 = Y0 , Z00 =
00
00
00
3 1015 and X0 = X0 , Y0 = Y0 , Z0 = 5 1015 , respectively. The set
of the three produced sequences is denoted KS1. The same approach is
achieved from another set of sequences denoted KS2. The first sequence
is generated with X0 = 0.328964524728163, Y0 = 0.423936234268352 and
Z0 = 0.267367904037358. The two supplementary sequences are obtained
by decrementing and incrementing of 1015 the last seed. In both cases, the

13

analysis is done using the linear correlation coefficient of Pearson, the correlation coefficient of Kendall [Kendall, 1970] and the Hamming distance. The
same analysis is conducted on the sets KS1 and KS2 by using the algorithm
proposed by Patidar et al [Patidar, 2009a], with the parameter = 3.9999.
As the algorithm uses only two chaotic logistic maps, for each set of sequences only the last two seed values are considered. The results are given
in Table 3 and show that, for the proposed algorithm the correlation coefficient values are close to 0 and the proportion of elements that differ in
sequences are around 50%. The results show also that, the sequences are
highly correlated for the Patidars algorithm.
Table 3: Pearsons and Kendalls correlation coefficients and Hamming
distance (in term of proportion) between large output sequences S1 , S2 , S3
produced from slightly different initial seeds.
PRBG

Set
KS1

Proposed
algorithm
KS2

KS1
Patidar et al.
algorithm
KS2

Tests
Pearson Corr.
Kendall Corr.
Ham. Dist.

S1 /S2
0.000422
0.000150
0.499985

S1 /S3
0.000201
0.000437
0.500064

S2 /S3
0.000127
0.000141
0.500033

Pearson Corr.
Kendall Corr.
Ham. Dist.
Pearson Corr.
Kendall Corr.
Ham. Dist.

0.000423
0.000116
0.500002
0.329043
0.233170
0.333416

0.000235
0.000025
0.500055
0.329214
0.231704
0.333362

0.000583
0.000199
0.499931
0.329024
0.231653
0.333366

Pearson Corr.
Kendall Corr.
Ham. Dist.

0.329542
0.231709
0.333284

0.329417
0.232413
0.333324

0.330055
0.231693
0.333354

Another test of correlation using the randomness of the sequences is achieved.

The test is to concatenate the three generated sequences and evaluate the
obtained sequence through the NIST tests. The results are presented in Table 4. In each case, all the pvalue are larger than 0.01 for the current PRBG.
Therefore, the concatenated sequence can be viewed as a random sequence,
which prove that the sequences S1 , S2 and S3 are completely uncorrelated.
The results of the Patidar et al algorithm are added to show that, it is
not enough just to combine multiple chaotic logistic maps to build a secure
generator. Indeed, other treatments such as xor, permutations, etc., should
be included in the algorithm to produce sequences of high cryptographic
qualities.

14

Table 4: Results of the NIST tests on the concatenated sequence obtained

from the sequences of the set KS1 (resp. KS2) for the proposed and Patidar
et al algorithm.
Test Name

Frequency
Block-Frequency
Cumulative Sums (1)
Cumulative Sums (2)
Runs
Longest Run
Rank
FFT
Non-Overlapping
Overlapping
Universal
Approximate Entropy
Random Excursions
Random Ex-Variant
Serial (1)
Serial (2)
Linear Complexity

Proposed algo.
KS1
KS2
pvalue
pvalue
0.888272 0.189097
0.013966 0.409511
0.851269 0.250461
0.723802 0.375858
0.239428 0.196619
0.341867 0.124501
0.690933 0.468857
0.704824 0.837336
0.014372 0.017263
0.544746 0.513071
0.693543 0.467674
0.534042 0.087565
0.016321 0.014831
0.014383 0.013285
0.532881 0.383964
0.508815 0.828262
0.956706 0.189871

15

Patidar et al algo.
KS1
KS2
pvalue
pvalue
0.218594 0.933359
1.000000 1.000000
0.343496 0.679001
0.284913 0.757413
0.000000 0.000000
0.000000 0.000000
0.611764 0.788756
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.000000 0.000000
0.013588 0.000622
0.125754 0.038526
0.000000 0.000000
0.000000 0.000000
0.817657 0.400909

5.3

Quality of pseudo-random sequences.

The strength of any generator is based on undeniable quality of its outputs.

Indeed, whichever way the generator is designed, the produced sequences
must be strong (i.e. random, uncorrelated and sensitive). In the literature, various statistical tests are available to analyse the randomness of
sequences. In fact, the NIST proposes a battery of tests that must be applied on the binary sequences [Rukhin, 2010]. One can also find other tests
such as TestU01 [Ecuyer, 2007] or the DieHARD suites [Marsaglia, 1996].
Here, the NIST tests are used to evaluate the randomness level of the PRBG
outputs. Two sets of pseudo-random sequences were produced with different
structures of seeds. For a complete analysis, the tests were applied to different aspects of the sequences (individual sequences, concatenated sequence
and resulting sequences). All the produced sequences pass successfully the
statistical tests. The correlation between the outputs is evaluated and the
results showed that only a very small (or negligible) correlation exists between sequences. The sensitivity related to the seed values is also analysed
and the results have shown that the proposed PRBG is very sensitive to
these starting parameters.

5.4

Weak or degenerate keys.

A crucial element for any PRBG based chaos, is to ensure that the sequences
are always generated from strong keys. Therefore, a careful study of the
chaotic regions in the space of initial seeds is necessary in order to avoid weak
or degenerate keys. The first task is to choose a logistic map, with parameter
that contributes to have an excellent chaotic behaviour of the function. To
avoid redundancy on the chaotic trajectories, initial seed values have to be
taken in the interval ]253 , 21 [ with a difference > 226 between them. To
prove the quality of outputs, two groups consisting of 15000 sequences are
produced using successive seed values. The seeds close to the interval bound
expected to be weak are also tested. The various statistical tests clearly
show the quality of tested sequences. Thus, these regions are considered as
homogeneously chaotic, allowing to choose independently the seed values in
the interval ]253 , 21 [. Therefore, the proposed generator does not present
weak or degenerate keys.

5.5

Speed analysis.

Beyond having a PRBG with a high level of randomness, it is also necessary

to have a fast generator. Because, in real-time applications, the temporal
constraint in the execution of a process is as important as the result of
this process. Thus, for a fast generator, the domain of its applications can
be extended. The speed performance analysis is achieved on a personal
computer with Intel(R) Core(TM) 2 Duo CPU P7350 @ 2.00 GHz 2. The
16

algorithm is implemented using GCC on Fedora release 16 (Verne). The

Table 5 shows the performance in terms of speed of the proposed algorithm
compared with others. The algorithm has a good throughput which can
be an advantage for applications requiring a high security level and a fast
execution time.
Table 5: Comparison of speed between the proposed algorithm and some
other algorithms.
Generator
Proposed
Ref. [Pareschi, 2006]
Ref. [Yang, 2012]

5.6

Speed (Mbit/s)
44.1120
40.0000
0.4844

Attacks.

Any new pseudo-random number generator must be analysed against attacks

in order to check if the generator can not be broken. Here, the resistance of
the generator against three basic attacks as the brute-force attack, differential attack and guess-and-determine attack is discussed.
5.6.1

Brute-force attack.

A brute-force attack [Alvarez, 2006] is a standard attack that can be used

against any PRNG. The strategy consists in checking systematically all possible keys until the correct key is found. In the worst case, all the combinations are tested, that necessitates to try all the key space. On average,
just half of the key space need to be tested to find the original key. Such
an attack might be utilized when it is not possible to detect any weakness
in the algorithm, that would make the task easier. To resist this kind of
attack, the size of the key space must be large. It is generally accepted that
a key space of size larger than 2128 is computationally secure against such
attack. In this case, the size of the key space is around 2173 , which clearly
allows to resist the brute force-attack.
5.6.2

Differential attack.

Such technique of cryptanalysis was introduced by Biham and Shamir [Biham, 1993].
As a chosen-plaintext attack, its principle is to analyse and exploit the effect of a small difference in input pairs on the difference of corresponding
output pairs. This strategy allows to find the most probable key that was
used to produce the pseudo-random sequence. Given two inputs I and I 0

17

(e.g. X0 , Y0 , Z0 and X00 , Y00 , Z00 ) and the corresponding outputs O and O0 ,
the most commonly used differences are:
1. Subtraction modulus: the differences related to both inputs and outputs are defined by in = |I I 0 | and out = |O O0 |, respectively.
Here, for inputs the difference can be computed between (X0 , X00 ),
(Y0 , Y00 ) and (Z0 , Z00 ) and for outputs, the difference can be computed
between the two pseudo-random sequences relatively to the bits or
blocks of bits.
2. Xor difference: defined by in = I I 0 and out = O O0 .
The diffusion aspect on the initial conditions is then measured by a differential probability. However, in the design of the algorithm, the decorrelation
of outputs was taken into account by choosing the initial seed values in
]253 , 21 [ (with > 226 ) and by making 30 iterations before the beginning of the generation. Moreover, the results of the analyses showed that
even with a small difference on the seeds, the produced outputs are almost
independent from each other. Thus, the proposed PRBG should resist to
the differential attack.
5.6.3

Guess-and-determine attack.

Guess-and-determine attack is proven to be effective against word-oriented

stream ciphers [Ahmadi, 2009]. As it comes from the name, in guess-anddetermine attacks, the strategy is to guess firstly the value of few unknown
variables of the cipher and then, the remaining unknown variables are deduced by iterating the system a few times and by comparing the produced
pseudo-random sequence with the original pseudo-random sequence. If these
two sequences are the same, then the guessed values are correct and the cryptosystem is broken otherwise the attack should be repeated with new guessed
values. It seems that the attack discussed in reference [Ahmadi, 2009] can
not be directly applied on the proposed algorithm which is not of the same
family of involved stream ciphers. Indeed, the internal structure of the cipher algorithm is completely different from a Linear Feedback Shift Register
(LFSR). Here the algorithm starts with three chosen seed values and generates a 32-bit bloc after each iteration. An alternative way to apply such
attack would be to guess and fix the two seed values X0 and Y0 , then iterate
the algorithm to find the seed Z0 . Knowing that the algorithm is very sensitive to initial seeds, one should try in the worst case 257.67 different values.
Once all the comparisons made without success, the two initial seeds (X0
and Y0 ) are guessed again and the process is repeated until success. This
process has almost the same complexity than a classic brute-force attack.

18

Conclusions.

A novel pseudo-random bit generator based on the combination of three

chaotic logistic maps was presented. For three given initial seeds, the generator produces a sequence formed of 32-bit blocks. The treatment combines
permutations and xor operation on the 32 least significant bits of mantissa
of the elements obtained by the logistic maps. Such a PRBG has shown its
ability to produce a very large number of pseudo-random sequences which
can be useful in several cryptographic applications. The advantages of the
generator are: a high sensitivity related to the initial seed values, a high
randomness level, the resistance against several attacks and the rapidity of
the algorithm.

References
[Sun, 2009] Sun, F., and S. Liu (2009). Cryptographic pseudo-random sequence from the spatial chaotic map. Chaos Solitons Fractals, 41(5),
22162219.
[Weisstein, Eric W.] Weisstein, Eric W. Logistic Map. From MathWorld
A Wolfram Web Resource., http://mathworld.wolfram.com/
LogisticMap.html.
[Goldberg, 1991] Goldberg, D. (1991). What every computer scientist
should know about floating-point arithmetic ACM Computing Surveys,
23(1),548.
[Miyazaki, 2010] Miyazaki, T. and Araki, S. and Uehara, S. (2010). A study
on differences in properties of the logistic maps over integers affected
by rounding. Information Theory and its Applications (ISITA), 2010
International Symposium on, 10830835.

[Alvarez, 2006] Alvarez,

G., and S. Li (2006). Some Basic Cryptographic
Requirements for Chaos-Based Cryptosystems. International Journal
of Bifurcation and Chaos, 16(8), 21292151.
[Guyeux, 2010] Guyeux, C., QianxueWang, and J.M. Bahi (2010). A Pseudo
Random Numbers Generator Based on Chaotic Iterations: Application
to Watermarking. Web Information Systems and Mining, 6318, 202
211.
[Zheng, 2008] Zheng, F., Tian, X., Song, J., and X. LI (2008). Pseudorandom sequence generator based on the generalized Henon map. The
Journal of China Universities of Posts and Telecommunications, 15(3),
6468.

19

[Pareek, 2010] Pareek, N.K., Patidar, V., and K.K. Sud (2010). A Random
Bit Generator Using Chaotic Maps. International Journal of Network
Security, 10(1), 3238.
[Patidar, 2009a] Patidar, V., and K.K. Sud (2009a). A Pseudo Random Bit
Generator Based on Chaotic Logistic Map and its Statistical Testing.
Informatica 33, 441452.

[Or
ue, 2010] Or
ue, A.B., Alvarez,
G., Guerra, A., Pastor, G., Romera, M.,
and F. Montoya (2010). Trident, a new pseudo random number generator based on coupled chaotic maps. Computational Intelligence in Security for Information Systems, Advances in Intelligent and Soft Computing, 85, 183190.
[Bose, 1999] Bose, R., and A. Banerjee (1999). Implementing Symmetric
Cryptography Using Chaos Functions, in: Proceedings of the 7th International Conference on Advanced Computing and Communications
318321.
[Baptista, 1998] Baptista, M.S. (1998). Cryptography with chaos. Physics
Letters A, 240(1-2), 5054.
[Cecen, 2009] Cecen, S., Demirer, R.M., and C. Bayrak (2009). A new hybrid nonlinear congruential number generator based on higher functional power of logistic maps. Chaos, Solitons and Fractals, 42(2), 847
853.
[Xuan, 2011] Xuan, S., Zhang, G., and Y. Liao (2011). Chaos-based true
random number generator using image. in: IEEE International Conference on Computer Science and Service System (CSSS), Nanjing, China,
21452147.
[Pareek, 2006] Pareek, N.K., Patidar, V. and K.K. Sud (2006). Image encryption using chaotic logistic map. Image and Vision Computing,
24(9), 926934.
[IEEE, 2008] IEEE Standard for Floating-Point Arithmetic. IEEE Std 7542008, 158.
[Rukhin, 2010] Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker,
E., Leigh, S., Levenson, Vangel, M., Banks, D., Heckert, A., Dray, J.,
and S. Vo (2010). A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST Special
Publication Revision 1a.
[Patidar, 2011] Patidar, V., Pareek, N.K., Purohit, G., and K.K. Sud
(2011). A robust and secure chaotic standard map based pseudorandom
20

permutation-substitution scheme for image encryption. Optics Communications, 284(19), 43314339.

[Kendall, 1970] Kendall, M.G. (1970). Rank correlation methods. Fourth
ed., Griffin, London.
[Ecuyer, 2007] Lecuyer, P., and R. Simard (2007). TestU01: A C library
for empirical testing of random number generators. ACM Transactions
on Mathematical Software, 33 (4), 22-es.
[Marsaglia, 1996] Marsaglia, G. (1996). Diehard: a battery of tests of randomness. http://stat.fsu.edu/geo/diehard.html
[Biham, 1993] Biham, E., and A. Shamir (1993). Differential Cryptanalysis
of the Data Encryption Standard. Springer-Verlag.
[Yang, 2012] Yang, L., and T. Xiao-Jun (2012). A new pseudorandom number generator based on a complex number chaotic equation. Chinese
Physics B, 21(9), 17.
[Pareschi, 2006] Pareschi, F., Setti, G., and R. Rovatti, (2006). A Fast
Chaos-based True Random Number Generator for Cryptographic Applications. in: Proceedings of he 32nd European Solid-State Circuits
Conference (ESSCIRC), 130133.
[Ahmadi, 2009] Ahmadi, H., and T. Eghlidos (2009). Heuristic guess-anddetermine attacks on stream ciphers. Information Security, IET, 3(2),
66-73.

21

Algorithm 1 The PRBG algorithm

Require: X0 ; Y0 ; Z0 ; N ;
Ensure: A sequence of N blocks of 32 bits
1: Declaration: union ieee754 double F1 , F2 , F3 ;
2: Initialization: i = 1; j = 1; X = X0 ; Y = Y0 ; Z = Z0 ;
3: while i 30 do
4:
X 3.9999 X (1 X)
5:
Y 3.9999 Y (1 Y )
6:
Z 3.9999 Z (1 Z)
7:
ii+1
8: end while
9: while j N do
10:
X 3.9999 X (1 X)
11:
Y 3.9999 Y (1 Y )
12:
Z 3.9999 Z (1 Z)
13:
F1 (union ieee754 double ) & X
14:
F2 (union ieee754 double ) & Y
15:
F3 (union ieee754 double ) & Z
16:
M0X F1 > ieee.mantissa0
17:
M1X F1 > ieee.mantissa1
18:
M0Y F2 > ieee.mantissa0
19:
M1Y F2 > ieee.mantissa1
20:
M0Z F3 > ieee.mantissa0
21:
M1Z F3 > ieee.mantissa1
22:
k 32
23:
while k > 0 do
24:
lk1
25:
PX M0Z mod k
26:
PY M0X mod k
27:
PZ M0Y mod k
28:
Bx (M1X >> (PX ) & 1)
29:
By (M1Y >> (PY ) & 1)
30:
Bz (M1Z >> (PZ ) & 1)
31:
B (Bx + By + Bz ) mod 2 {output bit}
32:
bx (M1X >> (l) & 1)
33:
by (M1Y >> (l) & 1)
34:
bz (M1Z >> (l) & 1)
35:
if bx 6= Bx then
36:
M1X M1X (1 << (l))
37:
M1X M1X (1 << (PX ))
38:
end if
39:
if by 6= By then
40:
M1Y M1Y (1 << (l))
41:
M1Y M1Y (1 << (PY ))
42:
end if
43:
if bz 6= Bz then
44:
M1Z M1Z (1 << (l))
45:
M1Z M1Z (1 << (PZ ))
46:
end if
47:
k k1
48:
end while
49:
j j+1
50: end while

22