2 Linear feedback shift registers (LFSRs) make extremely good pseudo-random pattern generators and are one class of generators for random key-streams which can be used in stream ciphers, and are well suited to low power or high speed requirements.
4 choosing a feedback vector which corresponds to a primitive polynomial the generator will provide a key-stream sequence
5 that iterates through all 2n-l possible linear states, where n is the number of stages.
7 The register consists of a series of cells that are set by an initialization vector that is most often, the secret key. The behavior of the register is regulated by a clock and at each clocking instant, the contents of the cells of the register are shifted right by one position, and the Exclusive-OR (XOR) of a subset of the cell contents is placed in the leftmost cell.
9 The tap sequence of an LFSR can be represented as a polynomial mod 2. This means that the coefficients of the polynomial must be 1 's or D's. This is called the feedback polynomial or characteristic polynomial.
11 Likewise, because the register has a finite number of possible states, it must eventually enter a repeating cycle. However, an LFSR with a well-chosen feedback function can produce a sequence of bits which appears random and which has a very long cycle.
13 For example, the polynomial $x^{6} + x^{5} + x^{0}$ translates to the state transition function:
14 $s_{i+1} = [s{i,5} /xor s_{i,6} , s_{i,1} , s_{i,2} , s_{i,3} , s_{i,4} , s_{i,5}]$
17 The Mersenne Twister algorithm generates a sequence of word vectors, which are considered to be uniform pseudorandom integers between 0 and 2w – 1. Dividing by 2w – 1, each word vector can be a real number in [0, 1]. With the restriction that 2nw − r − 1 is a Mersenne prime. For a word x with w bit width, it is expressed as the recurrence relation:
18 $X_{k+n} = X_{k+m} xor (X_{k} ^{u} | X_{k+1} ^{l})A$
20 With | as the bitwise or and xor as the bitwise exclusive or (XOR), $x_{u}$, $x_{l}$ being x with upper and lower bitmasks applied.
22 A is the twist transformation which is defined in rational normal form.
24 Finally, to improve the statistical properties of the generator the numbers generated in the recurrence are modified, tempered, with a bitwise multiplication by a w × w binary matrix (T): [z = x_{k+n} T] being z the output of the generator.
26 The algorithm is split into three different tasks:
27 1. Initialization: generation of the first n vectors of the recurrence from a seed.
28 2. Obtaining the linear recurrence.
29 3. The tempering of the generated variables from the linear recurrence.
32 To use the concept of quadratic residue, Blum, Blum and Shub proposed to choose the two odd primes p and q, and compute n= p*q. Then square modulo n of seed is computed and theresulting number is considered to be the first number generated. The seed is replaced with generated number insubsequent iterations and a square modulo n is computedagain, generating a number per iteration. To geta bit sequence, least significant bit of generated number isextracted per iteration and is added to the generated binarysequence. Hence BBS needs only one square (ormultiplication) per bit generated. Let the seed is s, s€Z_{n},
34 $X_{i}=S^{2}mod n$ and the bit $bi=X_{1}mod 2$ For ith iteration
35 $X_{i}=X{_{i-1}}^{2}mod n$ and $b_{i}=X_{i}mod 2$
36 This way the algorithm needs to compute only one square operation to generate a bit, which is much less than any of the other cryptographically secure algorithm.
41 The CA will evolve in discrete time steps, where the next state of each cell interacts with their immediate neighbors based upon a local rule and updated simultaneously were initialized using six random seeds.. A cellular automata can be viewed as a state machine consisting of an array of cells which hold their current states. where the top row represents the eight [2x2x2 = 23 = 8] possible binary configurations for a three-cell neighborhood and a total of [28 = 256] elementary CA, each of which can be indexed with an 8-bit binary number and the bottom row represents the next state for the cell of interest. While higher dimensions and state values can be used.
42 The algorithm used to compute the next cell state is referred to as the CA local rule which have certain states [S ∈ {0,1}, i = 0,1,.., N – 1 ]. For example, the rule number of { I7I6I5I3I2I1I0 =00011110} is 30. If the rule of a CA involves only XOR logic, then it is called a linear rule. Rules involving XNOR logic are referred to as complement rules. A CA with all the cells having linear rules is called a linear CA, whereas a CA having a combination of XOR and XNOR rules is called additive CA. If all the cells obey the same rule, then the CA is said to be a uniform CA, otherwise, it is a hybrid CA. A CA is said to be a null boundary CA if both the left and right neighbour of the leftmost and rightmost terminal cell is connected to logic 0-state. On the fact that the CAs from class III are chaotic dynamical systems and CAs from class II exhibit periodic behaviour (each state lies in some cycles).
47 Chaos theory is well-studied in mathematics and nature phenomenal that widely exists in nonlinear systems [1, 2, 3]. It has many exceptional good properties such as the sensitivity to initial conditions and parameters, the pseudo-randomness, the topological transitivity, being irregular, non-periodicity, unpredictability, and ability to reciprocal synchronization [4]. However, in practice these solutions have also some important drawbacks and limitations, because the chaotic nature of generated series is non-ideal, due to the limited precision of arithmetic operations and quantization. As a result, instead of random number sequences we get pseudo-random or periodic series. In practice, the chaotic nature of the obtained series is non ideal, due to the finite precision of arithmetic and quantization. As a result we get pseudo-random or periodic series.
49 Theoretically, chaos based Pseudo-Random Number Generators (PRNG) is proofed with good randomness and infinite period as well. Hence, from the cryptographer’s point of view, the most essential drawbacks of the chaotic systems are: weak resistance to recovery of parameters, relatively low digital precision comparing to the analog generators, periodicity problems, non ideal probability distributions, higher level of correlation and suffer from serious dynamical degradations due to quantization error and finite representation of system states, including loss of periodicity and shorter pseudo-orbits.
