# Study of a New Chaotic Dynamical System and Its Usage in a Novel Pseudorandom Bit Generator

Authors: Ana-Cristina Dăscălescu; Radu Eugen Boriga; Adrian-Viorel Diaconu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

A new chaotic discrete dynamical system, built on trigonometric functions, is proposed. With intent to use this system within cryptographic applications, we proved with the aid of specific tools from chaos theory (e.g., Lyapunov exponent, attractor’s fractal dimension, and Kolmogorov-Smirnov test) and statistics (e.g., NIST suite of tests) that the newly proposed dynamical system has a chaotic behavior, for a large parameter’s value space, and very good statistical properties, respectively. Further, the proposed chaotic dynamical system is used, in conjunction with a binary operation, in the designing of a new pseudorandom bit generator (PRBG) model. The PRBG is subjected, by turns, to an assessment of statistical properties. Theoretical and practical arguments, rounded by good statistical results, confirm viability of the proposed chaotic dynamical system and newly designed PRBG, recommending them for usage within cryptographic applications.


---

## Body

## 1. Introduction

Nowadays, more and more, it appears that skilful genesis of chaos turns out to be a key issue in many technological application fields such as engineering, medicine, communications, information storage, and, with particular importance, cryptography [1–6].Designing of dynamical systems, intended to be used as base of cryptosystems, must be done so as to ensure the use of a set of associated control parameters’ values that leads to chaos [7–11]. Moreover, the ergodic [12–15] and randomness properties [16–19] must be confirmed, as a certainty of high security level of the chaotic dynamical system.Since 1963, when Lorenz found the first chaotic attractor in a three-dimensional autonomous system while studying atmospheric convection [20], chaotification became a very attractive subject, leading to the development of new chaotic dynamic systems, for example, [21–25], and new chaos-based PRBGs, for example, [26–30], whose properties have been analyzed extensively and thoroughly in research or review articles and books, for example, [31–36].Motivated by the extent of previous work, the present paper aims to present a new chaotic discrete dynamical system which, furthermore, may be included in the wide family of PRBGs through a simple, interesting, and yet complex new PRBG model, based on binary operation.The rest of this paper is organized as follows. Section2 presents the design of newly proposed dynamical system, including its chaotic behavior assessment (as a first step in system’s evaluation process to establish its suitability within any cryptographic application). Section 3 showcases the detailed and comprehensive randomness’ testing process of sequences generated by the new chaotic dynamical system (as a second step in system’s evaluation process to establish its suitability within any cryptographic application). Section 4 presents the designing of a new PRBG scheme (based on binary operation, which uses previously designed and tested chaotic dynamical system), including the results of analysis performed using NIST suite in order to test the randomness and uniformity of values generated by the new PRBG. Finally, Section 5 concludes the work carried out.


## 2. Proposed Discrete Dynamical System and Its Basic Properties

Newly dynamical system introduced in paper uses (1) [37, 38] as model for chaos generation. Here, whilst f represents a periodic real map (selected so as to ensure a large phase space), h represents a bounded real map (which, by an appropriate selection, restricts the phase space to a closed interval in which the dynamical system has good chaotic properties):
(1)xn+1=h(f(xn)).Therefore, the newly proposed one-dimensional discreet dynamic system, which is defined with respect to form (1), is given by (2) or (and), in a more detailed design, by (3). Here, r represents the control parameter of the resulted chaotic map, while arctg (i.e., arctangent function), and ctg (i.e., cotangent function), respectively, were chosen with respect to the above affirmations (i.e., the first one restricts the phase space to a close interval in which the dynamical system has good chaotic properties, while the second one ensures a large phase space):
(2)xn+1=fp(xn),(3)fp:[-1,1]⟶[-1,1],fp(x)=2πarctg(ctg(rx)).In the following, dynamical behavior of newly proposed chaotic system is investigated, by both theoretical analysis and numerical simulation (e.g., by means of Lyapunov exponent, attractor’s geometric shape and fractal structure, and system’s ergodicity, i.e., Kolmogorov-Smirnov tests, etc.).


### 2.1. Sensitivity Level to Initial Conditions

The behavior of the proposed discrete dynamic system (3), in terms of its evolution over time domain, depends on both the control parameter r and the initial condition x0. First of all, we propose stability analysis of fixed points in order to assess system’s sensitivity level to initial conditions.f
p map’s fixed points are given by (4), and, according to the theorem of fixed points [39], xk points are attractors if condition (5) is fulfilled, that is, if the control parameter r meets condition (6). Thus, taking into account the fact that fp map is defined on the interval [-1,1], there exists only one fixed point, that is, (7), which is also an attractor:
(4)tk=π(2k+1)2r+π,k∈ℤ,(5)|fp′(tk)|<1,k∈ℤ,(6)r<π2,(7)t0=π2r+π.From the above equations, it can be noticed that for anyr∈(0,π/2), all trajectories that start at initial point x0 converge, in time, to the attractor point t0; for any r>π/2, fixed point t0 loses its stability, and other instable fixed points appear. The aforementioned statements are also substantiated by the bifurcation diagram, namely, the one showcased in Figure 1(a), which emphasizes the stability of fp’s fixed points (i.e., for any values of parameter r, close to π/2, fp has an instable behavior, and for any values of the parameter r, higher than π/2, the map enters into a complete chaotic regime). The road to chaos of the fp map, with r>π/2, is not achieved through doubling process of the period, specific to some chaotic maps, but is induced by existence of a dense set of periodic orbits, whose periods are in the [-1,1] interval. Another tool used to assess fp’s sensitivity to the initial conditions is the Lyapunov exponent (8) and, taking into consideration the fact that orbit {x1,x2,…,xn} is chaotic if this exponent is positive, (9) is derived (which is equivalent to r>π/2, meaning that for any r∈(π/2,10)fp’s orbits are chaotic). Lyapunov exponent, numerically computed [40] with respect to the parameter r within (0,10) interval, is shown in Figure 1(b). Consider
(8)λ=limn→∞1n∑i=1nln|fp′(xi)|=limn→∞1n∑i=1nln|-2rπsin2rx(1+ctg2rx)|=ln2rπ(9)ln2rπ>0.Bifurcation diagram offp map (a) and Lyapunov exponent of fp map (b).
(a)
(b)


### 2.2. Attractor’s Geometric Shape and Fractal Structure

Analysis of dynamical system’s attractor’s shape can provide meaningful information about system behavior in time, for certain values of its parameters. The attractor of a dynamical system with a periodic behavior has a regular shape, while the one corresponding to a chaotic dynamical system has a complex structure, of fractal type, called strange attractor [39].Figure2 showcases fp’s attractor, for r=7, where it can be observed that its shape is irregular, of fractal type, and complex shaped, in comparison with ones of, for example, tent or logistic maps (i.e., whose attractors exhibit a regular shape, i.e., triangle, resp., hyperbola shaped).Figure 2
Attractor offp map, for r=7.Fractal structure of an attractor is indicated by a fractional value of its fractal dimension, which is a ratio that provides a statistical index of complexity comparing how in detail a pattern changes with the scale at which it is measured or, alternatively, by a measure of the space-filling capacity of a pattern, telling how a fractal scale is different than the space in which it is embedded. There are several types of fractal dimensions, which can be theoretically and empirically estimated, such as Hausdorff dimension, Minkowski-Bouligand dimension, box-counting dimension, information dimension, and correlation dimension [41–44]. Using plots from Figure 3, we established that the attractor of the fp map has a box-counting dimension Db = 0.97863 and a correlation dimension Dc = 0.97064. Fractional values, of fractal dimensions previously estimated, allow us to conclude that the proposed map has a strange attractor which, by turns, indicates a chaotic behavior.f
p’s attractor’s fractal dimensions: box-counting dimension (a) and correlation dimension (b).
(a)
(b)


### 2.3. System’s Ergodicity

In this subsection, using Birkhoff’s theorem [5, 45] in conjunction with Kolmogorov-Smirnov test [46, 47], we intend to prove that the proposed dynamical system is ergodic for r>π/2 (i.e., long-term behavior of fp’s orbits is independent from the initial condition, and thus it may be subjected to a battery of statistical tests).The Kolmogorov-Smirnov test is applied on two amounts of independent data(x1,x2,…,xn) and (y1,y2,…,yn), corresponding to the measurements of two random variables X and Y. Random variable X is obtained through an n-times iteration of fp map, for a fixed parameter r and for a fixed initial condition x0 (namely, r>π/2 and x0∈[-1,1]). Second random variable, that is, Y, is obtained by selecting, at time k, the values generated by n orbits of the map, arising from n initial seeding points (belonging to [-1,1] interval) and same r parameter (previously fixed). Moment k=100 is chosen from fp’s stationary zone, previously established using Kolmogorov-Smirnov test, as described in [46, 47].Due to the fact that the random valuesX and Y correspond to time average of fp and space average, respectively, the purpose of the test is to establish if the two experimental data sets derive from populations with the same distribution or not, with respect to Birkhoff’s theorem. The analysis is based on distribution functions FeX and FeY, associated with the experimental independent data sets X and Y.Kolmogorov-Smirnov test is applied as follows:(1)
the maximum absolute difference between the two distribution functionsδ is computed:
(10)δ=maxu|FeX(u)-FeY(u)|;(2)
for a significance levelα, Δα is computed (α representing probability law’s quantile, for the random value Δ); that is, P(Δ>Δα)=α,
(11)Δα≅n+mnm12ln2α;(3)
in case ofδ≤Δα, the hypothesis H0 is accepted (i.e., the two random variables X and Y have the same probability law; in other words, if the absolute maximum distance between the two distribution functions FeX and FeY is lower than a certain accepted value Δα, then it will be decided that the two random variables X and Y have the same probability law); otherwise the test rejects H0 hypothesis (i.e., for the chosen level, the two sets of experimental data come from random values with different probability laws).Kolmogorov-Smirnov test was performed over a sequence ofn=m=100.000 samples, with a significance level set to α=0.05; the decision regarding system’s ergodicity is based on Monte Carlo analysis (i.e., evaluating Kolmogorov-Smirnov test’s ability to accept bad data as good data). The above experiment was repeated 500 times; at the end of each round, H0 hypothesis’s acceptance proportion (which belongs to [0.93,0.97] interval) was recorded.Test’s overall results are summarized in Table1. One can observe that in case of all values selected for r parameter, with r∈(π/2,10), the acceptance proportion of H0 hypothesis lies within the confidence interval. Thus, ergodicity of the proposed dynamical system is confirmed (over the entire interval of interest, for parameter r).Table 1
Results offp’s ergodicity property testing.
Experiment iteration(s)
Parameter value
KS test value
Test result
1–49
—
∈ [0.93, 0.97]
PASSED
50
2.805107703154233
0.956
PASSED
51–99
—
∈ [0.93, 0.97]
PASSED
100
4.342554676193408
0.950
PASSED
101–149
—
∈ [0.93, 0.97]
PASSED
150
5.352537126362448
0.950
PASSED
151–199
—
∈ [0.93, 0.97]
PASSED
200
5.930260965351542
0.966
PASSED
201–249
—
∈ [0.93, 0.97]
PASSED
250
6.547089923300568
0.940
PASSED
251–299
—
∈ [0.93, 0.97]
PASSED
300
7.300182966818144
0.966
PASSED
301–349
—
∈ [0.93, 0.97]
PASSED
350
7.710976298365504
0.960
PASSED
351–399
—
∈ [0.93, 0.97]
PASSED
400
8.299998361920006
0.950
PASSED
401–449
—
∈ [0.93, 0.97]
PASSED
450
9.127429903281719
0.964
PASSED
451–499
—
∈ [0.93, 0.97]
PASSED
500
9.858890151572155
0.952
PASSEDBased on numerical results previously obtained, using instruments from the chaos theory, we can conclude thatfp map has a chaotic behavior, without intermittent scenarios, for any combination between the parameter r∈(π/2,10) and the initial seeding point x0∈[-1,1].The chaotic behavior is a necessary but not sufficient condition to allow usage of the proposed dynamic system within cryptographic applications. System’s security level, against some statistical cryptanalytic attacks, is assessed after a statistical analysis of the randomness of values generated. There are several options available for analyzing randomness of a newly developed pseudorandom bit generator (PRBG), as it will be revealed in the following section.


## 2.1. Sensitivity Level to Initial Conditions

The behavior of the proposed discrete dynamic system (3), in terms of its evolution over time domain, depends on both the control parameter r and the initial condition x0. First of all, we propose stability analysis of fixed points in order to assess system’s sensitivity level to initial conditions.f
p map’s fixed points are given by (4), and, according to the theorem of fixed points [39], xk points are attractors if condition (5) is fulfilled, that is, if the control parameter r meets condition (6). Thus, taking into account the fact that fp map is defined on the interval [-1,1], there exists only one fixed point, that is, (7), which is also an attractor:
(4)tk=π(2k+1)2r+π,k∈ℤ,(5)|fp′(tk)|<1,k∈ℤ,(6)r<π2,(7)t0=π2r+π.From the above equations, it can be noticed that for anyr∈(0,π/2), all trajectories that start at initial point x0 converge, in time, to the attractor point t0; for any r>π/2, fixed point t0 loses its stability, and other instable fixed points appear. The aforementioned statements are also substantiated by the bifurcation diagram, namely, the one showcased in Figure 1(a), which emphasizes the stability of fp’s fixed points (i.e., for any values of parameter r, close to π/2, fp has an instable behavior, and for any values of the parameter r, higher than π/2, the map enters into a complete chaotic regime). The road to chaos of the fp map, with r>π/2, is not achieved through doubling process of the period, specific to some chaotic maps, but is induced by existence of a dense set of periodic orbits, whose periods are in the [-1,1] interval. Another tool used to assess fp’s sensitivity to the initial conditions is the Lyapunov exponent (8) and, taking into consideration the fact that orbit {x1,x2,…,xn} is chaotic if this exponent is positive, (9) is derived (which is equivalent to r>π/2, meaning that for any r∈(π/2,10)fp’s orbits are chaotic). Lyapunov exponent, numerically computed [40] with respect to the parameter r within (0,10) interval, is shown in Figure 1(b). Consider
(8)λ=limn→∞1n∑i=1nln|fp′(xi)|=limn→∞1n∑i=1nln|-2rπsin2rx(1+ctg2rx)|=ln2rπ(9)ln2rπ>0.Bifurcation diagram offp map (a) and Lyapunov exponent of fp map (b).
(a)
(b)


## 2.2. Attractor’s Geometric Shape and Fractal Structure

Analysis of dynamical system’s attractor’s shape can provide meaningful information about system behavior in time, for certain values of its parameters. The attractor of a dynamical system with a periodic behavior has a regular shape, while the one corresponding to a chaotic dynamical system has a complex structure, of fractal type, called strange attractor [39].Figure2 showcases fp’s attractor, for r=7, where it can be observed that its shape is irregular, of fractal type, and complex shaped, in comparison with ones of, for example, tent or logistic maps (i.e., whose attractors exhibit a regular shape, i.e., triangle, resp., hyperbola shaped).Figure 2
Attractor offp map, for r=7.Fractal structure of an attractor is indicated by a fractional value of its fractal dimension, which is a ratio that provides a statistical index of complexity comparing how in detail a pattern changes with the scale at which it is measured or, alternatively, by a measure of the space-filling capacity of a pattern, telling how a fractal scale is different than the space in which it is embedded. There are several types of fractal dimensions, which can be theoretically and empirically estimated, such as Hausdorff dimension, Minkowski-Bouligand dimension, box-counting dimension, information dimension, and correlation dimension [41–44]. Using plots from Figure 3, we established that the attractor of the fp map has a box-counting dimension Db = 0.97863 and a correlation dimension Dc = 0.97064. Fractional values, of fractal dimensions previously estimated, allow us to conclude that the proposed map has a strange attractor which, by turns, indicates a chaotic behavior.f
p’s attractor’s fractal dimensions: box-counting dimension (a) and correlation dimension (b).
(a)
(b)


## 2.3. System’s Ergodicity

In this subsection, using Birkhoff’s theorem [5, 45] in conjunction with Kolmogorov-Smirnov test [46, 47], we intend to prove that the proposed dynamical system is ergodic for r>π/2 (i.e., long-term behavior of fp’s orbits is independent from the initial condition, and thus it may be subjected to a battery of statistical tests).The Kolmogorov-Smirnov test is applied on two amounts of independent data(x1,x2,…,xn) and (y1,y2,…,yn), corresponding to the measurements of two random variables X and Y. Random variable X is obtained through an n-times iteration of fp map, for a fixed parameter r and for a fixed initial condition x0 (namely, r>π/2 and x0∈[-1,1]). Second random variable, that is, Y, is obtained by selecting, at time k, the values generated by n orbits of the map, arising from n initial seeding points (belonging to [-1,1] interval) and same r parameter (previously fixed). Moment k=100 is chosen from fp’s stationary zone, previously established using Kolmogorov-Smirnov test, as described in [46, 47].Due to the fact that the random valuesX and Y correspond to time average of fp and space average, respectively, the purpose of the test is to establish if the two experimental data sets derive from populations with the same distribution or not, with respect to Birkhoff’s theorem. The analysis is based on distribution functions FeX and FeY, associated with the experimental independent data sets X and Y.Kolmogorov-Smirnov test is applied as follows:(1)
the maximum absolute difference between the two distribution functionsδ is computed:
(10)δ=maxu|FeX(u)-FeY(u)|;(2)
for a significance levelα, Δα is computed (α representing probability law’s quantile, for the random value Δ); that is, P(Δ>Δα)=α,
(11)Δα≅n+mnm12ln2α;(3)
in case ofδ≤Δα, the hypothesis H0 is accepted (i.e., the two random variables X and Y have the same probability law; in other words, if the absolute maximum distance between the two distribution functions FeX and FeY is lower than a certain accepted value Δα, then it will be decided that the two random variables X and Y have the same probability law); otherwise the test rejects H0 hypothesis (i.e., for the chosen level, the two sets of experimental data come from random values with different probability laws).Kolmogorov-Smirnov test was performed over a sequence ofn=m=100.000 samples, with a significance level set to α=0.05; the decision regarding system’s ergodicity is based on Monte Carlo analysis (i.e., evaluating Kolmogorov-Smirnov test’s ability to accept bad data as good data). The above experiment was repeated 500 times; at the end of each round, H0 hypothesis’s acceptance proportion (which belongs to [0.93,0.97] interval) was recorded.Test’s overall results are summarized in Table1. One can observe that in case of all values selected for r parameter, with r∈(π/2,10), the acceptance proportion of H0 hypothesis lies within the confidence interval. Thus, ergodicity of the proposed dynamical system is confirmed (over the entire interval of interest, for parameter r).Table 1
Results offp’s ergodicity property testing.
Experiment iteration(s)
Parameter value
KS test value
Test result
1–49
—
∈ [0.93, 0.97]
PASSED
50
2.805107703154233
0.956
PASSED
51–99
—
∈ [0.93, 0.97]
PASSED
100
4.342554676193408
0.950
PASSED
101–149
—
∈ [0.93, 0.97]
PASSED
150
5.352537126362448
0.950
PASSED
151–199
—
∈ [0.93, 0.97]
PASSED
200
5.930260965351542
0.966
PASSED
201–249
—
∈ [0.93, 0.97]
PASSED
250
6.547089923300568
0.940
PASSED
251–299
—
∈ [0.93, 0.97]
PASSED
300
7.300182966818144
0.966
PASSED
301–349
—
∈ [0.93, 0.97]
PASSED
350
7.710976298365504
0.960
PASSED
351–399
—
∈ [0.93, 0.97]
PASSED
400
8.299998361920006
0.950
PASSED
401–449
—
∈ [0.93, 0.97]
PASSED
450
9.127429903281719
0.964
PASSED
451–499
—
∈ [0.93, 0.97]
PASSED
500
9.858890151572155
0.952
PASSEDBased on numerical results previously obtained, using instruments from the chaos theory, we can conclude thatfp map has a chaotic behavior, without intermittent scenarios, for any combination between the parameter r∈(π/2,10) and the initial seeding point x0∈[-1,1].The chaotic behavior is a necessary but not sufficient condition to allow usage of the proposed dynamic system within cryptographic applications. System’s security level, against some statistical cryptanalytic attacks, is assessed after a statistical analysis of the randomness of values generated. There are several options available for analyzing randomness of a newly developed pseudorandom bit generator (PRBG), as it will be revealed in the following section.


## 3. Randomness Analysis of the Proposed Chaotic Discrete Dynamical System

In order to assess PRBG’s statistical properties (i.e., its true randomness and implicit suitability within cryptographic applications; see e.g., [48–52], etc.), different testing tools such as CrypTool and VRA (for basic statistical measures’ quantification), respectively NIST [53] and DIEHARD [54] standard tests batteries (for high end quantitative and qualitative assessment) were used. Operating methodology, for each of the above tests, and obtained results are presented and discussed in the following subsections.Chaotic cryptography deals with real numbers, so, in order to proceed and apply the battery of the statistical tests aforementioned, we have to apply a computational method to transform a chaotic sequence of real numbers into a bitstream. The discretization method that we used consisted in the extraction of the fractional parts of the generated subunitary real numbers.


### 3.1. CrypTool Analysis

CrypTool was used to compute the occurrence frequencies of any binary substring, composed ofn symbols (i.e., the n-grams), over the flow of bits generated with the proposed PRBG. For true random bitstreams, it is expected that each entry within the n-gram has the same probability of occurrence. The n-gram statistics were performed over 1.000 randomly chosen binary sequences, each sequence being generated using different initial seeding points and of i=1.000.000 bits in length; overall results are presented in Table 2.Table 2
PRBG’sn-gram reports.
n-gram’s order
Substring
Frequency (%)
|
Δ
|
Histogram(n=1)
0
50.0734
0.0734
1
49.9266
0.0734
Digram(n=2)
00
24.9605
0.0395
01
24.9660
0.0340
10
24.9660
0.0340
11
25.1074
0.1074
Trigram(n=3)
000
12.4899
0.0101
001
12.4706
0.0294
010
12.4293
0.0707
011
12.5367
0.0367
100
12.4705
0.0295
101
12.4954
0.0046
110
12.5367
0.0367
111
12.5707
0.0707
4-gram(n=4)
0000
6.2240
0.0260
0001
6.2659
0.0159
0010
6.2015
0.0485
0011
6.2691
0.0191
0100
6.2085
0.0415
0101
6.2208
0.0292
0110
6.2568
0.0068
0111
6.2799
0.0299
1000
6.2658
0.0158
1001
6.2047
0.0453
1010
6.2278
0.0222
1011
6.2676
0.0176
1100
6.2620
0.0120
1101
6.2746
0.0246
1110
6.2799
0.0299
1111
6.2908
0.0408
12-gram(n=12)
000000000000
0.0265
0.0020
—
≈0.0244
≈0
111111111111
0.0284
0.0039It can be observed that the deviation from ideal value, of eachn-gram’s entry, is under 0.1%. Thus, PRBG’s n-gram reports not only do not emphasize the dominant presence of any binary substring (i.e., in terms of frequency of use) [55, 56], but they also highlight a uniform system dynamics (i.e., in terms of the time evolution of fp’s trajectories). Positive results obtained at this point guide us to perform the next statistical analysis.


### 3.2. Visual Recurrence Analysis

A RP (i.e., Recurrence Plot) holds important insights into the time evolution offp’s trajectories because typical patterns in RPs are linked to specific system behavior [57]. Yet, without proper settings of analysis’ parameters, any RP is just a simple image, completely devoid of information. Thus, to obtain as much information, suitable embedding dimension and adequate time delay must be chosen. With the aid of AMI (i.e., Average Mutual Information) and FNN (i.e., False Nearest Neighbors) toolboxes (included in VRA’s statistical test suite), these parameters can be correctly set to the optimal value [58]. AMI and FNN were performed on binary sequences, each of i=1.000.000 bits in length (generated with 100 randomly chosen seeds); corresponding graphs are presented in Figures 4(a) and 4(b), respectively. Analyzing the two graphs, first AMI minimum and Optimal Global Embedding Dimension (OGED) are found: time delay d=3 and embedding dimension m=3. With these two parameters bitstream’s RPI (i.e., Recurrence Plot Image) is computed, as shown in Figure 4(c).PRBG’s visual recurrence analysis: AMI graph (a), FNN graph (b), and recurrence plot (c).
(a)
(b)
(c)Lack in clear patterns, within the RPI, indicates that consecutive samples in bitstream’s structure are much far apart and uncorrelated. More than that, RPI’s homogeneity along the major diagonal and its irregular distribution emphasizes a stationary, mostly stochastic behavior (i.e., intrinsically nondeterministic, nonintermittent, and sporadic), of the system that has generated the bitstream and, namely, a true random process (i.e., random binary strings).VRA, through its embedded RQA (i.e., Recurrence Quantification Analysis) tool, also provides other additional measures (e.g., entropy, mean, percentage of recurrence and of determinism, etc.); some of them, the most important ones, are quantified in Table3. One can notice that all the measures have values close to ideal [59].Table 3
PRBG’s general statistics.
Mean
Variance
Standard deviation
Skewness
Kurtosis
Entropy
0.5007
0.2500
0.5000
−0.0029
−1.9999
0.9999Despite the fact that skewness has a negative value (i.e., indicating that the tail on the left side of the probability density function is longer than the right side and the bulk of the values lie to the right of the mean), being close to zero indicates that the values are relatively evenly distributed on both sides of the mean, typically (but not necessarily) implying a symmetric distribution [60]. At the same time, Kurtosis’s high-level and negative value denotes a platykurtic distribution (i.e., data set with flatter peak around its mean, which causes thin tails within the distribution and low level of data fluctuation) [61].Good general statistical properties revealed with the aid of VRA (either visually—evaluation of RPI’s structural properties or through different specific measures evaluation—RQA), highlights randomness of bitstreams generated using the proposed PRBG function, thus allowing advancement to other statistical test suites.


### 3.3. NIST Statistical Testing

For the numerical experimentations of the proposed pseudorandom bit generator, we have generatedm=2.000 different binary sequences from 500 randomly chosen seeds, each sequence having a length of n=1.000.000 bits, and we have computed the p-value corresponding to each sequence for all the 15 tests of the NIST suite. The significance level of each test in NIST is set to 1%, which means that 99% of test samples pass the tests if the random numbers are truly random. The acceptance region of the passing ratio is given by (12), where m represents the number of samples tested and p=1-α is the probability of passing each test:
(12)[p-3p(1-p)m,p+3p(1-p)m].Form=2000 and the probability p=0.99 (corresponding to the significance level α=0.01), we obtained the confidence interval [0.983,0.996]. In the second column of Table 4, we have summarized the results obtained after applying nonparameterized and parameterized tests of the NIST suite on the binary sequences produced by the proposed pseudorandom bit generator. The computed proportion for each test lies inside the confidence interval. Hence, the tested binary sequences generated by the proposed PRBG are random with respect to all tests of NIST suite. If tested sequences are truly random, then p-values are expected to appear uniform in the interval [0,1). NIST recommends to apply the χ2-test in which the interval [0,1) is divided into 10 subintervals. Defining Fi as number of occurrences of the p-value in ith interval, then the χ2 statistic is (13). NIST recommends setting its significance level to 0.01%, so the acceptance region of statistics has the valueχ2≤33.72. A p-value that corresponds to uniformity of p-values is calculated as in (14), so it must be greater than 0.0001 to ensure that the p-values could be considered uniformly distributed. The results from the third column of Table 4 lead us to the conclusion that p-values, for each statistical test, are uniformly distributed:
(13)χ2=∑i=110(Fi-m/10)2(m/10),(14)igamc(92,χ22).Table 4
NIST tests’ results.
Test name
Passing ratio of the test
Uniformityp-value
Test result
Frequency
0.992
0.602803
PASSED
Block frequency
0.990
0.748891
PASSED
Cumulative sums
0.991
0.090388
PASSED
Runs
0.990
0.939005
PASSED
Longest run
0.989
0.592443
PASSED
Rank
0.991
0.840367
PASSED
FFT
0.989
0.242363
PASSED
Nonoverlapping template
0.983
0.761719
PASSED
Overlapping template
0.983
0.230755
PASSED
Universal
0.987
0.050629
PASSED
Approximate entropy
0.988
0.959347
PASSED
Random excursions
0.987
0.614382
PASSED
Random excursions variant
0.984
0.830939
PASSED
Serial
0.986
0.209392
PASSED
Linear complexity
0.989
0.764655
PASSEDThe method to calculate the passing ratio of total test and the uniformityp-value of total test samples follows the same methodology described above. In this case, we considered the number of samples m=30.000, so the acceptance region is [0.988,0.992]. For the passing ratio of the total test we obtained the value 0.988, and the p-value corresponding to the uniformity of p-values from the total test was 0.294808, so the proposed map has perfect cryptographic properties.


## 3.1. CrypTool Analysis

CrypTool was used to compute the occurrence frequencies of any binary substring, composed ofn symbols (i.e., the n-grams), over the flow of bits generated with the proposed PRBG. For true random bitstreams, it is expected that each entry within the n-gram has the same probability of occurrence. The n-gram statistics were performed over 1.000 randomly chosen binary sequences, each sequence being generated using different initial seeding points and of i=1.000.000 bits in length; overall results are presented in Table 2.Table 2
PRBG’sn-gram reports.
n-gram’s order
Substring
Frequency (%)
|
Δ
|
Histogram(n=1)
0
50.0734
0.0734
1
49.9266
0.0734
Digram(n=2)
00
24.9605
0.0395
01
24.9660
0.0340
10
24.9660
0.0340
11
25.1074
0.1074
Trigram(n=3)
000
12.4899
0.0101
001
12.4706
0.0294
010
12.4293
0.0707
011
12.5367
0.0367
100
12.4705
0.0295
101
12.4954
0.0046
110
12.5367
0.0367
111
12.5707
0.0707
4-gram(n=4)
0000
6.2240
0.0260
0001
6.2659
0.0159
0010
6.2015
0.0485
0011
6.2691
0.0191
0100
6.2085
0.0415
0101
6.2208
0.0292
0110
6.2568
0.0068
0111
6.2799
0.0299
1000
6.2658
0.0158
1001
6.2047
0.0453
1010
6.2278
0.0222
1011
6.2676
0.0176
1100
6.2620
0.0120
1101
6.2746
0.0246
1110
6.2799
0.0299
1111
6.2908
0.0408
12-gram(n=12)
000000000000
0.0265
0.0020
—
≈0.0244
≈0
111111111111
0.0284
0.0039It can be observed that the deviation from ideal value, of eachn-gram’s entry, is under 0.1%. Thus, PRBG’s n-gram reports not only do not emphasize the dominant presence of any binary substring (i.e., in terms of frequency of use) [55, 56], but they also highlight a uniform system dynamics (i.e., in terms of the time evolution of fp’s trajectories). Positive results obtained at this point guide us to perform the next statistical analysis.


## 3.2. Visual Recurrence Analysis

A RP (i.e., Recurrence Plot) holds important insights into the time evolution offp’s trajectories because typical patterns in RPs are linked to specific system behavior [57]. Yet, without proper settings of analysis’ parameters, any RP is just a simple image, completely devoid of information. Thus, to obtain as much information, suitable embedding dimension and adequate time delay must be chosen. With the aid of AMI (i.e., Average Mutual Information) and FNN (i.e., False Nearest Neighbors) toolboxes (included in VRA’s statistical test suite), these parameters can be correctly set to the optimal value [58]. AMI and FNN were performed on binary sequences, each of i=1.000.000 bits in length (generated with 100 randomly chosen seeds); corresponding graphs are presented in Figures 4(a) and 4(b), respectively. Analyzing the two graphs, first AMI minimum and Optimal Global Embedding Dimension (OGED) are found: time delay d=3 and embedding dimension m=3. With these two parameters bitstream’s RPI (i.e., Recurrence Plot Image) is computed, as shown in Figure 4(c).PRBG’s visual recurrence analysis: AMI graph (a), FNN graph (b), and recurrence plot (c).
(a)
(b)
(c)Lack in clear patterns, within the RPI, indicates that consecutive samples in bitstream’s structure are much far apart and uncorrelated. More than that, RPI’s homogeneity along the major diagonal and its irregular distribution emphasizes a stationary, mostly stochastic behavior (i.e., intrinsically nondeterministic, nonintermittent, and sporadic), of the system that has generated the bitstream and, namely, a true random process (i.e., random binary strings).VRA, through its embedded RQA (i.e., Recurrence Quantification Analysis) tool, also provides other additional measures (e.g., entropy, mean, percentage of recurrence and of determinism, etc.); some of them, the most important ones, are quantified in Table3. One can notice that all the measures have values close to ideal [59].Table 3
PRBG’s general statistics.
Mean
Variance
Standard deviation
Skewness
Kurtosis
Entropy
0.5007
0.2500
0.5000
−0.0029
−1.9999
0.9999Despite the fact that skewness has a negative value (i.e., indicating that the tail on the left side of the probability density function is longer than the right side and the bulk of the values lie to the right of the mean), being close to zero indicates that the values are relatively evenly distributed on both sides of the mean, typically (but not necessarily) implying a symmetric distribution [60]. At the same time, Kurtosis’s high-level and negative value denotes a platykurtic distribution (i.e., data set with flatter peak around its mean, which causes thin tails within the distribution and low level of data fluctuation) [61].Good general statistical properties revealed with the aid of VRA (either visually—evaluation of RPI’s structural properties or through different specific measures evaluation—RQA), highlights randomness of bitstreams generated using the proposed PRBG function, thus allowing advancement to other statistical test suites.


## 3.3. NIST Statistical Testing

For the numerical experimentations of the proposed pseudorandom bit generator, we have generatedm=2.000 different binary sequences from 500 randomly chosen seeds, each sequence having a length of n=1.000.000 bits, and we have computed the p-value corresponding to each sequence for all the 15 tests of the NIST suite. The significance level of each test in NIST is set to 1%, which means that 99% of test samples pass the tests if the random numbers are truly random. The acceptance region of the passing ratio is given by (12), where m represents the number of samples tested and p=1-α is the probability of passing each test:
(12)[p-3p(1-p)m,p+3p(1-p)m].Form=2000 and the probability p=0.99 (corresponding to the significance level α=0.01), we obtained the confidence interval [0.983,0.996]. In the second column of Table 4, we have summarized the results obtained after applying nonparameterized and parameterized tests of the NIST suite on the binary sequences produced by the proposed pseudorandom bit generator. The computed proportion for each test lies inside the confidence interval. Hence, the tested binary sequences generated by the proposed PRBG are random with respect to all tests of NIST suite. If tested sequences are truly random, then p-values are expected to appear uniform in the interval [0,1). NIST recommends to apply the χ2-test in which the interval [0,1) is divided into 10 subintervals. Defining Fi as number of occurrences of the p-value in ith interval, then the χ2 statistic is (13). NIST recommends setting its significance level to 0.01%, so the acceptance region of statistics has the valueχ2≤33.72. A p-value that corresponds to uniformity of p-values is calculated as in (14), so it must be greater than 0.0001 to ensure that the p-values could be considered uniformly distributed. The results from the third column of Table 4 lead us to the conclusion that p-values, for each statistical test, are uniformly distributed:
(13)χ2=∑i=110(Fi-m/10)2(m/10),(14)igamc(92,χ22).Table 4
NIST tests’ results.
Test name
Passing ratio of the test
Uniformityp-value
Test result
Frequency
0.992
0.602803
PASSED
Block frequency
0.990
0.748891
PASSED
Cumulative sums
0.991
0.090388
PASSED
Runs
0.990
0.939005
PASSED
Longest run
0.989
0.592443
PASSED
Rank
0.991
0.840367
PASSED
FFT
0.989
0.242363
PASSED
Nonoverlapping template
0.983
0.761719
PASSED
Overlapping template
0.983
0.230755
PASSED
Universal
0.987
0.050629
PASSED
Approximate entropy
0.988
0.959347
PASSED
Random excursions
0.987
0.614382
PASSED
Random excursions variant
0.984
0.830939
PASSED
Serial
0.986
0.209392
PASSED
Linear complexity
0.989
0.764655
PASSEDThe method to calculate the passing ratio of total test and the uniformityp-value of total test samples follows the same methodology described above. In this case, we considered the number of samples m=30.000, so the acceptance region is [0.988,0.992]. For the passing ratio of the total test we obtained the value 0.988, and the p-value corresponding to the uniformity of p-values from the total test was 0.294808, so the proposed map has perfect cryptographic properties.


## 4. Proposed PRBG and Its Statistical Testing

Most chaos-based PRNGs (and, implicitly, their subsequent PRBGs) are based on a single chaotic system (e.g., [25–29, 52]) and generate the random numbers (resp., the bitstreams) directly from its orbit. These types of PRNGs/PRBGs are potentially insecure, since the output values may expose some information about their underlying chaotic system [62]. To overcome this difficulty, a series of pseudorandom number (bit) generators based on a couple of chaotic system have been proposed (e.g., [63–67]). In the following, we present a novel PRNG/PRBG model, based on two chaotic maps coupled using a binary operation.We consider two one-dimensional chaotic maps (e.g., as the previously designed model, i.e., (3)) defined as follows:
(15)f1:[-1,1]⟶[-1,1],f1(x,r1)=2πarctg(ctg(r1x)),f2:[-1,1]⟶[-1,1],f2(x,r2)=2πarctg(ctg(r2x)),
where x01, x02 are the initial conditions, r1, r2 are the control parameters, and xi1, xi2 are the two orbits obtained by recurrences xi+11=f1(xi1,r1), xi+12=f2(xi2,r2), for any i∈{0,1,2,…}.Also, we consider the binary operation given by the formula(16)a*b=a+b1-a·b,
where a,b∈[-1,1].The output{y0,y1,y2,…} of the proposed PRNG is obtained applying the binary operation (16) to the chaotic maps f1 and f2 defined by (15); thus,
(17)yi=f1(xi1,r1)*f2(xi2,r2)=f1(xi1,r1)+f2(xi2,r2)1-f1(xi1,r1)·f2(xi2,r2)
for any i∈{0,1,2,…} and (x01,r1,x02,r2)∈[-1,1]×[1,10]×[-1,1]×[1,10] is the seed of the proposed PRNG.The real numbers obtained using the proposed PRNG were discretized extracting their fractional parts in order to apply the NIST statistical tests. For the numerical experimentations on the proposed pseudorandom numbers generator, we have generated 2.000 different binary sequences (sample sizem=2.000). Each sequence, with one million bits in length, has been generated from a randomly chosen seed (x01,r1,x02,r2), and for each we computed the p-value corresponding to the NIST tests. In Table 5 we have summarized the results obtained after implementing nonparameterized and parameterized tests of NIST suite on the binary sequences produced by the proposed pseudorandom numbers generator.Table 5
NIST tests’ results.
Test name
Passing ratio of the test
Uniformityp-value
Test result
Frequency
0.991
0.045971
PASSED
Block frequency
0.991
0.653773
PASSED
Cumulative sums
0.990
0.035876
PASSED
Runs
0.991
0.235589
PASSED
Longest run
0.987
0.937919
PASSED
Rank
0.994
0.221898
PASSED
FFT
0.988
0.160357
PASSED
Nonoverlapping template
0.986
0.036592
PASSED
Overlapping template
0.985
0.316808
PASSED
Universal
0.989
0.703417
PASSED
Approximate entropy
0.991
0.129620
PASSED
Random excursions
0.992
0.806491
PASSED
Random excursions variant
0.985
0.885727
PASSED
Serial
0.987
0.737475
PASSED
Linear complexity
0.990
0.325206
PASSEDIt can be seen that the computed proportion for each test lies inside the confidence interval; hence, the tested binary sequences generated by the proposed PRBG are random with respect to all the 16 tests of NIST suite.


## 5. Conclusions

Development of new chaotic dynamic systems, which meet the current demands of security, is a present research direction in the field of cryptography. The main objective is to obtain a large key space, induced by the control parameter and (or) initial conditions, for which the dynamic system is in chaotic regime, is ergodic, and has a uniform distribution of the values​​generated.With respect to the aforementioned ideas, in this paper we have designed a new one-dimensional chaotic dynamic system that meets these requirements.Moreover, a larger key space than the one of the known chaotic maps (e.g., logistic, tent, Hénon, etc.) was achieved, and, despite the fact that the implementation of trigonometric maps is little slower than the ones of other kinds of maps (e.g., polynomial, exponential, etc.), we consider that the advantage of a larger key space induced by their usage is a good compromise (i.e., a win-win situation).Using specific mathematical and numerical tools from chaos theory and statistics, we proved that the proposed chaotic dynamic system has very good cryptographic properties. The proposed map was used in a new innovative way to design a new PRNG/PRBG model, based on a well-known binary operation.We have performed an exhaustive testing process of the randomness of the generated binary sequences using the NIST suite to prove the viability of the proposed PRNG/PRBG.



---

*Source: 769108-2013-11-20.xml*