Sequence generator and method of generating a pseudo random sequence

• US 7,142,675 B2
• Filed: 02/12/2002
• Issued: 11/28/2006
• Est. Priority Date: 02/12/2002
• Status: Active Grant

• Current Assignee: Intellectual Ventures II LLC (Intellectual Ventures LLC)
• Original Assignee: City University of Hong Kong
• Inventors: Cheng, Lee Ming, Chan, Chi Kwong
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Chai, Longbit
• Application Number:
  US10/074,124
• Publication Number:
  US 20030152221A1
• Time in Patent Office: 1,750 Days
• Field of Search: 380/29, 380/44, 380 46- 47, 380/265, 708/250
• US Class Current: 380/46
• CPC Class Codes: H04L 9/0668 producing a non-linear pseudorandom sequence

Abstract

A sequence generator for generating a pseudo random sequence for random number generation or a stream cipher engine includes a plurality of linear feedback shift registers operable to generate a plurality of binary sequences. A plurality of nonlinear functions having the binary sequences as their input and operable to generate a second plurality of binary sequences. There are at least two switches and a controller including a shift register operable to control said first and second switches. The first switch is operative to select one of the second plurality of binary sequences to the first bit of the shift register, and the second switch is operative to select one of said second plurality of binary sequences to the output of the sequence generator.

Claims

1. A sequence generator comprising:

a plurality of linear feedback shift registers operable to generate a plurality of first binary sequences,

a plurality of nonlinear function generators having said first plurality of binary sequences as their input and operable to generate a second plurality of binary sequences,

at least first and second switches,

a controller including a shift register operable to control said first and second switches,

the first switch operative to select one of said second plurality of binary sequences to the first bit of the controller shift register, and the second switch operative to select one of said second plurality of binary sequences to an output.

2. A sequence generator for generating a pseudo random sequence for random number generation or a stream cipher engine comprising:

a sequence generator operable to generate a first plurality of binary sequences,

at least first and second nonlinear function generators having said first plurality binary sequences as their input, the first nonlinear function generator operative to generate a second plurality of binary sequences and the second nonlinear function generator operative to generate a third plurality of binary sequences,

at least first and second switches,

a controller having an input and at least first and second outputs operable to control said first and second switches,

the first switch operable to select one said second plurality of binary sequences to the input of the controller, and the second switch operable to select one of said third plurality of binary sequences to an output.

3. A sequence generator according to claim 2 wherein the sequence generator includes a plurality of feedback shift registers each operable to generate a binary sequence.

4. A sequence generator according to claim 2 wherein the nonlinear function generators includes a plurality of Boolean functions, each Boolean function having the first plurality of binary sequences as an input and being operable to generate a binary sequence.

5. A sequence generator according to claim 2 wherein the switches are multiplexers.

6. A sequence generator according to claim 2 wherein the controller includes a shift register, the input of the controller being the first bit of the register and the outputs of the controller being at positions along the register.

7. A method of generating a pseudo random sequence in a sequence generator having a plurality of linear feedback shift registers and nonlinear function generators, the method comprising:

in the linear feedback shift registers, generating a first plurality of binary sequences,

in the nonlinear function generators, applying a plurality of nonlinear functions to the first plurality of binary sequences to obtain an uncorrelated second plurality of binary sequences, and

randomly selecting an output sequence from one of the second plurality of binary sequences.

8. A method according to claim 7 wherein the nonlinear functions are arranged to provide a one-to-many relationship between the first and second plurality of binary sequences.

9. A method according to claim 7 wherein the nonlinear functions are Boolean functions.

10. A method according to claim 7 wherein the output sequence is randomly selected by applying one of the second plurality of binary sequences to a shift register.