Method of generating a chaos-based pseudo-random sequence and a hardware generator of chaos-based pseudo random bit sequences

• US 7,779,060 B2
• Filed: 11/12/2003
• Issued: 08/17/2010
• Est. Priority Date: 11/12/2002
• Status: Active Grant

• Current Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Inventors: Amato, Paolo, Rizzotto, Gianguido, Kocarev, Ljupco
• Primary Examiner(s): Ngo; Chuong D
• Application Number:
  US10/712,988
• Publication Number:
  US 20040153291A1
• Time in Patent Office: 2,470 Days
• Field of Search: 708/250, 708/252, 708/254, 708/255
• US Class Current: 708/250
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 9/001 using chaotic signals
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator

Abstract

A method for generating cryptographically secure (or unpredictable) pseudo-random numbers uses simple functions whose inverse is not a well-defined function and has a large number of branches, although the inverse could be easily computed on each particular branch. In this way the sequence of numbers is practically unpredictable and at the same time may be generated using very simple functions. A generator of such a pseudo-random bit sequence comprises circuit means for storing bit strings representing integer numbers of the pseudo-random sequence; a shift register coupled to the circuit means; a command circuit generating shift commands for the shift register; second circuit means for storing the bits output by the shift register; an adder modulo 2 summing the bits stored in the second circuit means, generating a bit of the chaos-based pseudo-random bit sequence; a second adder summing up the bit strings currently stored in the shift register and in the first circuit means, generating a bit string representing a successive number of the pseudo-random sequence.

Claims

1. A computer-implemented method for generating a chaos-based pseudo-random sequence (Xn) comprising the steps of:

defining a chaotic map for generating a pseudo-random sequence of integer numbers (xn) comprised in a certain interval ([0, q]);

defining a function (H(x)) on a first interval (x [0, q]) whose inverse has a plurality of branches;

choosing a seed (x0) of said pseudo-random sequence of integer numbers (xn) comprised in said interval ([0, q]);

generating numbers of said pseudo-random sequence (xn);

calculating numbers of a chaos-based pseudo-random sequence (Xn) by applying said function (H(x)) to corresponding integer numbers of said pseudo-random sequence (xn);

storing said chaos-based pseudo-random sequence (Xn) in a circuit; and

generating encrypted data, using a computer-implemented data generator, on a computer-readable medium by utilizing said chaos-based pseudo-random sequence (Xn) in an encryption application executing on a computer;

wherein said chaotic map is a linear congruential generator defined by;

choosing a first integer number (m);

choosing a second odd integer number (p) greater than the power of 2 raised to said first integer number (2m);

choosing a third integer number (M) much greater than said first integer number (m);

said chaotic map being defined by the following equation;

$x_{n+1}=\left(\frac{p}{2^m}·<br><br>x_n\right)<br><br><br><br>\mathrm{mod}<br><br><br><br>2^{<br><br>M}.$

2. The method of claim 1, wherein the inverse of said function (H(x)) has a number of branches equal to the largest bound (q) of said interval ([0, q]).

3. The method of claim 1, wherein defining said function (H(x)) comprises defining (H(x)) such that it may assume only two values ( ).

4. The method of claim 3, comprising the steps of:

representing in binary form said integer numbers (xn) of said pseudo-random sequence;

defining a second integer number k;

defining said function (H(x)) as the binary sum of the k least significant bits of the binary representation of its argument (x).

5. The method of claim 4, comprising the steps of:

providing circuit means for storing bit strings representing integer numbers (xn) of said pseudo-random sequence;

providing a shift register (R1) coupled to said circuit means;

storing a seed (x0) in said circuit means;

carrying out cyclically the following operations;

copying in said shift register (R1) a bit string stored in the circuit means representing a current number (xn) of said pseudo-random sequence,

providing k shift commands to said shift register,

generating a bit (Xn) of said chaos-based pseudo-random bit sequence by summing modulo 2 the k bits output by said shift register,

generating a bit string representing a successive number (xn+1) of said pseudo-random sequence by summing up the bit string currently stored in said shift register (R1) and the bit string representing said current number (xn),

storing in the circuit means the bit string representing said successive number (xn+1).

6. The method of claim 4, comprising the steps of:

providing circuit means for storing bit strings representing integer numbers (xn) of said pseudo-random sequence;

providing a register coupled to said circuit means;

storing a seed (x0) in said circuit means;

carrying out cyclically the following operations;

copying in said register a bit string stored in the circuit means representing a current number (xn) of said pseudo-random sequence,

generating a bit (Xn) of said chaos-based pseudo-random bit sequence by summing modulo 2 the k least significant bits of the bit string stored in said register,

generating a bit string representing a successive number (xn+1) of said pseudo-random sequence by summing up the bit string representing said current number (xn) and the bit string obtained eliminating the k least significant bits of the bit string stored in said register,

storing in the circuit means the bit string representing said successive number (xn+1).

7. The method of claim 3, wherein said chaotic map is a truncated linear congruential generator.

8. The method of claim 7, wherein said truncated linear congruential generator is defined by:

choosing a first integer number (m);

choosing a second odd integer number (p) greater than the power of 2 raised to said first integer number (2M);

choosing a third integer number (M) much greater than said first integer number (m);

said chaotic map being defined by the following equation;

$x_{n+1}={\mathrm{trunc}}_k<br><br>\left(\left(\frac{p}{2^m}·<br><br>x_n\right)<br><br><br><br>\mathrm{mod}<br><br><br><br>2^{<br><br>M}\right).$

9. The method of claim 7, wherein said linear congruential generator is defined by:

choosing a first integer number (m);

choosing a second odd integer number (p) greater than the power of 2 raised to said first integer number (2m);

choosing a third integer number (M) much greater than said first integer number (m);

said chaotic map being defined by the following equations;

$\hspace{1em}<br><br>\{\begin{array}{c}{y}_n=x_n\oplus <br><br>X_n\\ x_{n+1}={\mathrm{trunc}}_k<br><br>\left(\left(\frac{p}{2^m}·<br><br>y_n\right)<br><br><br><br>\mathrm{mod}<br><br><br><br>2^{<br><br>M}\right)\end{array}.$

10. The method according to claim 1 wherein said third integer number (M) is greater than or equal to 64.

11. A generator of chaos-based pseudo-random bit sequences operable in an encryption application, comprising:

circuit means for storing bit strings representing integer numbers (xn) of said pseudo-random sequence;

a register coupled to said circuit means;

an adder modulo 2 summing the k least significant bits of the of the bit string stored in said register, generating a bit (Xn) of said chaos-based pseudo-random bit sequence;

a second adder summing up the bit string representing said current number (xn) and the bit string obtained eliminating the k least significant bits of the bit string stored in said register; and

a data generator for generating encrypted data on a computer-readable medium based on said pseudo-random sequence.

12. A generator of chaos-based pseudo-random bit sequences operable in an encryption application, comprising:

circuit means for storing bit strings representing integer numbers (xn) of said pseudo-random sequence;

a shift register coupled to said circuit means;

a command circuit generating shift commands for said shift register;

second circuit means for storing the bits output by said shift register;

an adder modulo 2 summing the bits stored in said second circuit means, generating a bit (Xn) of said chaos-based pseudo-random bit sequence;

a second adder summing up the bit strings currently stored in said shift register and in said first circuit means, generating a bit string representing a successive number (xn+1) of said pseudo-random sequence; and

a data generator for generating encrypted data on a computer-readable medium based on said pseudo-random sequence.