Apparatus and method for random number generation

• US 5,434,806 A
• Filed: 01/11/1994
• Issued: 07/18/1995
• Est. Priority Date: 05/12/1992
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Hofverberg, Mikael N.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/178,255
• Time in Patent Office: 553 Days
• Field of Search: 364/717, 380/46, 331/78
• US Class Current: 708/253
• CPC Class Codes: G06F 2207/581 Generating an LFSR sequence, e.g. an m-sequence; sequence may be generated without LFSR, e.g. using Galois Field arithmetic
• CPC Class Codes: G06F 2207/583 Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

An apparatus and a method for random number generation. The apparatus includes a feedback shift register which receives signals from a first signalling device, the shift register further being connected to a t least one delay device. This or these delay device(s) deliver (each) a random number when receiving a clock signal from a second sigalling device. The first signalling device includes a fast clock and the feedback shift register is connected to the delay device(s) via at least one logical gate, the output(s) of delay device(s) being fed back to the gate(s), the second signalling device delivering clock signals originating from external events.

Claims

1. An apparatus for generating random numbers comprising:

first and second signalling devices;

at least one clocked delay device; and

a feedback shift register which receives signals from the first signalling device and which is connected to the at least one clocked delay device,

wherein the at least one clocked delay device, upon receiving a clock signal from the second signalling device, produces a random number, the first signalling device comprises a fast clock, the feedback shift register is connected to the at least one clocked delay device via at least one logical gate, an output of the at least one clocked delay device is fed back to an input of the at least one logical gate, the clock signals from the second signalling device are produced in response to events external to the apparatus, and the fast clock produces a clock signal having a frequency that exceeds a frequency of the clock signals from the second signalling device.

2. The apparatus of claim 1, wherein the clock signals from the second signalling device are produced in response to asynchronous external events.

3. The apparatus of claim 1, wherein the feedback shift register comprises a PN-register.

4. The apparatus of claim 3, wherein the at least one logical gate comprises an XOR-gate.

5. The apparatus of claim 4, wherein the at least one clocked delay device comprises a D-type flip-flop.

6. The apparatus of claim 5, wherein a data input of the at least one clocked delay device is connected to the feedback shift register via an XOR-gate, an output of the delay device is connected to an XOR-gate via a feedback loop, and the second signalling device delivers parallel clocking signals to a plurality of the clocked delay devices.

7. The apparatus of claim 1, comprising a plurality of clocked delay devices connected in parallel for generating a plurality of random numbers in parallel.

8. The apparatus of claim 7, wherein each of a plurality of bit-positions of the feedback shift register is connected to a respective logical gate, an output of each logical gate is connected to a respective clocked delay device, an output of each clocked delay device is fed back to an input of its respective logical gate, and the clocked delay devices are connected in parallel to the second signalling device for receiving signals produced in response to asynchronous external events.

9. The apparatus of claim 8, wherein the fast clock has a clocking frequency f₁ that exceeds a clocking frequency f₂ of the second signalling device, whereby the feedback shift register wraps around at least once between two consecutive clock signals from the second signalling device.

10. The apparatus of claim 9, wherein the feedback shift register is an 18-bit PN-register and f₁ is about one megahertz.

11. The apparatus of claim 8, wherein the feedback shift register, first signalling device, at least one clocked delay device, and at least one logical gate are integrated in an LSI circuit.

12. The apparatus of claim 8, wherein a data input of the at least one clocked delay device is connected to the feedback shift register via an XOR-gate, an output of the clocked delay device is connected to an XOR-gate via a feedback loop, and the second signalling device delivers parallel clocking signals to a plurality of the clocked delay devices.

13. The apparatus of claim 1, wherein the fast clock has a clocking frequency f₁ that exceeds a clocking frequency f₂ of the second signalling device, whereby the feedback shift register wraps around at least once between two consecutive clock signals from the second signalling device.

14. The apparatus of claim 1, wherein the feedback shift register, first signalling device, at least one clocked delay device, and at least one logical gate are integrated in an LSI circuit.

15. A method for generating random numbers, whereby a random number generated by one apparatus is independent of a random number simultaneously generated by another apparatus, each apparatus comprising a PN-register that receives a clocking signal from a first signalling device and that is connected to a delay device, the delay device receiving from a second signalling device an asynchronous external signal and thereupon producing a random number, comprising the steps of:

connecting a data input of the delay device to the PN-register via a logical gate;

feeding an output from the delay device back to an input of the logical gate; and

delivering signals from the first signalling device with a clocking frequency f₁ that exceeds a clocking frequency f₂ of signals delivered from the second signalling device.

16. The method of claim 15, wherein f₁ is so high that the PN-register wraps around at least once in a time between each signal delivered from the second signalling device.

17. The method of claim 15, wherein each apparatus comprises a plurality of delay devices, and the method further comprises the step of delivering clock signals to the delay devices from the second signalling device in parallel.