Design and Implementation of a True Random …

1 Design and Implementation of a true Random NumberGenerator based on digital circuit ArtifactsMichael Epstein1, Laszlo Hars2, Raymond Krasinski1,MartinRosner3,Hao Zheng41 Philips Electronics, Philips Intellectual Property and Standards, 345 Scarborough Road,Briarcliff Manor, NY 10510{ , Technology, 1251 Waterfront Place,Pittsburgh, PA Electronics, Philips Research, 345 Scarborough Road,Briarcliff Manor, NY 286 Broadway,Pleasantville, NY are many applications for true , unpredictable Random example the strength of numerous cryptographic operations is often de-pendent on a source of truly Random numbers. Sources of Random informationare available in nature but are often hard to access in integrated circuits.}

2 Insome specialized applications, analog noise sources are used in digital circuitsat great cost in silicon area and power consumption. These analog circuits areoften influenced by periodic signal sources that are in close proximity to therandom number generator. We present a Random number generator comprisedentirely of digital circuits, which utilizes electronic noise. Unlike earlier work[11], only standard digital gates without regard to precise layout were IntroductionTrue Random - number generators are often desirable in many applications ranging fromstatistical system analysis to information security protocols and algorithms. Currentlyavailable true Random number generators utilize circuitry that often consumes signifi-cant resources on integrated circuits and/or require incompatible analog and digitalelements.

3 Other, more primitive generators do not provide a convenient interface toelectronic devices. In this paper we describe the Design of a new type of true randomnumber generator that is based solely on digital components ( it is inexpensive tobuild), consumes little power, provides high throughput, and passes the DIEHARD[15] suite of tests for randomness. It is envisioned that this Design of a Random numbergenerator will provide an inexpensive alternative to generators that are currently em-bedded in many systems such as microprocessors and smart paper introduces the concepts behind a simple true Random number focus of this paper is on digital circuits that exhibit metastability and those thatfunction as unstable oscillators.

4 Others have used metastability as a source of Random -ness and have found some success, but only after trimming devices with a laser toachieve a precisely balanced circuit . (See, [10], [11], [12]).We designed and implemented a wide array of this type of true Random numbergenerators. The prototype chip consists of nine distinct designs. The prototype chipwas mounted on an acquisition breadboard for testing. The extracted results wereanalyzed to determine which designs yield the best results. The results show that evenwithout de-biasing the resulting sequences, some of the designs provide Random data-sets that pass the DIEHARD suite of tests.

5 This paper details the methodology fordesign, Implementation and testing of a true Random number generator based on digi-tal artifacts . We conclude this paper by providing results, and outlining the necessarysteps to create practical versions of these promising Description of digital ArtifactsThe Design described in this paper yields Random results by means of digital circuitartifacts [13], [14]. The Design utilizes a pair of oscillators that are permitted to free-run. At some point, the free-running oscillators are coerced to matching states via a bi-stable device. While we believe that the circuit utilizes the metastability artifact, thisconjecture has not been proven. However, we have experimental results from a similarcircuit composed of discrete components, which does show metastability.

6 A discus-sion of the two possible causes of randomness, metastability and oscillator drift andjitter, is presented MetastabilityDigital circuits, by their nature, are designed to be predictable. If the same logic levelsin the same order are presented to digital circuit , the same result should always if the rules governing the inputs of digital circuits are violated then the re-sults can become unpredictable. In particular, the metastability phenomenon mayoccur in a digital flip-flop or in a latch. A flip-flop, which is a memory element thatcan store one bit, is one type of bi-stable device. At the heart of every flip-flop is apair of logic gates that are fed back to each other.

7 This electrical feedback is whatpreserves the logical bit stored in the circuit . If the setup and hold conditions of theflip-flop are violated [1] then the pair of gates will behave unpredictably or even oscil-late about some intermediate voltage [2]. During the oscillatory or metastable state,the output is neither a logical zero nor a logical one. After some time the oscillationswill die out and the flip-flop will settle into a logical state of a zero or a one as shownin figure are three uncertainties at work here. The first uncertainty is if the circuit willbehave normally attain a logical state after the usual delay for the flip-flop, or willthe circuit enter the metastable state [3].

8 The second uncertainty is the state that theflip-flop will settle into. The third uncertainty is the length of time that the circuit willremain metastable [1]. Some of these uncertainties have been measured [4] and mod-eled [5] for various kinds of circuitry and environmental conditions. It has also beenshown that this phenomenon cannot be avoided in any flip-flop [4], [5]. Thus, themetastability phenomenon provides a source of randomness that can be used to con-struct a true Random number generator without the need for specialized analog from metastable statedisplayed on a TDS7254 Tektronix oscilloscope usingthe P7240 active probe. The signal resolving from a metastable state was captured using infi-nite persistence in the Fast Acquisition mode [y-axis: 1volt/division with 8 divisions shown; x-axis: 2ns/division with 10 divisions shown].

9 Lower intensity (lighter traces) shows more fre-quent signal traces. Note the single trace where the signal oscillates toward zero but eventuallystabilizes at a Oscillator Drift and JitterA clock period is never a precise constant, even in highly regulated clock oscillators,such as those that utilize a crystal. Careful observation shows that the oscillating sig-nal has slight changes of phase. Such perturbations of oscillator period are calledjitter. Some components of jitter are Random [6]. Precise measurement of jitter is moreof an art that a science [7].The Design uses two free-running (without a crystal or similar reference) oscilla-tors, which are allowed to drift away from each other.

10 Such oscillators are known toexhibit a great deal of variability even over short periods of time. Thus, the differentinternal noise of the two similar oscillators (causing phase jitter, accumulated as phasedrift) can be utilized as a source of randomness. After some time the instantaneousvoltage is latched by a digital bi-stable circuit , capturing the Random Integrated circuit DesignIn order to validate these concepts,an integrated circuit containingnine distinct types (or styles) ofrandom number generators wasconstructed. Each Design utilized abi-stable device, which in mostcases contained a pair of gates toform the memory element. Giventhe obvious dependence on circuitdelayseachstyleofrandomgenerator was replicated in 15 to31 different varieties for a total gate sizes, and thusdifferent circuit delays, in pairs ofmatched or sometimes unmatchedgates in an effort to explore theentire problem space for each ofthe nine styles.