Device and method for generating a random number and random element for use in the same

FIELD OF THE INVENTION

The invention relates to a device and a method for generating a random number and to a random element for use in said device and said method.

BACKGROUND OF THE INVENTION

Random Number Generators (RNGs) are an essential part of many security systems and protocols. For instance, they enable the following cryptographic primitives: random nonces in challenge-response protocols, randomized encryption schemes (e.g.

ElGamal, Paillier), secret sharing, and key generation. In all these applications it is of the utmost importance for the generated numbers to be completely unpredictable. Any degree of predictability, however small, may give an attacker a fatal advantage. In fact, a sequence of numbers is considered to be a random sequence in the mathematical sense only if it is impossible to predict any given number in the sequence even if all preceding numbers are known. Furthermore, there are many non-cryptographic applications that need random input, e.g. Monte Carlo simulations. For these applications it is also desired to have a true sequence of random numbers.

PCs contain a so-called "pseudo-random number generator" (PRNG). A

PRNG produces numbers that are computed using an algorithm, hence they are deterministic. Most PRNGs are completely unsuitable for any serious cryptographic or scientific use, since the sequence starts repeating itself after a "short" period.

Devices for generating random numbers are known which rely on fundamentally irregular natural processes, such as the noise generated by an electrically resistive element (Johnson noise) or the intrinsic unpredictability of the time between decays of radioactive nuclei. Some further examples of random number generators are described, for example, by Bruce Schneier in "Applied Cryptography" (John Wiley & Sons, 1996, chapter

17.4).

A method and an apparatus for generating random numbers are disclosed in

US 2001/0046293 Al. A potential difference is applied across a liquid crystal cell to cause a

chaotic turbulent flow, and a physical property of the liquid crystal material is repeatedly measured and used to set bits for generating a sequence of random numbers.

Some Smart Cards are provided with a RNG that is based on a noisy measurement of e.g. a temperature or a resistance. The noise, which is caused by unpredictable thermal changes in the environment, is converted to a numerical value and serves as the RNG output used by the Smart Card. In the Smart Card world the usual random number generators use some active circuitry to provide a random signal. This signal is sampled and used to derive single random bits. The bits are collected and a user can request a random byte after at least eight random bits have been collected. The main disadvantage of many methods of generation random numbers, in particular of the use of noise, is that the generating rate is rather slow. Usually it takes a lot of CPU clocks before a new random bit can be retrieved. The execution time of the algorithm is limited by the speed of the RNG in the case in which a larger amount of random bytes (e.g. for blinding in cryptographic operations) is required. The above methods can be attacked, which is why random numbers must be tested. As the circuitry is an active piece of the hardware, there is the possibility to attack it such that the random numbers are not random anymore. The blinding of a cryptographic algorithm could be broken in this way. Thus, it is often preferred to carry out randomness tests continuously on-chip on the RNG. However, these optional tests of course need random numbers. Thus, these tests take very long and further slow down (cryptographic) algorithms.

A major drawback of a RNG using the time between decays of radioactive nuclei or a similar method is that special and complex equipment is needed for measuring or detecting the relevant events. This makes it difficult or even impossible to implement such a RNG in an integrated circuit for use in a commercial product. DE 103 58 392 Al discloses an assembly for generating random numbers using a computer, wherein the numbers are determined from the random bubble formation in a boiling liquid. The assembly comprises a light source, a boiling liquid, and a phototransistor. The transistor output is connected to a computer for measurement recording and random number generation. One drawback of this setup is that it cannot be used continuously since the boiling water will evaporate after some time. Furthermore, some time is needed for starting up this assembly, i.e. for heating up the water to boiling temperature. In addition, it is found to be impossible to implement this setup in an integrated circuit.

OBJECT AND SUMMARY OF THE INVENTION

It is an object of the present invention to provide a device and a method for generating a random number and a random element for use in said device and a method which provides a fast and reliable generation of a random number without the need for complex equipment and with a possible implementation into an integrated circuit.

Furthermore, it is impossible even in theory to prove that a sequence of numbers is random. It is only possible to show that it is not random. Hence, there is a small possibility that a RNG that seems to work all right is actually vulnerable to attack. It is therefore desired to find new RNG technologies. Therefore, it is a further object of the present invention to provide a device and a method for generating random numbers which are an alternative to known devices and methods.

In accordance with the above objects of the present invention, a device for generating a random number is provided, said device comprising: a random element comprising a fluid and a plurality of particles comprised in said fluid, a challenge means for providing a challenge to said random element, and a generating means for generating a random number based on a response of said random element to said challenge.

The present invention further provides a method of generating a random number by use of a random element comprising a fluid and a plurality of particles comprised in said fluid, said method comprising the steps of providing a challenge to said random element, and generating a random number based on a response of said random element to said challenge.

Still further, according to the present invention, a random element for generating a random number is provided, comprising: a fluid and a plurality of particles comprised in said fluid, wherein said random element is adapted to generate a response to a challenge provided to said random element, said random number being generated on the basis of said response.

The present invention is based on the idea that a distribution of a plurality of particles comprised (e.g. suspended) in a fluid is random. Under the provision that the system containing the particles and the fluid is a closed one, the distribution will continuously change. If each distribution can be associated with a number, the changing system will correspond to a sequence of random numbers. The distribution is easily detectable from the outside if the particles and the fluid have different values of at least one particular physical

property. The different random distributions or states of the system may be detected by measuring a response to a challenge interacting with said physical property.

Physically unclonable functions (PUFs) are known as identification means. Each PUF is unique and cannot be reproduced identically. The PUF can be measured or "challenged" - for example - by illumination (usually with a laser beam), and the PUF will provide a unique response. The response to a certain challenge, e.g. illumination pattern, is always the same for any particular PUF as long as there is no change to its composition or structure. PUFs are called physically unclonable since even a minor change to its structure leads to a significant change in the response or identification signal of this PUF, and it is accordingly impossible or at least virtually impossible (i.e. the necessary effort is too high) to "clone", i.e. copy, a given PUF.

Further details on PUFs may can be found, for example, in Pappu Srinivasa Ravikanth, Physical One- Way Functions, Doctoral Thesis 2001; US 6,584,214 Bl; P. Tuyls, B. Skoric, Secret Key Generation from Classical Physics, chapter in "AMIware: Hardware Technology Drivers of Ambient Intelligence", Philips Research Book Series, Kluwer, 2005 and B. Skoric, P. Tuyls, W. Ophey, Robust Key Extraction from Physical Unclonable Functions, Lecture Notes in Computer Science, Volume 3531, Jan 2005, Pages 407 - 422.

It is essential for the use of a PUF as an identification or authentication means that the structure of the PUF is as stable as possible. However, the random element of the present invention is comparable to an unstable PUF, i.e. a PUF which constantly or at least repeatedly changes its structure. Since the change of the random means is random, the readout of such an unstable PUF is not a constant identification code but a random number.

The term "random number" in the context of the present invention is not limited to a number in the mathematical sense. It also includes any kind of symbol, e.g. a speckle pattern resulting from an "unstable PUF". Furthermore, the term "particle" is not restricted to a piece of solid material. In the context of the present invention the particle may also be, for example, of liquid form.

According to one embodiment of the present invention, said challenge means includes a radiation source for directing a radiation beam at said random element. The radiation beam is altered upon hitting the plurality of particles. Possible interactions between the particles and the radiation beam include scattering, reflection, refraction and deflection, a result of these interactions depending on the distribution of the particles in said fluid in all cases. Thus, irradiating the random element with a radiation beam is an easy way to obtain

data depending on the instantaneous distribution of the particles in the fluid, from which data a random number can be suitably generated or calculated.

According to a preferred embodiment of the present invention, said radiation source is adapted for generating a beam of electromagnetic radiation, in particular of light. There are many well known methods and devices in the art for generating and directing electromagnetic radiation, in particular light. A path of the electromagnetic radiation beam is independent of external influences on the device. Thus, any unwanted interference from the outside of the random number generator with this part of the generation or tampering with the radiation can be reduced or even completely avoided. According to a further embodiment of the present invention, said generating means comprises a detector for detecting said response in the form of a speckle pattern. The interaction between the plurality of particles and the radiation beam may result in a response which resembles the response of a PUF to a challenge. While the PUF is intended to produce always the same response to a given challenge, the response given by the random element is unpredictable even in the case of identical challenges. However, the ways of detecting the response which are known for reading out PUFs can also be used to detect the response of the random element of the present invention.

Further details on reading out PUFs may be found, for example, in the documents cited above. These documents, in particular their passages about reading out different forms of PUFs, are incorporated by reference herein.

According to yet another embodiment of the present invention, said radiation source is adapted for generating a beam of acoustic radiation. A sound wave representing an acoustic radiation can be considered to be an alternative to the above described electromagnetic radiation. Like electromagnetic radiation, the acoustic radiation can interact with the plurality of particles, resulting in a detectable response which is dependent on the distribution of the particles in the fluid.

According to yet another preferred embodiment of the present invention, said radiation source is adapted for generating a coherent radiation beam, in particular a laser beam. A coherent radiation beam can lead to a response which results, at least in part, from an interference of parts of the radiation forming the response with other parts of that radiation. As it is known from optical PUFs that even a minor change in the configuration of the PUF will lead to a substantial change in the response, e.g. the resulting speckle pattern, the unpredictability of the random numbers generated by a device according to the present invention is even increased.

The present invention is not restricted to challenges in the form of a radiation beam. Another possible way to challenge the random element in order to produce a response is to expose the random element and the plurality of particles therein to an electric and/or a magnetic field. Since the particles and the fluid have different electric and/or magnetic properties, the overall electric and/or magnetic property of the random element depends on the distribution of the plurality of particles. This overall property may be used as a basis for generating a random number as it will change with the changing distribution. A simple way of implementing is to apply a (preferably alternating) voltage, i.e. an electric field, to said random element and to measure the capacitance of the random element.

According to a further embodiment of the present invention, therefore, said challenge means comprises a field-generating means for applying an electric and/or magnetic field to said plurality of particles, in particular for applying an alternating electric and/or alternating magnetic field. It is preferred in particular that said generating means is adapted for generating said random number on the basis of an electric and/or a magnetic characteristic of said random element, in particular on a capacitance value of said random element.

According to a preferred embodiment of the present invention, said fluid is a liquid. The purpose of providing a fluid is to allow the particles to change their location and their orientation, i.e. to allow a floating of the plurality of particles. Therefore, a gas is also suitable as a fluid for the present invention. A liquid is preferred, however, because of its better handling properties and stability.

According to another embodiment of the present invention, a density of said fluid and a density of a particle of said plurality of particles is substantially the same. The influence of gravity on the distribution of said plurality of particles is greatly reduced when the density is substantially equal for said fluid and a particle. In such a case an upward or downward drift of said particle is minimized, which may otherwise lead to an accumulation of particles and may reduce the randomness of the distribution.

According to a preferred embodiment of the present invention, said device further comprises a movement means for inducing a movement of said plurality of particles in said fluid. Moving said plurality of particles means a relative movement or change in position between different particles of said plurality of particles. As a consequence of this additional inducement of such a movement, the distribution will change and the unpredictability will increase.

According to a further preferred embodiment, said movement means comprises a heating element for heating said fluid and/or said plurality of particles. A heating of said fluid and/or of said plurality of particles may imply a temperature drop or temperature gradient within the random element. This temperature gradient may lead to a thermal convection, an unpredictable, chaotic movement of the fluid. However, it was found that an increased temperature can lead to a further randomization of the particle positions, probably due to an increased amount of Brownian motion, without the need for a temperature gradient. In cases in which the device is included as a random number generator, for instance in an integrated circuit, this integrated circuit as a whole may be considered to be a heating element if a considerable amount of the heat generated during operation of the integrated circuit reaches the device, i.e. the random element.

According to another embodiment, said movement means comprises a pump for inducing a turbulent flow of said fluid. Like the flow owing to thermal convection, a turbulent flow is unpredictable and random. The turbulent flow will swirl the plurality of particles continuously, thus randomizing it.

According to another embodiment of the present invention, the device comprises an integrated circuit providing the functionality of said generating means and of said radiation source and/or said field means, wherein said random element is attached to or included in said integrated circuit. The random number generator according to the present invention can be readily incorporated in a computer or a similar device which has a need for a true random number generator in that the elements of the device are integrated within an integrated circuit.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will now be described and illustrated in greater detail with reference to preferred embodiments and the accompanying Figures.

Fig. 1 is a schematic diagram illustrating a first embodiment of a device for generating a random number according to the present invention; Fig. 2 is a schematic diagram illustrating a second embodiment of a device for generating a random number according to the present invention;

Fig. 3 is a schematic diagram illustrating a third embodiment of a device for generating a random number according to the present invention;

Fig. 4 is a schematic diagram illustrating a fourth embodiment of a device for generating a random number according to the present invention; and

Fig. 5 is a schematic flow-chart illustrating a method of generating a random number according to the present invention.

DESCRIPTION OF EMBODIMENTS

Fig. 1 is a schematic diagram illustrating a first embodiment of a device for generating a random number according to the present invention. The device 10 comprises a random element 15, a challenge means 30, and a generating means 35. The random element 15 comprises air as a gas 20 and a plurality of particles 25. The random element 15 is connected by means of pipes 40 to a pump 45 so that a closed cycle is formed. The generating means 35 comprises a detector 50 that is connected to a calculation means 55.

The pump 45 drives air through the random element 15 and causes it to have a turbulent flow. The plurality of particles 25 in the random element 15 is suspended in said turbulent flow and thus has a chaotic and random distribution. The challenge means 30 generates a light beam 60 which is directed to said random element 15 and impinges on the plurality of particles 25. Depending on the orientation and position of the particles 25, the incident beam 60 is partly reflected. The resulting reflected beams form a response 65 to said beam 60. The reflected beam, i.e. the response, is at least partially detected by the detector 50 of the generating means 35. The detector 50 outputs a signal corresponding to the detected response to said calculation means 55, where a random number is derived from said signal. The random number is then outputted. Alternatively, the signal corresponding to the detected response of said detector 50 may be outputted as such as a random number.

The particles of the present invention are not restricted to having equal shape or size. Any suitable particle - including liquid particles - may be used, as long as there is a difference in a relevant physical property of the particle to that of the fluid.

Fig. 2 is a schematic diagram illustrating a second embodiment of a device for generating a random number according to the present invention. The device 110 comprises a random element 115, a challenge means 130, and a generating means 135 arranged on an integrated circuit 170. The random element 115 comprises a plurality of particles 125 suspended in a liquid 120. The liquid 120 is held in a container whose bottom wall is formed by a surface of the integrated circuit 170 and whose top wall is formed by a transparent cover plate 175. The challenge means 130 comprises a laser source 180 and a collimating mirror 185. The detector 150 of the generating means 135 is formed by pixel sensors of said

integrated circuit 170. Said device 110 further comprises a mirror 190 arranged above the random element 115 and the pixel sensors of the generating means 135, and a resistance element 195 of said integrated circuit 170 arranged beneath the random element 115.

The laser source 180 generates a laser beam 160 which is directed at said random element. The laser beam 160 crosses the transparent cover plate 175 and is scattered at said plurality of particles 125, resulting in a plurality of beams forming a response 165 to the challenge of the impinging beam 160. Said beams are partially reflected by said mirror 190 and result in a speckle pattern (due to interference) which is detected by said pixel sensors of said detector 150. The detected speckle pattern is used to generate a random number. In order to increase the unpredictability of the process, the liquid 120 is heated by said resistance element 195, causing a thermal convection of said liquid 120 and further disturbing said plurality of particles 125.

Fig. 3 is a schematic diagram illustrating a third embodiment of a device for generating a random number according to the present invention. The device 210 comprises a challenge means 230, a generating means 235, and a random element 210 arranged between the challenge means 230 and the generating means 235. The random element includes a liquid 220 and a plurality of particles 225. The device 210 shown in Fig. 3 is somewhat similar to an acoustic PUF. However, the plurality of particles 225 of the random element 215 is of course not fixed but may change its configuration at any time. According to the present embodiment, the response to an acoustic wave is measured and used for generating a random number. The challenge means 230 receives an electrical signal and transforms it to a mechanical vibration. This vibration propagates as a sound wave through said random element 215 and is scattered on the randomly distributed particles 225 forming inhomogeneities in the liquid 220. The response to the wave is measured by the generating means 235 by means of a further transducer and converted back into an electrical signal, which is used for generating a random number.

Fig. 4 is a schematic diagram illustrating a fourth embodiment of a device for generating a random number according to the present invention. The device 310 comprises a random element 315 which is provided with two electrodes connected to challenge means 330 comprising a voltage source 397 via an ampere meter of a generating means 335. Said random element 315 comprises a plurality of particles 325 suspended in a liquid 320. An alternating voltage is applied to said random element 315 by means of said voltage source 397, and a capacitance value of said random element 315, which is used for calculating a

random number, is obtained through a detection of the resulting alternating current by said ampere meter.

Another preferred embodiment (not shown) includes a stable current source which provides a current for an alternating charging/discharging of the capacitor formed by the random element. For obtaining a value of the capacitance for use in the generation of a random number, the time for charging and/or discharging the capacitor is measured, e.g. in terms of a clock cycle of a chip comprising the device.

Fig. 5 is a schematic flow-chart illustrating a method of generating a random number according to the present invention. In a step 410, a challenge is provided to a plurality of particles of a random element, which random element comprises a fluid in which the plurality of particles is suspended. In a following step 420, a random number is generated based on a response of said plurality of particles to said challenge. After step 420 the process may be repeated for generating further random numbers, e.g. for generating a sequence of random numbers. Although features of the above described embodiments are described in the context of the respective embodiment each time, it is to be understood that features of different embodiments may nevertheless be combined according to the present invention.

The principle of detecting the response to said challenge may be virtually the same as detecting a speckle pattern in a PUF reader. The scattering element may comprise, for example, small particles mixed in a liquid and may be called a very unstable PUF. An illumination thereof, e.g. by a laser-beam, will redistribute the particles with respect to each other, mainly owing to thermal motion. The heating may be induced by a (small) absorption of the light in the particles and/or in the liquid and/or the casing. The laser beam enters the liquid cell, where the light will be scattered by the particles and part of this scattered light will produce a speckle pattern on a camera. The heating of the liquid causes the particles to move constantly and produce a new speckle pattern on the camera. The PUF may also be heated by other means, for example if the PUF is installed on top of a silicon chip containing an integrated resistance, in that a voltage is applied to this resistance.

When the chip needs a sequence of random bits (i.e. a random number in mathematical sense) for use in a cryptographic protocol, it will irradiate the liquid with the laser and record the generated speckle pattern on the camera. Then a random bit string is extracted from the speckle pattern. This may be done by using a Fuzzy Extractor (combined with Universal Hash Functions) or by compressing the speckle pattern with an appropriate

compressing algorithm, e.g. the context tree-weighting algorithm (but an alternative compression algorithm may be used as well).

Another possible embodiment is based on an unstable "coating PUF", wherein a capacitance of a fluid cell containing random (moving) dielectric particles is measured. The present invention proposes a random element with mutually displaceable dielectric particles. For example, the particles may be provided within a suitable liquid. Such a system forms an unstable PUF. In this case, the random element response will be completely random, as it is dependent on particle distribution. The latter is variable, for example because of a thermal motion that occurs in the random element. By measuring the "unstable PUF response" and generating a bit string based on the outcome of the measurement, a true random number generator can be obtained. Preferred embodiments have additional elements for inducing motion in the liquid, such as a heating resistor provided adjacent to the liquid. An alternative way to induce a motion may employ a piezo element for "shaking" the random element.

Finally, it should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be capable of designing many alternative embodiments without departing from the scope of the invention as defined by the appended claims. In the claims, any reference signs placed in parentheses shall not be construed as limiting the claims. The word "comprising" and "comprises", and the like, does not exclude the presence of elements or steps other than those listed in any claim or the specification as a whole. The singular reference of an element does not exclude the plural reference of such an element and vice versa. In a device claim enumerating several means, several of these means may be embodied by one and the same item of software or hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.