JP3606418B2 - Random number generator - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a random number generation device, and more particularly to a device that generates challenge data used for authentication between devices using a challenge and a response.
[0002]
[Prior art]
As an authentication method between two devices connected via a communication path, a one-way authentication method using an encryption technique described in the international standard ISO / IEC 9798-2 is usually used.
When a certified device is called a prover and a device that authenticates a prover is called a certifier, this authentication method informs the key itself that the prover has the same secret data as the certifier called the authentication key. It is based on proof to the certifier. For this purpose, first, the certifier selects some data (challenge data) and throws it to the prover. On the other hand, the prover possesses a certain cryptographic conversion and encrypts the challenge data using the authentication key. The encrypted data is returned to the authenticator as a response. The authenticator who has received this response shares the authentication key with the decryption conversion which is the reverse conversion of the encryption conversion, and decrypts the response by the decryption conversion using the authentication key. If this result matches the challenge data, the prover is authenticated as valid.
[0003]
The challenge data in this authentication method is data of a relatively long bit length (n bits: currently 60 bits or more), and it is necessary to be able to take 2 ^ n (2 to the power of n) values as randomly as possible. It is. This is an attack (hereinafter referred to as “table attack”) in which a communication path between devices is monitored (wiretapping) and all combinations of challenges and responses are exploited in a table and used as a fake response to subsequent challenges. ).
<First Conventional Example>
An example of a method for generating challenge data is a method using a counter. An n-bit counter is provided, which is counted up and used for every authentication. The advantage of this method is that as long as the counter continues to operate, the challenge data is guaranteed to be different for each authentication. It cannot be abused to counterfeit the response to the challenge. However, in order to secure this method, a counter having a bit length as long as n bits is required. Further, when applied to an actual device, it is necessary to realize that the contents are not erased even if the counter is turned off.
<Second Conventional Example>
An example of another generation method of challenge data is shown in Japanese Patent Publication No. H8-292931. In this method, the counter is operated in a free run, and is converted and used by a fixed random number generation calculation program during authentication. This is a method utilizing the fact that authentication between actual devices is performed at random timing. If this method is used, even if the counter is reset when the power is turned off, if the timing of use is arbitrary (random), more types of values can be taken as challenge data than in the first conventional example.
[0004]
However, even in this case, the counter needs to have a length of n bits. This is because if the counter is short, the same value is output many times as the counter output, and the table attack is established.
<Third conventional example>
Further, a method of replacing the counter in the second conventional example with a linear feedback shift register (LFSR) that generates an M-sequence in code theory, for example, can be considered. The M series and the LFSR are described in detail, for example, in Hideki Imai, “Code Theory”, edited by the Institute of Electronics, Information and Communication Engineers 1990. This is a method in which the LFSR is operated in a free run, this is stopped at the time of authentication, and challenge data having a required bit length is output from that state.
[0005]
Thereby, unlike the counter in the second conventional example, by keeping the inside of the LFSR secret, it is difficult to predict the next challenge data, and the safety is improved.
However, in order to generate 2 ^ n kinds of challenge data, an LFSR of n bits or more is required. This is because the number of possible value types of the LFSR is the number of possible value types of the output n bits of the random number generation device. For example, when the output of a 20-bit LFSR is 80 bits, the number of types of values that can be taken by this output is not 2 ^ 80 but only 2 ^ 20. In order for the challenge data to take 2 ^ 80 values, it is necessary to provide an 80-bit LFSR.
[0006]
[Problems to be solved by the invention]
As described above, in the above prior art, an n-bit counter and random number generating means are required to generate challenge data that can take 2 ^ n values randomly. In other words, large-scale hardware or software is required to generate secure challenge data suitable for authentication. This hinders product downsizing and authentication circuit LSIs.
[0007]
Therefore, the present invention has been made in view of such a point, and an object thereof is to provide a random number generation device for generating challenge data that can be realized on a small scale.
The “random number” here does not require that the next challenge data cannot be predicted. It is important that the challenge data can take as many values as possible (maximum 2 ^ n ways). Specifically, it aims at providing the random number generator which satisfy | fills the following conditions.
(1) Output data consisting of n bits can take 2 ^ n values.
(2) It can be realized with small hardware.
(3) It is desirable that the next challenge data is not predicted from one challenge data. It is desirable that the inside of the random number generator is not analyzed from the output value.
[0008]
[Means for Solving the Problems]
In order to achieve the above object, the present invention provides a random number generator for generating an n-bit random number, which holds the random number. n-bit Generated by the holding means, a random number generating means for generating a k-bit random number smaller than n, and an instruction to generate a new random number. k-bit random number At least part of Of the holding means n-bit The storage means for storing in part and storing the value obtained by reusing the last random number held in the holding means in the remaining part of the holding means, and the value stored in the holding means by the storage means Output means for outputting as a new random number.
[0009]
Thus, a random number generation device that generates 2 ^ n kinds of challenge data is realized with a small circuit.
Here, the random number generation means is a k-bit free-run counter, the holding means is a first-in first-out queue buffer such as a shift register, or the number of random digits stored in the holding means is variable. The random number generated by the random number generation means is stored in the holding means after being subjected to a certain conversion, reused after being subjected to a certain conversion on the immediately preceding random number, the holding means It is also possible to output a value obtained by performing a certain conversion on the value stored in, as a new random number.
[0010]
As a result, a more compact random number generation device can be realized, or the confidentiality of the next generated random number can be increased.
[0011]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, a random number generation device according to the present invention will be described in detail with reference to the drawings.
(Embodiment 1)
FIG. 1 is a block diagram illustrating a configuration of a random number generation device according to the first embodiment.
The random number generation device is a random number generation device that generates 64-bit challenge data, and includes a control unit 10, a counter 11, and four shift registers 12a to 12d.
[0012]
The counter 11 is a 16-bit free-run counter in which the terminal C15 is the MSB and the terminal C0 is the LSB, and increments by one at a constant frequency since the power is turned on.
Each of the four shift registers 12a to 12d is a 16-bit shift register having a parallel output terminal, and shifts one bit to the right when one clock signal is input to the clock terminal. These are connected in series to form a 64-bit shift register, that is, a first-in first-out queue buffer, which holds challenge data. The shift register 12a has parallel input terminals connected to the outputs C0 to C15 of the counter 11, and takes in the count values C0 to C15 of the counter 11 at that moment when a set signal is input.
[0013]
The control unit 10 performs control for generating new challenge data, receives the request from the outside, outputs a set signal to the shift register 12a, and outputs a clock signal to the four shift registers 12a to 12a. Or output to 12d.
Next, the operation of the random number generation device configured as described above will be described.
FIG. 2 is a flowchart showing the operation of the control unit 10.
[0014]
When receiving a signal requesting new challenge data from the outside (step S20), the control unit 10 outputs 16 clock signals to each of the four shift registers 12a to 12d (step S21). As a result, the 64-bit challenge data stored in the four shift registers 12a to 12d is shifted 16 bits to the right. That is, the upper 48 bits R16 to R63 of the old challenge data are shifted downward by 16 bits and moved to the lower 48 bits R0 to R47 of the new challenge data.
[0015]
Subsequently, the control unit 10 outputs a set signal to the shift register 12a (step S22). As a result, the value of the counter 11 at the moment when the set signal is output is input in parallel to the shift register 12a. That is, the value of this counter becomes the upper 16 bits R48 to R63 of the new challenge data.
As described above, the random number generation device generates 64-bit new challenge data in which the new value from the counter 11 is the upper 16 bits and the upper 48 bits of the immediately previous challenge data is the lower 48 bits.
[0016]
Note that this random number generation device utilizes the fact that authentication between devices is performed at random times. That is, since a challenge data request is generated at an arbitrary (random) timing, the value input in parallel from the counter 11 to the shift register 12a can take 2 ^ 16 values. Then, considering that the values stored in the other shift registers 12b to 12d are values previously stored in the shift register 12a, the entire 64-bit shift registers 12a to 12d are 2 ^ 64. It can take street values.
[0017]
Further, the four shift registers 12a to 12d are used not only for generating challenge data, but also functioning as output registers of the present apparatus.
Therefore, it can be said that this apparatus is a random number generation apparatus that generates 64-bit challenge data using only one 16-bit counter 11. Thereby, an apparatus for generating a large random number with a small hardware scale is realized.
(Embodiment 2)
Next, a random number generation device according to Embodiment 2 will be described.
[0018]
The present embodiment is a random number generation device that generates 64-bit challenge data as in the first embodiment. However, unlike the first embodiment in which the upper 16 bits are constantly updated, the number of upper bits to be updated is variable. It is characterized by doing. The description will focus on the differences from the first embodiment.
FIG. 3 is a block diagram illustrating a configuration of the random number generation device according to the second embodiment. The same components 11, 12a to 12d as those in the random number generation device of the first embodiment are denoted by the same reference numerals.
[0019]
In the random number generation device, one shift register 12e is further added to the first embodiment, and the control unit 10 of the first embodiment is replaced with a new control unit 13.
The new shift register 12e has the same function as the shift register 12a of the first embodiment, is connected in series to the upper digits of the four shift registers 12a to 12d in the first embodiment, and receives a set signal when it receives a set signal. The count value from 11 is input in parallel.
[0020]
The control unit 13 includes an effective digit detection unit 13a in addition to the functions of the control unit 10 of the first embodiment. The significant digit detection unit 13a detects the number of significant digits of the count value of the counter 11 (which is equal to the value input in parallel to the shift register 12e) when the control unit 10 issues a set signal. Here, the effective digit means a digit excluding reading zero. For example, when the count value is “0001011100101101”, 13 digits excluding the leading three digits of reading zero are effective digits.
[0021]
Unlike the first embodiment in which the control unit 10 always issues 16 clock signals each time a new challenge data request is received, the control unit 10 generates clock signals corresponding to the number of effective digits detected by the effective digit detection unit 13a.
FIG. 4 is a flowchart showing the operation of the control unit 10.
When a new challenge data request is received from the outside (step S30), first, a set signal is issued to the shift register 12e (step S31). As a result, the 16-bit count value from the counter 11 is input to the shift register 12e in parallel and is also taken into the effective digit detection unit 13a.
[0022]
Then, the valid digit detection unit 13a detects the number of valid digits of the count value (step S32).
Finally, the control unit 10 outputs a clock signal corresponding to the number of significant digits detected by the significant digit detection unit 13a to the six shift registers 12a to 12e (step S33). As a result, the old challenge data stored in the four shift registers 12a to 12d is shifted to the right by the number of digits corresponding to the number of clocks to become new challenge data.
[0023]
As described above, according to the random number generation device according to the present embodiment, the number of digits of the new count value stored above the old challenge data is variable (random), and therefore the number of digits is fixed. Compared to 1, prediction of new challenge data becomes more difficult.
(Embodiment 3)
Next, a random number generation device according to Embodiment 3 will be described.
[0024]
This embodiment is a random number generation device that generates 64-bit challenge data as in the first embodiment, but unlike the first embodiment in which the count value from the free-run counter is directly input to the upper digits of the old challenge data, The count value is inputted after being converted.
Figure 5 These are block diagrams which show the structure of the random number generator which concerns on Embodiment 3. FIG. The counter 11 has the same function as that of the first embodiment.
[0025]
When the set signal is input, the data converter 15 takes in the count value of the counter 11 at that moment and performs a certain conversion.
FIG. 6 is a diagram illustrating an example of the conversion logic of the data converter 15.
The data converter 15 includes a key data storage unit 1520 and 15 exclusive OR units 1500 to 1515. The input count value C0 to 15 and a 16-bit secret stored in the key data storage unit 1520 in advance. The key data F0 to F15 are exclusive ORed for each bit, and the result is output as new 16-bit data D0 to D15.
[0026]
Each of the four registers 16a to 16d is a 16-bit parallel input / output register, which holds 64-bit challenge data, and constitutes a pipeline. That is, when one clock signal is input, the value of the upper register (or data converter 15) is fetched. That is, it can be said that the total 80-bit holding means composed of the data converter 15 and the four registers 16a to 16d constitutes an 80-bit shift register that shifts downward by 16 bits at a time.
[0027]
The control unit 14 corresponds to the control unit 10 of the first embodiment, and performs the following control.
When a signal for requesting new challenge data is received from the outside, first, a set signal is output to the data converter 15. As a result, the value of the counter 11 at the moment when the set signal is output is taken into the data converter 15 and converted.
[0028]
Next, the control unit 14 outputs one clock signal to the four registers 16a to 16d. As a result, the four registers 16a to 16d capture 16-bit data stored in the immediately preceding upper data converter 15 and registers 16a to 16c, respectively.
As a result, the count value from the free run counter 11 is converted by the data converter 15 and then stored in the upper 16 bits R48 to R63 of the new challenge data, and the upper 48 bits R16 to R63 of the old challenge data are 16 bits lower. Is shifted to the lower 48 bits R0 to R47 of the new challenge data. As a result, new challenge data R0 to R63 are generated in the four registers 16a to 16d.
[0029]
As described above, in the first embodiment, when the time from when the old challenge data is requested to when the new challenge data is requested (increment number in the free-run counter 11) is known, it is stored in the upper 16 bits of the new challenge data. Although there is a weak point that the value is known, in this embodiment, since the secret data converter 15 is inserted between the counter 11 and the register 16a, the prediction of the value becomes more difficult. .
(Embodiment 4)
Next, a random number generation device according to Embodiment 4 will be described.
[0030]
The present embodiment is a random number generation device that generates 64-bit challenge data using four 16-bit registers 16a to 16d as in the third embodiment, but between the counter 11 and the uppermost register 16a. Instead of inserting a converter, a converter is inserted between the registers 16a to 16d.
FIG. 7 is a block diagram illustrating a configuration of a random number generation device according to the fourth embodiment.
[0031]
Unlike the third embodiment, data converters 17a to 17c are inserted between the 16-bit registers 16a to 16d and connected in series.
Each of the data converters 17a to 17c has, for example, conversion logic shown in FIG.
The four registers 16a to 16d and the three data converters 17a to 17c constitute a four-stage pipeline. That is, the top stage is a set of the register 16a and the data converter 17a, the second stage is a set of the register 16b and the data converter 17b, and the third stage is a set of the register 16c and the data converter 17c. There is a register 16d at the bottom.
[0032]
When receiving a signal for requesting new challenge data from the outside, the control unit 18 outputs one clock signal to the four registers 16a.
As a result, the four registers 16a to 16d fetch values from the upper counter 11 and the data converters 17a to 17c, respectively. Immediately thereafter, the data converters 17a to 17c are fetched to the upper registers 16a to 16c, respectively. Convert the new value.
[0033]
In this way, in this random number generation device, when a signal for requesting new challenge data is input from the outside, the count value of the free-run counter 11 is stored in the upper 16 bits R48 to R63 of the new challenge data. The upper 48 bits R16 to R63 of the old challenge data are converted in 16-bit units and then shifted to the lower 16 bits to move to the lower 48 bits R0 to R47 of the new challenge data. New challenge data R0 to R63 are generated in the registers 16a to 16d.
[0034]
As described above, the random number generation device of the present embodiment reuses the upper 48 bits of the old challenge data when generating new challenge data as in the case of the first embodiment. Since it is part of the new challenge data after the conversion in, it is difficult to understand that the previous challenge data is reused just by looking at the new challenge data.
[0035]
Note that the three data converters 17a of the present embodiment all have the same conversion logic, but they may be different. Thereby, prediction of new challenge data can be made more difficult.
(Embodiment 5)
Next, a random number generation device according to Embodiment 5 will be described.
[0036]
The present embodiment is a random number generation device including four stages of pipelines (four 16-bit registers 16a to 16d) as in the third embodiment, but a converter is provided between the counter 11 and the uppermost register 16a. In this case, a converter is placed at the output of each of the registers 16a to 16d.
FIG. 8 is a block diagram illustrating a configuration of a random number generation device according to the fifth embodiment.
[0037]
The counter 11, the control unit 18, and the four registers 16a to 16d are the same as those in the fourth embodiment.
The data converter 19 performs a certain conversion on the input 64-bit data and outputs it as new 64-bit data. For example, the data converter 15 has a configuration in which the data converter 15 shown in FIG. 6 is expanded to 64 bits. Have. However, the secret key data is set so that when the input data is divided into 16-bit blocks, the conversion for each block is different.
[0038]
When receiving a signal for requesting new challenge data from the outside, the control unit 18 outputs one clock signal to the four registers 16a.
As a result, the four registers 16a to 16d fetch values from the upper counter 11 and the registers 16a to 16c, respectively. That is, the count value of the free run counter 11 is stored in the register 16a, and the values of the upper registers 16a to 16c are stored in the three registers 16b to 16d, respectively.
[0039]
The new 64-bit data stored in the four registers 16a is converted by the data converter 19 and becomes new 64-bit challenge data.
As described above, the random number generation device according to the present embodiment has a configuration in which the data converter 19 that performs secret conversion is further added to the output of the random number generation device according to the first embodiment. Predicting difficult challenge data becomes even more difficult.
[0040]
The random number generation devices according to the first to fifth embodiments generate 64-bit challenge data including the 16-bit free-run counter 11, but the present invention is limited to such numerical values. It is not a thing. For example, it may be a random number generation device that generates 512-bit challenge data including a 32-bit free-run counter.
[0041]
The free-run counter 11 can be replaced with a 16-bit random number generator. For example, it may be realized by the LFSR of the third conventional example. This is because the gist of the present invention is not to use a free-run counter, but to generate a random number having a larger number of bits than that using a device that generates a random number having a smaller number of bits. .
[0042]
It goes without saying that the present invention can be realized not only by hardware using a logic circuit but also by software.
In addition, the random number generation device of the second embodiment has shifted the old challenge data to the right by the number of significant digits of the count value. However, the method of changing the number of digits to be shifted is not limited to this method. The hash value obtained from a certain hash function may be the number of digits to be shifted.
[0043]
In addition, the data converters 17a to 17c of the fourth embodiment may be independent or separate ones. Although the conversion logic is the same, only the secret key data stored in each key data storage unit can be different.
Furthermore, the data converters 15, 17 a to 17 c and 19 in Embodiments 3 to 5 are not limited to those that perform exclusive OR as shown in FIG. 6, but only from wiring for performing bit substitution, for example. It can also be. As a result, the circuit can be made compact and the processing speed can be increased.
[0044]
【The invention's effect】
As is apparent from the above description, the present invention is a random number generation device for generating an n-bit random number, which holds the random number. n-bit Generated by the holding means, a random number generating means for generating a k-bit random number smaller than n, and an instruction to generate a new random number. k-bit random number At least part of Of the holding means n-bit The storage means for storing in part and storing the value obtained by reusing the last random number held in the holding means in the remaining part of the holding means, and the value stored in the holding means by the storage means Output means for outputting as a new random number.
[0045]
That is, since the immediately preceding random number is reused as a part of a new random number, a random number as long as n bits can be generated by a k-bit random number generating means substantially smaller than n. This makes it possible to realize a random number generator for generating challenge data on a small scale.
Here, the random number generation means may be a k-bit free-run counter, and the storage means may store the count value of the random number generation means when the instruction is received in the holding means.
[0046]
Thereby, the k-bit random number generation means can be made compact.
The holding means may be a first-in first-out queue buffer such as a shift register, and the storage means may store the random number generated by the random number generation means in the holding means.
[0047]
Thereby, the reuse can be realized with a simple circuit.
Further, the number of random numbers stored in the holding unit by the storage unit may be variable. For example, only the significant digit portion of the random number is stored.
This makes it difficult to predict the next random number even when the time when the free-run counter is activated is known.
[0048]
The storage means performs constant conversion on the random number generated by the random number generation means, and then stores the random number in the holding means, or performs constant conversion on k-bit data shifted in the holding means. The output means can also shift the value, or the output means can perform a certain conversion on the value stored in the holding means and output it as a new random number.
[0049]
This makes it difficult to predict the next random number based on the immediately preceding random number and increases the degree of secrecy.
Therefore, according to the present invention, a random number generation device capable of generating a random number having a large number of digits with a small configuration is realized, and is particularly suitable for generating random challenge data in challenge-response type inter-device authentication. Its practical value is great.
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a configuration of a random number generation device according to a first embodiment of the present invention.
FIG. 2 is a flowchart showing an operation of the control unit 10 shown in FIG.
FIG. 3 is a block diagram showing a configuration of a random number generation device according to Embodiment 2 of the present invention.
4 is a flowchart showing the operation of the control unit 13 shown in FIG.
FIG. 5 is a block diagram showing a configuration of a random number generation device according to Embodiment 3 of the present invention.
6 is a block diagram showing a configuration of the data converter 15 shown in FIG. 5. FIG.
FIG. 7 is a block diagram showing a configuration of a random number generation device according to Embodiment 4 of the present invention.
FIG. 8 is a block diagram illustrating a configuration of a random number generation device according to a fifth embodiment of the present invention.
[Explanation of symbols]
10 Control unit
11 Free run counter
12a to 12e shift register
13, 14, 18 Control unit
13a Effective digit detector
15, 17a-17c, 19 Data converter
1500 to 1515 Exclusive OR part
1520 Key data storage unit
16a-16d registers

Claims (9)

A random number generator for generating an n-bit random number,
N-bit holding means for holding the random number;
random number generating means for generating a k-bit random number smaller than n;
When an instruction to generate a new random number is received, at least a part of the k-bit random number generated by the random number generation unit is stored in a part of the n bits of the holding unit, and the remaining part of the holding unit Storage means for storing a value obtained by reusing the immediately preceding random number held in the holding means;
A random number generation device comprising: output means for outputting a value stored in the holding means by the storage means as a new random number. The random number generating means is a k-bit free-run counter;
The random number generation device according to claim 1, wherein the storage unit stores the count value of the random number generation unit when the instruction is received in the holding unit. The holding means is a first-in first-out queue buffer,
3. The random number generation device according to claim 2, wherein the storage unit stores the random number generated by the random number generation unit in the holding unit. 4. The random number generation device according to claim 3, wherein the number of digits of random numbers stored in the storage unit by the storage unit is variable. 5. The random number generation device according to claim 4, wherein the storage unit stores a significant digit portion of the random numbers generated by the random number generation unit in the holding unit. 2. The random number generation device according to claim 1, wherein the storage means stores a predetermined conversion on the random number generated by the random number generation means and then stores the random number in the holding means. The holding means is a register that shifts in units of k bits;
2. The storage unit stores the k-bit random number generated by the random number generation unit in the holding unit and shifts the k-bit data to be shifted after performing certain conversion on the shifted k-bit data. The random number generator described. 2. The random number generation device according to claim 1, wherein the output means outputs a new random number after performing a certain conversion on the value stored in the holding means. An authentication device for authenticating the other party's legitimacy,
A new n-bit random number generated by the random number generation device according to claim 1 is used as challenge data, and the authenticity of the other party is authenticated by a challenge-response method using the challenge data.
An authentication apparatus characterized by that.

Images