Note: Descriptions are shown in the official language in which they were submitted.
CA 02445630 2003-10-27
1
Random number generator
Description
The invention concerns a method to generate random numbers, whereby the
oscillations of at least two oscillators, that are independent from one
another, are
compared. The invention also concerns an electronic equipment with a processor
and a random number generator.
From WO 97/43709 a method to generate random numbers is known, wherein a
random signal is generated by means of a stochastic random number generator.
The known random signal generator has a voltage-controlled oscillator, the
frequency control input of which is connected with a noise voltage source. On
its
output the random signal generator has an oscillator signal, the frequency of
which fluctuates about a mid-frequency in accordance with the stochastically
changing noise voltage applied to the frequency control input. In addition,
the
random generator has several dynamic flip-flops, that with their data inputs
are
connected to a ring oscillator allocated to it. In doing so, a ring oscillator
is
provided for each flip-flop, while the frequencies of these ring oscillators
differ
somewhat from one another and are greater in each case than the frequency of
the voltage-controlled oscillator of the random signal generator. The cycle
inputs
of the flip-flops are connected to the output of the random signal generator,
so
that in the case of a cycle edge of the oscillation signal of the voltage-
controlled
oscillator with its randomly changing frequency a signal value of the
individual
oscillation signal of the ring oscillators is scanned and read into the flip-
flop
allocated to the respective ring oscillator. Afterwards the signal values
temporarily
stored in the individual flip-flops are fed emitted on an output of the flip-
flop as a
binary number signal of the random number to be generated and having several
digits. The binary values of the number signals fed to the output of the flip-
flop
should be evenly distributed. The prior known random number generator has,
however, the disadvantage that it requires the installation of additional
hardware
components and has a complicated construction.
From US 4,855,690 a random number generator is known, that uses an analogue
oscillator with a triangular output signal to change the frequency of a
voltage-
Translation PCT-EP02-03574 004511996 v2.doc
CA 02445630 2003-10-27
2
controlled oscillator having a higher frequency. The output of the voltage-
controlled oscillator is resolved to generate random digital values.
From US 5,153,532 a random number generator is known, wherein separate time
signal are used with different frequencies.
The object of the invention is to find a method to generate random numbers,
that
can be employed in a conventional computer system without the use of
additional
hardware. This method should replace an electronic equipment described in the
introduction and, moreover, be able to check the quality of the random numbers
and its own operation.
In the case of a method to generate random numbers, whereby the oscillations
of
at least two oscillators, independent from one another, are compared, this
objective is achieved by that the frequency deviation, occurring during the
operation of oscillators, is used for the generation of random numbers.
Oscillators
do not have an exact constant frequency during their operation, since
frequency
deviations occur in the form of a so called flutter. The frequency deviations
of the
oscillators are also designated as drift. Based on the different drifts the
two
oscillators do not oscillate synchronously, but phase shifts occur which are
not
predictable. The frequency deviation has a natural origin, but can also be
artificially produced. Under frequency deviation the sum of the frequency
deviations of the two oscillators is understood.
In the meantime a processor has been installed in a plurality of electronic
equipment. The method according to the invention has the advantage that a
processor, already installed, can be used. Consequently no additional
hardware,
for example in the form of an additional oscillator, is required to generate
the
random numbers.
A preferred embodiment of the method is characterised in that the oscillator
or
the pulse generator of a processor is used as one of the two oscillators.
Translation PCT-EP02-03574 004511996 v2.doc
CA 02445630 2003-10-27
3
A further preferred embodiment of the method is characterised in that a real
time
clock is used as one of the two independent oscillators. Nowadays many
electronic equipment and almost every computer contains a real time clock.
Consequently, no additional hardware components are necessary for the second
oscillator either. Instead of the real time clock another, equipment-inherent
or
external oscillator may, of course, also be used.
A further preferred embodiment of the method is characterised in that in a
first
step of the method the time of the real time clock is interrogated and is
allocated
to a start value. In a second step of the method the time of the real time
clock is
interrogated again as a function of the pulse number and compared with the
starting value until the interrogated time deviates from the starting value.
The time
of the real time clock is updated at more or less regular time intervals.
After an
updating of the real time clock the interrogated time no longer concurs with
the
starting value. By means of steps 1 and 2 of the method the number of
comparisons to be carried out until the real time clock is updated, can be
determined.
A further preferred embodiment of the method is characterised in that the
number
of comparisons is used as a random number. By virtue of this it is possible to
generate random numbers with a greater entropy, that cannot be predicted with
a
justifiable effort.
A further preferred embodiment of the method is characterised in that the time
interval between two comparisons according to the second step of the method is
smaller than the reciprocal value of the sum of the relative frequency
deviations
of the two oscillators. By this it will be ensured that the time interval of
the time
interrogations is smaller than the time deviation of the oscillation period of
the
second oscillator resulting from the combined frequency deviation (drift).
Thus the
accuracy of the measuring of the time deviation of the oscillation period is
within
the unpredictable statistical fluctuation.
A further preferred embodiment of the method is characterised in that steps 1
and
2 of the method are repeated until a predetermined number of repeats are
Translation PCT-EP02-03574 004511996 v2.doc
CA 02445630 2003-10-27
4
reached. When the processor and the real time clock work synchronously, the
number of comparisons would alternate between to integers. In practice the
processor and the real time clock work, however, asynchronously. As a result
of
the unpredictable frequency deviations and the so called flutters of both
oscillators the number of comparisons varies clearly more than between two
integers. By repeating steps 1 and 2 of the method the different numbers of
comparisons between two updates of the real time are determined.
A further preferred embodiment of the method is characterised in that the
entropy
produced while generating the random numbers is calculated during the
generation of the random numbers. Within the scope of this present invention
the
term "entropy" is used as a measure of predictability of the random numbers
produced. The entropy indicates the average information contents of a
character
set. The greater the entropy, the smaller the probability that the random
numbers
produced can be predicted. By this it will be ensured that the random numbers
have a predetermined magnitude of the entropy. The entropy is preferably
calculated in accordance with the Shannon method.
A further preferred embodiment of the method is characterised in that the
processor is used also to compare the oscillations of the two oscillators.
This has
the advantage that the random numbers can be generated purely by software
without the use of further hardware.
A further preferred embodiment of the method is characterised in that the
processor is used for the calculation of the entropy produced during the
generation of the random numbers. This has the advantage that the processor,
already present, can be made use of. No additional hardware is required.
A further preferred embodiment of the method is characterised in that the
random
numbers generated are supplied as starting value to a pseudo-random number
generator. In the pseudo-random number generator, connected downstream, a
series of random numbers is deterministically produced, the initial value of
which
is unknown. By means of the pseudo-random number generator a fast
regeneration of random numbers is possible.
Translation PCT-EP02-03574 004511996 v2.doc
CA 02445630 2003-10-27
A further preferred embodiment of the method is characterised in that the
random
numbers generated are combined with one another by cryptographic methods. By
virtue of this the random numbers will be mixed to reduce a possible
undesirable
distribution of the random numbers produced.
5
A further preferred embodiment of the method is characterised in that further
random numbers, produced in a different manner, are added to the random
numbers produced. The further random numbers may be obtained, for example,
from the, task switches of the processor or from the free capacity of a fixed
disk.
A further preferred embodiment of the method is characterised in that in the
case
of the processor one deals with the processor of a particular electronic
equipment
with Internet connection, e.g. of a computer, of a telecommunication device,
in
particular of a mobile telephone, of a terminal, in particular of a multimedia
terminal, or of a car radio.
In the case of an electronic equipment with a processor and random number
generator the above stated objective is achieved by that the random number
generator operates according to one of the above described methods.
This present invention makes the production of random numbers possible from
the comparison of two oscillators purely by software, without the use of any
additional hardware. One of the oscillators is used both for the control of
the
measuring progress and for comparing the phases with the second oscillator.
Even the calculation of the entropy produced can be carried out by one of the
"oscillators". In contrast to this, in the case of a solution based on
hardware,
separate electronic sub-assemblies are used for each of these functions that
are
correspondingly connected with one another.
Moreover, the solution according to the invention has the advantage that in
contrast to a purely hardware solution, it has versatile application
possibilities.
The method can be used both is server systems and in client computers.
Moreover, the method can be particularly advantageously used in mobile
telephones.
Translation PCT-EP02-03574 004511996 v2.doc
CA 02445630 2003-10-27
6
A further advantage is that the method can be directly integrated in very high
level language, like JAVA or C++. The method can be used to produce random
numbers in any system independently from a platform. The only prerequisite,
placed on the hardware to be used, is the presence of two independent
oscillators.
The two oscillators can be integrated in the one and same equipment, but the
use
of two oscillators in separate equipment is also possible. Main fields of
application
for the method are computers and mobile telephones with Internet connection.
The random numbers produced can be used for the production of codes by
asymmetrical coding method and to start the symmetrical encoding (SSL).
Further advantages, features and details of the invention become obvious from
the following description, in which an embodiment is described in detail with
reference to the drawing. In doing so the features mentioned in the claims and
in
the description may be significant for the invention individually or in any
combination. They show in:
Fig.1 - a schematic illustration of a comparison of the oscillations of two
oscillators,
Fig.2 - a flow chart of the method of a collector for dynamic entropy, and
Fig.3 - a flow chart of the method of an embodiment of the method according to
the invention.
In Fig.1 the cycles of a processor are designated by 1. The cycles of the
processor fluctuate between zero and one. The cycles of a real time clock are
designated in Fig.1 by 2, which also fluctuate between zero and one. The
processor 1 has a clearly greater frequency than the real time clock 2. Dotted
lines 5 and 7 indicate that the real time clock 2 is updated at more or less
regular
intervals.
Translation PCT-EP02-03574 004511996 v2.doc
CA 02445630 2003-10-27
7
Arrow 10 indicates a first time interrogation, the result of which is
allocated to a
starting value. Arrows 12, 13, 15 and 16 indicate further time interrogations.
The
time interrogations 12, 13, 15 and 16 are carried out always after a certain
number of cycles of the processor. The interrogated time is compared after
each
time interrogation 12, 13, 15 and 16 with the starting value obtained from the
time
interrogation 10. In the example illustrated in Fig.1 the time interrogations
12 and
13 show that the interrogated time concurs with the starting value. However, a
comparison of the time interrogated at the time interrogation 15 does not
concur
with the starting value.
The double arrows 18, 19, 22 and 23 in Fig.1 indicate loops that are passed
through after a positive comparison. After a positive comparison, i.e. when
the
interrogated time corresponds with the starting value, a renewed time
interrogation is carried out. Arrow 25 in Fig.1 indicates the time deviation
of the
oscillation period of oscillator 2 resulting from the combined frequency
deviation.
The dotted line 27 indicates that the updating 7 of the real time clock 2 for
this
case is carried out already at 7, that the combined drift leads to a
shortening of
the oscillation period of oscillator 2. In this case the result of the time
interrogation
15 is that the interrogated time does not concur with the starting value
obtained
from 10. For the case that the combined drift would result in a lengthening of
the
oscillation period of oscillator 2, only the time interrogation 16 would
result in a
negative time comparison.
Fig.2 illustrates the flow chart of the method of a collector 29 for dynamic
entropy.
First of all in 30 a variable designated as period is set to zero. The first
time
interrogation is carried out at a time tag 32. The first time interrogation 32
in Fig.2
corresponds to arrow 10 of Fig.1. After the first time interrogation 32 a
second
time interrogation is carried out at the second time interrogation tag 34. The
second time interrogation tag 34 of Fig.2 corresponds to arrow 12 of Fig.1.
After
the second time interrogation 34 the period is increased by one. Following
this in
a comparison 38 it is checked whether the results of the time interrogations
32
and 34 concur. If that is the case, a renewed time interrogation 34 is carried
out,
as this is indicated by arrow 40. The loop 40 is repeated until the comparison
38
provides the result that the time interrogations 32 and 34 do not concur. As
it is
Translation PCT-EP02-03574 004511996 v2.doc
CA 02445630 2003-10-27
indicated by arrow 42, in the case of such a negative comparison a counter i
is
increased by one in step 44 of the method.
Fig.3 illustrates the flow chart of the method of a random number generator
50.
The start of the flow chart is indicated by a point 52. In a block 56 static
entropy is
produced and the counter i is set to zero. Corresponding to the flow chart
illustrated in Fig.2 in a block 58 dynamic entropy is produced and the counter
i is
increased. In a comparison 60 it will be checked whether the value of the
counter
i corresponds to an adjustable pre-set value.
If this is not the case, it will pass again through block 58, as this is
indicated by
arrow 62. When the value of the counter i reaches the adjustable pre-set
value,
the entropy is calculated in a block 64 and the counter i is set again to
zero. The
purpose of the loop 62 passing through l-times is to prevent the calculation
of the
entropy unnecessarily too often. The calculation 64 of the entropy is carried
out
only when it is expected that the value of the entropy is sufficiently high.
In
experimental measurings the pre-set value can be determined for a special
system.
Following this in a comparison 66 it is checked whether the entropy is greater
than a nominal value to be pre-set. If this is not the case, a return to block
56
takes place as it is indicated by arrow 68, where static entropy will be
collected
again. Within the scope of this present invention random data, present in a
computer system, tike for example the free memory, is considered as static
entropy.
When the result of the comparison 66 is that the entropy determined in 64 is
greater than a nominal value to be pre-set, a so called hash counter in a
block 70
is increased by a value and the entropy variable is set to zero. It will be
checked
in a comparison 72 whether the hash counter is greater than a pre-set value.
If
this is the case, the output of the number determined takes place, as this is
indicated by arrow 76. It the hash counter is not yet greater than a nominal
value
to be pre-set, a return to block 56 takes place, as this is indicated by arrow
74.
Translation PCT-EP02-03574 004511996 v2.doc
CA 02445630 2003-10-27
9
By setting the hash counter in 70 the data will be additionally thoroughly
mixed.
The randomness of the data is retained, but static distributions that may
occur
within the presentation of the data are thus prevented.
Translation PCT-EP02-03574 004511996 v2.doc
