Applied Mathematics, 2011, 2, 1531-1534

doi:10.4236/am.2011.212217 Published Online December 2011 (http://www.SciRP.org/journal/am)

Copyright © 2011 SciRes. AM

Cryptographic PRNG Based on Combination of LFSR

and Chaotic Logistic M a p

Hamed Rahimov, Majid Babaei, Mohsen Farhadi

Department of C om put er Engineering, Shahrood University of Technology, Shahrood, Iran

E-mail: hrahimov@shahroodut.ac.ir, babaee@comp.tus.ac.ir, mfarhadi@shahroodut.ac.ir

Received September 6, 2011; revised October 21, 2011; accepted October 30, 2011

Abstract

The random sequence generated by linear feedback shift register can’t meet the demand of unpredictability

for secure paradigms. A combination logistic chaotic equation improves the linear property of LFSR and

constructs a novel random sequence generator with longer period and complex architecture. We present the

detailed result of the statistical testing on generated bit sequences, done by very strict tests of randomness:

the NIST suite tests, to detect the specific characteristic expected of truly random sequences. The results of

NIST’s statistical tests show that our proposed method for generating random numbers has more efficient

performance.

Keywords: Random Bit Generator, Combination, Chaotic, Logistic Equations, LFSR, NIST Suite Tests

1. Introduction

With perfect method of cryptographic algorithm based

on generating high performance of random numbers, the

need for random numbers of high quality is growing [1,

2]. Random numbers are also used for key generation in

symmetric. For example, in the Smart cards, the main

problem is the security wh ich improves by using reliable

random number generators (RNG s ) [3] .

One of the most reliable methods that work as RNG in

cryptographic algorithms is Linear Feedback Shift Regi-

ster (LFSR) [4-6] in stream cipher usage and is appropri-

ate to low power or high speed application [5]. Since

LFSRs are linear systems. They lead to responsible easy

cryptanalysis tools. The short period of LFSR’s outputs

is the negative point of using this system as a reliable

method in cryptographic algorithms.

LFSR is a shift registered the inputs of which are

based on linear function of its previous states. It uses two

linear operators Exclusive-OR () [6]. Th e LFSR is ini-

tializing by the random string that is called the seed and

since the operation of register is deterministic, the re-

sult’s string which is produced by the LFSR is comple-

tely determined (i.e. the current bit determined by its

previous states) [4,7]. If the LFSR has the n bits the big-

gest number for internal state is 2n so to gain the longest

period of this method (i.e. 2n–1), LFSR with length n

needs to find n exponent primitive polynomial [4,7]. The

architecture is shown in Figure 1.

However, the production of n exponent primitive poly-

nomials becomes more difficult with the increment of n.

Generally, through 1

2n

factorization, we can make sure

that an n exponent polynomial is a primitive po lynomial.

Furthermore, the items of n exponent primitive polyno-

mial are more complex to make a breakthrough. If the

exponent of primitive polynomial is bigger, LFSR will

be longer.

Reese defined a genetic algorithm for optimization

problem. That parent population was generated by ran-

dom number generator, pseudo random number genera-

tor, quasi random number generator [7]. Finally she ran-

ked these generators with comparing precisions gene-

rated answers by GA and showed the genetic algorithm

is a criterion to realize what initial population is more

uniformity [8]. Also chaotic random number generator

(CRNGs) was compared to other RNGs with this method

[9]. In this Paper we used another famous test method:

NIST suite test that is a statistical package comprising of

15 tests.

2. Chaotic Logistic Equation

The simple modified mathematical from of the logistic

equation is given as:

1

()(1 )

nnn n

xx rxx

(1)

where xn is the state variable, which lies in the interval