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.times.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.sub.i from the i-th LFSR 902 and a pseudorandom number Y.sub.i-1 from a (i-1)th Exclusive OR circuit 802 and outputs a pseudorandom number Y.sub.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.sub.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.sub.i-1 and outputs a logical sum thereof Therefore, when the logical value of the clock control signal Y.sub.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.sub.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.sub.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.sub.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.sub.0 is a predetermined constant and it may be, for example, Y.sub.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 supplied from the register 205 by shifting the m-bit data rightward by 1 bit, adds a 1-bit output data from the function generator circuit 401 to the leftmost end of the (m-1) bits and supplies a resultant m-bit data to the register 205 through the selector 204.
Therefore, the function generator circuit 202 of this pseudorandom number generating circuit shown in FIG. 3 converts a data indicative of a current internal state of the register 205 through the operations of the function generator circuit 401 and the shifter 402 and outputs the converted data to the register 205 and the register 205 takes in and holds the data output from the function generator circuit 202 through the selector 204 every time each of the clock pulses of the clock signal CLK is input in the usual operating state thereof. Therefore, the function generator circuit 202 generates pseudorandom numbers on the basis of the internal state of the register 205 which is changed every time a clock pulse is input and outputs the pseudorandom numbers through the terminal 317.
FIG. 4 is a functional block showing a basic construction of the linear feedback shift register constituting the pseudorandom number generator shown in FIG. 1. In FIG. 4, components which are the same as those shown in FIGS. 2 and 3 are depicted by the same reference numerals without detailed description thereof.
The LFSR 902 shown in FIG. 4 differs from the pseudorandom number generating circuit shown in FIG. 2 or 3 in that a function generator circuit 401 thereof is constituted with an Exclusive OR circuit 501. The Exclusive OR circuit 501 outputs an exclusive logical sum of a predetermined number of bits of the m-bit data from the register 205 to the output terminal 317 and to the shifter 402.
Therefore, the function generator circuit 202 of this pseudorandom number generating circuit also converts a data indicative of a current internal state of the register 205 by the operations of the function generator circuit 401 and the shifter 402 and outputs the converted data to the selector 204 and the register 205 takes in and holds the data output from the selector 204 every time when a clock pulse of the clock signal CLK is input in the usual operating state thereof, and, therefore, the function generator circuit 202 generates pseudorandom numbers on the basis of the internal state of the register 205 which is changed every time a clock pulse is input and outputs the pseudorandom numbers from the terminal 317.
When a period of pseudorandom numbers generated in such LFSR 902 is 2.sup.m -1, the latter LFSR is specifically called as an M series generator.
However, in the conventional pseudorandom number generator shown in FIG. 1, when the clock signal is supplied from the input terminal 103, the clock signal is blocked by the OR circuit 901 and the content of the i-th LFSR 902 is not updated if the logical value of the clock control signal Y.sub.i-1 is "1". As a result, the previously mentioned lock-in problem occurs. In order to prevent the cryptanalysts based on the lock-in phenomenon, a large number of LFSR's 902 must be cascade-connected and, therefore, the size and cost of the conventional pseudorandom number generator become considerable. When such pseudorandom number generator is designed by taking the size and cost into consideration, the performance thereof may be restricted necessarily.