JP4640663B2 - Secret information generating apparatus and method - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a secret information generation apparatus and method for generating secret information used for encryption communication, digital signature, and the like in the field of information security.
[0002]
[Prior art]
Conventionally, in order to prevent transmission information from being disclosed to third parties other than those concerned, encryption technology for encrypting transmission information and digital signature technology for ensuring that transmission information is not tampered with or forged are used. It is used. In addition, for example, in order to be able to confirm the legitimacy of a user who accesses a host device from a terminal device, it is generally performed that an authentication password is assigned to each user and the authentication password is requested to be input at the time of access. It has been broken. Secret information that is not known to a third party is used for the encryption key used for the encryption technology, the random number used for the digital signature technology, and the authentication password.
[0003]
Here, the problems in the above-described encryption technology, digital signature technology, and authentication password assignment will be considered. For example, consider a case where a user performs encrypted communication in a certain network. Assuming that the same common key encryption algorithm is distributed to each user in order to realize encrypted communication, in order for users to securely perform encrypted communication, specific users share them. There is a problem that the use of the encryption key by other users must be avoided.
[0004]
Also, consider a digital signature scheme that places the basis of security in a discrete logarithm problem, such as El Gamal signature. In such a digital signature method, if the combination of the same secret key and secret information is used again, the secret key is specified. Accordingly, when a certain secret key is continuously used, there is a problem that it is necessary to avoid generating a digital signature using the same secret information. This fact is described in “Douglas R. Stinson, supervised by Koichi Sakurai,“ Basics of Cryptography ”pp. 224-225, Kyoritsu Shuppan "etc.
[0005]
Further, for example, consider a case where a secret password is assigned to each user in a certain security system. In this case, there is a problem that it is necessary to avoid assigning the same password to different users.
[0006]
In the encryption technique, digital signature technique, and authentication password assignment, there are problems as described above. Therefore, in order to prevent the occurrence of these problems, secret information generally requires the following properties.
(1) The number of elements in the entire set of secret information that may be generated is very large.
(2) It is difficult to estimate the information that is the source of the secret information from the secret information.
(3) The secret information that is actually generated is less biased in the distribution of the entire set of secret information that may be generated.
[0007]
Regarding the above property (3), as a more severe condition,
(3) The secret information once generated is not generated for a predetermined period.
May be required.
[0008]
By the way, various problems in the above-described encryption technology, digital signature technology, and authentication password assignment are very small if the properties (1) to (3) required for the secret information are satisfied. . However, in order to further strengthen the system using the secret information, it is preferable to satisfy the property (3) ′, which is a more severe condition than the property (3). As a method for satisfying this property (3) ′, all the generated secret information is stored, and when the newly generated secret information matches the stored secret information, it is generated again. It is possible to fix it.
[0009]
[Problems to be solved by the invention]
However, if the property (3) ′ is to be satisfied by the above-described method, a very large storage area is required to store the secret information. There is also a problem that the procedure for keeping secret information from duplicating becomes complicated. For this reason, all the secret information generated is stored, and when the newly generated secret information matches the stored secret information, the method is not used again, that is, the secret information is generated. Satisfy the condition that secret information generated once does not need to be generated for a certain period of time without requiring many storage areas for storing information and complicated procedures to prevent duplication of secret information There is a need for an apparatus and method for generating secret information that can be used.
[0010]
The present invention solves the above-mentioned conventional problems, and its purpose is to eliminate many storage areas for storing secret information and complicated procedures for preventing secret information from being duplicated. It is an object of the present invention to provide a secret information generation apparatus and method that does not generate secret information once generated for a predetermined period.
[0011]
[Means for Solving the Problems]
In order to achieve the above object, the secret information generating apparatus of the present invention is an n-bit binary vector generating means for generating a sequence of n-bit binary vectors, wherein the value of each binary vector is varied during a period T. A binary vector bijection map generating means for sequentially inputting the generated n-bit binary vector and generating an n-bit binary vector bijective map, and the generated n A binary vector combining unit that combines m consecutive bit binary vector bijective maps, and a binary vector extracting unit that extracts a d-bit binary vector at a predetermined position in the combined m × n-bit binary vector. Extracting at least one n-bit binary vector bijection map Ete constructed.
[0012]
In this case, the n-bit binary vector generation means is a k-bit binary vector generation means for generating a sequence of k-bit binary vectors, and generates the binary vectors with different values during the period T. And means for generating an n-bit binary vector obtained by combining the k-bit binary vector and the nk-bit random number, You can also
[0013]
Further, it is preferable that the binary vector bijection map generation means can easily generate an output from an input inside the system and it is difficult to restore the input from the output outside the system.
[0014]
In addition, it is preferable that the period T in which binary vectors having different values are generated by the n-bit binary vector generating unit and the number m of binary vectors combined by the binary vector combining unit are relatively prime.
[0015]
The secret information generation method of the present invention is a procedure for generating a sequence of n-bit binary vectors, which guarantees that the values of each binary vector are generated during a period T, and A procedure of sequentially inputting the generated n-bit binary vector to generate an n-bit binary vector bijection map, and a procedure of combining consecutive m pieces of the generated n-bit binary vector bijection map And a procedure for extracting a d-bit binary vector at a predetermined position in the combined m × n-bit binary vector, and extracting so as to include at least one n-bit binary vector bijection map. It is configured with.
[0016]
In this case, the procedure for generating the sequence of n-bit binary vectors is a procedure for generating a sequence of k-bit binary vectors, and during the period T, the value of each binary vector is generated differently. And a procedure for generating an n-k bit random number, and a procedure for generating an n-bit binary vector obtained by combining the k-bit binary vector and the n-k bit random number. You can also.
[0017]
The procedure for generating the binary vector bijection map is preferably easy to generate an output from the input inside the system and difficult to restore the input from the output outside the system.
[0018]
Also, a period T in which binary vectors having different values are generated by the procedure for generating the n-bit binary vector and the number m of n-bit binary vectors to be combined by the procedure for combining the binary vectors are relatively prime. It is preferable that
[0019]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, the present invention will be described in detail based on the illustrated embodiment. FIG. 1 shows an example of a schematic configuration of a secret information generating apparatus according to the present invention. The secret information generating apparatus 2 shown in the figure includes a binary vector generating unit 4 as an n-bit binary vector generating unit, a bijection mapping generating unit 6 as a binary vector bijective mapping generating unit, and a binary vector combining unit. The binary vector combining unit 8 and a binary vector extracting unit 10 as binary vector extracting means are configured.
[0020]
The binary vector generation unit 4 sequentially generates an n-bit binary vector (bit string) g (= g (t), g (t + 1), g (t + 2),...). Generate by changing the value of each binary vector. Therefore, T consecutive binary vectors g (t), g (t + 1), g (t + 2),..., G (t + T) are all different values.
[0021]
The bijection map generation unit 6 is sequentially input with the n-bit binary vector g generated by the binary vector generation unit 4, and the n-bit binary vector bijection map f (= f (g (t)), f (G (t + 1)), f (g (t + 2)),.
[0022]
Here, the binary vector bijection map f generated by the binary vector generation unit 4 and the binary vector bijection map f generated by the bijection map generation unit 6 have a relationship of f1 ≠ f2 if g1 ≠ g2. There is a relationship that if the binary vector bijection map f is different, the original binary vector g also has a different value. In addition, it is easy to derive the binary vector bijective map f inside the system, but it is difficult to derive the original binary vector g from the binary vector bijective map f outside the system. Have
[0023]
Further, since f is a bijective map, the period of the binary vector bijective map f generated by the bijective map generation unit 6 is the period T of the binary vector g generated by the binary vector generation unit 4. Matches. Therefore, as described above, consecutive T binary vector bijection maps f (g (t)), f (g (t + 1)), f (g (t + 2)),..., F (g ( t + T)) are all different values.
[0024]
The binary vector combination unit 8 combines m consecutive n-bit binary vector bijection maps f generated by the bijection map generation unit 6 to generate an m × n-bit binary vector. The binary vector combining unit 8 generates a value of an m × n-bit binary vector by changing it with a period T / GCD (T, m) (a value obtained by dividing T by the greatest common divisor of T and m). Therefore, the continuous T / GCD (T, m) m × n-bit binary vectors all have different values.
[0025]
The values are selected so that the period T of the n-bit binary vector g generated by the binary vector generation unit 4 and the number m of binary vectors combined by the binary vector combining unit 8 are relatively prime. It is preferable to do. If the period T and the number m are selected so as to be relatively prime, all T consecutive m × n-bit binary vectors have different values.
[0026]
The binary vector extraction unit 10 generates a d-bit (d ≧ n) binary vector L (= L (t)) at a predetermined position from the m × n-bit binary vector generated by the binary vector combination unit 8. ). However, the position where the d-bit binary vector is extracted is selected so as to include at least one n-bit binary vector bijection map f (g (t + r)). The d-bit binary vector L extracted by the binary vector extraction unit 10 has the following properties.
(1) By increasing the period T of the n-bit binary vector g generated by the binary vector generation unit 4, the number of elements in the entire set of d-bit binary vectors L that may be generated increases. In particular, by selecting the period T of the n-bit binary vector g and the number m of binary vectors combined by the binary vector combining unit 8 to be relatively prime, T consecutive m × n bits Since all binary vectors can be generated with different values, the number of elements in the entire set of d-bit binary vectors L that may be generated further increases.
(2) Since it is difficult to derive the original binary vector g from the binary vector bijective map f, the original binary vector is derived from the d-bit binary vector L including at least one binary vector bijective map f. It is also difficult to derive g.
(3) The T / GCD (T, m) consecutive m × n-bit binary vectors are all different values, and the binary vector extraction unit 10 pre-determines from the m × n-bit binary vector in advance. The d-bit binary vector L is extracted so that the d-bit binary vector L at a predetermined position is included in at least one n-bit binary vector bijection map f. For this reason, the period of the d-bit binary vector coincides with the period of the m × n-bit binary vector and becomes T / GCD (T, m). That is, the continuous T / GCD (T, m) binary vectors L all have different values. In other words, the d-bit binary vector L once generated is never generated again during the period of T / GCD (T, m).
[0027]
Due to the properties (1) to (3), a d-bit binary vector L can be used as secret information.
[0028]
FIG. 2 shows an example of a detailed configuration of the secret information generating apparatus according to the present invention. The secret information generation apparatus 11 shown in the figure is a more specific example of the schematic configuration shown in FIG. The binary vector generation unit 12 corresponds to the binary vector generation unit 4 shown in FIG. 1, and includes k stages (where k <n) linear feedback shift registers (LFSR) 13 and n-k bit binary vectors. N, which is a combination of the k-bit binary vector from the LFSR 13 and the n-k bit binary vector from the preset memory 14 at the timing when the clock is input to the clock terminal 16. Output a binary vector of bits.
[0029]
Here, a specific configuration example of the LFSR 13 will be described first. FIG. 3 shows an example of the configuration of the LFSR 13. The LFSR 13 includes k-1 AND elements 18-1 to 18-k-1, k-1 exclusive OR elements 20-1 to 20-k-1, and k D flip-flops 22. -1 to 22-k.
[0030]
The input terminals c1 to ck-1 are for setting binary fixed values. The values of the D flip-flops 22-1 to 22-k are output from the output terminals x1 to xk. In this circuit, when at least one of the k D flip-flops 22-1 to 22-k is set to 1 and the clock is input to the clock terminal 16, the state is changed. Let At this time, the number of clocks required until the value of each D flip-flop 22-1 to 22-k returns to the initial value is called a period. This period can be changed by changing the values set in the input terminals c1 to ck-1. In particular, the following characteristic equation C (x) on GF (2) = C0 + C1x + c2x2 +... + Ck-1xk-1
When is irreducible and primitive over GF (2), its period is known to be 2k-1 and maximized. When 2k-1 is a prime number, the characteristic equation is always primitive if it is irreducible and primitive on GF (2), and its period is 2k-1, which is the maximum.
[0031]
Returning again to FIG. An arbitrary fixed value can be set in the preset memory 14. On the other hand, the LFSR 13 changes its output value every time a clock is input to the clock terminal 16. When the period of this change is T, the value of the n-bit binary vector g obtained by combining the k-bit bit string from the LFSR 13 and the nk-bit bit string from the preset memory 14 is different during the period T. It will be a thing. That is, T consecutive binary vectors g all have different values.
[0032]
The encryption unit 24 corresponds to the bijection map generation unit 6 shown in FIG. 1, and encrypts the n-bit binary vector from the binary vector generation unit 12 using a common key encryption algorithm. Specifically, the encryption unit 24 encrypts an n-bit binary vector from the binary vector generation unit 12 with an encryption key input to the key input terminal 26, and outputs an n-bit binary vector that is encrypted data. To do. By performing encryption with the encryption unit 24, the uniqueness of decryption is guaranteed, and it is difficult to restore the data before encryption from the encrypted data without knowing the encryption key. Become. Therefore, if the encryption unit 24 keeps the key secretly in the system, it is easy to generate the output from the input inside the system, and it is difficult to restore the input from the output outside the system. It can be said that a certain binary vector bijection map f is realized.
[0033]
The shift register 28 corresponds to the binary vector combination unit 8 shown in FIG. 1, and has a storage area of n × m bits. The shift register 28 inputs the n-bit binary vector from the encryption unit 24 to the leftmost storage area, and each time a clock is input to the clock terminal 16, the stored content is shifted to the right by n bits. Shift to storage area. Therefore, every time m times of clocks are input to the clock terminal 16, all the contents stored in the shift register 28 are replaced.
[0034]
As described above, the binary vector generation unit 12 outputs an n-bit binary vector at the timing when the clock is input to the clock terminal 16, and the n-bit binary vector is encrypted by the encryption unit 24, and the shift register 28. Is input. Therefore, in the shift register 28, the timing at which the n-bit binary vector from the encryption unit 24 is input is synchronized with the timing at which the stored content is shifted to the right storage area by n bits, Every time the stored content is shifted to the right storage area by n bits, the n-bit binary vector from the encryption unit 24 is stored in the leftmost n-bit storage area.
[0035]
The binary vector extraction unit 30 corresponds to the binary vector extraction unit 10 shown in FIG. 1 and is configured by d D flip-flops 34-1 to 34-d. A clock obtained by dividing the clock input to the clock terminal 16 into 1 / m by the 1 / m frequency divider 32 is input to each of the D flip-flops 34-1 to 34-d. Each time m clocks are input, one clock is input. Each D flip-flop 34-1 to 34-d holds a binary vector of d bits continuous from the left end of the storage area of the shift register 28, and outputs the value every time a clock is input. As described above, every time m clocks are input to the clock terminal 16, the contents of the shift register 28 are switched. Therefore, each time the contents of the shift register 28 are replaced, each D flip-flop 34-1 to 34-d outputs a continuous d-bit binary vector from the left end of the storage area. The d-bit binary vectors output from the D flip-flops 34-1 to 34-d are output from the secret information output terminal 36 as secret information.
[0036]
As described above, in the secret information generating apparatus according to the present embodiment, the n-bit binary vector g is generated by changing the period T, the n-bit binary vector bijection map f is generated from the binary vector g, and The m binary vector bijection maps f are combined, and a d-bit binary vector L at a predetermined position of the m × n-bit binary vector is extracted as secret information. Therefore, as in the case of adopting a method of storing all the generated secret information and regenerating again when the newly generated secret information matches the stored secret information, The secret information once generated can be prevented from being generated for a predetermined period without requiring a complicated procedure for preventing the secret information from being duplicated.
[0037]
Next, another embodiment of the present invention will be described. In the embodiment described above, as shown in FIG. 2, the binary vector generation unit 12 includes the preset memory 14 in which an arbitrary fixed value is set. However, a random number generation unit is provided instead of the preset memory 14. May be.
[0038]
FIG. 4 shows another example of the detailed configuration of the secret information generating apparatus according to the present invention. Compared with the secret information generation device 11 shown in FIG. 2, the secret information generation device 40 shown in FIG. 2 has the binary vector generation unit 42 generate random numbers instead of the preset memory together with the LFSR 13 as k-bit binary vector generation means. The difference is that a random number generation unit 44 is provided as a means. Since the other configuration is the same as that of the secret information generating apparatus 11, the description thereof is omitted.
[0039]
As described above, the LFSR 13 sequentially generates k-bit binary vectors, and changes the value of each binary vector during the period T for generation. The random number generator 44 generates nk bits of random numbers at a predetermined timing.
[0040]
The binary vector generation unit 42 is an n-bit combining the k-bit binary vector from the LFSR 13 and the n-k bit random number or pseudo-random number from the random number generation unit 44 at the timing when the clock is input to the clock terminal 16. A binary vector g is output.
[0041]
In this way, by generating an n-k bit random number and including the random number in the n-bit binary vector g, the generated secret information has no periodicity, and the generation of secret information closer to a genuine random number can be achieved. It becomes possible.
[0042]
The embodiment of the present invention has been described with reference to the drawings. However, the present invention is not limited to the matters shown in the above-described embodiments, and it is obvious that changes, improvements, and the like can be made based on the description of the scope of claims.
[0043]
【The invention's effect】
As described above, according to the present invention, all the generated secret information is stored, and when the newly generated secret information matches the stored secret information, it is generated again. In addition, the secret information once generated can be prevented from being generated for a predetermined period without requiring a large number of storage areas and complicated procedures for preventing the secret information from overlapping.
[Brief description of the drawings]
FIG. 1 is a diagram showing an example of a schematic configuration of a secret information generating apparatus according to the present invention.
FIG. 2 is a diagram showing an example of a detailed configuration of a secret information generating apparatus according to the present invention.
FIG. 3 is a diagram illustrating an example of a configuration of a linear feedback shift register.
FIG. 4 is a diagram showing another example of a detailed configuration of the secret information generating apparatus according to the present invention.
[Explanation of symbols]
2 Secret Information Generating Device 4 Binary Vector Generating Unit 6 Bijection Mapping Generating Unit 8 Binary Vector Combining Unit 10 Binary Vector Extracting Unit 11 Secret Information Generating Device 12 Binary Vector Generating Unit 13 Linear Feedback Shift Register (LFSR)
14 preset memory 16 clock terminal 18-1 to 18-k-1 AND element 20-1 to 20-k-1 exclusive OR element 22-1 to 22-k D flip-flop 24 encryption unit 26 key input terminal 28 Shift register 30 Binary vector extraction unit 32 Frequency divider 34-1 to 34-d D flip-flop 36 Secret information output terminal 40 Secret information generation device 42 Binary vector generation unit 44 Random number generation unit

Claims (6)

  n-bit binary vector generation means for generating a sequence of n-bit binary vectors, which guarantees that the values of each binary vector are generated differently during a period T; Binary vector bijection map generation means for sequentially inputting a binary vector sequence and generating a sequence of n-bit binary vector bijection maps; Binary vector combining means for combining the individual, and binary vector extracting means for extracting a d-bit binary vector at a predetermined position in the combined m × n-bit binary vector, wherein A secret information generation device comprising: an extraction that includes a bijection map   The n-bit binary vector generation means is a k-bit binary vector generation means for generating a sequence of k-bit binary vectors, and guarantees that the values of each binary vector are generated differently during a period T. And a random number generating means for generating n-k bit random numbers, and generating a sequence of n-bit binary vectors obtained by combining the k-bit binary vectors and the n-k bit random numbers. The secret information generating apparatus according to claim 1.   2. The binary vector bijection map generation means is characterized in that it is easy to generate an output from an input inside the system and it is difficult to restore the input from the output outside the system. 2. The secret information generation device according to 2.   2. The period T in which binary vectors having different values are generated by the n-bit binary vector generating unit and the number m of binary vectors combined by the binary vector combining unit are relatively prime. The secret information generation device according to any one of? A procedure for obtaining a k-bit bit string from a linear feedback shift register that generates k-bit bit strings having different values during the period T;
A procedure for reading an n-k bit sequence stored in advance from a preset memory;
Combining the k-bit bit string and the nk bit string to generate an n-bit binary vector;
A procedure of obtaining the n-bit encrypted data by inputting the n-bit binary vector to the encryption means and encrypting it using a predetermined encryption key;
a procedure for sequentially inputting the n-bit encrypted data into a shift register capable of storing n × m-bit data;
The d D flip-flops connected to extract d bits at a predetermined position of the shift register so as to include at least one n-bit encrypted data include m pieces of the encrypted data held in the shift register. The procedure to operate every time it is replaced,
A secret information generation method characterized in that d-bit secret information is obtained from the d D flip-flops . A procedure for obtaining a k-bit bit string from a linear feedback shift register that generates k-bit bit strings having different values during the period T;
obtaining an nk bit sequence from a random number generator for generating an nk bit random number;
Combining the k-bit bit string and the nk bit string to generate an n-bit binary vector;
A procedure of obtaining the n-bit encrypted data by inputting the n-bit binary vector to the encryption means and encrypting it using a predetermined encryption key;
a procedure for sequentially inputting the n-bit encrypted data into a shift register capable of storing n × m-bit data;
The d D flip-flops connected to extract d bits at a predetermined position of the shift register so as to include at least one n-bit encrypted data include m pieces of the encrypted data held in the shift register. The procedure to operate every time it is replaced,
A secret information generation method characterized in that d-bit secret information is obtained from the d D flip-flops .

Images