Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-09-21
2001-02-20
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S253000
Reexamination Certificate
active
06192385
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention claims priorities from Japanese Patent Applications No. 9-276517 filed Sep. 24, 1997 which is incorporated herein by reference.
1. Field of the Invention
The present invention relates to a pseudorandom number generating method and a pseudorandom number generator.
2. Description of the Related Art
A technique for operating a clock signal supplied to one pseudorandom number generator circuit dependently upon a pseudorandom number generated by another pseudorandom number generator circuit has been generally used since the mechanical cryptography in the World War II. Further, it is described in a book “Fundamental Cryptography” of Masataka Kato who was a specialist in the cryptographic field of the Imperial Army of Japan, which was published in 1989 by Science Ltd., that high quality pseudorandom number can be generated by thinning an output of an M series generator. However, there has been a problem that it is difficult to theoretically analyze a pseudorandom number generator which operates a clock signal, except a pseudorandom number generator (
FIG. 1
) constructed with “a plurality of cascade-connected linear feedback shift registers (LFSR's), particularly, LFSR's called M series generators”, which will be described later.
However, such conventional pseudorandom number generator has the lock-in problem and, in order to prevent a cryptanalysts utilizing the lock-in phenomenon, a large number of LFSR's must be cascade-connected.
The lock-in problem means that, when a clock control signal generated on the basis of pseudorandom numbers generated by an initial stage LFSR is used, there may be a case where no clock is supplied to a next stage LFSR in a period of a plurality of successive clocks and, therefore, operations of the remaining LFSR's are stopped, resulting in that the pseudorandom number output from the pseudorandom number generator during that period is fixed to the same value.
This problem and other matters related thereto are described in detail in, for example, Dieter Gollmann and William G. Chambers, “Clock-Controlled Shift Registers, A Review”, IEEE Journal on Selected Areas in Communications, Vol. 7, No. 4, pp. 525-533, May 1989 and Bruce Schneier, “Applied Cryptography: Protocols, Algorithms and Source Code in C”, 2nd Edition, John Wiley & Sons, 1996.
FIG. 1
is a functional block diagram showing a basic construction of the conventional pseudorandom number generator having, as pseudorandom number generating circuits thereof, a plurality of cascade-connected orderly linear feedback shift registers (LFSR's). As shown in
FIG. 1
, the pseudorandom number generator includes a plurality (n) of m-bit LFSR's, where n and m are positive integers, respectively. When a value of a control signal L supplied to the respective LFSR's
902
through an input terminal
104
is logical “0” and a clock signal CLK is supplied from an i-th logical sum (OR) circuit
901
to an i-th LFSR
902
, the i-th LFSR
902
holds a train of m bits of a train of (n×m) bits supplied to the i-th LFSR
902
through an input terminal
105
, where i is a positive integer up to n. On the other hand, when the control signal supplied to the input terminal
104
is logical “1”, the i-th LFSR
902
shifts the m-bit content thereof and outputs a pseudorandom number Xi (1 bit), every clock pulse of the clock signal which is an output of the i-th OR circuit
901
.
An i-th Exclusive OR circuit
802
receives the pseudorandom number X
i
from the i-th LFSR
902
and a pseudorandom number Y
i−1
from a (i−1)th Exclusive OR circuit
802
and outputs a pseudorandom number Y
i
to a (i+1)th LFSR
902
as a clock control signal and to an (i+1)th Exclusive OR circuit
802
. The last Exclusive OR circuit
802
outputs a pseudorandom number Y
n
to an output terminal
106
as an output of this pseudorandom number generator.
The i-th OR circuit
901
receives the clock signal CLK from the input terminal
103
and the clock control signal Y
i−1
and outputs a logical sum thereof Therefore, when the logical value of the clock control signal Y
i−1
is “0”, the i-th OR circuit
901
outputs the clock signal supplied from the input terminal
103
as it is. On the contrary, when the logical value of the clock control signal Y
i−1
is “1”, the clock signal supplied from the input terminal
103
is blocked by this OR circuit
901
.
Therefore, when the clock signal is supplied from the input terminal
103
while the logical value of the clock control signal Y
i−1
is “0”, the content of the i-th LFSR
902
is updated. However, when the logical value of the clock control signal Y
i−1
is “1”, the content of the i-th LFSR
902
is not updated even if the clock signal is supplied from the input terminal
103
.
Incidentally, the clock control signal Y
0
is a predetermined constant and it may be, for example, Y
0
=0.
Now, a conventional pseudorandom number generator circuit used to constitute the pseudorandom number generator shown in
FIG. 1
will be described in detail.
FIG. 2
is a functional block diagram showing an example of a basic construction of the conventional pseudorandom number generating circuit. In
FIG. 2
, a register
205
is responsive to a clock signal CLK from an input terminal
315
to hold a data of m bits output from a selector
204
as a data representing the state of its content and simultaneously supply the data thus held to a function generator circuit
202
. The function generator circuit
202
converts the m-bit data supplied from the register
205
in a manner predetermined for the m-bit data to generate a data of (m+1) bits by adding 1 bit to the m-bit data. Further, the function generator circuit
202
supplies m bits of the (m+1)-bit data to the selector
204
and outputs the remaining 1 bit from an output terminal
317
as pseudorandom numbers.
The selector
204
selects and outputs the m-bit data supplied from an input terminal
313
when a logical value of the control signal L supplied from an input terminal
314
is “0” and selects and outputs the m-bit data supplied from the function generator circuit
202
when the control signal L is logical “1”.
In a usual operating state of this pseudorandom number generating circuit, the function generator circuit
202
converts, in the above described manner, the data supplied from the register
205
and representing a current state of the content of the register
205
and outputs the converted data to the selector
204
. The register
205
takes in and holds the converted data supplied from the selector
204
every time when the clock pulse of the clock signal CLK is input. Therefore, the internal state of the register
205
is changed every clock pulse and the function generator circuit
202
generates pseudorandom numbers dependently on the changed internal state of the register
205
and outputs the pseudorandom numbers through the terminal
317
.
FIG. 3
is a functional block diagram showing a basic construction of the conventional pseudorandom number generating circuit which is specifically called “non-linear feedback shift register”. In
FIG. 3
, components which are the same as those shown in
FIG. 2
are depicted by the same reference numerals, respectively, without detailed description thereof.
The pseudorandom number generating circuit shown in
FIG. 3
differs from the pseudorandom number generating circuit shown in
FIG. 2
in construction of the function generator circuit
202
. That is, the function generator circuit
202
of the pseudorandom number generating circuit shown in
FIG. 3
is constituted with a function generator circuit
401
and a shifter
402
.
The function generator circuit
401
functions to output a 1-bit data for an input m-bit data and the output data of the function generator circuit
401
is supplied to the shifter
402
and is output through the output terminal
317
as pseudorandom number.
The shifter
402
derives left side (m−1) bits of the m-bit data
Foley & Lardner
Mai Tan V.
NEC Corporation
LandOfFree
Pseudorandom number generating method and pseudorandom... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pseudorandom number generating method and pseudorandom..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pseudorandom number generating method and pseudorandom... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2569202