JPH09311627A - Method and device for generating cipher key of cipher based on circulating computation - Google Patents

Abstract

PROBLEM TO BE SOLVED: To simplify generation of a cipher key to be used for enciphering and deciphering cipher based on circulating computations, by using a binary series generated at random. SOLUTION: A random number having a length of e(1)+...+e(k) bits generated at random by a random number generating means 102 is inputted into a binary digit string dividing means 131, and the input random number is divided into k random numbers of e(1),..., e(k) bits respectively. An addition means 132 adds 1 to the k random numbers respectively, and further a simultaneous congruence expression solution finding means 133 solves simultaneous congruence expressions relating to x, x=aj (mod pj ), j=1,..., k, where k random numbers are designated as a1 ,..., ak . A found solution is supplied to a cipher device 105 as a cipher key A for the cipher device based on a circulating computation. The cipher device 105 thereby secures remarkable simplification of ciphering and deciphering caused by the cipher key A.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and apparatus for generating an encryption key for encryption based on circular operation, and is particularly adopted in a communication system or computer system to prevent unauthorized persons from illegally acquiring information. In order to do so, the present invention relates to a method and apparatus for generating a cryptographic key based on cyclic operation, which is used in encryption for converting information into ciphertext and decryption for restoring original information from ciphertext.

[0002]

2. Description of the Related Art In a conventional encryption method and apparatus of this type, a linear transformation (also called an affine transformation) Y is often used.
= AX + B (mod P) was combined to perform encryption. The linear conversion here is the integer X to be converted.
Is multiplied by an integer A, an integer B is added to the multiplication result AX, and the remainder (called a remainder) when the addition result AX + B is divided by P is a ciphertext Y. This is represented by Y = AX + B (mod P) described above.

In such a linear conversion cipher, A,
B and P are predetermined integers, generally A and B are encryption keys, and P is an alphabet number. Especially A =
It is called a Caesar cipher that sets 1, the encryption key is B, and the alphabet is P. In addition, a cryptographic key of which A is B, B = 0, and P is the number of alphabets is called a product cipher.

In an ordinary computer, since an 8-bit integer is often treated as one character, each of A, X and B is an 8-bit integer, so P = 256. Therefore, the lower 8 bits of the operation result AX + B are AX
It becomes equal to + B (mod P). That is, the remainder can be calculated by ignoring the upper bits without dividing.

In addition, in an encryption method called multiple remainder encryption, nonlinear encryption is performed by combining linear transformations in which A and B are predetermined integers and P is an encryption key. In addition, about Caesar cipher, product cipher, and linear conversion cipher, for example, from Kojio Matsui "Introduction to Cryptanalysis by Computer" (Morikita Publishing Co., Ltd., 1990), there are detailed explanations on pages 39 to 55. Further, the multiple residue cipher is described in detail, for example, in Japanese Patent Laid-Open No. 6-75525.

In the following description, X is called plaintext and Y
Is also called ciphertext. Furthermore, in the following description, x = Y
mod Z means substituting the remainder obtained by dividing Y by Z into X, and X = Y / Z means substituting the quotient obtained by dividing Y by Z into X, = Y (mod
Z) shall mean that the remainder obtained by dividing X by Z and the remainder obtained by dividing Y by Z are equal.
Further, X = Y (mod Z) is called a congruential expression.

However, the cipher obtained by such linear conversion has a problem that it can be easily deciphered. The reason is that even a third party who does not know the encryption key
This is because, if some input / output pairs are available, a cryptographic key can be estimated by constructing a linear equation based on them and solving the linear equation.

Further, the multi-residue cipher has a problem that the amount of calculation is large. The reason is that in the linear conversion cipher, a value that is a power of 2 is usually selected as the modulus P, so that division is not necessary, but in the multiple residue cipher, a prime number is selected as the modulus P, so division is performed. It depends on what you need.

Therefore, conventionally, an encryption method and a decryption method based on a cyclic operation have been used as a non-linear conversion that does not require division. This encryption method uses n-bit plaintext X
And Y = AX, and Y = (lower n bits of Y) + (n higher bits of Y) until Y becomes an n-bit integer.
This is an encryption method in which Y is output as a ciphertext when Y becomes an n-bit integer.

In this case, Y = (lower n bits of Y) +
Since the operation (upper n bits of Y) is repeated at most twice for one encryption, high speed processing is possible. It is known that in order to decrypt the original information from the ciphertext generated by the cryptographic method based on the circular operation, an integer that is relatively prime to 2 ⁿ -1 must be used as A.

[0011]

The problem with the above-described conventional encryption and decryption methods based on cyclic operations is that the randomly generated binary sequence cannot be used as an encryption key, and the value of A is , It is necessary to exhaustively generate and use an integer prime to 2 ⁿ -1, which requires a huge amount of calculation to generate an encryption key, and is an inexpensive random number generator that generates a binary sequence. There was a problem that was not available.

An object of the present invention is to solve the above-mentioned problems,
An object of the present invention is to provide an encryption key generation method and device for encryption based on a cyclic operation for generating a value of A that is relatively prime to 2 ⁿ −1 from a randomly generated binary sequence.

[0013]

The present invention has the following means in order to achieve the above object. According to the method for generating a cryptographic key based on the cyclic operation of the present invention, a predetermined integer n can be factored into 2 ⁿ −1 = p ₁ p ₂ ... P _k , and the length of p _j is e. (J) bits, a random number of length e (1) + ... + e (k) bits is divided into k random numbers of e (1) ,. 1 is added to each of the k divided random numbers, and the k divided random numbers are a ₁ , ..., A _k
As a simultaneous congruence equation x = a _j (mod p _j ), j
= 1, ..., K is characterized in that at least one key obtained by solving k is generated as an encryption key.

Further, the first configuration of the present invention relating to the encryption key generation apparatus for encryption based on the cyclic operation has the input means for inputting and transmitting the control signal for designating the encryption processing from the outside, and the random binary sequence. To generate length e (1) + …… +
a random number generating means for sending the e (k) of bit random number, a storage means comprising a storage medium of a given capacity, the ^{_{2 n -1 = p 1 p 2}} ...... p k for integer n to a predetermined When the prime factorization is possible and the length of p _j is e (j) bits, the random numbers transmitted by the random number generating means are k pieces each having a length e (1), ..., E (k) bits. Bit string dividing means for storing the random number divided into k random numbers in the storage means, addition means for adding 1 to each of the k random numbers stored in the storage means, and the storage means The k random numbers are a ₁ , ..., A _k , and the simultaneous congruence equation x = a _j (mod p _j ), j = 1 ,.
When a control signal is input to the control signal inputting means, a simultaneous congruential solution solving means for solving e (1) + ... + e (k) -bit random numbers is provided. Processing for sequentially performing the processing by the bit string dividing means, the adding means, and the simultaneous congruence equation solving means, and supplying at least one of the solutions obtained by the simultaneous congruence equation solving means as an encryption key to an encryption device. It has the configuration.

A second structure of the present invention relating to a cryptographic key generation device based on a cyclic operation is the same as the first structure except that the bit string dividing means, the adding means, and
The simultaneous joint solution solving means is integrated to form a data processing means, and the data processing means sequentially executes the processing based on the control signal input from the control input means.

[0016]

BEST MODE FOR CARRYING OUT THE INVENTION In an encryption method based on a circular operation, Y = AX (A is an encryption key) for an n-bit plaintext X, and Y = (Y The operation of (lower n bits) + (upper n bits of Y) is repeatedly executed, and when Y becomes an integer of n bits, Y is output as a ciphertext.

However, in the above-described encryption method, there is a condition that an integer that is relatively prime to 2 ⁿ -1 is exhaustively generated and used as a value that the encryption key A should take. It was difficult to randomly generate A easily.

In the present invention, 2 ⁿ -1 is 2 ⁿ -1 = p ₁ p
₂ ...... If p _m can be factored, the known Chinese remainder theorem states that the simultaneous congruence equation x = a for x
The solution of _j (mod p _j ), j = 1, ..., M and (a ₁ , a
_{, 2} , ..., A _m ) corresponds to one to one, and if x is a multiple of p, then x = 0 (mod p), so 0 <a
A set of integers (a ₁ , a where _j <p _j , j = 1, ..., M)
₍₂ , ..., _Am ) is randomly determined to solve the above-mentioned simultaneous congruence equation, and the fundamental feature of the encryption key generation method is that an integer that is a prime number of 2 ⁿ −1 is obtained as the solution.

As a configuration for embodying such an encryption key generating method, as shown in FIG. 1, a control signal input means 101 for inputting / outputting a control signal and a length e (1) + ... + e.
(K) Random number generating means 102 for outputting a random number, bit string dividing means 131 for sequentially performing the above-mentioned encryption key generating process on the random number output by the random number generating means 102, and adding means
Data processing means 103 including 132 and simultaneous congruent equation solving means 133 as an integrated configuration, and storage means 104 for providing a processing execution area, and data processing means when control signal input means 101 receives a control signal from the outside An embodiment of the invention is that an encryption key is generated by and is provided to an encryption device 105 that performs encryption and decryption.

[0020]

Next, the present invention will be described with reference to the drawings. FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention. In the embodiment shown in FIG. 1, a control signal input means 101 for inputting and outputting a control signal as an encryption key setting command received from a higher-level device (not shown), and a random number for transmitting a random number as mother data necessary for generating a desired encryption key. Generating means 102, data processing means 103 for performing data processing for generating a cryptographic key on the random numbers sent by the random number generating means 102, and storage means 104 for providing an execution area necessary for data processing by the data processing means 103. With.

The data processing means 103 includes a bit string dividing means 131 for performing a bit string dividing process on the random number sent from the random number generating means 102, and an adding means 132 for adding a predetermined integer to the divided random number subjected to the bit string dividing process. And a simultaneous congruence equation solving means 133 which performs solution finding processing using the simultaneous agreement equation on the output of the adding means 132 and outputs the solution as an encryption key. It is to be noted that FIG. 1 also shows a cryptographic device 105 for performing encryption and decryption based on a circular operation upon receiving the provision of the cryptographic key.

Prior to the description of the embodiment shown in FIG. 1, the contents of the encryption key generation method based on the circular operation of the present invention will be described. For a predetermined integer n, 2 ⁿ −1 =
_{p 1 p 2 ...... p k 2} n -1 and so that is assumed to be disassembled prime factors. By the way, according to the Chinese Remainder Theorem, the solution of the simultaneous congruence equation and the equation (a ₁ , a
₂ , ..., A _k ) correspond one-to-one.

[0023]

[Equation 1]

If the solution x of the simultaneous congruential equation is not prime to 2 ⁿ -1, then x becomes a multiple of p _j for some j = 1, 2, ..., K, and x = 0 (mod p _j ). Therefore,
0 <a _j <p for all j = 1, 2, ..., K
_{If j} , then the solution of the system of congruences above is prime to 2 ⁿ -1.

The above description is to say, the value of disjoint A and 2 ⁿ -1, in spite of the interval 0 <exist discontinuously over the the A <2 ⁿ -1, on their When converted to the parameters of the simultaneous congruence equation of, the conversion result (a ₁ , a
₂ , ..., a _k ) is a continuous region 0 <a ₁ <p ₁ , 0 <a ₂
<P _2, ......, 0 <shows an interesting fact that there in a _m <p _k. In the above description, continuity means continuity as an integer.

From such a background, in the encryption key generating method based on the circular operation of the present invention, first, for e (j) such that 2 ^{e (j)} <p _j , the length is e (j) bits. Is generated at random, and one obtained by adding 1 is added to a _j
Value. When e (j) = 0, a _j = 1
And By doing _{so, 0 <a j <p j} a j which satisfies the condition that is obtained. Then, the solution of the above simultaneous congruential equation is obtained for (a ₁ , a ₂ , ..., _Ak ) thus generated, and the solution is set as the value of A. By doing so, the randomly generated length e (1) + e (2) +
The basic feature is that it is possible to generate a value of A that is relatively prime to 2 ⁿ −1 from a binary sequence of + e (k) bits.

Returning to FIG. 1 again, the description of the embodiment will be continued. In FIG. 1, the control signal input means 101 supplies a control signal to the data processing means 103 when a control signal instructing to set an encryption key is input from the outside. The random number generating means 102 generates a random number of length e (1) + ... + e (k) bits and generates the random number 1021 in the data processing means 103.
Supply. The data processing means 103 is a control signal input means.
Upon receiving the control signal 1011 from 101, the random number generating means 102
, A random number 1021 of length e (1) + ... + e (k) bits is input.

The data processing means 103 performs the following processing. That is, the bit string dividing means 131 uses the random numbers 1021 of length e (1) + ... + (k) bits obtained from the random number generating means 102 as e (1), ..., E (k), respectively.
The random number is divided into k random numbers of bits, and the k random numbers are stored in the storage means 104. The adding means 132 is the storage means 10
Add 1 to each of the k random numbers stored in 4.

The simultaneous congruential equation solving means 133 includes a storage means 104.
Let _{k 1} , the random numbers stored in, be a ₁ ,.
Simultaneous congruential expression x = a _j (mod p _j ), j = 1, for x
.., k, and the obtained key is supplied to the encryption device 105 as the encryption key A1031.

The cryptographic device 105 performs encryption based on the circular operation on the information 1511 input from the input terminal 151 based on the cryptographic key A1031 and outputs the obtained ciphertext 1521 from the output terminal 152. On the other hand, based on the encryption key A, the ciphertext 1541 input from the input terminal 154 is decrypted based on the cyclic operation, and the restored information is output from the output terminal 153 as the decryption information 1531. In the above, n, k and e (j), p _j , j = 1, ...
..., k are the integers described in the above description.

FIG. 2 is a flow chart for explaining the first encryption key generating operation by the data processing means 103 of FIG. The operation of the embodiment of FIG. 1 will be further described below with reference to the flowchart of FIG. Data processing means 10
3 is the length e (1) + ... + e from the random number generation means 102.
A (k) -bit random number is obtained (step 201). The bit string dividing means 131 has a length e output from the random number generating means 102.
(1) + ... + e (m) -bit random numbers e
(1), ..., E (k) bits are divided into k random numbers,
The random number divided into k pieces is stored in the storage means 104 (step 202).

The adding means 132 adds 1 to each of the k random numbers stored in the storage means 104 (step
203). The simultaneous congruence solving means 133 sets the k random numbers stored in the storage 104 to a ₁ , ..., A _k, and the simultaneous congruence equation x = a _j (mod p _j ), j = 1 regarding x. …
..., k is solved (step 204). In this way, the obtained solution is supplied to the encryption device 105 as the encryption key A (step 205).

In the above embodiment, the encryption device 105
However, since the encryption based on the cyclic operation is performed only once for one block of information, the case where only one encryption key is required is taken as an example. For example, the encryption based on the cyclic operation is 1 When the block information is repeatedly applied m times with different encryption keys, m encryption keys are required. In such a case, the data processing means 10 of FIG. 1 is followed according to the processing flow of FIG. 3 showing a flowchart for explaining the second encryption key generating operation by the data processing means 103.
3 should work.

That is, first, the variable C is set to C = 0 (step 301), the process for generating the encryption key including the steps 201 to 205 of FIG. 2 is executed (step 200), and then C = C + 1. (Step 302), if C = m, then the processing is terminated, and if not, it is judged to shift the control to step 200 (step 303). Thus, the generation of the encryption key used for encryption and decryption based on the cyclic operation can be significantly simplified from the randomly generated binary sequence.

[0035]

As described above, according to the present invention, A having a value that is relatively prime to 2 ⁿ -1 is obtained as a solution of the simultaneous congruential equation from a randomly generated binary sequence, and is used as an encryption key. By implementing a simple method and device,
And has a second effect. The first effect is that an encryption key for an encryption device that performs encryption and decryption based on a circular operation can be generated at high speed. Because 2
Since there was no choice but to generate an integer that is relatively prime to ⁿ −1 by brute force, a huge amount of calculation was required to generate the encryption key. However, according to the present invention, the calculation required to solve almost simultaneous simultaneous congruences This is because the encryption key can be generated only by the amount.

The second effect is that the encryption key generating device can be realized at low cost. This is because conventionally, in order to generate an encryption key required for a cryptographic device based on a circular operation at high speed, a random number generator that generates an integer that is relatively prime to 2 ⁿ -1 was required. This is because the random number generating means for generating a binary sequence can be used. This is because a high-speed random number generating means for generating a binary sequence can be realized at low cost.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention.

FIG. 2 is a flowchart illustrating a first encryption key generation operation of FIG.

FIG. 3 is a flowchart illustrating a second encryption key generation operation of FIG.

[Explanation of symbols]

 101 Control signal input means 102 Random number generation means 103 Data processing means 104 Storage means 105 Cryptographic apparatus 131 Bit string division means 132 Addition means 133 Simultaneous congruence solving means

Claims (3)

[Claims] 1. 2 ⁿ -1 for a predetermined integer n
= P ₁ p ₂ ...... can be factored into p _k , and if the length of p _j is e (j) bits, the length e (1) + ... +
The e (k) -bit random numbers are e (1), ..., e, respectively.
(K) to each random number is divided into the k number after divided into k random bits plus 1, a ₁ divided random number to said k pieces, ..., simultaneous with respect to x as a _k A method for generating an encryption key for encryption based on a cyclic operation, characterized in that at least one key obtained by solving the congruence formula x = a _j (mod p _j ), j = 1, ..., K is generated as an encryption key. . 2. An input means for inputting and transmitting a control signal for designating an encryption process from the outside, and a random number sequence having a length of e (1) + ... + e (k) bits and randomly generating a binary sequence. 2 ⁿ −1 = for a predetermined integer n, a random number generating means for sending, a storage means composed of a storage medium of a predetermined capacity,
p ₁ p ₂ ...... can be factorized into p _k , and when the length of p _j is e (j) bits, the random numbers transmitted by the random number generating means are respectively lengths e (1) ,. , E (k)
A bit string dividing means for decomposing into k random numbers of bits and storing the k divided random numbers in the storage means; addition means for adding 1 to each of the k random numbers stored in the storage means; The k random numbers stored in the storage means are a ₁ ,
..., _ak simultaneous simultaneous congruence equation x = a _j (mod
p _j ), j = 1, ..., K and simultaneous congruential equation solving means, and when a control signal is input to the control signal input means, e (1) + provided from the random number generating means is provided. …… ＋
For the random number of e (k) bits, the processes by the bit string dividing means, the adding means, and the simultaneous congruence solving means are sequentially executed, and the solution obtained by the simultaneous congruence solving means is used as an encryption key. An encryption key generation device for encryption based on cyclic operation, characterized in that at least one key is supplied to the encryption device. 3. The bit string dividing means, the adding means, and the simultaneous congruent solution means are integrated to form a data processing means, and the data processing means is sequentially operated based on a control signal input from the control input means. The encryption key generating device according to claim 2, wherein the process is executed.