JP2000244479A - Encryption method and device, and decryption method and device - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To enable more secure encryption with a simple configuration. SOLUTION: A structured key means 1, which is a weak encryption means, is connected in series with a strong encryption means 2 such as FEAL or DES. The structured key means 1 has a structure in which the key itself performs encryption, and is a key that is not disclosed. As the structured key means 1, it is more preferable to use a bit transposition in which there is no special relation between input and output. In this case, a decryption method is used in addition to checking both the strong encryption means 2 and the structured key means 1. No. If you have the number of bits of input and output B, in order to perform both tests, 2 ^B · ^B! Operations are required, and if B = 64 bits, 2 ^B · B! $ 10 Requires ¹⁰⁸ calculations. Stronger encryption can be performed with a simple configuration.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to an encryption method and apparatus and a decryption method and apparatus used for protecting data transmitted in a computer network system.

[0002]

2. Description of the Related Art Encryption technology prevents information from being stolen or leaked by an attacker, and enables reliable communication based on mutual authentication. In a large-scale distributed information communication network system that will arrive in earnest, the development and spread of such encryption technology is indispensable in order to protect information.

[0003] Encryption methods are roughly classified into a common key method (common key method) and a public key method. In the conventional key method, the encryption key and the decryption key are common. In the public key method, the encryption key and the decryption key are different, and the encryption key is made public.

[0004] Various encryption systems have been proposed. Among them, a practical code is a DES (Data Encryption Standard) in an encryption method of a conventional key method.
d) Method and FEAL (Fast Data Encipherment Algoli
sm) method, and in public key encryption method, RSA
(Rivest Shamir Adleman) system.

[0005] In the DES system and the FEAL system, encryption is performed by an algorithm for performing strong encryption. In such a strong encryption method, it can be said that the relationship between the input plaintext and the output ciphertext and the relationship between the key and the output ciphertext are randomly established. Such a relationship can be expressed as f (p, K) = Rand (p, K), where p is a plaintext to be input and K is a key.

Further, in such a strong encryption method, the bit change height of the output ciphertext with respect to the bit change height of the input plaintext and the bit change height of the output ciphertext with respect to the bit change height of the key are random. And f (Δp, ΔK) = Rand (Δp, ΔK).

In general, such an encryption algorithm has an involution structure. The involution structure is a structure where f = f ⁻¹ holds when c = f (p) and p = f ⁻¹ (c). In the case of having an involution structure, encryption and decryption can be performed by the same processing process. The algorithm that takes the EX-OR (the algorithm that performs the addition of mod2) is a simple example of the involution structure.

[0008]

Problems to be solved by the invention are as follows:
As described above, various things have been proposed. In order to ensure reliability and to share hardware, standardization of an encryption method is being studied.

However, with the development of computer technology, such as the development of a massively parallel processing computer, the above-mentioned conventional encryption system is no longer sufficiently secure. This is one obstacle in standardizing the encryption method.

That is, one barometer of the strength of encryption is the key bit length. In other words, the longer the bit length of the key, the lower the risk of being broken by exhaustion. Therefore, the encryption strength can be increased by increasing the bit length of the key.

However, when the number of bits of the key increases, the processing becomes complicated and cost performance deteriorates. As an appropriate compromise, the bit length is conventionally 64 bits in the DES system and the FEAL system.

[0012] In such a case, for example, in the DES method, in order to decrypt the encrypted with lice look crushed, there is a need for operation of 2 ⁵⁵ times. In FEAL, to decrypt the encrypted with lice look crushed, there is a need for operation of 2 ⁶⁴ times. Therefore, in the case of performing the calculation at a speed of 1 μs and performing the decoding at one time without performing the parallel processing, it takes about 1100 years in the DES system and about 510,000 years in the FEAL system to perform the decoding with exhaustion. Thus, the DES method and the FEAL method can be said to be sufficiently secure encryption.

[0013] However, the recent improvements in Konpita processing speed is remarkable, when the by carrying out calculation by parallel processing of ¹⁰⁶ becomes feasible, to perform decryption with lice seen crushed, the DES scheme 9. About 6 hours or 6.1 months will be good.

Accordingly, an object of the present invention is to provide an encryption method and apparatus capable of performing more secure encryption in preparation for a future increase in computation speed, such as the development of such a massively parallel computer, and decryption. It is to provide a method and an apparatus.

[0015]

According to the present invention, when an input code is x, a key code is k, a bit change height of an arbitrary input code is Δx, and a bit change height of an arbitrary key code is Δk, f = When encrypting the algorithm f such that f- ¹ or f- ¹ exists and f (x, k) = Rand (x, k) f (Δx, Δk) = Rand (Δx, Δk) Is an encryption method that uses a structured key that is independent of the algorithm key and that itself forms a bit transposition algorithm.

Further, according to the present invention, the input code is x, the key code is k, the bit change height of any input code is Δx,
When the bit change height of an arbitrary key code is Δk, f
= F ^-1 or f ^-1 exists, and the algorithm f is encrypted so as to satisfy f (x, k) = Rand (x, k) f (Δx, Δk) = Rand (Δx, Δk) This is an encryption device in which a processing circuit of an algorithm for performing bit transposition of an independent structured key is arranged in series with the encryption device.

Further, according to the present invention, the input code is x, the key code is k, the bit change height of any input code is Δx,
When the bit change height of an arbitrary key code is Δk, f
= F ^-1 or f ^-1 exists, and the decoding of the algorithm f is performed such that f (x, k) = Rand (x, k) f (Δx, Δk) = Rand (Δx, Δk) This is a decryption method that uses a structured key that is independent of the algorithm key and that itself forms a bit transposition algorithm as the key at that time.

Further, according to the present invention, the input code is x, the key code is k, the bit change height of any input code is Δx,
When the bit change height of an arbitrary key code is Δk, f
= F ^-1 or f ^-1 exists, and the decoding of the algorithm f is performed such that f (x, k) = Rand (x, k) f (Δx, Δk) = Rand (Δx, Δk) This is a decryption device in which a processing circuit of an algorithm for performing bit transposition of an independent structured key is arranged in series with the decryption device.

As described above, according to the present invention, the encryption strength is increased by adding the structured key of the encryption algorithm to the key itself in series with the algorithm that performs strong encryption such as the DES method or the FEAL method. Be strengthened.

[0020]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described in the following order. a. Encryption method to which the present invention can be applied a1. About structured key a2. Consideration when EX-OR is used as structured key a3. Considerations when using a bit translator as a structured key

A. Encryption method to which the present invention can be applied a1. Structured key In the modern cryptographic protocol, the following protocol is proposed in order to measure the reliability and security of cryptography. Encryption processing other than key is disclosed. No information is known other than the key exhaustion or computationally secure method.Considering such a protocol, consider a stronger encryption method. I will do it.

In the conventional encryption algorithm, the key is only a simple code. In order to perform stronger encryption, it is conceivable to additionally use a structured key.
That is, it is conceivable to provide a key having a structure in which the key itself performs encryption in series with a strong encryption algorithm such as the DES scheme or the FEAL scheme. The use of a structured key in this way would make decryption more difficult.

Such a structured key is kept secret. Then, all the encryption processes other than the structured key are disclosed in accordance with the modern encryption protocol. The structured key is desirably a simple structure because it is stored in a recording medium and kept secret.

FIG. 1 shows an encryption process using such a structured key. In FIG. 1, reference numeral 1 denotes a structured key unit, and 2 denotes an encryption unit. The structured key means 1 and the encryption means 2 are arranged in series. If the structured key means 1 and the encryption means 2 are arranged in series, the encryption means 2 may be arranged before the encryption means 2 or the structured means 1 may be arranged before and after the encryption means 2.
It is also conceivable to arrange

The structured key means 1 is for encrypting the input plaintext p by an algorithm g to generate an intermediate code p '. The algorithm used to encrypt the structured key 1 is kept secret.

The encryption means 2 is provided with the intermediate code p 'output from the structured key means 1 and the key K. The encryption means 2 converts the intermediate code p 'into the key K
Is used to perform strong encryption by the algorithm f to generate a ciphertext c. The algorithm of the encryption means 2 can be made public.

FIG. 2 shows a decryption process for decrypting a ciphertext encrypted using such a structured key. Decryption corresponds to the encryption process shown in FIG.

In FIG. 2, reference numeral 3 denotes decoding means, and 4 denotes structuring means. The decryption means 3 uses the key K to generate an intermediate code p 'from the ciphertext c by the algorithm f ^-1 . The structured key means 4 is provided with the intermediate code p 'decrypted by the decrypting means 3. Structured key means 4
Generates a plaintext p from the intermediate code p ′.
As a result, the plaintext p is decrypted from the ciphertext c.

Here, the algorithm f and the algorithm g will be described. The algorithm f performs strong encryption. This algorithm f satisfies the following conditions.

F = f ⁻¹ (involution structure)
Or f ^-1 is present. Assuming an input p ′ and a key K, f (p ′, K) = Rand (p ′, K) That is, the output f (p ′, K) randomly corresponds to p ′ and K. Assuming that the input bit change amount is Δp ′ and the key bit change amount is ΔK, f (Δp ′, ΔK) = Rand (Δp ′, ΔK) That is, for Δp ′ and ΔK, the output change amount is also random. Corresponding. Encryption can be expressed by c = f (p ′), and decryption can be expressed by p ′ = f ⁻¹ (c). However, if it is an involution structure, p '
= F (c). When the input p 'and the output c are known, the key K can be decrypted by exhaustive inspection of the key K, but when either p' or c is unknown, one of the key K and the key K cannot be decrypted. Take.

As such an algorithm f, DE
The S method or the FEAL method can be used.

The algorithm g performed by the structured key means 1 is as follows:
It has the following structure. g = g ⁻¹ or g ⁻¹ is present. For a bit change height Δp of the input p, g (Δp) ≠ Rand (Δp) may be satisfied. When both the input p and the output p ′ are known, the structure of g may be known, but when the structure of g and the variables in g are not known, one of p and p ′ may be known. , Can not know the other.

As the algorithm g, a very simple structure, for example, an EX-OR structure, a bit transposition, a substitution table, or the like can be considered. As described later, as the algorithm g used as the structured key, bit transposition is preferable.
With the -OR structure, encryption cannot be sufficiently strengthened.

A2. Consideration when EX-OR is used as a structured key As a structured key for encryption processing for performing strong encryption,
Consider a case in which an algorithm that takes an EX-OR using a key k that is selected at all at random is adopted.

FIG. 3 shows an example in which the structure of the EX-OR is used as the algorithm g of the structured key. In FIG. 3, reference numeral 11 denotes structured key means. In this case, the structured key means 11 is a circuit that performs an EX-OR of the key k and the input p. The encryption processing means 12
This is an encryption circuit that performs strong encryption such as the DES method or the FEAL method.

As described above, the encryption strength when the algorithm for taking the EX-OR is used as a structured key for the algorithm of the strong encryption method will be considered. It is assumed that f = f ⁻¹ for convenience. In the description below, the addition symbol “+” indicates exclusive OR.

In such encryption, the plaintext is p, EX-O
Assuming that the intermediate code output from the R circuit is p ′ and the ciphertext is c, c = f (p ′, K) and p ′ = p + k. Also, the decoding is: p = k + p ′, p ′ = f (c, k), where f is a random function. To summarize the above equations, encryption can be expressed as c = f (p + k, K) = Rand (p + k, K), and decryption can be expressed as p = k + f (c, K) = k + Rand (c, K).

The following can be understood from the above equation. In other words, the encryption procedure is based on a random function of two keys k and K, but the decryption procedure is based on a random function of one key K. Is necessary, but k does not have to be exhausted.

That is, in the direction of decoding, the following relationship holds: f (c, K) + p = k = constant. Because of this, attackers
I samples (c _i, P_i) And shown in FIG.
As described above, the circuit 13 for processing the algorithm f and the EX-
OR processing circuit 14
Key K can be searched. In other words, in the exhaustion of K, all
When the output becomes constant in i samples,
The outputs (k) and K are known as keys. So this
The number of decipherers of the method is i · 2^B(B: key and input / output
Number of bits in the code).

Since the function f is a random function, when the output (k) becomes constant once, the probability (error rate) that the output (k) and the key (K) are not real at that time is represented by the number of codes 2 equivalent to enough low probability 2 ^-B to take one of the code of ^B within the individual. In other words, it can be said that the decoding can be sufficiently performed even when i = 2.

From the above considerations, it is not possible to sufficiently enhance the encryption strength in the configuration in which the EX-OR is used as the structured key.

A3. Consideration when a bit translator is used as a structured key Let us consider a case where a bit translator is used as a structured key. As shown in FIG. 5, the bit translator randomly replaces each bit of the input code. The algorithm g (p) of the bit transpose can be expressed as g (p) = Rand (p) g (Δp) ≠ Rand (Δp) g ≠ g ⁻¹ .

FIG. 6 shows an encryption process when a bit translator is used as a structured key, and FIG. 7 shows a decryption process. In the encryption processing shown in FIG. 6, reference numeral 21 denotes a bit translator as structured key means. The bit transposition unit 21 transposes the input bits by the algorithm g. 22 is an encryption means. Encryption means 22
Performs strong encryption by the algorithm f. As this algorithm, the DES method or the FEAL method is used.

In the decoding process shown in FIG.
Reference numeral 3 denotes a decryption unit. The decryption unit 23 generates an intermediate code p ′ from the cipher text c by the algorithm f.
This intermediate code p 'is supplied to the inverse bit transposition unit 24,
The inverse bit translator 24 performs an inverse bit conversion by the algorithm g ^-1 .

In this case, the encryption of the encryption means 22 is f, the algorithm of the bit translator 21 is g, the input plaintext is p, the intermediate code is p ', and the ciphertext is c. f (p ', k) = f (g (p), K). The decoding can be expressed as p = g ^-1 (p ') = g ^-1 (f (c, K)).

Since the algorithm represented by f performs strong encryption, the bit change height (Δp or Δ
Since K and Δc) are randomly associated with each other, the key K of the algorithm f is determined by exhaustiveness and the connection of the algorithm g is determined by exhaustiveness against a decryption attack against the bit change height. Can't decipher it except Further, since the algorithm g has no special relation between its input and output, there is no decryption method other than the inspection of both the algorithm f and the algorithm g for attacks other than the attack with a high bit change after all. I can say.

Assuming that the number of bits of input and output is B, when the key K of the algorithm f is exhaustively searched, 2 ^B operations are required, and the number of exhaustions of the connection of the algorithm g is B! Since it is, in the case of performing the encryption in such an algorithm, to be decoded by the lice look crushed, both at 2 ^B · ^B
! Operations are required. If B = 64 bits, B! ≒ 10 ⁸⁹ 2B · B! ≒ 10 ¹⁰⁸ In this case, even if the processing speed is set to 1 μs and the parallel processing of 10 ⁶ is performed, it takes about 10 ⁸⁹ years to perform the decoding with exhaustion.

FIG. 8 shows an example of a configuration in which communication is performed by strengthening the encryption strength using the structured key. In FIG. 8, a computer system 31 that performs communication includes a structured key unit 32, a key management for managing the structured key unit 32, and a key management unit 3 for performing key management of an encryption / decryption device.
3 are provided. The structured key means 32 and the key management means 33 are processed by software, for example. Encryption /
The decoder 35 and the modem 36 are connected to a control line 37.
Through a computer system 31.

When data is output from the computer system 31 via the line 34, the data from the computer system 31 is converted into an intermediate code by the algorithm g of the structured key means 32. This intermediate code is supplied to the encryption / decryption unit 35. The data is encrypted by the encryption / decryption unit 35 by the algorithm f, and the encrypted data is output to the line 34 via the modem 36.

When the data transmitted via the line 34 is received by the computer system 31, the line 3
4 is supplied to the encryption / decryption unit 35 via the modem 36. In the encryption / decryption unit 35,
The data sent by the algorithm f is decrypted,
An intermediate code is generated. This intermediate code is supplied to the structured key means 32 of the computer system 31. The structured key means 32 decrypts the data from the intermediate code.

[0051]

According to the present invention, the DES system and the FEA
By adding the structured key of the encryption algorithm to the key itself in series with the algorithm that performs strong encryption like the L system, the encryption strength can be enhanced and the data security can be increased.

[Brief description of the drawings]

FIG. 1 is a block diagram used to explain encryption using a structured key.

FIG. 2 is a block diagram used for explaining encryption decryption using a structured key.

FIG. 3 is a block diagram used for description when an EX-OR is used as a structured key.

FIG. 4 is a block diagram used to explain decryption when an EX-OR is used as a structured key.

FIG. 5 is a schematic diagram used for describing a bit translator.

FIG. 6 is a block diagram used to explain an encryption process when a bit translator is used as a structured key.

FIG. 7 is a block diagram used for describing a decoding process when a bit translator is used as a structured key.

FIG. 8 is a block diagram showing an example configuration in which encryption / decryption is performed using a structured key.

[Explanation of symbols]

1 ... structured key means, 2 ... encryption means, 3 ...
Decryption means, 4 ... structured key means, 11 ... EX-OR circuit as structured key means, 14 ... EX-OR
Circuit, 21: bit transposition, 24: reverse bit transposition

Claims (4)

[Claims] When an input code is x, a key code is k, a bit change height of an arbitrary input code is Δx, and a bit change height of an arbitrary key code is Δk, f = f ⁻¹ or f ⁻¹ is obtained. The key of the above algorithm exists as a key at the time of encrypting the algorithm f such that f (x, k) = Rand (x, k) and f (Δx, Δk) = Rand (Δx, Δk). And an encryption method using a structured key independent of the key itself and forming a bit transposition algorithm. 2. When an input code is x, a key code is k, a bit change height of an arbitrary input code is Δx, and a bit change height of an arbitrary key code is Δk, f = f ⁻¹ or f ⁻¹ is obtained. Exists, and is independent in series with an encryption device that performs encryption of the algorithm f such that f (x, k) = Rand (x, k) and f (Δx, Δk) = Rand (Δx, Δk). An encryption device in which a processing circuit of an algorithm for performing bit transposition of a structured key is arranged. 3. When an input code is x, a key code is k, a bit change height of an arbitrary input code is Δx, and a bit change height of an arbitrary key code is Δk, f = f ⁻¹ or f ⁻¹ is obtained. Exists, and f (x, k) = Rand (x, k) The key of the above algorithm is used as a key when decoding the algorithm f so as to satisfy f (Δx, Δk) = Rand (Δx, Δk). And a decryption method using a structured key in which the key itself forms a bit transposition algorithm. 4. When an input code is x, a key code is k, a bit change height of an arbitrary input code is Δx, and a bit change height of an arbitrary key code is Δk, f = f ⁻¹ or f ⁻¹ is obtained. Exists, and is independent in series with a decoding device that decodes the algorithm f so as to satisfy f (x, k) = Rand (x, k) f (Δx, Δk) = Rand (Δx, Δk) A decryption device in which a processing circuit of an algorithm for transposing a bit of a structured key is arranged.