# A Novel True Random Number Generator Based on Mouse Movement and a One-Dimensional Chaotic Map

Authors: Wang Xingyuan; Qin Xue; Teng Lin
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

We propose a novel true random number generator using mouse movement and a one-dimensional chaotic map. We utilize thex-coordinate of the mouse movement to be the length of an iteration segment of our TRNs and the y-coordinate to be the initial value of this iteration segment. And, when it iterates, we perturb the parameter with the real value produced by the TRNG itself. And we find that the TRNG we proposed conquers several flaws of some former mouse-based TRNGs. At last we take experiments and test the randomness of our algorithm with the NIST statistical test suite; results illustrate that our TRNG is suitable to produce true random numbers (TRNs) on universal personal computers (PCs).


---

## Body

## 1. Introduction

Random number generators (RNGs) have been widely used in recently science and technology, such as simulation, sampling, numerical analysis, computer programming, decision making, recreation, cryptographic protocols, and cryptosystems [1–7]. RNGs have two basic types: true random number generators (TRNGs) and pseudorandom number generators (PRNGs). TRNGs produce true random numbers, which are nondeterministic. That means even if all the previous values have been gotten, the next value is unpredicted. PRNGs, on the contrary, are deterministic. The pseudorandom numbers (PRNs) are generated by deterministic programs and an input called seed and can be predicted by post-time series. Because TRNGs have better security property, in the higher security required areas, like generating cryptographic keys and initialization variables in cryptographic protocols, and so forth, TPRGs are irreplaceable.However, it is widely known that TRNGs need a certain physical phenomena, like thermal noise [8, 9], atmospheric noise [10, 11], and coin tossing [1]. So if one wants to utilize the above methods to produce true random numbers (TRNs) in a personal computer (PC), which is the most widely used platform, additional equipments must be required. It is impossible in short-finance situation. So we turn to figure out the problem by using the existed equipments. We consider mouse a proper source for TRNs, because it is used universally and it produces a real random source. People move mouse in a true random pattern, and others could hardly tell the regulation of it. Even the attackers get the pattern of the past mouse movement, they cannot tell the following action the user will take. Thus, mouse appears to be a TRNG, and an increasing number of researches are focusing at this field.Hu et al. [12] and Zhou et al. [13] talk about the algorithms of generating TRNs based on mouse movement and chaotic cryptography, respectively. In literature [12], Hu et al. provide three approaches to postprocess the mouse movement pattern, and one way to transform mouse movement pattern to digital numbers. Experiment results show that their methods pass statistical tests. However, in literature [13], Zhou et al. also provide three approaches, two of which are different from the approaches in literature [12], while one of which is the same. Although two of approaches in literature [12] and all of those in literature [13] can pass the randomness test, there are some drawbacks of their algorithms. Firstly, their methods require proper movement numbers of mouse movement pattern; neither too much or too little will break the security of the algorithm. This is because their postprocess way is generally a way to count pixels of the image, so if the image’s pixels’ distribution is not uniform, the produced TRNs are not uniform, either. Thus, the produced RNs cannot pass statistical tests [13] and be provided randomness. That is to say, the TRNs’ properties rely on the mouse-produced image’s properties. Combining this reason and the issue of key space, literature [12] requires the number of points of samples to be between 256 and 1024, which limits user’s action, and is inconvenient. Second, the “MASK” method, which is considered by that first paper as the best approach among the three methods of that paper and concluded that it is able to practice in common PC applications, is a parallel image encryption algorithm [13]; it is not suitable for using on a one-element PC. Plus, the tent-map-based approach (TMA) contained in literature [13] is evaluated by the author that is unconvinced for users, since it can only produce a 104-bit random number with a single mouse movement. As well as the other method mentioned in literature [13], the free forward-feedback nonlinear digital filter method (FFNF) is also not suitable for usage because of its low speed. And the discrete 2D chaotic map permutation method in literature [12] has not also been considered random at all. Thus, we just need to compare the left two approaches, the Spatiotemporal chaos method in literature [12] and the New approach based on tent map method (NPTM) in literature [13].Here we propose a simple algorithm of TRNGs based on user’s mouse movement and a one-dimensional chaotic map. We utilize thex-coordinate to be the length of an iteration segment of our TRNs and y-coordinate to be the initial value of this iteration segment. And, when it iterates, we perturb the parameter. We take some experiments and a NIST statistical suite to test the randomness of this TRNG and compare it to the two methods mentioned above. Results show that our algorithm is random and most of the randomness properties are better than the two methods. Plus, the time cost of our algorithm is even lower. And also, our algorithm needs no additional equipments. Therefore, we can conclude that our algorithm is an effective and practicable method to produce TRNs for universal computers.


## 2. Introduction of the One-Dimensional Chaotic Map

In 2009, Aguirregabiria proposed a class of one-dimensional smooth map [14], which is depicted as follows. It has a good property that, in a certain parameter interval, this class of maps has positive Lyapunov exponent:(2.1)fr(x)=(1+r)f(x)f(c)+rf(x),
here f should accord in three conditions:(i)
f:[0,1]→[0,1] of class C3,(ii)
the Schwarzian derivative is negative in the whole interval. Schwarzian derivative is defined as(2.2)Sf(x)=f′′′(x)f′(x)-32(f′′(x)f′(x))2,(iii)
f is a unimodal map and f(0)=f(1)=0. That is to say, the map increases from f(0)=0, when it comes to the maximum f(c), c∈(0,1), the map begins to decrease until f(1)=0 again.When map satisfies the three conditions above, we call the map “S-unimodal” [14].Takef(x)=x(1-x), for example, and in the rest of this paper, f(x) is also defined as that. Then, by the proof in literature [14], the function fr(x) has positive Lyapunov exponent in the interval (-0.75,+∞). We draw the Lyapunov exponent in Figure 1(a) by computing numerically by(2.3)λ=lim⁡N→∞1N∑n=1Nln⁡|fr′(xn)|.The curves of Lyapunov exponent.
(a)
Map (1) forr∈(-1,100)(b)
Map (4) forr∈(-30,70), k=30And then, we use a modified class of one-dimensional maps in (2.4), here k is the expansion coefficient of r on negative axle:(2.4)frk=(k+r)f(x)kf(c)+rf(x).By simple calculation, one can find out that whenr>k, frk is S-unimodal, too. Here we take k=30; one can see that frk has positive Lyapunov exponent λ showed in Figure 1(b), when r>-22.5. And in the rest of this paper, we are likely to use these parameters to build our TRNG.


## 3. TRNGs Algorithm Based on Mouse Movement

Here we are going to depict our algorithm carefully. We firstly choose the one-dimensional map depicted before to be the iteration map of our TRNGs algorithm. We then get the pattern of the mouse movement showed in Figure2, which is the material of our TRNGs. We utilize the points of mouse movement, which construct Figure 2. We consider the x-coordinate of a point to be the numbers of the iteration and the y-coordinate to be the initial of the iteration. So that one point can deduce a sequence of numbers, which is produced by iterations. The more points the mouse moving, the more sequences will be produced. And as the initial value and the numbers of one iteration are totally unknown and absolutely cannot be predicted, those sequences are TRNs. And even there are only a few points existed; there will be lots of numbers produced. That solves the problem in literature [12] of constraining the number of points of mouse movement pattern. To remark it, the y-coordinate should be divided by 900 before it is used to be the initial value.Figure 2
The mouse movement pattern.What is more, we add perturbation in each iteration, which will increase the randomness and break the periodic phenomenon. We replace the parameterri with the value xi-1.5. That will guarantee the parameter r will not depart too much but approximate the value −1. It will preserve properties of the TRNs we produced. And we use the binary quantization to transform our TRNs to a binary sequence in (3.1). Here t is the threshold, and we adopt t=0.5. Although there are lots of methods to be the transformation [15–18], we still use binary quantization for its simplicity. In the next section, we will introduce several experiments and statistical tests to test the sequence we generated whether random or not and compare the time cost and the randomness with the spatiotemporal chaos approach:(3.1)xi′={0,xi<t,1,xi≥t,i∈N.


## 4. Experiments and Results

### 4.1. Kernel Density Map, Histogram, and Autocorrelation Function

Using the algorithm we proposed above and the pattern we have, we produced 1000000 TRNs. We firstly draw the kernel density map in Figure3 and histogram in Figure 4 with the real value sequence of our TRNs, which are real numbers. The histogram equation is in(4.1)D=∑0n-d-1xi′⊕xi+d′,d≥0.Figure 3
Kernel density map.Figure 4
Histogram of the sequence.Consideringx′ is an n number binary sequence, x′′ is a shifted sequence referred to x′. Let D be the number of bit-to-bit disagreements between x′and x′′. Here d is the number of time sequences between x′ and x′′.Moreover, we draw the autocorrelation function of our binary sequences TRNs using the equation in (4.2).The autocorrelation functionC is(4.2)C=n-d-2Dn-d.The autocorrelation function then is shown in Figure5, which is a δ-like function.Figure 5
Autocorrelation function.


### 4.2. NIST Statistical Test Suite

We also test our binary sequences with the NIST statistical test suite [19], which depicts deviations of a binary sequence from randomness. Unlike the Version 1.7 (and before) NIST statistical test suite [20] used in [12], which contains 16 items, including Lempel-Ziv complexity test (LZCT), we use the 2010 version NIST statistical test suite [19], the number of the items of which is 15. Thus, in this paper, we just list 15 items for comparison. The value of each test represents the degree of randomness of the tested sequence. 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. For more details, please refer to literature [19]. In this test, all approaches were implemented with nonoptimized Matlab codes, running on an ordinary PC with 1.5 GHz Intel Celeron CPU.In Table1, we compare the time used in order to generate 256-bit data, including our algorithm, Spatiotemporal chaos in literature [12], and the New approach based on tent map (NPTM) in literature [13]. Moreover, we list results of the NIST statistical test suite of our algorithm, the spatiotemporal chaos approach contained in literature [12], and the New approach based on tent map (NPTM) contained in literature [13] in Table 2. As there are two tests of spatiotemporal chaos approaches for n=1000 and n=10000, respectively, we list them all in the table.Table 1
Average time required to generate a random number using different approaches.
ApproachOur algorithmSpatiotemporal chaosNPTMTotal time (milliseconds)217230282Table 2
800-22 test’s results.
TestOur algorithmSpatiotemporal chaos (n=10000)Spatiotemporal chaos (n=1000)NPTMConclusionFrequency test0.7236740.32950.09380.1223RandomFrequency test within a block0.7777090.83030.91750.2236RandomRuns test0.6032110.98810.89990.0391RandomTest for the longest run of ones in a block0.7840890.37820.20190.0616RandomBinary matrix rank test0.264830.82740.67240.3221RandomDiscrete fourier transform test0.8077480.20870.03460.2622RandomMaurer’s “universal statistical” test0.4412630.24570.14660.0640RandomLinear complexity test0.6267670.57250.46540.3267RandomNonoverlapping template matching test0.9048320.62380.53830.0012RandomOverlapping template matching test0.6256510.22640.01410.4118RandomApproximate entropy test0.702130.50390.41800.9737RandomSerial test0.6170750.34480.10570.6434RandomCumulative sums test0.7375180.27880.13140.1875RandomRandom excursions test0.722640.35380.40720.6352RandomRandom excursions variant test0.8638320.74590.67310.9216Random


### 4.3. Results and Comparison

By comparing the items in Table2, we find out that there are more items, although not all of them, of our algorithm that are better than that of the other three methods. For example, comparing to Spatiotemporal chaos (n=10000) and Spatiotemporal chaos (n=1000), there are 12 items in 15 in the table of our method that are better than that of the two methods. And also, comparing to NPTM, there are also 11 items of ours that are better than that of it.


## 4.1. Kernel Density Map, Histogram, and Autocorrelation Function

Using the algorithm we proposed above and the pattern we have, we produced 1000000 TRNs. We firstly draw the kernel density map in Figure3 and histogram in Figure 4 with the real value sequence of our TRNs, which are real numbers. The histogram equation is in(4.1)D=∑0n-d-1xi′⊕xi+d′,d≥0.Figure 3
Kernel density map.Figure 4
Histogram of the sequence.Consideringx′ is an n number binary sequence, x′′ is a shifted sequence referred to x′. Let D be the number of bit-to-bit disagreements between x′and x′′. Here d is the number of time sequences between x′ and x′′.Moreover, we draw the autocorrelation function of our binary sequences TRNs using the equation in (4.2).The autocorrelation functionC is(4.2)C=n-d-2Dn-d.The autocorrelation function then is shown in Figure5, which is a δ-like function.Figure 5
Autocorrelation function.


## 4.2. NIST Statistical Test Suite

We also test our binary sequences with the NIST statistical test suite [19], which depicts deviations of a binary sequence from randomness. Unlike the Version 1.7 (and before) NIST statistical test suite [20] used in [12], which contains 16 items, including Lempel-Ziv complexity test (LZCT), we use the 2010 version NIST statistical test suite [19], the number of the items of which is 15. Thus, in this paper, we just list 15 items for comparison. The value of each test represents the degree of randomness of the tested sequence. 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. For more details, please refer to literature [19]. In this test, all approaches were implemented with nonoptimized Matlab codes, running on an ordinary PC with 1.5 GHz Intel Celeron CPU.In Table1, we compare the time used in order to generate 256-bit data, including our algorithm, Spatiotemporal chaos in literature [12], and the New approach based on tent map (NPTM) in literature [13]. Moreover, we list results of the NIST statistical test suite of our algorithm, the spatiotemporal chaos approach contained in literature [12], and the New approach based on tent map (NPTM) contained in literature [13] in Table 2. As there are two tests of spatiotemporal chaos approaches for n=1000 and n=10000, respectively, we list them all in the table.Table 1
Average time required to generate a random number using different approaches.
ApproachOur algorithmSpatiotemporal chaosNPTMTotal time (milliseconds)217230282Table 2
800-22 test’s results.
TestOur algorithmSpatiotemporal chaos (n=10000)Spatiotemporal chaos (n=1000)NPTMConclusionFrequency test0.7236740.32950.09380.1223RandomFrequency test within a block0.7777090.83030.91750.2236RandomRuns test0.6032110.98810.89990.0391RandomTest for the longest run of ones in a block0.7840890.37820.20190.0616RandomBinary matrix rank test0.264830.82740.67240.3221RandomDiscrete fourier transform test0.8077480.20870.03460.2622RandomMaurer’s “universal statistical” test0.4412630.24570.14660.0640RandomLinear complexity test0.6267670.57250.46540.3267RandomNonoverlapping template matching test0.9048320.62380.53830.0012RandomOverlapping template matching test0.6256510.22640.01410.4118RandomApproximate entropy test0.702130.50390.41800.9737RandomSerial test0.6170750.34480.10570.6434RandomCumulative sums test0.7375180.27880.13140.1875RandomRandom excursions test0.722640.35380.40720.6352RandomRandom excursions variant test0.8638320.74590.67310.9216Random


## 4.3. Results and Comparison

By comparing the items in Table2, we find out that there are more items, although not all of them, of our algorithm that are better than that of the other three methods. For example, comparing to Spatiotemporal chaos (n=10000) and Spatiotemporal chaos (n=1000), there are 12 items in 15 in the table of our method that are better than that of the two methods. And also, comparing to NPTM, there are also 11 items of ours that are better than that of it.


## 5. Conclusion

In this paper, we first summarize some drawbacks of two proposed mouse movement TRNGs and propose a novel TRNG which conquers the flaws of the former two. The new algorithm is based on mouse movement and a one-dimensional chaotic map. The approach utilizes thex-coordinate of the mouse movement to be the length of the iteration, and the y-coordinate to be the initial value of this iteration segment. And we perturb the parameter with the real value of the produced TRNG itself when it iterates.And then, we do some experiments and we compare the time cost of the three approaches and get the result that ours is a little bit faster than the other two. Last but not least, we test the three sequences with the NIST statistical test suite. Results show that our algorithm is better than the other two and is suitable to produce TRNs on universal PC.



---

*Source: 931802-2012-02-02.xml*