Random number generator circuit

• US 4,905,176 A
• Filed: 10/28/1988
• Issued: 02/27/1990
• Est. Priority Date: 10/28/1988
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Schulz, Raymond A.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Mai, Tan Y.
• Application Number:
  US07/264,467
• Time in Patent Office: 487 Days
• Field of Search: 366/717, 380/46, 331/78
• US Class Current: 708/252
• 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: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators

Abstract

A very large scale integrated (VLSI) compatible, random number generator which is highly invulnerable to cryptographic attack. The invulnerability to cryptographic attack is based upon a low frequency sampling of the output of a pseudo-random number generator which is operated at a varying frequency from a free-running ring oscillator. In a first embodiment, a free-running ring oscillator is used to drive a sampled linear feedback shift register. The asynchronous, serial pseudo-random number output from the linear feedback shift register is sampled periodically, thereby introducing randomly occurring deviations from the pseudo-random number sequence. A variation of the free-running ring oscillator is employed as the pseudo-random number generator, by introducing into the feedback loop of the ring oscillator, an exclusive OR circuit which is connected so that the ring oscillator thereby produces a serial, pseudo-random number sequence. Additional uncertainty in the sequence of random numbers produced by the free-running pseudo-random number generator, is caused by the race condition which occurs at the inputs to the exclusive OR connected in the circuit.

Claims

1. A random number generator circuit, formed on an integrated circuit chip, said chip having power supply voltage which randomly varies with respect to time, comprising:

a plurality of n delay stages serially connected in a sequence with a feedback input at a first stage in said sequence and a feedback output at a last stage in said sequence, each stage including at least two inverter circuits, each inverter circuit having a power supply input terminal;

an exclusive OR circuit coupled in a feedback path between said feedback output of said last stage and said feedback input of said first stage;

said plurality of n delay stages being divided into a first subplurality of i stages, having a first output coupled as a first input to said exclusive OR circuit;

said plurality of n delay stages having a second subplurality of n minus i stages in said plurality of stages, with said feedback output coupled as a second input to said exclusive OR circuit;

said exclusive OR circuit generating a pseudo-random signal pattern at the output thereof in response to inputs from said first and second subpluralitys of delay stages;

each said delay stage in said plurality of n delay stages propagating signals which traverse consecutive ones of said delay stages, each said delay stage applying a randomly varying magnitude of signal propagation delay to said signals in response to said randomly varying power supply voltage applied to said delay stages, resulting in randomly occurring race conditions between said first and second inputs of said exclusive OR circuit;

said exclusive OR circuit randomly changing said pseudo-random signal pattern in response to said randomly occurring race conditions, and;

a sampling circuit having an input connected to said feedback output of said second subplurality of stages, for periodically sampling the binary state at said feedback output of said second subplurality of stages;

whereby said sampling circuit outputs a pseudo-random signal pattern which randomly changes with time.

2. The apparatus of claim 1, wherein said sampling circuit samples at a frequency whose period is longer than the duration required for a signal to propagate through said n delay stages.

3. A random number generator circuit, formed on an integrated circuit chip, said chip having power supply voltage which randomly varies with respect to time, comprising:

a plurality of n delay stages serially connected in a sequence with a feedback input at a first stage in said sequence and a feedback output at a last stage in said sequence, each stage including at least two inverter circuits, each inverter circuit having a power supply input terminal;

an exclusive OR circuit coupled in a feedback path between said feedback output of said last stage and said feedback input of said first stage;

said plurality of n delay stages being divided into a first subplurality of i stages, having a first output coupled as a first input to said exclusive OR circuit;

said plurality of n delay stages having a second subplurality of n minus i stages in said plurality of stages, with said feedback output coupled as a second input to said exclusive OR circuit;

said exclusive OR circuit generating a pseudo-random signal pattern at the output thereof in response to inputs from said first and second subpluralities of delay stages;

each said delay stages in said plurality of n delay stages propagating signals which traverse consecutive ones of said delay stages, each said delay stage applying a randomly varying magnitude of signal propagation delay to said signals in response to said randomly varying power supply voltage applied to said delay stages, resulting in randomly occurring race conditions between said first and second inputs of said exclusive OR circuit;

said exclusive OR circuit randomly changing said pseudo-random signal pattern in response to said randomly occurring race conditions, and;

a sampling circuit having an input connected to the output of said second subplurality of stages, for periodically sampling the binary state at the output of said second subplurality of stages;

whereby said sampling circuit outputs a pseudo-random signal pattern which randomly changes with time.

4. The apparatus of claim 3, wherein said sampling circuit samples at a frequency whose period is longer than the duration required for a signal to propagate through said n delay stages.

5. A random number generator circuit, formed on an integrated circuit chip, said chip having a power supply voltage which randomly varies with respect to time, comprising:

a free-running ring oscillator, having a plurality of inverter circuits connected in cascade and having an output, each inverter circuit having a power supply input terminal;

a feedback shift register having a plurality of n delay stages serially connected in a sequence with a feedback path, each stage having a clock input connected to said output of said ring oscillator, said stages being divided into a first subplurality of i stages, having an output coupled as a first input to an exclusive OR device;

said feedback shift register having a second subplurality of n minus i stages in said plurality of stages, with an output coupled as a second input to said exclusive OR circuit;

a sampling circuit having an input coupled to said feedback path, for periodically sampling the binary state of a pseudo-random signal pattern output by said exclusive OR circuit;

each said inverter circuit in said ring oscillator propagating an oscillator signal which traverses consecutive ones of said inverter circuits, each said inverter circuit applying a randomly varying magnitude of signal propagation delay to said oscillator signal in response to said randomly varying power supply voltage applied to said inverter circuits, resulting in an oscillator signal output from said ring oscillator with a randomly varying frequency;

said sampling of said pseudo-random signal pattern by said sampling circuit randomly changing in response to said randomly varying ring oscillator frequency; and

whereby said sampling circuit outputs a pseudo-random signal pattern which randomly changes with time.

6. The apparatus of claim 5, which further comprises:

said sampling circuit having an input connected to the output of said second subplurality of stages, for periodically sampling the binary state at the output of said second subplurality of stages;

whereby said sampling circuit outputs a pseudo-random signal pattern which randomly changes with time.

7. The apparatus of claim 6, wherein said sampling circuit samples at a frequency whose period is longer than the duration required for a signal to propagate through said n delay stages.

8. The apparatus of claim 5, which further comprises:

said sampling circuit having an input connected to the output of said exclusive OR circuit, for periodically sampling the binary state at the output of said exclusive OR circuit;

whereby said sampling circuit outputs a pseudo-random signal pattern which randomly changes with time.

9. The apparatus of claim 8, wherein said sampling circuit samples at a frequency whose period is longer than the duration required for a signal to propagate through said n delay stages.