JP2003283488A - Encryption device, decryption device, encryption / decryption device, and encryption system - Google Patents

Abstract

An object of the present invention is to provide an encryption device, a decryption device, an encryption / decryption device, and an encryption system having high encryption strength that can withstand a quantum computer. SOLUTION: Key generation means capable of generating a plurality of encryption keys, encryption means for encrypting an original using the encryption key generated by the key generation means, and encryption protected from the encryption key An encryption device having an encryption key protection unit for creating a key, wherein the key generation unit and the encryption key protection unit are public keys,
Further, the present invention is an encryption device that performs multi-stage encryption using a plurality of encryption keys generated by a key generation unit.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a public key cryptosystem, and more particularly to an encryption device, a decryption device, an encryption / decryption device, and a cryptosystem having a high encryption strength.

[0002]

2. Description of the Related Art In recent years, with the expansion and popularization of network communication, the importance of the encryption technology has been recognized again. There are two types of ciphers used for network communication, one is a secret key cryptosystem and the other is a public key cryptosystem. Many of the public-key cryptosystems are based on the RSA cryptosystem (for example, JP-A-11-039437, JP-A-10-177341, etc.), and this cipher utilizes the difficulty of factorization. It is a public-key cryptosystem with quasi-exponential order strength, and has sufficient security that a normal computer can withstand. Elliptic encryption, which is public key cryptography (for example, Japanese Patent Laid-Open Nos. 2000-293101 and 11-33).
1149, etc.) has an exponential order of strength.

On the other hand, research on quantum computers, which is a fusion of quantum mechanics and information science, has made rapid progress since the beginning of the 1990s, and in particular, the discovery of algorithms on quantum computers that solves the prime factorization and discrete logarithm problems at high speed (1994 ) Is shocking the world of cryptography. In other words, if the quantum computer were put into practical use, the RSA encryption could be easily decrypted,
It will cause immense damage to the information society. Due to the trend of the information-oriented society, there is a demand for the rapid development of a cipher having a strength that can withstand a quantum computer.

[0004]

SUMMARY OF THE INVENTION The present invention has been made in view of the above situation related to a cryptographic system using a public key cryptosystem. An object is to provide a decryption device and a cryptosystem.

[0005]

The inventor of the present invention has found that a Petri net widely known as net theory (see, for example, Japanese Laid-Open Patent Publication No.
10-334075, Japanese Patent Laid-Open No. 08-137825, etc.), and has been engaged in research on system modeling and analysis for a long time, and in recent years, especially in the design of public key cryptography utilizing the difficulty of Petri net analysis. I have considered the possibility. In the process, it became clear that RSA cryptography, which is used in many practical cryptographic tools such as PGP and SSL, cannot withstand quantum computers. The present invention has been completed by finding that it is possible to design public key cryptography much stronger than RSA by utilizing elementary T-invariant, which is a basic periodic element of the net.

That is, the invention of claim 1 includes a key generation means capable of generating a plurality of encryption keys, and an encryption means for encrypting an original text using the encryption key generated by the key generation means, An encryption device having an encryption key protection means for creating an encryption key protected from the encryption key, wherein the key generation means and the encryption key protection means are public keys. In the invention, a plaintext is used as a first original text, the key generation means sequentially generates a plurality of encryption keys, and the plurality of encryption keys are sequentially used to encrypt the original text by the encryption means. Create a encrypted ciphertext, create a protection encryption key from the encryption key used for the encryption by the encryption key protection means, and use the encryption text and the protection encryption key as the next original text. It is an encryption device that repeats encryption to encrypt plain text in multiple stages.

The inventions of claims 3 and 4 relate to a preferred form of the key generating means. In the encryption device of the present invention, the invention of claim 3 uses a petri net as the key generating means. An encryption device as a key generation means for generating an encryption key according to the present invention, wherein the encryption key is a randomly extracted Petri net elementary T-invarian.
It is an encryption device with t (basic periodic element).

The invention of claim 5 relates to a preferred form of the encryption means, and is an encryption device in which the encryption means is an encryption means using a secret key encryption such as DES. The present invention relates to a preferable mode of the encryption key protection means, and in the encryption device of the present invention, the encryption key protection means is an encryption key protection means using a hash function.

Claims 7 and 8 are the decryption device of the present invention, and the invention of claim 7 receives the ciphertext and the protection encryption key created by the encryption device of the present invention, A decryption device for decrypting the ciphertext, which has an encryption key restoration means for decompressing the protection encryption key and restoring the encryption key, and discloses the key generation means and the encryption key protection means. This is a decryption device using a key and the encryption key restoring means as a secret key. The invention of claim 8 is a decryption device, wherein the encryption key restoration means is an encryption key restoration means using an inverse hash function.

A ninth aspect of the present invention is the encryption / decryption device of the present invention, wherein the encryption / decryption device of the present invention and the decryption device of the present invention are integrally configured. is there.

A tenth aspect of the present invention is a public-key cryptosystem according to the present invention, which is created by the encryption device or encryption / decryption device of the present invention, and the encryption device or encryption / decryption device. A transmitting means for transmitting the encrypted text and the protected encryption key to a destination, a receiving means for receiving the encrypted text and the protected encryption key transmitted via the transmitting means, and a receiving means for receiving the encrypted text and the protected encryption key. A decryption device or an encryption / decryption device of the present invention that decrypts the received ciphertext and the protection encryption key.
It is an encryption system having a decryption device.

[0012]

BEST MODE FOR CARRYING OUT THE INVENTION The most important feature of the present invention is to have a key generation means capable of generating a plurality of encryption keys, and the encryption key generated by the key generation means using this key generation means as a public key. Is to encrypt the original text using. That is, while the conventional public key encryption is encrypted with one fixed public key,
According to the present invention, by using a key generation means capable of generating a plurality of encryption keys, decryption of a cipher requires a calculation time which is an accumulation of exponential order deciphering times when only one step of encryption is performed, which is more than that of a conventional cipher. High security can be obtained.

The key generating means is not particularly limited to the present invention, but it is preferable to use a key generator using a Petri net, and further, the encryption key is a randomly extracted Petri net. Elementary T-invarian, which is the fundamental periodic element of
It is preferably t. The basic periodic element of a Petri net is enormous, and it is relatively easy to find one of them, but it is difficult to find all of them both spatially and temporally (NP hard). By using this property, the present invention can be preferably implemented by a mode in which the basic periodic element is used as an encryption key and a Petri net that creates such an encryption key is disclosed as a key generator. A Petri net is a type of model that represents a discrete event system consisting of multiple processes that run in parallel and simultaneously. The components of the system are divided into conditions (places) and events (transitions), and the connections between conditions are Parts that flow through the system and are related by arcs represented by lines are represented by tokens that move in the Petri net.

The present invention is not particularly limited as an encryption means for encrypting an original text using an encryption key.
It is possible to use DES, which is a data encoding standard widely used worldwide including general business (for example, Japanese Patent Laid-Open Nos. 10-063183 and 09-127868). Further, as an encryption key protection means for protecting the encryption key, a hash function (for example, Japanese Patent Laid-Open No. 2001-282375) is used.
Japanese Patent Laid-Open No. 2001-255815, etc.) can be used. Hash functions can be binary or arbitrary length
A computationally efficient function that maps a string to a fixed length binary string, SHA, RIPE-
M, MD5, etc. are known.

According to the present invention, even in the first embodiment in which only one-step encryption is performed as described above, it is possible to obtain higher security than the conventional encryption, but it is also possible to generate a plurality of encryption keys. Since the key generator is used as the public key,
A second embodiment in which multi-stage encryption is performed with a plurality of encryption keys generated by the key generator is possible, and the security strength of ciphertexts can be exponentially accumulated by this multi-stage encryption.

That is, a plaintext is used as a first original text, a plurality of encryption keys are sequentially generated by a key generator, the plurality of encryption keys are sequentially used, and the original text is encrypted by an encryption means. Created a ciphertext, created a protection encryption key from the encryption key used for encryption by the encryption key protection means, repeat the encryption of the original text with the ciphertext and the protection encryption key as the next original text, By encrypting the plaintext in multiple stages, for example, if the strength of the cipher at each stage (calculation amount when attacking) is S ⁿ , the strength obtained by the k-stage cipher is (S ⁿ ) ^k , By increasing the number of encryption steps, it is possible to obtain high security strength, which is difficult to decrypt spatially and temporally. In the conventional public key encryption, the number of encryption keys is one, and even if encryption is performed in multiple stages using this, the strength of security does not increase.

Next, an embodiment of the decoding apparatus of the present invention will be described. The decryption device of the present invention is a device that receives the ciphertext created by the encryption device of the present invention and the protection encryption key, and decrypts the ciphertext. The decryption device decompresses the protection encryption key to decrypt the encryption key. Is a decryption device that has an encryption key restoration means for restoring the key, the key generation means and the encryption key protection means are public keys, and the encryption key restoration means is a secret key. When using a hash function as a protection measure,
The inverse hash function is used as the encryption key restoration means.

For example, in the case of a ciphertext encrypted in multiple stages, the received ciphertext and the protection encryption key are used as the original text, and (1)
Extract the ciphertext and the protection encryption key from the original text, (2) restore the encryption key from the protection encryption key using the inverse hash function, and (3) use the restored encryption key as the decryption key of the private key encryption. By repeating the decryption operations (1) to (3) for decrypting the ciphertext using the decrypted text as the original text, the plaintext can be finally obtained.

Next, an embodiment of the cryptographic system of the present invention will be described. A public-key cryptographic system of the present invention includes an encryption device or an encryption / decryption device of the present invention,
A transmitting unit that transmits the ciphertext and the protection encryption key created by the encryption device or the encryption / decryption device to the destination, and receives the ciphertext and the protection encryption key transmitted via the transmission unit. 1 is a cryptographic system including a receiving unit and a decrypting device or an encrypting / decrypting device of the present invention which decrypts the encrypted text by receiving the encrypted text and the protection encryption key received via the receiving unit, and FIG. FIG. 3 is a conceptual diagram for explaining the embodiment.

In FIG. 1, the plaintext created by the sender (Sender) is'I love you ', and this is the first original text, and a plurality of encryption keys are sequentially generated by a key generator. A ciphertext generated by encrypting the original text with an encryption means such as DES by sequentially using the generated encryption keys.
Create a protected encryption key from the encryption key used for encryption with the Hash Function, repeat the encryption of the original text with the encrypted text and the protected encryption key as the next original text, and make the plain text in multiple stages. 1 shows a cryptographic system having an encryption device for encryption. The ciphertext and the protection encryption key finally created by the encryption device are transmitted by the transmission means (not shown), and receive the ciphertext and the protection encryption key received via the reception means (not shown). The decryption device is a reverse hash function (Reverse Hash Functio
By repeating the decryption operation as described in the above embodiment using n), the receiver (Receiver)
You can get the plaintext ('I love you'). It should be noted that FIG. 1 is an example for explaining the embodiment and does not limit the present invention.

Above, as an embodiment of the apparatus of the present invention,
Although the encryption device and the decryption device have been described, the device of the present invention is a form of an encryption / decryption device in which the above-described encryption device of the present invention and the above-described decryption device of the present invention are integrally configured. It is clear that it can be implemented as.

According to the above-described embodiment, the present invention uses a key generation means capable of generating a plurality of encryption keys as a public key, so that only one-step encryption can be performed.
It is possible to obtain higher security than conventional ciphers, and further, in the form of multi-stage encryption with a plurality of encryption keys, the security strength of ciphertexts can be accumulated in an exponential order, and even in quantum computers. It is possible to provide an encryption device, a decryption device, an encryption / decryption device, and an encryption system having a high encryption strength that can be endured.

[0023]

The present invention will be described in detail below with reference to examples, but the present invention is not limited to these examples. In addition, as an embodiment, in order to make the description easy to understand, a cryptographic system of the present invention using a simple Petri net as a key generator will be described. First, the creation of the public key and the private key will be described. FIG. 2 is a diagram showing a Petri net used as a key generator in the present embodiment, and the PT connection matrix N of the Petri net in FIG. 2 is represented by Formula 1. The hash function H used in this embodiment is Equation 2, where the elements of the vector C are Equation 3, and the public key of this embodiment is <N, H>.
It is represented by.

[0024]

[Equation 1]

[0025]

[Equation 2]

[0026]

[Equation 3] The Petri net shown in FIG. 2 has 16 primary T-ins shown in Table 1.
With variants, these elementary T-invariants are obtained during the generation of Petri nets. Table 2 shows the inverse hash function (Equation 4). This table shows the value of the hash function H and the elementary Ti.
Shows the correspondence with nvariant. In this way, the secret key (Equation 5) of this embodiment is determined. It should be noted that these two pieces of information are arranged in the ascending order of V _i so that the inverse hash function can be efficiently executed in a short time, as described later.

[0027]

[Table 1]

[0028]

[Table 2]

[0029]

[Equation 4]

[0030]

[Equation 5] Next, the encryption of the plaintext P will be described. Plaintext P is "I lo
ve you ”, encryption shall be performed twice, and the private key cryptosystem used shall be DES. A: First encryption (1) First, the primary T-invariant is randomly calculated from the PT connection matrix N of the Petri net as the first encryption key,
I got the number 6.

[0031]

[Equation 6] (2) The plaintext P was encrypted using the mathematical expression 6 as the DES encryption key, and the ciphertext shown in Table 3 was obtained.

[0032]

[Table 3] (3) The hash value of the encryption key (Equation 6) was calculated using the hash function (Equation 2), and Equation 7 was obtained.

[0033]

[Equation 7] (4) The ciphertext in Table 3 and the hash value of the encryption key (Equation 7) were combined to obtain the combined ciphertext C ₁ in Table 4 as the result of the _first encryption.

[0034]

[Table 4] B: Second encryption In the second encryption, the operations (1) to (4) are performed as in the first encryption. That is, (1) an elementary T-invariant was randomly calculated as the second encryption key from the PT connection matrix N of Petri net, and Equation 8 was obtained. (2) C ₁ (Table 4) was treated as the original text, and encryption was performed using Equation 8 as the encryption key, and the ciphertext of Table 5 was obtained. (3) The hash value of the encryption key (Equation 8) was calculated using the hash function (Equation 2), and Equation 9 was obtained.
(4) Similar to the first time, the ciphertext in Table 5 and the hash value of the encryption key (Equation 9) were combined to obtain the combined ciphertext C ₂ in Table 6.

[0035]

[Equation 8]

[0036]

[Table 5]

[0037]

[Equation 9]

[0038]

[Table 6] Thus, the final combined ciphertext of Table 6 C = C ₂
And the sender sends the final combined ciphertext C = C ₂ to the receiver.

Next, the decoding will be described. The decryption is also repeated as many times as the encryption, just like the encryption. A: 1-time decoding (1) from the ciphertext C = C ₂ combined received extracts the hash value of the encrypted and the encryption key (number 10).

[0040]

[Equation 10] (2) Using the inverse hash function, we obtained the elementary T-invariant of Eq. 11 from the hash value of the encryption key (Eq. 10).

[0041]

[Equation 11] Here, a specific execution of the inverse hash function will be described. That is, (a) the hash value of the encryption key of Expression 10 is searched from the inverse hash function table shown in Table 2 by the binary search. This search by arranging V _i in ascending order, O (log |
It requires only the calculation time of T |) and can be performed in a short time. Then, in (b) Table 4, from the elementary T-invariant placed on the right side of the hash value, the elementary T-inv corresponding to the hash value
Find an ariant. As described above, the encryption key can be restored. (3) The decrypted text of Table 7 was obtained by decrypting the encrypted text using the equation 11 as the decryption key of DES.

[0042]

[Table 7] B: Second Decoding Similarly to the first decoding, the operations (1) to (3) are repeated for the second decoding. That is, (1) the ciphertext (1
The encrypted text and the hash value of the encryption key (Equation 12) are extracted from the decrypted text of the second time. (2) Using the inverse hash function, from the hash value (12) of the encryption key, the elementary T-
got an invariant. (3) The ciphertext was decrypted by using the number 13 as the decryption key of DES, and the decrypted text of Table 8 was obtained. The decrypted text in Table 8 matches the plaintext P created by the sender.

[0043]

[Equation 12]

[0044]

[Equation 13]

[0045]

[Table 8] The present embodiment is a very simple example of performing two-stage encryption using two randomly generated encryption keys by a key generation means using a Petri net having 16 elementary T-invariants. However, according to the present invention, specifically, it is possible to perform multi-stage encryption with a plurality of encryption keys generated by the key generation means, using a key generation means capable of generating a plurality of encryption keys as a public key. It is a demonstration. Although the embodiments of the present invention have been described above, it is obvious that various changes may be made in the form and details without departing from the spirit and scope of the present invention defined in the claims. .

For example, with respect to the Petri net PT concatenation matrix, the size of 9 × 5 is used in the embodiment.
In order to increase the encryption strength, it is desirable that the size be several hundreds × thousands. Further, although the embodiment in which the Petri net is used as the key generation means has been described, for example, the conventional encryption key generator may be implemented as the key generation means which is the public key of the present invention, and is used in the embodiment. DE as a means of encryption
S, the hash function as the encryption key protection means, does not limit the present invention at all.

[0047]

As described above in detail, according to the present invention, by using the key generation means capable of generating a plurality of encryption keys as the public key, even in the mode of only one-stage encryption,
It is possible to obtain higher security than conventional ciphers, and further, in the form of multi-stage encryption with a plurality of encryption keys, the security strength of ciphertexts can be accumulated in an exponential order, and even in quantum computers. There is an effect that it is possible to provide an encryption device, a decryption device, an encryption / decryption device, and an encryption system having a high encryption strength that can be endured.

[Brief description of drawings]

FIG. 1 is a conceptual diagram for explaining an embodiment of a cryptographic system of the present invention.

FIG. 2 is a diagram showing a Petri net used as a key generator in the embodiment of the present invention.

Claims (10)

[Claims] 1. A key generation means capable of generating a plurality of encryption keys, an encryption means for encrypting an original text using the encryption key generated by the key generation means, and a key protection means protected from the encryption keys. And an encryption key protection unit that creates an encryption key, wherein the key generation unit and the encryption key protection unit are public keys. 2. The plain text is used as a first original text, the key generation means sequentially generates a plurality of encryption keys, the plurality of encryption keys are sequentially used, and the original text is generated by the encryption means. An encrypted ciphertext is created, a protection encryption key is created from the encryption key used for the encryption by the encryption key protection means, and the encryption text and the protection encryption key are used as the next original text. 2. The plaintext is encrypted in multiple stages by repeating the encryption of 1.
The encryption device described. 3. The encryption device according to claim 1, wherein the key generation unit is a key generation unit that generates an encryption key using a Petri net. 4. The encryption apparatus according to claim 3, wherein the encryption key is a randomly extracted elementary T-invariant (fundamental periodic element) of a Petri net. 5. The encryption means is an encryption means using a secret key encryption such as DES.
The encryption device according to claim 4. 6. The encryption device according to claim 1, wherein the encryption key protection unit is an encryption key protection unit using a hash function. 7. A decryption device for decrypting the ciphertext by receiving the ciphertext created by the encryption device according to any one of claims 1 to 6 and a protection encryption key, It has an encryption key restoration means for decompressing the protection encryption key and restoring the encryption key, the key generation means and the encryption key protection means are public keys, and the encryption key restoration means is a secret key. A decoding device characterized by the above. 8. The decryption device according to claim 7, wherein the encryption key restoration means is an encryption key restoration means using an inverse hash function. 9. An encryption / decryption device, characterized in that the encryption device according to any one of claims 1 to 6 and the decryption device according to claim 7 or 8 are integrally configured. apparatus. 10. A public-key cryptosystem, comprising:
An encryption device according to any one of claims 1 to 6, or an encryption / decryption device according to claim 9, a ciphertext created by the encryption device or the encryption / decryption device, and a protection encryption key. To a destination, a receiving means for receiving the ciphertext and the protection encryption key transmitted via the transmission means, and a ciphertext and the protection encryption key received via the receiving means. The decryption device according to claim 7 or 8 or the encryption according to claim 9 for decrypting the ciphertext in response to
A cryptographic system comprising a decryption device.