The generation of a pseudorandom string for the construction of the encryption keys.

Dascalescu, Ana ; Nidelea, Marinela

1. INTRODUCTION

The stream ciphers encrypt individual characters (usually binary digits) of a plaintext message one at a time, using an encrypted transformation which varies with time. The main problem is to generate such encryption key that can be obtained either randomly or based on an algorithm which starts from a small sequence of encryption keys. In this regard, the article presents the results obtained in a project that aims to generate a pseudorandom sequence with large period to build the encryption stream keys.

There are described the implementation stages of a new algorithm for the generation of the irreducible polynomials of degree higher than 256 that have coefficients in the finite field [Z.sub.2]. The string of bits corresponding to the coefficients of the generated polynomials is used for the construction of a shift register linear feedback. The obtained result is a string of pseudorandom numbers with long period that can be successfully used for the construction of the encryption stream keys.

2. ABOUT THE GENERATION OF THE PSEUDORANDOM NUMBERS

A perfect random number is a number that the attacker cannot guess but through gross strength. A very important part of the cryptanalysis is based on exploiting the imperfections of some functions that generates random numbers.

A pseudorandom numbers generator (PRNG) is an algorithm for generating a string of numbers that are relatively independent to each other and that approximates some properties of the strings of random numbers.

Since any PRNG that runs on a deterministic computer is a deterministic algorithm, the generated string will have certain characteristics that a string of natural random number does not have. This characteristic is the frequency, guaranteed by the fact that the generator uses a fixed amount of memory, which will lead, after a sufficiently number of iterative, the algorithm returns to an interior state already crossed. Another characteristic of a PRNG is highlighted by the possibility of being activated from an arbitrary starting point--the initially state, each time producing the same string of numbers (Bruen, 2005).

To generate a string of numbers, will be established the initial values [x.sub.1], [x.sub.2], ..., [x.sub.k] which form the seed of the generator. It will be applied the recurrence relationship:

[x.sub.n] = g([x.sub.n-1], [x.sub.n-2], ..., [x.sub.n-k]), n > k (1)

where g:M [right arrow] M with M a sub-multitude of natural numbers that can be represented in computer.

The generator of pseudorandom numbers must fulfill the following conditions:

* To be simple and quick;

* To produce strings of numbers with arbitrary length which includes no repetitions;

* To generate numbers with an uniform distribution;

The implementation of these conditions can be ensured through a good option of the function.

In practice, the pseudorandom number generators used up to present can be divided in the following classes: arithmetical pseudorandom numbers, mathematical pseudorandom numbers, pseudorandom numbers based on feedback shift register, pseudorandom numbers based on chaotic functions. (Shaska, 2007).

2.1 Generation of pseudorandom numbers by shift registers

A linear feedback shift register includes two parts: one shifting registry composed of one string of bits whose number determines the length of the registry and a feedback function.

To generate a bit, all the existing bits in the register are shifted to the right. The output of the register is the bit from the right position, which leaves the register through the shifting. The register is completed with a new bit position on the left, this being calculated as the value of a function of other bits from the register (Fig.1). The period of a shift register is determined by the length of the string of generated bits, before this string to be repeated.

[FIGURE 1 OMITTED]

The simplest register is LFSR (Linear Feedback Shift Register). The feedback function is XOR operation between certain bits of the register; the list of bits is called the "tap" sequence or Fibonacci configuration.

A generator of n-bit LFSR can be in one of the 2n - 1 possible states (excluding the state in which all the bits of the register are 0, since this will generate an infinite string of zeros) and theoretically could generate a string of length m = [2.sup.n-1] pseudorandom bits before it repeats. In order to the LFSR to go through all [2.sup.n-1] possible state is necessary to choose a specific "tap" sequence. In this case the generator is a maximal LFSR, and the generated string of bits is called the m-string.

The configuration of a linear feedback shift register with n states may be based on a polynomial (named characteristic) p(x) = 1 + [c.sub.1]x + [c.sub.2] [x.sup.2] + ... + [c.sub.n][x.sup.n] [member of] [Z.sub.2][x], [c.sub.n] = 1 (2)

[FIGURE 2 OMITTED]

In Figure 2 it can be observed that a LFSR with the initial state [[s.sub.n-1], [s.sub.n-2], ..., [s.sub.0]] determines in a unique way, the output sequence s = [s.sub.0], [s.sub.1], [s.sub.2] ..., through the following recurrence:

[s.sub.j] = ([c.sub.1][s.sub.j-1] + [c.sub.2][s.sub.j-2] + ... + [c.sub.n][s.sub.j-n])mod 2, for j [greater than or equal to] n. (3) (Konheim, 2007).

A linear feedback shift register can be used for normal polynomial operations: additions, subtractions, multiplications and divisions. Therefore, the "tap" sequence may correspond to a polynomial g(x) [member of] [Z.sub.2] and in the storage elements f(x) [member of] [Z.sub.2] the coefficients of an arbitrary polynomial can be introduced. In the Figure 3 is presented a linear feedback shift register with a particularized structure to make the division of two polynomials. (Menezes, 1997).

[FIGURE 3 OMITTED]

If the polynomial g(x) [member of] [Z.sub.2] of degree n which forms the "tap" sequence is irreducible over [Z.sub.2], may be defined the multitude of the rests classes polynomial modulo g(x) such:

[G.sub.g] = {u = [a.sub.0] + [a.sub.1] [alpha] + ... + [a.sub.n-1] [[alpha].sup.n-1], [a.sub.i] [member of] [Z.sub.2]} (4)

g([alpha]) = 0, where a can be considered a polynomial of degree n -1.

In the register from Figure 3, if the "tap" sequence polynomial is irreducible and in the storage elements are introduced the initial polynomial coefficients b(x) = 1, namely the vector (1,0, ..., 0) at the next step a is obtain. Letting the register to function, the elements of the multitude {[alpha].sup.2], [[alpha].sup.3], ..., [[alpha].sup.n-1]} are consecutively generated. (Atanasiu, 2001).

In the algebraic theory of the finite fields, applied to the [G.sub.g] field defined above, the following results have been emphasized:

--the number of elements of [G.sub.g] is [2.sup.n];

--the [G.sub.g] field can be built from the roots of the polynomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

In conclusion, for the LFSR to generate a pseudorandom number sequence with maximum period, the polynomial which forms the "tap" sequence must be an irreducible polynomial modulo 2, with degree equal to the length of the register.

3. PROPOSED ALGORITHM FOR THE PSEUDORANDOM SEQUENCES GENERATION

In order to achieve the desideratum of pseudorandom number generation with longer periods it is proposed the elaboration of an algorithm that generates irreducible polynomials with a degree greater than 256. The results obtained are introduced in the linear feedback shift registers described above, resulting pseudo-random number sequences with longer periods, which can be used successfully for the construction of cryptographic stream keys.

Having as starting point the results from the theory of finite fields listed above, the algorithm involves the selection of a polynomial such as [u.sub.1] = x, and for each i = 1,2 ... 256 involves the construction of the polynomials ui through the following steps:

1) it calculates [v.sub.i] = the rest of the division of [([u.sub.i]).sup.2] to the polynomial f(x) [member of] [Z.sub.2].

2) it calculates the [f, {[v.sub.i] + x)] = [d.sub.i] the greatest common factor of f and the polynomials [v.sub.i] + x and interprets the result such as:

--if [d.sub.i] [not equal to] 1 then the polynomial f is reducible and the testing ends.

--if [d.sub.i] = 1, than it is built the polynomial [u.sub.i+1] = [v.sub.i] and the operations 1 and 2 are repeated.

If [d.sub.1] = [d.sub.2] = ... = [d.sub.256] = 1, then it concludes that the polynomial f is irreducible.

The number of irreducible polynomials with degree n in field [Z.sub.2] is N =[2.sup.n] - 2/n, and after running the program, the output is corresponding to some bits sequences in number of [2.sup.215].

The string of bits obtained by applying the algorithm, is used for the construction of the " tap" sequence of a LFSR that has custom structure (Fig. 3), thus being obtained sequences of pseudorandom numbers with long periods ([2.sup.255]).

4. CONCLUSIONS

The innovative method of generating pseudorandom numbers by the register with linear feedback, used in implementation of the presented algorithm, focuses on the following aspects:

--in the generated sequence of pseudo-random numbers is no obvious correlation between the initial values and any of the values generated by it; each element of generated string appears as the output of a random independent event with the probability 1/2.

--the generated sequence of pseudo-random numbers is by the large period (up to [2.sup.255]), due to the "tap" sequence from the linear feedback shift register that has the structure of an irreducible polynomial in [Z.sub.2].

The proposed algorithm is used to generate the irreducible polynomials with a degree higher than 256. The outputs are sequences of numbers 0 and 1, corresponding to the coefficients of an irreducible polynomial in [Z.sub.2]. Based on the bits string obtained is build the "tap sequence" for a linear feedback shift register obtaining pseudorandom numbers sequences with longer periods ([2.sup.255]) that can be used successfully for construction of the encryption stream keys.

The next phase of the research project is to develop an algorithm to generate primitive polynomials of degree higher than 256, in order to obtain pseudorandom sequences with longer period.

5. REFERENCES

Atanasiu, A. (2001). Teoria codurilor corectoare de erori, Bucharest Universty, ISBN 973-575-589-0, Bucharest

Bruen, A.; Forcinito M. (2005). Cryptography, Information Theory, and Error--Correction, Wiley--Interscience, ISBN 978-0-471-65317-2, New Jersy

Konheim, A. (2007). Computer Security and Cryptography, Wiley--Interscience, ISBN 0-471-947830, New York

Menezes, A.; Ooeschot, P. & Vanstone S. (1997). Handbook of Applied Cryptography, CRC Press, ISBN 0-8493-8523-7., New York

Shaska, T. (2007). Advances in Coding Theory and Cryptography, World Scientific, ISBN 9812707017, United Kingdom