Method and apparatus for generating truly random numbers

• US 5,781,458 A
• Filed: 03/05/1997
• Issued: 07/14/1998
• Est. Priority Date: 03/05/1997
• Status: Expired due to Term

• Current Assignee: Transcrypt International, Inc. (JVC Kenwood Corporation)
• Original Assignee: Transcrypt International, Inc. (JVC Kenwood Corporation)
• Inventors: Gilley, James E.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/811,425
• Time in Patent Office: 496 Days
• Field of Search: 364/717.01, 364/717.02, 364/717.06, 380/46
• US Class Current: 708/255
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator

Abstract

A method and apparatus for generating truly random numbers which may be used in a cryptographic key generator is adapted to extract entropy from the output signal of an RC oscillating circuit comprised of a resistor, a capacitor, and two nand gates. The entropy data is extracted by comparing the period of a first cycle with the period of a second cycle where the first and second periods are separated by two cycles. If the compared periods are equal, the data is discarded. If the previous period is greater than the later period, a "1" is assigned to a shift register. Otherwise, a ".O slashed." is assigned to the shift register. In this way, a plurality of bits are assigned to the shift register. A routine is then called which processes the bit data to reduce any cycle to cycle data correlation.

Claims

1. A method of generating random numbers comprising the steps of:

generating a signal from an RC oscillating circuit to provide a source of entropy;

providing software which performs the processing steps of;

extracting entropy data from the signal generated by the RC oscillating circuit, and

processing the data to reduce any cycle-to-cycle data correlation.

2. The method of claim 1 wherein the RC oscillating circuit comprises two logic gates.

3. The method of claim 2 wherein the logic gates are nand gates.

4. The method of claim 2 wherein the logic gates are part of a processor.

5. The method of claim 1 wherein the step of extracting entropy data further comprises the steps of:

determining the periods of a plurality of cycles of the signal;

comparing at least two of the determined periods; and

assigning a value to a memory location based on the comparison of the at least two of the determined periods.

6. The method of claim 5 wherein the value assigned to the memory location is determined by whether the more recent of the at least two of the determined periods is greater than or less than the compared period.

7. The method of claim 5 wherein the step of comparing at least two of the determined periods is accomplished by comparing the period of the most recent cycle of the oscillating signal with the period of a preceding non-successive cycle of the oscillating signal.

8. The method of claim 7 wherein the previous non-successive cycle is two cycles prior to the most recent cycle.

9. The method of claim 1 wherein the step of extracting entropy data further comprises the steps of:

determining the frequencies of a plurality of cycles of the oscillating signal; and

comparing at least two of the determined frequencies.

10. The method of claim 1 wherein the step of processing the data further comprises the steps of:

placing the extracted entropy data into a first memory location;

providing a second memory location; and

processing the extracted entropy data and incorporating it into the second memory location.

11. The method of claim 10 wherein the processing is accomplished in a non-linear fashion.

12. The method of claim 10 wherein the processing of the extracted entropy data further comprises the steps of:

combining the data in the first memory location and the data in a portion of the second memory location; and

replacing the portion of memory in the second memory location with the combined data.

13. The method of claim 12 wherein the step of processing the data to reduce any cycle to cycle data correlation is performed once after substantially every oscillator cycle.

14. The method of claim 10 wherein the first memory location is comprised of a 32-bit shift register and the second memory location is comprised of a buffer having a plurality of 32-bits blocks.

15. A method of generating random numbers for use in a cryptographic key generator comprising the steps of:

generating an oscillating signal from an RC oscillating circuit;

determining the periods of a plurality of cycles of the oscillating signal;

comparing at least two of the determined periods;

assigning a bit value to a memory location based on the comparison of the at least two of the determined periods;

repeating the steps of comparing and assigning in order to assign a plurality of bit values to the memory location; and

processing the plurality of bit values to reduce any cycle-to-cycle data correlation to increase the randomness of the plurality of bits.

16. The method of claim 15 wherein the RC oscillating circuit comprises a resistor, a capacitor, and two digital gates.

17. The method of claim 16 wherein the two digital gates are inverting gates.

18. The method of claim 15 wherein the step of comparing at least two of the determined periods is performed without comparing periods of successive cycles.

19. The method of claim 18 wherein the compared periods are taken from cycles which are two cycles apart.

20. The method of claim 15 wherein the step of processing the plurality of bit values is accomplished using a hash routine.

21. The method of claim 15 further comprising the steps of:

providing a memory buffer;

combining the plurality of bit values in the memory location with data from a portion of the memory buffer; and

replacing the data from the portion of the memory buffer with the combined data.

22. The method of claim 21 wherein the step of processing the plurality of bit values is performed after each time that a bit value is assigned to the memory location.

23. The method of claim 21 wherein the memory buffer is comprised of a buffer having a plurality of blocks of 32-bits each, and the memory location is comprised of a 32-bit shift register.

24. An apparatus for generating random numbers comprising:

an RC oscillating circuit comprising a resistor, a capacitor, and two logic gates for creating a digital signal having a period for each cycle of the digital signal;

a processor for performing the processing steps of;

(a) determining the period of a first cycle,

(b) determining the period of a second cycle,

(c) determining the difference between the determined periods of the first and second cycles,

(d) assigning a bit to a memory location with the value of the bit being dependent on the determined difference,

(e) repeating steps (a) through (d) for a plurality of cycles, to assign a plurality of bits to the memory location, and

(f) processing the plurality of bits in the memory location to reduce and correlation between successive bits.

25. The apparatus of claim 24 wherein the two logic gates are comprised of nand gates.

26. The apparatus of claim 24 wherein the processor is a digital signal processor.

27. The apparatus of claim 24 further comprising a memory buffer containing data, wherein the step of processing the plurality of bits is accomplished by combining the assigned plurality of bits in the memory location with at least some of the data in the memory buffer and placing the combined data into the memory buffer.

28. The apparatus of claim 24 wherein the first and second cycles are non-successive cycles.

29. The method of claim 28 wherein the first cycle precedes the second cycle by two cycles.