Method and system for generating a cryptographically random number stream

• US 7,502,468 B2
• Filed: 09/02/2004
• Issued: 03/10/2009
• Est. Priority Date: 09/02/2003
• Status: Active Grant

• Current Assignee: Ncipher Security Limited
• Original Assignee: nCipher Corporation Limited (Thales SA)
• Inventors: Blakley, George Robert, Herrington, Scott, Goble, Richard, Findley, Randall, Stein, Kyle
• Primary Examiner(s): COLIN, CARL G
• Application Number:
  US10/932,928
• Publication Number:
  US 20050110399A1
• Time in Patent Office: 1,650 Days
• Field of Search: 380/46, 380/262, 380/264, 380/265, 380/268
• US Class Current: 380/46
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator

Abstract

A method and system for generating a cryptographically random number stream (100) is provided. A system includes a module (102) configured to provide at least two statistically random number streams (106) and (108) and an oscillator (104) operably coupled to the module (102). The oscillator (104) is configured to operate at a frequency which varies in response to physically unpredictable events and to select a current number from one of the at least two statistically random number streams (106) and (108) based on the oscillator'"'"'s state. A process includes several steps. At least two statistically random number streams are provided (138). A current number is selected (140) from one of the at least two statistically random number streams based on the state of an oscillator operating at a frequency which varies in response to physically unpredictable events. The step of selecting (140) is repeated (142) to create the cryptographically random number stream. The number streams can be carried by signals (132), (134), and (136). An apparatus for performing the process is also disclosed.

Claims

1. A system for creating a cryptographically random number stream, comprising:

a module configured to provide at least two statistically random number streams;

an oscillator distinct from said module operably coupled to the module, wherein the oscillator is configured to operate at a frequency which varies in response to physically unpredictable events and to select a current number from one of the at least two statistically random number streams based on the oscillator'"'"'s state;

whereby the system creates the cryptographically random number stream.

2. The system of claim 1, wherein the at least two statistically random number streams are frequency-aligned with one another.

3. The system of claim 1, wherein the oscillator is further configured to periodically select the current number from one of the at least two statistically random number streams based on the oscillator'"'"'s state.

4. The system of claim 3, wherein the period of selection by the oscillator varies over time.

5. The system of claim 4, wherein the period of the selection by the oscillator is in frequency alignment with the statistically random number streams.

6. The system of claim 1, wherein the oscillator is further configured to aperiodically select the current number from one of the at least two statistically random number streams based on the oscillator'"'"'s state.

7. The system of claim 1, wherein the frequencies of the at least two statistically random number streams are identical.

8. The system of claim 1, wherein the frequency of the oscillator averages less than ½

the lesser of the frequencies of the at least two statistically random number streams.

9. The system of claim 8, wherein the frequency of the oscillator averages less than ½

and more than 1/64 the lesser of the frequencies of the at least two statistically random number streams.

10. The system of claim 1, wherein the oscillator operably coupled to the module comprises a plurality of oscillators operating at frequencies which vary in response to physically unpredictable events, wherein the oscillators of the plurality of oscillators are configured to operate collectively as the oscillator operably coupled to the module.

11. The system of claim 1, wherein the each statistically random number stream comprises a statistically random bit steam, whereby the cryptographically random number stream comprises a ayptographically random bit steam.

12. The system of claim 11, further comprising:

a combiner operably coupled with the oscillator;

a bit stream component operably coupled to the combiner and configured to provide another statistically random number stream;

wherein the component is configured to XOR a current number of the another statistically random number stream and a current number of the cryptographically random number stream output by the oscillator.

13. The system of claim 12, wherein the module comprises at least two linear feedback shift registers each having different taps and each producing one of the module'"'"'s statistically random number streams.

14. The system of claim 1, wherein the at least two statistically random number steams consist of exactly two statistically random number streams.

15. The system of claim 1,

wherein the module is configured to provide the at least two statistically random number streams at a rate of one number per clock cycle;

wherein the oscillator is configured to select the current number at a rate of one number per clock cycle; and

whereby the system creates the cryptographically random number stream at a rate of one number per clock cycle.

16. A method for creating a signal stream comprising a cryptographically random number stream, the method comprising the steps of:

providing at least two signal streams, wherein each signal stream comprises a statistically random number stream, and wherein each signal of each signal stream comprises a number of the corresponding statistically random number stream;

selecting a current signal from one of the at least two signal streams based on the state of an oscillator which is distinct from the module and which operates at a frequency which varies in response to physically unpredictable events, wherein the current signal corresponds to a current number of the statistically random number stream corresponding to the one signal stream; and

repeating the step of selecting to create a signal stream comprising the cryptographically random number stream.

17. The method of claim 16, wherein the step of providing at least two signal streams comprises the step of:

providing at least two frequency-aligned signal streams, wherein each signal stream comprises a statistically random number stream, and wherein each signal of each signal stream comprises a number of the corresponding statistically random number stream.

18. The method of claim 16, wherein the step of repeating comprises the step of:

repeating at a fixed frequency the step of selecting to create the signal stream comprising the cryptographically random number stream.

19. The method of claim 16, wherein the step of repeating comprises the step of:

repeating at a varying frequency the step of selecting to create the signal stream comprising the cryptographically random number stream.

20. The method of claim 16, wherein the step of providing at least two signal streams comprises the step of:

providing at least two identical-frequency signal streams having, wherein each signal stream comprises a statistically random number stream, and wherein each signal of each signal stream comprises a number of the corresponding statistically random number stream.

21. The method of claim 16, wherein the step of selecting comprises the step of:

selecting the current signal from one of the at least two signal steams based on the state of the oscillator operating at the frequency which varies in response to physically unpredictable events, the oscillator frequency averaging less than ½

the lesser of the frequencies of the at least two signal steams, wherein the current signal corresponds to the current number of the statistically random number stream corresponding to the one signal stream.

22. The method of claim 21, wherein the step of selecting comprises the step of:

selecting the current signal from one of the at least two signal steams based on the state of the oscillator operating at the frequency which varies in response to physically unpredictable events, the oscillator frequency averaging less than ½ and

more than 1/64 the lesser of the frequencies of the at least two signal streams, wherein the current signal corresponds to the current number of the statistically random number steam corresponding to the one signal stream.

23. The method of claim 16, wherein the step of repeating comprises the step of:

repeating, in frequency alignment with the signal stream having the lesser frequency, the step of selecting to create a signal stream comprising the cryptographically random number steam.

24. The method of claim 16, wherein the step of repeating comprises the step of:

repeating aperiodically the step of selecting to create a signal stream comprising the cryptographically random number stream.

25. The method of claim 16, wherein the step of providing at least two signal streams comprises the step of:

providing at least two signal streams, wherein each signal stream comprises a statistically random bit stream, and wherein each signal of each signal stream comprises a bit of the corresponding statistically random bit stream; and

whereby the cryptographically random number stream comprises a cryptographically random bit stream.

26. The method of claim 25, further comprising the step of:

XORing the selected current signal'"'"'s number with another signal stream'"'"'s current number, wherein the another signal stream comprises another statistically random bit stream;

wherein the step of repeating comprises the step of repeating the steps of selecting and XORing; and

whereby yet another signal stream is created comprising another cryptographically random bit stream.

27. The method of claim 26, wherein the step of providing comprises the step of:

providing at least two signal streams provided, respectively, by at least two linear feedback shift registers each having different taps, wherein each signal stream comprises a statistically random bit stream, and wherein each signal of each signal stream comprises a hit of the corresponding statistically random bit stream.

28. The method of claim 16, wherein the step of providing consists of the step of:

providing exactly two signal streams, wherein each signal stream comprises a statistically random number stream, and wherein each signal of each signal stream comprises a number of the corresponding statistically random number stream.

29. The method of claim 16,

wherein the step of providing comprises the step of providing at least two signal streams at a rate of one signal per clock cycle, wherein each signal stream comprises a statistically random number stream, and wherein each signal of each signal stream comprises a number of the corresponding statistically random number stream;

selecting, at the rate of one signal per clock cycle, a current signal from one of the at least two signal streams based on the state of an oscillator operating at a frequency which varies in response to physically unpredictable events, wherein the current signal corresponds to a current number of the statistically random number stream corresponding to the one signal stream; and

repeating, at the rate of one signal per clock cycle, the step of selecting to create a signal stream comprising the cryptographically random number stream.

30. A process for creating a cryptographically random number stream, comprising the steps of:

providing at least two statistically random number streams;

selecting a current number from one of the at least two statistically random number streams based on the state of an oscillator which is distinct from the module and which operates at a frequency which varies in response to physically unpredictable events; and

repeating the step of selecting to create the cryptographically random number stream.

31. The process of claim 30, wherein the step of providing comprises the step of:

providing at least two statistically random number streams which are frequency-aligned with one another.

32. The process of claim 30, wherein the step of repeating comprises the step of:

repeating at a fixed frequency the step of selecting to create the cryptographically random number stream.

33. The process of claim 30, wherein the step of repeating comprises the step of:

repeating at a varying frequency the step of selecting to create the cryptographically random number stream.

34. The process of claim 30, wherein the step of providing comprises the step of:

providing at least two statistically random number streams with identical frequencies.

35. The process of claim 30, wherein the step of selecting comprises the step of:

selecting the current number from one of the at least two statistically random number streams based on the stale of the oscillator operating at the frequency which varies in response to physically unpredictable events, wherein the frequency of the oscillator avenges less than ½

the lesser of the frequencies of the at least two statistically random number streams.

36. The process of claim 30, wherein the step of selecting comprises the step of:

selecting the current number from one of the at least two statistically random number streams based on the state of the oscillator operating at the frequency which varies in response to physically unpredictable events, wherein the frequency of the oscillator avenges less than ½ and

more than 1/64 the lesser of the frequencies of the at least two statistically random number streams.

37. The process of claim 30, wherein the step of repeating comprises the step of:

repeating, in frequency alignment with the signal steam having the lesser frequency, the step of selecting to create the cryptographically random number stream.

38. The process of claim 30, wherein the step of repeating comprises the step of:

repeating aperiodically the step of selecting to create the cryptographically random number stream.

39. The process of claim 30, wherein the step of providing comprises the step of:

providing at least two statistically random bit streams;

whereby the cryptographically random number stream comprises a cryptographically random bit stream.

40. The process of claim 39, further comprising the step of:

XORing the selected current number with another statistically random bit stream'"'"'s current number;

wherein the step of repeating comprises the step of repeating the steps of selecting and XORing; and

whereby another cryptographically random bit stream is created.

41. The process of claim 40, wherein the step of providing comprises the step of:

providing at least two statistically random bit streams, respectively, by at least two linear feedback shift registers each having different taps.

42. The process of claim 30,

wherein the step of providing consists of the step of providing exactly two statistically random number streams;

and

wherein the step of selecting consists of the step of selecting the current number from one of the exactly two statistically random number streams based on the state of the oscillator operating at a frequency which varies in response to physically unpredictable events.

43. The process of claim 30,

wherein the step of providing comprises the step of providing at least two statistically random number streams at a rate of one number per clock cycle;

wherein the step of selecting comprises the step of selecting, at the rate of one number per clock cycle, a current number from one of the at least two statistically random number steams based on the state of an oscillator operating at a frequency which varies in response to physically unpredictable events; and

whereby the step of repeating comprises the step of repeating the step of selecting to create the cryptographically random number stream at the rate of one number per clock cycle.

44. An apparatus for creating a cryptographically random number stream, comprising:

providing means for providing at least two statistically random number streams;

selecting means for selecting a current number from one of the at least two statistically random number streams based on the state of an oscillator which is distinct from said providing means and which operates at a frequency which varies in response to physically unpredictable events;

and whereby repeated operation of the apparatus creates a cryptographically random number stream.

45. The apparatus of claim 44, wherein the means for providing comprises:

means for providing at least two statistically random number streams which are frequency-aligned with one another.

46. The apparatus of claim 44, wherein the means for providing comprises:

means for providing at least two statistically random number streams with identical frequencies.

47. The apparatus of claim 44, wherein the means for selecting comprises:

means for selecting the current number from one of the at least two statistically random number steams based on the state of the oscillator operating at the frequency which varies in response to physically unpredictable events, wherein the frequency of the oscillator averages less than ½

the lesser of the frequencies of the at least two statistically random number streams.

48. The apparatus of claim 44, wherein the means for selecting comprises:

means for selecting the current number from one of the at least two statistically random number streams based on the state of the oscillator operating at the frequency which varies in response to physically unpredictable events, wherein the frequency of the oscillator averages less than ½ and

more than 1/64 the lesser of the frequencies of the at least two statistically random number streams.

49. The apparatus of claim 44, wherein the means for providing comprises:

means for providing at least two statistically random bit streams;

whereby the cryptographically random number stream comprises a cryptographically random bit stream.

50. The apparatus of claim 49, further comprising:

means for XORing the selected current number with another statistically random bit stream'"'"'s current number;

whereby repeated operation of the apparatus creates another cryptographically random bit stream.

51. The apparatus of claim 44,

wherein the means for providing consists of a means for providing exactly two statistically random number streams;

and

wherein the means for selecting consists of a means for selecting a current number from one of the exactly two statistically random number streams based on the state of an oscillator operating at a frequency which varies in response to physically unpredictable events.

52. The apparatus of claim 44,

wherein the means for providing comprises a means for providing at least two statistically random number streams at a rate of one number per clock cycle;

wherein the means for selecting comprises a means for selecting, at the rate of one number per clock cycle, a current number from one of the at least two statistically random number streams based on the state of an oscillator operating at a frequency which varies in response to physically unpredictable events; and

whereby repeated operation of the apparatus creates a cryptographically random number stream at the rate of one number per clock cycle.