Pseudo-random number generation based on periodic sampling of one or more linear feedback shift registers

• US 20050036607A1
• Filed: 08/15/2003
• Published: 02/17/2005
• Est. Priority Date: 08/15/2003
• Status: Active Grant

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Chen, Sherman (Xuemin), Wan, Wade Keith
• Granted Patent: US 8,229,108 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: H04L 9/0668 producing a non-linear pseudorandom sequence

Abstract

One or more methods and systems of generating pseudo-random numbers that are used as encryption keys in cryptographic applications are presented. In one embodiment, a method of generating pseudo-random numbers is performed by sampling output sequences of a linear feedback shift register with a specified periodicity. In one embodiment, the generating of pseudo-random numbers using linear feedback shift registers is accomplished by periodically switching between iterative outputs generated by multiple linear feedback shift registers. In one embodiment, a method of encrypting a pseudo-random number generated by a linear feedback shift register comprises using a nonlinear operator. In one embodiment, a method of further encrypting a pseudo-random number is accomplished by using a hashing function whose initial value varies over time by way of a function operating on one or more variables. In one embodiment, an apparatus for generating pseudo-random numbers using linear feedback shift registers comprises a digital hardware.

Claims

1. A method of generating pseudo-random numbers using a linear feedback shift register in which the correlation between successive pseudo-random numbers is reduced, said method comprising sampling output sequences of said linear feedback shift register with a specified periodicity.

2. The method of claim 1 wherein said linear feedback shift register generates said output sequences corresponding to maximal length sequences.

3. The method of claim 1 wherein said specified periodicity is equal to the number of bits output by said linear feedback shift register.

4. The method of claim 1 further comprising periodically switching between iterative outputs generated by two or more linear feedback shift registers.

5. The method of claim 3 further comprising periodically switching between iterative outputs generated by two or more linear feedback shift registers.

6. The method of claim 2 further comprising periodically switching between iterative outputs generated by two or more linear feedback shift registers.

14. The method of claim 4 further comprising operating a nonlinear operator on said pseudo-random number and one or more operands.

15. The method of claim 5 further comprising operating a nonlinear operator on said pseudo-random number and one or more operands.

16. The method of claim 6 further comprising operating a nonlinear operator on said pseudo-random number and one or more operands.

20. The method of claim 14 further comprising:

receiving said pseudo-random number generated from said linear feedback shift register; and

varying the initial value of said hashing function over time by way of a function operating on one or more variables.

21. The method of claim 15 further comprising:

receiving said pseudo-random number generated from said linear feedback shift register; and

varying the initial value of said hashing function over time by way of a function operating on one or more variables.

22. The method of claim 16 further comprising:

receiving said pseudo-random number generated from said linear feedback shift register; and

varying the initial value of said hashing function over time by way of a function operating on one or more variables.

7. A method of generating pseudo-random numbers using linear feedback shift registers in which the correlation between successive pseudo-random numbers is reduced, said method comprising periodically switching between iterative outputs generated by at least a first linear feedback shift register and iterative outputs generated by at least a second linear feedback shift register.

8. The method of claim 7 wherein said linear feedback shift registers comprise linear shift registers capable of generating maximal length sequences.

9. The method of claim 7 wherein said pseudo-random numbers are generated with period equal to the sum of each of the individual linear feedback shift register periods.

10. The method of claim 8 wherein said pseudo-random numbers are generated with period equal to the sum of each of the individual linear feedback shift register periods.

18. The method of claim 7 further comprising:

receiving said pseudo-random number generated from said linear feedback shift register; and

varying the initial value of said hashing function over time by way of a function operating on one or more variables.

19. The method of claim 18 wherein said one or more variables comprises the configuration of feedback taps associated with said linear feedback shift register.

11. A method of encrypting a pseudo-random number generated by a linear feedback shift register comprising operating a nonlinear operator on said pseudo-random number and one or more operands.

12. The method of claim 11 wherein said nonlinear operator comprises an XOR function.

13. The method of claim 12 wherein said one or more operands comprises one operand comprising a unique bit sequence corresponding to the LFSR currently used to generate said pseudo-random number.

17. A method of further encrypting a pseudo-random number generated from a linear feedback shift register by using a hashing function comprising:

receiving said pseudo-random number generated from said linear feedback shift register; and

varying the initial value of said hashing function over time by way of a function operating on one or more variables.

23. An apparatus comprising digital hardware for generating pseudo-random numbers using a linear feedback shift register in which the correlation between successive pseudo-random numbers is reduced.

24. The apparatus of claim 23 wherein said digital hardware comprises flip-flops and gates.