Random-number generator, communication system using the same and method therefor

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Industrial application field]

The present invention relates to an encryption method, and particularly to confidentiality of data, authentication of a sender / receiver, sharing of an encryption key, a zero-knowledge proof protocol, and the like in the field of encrypted communication. It also relates to simulations using random numbers such as Monte Carlo simulations.

【0002】

[Conventional technology]

Conventionally, as one of the random number generation methods, as shown in the literature "Modern Cryptography" (Ikeno, Koyama, published in 1986, Institute of Electronics, Information and Communication Engineers), pages 69 to 72, the maximum long-period sequence A linear feedback shift register (LFSR) that generates (M-sequence) is known.

【0003】

The LFSR method is the s-stage shift register R (t) = (r) as shown in Fig. 14._s (t), r_s-1 (t),_... , R₂ (t), r₁ (t)) and tap (drop line) row (h)_s , H_s-1 、_... , H₂ , H₁ ), And a pseudo-random number sequence is generated by simultaneously performing the following operations at each time point (stop).

【0004】

(a) Bit r of the rightmost register₁ Output (t) as a pseudo-random number sequence.

【0005】

k_t = r₁ (t) (b) r_s (t), r_s-1 (t),_... , R₂ Shift (t) to the right.

【0006】

r_i (t + 1) = r_{i + 1} (t) (i = 1, 2,_... , S-1) (c) Bit r of the leftmost register_s Calculate (t + 1) from the register contents and tap sequence as follows.

【0007】

[Outside 1]

<img file="JPH0736672A_D0001.tif" />To summarize the above, the LFSR method pseudo-random number generation algorithm uses the matrix H in s rows and s columns. R (t + 1) = H · R (t) mod2 (1) In other words [0008]

[Outside 2]

<img file="JPH0736672A_D0002.tif" />Can be expressed as.

【0009】

If you select the tap row of this s stage LFSR well, the maximum period is 2^s A bit sequence of pseudo-random numbers of -1 can be generated, and the sequence at that time becomes the above-mentioned maximum long-period sequence.

【0010】

However, in the random number generation method using this LFSR, the linearity of the LFSR is used to change the output pseudo-random number sequence of 2 s bits to the tap sequence of s stages (h)._s , H_s-1 、_... , H₂ , H₁ ) Can be determined by the following method.

【0011】

The output pseudo-random number sequence is k₁ , K₂ 、_... , K_2sIf so, at some point t (t = 1, 2,_... , S + 1) register contents R (t) R (1) = (k_s , K_s-1 、_... , K₁ )^TR (2) = (k_{s + 1} , K_s 、_... , K₂ )^T... R (s + 1) = (k_2s, K_2s-1 , ..., k_{s + 1} )^TCan be expressed as (^T Indicates transpose). At this time, the matrices X and Y X = (R (1), R (2),_... , R (s)) Y = (R (2), R (3),_... , R (s + 1)) Then, from equation (1) Y = H X Because the relationship is established H = Y X^-1 (2) H is obtained by, and the tap row is determined.

【0012】

That is, the random number period is 2^s Although it is -1, the LFSR configuration is determined by 2s bits. In this case, since all the random number sequences generated after that time are known, there is a drawback that it is inappropriate in terms of security to use the output random number sequence as a random number for encryption.

【0013】

Further, it is known that the number of random numbers required for analysis of an output random number sequence can be increased by using a nonlinear feedback shift register. However, the Berlekamp-Massay algorithm (ERBerlekamp Algebraic coding theory, McGraw-Hill Book Company, 1968) can be used to determine the minimum number of LFSRs that can generate the sequence, and a random number using a nonlinear feedback shift register. The generation method could also be analyzed by the method of Eq. (2).

【0014】

As described above, if the output random numbers up to a certain point in time can be obtained, the random number generation method capable of easily predicting all the random number sequences to be output after that is referred to as method A for convenience. Method A is not cryptographically secure as described above, but has the feature that high-speed processing is possible because it is easy to configure.

【0015】

Unlike the method A, the random number generation method in which it is very difficult to predict the random numbers to be generated after that point from only the random number sequence generated up to a certain point in time is shown below, and is called method B for convenience. To.

【0016】

As a method for realizing Method B, a method as shown in the document "Advances in Cryptography" ("Advancesin Cryptology", published in 1983, PLENUM PRESS, paragraphs 61 to 78) is known. That is, the random number sequence is b₁ , B₂ 、_... Then bit b_i Is x₀ With the initial values p and q as prime numbers x_{i + 1} = x_i²modn (i = 0, 1, 2,_... ) (3) b b_i = lsb (x_i ) (I = 0, 1, 2,_... ) Given by (where n = p · q, lsb represents the least significant bit).

【0017】

Random number sequence b generated by this method₁ , B₂ 、_... , B_i Only from b_{i + 1} Is known to require as much effort as factoring n. In other words, it is known that the amount of calculation for obtaining the random numbers that should be generated after that point from only the random number sequence generated up to that point is equivalent to the amount of calculation required for factoring n. There is. However, in order to make it difficult to factor n in terms of computational complexity, it is necessary to set p and q to about several hundred bits. In this way, random numbers generated by a method that makes it computationally difficult to predict the random numbers that should be generated after that point in time from only the random number sequence that has been generated up to that point in time are cryptographically. It is called a safe pseudo-random number.

【0018】

However, when a cryptographically secure pseudo-random number generation method is used as the random number generation method, it is necessary to set p and q to about several hundred bits as described above. In that case, x in Eq. (3)_{i + 1} = x_i²There was a problem that the amount of calculation for calculating modn was large and random numbers could not be generated at high speed.

【0019】

[Means for solving problems]

In order to solve the above problems, the random number generator of the present invention has a holding means for holding data and a conversion means for inputting the data held in the holding means and converting the input data value based on a predetermined parameter. An update means for updating the data held in the holding means based on the conversion result by the conversion means, and an output means for sequentially outputting a part of the data held in the holding means as a random number sequence. Eh.

【0020】

Further, according to another aspect of the present invention, a holding means for holding data, a conversion means for inputting data held in the holding means and converting an input data value based on a predetermined parameter, and the conversion. An update means for updating the data held in the holding means based on the conversion result by the means, an output means for sequentially outputting a part of the data held in the holding means as a random number sequence, and an output series as the parameter. It is provided with a calculation means for sequentially calculating a parameter series for which it is difficult to estimate the series from the above and changing the parameters.

【0021】

Further, according to another aspect of the present invention, the first holding means for holding the data and the data held in the first holding means are input, and the input data value is converted based on a predetermined parameter. Based on the first conversion means and the conversion result by the first conversion means, the first updating means for updating the data held in the first holding means and the first holding means hold the data. The transmission device is provided with a first output means for sequentially outputting a part of data as a random number sequence and an encryption means for encrypting a communication sentence based on the random number sequence output from the first output means. A second holding means for holding data, a second conversion means for inputting the data held in the second holding means and converting the input data value based on a predetermined parameter, and the second conversion. Based on the conversion result by the means, the second updating means for updating the data held in the second holding means and a part of the data held in the second holding means are sequentially output as a random number sequence. The receiving device is provided with a second output means and a decryption means for decrypting a code sentence based on a random number sequence output from the second output means.

【0022】

Further, according to another aspect of the present invention, the first holding means for holding the data and the data held in the first holding means are input, and the input data value is converted based on a predetermined parameter. Based on the first conversion means and the conversion result by the first conversion means, the first updating means for updating the data held in the first holding means and the first holding means hold the data. A first output means for sequentially outputting a part of data as a random number series, and a first calculation means for sequentially calculating a parameter series for which it is difficult to estimate the series from the output series as the parameter and changing the parameters. A second holding means for holding the data and a second holding means for holding the data by providing the transmitting device with an encryption means for encrypting the communication text based on the random number sequence output from the first output means and the second holding means. The data held in the second conversion means is input and the input data value is converted based on a predetermined parameter, and the data is held in the second holding means based on the conversion result by the second conversion means. A second updating means for updating data, a second output means for sequentially outputting a part of the data held in the second holding means as a random number series, and an estimation of the series from the output series as the parameters. The receiving device is provided with a second calculation means for sequentially calculating a parameter sequence that is difficult to perform and changing the parameters, and a decoding means for decrypting a code based on a random number sequence output from the second output means. Prepare.

【0023】

[Action]

In the random number generator of the present invention, the data held in the holding means is input, the input data value is converted by the conversion means based on a predetermined parameter, and the holding means is converted based on the conversion result by the conversion means. The update means updates the retained data. The output means sequentially outputs a part of the data held in the holding means as a random number series.

【0024】

Further, the calculation means sequentially calculates a parameter sequence in which it is difficult to estimate the sequence from the output sequence as the parameter, and changes the parameter.

【0025】

Further, on the transmitting side, the data held in the first holding unit that holds the data is input to the first conversion unit, the input data is converted based on a predetermined parameter, and based on the result of the conversion, the above-mentioned The data held in the first holding unit is updated, a part of the data held in the first holding unit is sequentially output as a random number sequence, and the communication message is encrypted based on the output random number sequence. The encrypted text is sequentially transmitted to the receiving side, and the receiving side inputs the data held in the second holding unit that holds the data to the second conversion unit, and converts the input data based on the predetermined parameters. Then, based on the result of the conversion, the data held in the second holding unit is updated, and a part of the data held in the second holding unit is sequentially output as a random number sequence, and the output is performed. Decrypts the cipher based on a random sequence.

【0026】

[Example]

(Example 1) FIG. 1 is a diagram showing a block configuration of a random number generator using an LFSR. It is composed of a linear conversion circuit 12 that linearly converts the values from the shift register 11 and each register of the shift register 11 and feeds them back to the shift register 11.

【0027】

The procedure for generating random numbers according to this embodiment is as follows (however, procedure 3.4.5 is performed at the same time).

【0028】

1. Set the initial value in each register of shift register 11.

【0029】

2. The linear transformation circuit 12 determines the linear transformation according to the parameters given from the outside.

【0030】

3. Each register shifts a given value to the right.

【0031】

4. Output the value of the rightmost register as a random number.

【0032】

5. Feedback transform the value of each register according to the linear transformation determined in 2., and use it as the value of the leftmost register.

【0033】

6. Repeat 3.4.5. Below, but the number of random numbers output is the number of random numbers required to analyze the random number sequence (currently) so that the output random number sequence cannot be analyzed by Eq. (2). Change the parameters input to the linear conversion circuit 12 and change the linear conversion method before it becomes larger than twice the stage of the shift register.

【0034】

In this procedure, all or part of the value output in step 4 or all or part of the output of the linear conversion circuit is a random number generated by the present invention. Figure 2 shows the random number generator when the AND circuit is used for the linear conversion circuit. In Fig. 2, the initial value is first set in the shift register. The value of the register connected to the AND circuit is the value h of the tap column described above._n , H_n-1 , ..., h₂ , H₁ Therefore, if the register value is changed, the linear conversion method will be changed. If the value of the register is changed by changing the parameter before the number of output random number series exceeds twice the number of stages of the shift register, equation (2) cannot be solved and the random number sequence cannot be analyzed.

【0035】

Also, in step 6, when the parameter to be input to the linear conversion circuit is changed after the number of output random numbers becomes more than twice the linear complexity determined by the random number sequence, and the linear conversion method is changed. However, equation (2) analyzes only the case of the linear conversion method, and it is possible to prevent all subsequent random number series from being analyzed as in the conventional example, so linear conversion is performed by parameters. It is safe after changing the method.

【0036】

(Example 2) In the random number generator by LFSR, the number of random numbers required for analysis of the output random number series is twice the number of stages of LFSR, but when the nonlinear feedback shift register is used, the number of random numbers required for analysis is large. The number can be increased more than in the case of LFSR. Therefore, since the number of bits required for the analysis of the output random number sequence by the equation (2) is increased, there is an advantage that the change cycle of the parameter for changing the non-linear conversion method can be increased. An example using the non-linear feedback shift register is shown in FIG.

【0037】

FIG. 3 is a block diagram showing a random number sequence generator when the nonlinear feedback shift register according to the present invention is used. It is composed of a non-linear conversion circuit 31 that non-linearly converts the values from the shift register 11 and each register of the shift register 11 and feeds them back to the shift register 11.

【0038】

The procedure for generating random numbers according to this embodiment is as follows (however, procedure 3.4.5. Is performed at the same time).

【0039】

1. Set the initial value in each register of shift register 11.

【0040】

2. The non-linear conversion circuit 31 determines the non-linear conversion according to the parameters given from the outside.

【0041】

3. Each register shifts a given value to the right.

【0042】

4. Output the value of the rightmost register as a random number.

【0043】

5. Feedback-convert the value of each register according to the non-linear transformation determined in 2. to obtain the value of the leftmost register.

【0044】

6. Repeat 3.4.5. Below, but the number of random numbers output will be larger than the number of random numbers required to analyze the random number sequence so that the output random number sequence cannot be analyzed by Eq. (2). Change the parameters input to the non-linear conversion circuit before, and change the non-linear conversion method.

【0045】

In this procedure, all or part of the value output in step 4 or all or part of the output of the nonlinear conversion circuit 31 is a random number generated by this embodiment. A specific configuration of the nonlinear conversion circuit 31 can be realized by a ROM or the like in which the input / output correspondence of a known nonlinear function is stored.

【0046】

(Example 3) In Example 1.2., An example in which a linear and non-linear feedback shift register is used is described in order to explain the present invention in an easy-to-understand manner. However, the essence of the above embodiment is based on a given initial value. In a random number generation method in which random numbers are generated in a chain by performing a predetermined conversion and feeding back, it is necessary to control the conversion method in the conversion by parameters given from the outside, especially to determine the conversion method. The parameter for controlling the conversion method is changed before the random number sequence is output, and the conversion method is changed. As is clear from this, it goes without saying that various methods can be used as the random number generation method, not limited to the linear and non-linear feedback shift registers.

【0047】

Further, the conversion method in the feedback conversion has also been described in the case of controlling by a parameter given from the outside, but it can also be controlled by a parameter obtained by synthesizing a parameter given from the outside and a parameter generated internally.

【0048】

(Example 4) FIG. 4 shows a case where a shift register is not used as a procedure for generating a random number.

【0049】

In this embodiment, Rs operating at the same clock₁ ~ R_n N registers, output from each register and final register (R)_n ) Performs (non-) linear conversion with the feedback output and outputs to the next register S₁ ~ S_m Consists of m (non-) linear conversion circuits.

【0050】

The procedure for generating random numbers according to this embodiment is as follows (however, procedure 3.4.5. Is performed at the same time).

【0051】

1. Set the initial value for each register.

【0052】

2.S₁ ~ S_m Each (non-) linear transformation circuit of is determines the (non-) linear transformation according to an externally given parameter.

【0053】

3. Rightmost register (R_n ) Is output as a random number, and the leftmost register (R)₁ ).

【0054】

4. Each register outputs the value held in 3. and at the same time holds the value in the input section.

【0055】

5. Each (non) linear conversion circuit is the value output from the front register and R_n The feedback output from is converted by the (non-) linear transformation determined in 2. and output to a later register.

【0056】

6. Repeat 3.4.5. Below, but the number of random numbers output will be larger than the number of random numbers required to analyze the random number sequence so that the output random number sequence cannot be analyzed by Eq. (2). Change the parameters input to the (non) linear conversion circuit before, and change the (non) linear conversion method.

【0057】

In this procedure, R_n All or part of the output of is a random number generated by this embodiment.

【0058】

Further, in the above procedure, each (non) linear conversion circuit can be configured by the above-mentioned ROM or the like, and each (non) linear conversion circuit may perform different (non) linear conversion.

【0059】

(Example 5) FIG. 5 shows an example in which a DES (Data Encryption Standard) encryption circuit is used for the pseudo-random number generator. Recently, a powerful decryption method called differential cryptanalysis has been proposed, and the security of DES encryption has been questioned. As a countermeasure, it is conceivable to change the key frequently. When using a DES encryption circuit, changing the DES encryption key changes the conversion method.

【0060】

(Example 6) According to the following embodiment, the parameter calculation circuit using the method B is provided to calculate the parameters given to the random number generator using the above method A, and the parameters are output from the parameter calculation circuit. By controlling the conversion method in the random number generator with the parameters, it is possible to generate a random number sequence that realizes both the high speed, which is the advantage of method A, and the safety, which is the advantage of method B, as follows. It was done.

【0061】

Conversion of the random number generating means by changing the value of the tap string before or near the number of random numbers output to the random number generator by the method A becomes larger than or near the number of random numbers required for the analysis of the random number sequence. By changing the method of, it is possible to prevent the analysis of the output random number sequence by the method of Eq. (2) and improve the safety of the output random number sequence. Therefore, the value of the tap row is controlled by the method B as a parameter.

【0062】

In this case, since it is sufficient that the parameters are calculated by the method B until the number of random numbers output by the random number generator using the method A becomes larger than the number of random numbers required for the analysis of the random number sequence, the method is used. Even if B cannot be calculated at high speed, it is possible to generate random numbers at high speed as a whole.

【0063】

Further, even if the value of the tap string is changed after outputting a sufficient number of random numbers for the analysis by the method of Eq. (2), the analysis can be performed only when the value of the tap string is changed. Moreover, since the value of the tap string is controlled by method B, it is difficult to predict the value of the next tap string, and it is possible to prevent all subsequent random number sequences from being analyzed as in the past. It is safe after changing the value of the tap column.

【0064】

(Example 7) In the random number generator by LFSR, the number of random numbers required for analysis of the output random number series is twice the number of stages of LFSR, but when the nonlinear feedback shift register is used, the number of random numbers required for analysis is large. The number can be increased more than in the case of LFSR. Therefore, since the number of bits required for the analysis of the output random number sequence by the equation (2) is increased, there is an advantage that the calculation cycle of the parameter for changing the non-linear conversion method can be increased. The fact that the calculation cycle can be increased is a particularly great advantage when the method B, which is difficult to perform high-speed processing, is used for the parameter calculation unit.

【0065】

An example using the non-linear feedback shift register is shown in FIG. FIG. 8 is a block diagram showing a random number sequence generator when the nonlinear feedback shift register according to the present invention is used. As a random number generation means based on the method A, a non-linear conversion circuit 21 that non-linearly converts the values from the shift register and each register of the shift register and feeds them back to the shift register is used, and a parameter calculation circuit 61 based on the method B is used. The non-linear conversion method is controlled by the output from the parameter calculation circuit 61.

【0066】

The random number generation procedure according to this embodiment is performed as follows (however, procedure 4.5.6. Is performed at the same time).

【0067】

1. Set initial values for each register of the shift register and the parameter calculation circuit.

【0068】

2. The parameter calculation circuit calculates the first parameter from the given initial value and outputs it to the nonlinear conversion circuit 21.

【0069】

3. The non-linear conversion circuit 21 determines the non-linear conversion according to the parameters given in 2.

【0070】

4. Each register shifts a given value to the right.

【0071】

5. Output the value of the rightmost register as a random number.

【0072】

6. The value of each register is feedback-converted according to the non-linear transformation determined in 3. to be the value of the leftmost register.

【0073】

7. Repeat 4.5.6. Below, but the number of random numbers output will be larger than the number of random numbers required to analyze the random number sequence so that the output random number sequence cannot be analyzed by Eq. (2). Previously, the parameter calculation circuit calculates the following parameters and outputs them to the non-linear conversion circuit 21 to change the non-linear conversion method.

【0074】

In this procedure, all or part of the value output in step 5, or all or part of the output of the nonlinear conversion circuit is a random number generated by the present invention. The specific configuration of the nonlinear conversion circuit 21 can be realized by a ROM or the like that stores the input / output correspondence of a known nonlinear function.

【0075】

(Example 8) In Examples 6 and 7, in order to explain the present invention in an easy-to-understand manner, an example using a linear and non-linear feedback shift register as a random number generation means has been described, but the essence of the present invention is a random number using the method A. The purpose is to control the conversion method of the generating means by the parameters output from the parameter calculating means using the method B. In particular, the conversion method is changed by the output from the parameter calculation means before outputting as many random number sequences as necessary for determining the conversion method of the random number generation means. As is clear from this, it goes without saying that various methods can be used as the random number generating means, not limited to the linear and non-linear feedback shift registers.

【0076】

In addition to equation (3), the literature "Cryptography and Information Security" (written by Tsujii and Kasahara, published in 1990, Akiaki Co., Ltd.) includes cryptographically secure pseudo-random number generation methods that can be used as method B. As shown on page 86), RSA ciphers, discrete logarithmic ciphers, and inverse logarithmic ciphers are known, and these can also be used in the algorithm of the parameter calculation means of the present invention.

【0077】

Further, the parameter generation means based on the method B can also be configured by combining the cryptographically secure pseudo-random number generation method and the method of using the ROM whose contents are kept secret as feedback as shown in FIG.

【0078】

In addition, since it is not possible to know the remaining values inside the ROM from the values generated from the ROM by only the method of using the ROM whose contents are kept secret as feedback, the parameter generation means based on the method B is used. Can be configured.

【0079】

Further, regarding the control of the conversion method of the random number generation means, the case of controlling only by the parameters generated by the parameter calculation circuit has been described, but the internal parameters of the random number generation means and the parameters calculated by the parameter calculation circuit are combined. It can also be controlled by parameters.

【0080】

(Example 9) FIG. 9 shows a case where a shift register is not used as a procedure for generating a random number.

【0081】

In this embodiment, R operates at the same clock as the random number generation means based on the method A.₁ ~ R_s S registers and the output from each register and the final register (R)_s ) Performs (non-) linear conversion with the feedback output and outputs it to the next register T₁ ~ T_m It is constructed by using m (non-) linear conversion circuits of the above and the parameter calculation circuit 61 based on the method B. Each (non) linear conversion method is controlled by the output from the parameter calculation circuit 61.

【0082】

The procedure for generating random numbers according to this embodiment is as follows (however, procedure 4.5.6. Is performed at the same time).

【0083】

1. Set initial values for each register and parameter calculation circuit 61.

【0084】

2. The parameter calculation circuit 61 calculates the first parameter from the given initial value and outputs it to each (non-) linear conversion circuit.

【0085】

3.T₁ ~ T_m Each (non-) linear transformation circuit in 2 determines each (non-) linear transformation according to the parameters given by 2.

【0086】

4. Rightmost register (R_s ) Is output as a random number, and the leftmost register (R)₁ ).

【0087】

5. Each register outputs the value held in 4. and at the same time holds the value in the input section.

【0088】

6. Each (non) linear conversion circuit is the value output from the front register and R_s The feedback output from is converted by the (non-) linear transformation determined in 3. and output to a later register.

【0089】

7. Repeat 4.5.6. Below, but the number of random numbers output will be larger than the number of random numbers required to analyze the random number sequence so that the output random number sequence cannot be analyzed by Eq. (2). Previously, the parameter calculation circuit calculates the following random number and outputs it to each (non) linear conversion circuit to change each (non) linear conversion method.

【0090】

In this procedure, R_s All or part of the output of is a random number generated by the present invention.

【0091】

Further, in the above procedure, each (non) linear conversion circuit can be configured by the above-mentioned ROM or the like, and each (non) linear conversion circuit may perform different (non) linear conversion.

【0092】

(Example 10) FIG. 10 shows an example in the case where the DES (Data Encryption Standard) encryption circuit 51 is used as the random number generation means in the present invention. Recently, a powerful decryption method called differential cryptanalysis has been proposed, and the security of DES encryption has been questioned. As a countermeasure, it is conceivable to change the key frequently. When using the DES encryption device 51, changing the DES encryption key changes the conversion method.

【0093】

(Example 11) As described above, since the random numbers generated by the above random number generator are strong against analysis, using these random numbers in the encryption method is strong and highly secure against analysis. Cryptographic communication can be realized. Hereinafter, an example of encrypted communication using a random number generator will be shown in an encrypted communication network based on an encryption method (stream cipher) in which an exclusive OR is taken bit by bit between a communication statement and a random number.

【0094】

Figure 11 shows a common key cryptographic communication network that shares a unique and secret encryption key among the subscribers of the network, where A, B, C, ..., N are the subscribers of that network, K._AB, K_AC, ... Indicates the encryption key shared between subscribers AB, the encryption key shared between subscriber ACs, and so on.

【0095】

FIG. 12 is a block diagram showing a configuration of a communication device 122 including a cryptographic device and a decryption device when a random number generator 121 including a random number generation circuit and a parameter calculation circuit according to the present invention is used.

【0096】

FIG. 13 shows the state of confidential communication between A and B in the cryptographic communication system shown in FIGS. 11 and 12.

【0097】

Cryptographic communication from subscriber A to subscriber B is performed according to the following procedure.

【0098】

1. The sender A of the communication is the secret key K shared with the destination B._ABAll or part of is set as the initial value of the random number generation circuit and the parameter calculation circuit, and the random number sequence k_i To generate.

【0099】

2. A is the generated random number sequence k_i And correspondence m_i Exclusive OR for each bit, ciphertext [0100]

[Outside 3]

<img file="JPH0736672A_D0003.tif" />And send the ciphertext to B.

【0101】

3. The recipient B of the communication is the secret key K shared with the source A._ABAll or part of is set as the initial value of the random number generation circuit and the parameter calculation circuit, and the same random number sequence k generated by the sender_i To generate.

【0102】

4.B is the generated random number sequence k_i And received ciphertext c_i Exclusive OR for each bit, and the communication statement [0103]

[Outside 4]

<img file="JPH0736672A_D0004.tif" />To restore.

【0104】

If you follow this procedure, only legitimate destination B will have its secret key K_ABSince you know the ciphertext, you can decrypt the received ciphertext into the original communication text, and other subscribers (C to N) do not know the secret key used to write the ciphertext, so you know the contents. Can't. As a result, confidential communication is realized. Further, even in a network in which the encryption key is not distributed in advance as shown in FIG. 11 but the encryption key needs to be shared between the sender and the receiver prior to performing the encrypted communication, a known method can be used. If key sharing is performed, encrypted communication can be realized by the same procedure.

【0105】

(Example 12) In the encrypted communication network shown in Example 11, since a unique and secret key is shared between the sender and the receiver of the message, the ciphertext is received and decrypted into a meaningful message. Being able to do so guarantees the recipient that the message was sent by another owner of the key. Therefore, in the secret communication system shown in the eleventh embodiment, it is possible to authenticate the sender and the receiver of the communication.

【0106】

(Example 13) In a network in which the encryption key is not distributed in advance as in Examples 11 and 12, but the encryption key needs to be shared between the sender and the receiver prior to performing the encrypted communication. , Diffie-Hellman's method (W. Diffie and MEHellman New Directions incryptography, IEEE, IT, vol.IT-22, No .6,1976) is well known. As the random number used at that time, the random number generated by the present invention can be used.

【0107】

Since it is not necessary for the sender and the called party to have the same random number used in that case, any value may be used as the initial value set in the random number generating means and the parameter generating means.

【0108】

[Effect of the invention]

As described above, according to the present invention, the number of random numbers output by the method (method A) that can be analyzed from a certain number of output sequences is before or near the number required for the analysis. Since the parameters of the method A are changed, it becomes difficult to collect the number of outputs required for the analysis of the method A, and there is an effect that the safety of the generated random numbers is improved.

【0109】

Further, by changing the parameters of the method A based on the random numbers output from the output sequence by the method (method B) that is difficult to analyze, there is an effect that the safety of the method A is further enhanced.

【0110】

In this case, since it is sufficient that the random numbers are output by the method B until the number of outputs output from the method A becomes larger than the number required for the analysis of the method A, the random numbers of the method B cannot be generated at high speed. You may. However, since the final output is the output from method A, it is possible to generate random numbers at high speed.

【0111】

Further, if this random number sequence is used for encrypted communication, there is an effect that high-speed and highly secure encrypted communication is realized.

[Simple explanation of drawings]

[Figure 1]

It is a figure which shows the block structure of the random number generator using LFSR.

[Figure 2]

It is a figure which shows the detailed block composition of the random number generator using LFSR.

[Fig. 3]

It is a figure which shows the block structure of the random number generator using the nonlinear feedback register.

[Fig. 4]

It is a figure which shows the block structure of the random number generator using a plurality of registers.

[Fig. 5]

It is a figure which shows the block structure of the random number generator using the DES encryption apparatus.

[Fig. 6]

It is a figure which shows the block structure of the random number generator using LFSR.

[Fig. 7]

It is a figure which shows the block structure of the random number generator using LFSR.

[Fig. 8]

It is a figure which shows the block structure of the random number generator using the nonlinear feedback register.

[Fig. 9]

It is a figure which shows the block structure of the random number generator using a plurality of registers.

[Fig. 10]

It is a figure which shows the block structure of the random number generator using the DES encryption apparatus.

[Fig. 11]

It is a figure explaining the common key cryptographic communication network.

[Fig. 12]

It is a block diagram which shows the structure of the communication device including the encryption device and the decryption device.

[Fig. 13]

It is a figure explaining the communication system which performs a secret communication.

[Fig. 14]

It is a figure which shows the block structure of the conventional random number generator using LFSR.

[Explanation of symbols]

11 shift register 12 Linear conversion circuit 21 registers 31 Non-linear conversion circuit 51 DES cryptographic circuit 61 Parameter calculation circuit 71 ROM 72 buffer 73 Square modulo calculation circuit 121 Random number generator 122 Communication equipment