US4905176A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Random number generator circuit
Assignee: International Business Machines Corp
•
Filing: 1988-10-28
•
Granted: 1990-02-27
•
Expires: 2008-10-28
Abstract
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.
Inventors
- 👤 Raymond A. Schulz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 22:26
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/58; G06F7/582; G06F7/584; G06F7/588; H; H03; H03K; H03K3/00; H03K3/84; G06F2207/00; G06F2207/58; G06F2207/581; G06F2207/583
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
323 words
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.
Claim 2
Dependent Claim
323 words
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.
Claim 3
Dependent Claim
31 words
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.
Claim 4
Dependent Claim
321 words
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.
Claim 5
Dependent Claim
321 words
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.
Claim 6
Dependent Claim
31 words
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.
Claim 7
Dependent Claim
272 words
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.
Claim 8
Dependent Claim
272 words
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.
Claim 9
Dependent Claim
53 words
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.
Claim 10
Dependent Claim
31 words
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.
Claim 11
Dependent Claim
51 words
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.
Claim 12
Dependent Claim
31 words
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.
References Cited (Backward Citations)
US3557356A
Cited
US3614399A
Cited
US3746847A
Cited
US3790768A
Cited
US4213101A
Cited
US4348597A
Cited
US4646032A
Cited
US4684903A
Cited
US4545024A
Cited
US4769777A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-02-26 | 1993-08-28 | 1994-02-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-02-26 | 1997-08-28 | 1998-02-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-02-26 | 2001-08-28 | 2002-02-27 | $7700.00 | Window Closed / Lapsed |