# Performance of Finite Precision on Discrete Chaotic Map Based on a Feedback Shift Register

Authors: Chunguang Huang; Qun Ding
Journal: Complexity
 (2020)

---

## Abstract

The scintillating technological improvements have changed the process of communication in all parts of the world. Shopping, banking, instant communication, and so on can be operated online and do not care about the linkage of those Internet communications. Because of simple chaotic structure, discrete nature, less arithmetic computation, and high complexity, low-dimensional chaotic systems such as a logistic map and tent map are more attractive than a high-dimensional chaotic system. To overcome the disadvantages of a low-dimensional chaotic map with a finite precision in chaos-based application, the chaotic map with a feedback shift register (CMFSR) is proposed. The related properties and performance associated with CMFSR are analysed. The relationship among the precision of the system, the architecture, and the performance are discussed. The experiments about new pseudorandom number generator (PRNG) based on CMFSR show that our scheme is simple, secure, and easy to accomplish. Experiments show that the proposed architecture of CMFSR is secure for random number generation.


---

## Body

## 1. Introduction

The digitalized message and data transmitted on the Internet becomes a major and essential part of information in the present world. The appearance of intruders in the communication between people need security solutions to protect the information in transmission. It is very crucial to protect the message from the sender to the receiver. A mathematical theory of cryptography plays a significant role in information security [1, 2]. One of the crucial common alikeness in traditional encryption schemes such as Data Encryption Standard [3] (DES), International Data Encryption Algorithm [4] (IDEA), and Advanced Encryption Standard [5] (AES) is to have the key to encrypt or decrypt the information. All of the encryption schemes mentioned are the block cipher. In the last decade, cryptography based on the chaotic system has received considerable attention from the security community and research because of the sensibility to initial conditions, chaotic system parameters, and pseudorandom parameters. All these properties can be used to design encryption algorithms with perfect complexity and excellent confusion and diffusion process.Pseudorandom number generators (PRNGs) [6–8] are a vital area of research due to its ubiquitous use [9] in a variety of applications such as cryptography. In particular, the chaotic map has been designed for many PRNGs. Some researchers use the chaotic system to build the cryptographic primitives such as public-key encryption algorithm and hashing functions. The sequence of a random number is said to be pseudorandom although the sequences seem to be random. The true random number generator (TRNG) is infinite, aperiodic, uncorrelated, and efficient for hardware and software [10]. It is hard to use the TRNG in modern digital devices because of infinite precision.In the literature, many algorithms are designed to produce PRNS with numerical methods such as linear congruential generator, midsquare method generator, or Fibonacci generator. However, these generators have proven to be not safe. Chaotic-based nonlinear functions because of their high sensitivity to initial conditions, aperiodicity, and unpredictability are used for PRNGs.Chaotic systems are classified into two types: continuous system and discrete system. In the real world, most models of nature are continuous such as variation of population or climate. For some applications on digital devices, the continuous chaotic system should be discretized. However, the performance of the discrete chaotic system degrades because of the finite precision effect. Some research studies do lots of investigation to improve the performance in low-dimensional systems [11–14] and high-dimension systems [15, 16]. Hua et al. [13, 14] proposed a novel and efficient low-dimensional chaotic system with high complexity. One dimension chaotic map such as the logistic map or tent map is efficient and straightforward theoretically and easy to realize in digital devices. However, when chaos is realized in digital devices such as CPU, MCU, or FPGA, the chaotic property will degrade with finite precision. Thus, the chaotic map with finite precision will fall into a cycle or some static point. Moreover, it will lead to serious negative result on some finite precision chaotic application [17].But one dimension chaotic map cannot be infinite or aperiodic when implemented with a finite precision hardware system such as a computer or FPGA [18]. Persohn and Povinelli [19] analyzed the PRNG based on logistic by finite precision floating-point representation. Real number implementations on finite precision are detrimental to the periodicity of the chaotic PRNGs. Sayed et al. [20] gave a methodology for fixed-point simulation of the generalized one-dimensional logistic map with the signed parameter and implemented in FPGA. The influence of a finite precision should be considered and the trade-off between computation performance and randomness is the key to design a pseudorandom number generator. Fan and Ding [21] analyze the logistic chaotic sequences with different computational precision thought autocorrelation function, permutation entropy, and statistical analysis. For every sequence of period p, the modified sequences have the same period length p. Che at el. [22] proposed a PRNG based on a digitalized modified logistic map, where the parameter of logistic map γ≥4. There are two multiplications needed in the system. The input of the logistic map is the combination of the LFSR and logistic map. The architecture of LFSR is not discussed clearly and not altered by the logistic map to improve it complexity. Some chaotic maps [23] are so complicated to calculate in floating-point notation which leads to massive latency in digital devices such as FPGA or MCU. Elmanfaloty and Abou-Bakr [24] discussed and proposed a one dimension chaotic map with finite precision implementation. But this kind of PRNG is only suitable for a tent map not for other one dimension chaotic map.This paper is organized as follows. In Section2, the classic traditional one dimension chaotic maps are introduced. Section 3 discusses the influence of finite precision on the discrete chaotic map on finite precision. A short period in the logistic map with finite precision comes out. It cannot be used in the most applications. So, an enhanced CMFSR is proposed in Section 4. The feedback shift register is used to improve the periodicity of the sequence. In Section 5, the logistic map and tent map with the feedback shift register are chosen to analyse the performance. Moreover, the statics and analysis of finite precision CMFSR are presented. Finally, Section 6 summarizes the contribution of this paper.


## 2. Traditional Chaotic Map

This section introduces the definition of the logistic map and tent map which are used in the following section.


### 2.1. Logistic Map with Finite Precision

The logistic map [25] is a very simple one-dimensional map widely used in growth biological population, complex system, pseudorandom number generator, and some cryptography. The logistic map is a discrete-time dynamic system that is described mathematically as follows:(1)fxn=xn+1=μxn1−xn.Here,x0 is the initial value which is the seed of the logistic map. Then, the xn can be generated after n times iteration. And xn is also a number between zero and one according to equation (1) and the value of the parameter μ are those in the interval [0, 4]. The system is chaotic if r∈3.57,4.In statistics, we describe a random movement with the word ergodicity to describe the statistic distribution of the state value of the system. Furthermore, the ergodicity can be described as the statistical probability distributions of the state value. Logistic maps with different system parametersμ are shown in Figure 1. All these three logistic maps with different parameters μ run with the same initial value x0 after 1000 iterations.Figure 1
Graphic iterations and probability distributions for the logistic map.
(a)
(b)
(c)
(d)
(e)
(f)It can be seen from Figure1 that the range of the x-value is in [0, 1] when μ=4, the range of the x-value is reduced with the decrease of the parameter value. It means that the ergodicity of the logistic map in interval [0, 1] gets better with the increase of the parameter μ.The distributions of these three logistic maps are shown in Figure1. The distribution range of the logistic map is expanded with the increase of the parameter μ. But the distribution is not even for each x-value because of the architecture of the logistic system. Graphic iterations of the logistic map with different parameters are shown in Figure 1(a) when μ=3.4, Figure 1(b) when μ=3.7, and Figure 1(c) when μ=4.0. The distribution of the logistic map with different parameters is shown in Figures 1(d)–1(f) separately.


### 2.2. Tent Map with Finite Precision

The tent map is also a one-dimensional chaotic map. The definition of the tent map is shown as follows:(2)xn+1=μxn,0≤xn<0.5,μ1−xn,0.5≤xn,where the initial condition of the chaotic tent map is xn and μ is the control parameter that lies in the range of [0, 2]. The tent map is a one-dimensional chaotic map. Moreover, it shows the chaotic behaviour when the control parameter value is close to 2. The distribution of the chaotic tent map with varying control parameter value, as shown in Figure 2. The x-axis is the value of xn and the y-axis is the frequency counts. Figures 2(a)–2(c) show the distribution of the tent map in a different parameter.Figure 2
Probability distributions for tent map.
(a)
(b)
(c)


## 2.1. Logistic Map with Finite Precision

The logistic map [25] is a very simple one-dimensional map widely used in growth biological population, complex system, pseudorandom number generator, and some cryptography. The logistic map is a discrete-time dynamic system that is described mathematically as follows:(1)fxn=xn+1=μxn1−xn.Here,x0 is the initial value which is the seed of the logistic map. Then, the xn can be generated after n times iteration. And xn is also a number between zero and one according to equation (1) and the value of the parameter μ are those in the interval [0, 4]. The system is chaotic if r∈3.57,4.In statistics, we describe a random movement with the word ergodicity to describe the statistic distribution of the state value of the system. Furthermore, the ergodicity can be described as the statistical probability distributions of the state value. Logistic maps with different system parametersμ are shown in Figure 1. All these three logistic maps with different parameters μ run with the same initial value x0 after 1000 iterations.Figure 1
Graphic iterations and probability distributions for the logistic map.
(a)
(b)
(c)
(d)
(e)
(f)It can be seen from Figure1 that the range of the x-value is in [0, 1] when μ=4, the range of the x-value is reduced with the decrease of the parameter value. It means that the ergodicity of the logistic map in interval [0, 1] gets better with the increase of the parameter μ.The distributions of these three logistic maps are shown in Figure1. The distribution range of the logistic map is expanded with the increase of the parameter μ. But the distribution is not even for each x-value because of the architecture of the logistic system. Graphic iterations of the logistic map with different parameters are shown in Figure 1(a) when μ=3.4, Figure 1(b) when μ=3.7, and Figure 1(c) when μ=4.0. The distribution of the logistic map with different parameters is shown in Figures 1(d)–1(f) separately.


## 2.2. Tent Map with Finite Precision

The tent map is also a one-dimensional chaotic map. The definition of the tent map is shown as follows:(2)xn+1=μxn,0≤xn<0.5,μ1−xn,0.5≤xn,where the initial condition of the chaotic tent map is xn and μ is the control parameter that lies in the range of [0, 2]. The tent map is a one-dimensional chaotic map. Moreover, it shows the chaotic behaviour when the control parameter value is close to 2. The distribution of the chaotic tent map with varying control parameter value, as shown in Figure 2. The x-axis is the value of xn and the y-axis is the frequency counts. Figures 2(a)–2(c) show the distribution of the tent map in a different parameter.Figure 2
Probability distributions for tent map.
(a)
(b)
(c)


## 3. Influence of Finite Precision on Discrete Chaotic Map

Chaotic systems are some mathematical equations/models derived from the rules of chaotic special behaviours. The logistic map is used to simulate the population growth [26] and a tent map is used to describe the stretching and folding of a one-dimensional elastic band of length one [27]. Theoretically, a chaotic system’s attractors are locally divergent and globally convergent. However, all the software/hardware platforms cannot own infinite precision. These withdraw causes negative impacts on some chaos-based applications. Some chaos-based applications based on the finite precision chaotic system are not secure because of the chaos degradation [28]. The periodicity, the orbit, and finite states of the chaotic system could be calculated and attacked by a high-performance computer. In this section, the logistic map is selected to analyze the performance of the one-dimensional chaotic map with finite precision.


### 3.1. Logistic Map with Finite Precision

In Section2, equation (1) is the definition of the logistic. It should be noted that the continuous logistic map is real. We can measure and analyze the property of the logistic map through the mathematical method or analogue circuit. But it cannot be used on a digital platform, so finite resolution of number using a binary representation is proposed for these applications.So, the value of the logistic map with an infinite precision can be written in a binary format as follows:(3)xn=a020+a121+⋯+ai2i+⋯=∑i=0∞ai2i,ai=0,1.AL-bits binary is used to represent x_n, and then x_n with L-bit precision xn¯ can be written as follows:(4)xn¯≈a020+a121+⋯+aL2L=∑i=1Lai2i,ai∈0,1.In the rest of the paper, we letzn=xn¯, and the logistic map with L-bit precision is given by(5)zn+1=μzn2L−zn≫L−2,where z_n is the iterated variable of the logistic map with L-bit precision, μ is a control parameter, and μ=4. Here symbol ≫L means a binary sequence shifts to right L bits. According to (5), we can zn+1 with L-bit precision for the next iteration. In order to evaluate the performance degradation with finite precision, some experiments have been carried out for different precision.


### 3.2. Distribution

The histogram is a graphical representation of the distribution of the logistic map output. And an equal probability of each series can generate a uniform distribution. Figure3 shows the distribution of the finite precision logistic map. Figures 3(a)–3(d) are the logistic map value distribution in different precision. It shows that distribution turns to flat and even with the increase of the precision of the logistic map. But the distribution of the value cannot be even because of the attribution of the logistic map.Figure 3
Distribution with different precision.According to equation (4), we set L equal 4, 8, 12, and 16 separately and initial value z0=1. Then, zn can be obtained after n times iteration. With the increase of precision, the distribution is not even for all values of the logistic map although the distribution becomes better.Figure4 shows the periodicity with the same initial value x0=1 for different precision. It shows that the length of cycle is varied randomly with a different precision. The cycle of the 7-bit logistic map is the longest compared to the other logistic map. And the number of iterations before cycle comes out is also random.Figure 4
Periodicity with the same initial valuex0=1 for different precision.To evaluate the relationship between precision and period, we set precisionL from 4 to 56, initial value of the system is 1, and control parameter μ is 4. Figure 5 shows the iteration times and period for all the logistic map with a different precision. The horizontal axis of the scatter plot denotes the precision of a logistic map from 4 to 27 shown in Figure 5(a) and 28 to 56 shown in Figure 5(b). And the vertical axis denotes the number of samples generated with equation (4). The blue bar in the figure denotes the iteration times before the logistic map running into the periodic orbit. And the yellow bar shows the period length of the logistic map with a concrete value on the top of a bar. By experimenting with a different precision, the period length of logistic system does not increase with the precision of the logistic.Figure 5
Relationship between precision and period of the logistic map. (a) 27-bits. (b) 27-bits to 56-bits.
(a)
(b)


## 3.1. Logistic Map with Finite Precision

In Section2, equation (1) is the definition of the logistic. It should be noted that the continuous logistic map is real. We can measure and analyze the property of the logistic map through the mathematical method or analogue circuit. But it cannot be used on a digital platform, so finite resolution of number using a binary representation is proposed for these applications.So, the value of the logistic map with an infinite precision can be written in a binary format as follows:(3)xn=a020+a121+⋯+ai2i+⋯=∑i=0∞ai2i,ai=0,1.AL-bits binary is used to represent x_n, and then x_n with L-bit precision xn¯ can be written as follows:(4)xn¯≈a020+a121+⋯+aL2L=∑i=1Lai2i,ai∈0,1.In the rest of the paper, we letzn=xn¯, and the logistic map with L-bit precision is given by(5)zn+1=μzn2L−zn≫L−2,where z_n is the iterated variable of the logistic map with L-bit precision, μ is a control parameter, and μ=4. Here symbol ≫L means a binary sequence shifts to right L bits. According to (5), we can zn+1 with L-bit precision for the next iteration. In order to evaluate the performance degradation with finite precision, some experiments have been carried out for different precision.


## 3.2. Distribution

The histogram is a graphical representation of the distribution of the logistic map output. And an equal probability of each series can generate a uniform distribution. Figure3 shows the distribution of the finite precision logistic map. Figures 3(a)–3(d) are the logistic map value distribution in different precision. It shows that distribution turns to flat and even with the increase of the precision of the logistic map. But the distribution of the value cannot be even because of the attribution of the logistic map.Figure 3
Distribution with different precision.According to equation (4), we set L equal 4, 8, 12, and 16 separately and initial value z0=1. Then, zn can be obtained after n times iteration. With the increase of precision, the distribution is not even for all values of the logistic map although the distribution becomes better.Figure4 shows the periodicity with the same initial value x0=1 for different precision. It shows that the length of cycle is varied randomly with a different precision. The cycle of the 7-bit logistic map is the longest compared to the other logistic map. And the number of iterations before cycle comes out is also random.Figure 4
Periodicity with the same initial valuex0=1 for different precision.To evaluate the relationship between precision and period, we set precisionL from 4 to 56, initial value of the system is 1, and control parameter μ is 4. Figure 5 shows the iteration times and period for all the logistic map with a different precision. The horizontal axis of the scatter plot denotes the precision of a logistic map from 4 to 27 shown in Figure 5(a) and 28 to 56 shown in Figure 5(b). And the vertical axis denotes the number of samples generated with equation (4). The blue bar in the figure denotes the iteration times before the logistic map running into the periodic orbit. And the yellow bar shows the period length of the logistic map with a concrete value on the top of a bar. By experimenting with a different precision, the period length of logistic system does not increase with the precision of the logistic.Figure 5
Relationship between precision and period of the logistic map. (a) 27-bits. (b) 27-bits to 56-bits.
(a)
(b)


## 4. Chaotic Map with Feedback Shift Register

This section proposes an architecture of CMFSR and discusses its properties and analyzes its chaotic behaviour.


### 4.1. Structures of CMFSR

There are four parts in the structure of the CMFSR which is shown in Figure6. Part 1 is a logistic map system with special precision. Part 2 is a feedback shift register with L shift unit. Part 3 is a control unit to control the operation of the value of the shift register. Part 4 is a combination module to combine the output from part 3.Figure 6
Structure of the CMFSR.


#### 4.1.1. Part 1: Chaotic Map

Part 1 is a discrete chaotic map withL-bit precision. The parameter of the system is μ, the input of chaotic map is the L-bit binary from part 4, and the output of part 1 is also L-bit binary as the input of the shift register.Mathematically, the proposed part 1 with the logistic map inL-bit precision can be defined as equation (5). The value range of control parameter μ is [3.5699456, 4], then the logistic map runs into a chaotic state. The closer the parameter reaches 4, the higher the Lyapunov exponent is and the better the chaotic property is.As for the tent map [29], the tent map works in the chaotic state with the control parameter in the range of 1<μ<2.


#### 4.1.2. Part 2: Feedback Shift Register

Part 2 is a feedback shift register (FSR) withk units and each unit has L-bit registers which can increase the linear complexities of the output sequence. The input of FSR is Sk which is an L-bit binary, and the output of the logistic map. And an L-bit binary from S0 is the output of Part 2 and it is also the output of the system. The value of the shift registers shifts from right to left in an order which can be written as follows: Si−1=Si. And the shift registers move when the output of Part 1 is generated.


#### 4.1.3. Part 3: Control Module

Part 3 is a control module to control the movement of theL-bit binary series. A control module can decide whether the series is passed to part 4 and how to change a L-bit binary series to get the high performance. Si will transform to S¯i according to the value of the control module parameter qi. Then, Si¯=qSi,m∈GF2L. Here, parameter m means left-cyclic shift m bits.Letdi=0,1∈GF2, then Si is the set of all binary sequence of length L.S
i
=
0,1
n
=
d
L
−
1
d
L
−
2
⋯
d
1
d
0. There are L bits binary sequence and di is one of them.LetqSi,1=dL−1dL−2⋯d1d0<<<m be the output after m left-cyclic shift operation, where “<<<” is a notation for a left-cyclic shift. We have(6)qSi,1=dL−1dL−2⋯d1d0<<<1=dL−2dL−3⋯d0dL−1=dL−1dL−2⋯d1d00mod2L−1.To eachdL−1dL−2⋯d1d0, associate the polynomial as follows:(7)fdx=dL−1xL−1+dL−2xL−2+⋯+d1x1+d0x0.Notice that(8)xfdx=dL−1xL+dL−2xL−1+⋯+d1x2+d0x1=dL−2xL−1+⋯+d1x2+d0x1+dL−1x0.Consequently, multiplyingfdx by xm corresponds to a cyclic shift through m positions to the right. So, the qSi,1 can be computed according to equation (8).


#### 4.1.4. Part 4: Combination Module

Part 4 is a combination module to combine the outputS¯i of the part 3. The input of part 3 is k L-bit binary series and the output of part 4 should also be L-bit binary series. The equation of part 4 can be written as follows:(9)G=∑i=0k−1qiS¯imod2L−1.In equation (7), Si¯ is the L-bit binary series, k is the number of the shift register, and mod2L−1 is used to generate the L-bit binary series for part 1 to do the next iteration.


## 4.1. Structures of CMFSR

There are four parts in the structure of the CMFSR which is shown in Figure6. Part 1 is a logistic map system with special precision. Part 2 is a feedback shift register with L shift unit. Part 3 is a control unit to control the operation of the value of the shift register. Part 4 is a combination module to combine the output from part 3.Figure 6
Structure of the CMFSR.


### 4.1.1. Part 1: Chaotic Map

Part 1 is a discrete chaotic map withL-bit precision. The parameter of the system is μ, the input of chaotic map is the L-bit binary from part 4, and the output of part 1 is also L-bit binary as the input of the shift register.Mathematically, the proposed part 1 with the logistic map inL-bit precision can be defined as equation (5). The value range of control parameter μ is [3.5699456, 4], then the logistic map runs into a chaotic state. The closer the parameter reaches 4, the higher the Lyapunov exponent is and the better the chaotic property is.As for the tent map [29], the tent map works in the chaotic state with the control parameter in the range of 1<μ<2.


### 4.1.2. Part 2: Feedback Shift Register

Part 2 is a feedback shift register (FSR) withk units and each unit has L-bit registers which can increase the linear complexities of the output sequence. The input of FSR is Sk which is an L-bit binary, and the output of the logistic map. And an L-bit binary from S0 is the output of Part 2 and it is also the output of the system. The value of the shift registers shifts from right to left in an order which can be written as follows: Si−1=Si. And the shift registers move when the output of Part 1 is generated.


### 4.1.3. Part 3: Control Module

Part 3 is a control module to control the movement of theL-bit binary series. A control module can decide whether the series is passed to part 4 and how to change a L-bit binary series to get the high performance. Si will transform to S¯i according to the value of the control module parameter qi. Then, Si¯=qSi,m∈GF2L. Here, parameter m means left-cyclic shift m bits.Letdi=0,1∈GF2, then Si is the set of all binary sequence of length L.S
i
=
0,1
n
=
d
L
−
1
d
L
−
2
⋯
d
1
d
0. There are L bits binary sequence and di is one of them.LetqSi,1=dL−1dL−2⋯d1d0<<<m be the output after m left-cyclic shift operation, where “<<<” is a notation for a left-cyclic shift. We have(6)qSi,1=dL−1dL−2⋯d1d0<<<1=dL−2dL−3⋯d0dL−1=dL−1dL−2⋯d1d00mod2L−1.To eachdL−1dL−2⋯d1d0, associate the polynomial as follows:(7)fdx=dL−1xL−1+dL−2xL−2+⋯+d1x1+d0x0.Notice that(8)xfdx=dL−1xL+dL−2xL−1+⋯+d1x2+d0x1=dL−2xL−1+⋯+d1x2+d0x1+dL−1x0.Consequently, multiplyingfdx by xm corresponds to a cyclic shift through m positions to the right. So, the qSi,1 can be computed according to equation (8).


### 4.1.4. Part 4: Combination Module

Part 4 is a combination module to combine the outputS¯i of the part 3. The input of part 3 is k L-bit binary series and the output of part 4 should also be L-bit binary series. The equation of part 4 can be written as follows:(9)G=∑i=0k−1qiS¯imod2L−1.In equation (7), Si¯ is the L-bit binary series, k is the number of the shift register, and mod2L−1 is used to generate the L-bit binary series for part 1 to do the next iteration.


## 4.1.1. Part 1: Chaotic Map

Part 1 is a discrete chaotic map withL-bit precision. The parameter of the system is μ, the input of chaotic map is the L-bit binary from part 4, and the output of part 1 is also L-bit binary as the input of the shift register.Mathematically, the proposed part 1 with the logistic map inL-bit precision can be defined as equation (5). The value range of control parameter μ is [3.5699456, 4], then the logistic map runs into a chaotic state. The closer the parameter reaches 4, the higher the Lyapunov exponent is and the better the chaotic property is.As for the tent map [29], the tent map works in the chaotic state with the control parameter in the range of 1<μ<2.


## 4.1.2. Part 2: Feedback Shift Register

Part 2 is a feedback shift register (FSR) withk units and each unit has L-bit registers which can increase the linear complexities of the output sequence. The input of FSR is Sk which is an L-bit binary, and the output of the logistic map. And an L-bit binary from S0 is the output of Part 2 and it is also the output of the system. The value of the shift registers shifts from right to left in an order which can be written as follows: Si−1=Si. And the shift registers move when the output of Part 1 is generated.


## 4.1.3. Part 3: Control Module

Part 3 is a control module to control the movement of theL-bit binary series. A control module can decide whether the series is passed to part 4 and how to change a L-bit binary series to get the high performance. Si will transform to S¯i according to the value of the control module parameter qi. Then, Si¯=qSi,m∈GF2L. Here, parameter m means left-cyclic shift m bits.Letdi=0,1∈GF2, then Si is the set of all binary sequence of length L.S
i
=
0,1
n
=
d
L
−
1
d
L
−
2
⋯
d
1
d
0. There are L bits binary sequence and di is one of them.LetqSi,1=dL−1dL−2⋯d1d0<<<m be the output after m left-cyclic shift operation, where “<<<” is a notation for a left-cyclic shift. We have(6)qSi,1=dL−1dL−2⋯d1d0<<<1=dL−2dL−3⋯d0dL−1=dL−1dL−2⋯d1d00mod2L−1.To eachdL−1dL−2⋯d1d0, associate the polynomial as follows:(7)fdx=dL−1xL−1+dL−2xL−2+⋯+d1x1+d0x0.Notice that(8)xfdx=dL−1xL+dL−2xL−1+⋯+d1x2+d0x1=dL−2xL−1+⋯+d1x2+d0x1+dL−1x0.Consequently, multiplyingfdx by xm corresponds to a cyclic shift through m positions to the right. So, the qSi,1 can be computed according to equation (8).


## 4.1.4. Part 4: Combination Module

Part 4 is a combination module to combine the outputS¯i of the part 3. The input of part 3 is k L-bit binary series and the output of part 4 should also be L-bit binary series. The equation of part 4 can be written as follows:(9)G=∑i=0k−1qiS¯imod2L−1.In equation (7), Si¯ is the L-bit binary series, k is the number of the shift register, and mod2L−1 is used to generate the L-bit binary series for part 1 to do the next iteration.


## 5. Performance Analysis

CMFSR is a pseudorandom number generator with the chaotic map and feedback register. First, the architecture of the CMFSR influences the performance of output sequence. Moreover, we use two architecture: logistic map with feedback shift register (LMFSR) and tent map with feedback shift register (TMFSR) and evaluate the performance of them. Second, the precision of the CMFSR can also decide the performance of the randomness and period of the sequence.To evaluate the performance of CMFSR architecture, we give several types of architecture to evaluate the influence of arch and decide what kind of architecture is best and analysis the reason. Logistic map with a feedback shift register (LMFSR) is used to evaluate the performance of the proposed method. The output of part 1 is as the input of the part 2. The amount of the shift registers or the operation in part 2 can influence the period, autocorrelation, and NIST performance.


### 5.1. Architecture of the Control Module

Some typical kinds of architecture in part 3 are shown in Table1. Let C denote the cyclic left shift operation of a sequence, which is defined by(10)C=S¯K−1,S¯K−2,…,S¯1,S¯0=qSK−1,mK−1,qSK−2,mK−1,…,qS1,m1,qS0,m0.Table 1
NIST result of LMFSR and CMFSR.
Type
LMFSR
CMFSR
Statistical test
p value
p value
Result
monobit_test
0.119002817
0.632865
PASS
Frequency
0.259390983
0.116785
PASS
runs_test
0.410376776
0.189808
PASS
longest_run
0.297010623
0.440344
PASS
Rank
0.222882463
0.910297
PASS
dft
0.699403654
0.191548
PASS
Nonoverlapping
0.99662573
0.999016
PASS
Overlapping
0.62520135
0.032062
PASS
Universal
0.489567646
0.414955
PASS
linear_complexity
0.360578591
0.552776
PASS
Serial
0.620509854
0.417542
PASS
Entropy
0.620341329
0.590568
PASS
cumulative_sums
0.104510369
0.746711
PASS
random_excursion
0.251021134
0.118151
PASS
random_excursion_variant_test
0.193716652
0.226293
PASSLetqSi,mi=n∈−1,0,…,L−1, where n means a cyclic shift left for n positions maps the bit string SL−1 into S¯L−1. If qSi,mi=−1, that means that S¯i=0 no matter what Si is. In Table 1, X means disconnected and Code represents the combination state of each control module which is used to describe the operation of the shift register. For example, if we let Code = 0x123, then m4=0,m3=X,m2=1,m1=2,andm0=3.


### 5.2. Analysis of the Experiment

The result of the exams in Figure7 shows the hist of the result with a different initial value. Figure 7(a) is the hist of LMFSR with the random initial value, and Figure 7(b) is the other hist of LMFSR with the initial value generated by the iteration of the logistic map.Figure 7
Hist of LMFSR period: (a) with special initial value of the LMFSR with 4 feedback shift registers, (b) with random initial value of the LMFSR with 4 feedback shift register, and (c) with 5 feedback shift register.
(a)
(b)
(c)Two shapes of the hist show that(1)
The period of LMFSR has no relation with an initial value(2)
The different outputs of LMFSR are uncorrelatedThe maximum period of all these experiments is 65500 when codeC = 0203. The whole length of feedback shift register is 16 bits, so the maximum length of the sequence should be 216=65536.Another test about LMFSR with 5 feedback shift register is performed, and the distribution about the period is shown in Figure7(c) the maximum length of the sequence should be 220=1048576. The result of the LMFSR with 5 feedback shift register in Figure 7(c) shows that the maximum of the LMFSR is 1048486 with C = 1x220. It shows that the maximum of the LMFSR is close to the maximum of the n-bit feedback shift register.Distribution of the value LMFSR generates is shown in Figure8, where C = 0203. The horizontal axis of the scatter number is the value which the logistic map gets with 8-bit precision, and the vertical axis denotes the amount of the special value. The bar with different colors denotes the initial value of the logistic map. Figure 8 means no matter what the initial value is, the difference of the value distribution is almost within 0.5% which is accepted.Figure 8
Distribution of 8-bit LMFSR with the different initial values.


### 5.3. Entropy

In a stream cypher, the key is usually used to set the initial state of an automaton. Then, the automaton is used to make sure that the results from different initialization keys are diffused. Entropy is an important parameter to measure the randomness of the signal samples and is given by(11)H=−∑i=1nPxilog2Pxi.For a truly random source consists ofn symbols, the Pxi is the probability of the sample value xi. Entropy will reach maximum value when pxi=1/n. If precision of LMFSR is 8-bit, n=28, then H=log2n=8. Figure 9 is a chart about the entropy of LMFSR with a different initial value. The bar with different colors means the different initial values from 1 to 8. And the amount of iteration is shown on x-axis. From Figure 9(a) we can see that with the increase of the iteration, the entropy of LMFSR increases simultaneously. After 10000 iterations, entropy is almost 8 for different initial value.Figure 9
Entropy of CMFSR with different initial values. (a) Entropy of LMFSR with 8-bit precision. (b) Entropy of CMFSR with 8-bit precision.
(a)
(b)


### 5.4. PRNG Based on CMFSR

The complexity of the chaotic system and random number generator can be measured by using various approaches. In this section, we use the Lyapunov exponent, autocorrelation, and correlation to measure the modified chaotic system with the feedback shift register.In order to improve the complexity of the chaotic system, we setK=24 and L=25−1. So, there are 16 stages of 31-bit words in part 2 according to Figure 5, which is defined over GFp=GF231−1. Zero stage and one stage in part 1 are not allowed in the stage because they will lead the logistic map to a fixed point. Both of them will be replaced by 230−1. A primitive feedback polynomial fx=x16−215x15+217x13+221x10+220x4+28+1 is used. According to primitive polynomial, stage 15, 13, 10, 4, and 0 are used in part 3. And the parameter mi∈0,25−1 in qSi,mi is modified after the perturbation of the chaotic system. For each mi∈0,25−1, let m0=Sk4:0, m4=Sk9:5, m10=Sk14:10, m13=Sk19:15, and m15=Sk24:20.The precision of the chaotic map is 31-bits. Logistic map and tent map are both used to evaluate the performance of the proposed system.


#### 5.4.1. Keyspace Analysis

The keyspace should be large enough to resist force attacks infeasible. For the CMFSR, the initial value of the chaotic map isL-bit binary and k×L-bit binary for the feedback shift register. So, the keyspace of LMFSR is 2L+K∗L. For instance, when calculation precision L=31 and 31 × 16 shift registers, then keyspace is 2527 which is much larger than the chaotic pseudorandom-number generator.


#### 5.4.2. Autocorrelation Analysis

Autocorrelation test is used to check if there is a correlation between the bits of given sequence and bits of a shift version of the same sequence. An autocorrelation algorithm can be used to detect the periodicity of the times series. It is defined as follows:(12)rzm=1N∑i=0NZn×Zn+m.where rz denotes the autocorrelation function and N is the amount of the values in the discrete chaotic sequence. According to the above theoretical basis, the autocorrelation test is down for a different logistic map with a different precision. Figure 10 shows the autocorrelation of the sequence generated by LMFSR in Figure 10(a) and TMFSR in Figure 10(b). As can be seen from the figure, the smaller the precision of the logistic map is, the denser the line of the autocorrelation is.Figure 10
Autocorrelation of CMFSR. (a) Autocorrelation of LMFSR. (b) Autocorrelation of TMFSR.
(a)
(b)


#### 5.4.3. NIST Test

To evaluate the randomness of LMFSR, we use NIST test suit [30] that was designed specifically with cryptographic operation in mind. And the version of NIST we used is STS 2.1.2. The test suite consists of 15 test such as frequency test, run test, cumulative sums test, various variations on templates test, entropy test, serial test, or discrete Fourier transform test. These tests are developed to test the randomness of binary sequence produced by either hardware or software based on cryptographic random or pseudorandom number generators.According to the NIST STS documentation, the sequences are considered to be uniformly distributed ifpvalue≥0.0001. Based on result of the CMFSR shown in Table 1, not only LMFSR but also TMFSR, the proposed architecture of the chaotic map with the feedback shift register improves the complexity of the chaotic map with finite precision. We conclude that the proposed CMFSR generates the random binary sequences suitable for cryptographic applications.


#### 5.4.4. Testu01 Test

TestU01 is used for testing. It is a software library which provides a collection of utilities to test the random number generator. And it can offer several batteries of the test. There are multiple tests for different performance aspects. Both the Small-Crush battery and the Crush battery are applied to check the randomness of the proposed CMFSR, where sequence with224 bits of numbers and 230 bit of numbers are generated, respectively, for LMFSR and TMFSR. If 0.0001≤pvalue≤0.9999, the associated test is a success. Any pvalue lying outside this range is considered as failure. Table 2 depicts the failure counts of tests in TestU01, which contain the comparisons with other PRNGs for classical logistic map, Addabbo’s system, and Li’s system. The result shows that the proposed CMFSR pass almost all the tests in Small-Crush and Crush batteries.Table 2
Success comparison of TestU01 results of CMFSR.
System
SP800-22(15)
Small-Crush(15)
Crush(144)
LMFSR
15/15
14/15
133/144
TMFSR
15/15
14/15
134/144
Logistic map
6/15
0/15
4/144
VPCMDP [17]
15/15
12/15
129/144
Li et al.’s [31]
14/15
0/15
0/144
Addabbo et al.’s [32]
13/15
1/15
22/144


## 5.1. Architecture of the Control Module

Some typical kinds of architecture in part 3 are shown in Table1. Let C denote the cyclic left shift operation of a sequence, which is defined by(10)C=S¯K−1,S¯K−2,…,S¯1,S¯0=qSK−1,mK−1,qSK−2,mK−1,…,qS1,m1,qS0,m0.Table 1
NIST result of LMFSR and CMFSR.
Type
LMFSR
CMFSR
Statistical test
p value
p value
Result
monobit_test
0.119002817
0.632865
PASS
Frequency
0.259390983
0.116785
PASS
runs_test
0.410376776
0.189808
PASS
longest_run
0.297010623
0.440344
PASS
Rank
0.222882463
0.910297
PASS
dft
0.699403654
0.191548
PASS
Nonoverlapping
0.99662573
0.999016
PASS
Overlapping
0.62520135
0.032062
PASS
Universal
0.489567646
0.414955
PASS
linear_complexity
0.360578591
0.552776
PASS
Serial
0.620509854
0.417542
PASS
Entropy
0.620341329
0.590568
PASS
cumulative_sums
0.104510369
0.746711
PASS
random_excursion
0.251021134
0.118151
PASS
random_excursion_variant_test
0.193716652
0.226293
PASSLetqSi,mi=n∈−1,0,…,L−1, where n means a cyclic shift left for n positions maps the bit string SL−1 into S¯L−1. If qSi,mi=−1, that means that S¯i=0 no matter what Si is. In Table 1, X means disconnected and Code represents the combination state of each control module which is used to describe the operation of the shift register. For example, if we let Code = 0x123, then m4=0,m3=X,m2=1,m1=2,andm0=3.


## 5.2. Analysis of the Experiment

The result of the exams in Figure7 shows the hist of the result with a different initial value. Figure 7(a) is the hist of LMFSR with the random initial value, and Figure 7(b) is the other hist of LMFSR with the initial value generated by the iteration of the logistic map.Figure 7
Hist of LMFSR period: (a) with special initial value of the LMFSR with 4 feedback shift registers, (b) with random initial value of the LMFSR with 4 feedback shift register, and (c) with 5 feedback shift register.
(a)
(b)
(c)Two shapes of the hist show that(1)
The period of LMFSR has no relation with an initial value(2)
The different outputs of LMFSR are uncorrelatedThe maximum period of all these experiments is 65500 when codeC = 0203. The whole length of feedback shift register is 16 bits, so the maximum length of the sequence should be 216=65536.Another test about LMFSR with 5 feedback shift register is performed, and the distribution about the period is shown in Figure7(c) the maximum length of the sequence should be 220=1048576. The result of the LMFSR with 5 feedback shift register in Figure 7(c) shows that the maximum of the LMFSR is 1048486 with C = 1x220. It shows that the maximum of the LMFSR is close to the maximum of the n-bit feedback shift register.Distribution of the value LMFSR generates is shown in Figure8, where C = 0203. The horizontal axis of the scatter number is the value which the logistic map gets with 8-bit precision, and the vertical axis denotes the amount of the special value. The bar with different colors denotes the initial value of the logistic map. Figure 8 means no matter what the initial value is, the difference of the value distribution is almost within 0.5% which is accepted.Figure 8
Distribution of 8-bit LMFSR with the different initial values.


## 5.3. Entropy

In a stream cypher, the key is usually used to set the initial state of an automaton. Then, the automaton is used to make sure that the results from different initialization keys are diffused. Entropy is an important parameter to measure the randomness of the signal samples and is given by(11)H=−∑i=1nPxilog2Pxi.For a truly random source consists ofn symbols, the Pxi is the probability of the sample value xi. Entropy will reach maximum value when pxi=1/n. If precision of LMFSR is 8-bit, n=28, then H=log2n=8. Figure 9 is a chart about the entropy of LMFSR with a different initial value. The bar with different colors means the different initial values from 1 to 8. And the amount of iteration is shown on x-axis. From Figure 9(a) we can see that with the increase of the iteration, the entropy of LMFSR increases simultaneously. After 10000 iterations, entropy is almost 8 for different initial value.Figure 9
Entropy of CMFSR with different initial values. (a) Entropy of LMFSR with 8-bit precision. (b) Entropy of CMFSR with 8-bit precision.
(a)
(b)


## 5.4. PRNG Based on CMFSR

The complexity of the chaotic system and random number generator can be measured by using various approaches. In this section, we use the Lyapunov exponent, autocorrelation, and correlation to measure the modified chaotic system with the feedback shift register.In order to improve the complexity of the chaotic system, we setK=24 and L=25−1. So, there are 16 stages of 31-bit words in part 2 according to Figure 5, which is defined over GFp=GF231−1. Zero stage and one stage in part 1 are not allowed in the stage because they will lead the logistic map to a fixed point. Both of them will be replaced by 230−1. A primitive feedback polynomial fx=x16−215x15+217x13+221x10+220x4+28+1 is used. According to primitive polynomial, stage 15, 13, 10, 4, and 0 are used in part 3. And the parameter mi∈0,25−1 in qSi,mi is modified after the perturbation of the chaotic system. For each mi∈0,25−1, let m0=Sk4:0, m4=Sk9:5, m10=Sk14:10, m13=Sk19:15, and m15=Sk24:20.The precision of the chaotic map is 31-bits. Logistic map and tent map are both used to evaluate the performance of the proposed system.


### 5.4.1. Keyspace Analysis

The keyspace should be large enough to resist force attacks infeasible. For the CMFSR, the initial value of the chaotic map isL-bit binary and k×L-bit binary for the feedback shift register. So, the keyspace of LMFSR is 2L+K∗L. For instance, when calculation precision L=31 and 31 × 16 shift registers, then keyspace is 2527 which is much larger than the chaotic pseudorandom-number generator.


### 5.4.2. Autocorrelation Analysis

Autocorrelation test is used to check if there is a correlation between the bits of given sequence and bits of a shift version of the same sequence. An autocorrelation algorithm can be used to detect the periodicity of the times series. It is defined as follows:(12)rzm=1N∑i=0NZn×Zn+m.where rz denotes the autocorrelation function and N is the amount of the values in the discrete chaotic sequence. According to the above theoretical basis, the autocorrelation test is down for a different logistic map with a different precision. Figure 10 shows the autocorrelation of the sequence generated by LMFSR in Figure 10(a) and TMFSR in Figure 10(b). As can be seen from the figure, the smaller the precision of the logistic map is, the denser the line of the autocorrelation is.Figure 10
Autocorrelation of CMFSR. (a) Autocorrelation of LMFSR. (b) Autocorrelation of TMFSR.
(a)
(b)


### 5.4.3. NIST Test

To evaluate the randomness of LMFSR, we use NIST test suit [30] that was designed specifically with cryptographic operation in mind. And the version of NIST we used is STS 2.1.2. The test suite consists of 15 test such as frequency test, run test, cumulative sums test, various variations on templates test, entropy test, serial test, or discrete Fourier transform test. These tests are developed to test the randomness of binary sequence produced by either hardware or software based on cryptographic random or pseudorandom number generators.According to the NIST STS documentation, the sequences are considered to be uniformly distributed ifpvalue≥0.0001. Based on result of the CMFSR shown in Table 1, not only LMFSR but also TMFSR, the proposed architecture of the chaotic map with the feedback shift register improves the complexity of the chaotic map with finite precision. We conclude that the proposed CMFSR generates the random binary sequences suitable for cryptographic applications.


### 5.4.4. Testu01 Test

TestU01 is used for testing. It is a software library which provides a collection of utilities to test the random number generator. And it can offer several batteries of the test. There are multiple tests for different performance aspects. Both the Small-Crush battery and the Crush battery are applied to check the randomness of the proposed CMFSR, where sequence with224 bits of numbers and 230 bit of numbers are generated, respectively, for LMFSR and TMFSR. If 0.0001≤pvalue≤0.9999, the associated test is a success. Any pvalue lying outside this range is considered as failure. Table 2 depicts the failure counts of tests in TestU01, which contain the comparisons with other PRNGs for classical logistic map, Addabbo’s system, and Li’s system. The result shows that the proposed CMFSR pass almost all the tests in Small-Crush and Crush batteries.Table 2
Success comparison of TestU01 results of CMFSR.
System
SP800-22(15)
Small-Crush(15)
Crush(144)
LMFSR
15/15
14/15
133/144
TMFSR
15/15
14/15
134/144
Logistic map
6/15
0/15
4/144
VPCMDP [17]
15/15
12/15
129/144
Li et al.’s [31]
14/15
0/15
0/144
Addabbo et al.’s [32]
13/15
1/15
22/144


## 5.4.1. Keyspace Analysis

The keyspace should be large enough to resist force attacks infeasible. For the CMFSR, the initial value of the chaotic map isL-bit binary and k×L-bit binary for the feedback shift register. So, the keyspace of LMFSR is 2L+K∗L. For instance, when calculation precision L=31 and 31 × 16 shift registers, then keyspace is 2527 which is much larger than the chaotic pseudorandom-number generator.


## 5.4.2. Autocorrelation Analysis

Autocorrelation test is used to check if there is a correlation between the bits of given sequence and bits of a shift version of the same sequence. An autocorrelation algorithm can be used to detect the periodicity of the times series. It is defined as follows:(12)rzm=1N∑i=0NZn×Zn+m.where rz denotes the autocorrelation function and N is the amount of the values in the discrete chaotic sequence. According to the above theoretical basis, the autocorrelation test is down for a different logistic map with a different precision. Figure 10 shows the autocorrelation of the sequence generated by LMFSR in Figure 10(a) and TMFSR in Figure 10(b). As can be seen from the figure, the smaller the precision of the logistic map is, the denser the line of the autocorrelation is.Figure 10
Autocorrelation of CMFSR. (a) Autocorrelation of LMFSR. (b) Autocorrelation of TMFSR.
(a)
(b)


## 5.4.3. NIST Test

To evaluate the randomness of LMFSR, we use NIST test suit [30] that was designed specifically with cryptographic operation in mind. And the version of NIST we used is STS 2.1.2. The test suite consists of 15 test such as frequency test, run test, cumulative sums test, various variations on templates test, entropy test, serial test, or discrete Fourier transform test. These tests are developed to test the randomness of binary sequence produced by either hardware or software based on cryptographic random or pseudorandom number generators.According to the NIST STS documentation, the sequences are considered to be uniformly distributed ifpvalue≥0.0001. Based on result of the CMFSR shown in Table 1, not only LMFSR but also TMFSR, the proposed architecture of the chaotic map with the feedback shift register improves the complexity of the chaotic map with finite precision. We conclude that the proposed CMFSR generates the random binary sequences suitable for cryptographic applications.


## 5.4.4. Testu01 Test

TestU01 is used for testing. It is a software library which provides a collection of utilities to test the random number generator. And it can offer several batteries of the test. There are multiple tests for different performance aspects. Both the Small-Crush battery and the Crush battery are applied to check the randomness of the proposed CMFSR, where sequence with224 bits of numbers and 230 bit of numbers are generated, respectively, for LMFSR and TMFSR. If 0.0001≤pvalue≤0.9999, the associated test is a success. Any pvalue lying outside this range is considered as failure. Table 2 depicts the failure counts of tests in TestU01, which contain the comparisons with other PRNGs for classical logistic map, Addabbo’s system, and Li’s system. The result shows that the proposed CMFSR pass almost all the tests in Small-Crush and Crush batteries.Table 2
Success comparison of TestU01 results of CMFSR.
System
SP800-22(15)
Small-Crush(15)
Crush(144)
LMFSR
15/15
14/15
133/144
TMFSR
15/15
14/15
134/144
Logistic map
6/15
0/15
4/144
VPCMDP [17]
15/15
12/15
129/144
Li et al.’s [31]
14/15
0/15
0/144
Addabbo et al.’s [32]
13/15
1/15
22/144


## 6. Conclusion

This paper presents the chaotic map with a feedback shift register. More precise results concerning the general behaviour of CMFSR are given and analyzed. Our main result concerns the relationship between the period and precision of CMFSR. Logistic map or tent map is a nonlinear module that works in a chaotic state. A feedback shift register is used to extend the periodicity of the finite precision logistic map. And the output of the feedback shift register is reorganized and moulded by the maximum number in a given precision. From the results proved here, we can get almost the maximum period which the feedback shift register can get. Because of the low hardware and software resource consumption, the feedback shift register is suitable to extend periodicity of the logistic map with finite precision. A well-designed CMFSR with the same precision compared to the logistic map has better performance. The proposed corresponding pseudorandom number generator is constructed and its randomness is evaluated via NIST SP800-22 and TestU01 test. The statistical results show that the proposed CMFSR has high reliability of randomness.



---

*Source: 4676578-2020-01-21.xml*