# Theorem to Generate Independently and Uniformly Distributed Chaotic Key Stream via Topologically Conjugated Maps of Tent Map

Authors: Zheng guang Xu; Qing Tian; Li Tian
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

This paper proposes a theorem to generate chaotic key stream from topologically conjugated maps of Tent Map. In this theorem, the condition for topological conjugation between Tent Map and a class of chaotic maps is first determined. Then, the chaotic attractor of the maps is divided into2n unequal subintervals, the chaotic orbit is sampled once in n time iteration, and, finally, the independently and uniformly distributed 2n phase key stream is obtained. The theoretical and numerical analyses show that the chaotic key stream generated by the proposed theorem successfully is independent and uniform, has a certain complex degree close to the maximum approximate entropy for 2n phase key stream, and satisfies the randomness requirement defined in NIST SP800-22. This theorem can be used in fields such as cryptography and numerical simulation.


---

## Body

## 1. Introduction

Random number generation is very important in cryptography, especially in key construction. In symmetric and asymmetric cryptosystems, the random number is the primary resource for key generation. Further, random number generators (RNGs) are used to create challenges, nonce, padding bytes, and blinding values in many cryptographic protocols.There are two basic types of generators that produce random sequences: true random number generators (TRNGs) [1] and pseudorandom number generators (PRNGs) [2–5]. PRNGs are generally faster than TRNGs, and, therefore, PRNGs are preferable in applications requiring a large number of random numbers.Chaotic system, characterized by sensitive dependence on initial conditions, similarity to random behavior, continuous broad-band power spectrum, inherent determinism, and simplicity of realization, can be potentially exploited for PRNGs [6, 7]. Most applications of chaotic maps use a one- or multidimensional chaotic map as a PRNG to produce a binary stream, which is then XORed with the plaintext to produce the cipher-text [8–11]. Thus, the statistical property—independently and identically distributed (IID)—of chaotic key stream plays an important role in avoiding cipher-text attacking.Tent Map is described by the uniform probability law, and, hence, the statistical independence of successive binary symbols is the main problem to be addressed. Some studies focus on experiments that determine the selection of a suitable Tent Map parameter for different applications where the statistical independence is of interest. The relationship between the Tent Map parameter and the statistical independence decision is indicated in [12]. Complying with the fair coin tossing model in [13], the threshold is given according to the Tent Map parameter to obtain a statistically independent key stream. Other studies have focused on theoretical proofs. Logistic Map is topologically conjugated with Tent Map [14], and, therefore, Hu et al. proposed a method for generating chaotic key stream based on Logistic Map [15]. This key stream is proved to be independent and uniform. AdrianLuca and Vlad provided another method for generating IID samples using Logistic Map by combining discrete noisy channel with the test of independence in contingency tables [16]. Until now, the research for generating IID key stream by topological conjugation has been limited to Logistic Map. However, in our study, we determine a more general condition, under which a class of chaotic systems can produce the IID key stream. Meanwhile, the proof in [14] can be considered as the example for the theorem proposed in this paper.


## 2. Theorem for Generation of IID Key Streams

In this section, we specify the conditions and process required for a class of topologically conjugated mapping systems of Tent Map to generate the IID key stream.Definition 2.1 (see [17]).
For two one-dimensional maps,we have(2.1)xk+1=g(xk),x∈I⊂R,yk+1=g(yk),x∈J⊂R.
If there exists a continuous and invertible map h:I→J, such that yk=h(xk), making h-1∘f∘h(xk)=g(xk) and h∘g∘h-1(yk)=f(yk), then f and g are said to be topologically conjugated via h.Lemma 2.2 (see [17]).
Iff and g are topologically conjugated via h, then fn and gn are topologically conjugated via h.Lemma 2.3 (see [17]).
Iff and g are topologically conjugated via h, and ρg is the probability density function of g, then the probability density function of  f is
(2.2)ρf(x)=ρg(h-1(x))|dh-1(x)dx|.Theorem 2.4.
For tent map, we have(2.3)xk+1=g(xk)={2xk,0≤xk≤122-2xk,12≤xk≤1
when ma=-4, and m,a∈R,
(2.4)f(xk)=mxk2+4xk,xk∈[min{0,a},max{0,a}],
and g(xk) are topologically conjugated via
(2.5)h(xk)=asin2πxk2,a≠0.
For the mapf(xk)=mxk2+4xk defined by (2.4), we choose n as sampling step, that is, xk+1=fn(xk), and can generate an independent uniformly distributed chaotic key stream {si}0∞ by the following process.(1)
Ifa>0, the chaotic attractor domain [0,a] is partitioned into N=2n subdomains τi=[ti,ti+1), where ti=h(i/N),i=0,1,…,N-1.(2)
Ifa<0, the chaotic attractor domain [a,0] is partitioned into N=2n subdomains τi=[ti,ti+1), where ti=h((N-i)/N),i=0,1,…,N-1.(3)
Then, chaotic key stream{si}0∞ is defined as:
ifxk∈τi, then sk=i.Proof.
(1)f(x)Is Surjective
Whenma=-4,f(xk)=mxk2+4xk=(-4/a)xk2+4xk. Ifa>0, it can be concluded that when xk∈[0,a],f(xk)∈[0,a].Ifa<0, it can be concluded that when xk∈[a,0],f(xk)∈[a,0].
Thus,f(x) is surjective in its definition domain [min{0,a},max{0,a}].
(2)Property of Topological Conjugation
Iff and g are topologically conjugated via h, then, according to Definition 2.1,
(2.6)h-1∘f∘h(xk)=g(xk),thatis,f∘h(xk)=h∘g(xk).
For Tent Map (2.3) and transformer (2.5),
(2.7)h∘g(xk)={asin2π2xk2=asin2πxk,0≤xk≤12asin2π(2-2xk)2=asin2(π-πxk)=asin2πxk,12≤xk≤1=asin2πxk,0≤x≤1=h(2xk).
When ma=-4, for map (2.4),
(2.8)f(xk)=-4axk2+4xk=4axk(a-xk).
Hence,
(2.9)f∘h(xk)=4a·asin2πxk2(a-asin2πxk2)=4asin2πxk2·cos2πxk2=a(2sinπxk2·cosπxk2)2=asin2πxk.
Thus, f∘h(xk)=h∘g(xk).
Hence,f and g are topologically conjugated via h.
(3)f(xk)Is Chaotic
To assure the key stream{si}0∞ produced by f(xk) is chaotic pseudorandom number with the potential characters proposed in paragraph 3 in Section 1, we prove the f(xk) is chaotic now.
As the reference [18–20] proposed, the Lyapunov exponents of corresponding orbits of two conjugated interval maps are the same. According to the computing method of Lyapunov exponent
(2.10)λ(g,x)=limn→∞1n∑i=1nln|g′(xi)|,
if λ(g,x) is the Lyapunov exponent of the orbit of g through x,λ(f,y) is the Lyapunov exponent of the orbit of f through y=h(x), and f∘h(xk)=h∘g(xk) is the conjugation, then λ(g,x)=λ(f,y) [18]. And the largest λ(g,x) with respect to changes of  δx0 is independent of x0 [20].
More precisely, for the map (2.4) f(yk)=myk2+4yk established by Theorem 2.4, Tent Map defined by (2.3), and yk=h(xk)=asin2(πxk/2) defined by (2.5), we have f∘h(xk)=h∘g(xk), and f′(h(xk))·h′(xk)=h′(g(xk))·g′(xk), that is, f′(yk)·h′(xk)=h′(g(xk))·g′(xk), thus,
(2.11)|f′(yk)|=|h′(g(xk))h′(xk)|·|g′(xk)|=|(πa/2)sin(2πxk)(πa/2)sin(πxk)|·|g′(xk)|=|2cos(πxk)|·|g′(xk)|.
Also, for xk in Tent Map, we have cos(πxk)=cos(π2xk-1), then
(2.12)λ(f,y)=limn→∞1n∑i=1nln|f′(yi)|=limn→∞1n∑i=1nln(|2cos(πxk)|·|g′(xk)|)=limn→∞1n∑i=1nln(|2cos(πxk)|)+λ(g,x)=limn→∞1nln(|2cos(πx1)|·|2cos(πx2)|⋯|2cos(πxn)|)+λ(g,x)=limn→∞1nln(|sin(πx1)||2cos(πx1)|·|2cos(πx2)|⋯|2cos(πxn)||sin(πx1)|)+λ(g,x)=limn→∞1nln(|sin(πx1)||2cos(πx1)|·|2cos(π2x1)|⋯|2cos(π2nx1)||sin(πx1)|)+λ(g,x)=limn→∞1nln(|sin(π2x1)|·|2cos(π2x1)|⋯|2cos(π2nx1)||sin(πx1)|)+λ(g,x)=limn→∞1nln|sin(π2nx1)||sin(πx1)|+λ(g,x)=limn→∞1nln|sin(π2nx1)|-limn→∞1nln|sin(πx1)|+λ(g,x)≤limn→∞1nlnn-0+λ(g,x)=λ(g,x)=ln2.
Hence, the largest Lyapunov exponent off(x) is ln2, and the map (2.4) is a chaotic system.
(4)Chaotic Key Stream Is Uniformly Distributed
From Lemma2.3, the probability density function of f is
(2.13)ρf=ρg(h-1(x))|dh-1(x)dx|.
Therefore, the probability off in the domain [ti,ti+1) is
(2.14)∫titi+1dh-1(x)dxdx=∫h(i/N)h((i+1)/N)dh-1(x)=h-1(x)|∫h(i/N)h((i+1)/N)dh-1h(i/N)h((i+1)/N)=h-1(h(i+1N))-h-1(h(iN))=i+1N-iN=1N.
Thus, the value of chaos has the same probability in each domain, and, hence, chaotic key stream is uniformly distributed.
(5)skIs Independent ofsk+1(Property of Independence)
In this part, we will show that the value ofsk+1 depends on the subdomains τij=[tji,tj+1i),  j=0,1,…,N-1,  tji=h((1/N)(i+j/N)), where xk is uniformly distributed according to the proof (4), and is independent of the τi to which xk belongs.
For simplicity, we will only consider the conditiona>0. According to Definition 2.1, Lemma 2.2, and the sampling way xk+1=fn(xk), we get that, for  θ∈[0,1], xk=h(θ)=asin2(πθ/2) is increasing and has a one-to-one correspondence with θ, and xk∈τji⇔θ∈[(1/N)(i+j/N),(1/N)(i+(j+1)/N)), then xk+1=h(2nθ)=asin2(π2nθ/2)∈h([i+j/N,i+(j+1)/N)). For h is an even function with period 2, then
(2.15)xk+1∈h([i+jN,i+j+1N))={[h(jN),h(j+1N)],iiseven[h(N-j-1N),h(N-jN)],iisodd.
Thus,  whensk=i,
(2.16)sk+1={j,iisevenN-j-1,iisodd,
that is,sk+1 is independent of sk.
Considering (1) to (5), the theorem proposes a method to establish a class of topologically conjugated maps of Tent Map and can generate independently and uniformly distributed chaotic key stream.


## 3. Examples of the Theorem2.4

This section consists of the illustration of the deduction in [14], which is an example of the proposed theorem. To illustrate the effectiveness and feasibility of the proposed theorem, another example is provided to verify the chaotic property, independently and uniformly distributed property, and  randomness of key streams. Due to the differences between theoretical values and calculated ones of a chaotic Logistic Map proposed in [21], all the examples are run with MATLAB (R2011a, v7.12) codes on the Window XP (32-bit) or Win7 (32-bit), and all the results are rounded into 4 digits after the decimal point.Example 3.1.
In Theorem2.4, when a=1,  m=-4,
(3.1)f(xk)=-4xk2+4xk=4xk(1-xk).
This map is the typical Logistic Mapf(x)=ux(1-x), when u=4. It is used in [14] for the generation of key stream. According to Theorem 2.4, when m=-4, the h(x)=sin2(πxk/2), then the proof of Deduction 1 in [14] can be considered as an example of the theorem proposed in this paper.Example 3.2.
In Theorem2.4, we choose a=8,m=-1/2,  and another chaotic map is obtained as follows:
(3.2)f(xk)=-12xk2+4xk,
and the transformer is
(3.3)h(xk)=8sin2πxk2.
We choose n=8 and divide the domain [0,a]=[0,8] into 2n=256 intervals, each intervals' beginning pot and ending pot is shown in Figure 1. Not similar to the Tent Map, the partition of the attractor domain for i.i.d key stream generation is symmetric and is not uniform equal.Figure 1
Partition of the attractor domain.(1)Chaotic Property of Map (3.2)For map (3.2), we set the initial condition x0=0.2323, and the results of 1,000 iterations are shown in Figure 2. It is observed that the values are nonperiodic and are distributed in almost the entire domain.Figure 2
1,000 iterations of map (3.2).(2)Independently and Uniformly Distributed Property of{si}0∞(a)  χ2Test[22]For the chaotic map (3.2) established by Theorem 2.4, we choose x0=0.2323 and sampling step n=8. After first 5,000 iteration abandoned, we get the 8-phase key stream {si}0M, where M is the lengths of sequence.We set significance levelα=0.05, then for M more than 100000, we get the same threshold χα2(M)=293.2478, and the results of χ2 test are shown in Table 1, where all the results pass the test successfully.Table 1
Results of uniform distribution of key stream{si}0M by map (3.2).
x
0
M
Threshold
χ
2
Result
100,000
293.2478
281.9430
Pass
200,000
293.2478
232.4326
Pass
0.2323
300,000
293.2478
239.8327
Pass
400,000
293.2478
246.4038
Pass
500,000
293.2478
246.6816
PassThen we choose 100 randomx0 and set M as 20,000 to do χ2 test. From the results in Figure 3, it can be observed that most of the tests passed and only 3 tests did not pass. As indicated in [12], the choice of initial value has an important impact on the statistical property of the chaotic system. Therefore, we can conclude that the key stream generated from Theorem 2.4 is uniformly distributed under the appropriate initial value.Figure 3
Result ofχ2 tests with 100 random number x1.(b) Approximate Entropy Analysis of
{
s
i
}
0
∞For the chaotic map (3.2) established by Theorem 2.4, we choose x0=0.2323 and sampling step n=8. After first 5,000 iteration abandoned, we get the 8-phase key stream {si}0M, where M is the lengths of sequence.According to the algorithm of approximate entropy in [23], we choose length of compared run lcr=2, filtering level r=0.25SD, where SD is the standard deviation of {si}0M. For different M, we compute the approximate entropy of {si}0M as shown in Table 2, where all the approximate entropies are close to the largest   approximate entropy ln8=2.0794 for 8-ary key stream, which is inferred in [24] and follows Theorem 2 in [23].Table 2
Approximate entropy analysis of{si}0M with different M.
lcr
r
x
0
M
Approximate entropy
3,000
2.0370
4,000
2.0291
5,000
2.0204
2
0.25 SD
0.2323
6,000
2.0108
7,000
2.0035
8,000
2.0009
9,000
1.9981Then we choose 100 randomx0 and set M as 6,000 with the same lcr=2 and r=0.25SD to compute the approximate entropy. From the results in Figure 4, it can be observed that the mean approximate entropy of {si}0M is close to the maximum approximate entropy ln8=2.0794 which shows that the sequence produced by Theorem 2.4 has a certain complex degree.Figure 4
Result of approximate entropy with 100 random numberx1.(3)Randomness Test of Key Streams{si}0∞In this part, we change{si}0∞ into binary sequences to carry out the test of NIST SP800-22 (April 2010), whose 15 tests depict the deviations of a binary sequence from randomness [25]. P value, as the probability against the null hypothesis, represents the degree of randomness of the tested sequence. When we choose significance level α=0.01, if the value is bigger than α=0.01, it demonstrates that the sequence passes the test and could be considered as random. And the bigger the value is, the more random the sequences are.First we use the chaotic map (3.2) established by Theorem 2.4 and choose x0=0.2323, sampling step n=8. After first 5,000 iteration abandoned, we get the 8-phase key stream {si}0M, where M is the lengths of sequence and M=125000. Then we test the binary sequences {bi}01000000, which is changed from 8-phase sequence {si}0M, with NIST SP800-22. The results are shown in Table 3, implying that the key streams produced by theorem can satisfy the random requirements in NIST SP800-22.Table 3
SP800-22 test’s results.
Test
P value
Results
Frequency (monobit) test
0.4156
Random
Frequency test within a block
0.7311
Random
Runs test
0.5957
Random
Test for the longest run of ones in a block
0.7238
Random
Binary matrix rank test
0.9087
Random
Discrete fourier transform test
0.4573
Random
Nonoverlapping template matching test
0.4903 (mean)
Random
Overlapping template matching test
0.0173
Random
Maurer’s “universal statistical” test
0.8827
Random
Linear complexity test
0.6231
Random
Serial test
0.7478 (mean)
Random
Approximate entropy test
0.0921
Random
Cumulative sums test
0.5617 (mean)
Random
Random excursions test
0.2387 (mean)
Random
Random excursions variant test
0.4487 (mean)
RandomThen we choose 100 randomx0 and set M=125000 to do SP800-22 test, and Table 4 lists the mean P value and the passing ratio. For the significance level α set as 0.01, it 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 [p-3p(1-p)/l,p+3p(1-p)/l], where l represents the number of the samples tested and p=1-α is the probability of passing each test [26]. For l=100 and p=0.99, we obtain the confidence interval [0.9602,1.0198], that is, [0.9602,1]. From Table 4, we can get that the computed passing ratio for each test lies inside the confidence interval.Table 4
MeanP value and the passing ratio in SP800-22 tests with 100 random x0.
Test
MeanP value
Passing ratio
Results
Frequency (monobit) test
0.4750
0.9900
Success
Frequency test within a block
0.8343
1.0000
Success
Runs test
0.8343
0.9900
Success
Test for the longest run of ones in a block
0.5749
1.0000
Success
Binary matrix rank test
0.0376
1.0000
Success
Discrete fourier transform test
0.2133
0.9800
Success
Nonoverlapping template matching test
0.4871
0.9907
Success
Overlapping template matching test
0.1719
0.9800
Success
Maurer’s “universal statistical” test
0.4750
0.9900
Success
Linear complexity test
0.4944
0.9700
Success
Serial test
0.2739
1.0000
Success
Approximate entropy test
0.4944
0.9800
Success
Cumulative sums test
0.7488
0.9900
Success
Random excursions test
0.3408
0.9871
Success
Random excursions variant test
0.3988
0.9837
Success


## 4. Conclusion

In this paper, we propose a new theorem for a class of topologically conjugated maps of Tent Map to generate independently and uniformly distributed key streams. Two examples are provided to validate that the key stream generated by the proposed theorem is theoretically and experimentally provedto beindependently and uniformly distributed. We also conducted experiments for testing the randomness of these key streams, and all the key streams passed the NIST SP800-22 test. In future, this theorem could be applied to information security, numerical simulation, and other fields.



---

*Source: 619257-2012-11-21.xml*