A Novel Approach for Producing High Throughput PRNG

A Novel Approach for Producing High Throughput PRNG

D. Magbul Basha1, R. Vijaya2

PG Student [VLSI] , Dept. of ECE, Dhruva Institute of Engineering and Technology, Hyderabad,A.P,India.1 Assistant Professor, Dept. of ECE, Dhruva Institute of Engineering and Technology, Hyderabad, A.P,India.2

ABSTRACT

When we want to design the fast circuit or fast system naturally we have to go for some solutions. And we know that pseudo random number generator is used to generate a long period random number sequence The PRNG collects randomness from various low-entropy input streams, and tries to generate outputs that are in practice indistinguishable from truly random streams. Typical PRNG consists of unpredictable input called seed value and a secret state S. but the output random numbers of such generators are predictable due to their linear structure. To overcome the unpredictability here we are presenting a new method called reseeding- mixing, And this method is use to extend the system period length and to enhance the statistical properties of a chaos-based pseudo random number generator (PRNG).In this model the reseeding method is used to remove the short periods of the digitized logistic map and the mixing method is for extends the system period length to 2253 by XORing with a DX generator. By that we will achieve a High throughput rate that is more than 6.4 Gb/s by producing the multiple bits per iteration and the low hardware is also validated. In this the output sequence of the RM- PRNG is used as a key to encryption and Decryption models. The simulation results are obtained by using Modelsim and synthesis output is validated by using Xilinx ISE.

Index Terms Reseeding ,Mixing, period extension, pseudo random number generator (PRNG).

1. INTRODUCTION

   Many cryptographic applications don't have a reliable source of real random bits, such as thermal noise in electrical circuits. Instead, they use a cryptographic mechanism, called a Pseudo-Random Number Generator (PRNG) to generate these values. Pseudo random number generator (PRNG)s are mainly used for test pattern generation, cryptography, and telecommunication systems. and also we have Some nonlinear PRNGs in dealt with the predictability problem, but incurred higher hardware cost and more process time, the Session keys,

   initialization vectors, salts to be hashed with passwords, unique parameters in digital signature operations. But recently security applications have increased the need for strong (secure) random number generation like automatic password generation, encryption algorithms, on-line gambling etc. so that the PRNG collects randomness from various low-entropy input streams, and tries to generate outputs that are in practice indistinguishable from truly random streams. A good PRNG should have three main characteristics those are of long- period random number sequence, a fit in statistical properties, a high pattern generation rate and an unpredictability. We have several Linear PRNGs, such as linear feedback shift registers (LFSRs) and multiple recursive generators (MRGs),which produce long-period random number sequences. When we fine the implementation, this linear PRNGs are efficient in test pattern generation rate and low hardware cost, but the output random numbers of such generators are unsecure due to their linear structure. So that will find Some nonlinear PRNGs but these are the factors of hardware cost and requires more processing time. To avoid all these problems Recently, a new method is proposed with nonlinear chaos-based PRNGs (CB-PRNGs) with lower hardware cost . Chaos theory studies nonlinear systems defined on a infinite state space whereas cryptography is cascade on a finite-state machine .

   To get over all the problems presented in liner and nonlinear PRNGs here we will find a new system which consists of a CB-PRNG and a long-period MRG. By using this method we will generated a long period randomness with high test pattern generation rate. In this the reseeding method removes the disadvantages of short periods in CB-PRNG while the mixing of the CB-PRNG with an MRG pushes the overall system period length to a value >2

   253 based on simple theoretical calculation. High throughput rate (>6.4 Gb/s) is achieved by outputting multiple bits per iteration and also the lower hardware is achieved by using a modelsim simulator. good statistical qualities of the random numbers.

2. EXISTING SYSTEM

   As we know that the Linear PRNGs, such as linear feedback shift registers (LFSRs) linear congruential generators (LCGs) and multiple recursive generators (MRGs) can produce long-period random number sequences. LFSR(linear feedback shift register) for test pattern generation Applications for the digital circuits and LFSRs include generating many number of fast digital counters, and. but the output random numbers of such generators are predictable due to their linear structure. for period extension presented a reseeding method either to perturb the state value or the system

   parameter of digitized logistic map (LGM) for removing the short periods of a CB-PRNG. applied a different reseeding method in perturbing a CB-PRNG to extend its period length up to3.3672*1029, and the lower bound of the reseeded system can be calculated. and these are discovered that the reseeding technique not only removes the short periods but also improves the statistical properties of CB-PRNG.

   In order to get the high randomness quality, PRNG can be implemented using some deterministic functions. But the circuit has to be operated in high precision (long bit length) digital operation or the truncation problem would make the randomness quality of test poor. Therefore, the implementations of deterministic are usually costly in area. Moreover, another problem of the deterministic function is that its sensitivity only occurs in initial value. For this here presented another technique that uses special hardware for the LFSR such that the reseeding circuitry area overhead is minimized. Also, the technique we presented is directly applicable to the transition fault model. The mixing technique is also widely applied in period extension of nonlinear PRNGs. And also we have several mixed nonlinear feedback shift registers (NLFSRs) to obtain a long- period and high-throughput-rate stream cipher. In general, mixing multiple CB-PRNGs results in higher hardware cost, lower throughput rate, and longer but unpredictable period length. Furthermore, one cannot be sure that the random numbers produced by these mixed PRNGs will have acceptable statistical properties. Since higher hardware cost is due to implementation of multiple CB-PRNGs which are more complex than linear PRNGs, mixing a CB- PRNG with a linear MRG instead of mixing two CB- PRNGs will reduced the hardware cost. In Section III, we will introduce our proposed method.

3. PROPOSED SYSTEM

   In our proposed RM-PRNG, which consists of a CB- PRNG and an MRG, the period length is considerably extended because the period length of the MRG is much longer than that of the CB-PRNG while the short periods of the CB-PRNG can be removed by our reseeding algorithm. Note that the lower bound of the period length in RM-PRNG can be calculated analytically in terms of the period length of the CB-PRNG and that of the MRG. In addition, the throughput rate is enhanced using a vector-mixing technique in the proposed RM-PRNG. Finally, the statistical properties is improved because the linear structure of the MRGs is broken by mixing with a CB-PRNG. T o overcome the problems presents in the choas based design and multiple recurive generators here we proposed a new design of combination of these two systems Fig. 1 shows the diagram of the proposed system, which is composed of three modules: Nonlinear Module, Reseeding Module, and Vector Mixing Module.

   Fig. 1. Structure of the proposed RM-PRNG.

   1. Nonlinear Module

      In implementation, the Nonlinear Module has a controlled 32-b state register and a Next-State construction circuitry. The controlled register stores the state value Xt which can be set to Seed1 by the Start command. The Next-State construction circuitry produces the next state value Xt+1 according to the

      recursive formula Xt+1 =F(Xt ). The module provides an extensive set of nonlinear structural material models, including Predefined and user-defined hyperelastic materials Small-strain and large-strain plasticity models using different hardening models. We use the LGM as the next-state construction function in the Nonlinear Module so that

      Xt+1 =F (Xt ) = Xt (1- Xt ), t0

      with = 4 and X0 ( 0,1) as an initial seed. Choosing a value 4 for not only makes the LGM chaotic but also simplifies the implementation of to merely left-shifting the product of Xt and (1- Xt ) by 2 b. However, the state size decreases from 32 to 31 b, because the dynamics Xt and (1- Xt ) in (1) are the same. This is equivalent to a degradation of resolution by 1 b. In addition, fixed points (at Xt = 0 and 0.75) as well as short periods exist when the LGM is digitized. From exhaustive runs for all of the 2 32 seeds, we obtain all other periods for the 32-b LGM ( P LGM )without reseeding. They are given in Table I with the longest period (18 675) and the set of short periods Ts (1338) listed separately along with their total occurrences. Clearly, the performance of a CB-PRNG using only the Nonlinear Module is unsatisfactory. To solve the fixed points and short- period problem, a Reseeding Module is in order.

      TABLE I

      REMOVAL OF SHORT PERIODS BY THE RESEEDING METHOD

      Fig. 2. Core layout and characteristics of proposed nonlinear PRNG.

   2. Reseeding Module

      For each generated state value The RC will be reset and the reseeding operation will be activated when

      either the fixed point condition is detected or the RC reaches the reseeding period. When RC reaches the reseeding period Tr or the fixed point condition is detected then RC will be reset and the reseeding operation will be activated. The sate register will be loaded through the rmux, when reseeding is activated [1].When the fixed point condition is detected or the reseeding period is reached, the value Zt+1 loaded to the state register will be perturbed away from Xt+1 in the RCU by the fixed pattern _ according to the formula given below

      Z t+1 [ j] = Xt+1[j] , 1 j 32 – L;

      R[i], 33-L j 32 , I = j + L -32 (2)

      where subscripts i,j are the bit-index, L is integer, and R0. In order to minimize the degradation of the statistical properties of chaos dynamics, the magnitude of the perturbation of the fixed pattern _ should be small compared with Xt. Here, we set L= 5 so that the maximum relative perturbation is only (2 5

      1) /2 32. Clearly, the effectiveness of removing short-periods depends on the reseeding period T, as well as the reseeding pattern R. However, choosing the optimal reseeding period and the reseeding pattern is nontrivial. Nevertheless, several guidelines to choose a suitable combination of Tr and R had been proposed and discussed in our previous work Then no effective reseeding will be realized and the system will be trapped in the short-period cycle.

      Hence, prime

      numbers should be used as the reseeding period candidates. In this study, we use Tr and R = 18(10010)", and the result is shown in Table I. One can see that the set of short periods Ts is indeed eliminated. The lowest period, the maximum period and the average period of the reseeded PRNG are, respectively, 1929, 2 330 875, and 2 321 423.005. Although the average period of the reseeded PRNG has increased more than 100 times relative to that of the non reseeded counterpart, the period can in fact be extended tremendously in the Vector Mixing Module described below.

   3. Vector Mixing Module

      An efficient MRG, called the DX generator , serves as the ALG in Vector Mixing Module. Specifically, we choose the DX generator with the following recurrence equation:

      Yt+1 = Yt + Bdx . Y t-7 mod M

      _ (3)

      Using an efficient search algorithm , we find that the particular choice of Bdx = 2 28 + 2 8 and M= 2 31 1 gives the maximum period of the DX generator. The LSBs of and that of Yt+1 are mixed in the Output Construction unit using a XOR operation to obtain the least significant bits of the output according to the equation

      OUT t+1 [1:31] = Xt+1 [1:31] XOR Yt+1

      _ _ (4)

      Then, the most significant bit (MSB) of Xt+1 is attached to OUT t+1 [1:31] to form the full 32-b output vector OUT .

   4. DX Generator (ALG)

   The value of Xt+1 is directly loaded into the state register if the reseeding is not activated. Vector Mixing Module is implemented by an auxiliary linear generator (ALG) and output construction. By mixing Xt+1 with the output Yt+1 from ALG in Vector Mixing Module, we obtain the output of the RM- PRNG (32-bit implementation).The models used in MPC are generally intended to represent the behavior of complex dynamical systems. The additional complexity of the MPC control algorithm is not generally needed to provide adequate control of simple systems, which are often controlled well by generic PID controllers. Common dynamic characteristics that are difficult for PID controllers include large time delays and high-order dynamics.

   The implementation of the DX generator is (the ALG) done by using 8-word registers, circular-left- shift (CLS), circular 3-2 counter and End Around Carry- carry look ahead adder (EAC-CLA). By using flip-flops the eight-word register was implemented. For generating two partial products signal Yt-7 is circular-left-shifted 28 and 8 b , using the modules CLS-28 and CLS-8 respectively. To combine these three 31-b operands into two 31-b operands a circular 3-2 counter is used, which consumes 247 gates. To evaluate Yt+1 31-b EAC-CLA is used with 348 gates. The schematic design of the 31-b EAC-CLA. The schematic design of the 31-b EAC-CLA includes four modules they are propagation and generation (PG) generators, end-around-carry (EAC) generator, internal carry (IC) generator, and CLAs.

4. RESULTS AND SIMULATION Pseudo Random Number Generator, Encryption and Decryption were designed using Verilog language in ModelSim 6.3. All the simulations are performed using ModelSim 6.3 simulator. The simulated output of Pseudo Random Number Generator, Encryption and Decryption are shown in Figure 3&4.

5. CONCLUSION

In this paper, we proposed a cryptographic algorithm using RM-PRNG to ensure secure communication. This Cryptographic algorithm allows people to carry over the confidence found in the physical world to the electronic world, thus allowing people to do business electronically without worry of deception. With these secure communications, the proposed cryptographic algorithm using RM-PRNG can a good candidate for protect the data in ATM cards, computer passwords and electronic commerce.

Figure 3. Simulation results for RM-PRNG

Figure 4. Simulation results for cryptography

REFERENCES

1. Chung-Yi Li, Yuan-Ho Chen, Tsin-Yuan Chang, Lih-Yuan Deng, and Kiwing To, Period Extension and Randomness Enhancement Using High-Throughput Reseeding-Mixing PRNG.

2. J. E. Gentle, Random Number Generation and Monte Carlo Methods, 2nd ed. New York: Springer-Verlag, 2003.

3. M. P. Kennedy, R. Rovatti, and G. Setti, Chaotic Electronics in Telecommunications. Boca Raton, FL: CRC, 2000.

4. D. Knuth, The Art of Computer Programming, 2nd ed. Reading, MA: Addison-Wesley, 1981.

5. A. Klapper and M. Goreky, Feedback shift registers, 2-adic span, and combiners with memory, J. Cryptology, vol. 10, pp. 111147, 1997.

6. D. H. Lehmer, Mathematical methods in large-scale computing units, in Proc. 2nd Symp. Large Scale Digital Comput. Machinery, Cambridge, MA, 1951, pp. 141146, Harvard Univ. Press.

7. S. Li, X. Mou, and Y. Cai, Pseudo-random bit generator based on couple chaotic systems and its application in stream- ciphers cryptography, in Progr. Cryptol.-INDOCRYPT, 2001, vol. 2247, pp. 316329, Lecture Notes Comput. Sci.

8. L. Y. Deng and H. Xu, A system of high-dimensional, efficient, long cycle and portable uniform random number generators, ACM Trans. Model Comput. Simul., vol. 13, no. 4, pp. 299309, Oct. 1, 2003.

9. L. Blum, M. Blum, and M. Shub, A simple unpredictable

pseudorandom number generator, SIAM J. Comput., vol. 15, pp. 364383, 1986.