Method for post-processing an output of a random source of a random generator

Abstract

A method and an assemblage for post-processing an output of a random source of a random generator are presented. In the method, an output signal of the random source is compressed, thereby yielding a sequence of compressed signal values that are checked in terms of their distribution.

Claims

1. A method for post-processing an output of a random source of a random generator, the random source outputting a digital output signal having a bit width of at least one bit, comprising: compressing, via a circuit, the output signal; and performing a blockwise linear logical combination of n successive bits of the output signal in a context of the compression, wherein n is a compression factor, with a result that a compressed output signal is generated that encompasses a sequence of compressed signal values, checking, via a checking device, the sequence of compressed signal values by a distribution test in terms of a distribution of the sequence.

2. The method as recited in claim 1, wherein the compression factor n is influenced as a function of the result of the distribution test.

3. The method as recited in claim 1, wherein the random source includes a ring oscillator that encompasses a ring-shaped interconnection of an odd number of inverting elements, the ring oscillator being sampled with a sampling clock at at least one sampling point.

4. The method as recited in claim 3, wherein a frequency of the sampling clock is influenced as a function of the result of the distribution test.

5. The method as recited in claim 3, wherein a frequency of the ring oscillator is influenced as a function of the result of the distribution test.

6. The method as recited in claim 5, wherein a frequency of the ring oscillator is influenced by selecting a number of inverting elements.

7. The method as recited in claim 5, wherein a frequency of the ring oscillator is influenced by modifying operating conditions.

8. The method as recited in claim 1, wherein the output signal of the random source includes a plurality of bits, and wherein at least two of the bits are combined by way of a linear operation into one bit that is correspondingly compressed by blockwise XORing of n successive bits, yielding a compressed bit sequence, and the compressed bit sequence is tested with regard to its distribution.

9. The method as recited in claim 1, wherein the output signal of the random source includes at least k bits, each of said k bits being equipped with a circuit for processing the output signal, the corresponding compressed k bits constituting an assignment having 2.sup.k possible values, and an occurrence of all the 2.sup.k possible values being counted in separate counters, and a frequency of occurrence of all the assignments are mutually compared.

10. An assemblage for post-processing an output of a random source of a random generator that outputs a digital output signal having a bit width of at least one bit, the assemblage comprising: a circuit configured to compress the output signal, a blockwise linear logical combination of n successive bits of the output signal being performed in a context of the compression, n being a compression factor, with a result that a compressed output signal is generated which encompasses a sequence of compressed signal values; and a checking device with which the sequence of compressed signal values is checked in terms of a distribution of the sequence.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows an embodiment of a ring oscillator.

(2) FIG. 2 shows an embodiment of the assemblage together with the ring oscillator of FIG. 1.

(3) FIG. 3 shows a further embodiment of the assemblage.

DETAILED DESCRIPTION

(4) The invention is schematically depicted in the drawings on the basis of embodiments, and will be described in detail below with reference to the drawings.

(5) FIG. 1 shows an embodiment of a ring oscillator as a random source, labeled in its entirety with the reference number 10. Ring oscillator 10 has a NAND element 14 and eight inverters 18, and thus nine inverting elements. Ring oscillator 10 thus has an odd number of inverting elements and three pickoffs or sampling points.

(6) Ring oscillator 10 can be started and stopped with a first input 20. The sampling rate is defined via a second input 28. The depiction furthermore shows a first sampling point 22, a second sampling point 24, and a third sampling point 26. This means that beginning from first sampling point 22, a sampling action always occurs after an odd number of inverting elements. This is not absolutely necessary, however, for the method presented.

(7) First sampling point 22 is sampled using a first flip-flop 30, yielding the sampled value s10. Second sampling point 24 is sampled using a second flip-flop 32, yielding the sampled value s11. Third sampling point 26 is sampled using a third flip-flop 34, yielding the sampled value s12. First flip-flop 30 has a further, fourth flip-flop 40 associated with it. This performs a memory function, and outputs the value s10′ that follows the value s10 in time, i.e. s10 and s10′ are chronologically successive sampled values of first sampling point 22. Correspondingly, second flip-flop 32 has associated with it a fifth flip-flop 42 that outputs s11′, and third flip-flop 34 has associated with it a sixth flip-flop 44 that outputs s12′. Flip-flops 40, 42, and 44 are suitable for resolving metastable states of flip-flops 30, 32, and 34. Metastable states arise from the fact that a switchover of the signal at input 28 occurs during an edge at the respective sampling point 22, 24, 26. Flip-flops 30, 32, and 34 then require a certain time until a stable final state is reached. In the present example, that time is guaranteed by the fact that it is not until the next active edge of the signal at input 28 that the now-stable value of flip-flops 30, 32, and 34 is transferred into flip-flops 40, 42, and 44. Flip-flops 30, 32, 34, 40, 42, and 44 serve as memory elements in accordance with claim 1.

(8) Ring oscillator 10 can thus in principle be constructed from, for example, nine inverters 18. One of these inverters 18 can be replaced by NAND element 14 in order to allow ring oscillator 10 to be stopped. Alternatively, this NAND element 14 can also be replaced by a NOR element.

(9) In the embodiment shown, the values of ring oscillator 10 are stored simultaneously, each in one flip-flop (FF) 30, 32, 34, at three different inverters. These pickoffs are intended to be distributed as regularly as possible over the elements of ring oscillator 10. For the case of nine inverting stages in ring oscillator 10, a pickoff or a sampling point 22, 24, 26 is therefore provided after each three inverting elements. As already mentioned, however, this is not necessary for the method presented. It is also possible to provide a pickoff again after an even number of inverting elements.

(10) The number of inverter stages in ring oscillator 10 determines the frequency of the oscillator, and should therefore be selected so that the flip-flops can store the respective signal value. If an oscillator frequency that is as high as possible is used, the probability of being in the vicinity of an edge when sampling is higher. The number of inverters in the oscillator ring is therefore selected to be as small as possible, but still large enough that the flip-flops are functional for the frequency attained. For a 180-nm technology, a frequency of approximately 1 GHz for ring oscillator 102 having nine inverters 18 was determined by simulation. The flip-flops can store the signal values at this frequency, as has been demonstrated.

(11) The method presented can be carried out with ring oscillator 10 according to FIG. 1 that has an odd number of inverting elements, values being picked off at at least one sampling point of the ring oscillator.

(12) A correlation with the system clock and thus with the sampling clock cycle obtained therefrom can be identified for ring oscillator 10. For this, a comparison is made as to whether the three bit values at the output of flip-flops 30, 32, and 34 are identical to those at the output of flip-flops 40, 42, and 44. Not all correlations can be identified here by comparing s10, s11, s12 to s10′, s11′, s12′, even if the divisor value of the frequency divider is divisible by the number of inverting elements in the oscillator ring. It can happen that after a respective arbitrary (optionally constant) number of sampling actions, sampling keeps occurring at the same position in the oscillator cycle. If that number is not simultaneously a divisor of the number of inverting elements in the oscillator, the comparison described above does not yield any information as to the correlation that exists. It is nevertheless possible to identify the correlation when all the samples are compared with the current sample. This is, however, very laborious.

(13) For the ring oscillator in accordance with FIG. 1 having, for example, nine inverters and three sampling points, the bit values stored at the sampling points generally change by at least one bit value after not too large a number of samples. A large number of successive identical bit values is detected by counting warnings, and either a fault is signaled or an influence is exerted on the frequency of the oscillator.

(14) For the ring oscillator according to FIG. 1, nine inverters and three sampling points are provided. In a first flip-flop that is connected to one sampling point of the oscillator, the states of the oscillator at the sampling point are stored. The second row of successive flip-flops is suitable for compensating for metastable states in the respective first flip-flops. Metastable states of this kind can arise from the fact that the sampling clock rate becomes active precisely during a state transition of the oscillator. Storing the state again in the respective second flip-flop ensures that the state of the first flip-flop can settle, over one period of the sampling clock rate, before that stable value is transferred into the second flip-flop. If this structure is realized in balanced fashion, a desired behavior can be achieved. This balancing requires the use of special gates, however, namely inverters and flip-flops, that possess sufficiently identical driver strength for the low-high and high-low edge, including for the internal nodes of the flip-flops. In addition, the layout must be constructed so that identical load capacitances exist for all pickoffs of the ring oscillators and their controlling nodes. For a balanced circuit according to FIG. 1, for example, the bit assignments 000 and 111 do not occur.

(15) In a test chip in this case, gates of a standard digital library were used. The ring oscillator can additionally have one more pickoff to which an amplifier is connected for frequency measurement purposes. In the context of measurements on this test chip, it was possible to ascertain that the predicted distribution of the output bits is not correct. The values 000 and 111 do both occur. It was additionally ascertained that the distribution of the remaining six states does not occur in equally distributed fashion even when the sampling frequencies are varied. It was found in particular that in the test chip in question, the number of sampled values having decimal values 3, 5, and 6 of the three sampled bits is appreciably higher than that of 1, 2, and 4.

(16) It was found that when a post-processing is performed in which the three output bits are XORed with one another, a 0 occurs as a result much more often than a 1. This bias in the zero-to-one distribution should in fact be avoided, or at least corrected by suitable post-processing. The sequence of random bits thereby obtained is also referred to as an “internal random sequence,” which should exhibit an equal distribution of 0 and 1 (see: Killmann, W., Schindler, W.: AIS 31, Version 1, BSI of Sep. 25, 2001). If a distribution of this kind of the internal random sequences is not possible, a complex structure that generates random numbers from the internal random sequences is also permissible as post-processing. Because such structures possibly effect a distortion that simply conceals the true (i.e. insufficient) behavior, particular testability is required even after post-processing if the test of the internal random sequences was not successful. This certification mode necessary for this purpose is described, for example, in the document DE 60 2004 011 081 T2. If such a test is passed, the post-processing structure is then therefore regarded as suitable, and the tests with regard to equal distribution of 0 and 1 can also be demonstrated on the output data of said complex post-processing structure.

(17) The result of the method described is to eliminate such a structure, and in particular the certification mode. This is possible if the internal random sequences already exhibit the required properties. For this, for example, a simple compression is already performed bitwise before the individual bits are further processed. The circuit of FIG. 2 proposes a compression, using a respective serial XOR, before the value is stored in the second flip-flop.

(18) FIG. 2 shows an assemblage 45 having ring oscillator 10 of FIG. 1, a first XOR element 50, a second XOR element 52, and a third XOR element 54 being provided. With these, a bitwise compression is performed. They thus constitute a circuit 47 for compression. The compressed values are inputted into second flip-flops 40, 42, and 44. The outputs thereof are labeled s10″, s11″, and s12″ (s1i″). Flip-flops 30, 32, and 34 serve as memory elements whose outputs s10, s11, and s12 are post-processed.

(19) Once the sampled values of ring oscillator 10 have each been stored in one of first flip-flops 30, 32, and 34, each individual bit s1i is, in a second step, XORed with the respective output of one of second flip-flops 40, 42, and 44. A compression is thereby achieved by allowing the value of s1i to enter, for example, n times into the value of s1i″.

(20) Second flip-flop 40, 42, and 44 at the same time also performs the task of taking into account metastable states in the respective first flip-flop 30, 32, and 34, by the fact that an entire sampling period is available for that labile state to settle. The degree of compression n should be selected to be sufficient that the prescribed zero-to-one distribution is achieved for each individual bit. Further processing of the bits can be accomplished using additional post-processing structures that do without a certification mode. For this, the three bits can be antivalently combined with one another, for example XORed, or can also be incorporated in parallel fashion into a post-processing structure. It is advantageous if the compression factor n is, if at all possible, odd. The result is that n successive zeros yield a different bit value (0) than n successive ones (1). It could furthermore be useful if n is a prime number, since the compression then cannot be assembled from a sum of multiple compressions.

(21) The bitwise serial XOR operation on the one hand achieves the objective of eliminating unequal zero-to-one distributions, and on the other hand entropy (the random value) is enriched by the compression.

(22) The improved distribution of 0 and 1 is determined by the magnitude of the compression factor n. A larger n as a rule yields a more equal distribution.

(23) At the same time, consideration must be given to how much entropy the sampled values contain. The amount of jitter present at the sampling point in time plays a role here. The jitter can be calculated as

(24) $\begin{array}{cc}{\sigma }_{\Delta T}=\sqrt{\frac{8}{3\eta }}\sqrt{\frac{V_{\mathrm{DD}}}{V_{\mathrm{Char}}}\frac{k_{B}T}{P}}\sqrt{\Delta T}& \left(1\right)\end{array}$
in which, for short-channel transistors,

(25) $\begin{array}{cc}{V}_{\mathrm{Char}}=\frac{3}{8}\left(\frac{V_{\mathrm{DD}}}{2}-V_T\right),& \left(2\right)\end{array}$
wherein furthermore k.sub.B=Boltzmann constant (1.38*10.sup.−23 J/K) η=technology constant of the switching elements used (typically ≈1) V.sub.DD=operating voltage of the oscillator (e.g. 1.8 V) T=temperature (e.g. 298 K) P=power consumption of the oscillator V.sub.T=threshold voltage of the transistors in the oscillator ΔT=time span between two sampling actions σ.sub.ΔT=standard deviation of the jitter.

(26) In order to calculate the entropy, it is assumed that in a region of ±1.299 σ.sub.ΔT around an oscillator edge, the entropy value is 0.5, and outside that region the value is assumed to be 0. If it is then assumed that the samples are uniformly distributed over the oscillator period if the oscillator frequency and sampling frequency are not oscillating with one another, one then obtains an entropy value in accordance with the proportion of the region of ±1.299 σ.sub.ΔT and the corresponding number of edges to be taken into account in proportion to the oscillator period. For a doubling of the sampling period this entropy value will assume a value √2=1.414 times greater, since the jitter increases by a factor of 1.414 according to the equation above. There is only one sampled value in the same time period, however, while prior to the doubling the sampling period had two sampled values.

(27) If the entropy for a single sampling period is equal to x, it is then 2*x for two samples. A doubling of the sampling period, however, yields a value of only 1.414*x for the entropy in the same time period.

(28) It is therefore more favorable to select the sampling period not to be too long, and conversely to compress more sampled values, i.e. an n as high as possible. On the other hand, however, it can also be unfavorable to compress too many sampled values with the XOR according to FIG. 2, since entropy values can then compensate for one another. It is noteworthy that an even number of entropy values of “1” cancel each other out in the context of XOR compression. Experimental investigations have shown that a compromise for the sampled values can exist for n between a few tens and a few hundreds to a few thousands. In this case the sampling frequencies were between 300 kHz and 12.5 MHz at an oscillator frequency of close to 1 GHz. The internal random sequences thereby obtained already passed the generally acknowledged statistical tests without utilizing additional post-processing.

(29) It can therefore be claimed that a ring oscillator is constructed from standard digital elements, namely inverters or inverting elements and a NAND or NOR to stop the oscillator. It can also be claimed that the digital standard design flow can be used for the design of the ring oscillator and for the sampling flip-flops, since no manual intervention in the layout is required. In the test chip in this case, not only were the digital elements very asymmetrical in terms of their driver effect with regard to the edges, but the capacitive load on the ring oscillator was also very differently distributed as a result of the connection of an amplifier for frequency measurement. All of this no longer had a disadvantageous influence on the statistical tests after XOR compression in a context of suitable parameters. The conditions of the tests can be met without additional complex structures for post-processing. For this, the three compressed signals can be XORed with one another (antivalence) or operating on using another linear function, e.g. equivalence, and this output signal is further processed.

(30) In a further embodiment, the output bits of the three sampling flip-flops can also be linearly combined with one another even before XOR compression, for example using XORs (antivalence) or also equivalence operators (XNOR).

(31) A device 49 for checking the compressed signal values in terms of their distribution is furthermore provided. The aforementioned XORing of the three compressed bits can also, for example, occur in this device 49, an output bit of the random generator being generated in each case.

(32) FIG. 3 shows a random generator 55 as a possible embodiment of the assemblage presented, having ring oscillator 10 and having a first XOR element 60 with output s01, a second XOR element 62 with output s012, and a third XOR element 64. Also provided is a second flip-flop 70 that outputs s012″. XOR elements 60, 62, and 64 constitute a circuit 57 for compression. A device 59 for testing a distribution is also depicted.

(33) The advantage of this embodiment is that only one signal now needs to be serially compressed by XOR. To be noted, however, is the fact that the properties of the circuit can no longer be evaluated as effectively as when the three compressed signals are preset. Because of the linearity of the XOR operations, the output signals of FIG. 2 and FIG. 3 are identical when the three output signals of FIG. 2—s10″, s11″, and s12″—are XORed to yield one signal s012″:
s012″=s10″⊕s11″⊕s12″.
Assuming
s10″=s10(0)⊕s10(1)⊕s10(2) . . . ⊕s10(n−1)
s11″=s11(0)⊕s11(1)⊕s11(2) . . . ⊕s11(n−1)
s12″=s12(0)⊕s12(1)⊕s12(2) . . . ⊕s12(n−1),
the equation above becomes
s012″=s10(0)⊕s10(1) . . . ⊕s10(n−1)⊕s11(0)⊕s11(1) . . . ⊕s11(n−1)⊕s12(0)⊕s12(1) . . . ⊕s12(n−1),
and according to FIG. 3:
s012=s10 ⊕s11 ⊕s12
and
s012″=s012(0)⊕s012(1)⊕s012(2) . . . ⊕s012(n−1)
the equation above becomes
s012″=s10(0)⊕s11(0)⊕s12(0)⊕s10(1)⊕s11(1)⊕s12(1) . . . s10(n−1)⊕s11(n−1)⊕s12(n−1).

(34) Because of the commutative antivalence law, according to which the operands can be arbitrarily interchanged, the two equations for s012″ are identical.

(35) A TRNG can be realized as intellectual property (IP) with the method presented. A product is referred to as IP when it provides a circuit description, together with tests, in such a way that a customer of said product is capable of realizing the circuit on a chip with the customer's own technology. Because of the extraordinarily low complexity in terms of circuit engineering, namely approximately 200 gate equivalents, it is usable practically everywhere randomness plays a role.

(36) The invention can moreover be employed in sensor evaluation systems for manipulation protection or in security applications where such TRNGs are connected to the Internet.

(37) Also presented is a circuit assemblage having at least one ring oscillator that encompasses a ring-shaped interconnection of an odd number of inverting elements, said ring oscillator being sampled at one or more sampling points or positions, the sampled values being stored in memory elements simultaneously with a sampling clock, the outputs of the memory elements being connected to an input of a linear logic element.

(38) Also presented is a circuit assemblage having a random source having at least one digital output signal having a bit width of at least one bit, and a having circuit for compressing said output signal, the circuit performing a blockwise XORing of n bits of each bit of the output signal to yield one respective bit of a compressed output signal, and the sequence of compressed signal values thus constituted being tested in terms of their distribution. The blockwise XOR operation means that n successive bits are respectively serially XORed with one another. The distribution test can be performed for each individual output bit according to FIG. 2 or for the combined output bit according to FIG. 3, for example in such a way that a number of zeros and ones in said bit sequence is counted and these count values are compared with one another. This comparison can be accomplished, for example, by calculating a difference between the two count values, a check being made as to whether the difference exceeds a defined maximum value. The comparison can also be made with fixed bounds.

(39) The circuit assemblage can be notable for the fact that as a function of the result of the distribution test, influence is exerted on the compression factor n.

(40) The random source can furthermore contain at least one ring oscillator that is made up of an annular interconnection of an odd number of inverting elements, said ring oscillator be sampled at at least one position using a clock.

(41) Depending on the result of the distribution test, influence can be exerted on the frequency of the sampling clock.

(42) In addition, as a function of the result of the distribution test, influence can be exerted on the frequency of the ring oscillator, for example by way of the number of inverting elements in the ring oscillator or by modifying the operating conditions of the oscillator (operating voltage, temperature).

(43) The output signal of the random source can be made up of multiple bits, and at least two of said bits are grouped together by a linear operation into one bit that is correspondingly compressed by blockwise XORing of n bits, and the compressed bit sequence is tested in terms of its distribution.

(44) The output signal of the random source can be made up of at least k bits that are not logically combined with one another, and each of these k bits is equipped with a circuit for processing the output signal; the correspondingly compressed k bits form an assignment having 2.sup.k possible values, and the occurrence of all these 2.sup.k possible values is counted in separate counters, and the frequency of occurrence of all these assignments are mutually compared.

(45) A distribution test may be accomplished, for example, by counting the occurrence of the bit value 0 and the bit value 1 in separate counters for m compressed output bits, and the comparison may be accomplished by calculating the difference between those counter values and comparing the difference to see whether it exceeds a defined bound.

(46) The number of inverting elements in the ring oscillator can be modified as follows:

(47) a) Generic approach for synthesis with a variable number of inverters (can be used only in a FPGA after re-synthesis; fixed in an ASIC).

(48) b) Equip the structure of the ring oscillator with inverters that in part can be bypassed, under the control of a control signal. This additional circuit amplifies the unequal capacitances of the nodes in the ring oscillator. This does not have a disadvantageous effect, however, if the compression factor and/or sampling frequency is/are correspondingly varied in such a way that the out-of-balance condition thereby caused is compensated for.

(49) A modification of the operating conditions of the oscillator can be provided, for example, by:

(50) a) modifying the operating voltage by way of a separately controllable supply voltage, or by way of series resistors in the power supply to the ring oscillator,

(51) b) modifying the operating temperature using heating or cooling elements that are selectably switched in.

(52) A mutual comparison means, for example, that the largest and the smallest number of an assignment are identified by a larger/smaller comparison, for example a) by checking whether a difference becomes negative, or b) by sorting the assignment values (bitwise decision beginning from the MSB; at the first deviation at a bit position, the value having a 1 at that location is larger than the other),

(53) and then calculating the difference between the largest and smallest value, which is in turn compared with a fixed bound.