Apparatus and method for generating a random bit sequence

• US 8,410,857 B2
• Filed: 07/30/2009
• Issued: 04/02/2013
• Est. Priority Date: 09/22/2008
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Dichtl, Markus, Meyer, Bernd
• Primary Examiner(s): Gannon, Levi
• Application Number:
  US13/119,765
• Publication Number:
  US 20110163818A1
• Time in Patent Office: 1,342 Days
• Field of Search: 331/57, 331/78, 380/46, 380/47, 708250-256, 714/728, 714/739
• US Class Current: 331/57
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

An apparatus for generating a random bit sequence has a ring oscillator which includes inverting digital devices and on which an oscillator signal can be tapped. An intermediate storage element monitors and stores fluctuating levels of the oscillator signal. At least two controllable switch devices for simultaneously exciting at least two harmonic wave edges of the ring oscillator are provided in a signal path of the ring oscillator. The phasing of the two harmonic wave edges and a potential convergence thereof are subject to statistical fluctuations, which are used as a basis for the random bit generation. A corresponding random number generator can be used in particular as an FPGA for security applications, such as cryptographic methods. The apparatus has substantially digital components, which are easy to produce in a standardized manner. A dedicated regulating circuit is not necessary. The apparatus is also robust toward exterior influences.

Claims

1. An apparatus for generating a random bit sequence comprising

a ring oscillator with a plurality of inverting digital devices and on which an oscillator signal can be tapped,

a buffer element for storing levels of the oscillator signal, and

at least two controllable switching devices provided in a signal path of the ring oscillator for simultaneously exciting at least two harmonic wave edges of the ring oscillator, the at least two harmonic wave edges forming the oscillator signal.

2. The apparatus according to claim 1, wherein the ring oscillator including as inverting digital devices an even number of serially connected inverters.

3. The apparatus according to claim 1, wherein the controllable switching devices being embodied as logical gates.

4. The apparatus according to claim 1, further comprising the buffer element registering and storing a number of at least one of rising and falling oscillator-signal edges.

5. The apparatus according to claim 4, further comprising a control device tapping a logical level of a random bit at an output of the buffer element, generating the start signal for generating a plurality of random bits, and feeding out the plurality of random bits as a random bit sequence.

6. The apparatus according to claim 1, further comprising a control device generating a start signal for the controllable switching devices and buffer element in such a way that every controllable switching device will in each case generate a harmonic wave edge of the oscillator signal and the buffer element will be reset.

7. The apparatus according to claim 1, wherein in each case an equal number of inverting digital devices being provided between the controllable switching devices.

8. The apparatus according to claim 1, wherein the controllable switching devices in a first switching state blocking oscillating of the ring oscillator and in a second switching state opening a signal path that includes the inverting digital devices.

9. The apparatus according to claim 1, wherein the inverting digital devices and controllable switching devices being integrated as at least two cyclically connected logical gates.

10. The apparatus according to claim 9, wherein a delay device being connected between an input of a logical gate and an output of the respectively other logical gate.

11. The apparatus according to claim 1, further comprising a second buffer element coupled to the ring oscillator in such a way that parasitic influences of the buffer elements will be symmetric with respect to the inverting digital devices.

12. The apparatus according to claim 1, wherein the buffer element being embodied as a flip-flop.

13. The apparatus according to claim 1, wherein the apparatus being embodied as an FPGA.

14. The apparatus according to claim 1, wherein the controllable switching devices being embodied as AND gates or OR gates.

15. A method for generating a random bit sequence comprising the steps:

providing a ring oscillator that includes digital switch elements;

exciting at least two harmonic wave edges of the ring oscillator, which harmonic wave edges form an oscillator signal that fluctuates between two predefined logical levels;

tapping the oscillator signal; and

determining a random bits as a function of a number of level crossings of the oscillator signal within a predefined period of time.

16. The method according to claim 15, wherein the predefined period of time being selected such that the harmonic wave edges will converge within the predefined period of time and cause the ring oscillator to oscillate in a stable manner.

17. The method according to claim 15, wherein the random bit being determined by counting at least one of rising and falling oscillator-signal edges within the predefined period of time.

18. The method according to claim 17, wherein a number of signal edges undergoing a modulo operation.

19. The method according to claim 15, wherein a plurality of random bits that supply a random bit sequence or binary random number being successively determined.

20. An apparatus for generating a random bit sequence comprising

a ring oscillator with a plurality of inverting digital devices and on which an oscillator signal can be tapped, wherein the inverting digital devices comprise an even number of serially connected inverters,

a buffer element for storing levels of the oscillator signal, wherein the buffer element registering and storing a number of at least one of rising and falling oscillator-signal edges,

at least two controllable switching devices provided in a signal path of the ring oscillator for simultaneously exciting at least two harmonic wave edges of the ring oscillator, the at least two harmonic wave edges forming the oscillator signal, and

a control device generating a start signal for the controllable switching devices and buffer element in such a way that every controllable switching device will in each case generate a harmonic wave edge of the oscillator signal and the buffer element will be reset.