JP2002287618A - Alternate password system - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a password system which is on password technology as information security technology, especially on technology for improving the safety of an existed block password, doubles the key size of the existed password, has safety corresponding to the key size, has safety equal to and over the existed password, has interchangeability with the existed password and is superior in efficiency by the minimum constitution of ciphering for two times. SOLUTION: A password device includes the respective steps of (1) initialization setting, (2) ciphering by a user u1 and (3) decoding by a user u2. Thus, the password system which makes the key size of the existed password twice, has safety corresponding to the key size, can prove that it has safety equal to and over the existed password, has interchangeability with the existed password and is superior in efficiency by the minimum constitution of ciphering for two times can be supplied.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an encryption technology as an information security technology, and more particularly to a technology for improving the security of an existing block cipher.

[0002]

2. Description of the Related Art A block cipher is an encryption method in which data is divided into blocks of a fixed size, and encryption is performed for each block using a key secretly shared by a sender and a receiver of communication. It is. The security of a block cipher depends on the key size. Therefore, by combining the same block cipher a plurality of times and increasing the size of the key to be used, the security of the block cipher can be improved. FIG. 2 is an example of a conventional combination method. Conventionally, a combination method in which the result of once encryption is again encrypted is mainly used.

When a cryptographic system with improved security is configured by combining existing block ciphers, the performance to be realized is that the key is long and that the security according to the key size is provided. , The relationship between the security of the existing cipher and the security of the existing cipher can be proved, the compatibility with the existing cipher is excellent, and the efficiency is excellent.

[0004] However, there is no conventional system that satisfies these five points simultaneously.

[0005]

SUMMARY OF THE INVENTION The present invention has been made in view of the problems in the prior art, and has doubled the key size of the existing encryption, has security corresponding to the key size, and It can be proved that it has security equal to or higher than encryption,
It is an object of the present invention to propose an encryption system that is compatible with existing encryption and that is highly efficient with a minimum configuration of two encryptions.

[0006]

According to the present invention, in order to solve the above-mentioned problems, according to the present invention, K1 and K2 are each a secret key of a block cipher, k is a key length of a block cipher,
Let E and D be the encryption and decryption functions of the block cipher, m be the block length of the block cipher, m be equal to or longer than k, IV be the initial value of m bits, a, b , C are each an arbitrary value of m bits,
f1 and f2 are functions of fi (a, b) = c (i = 1, 2), and g1 and g2 are gi (a, fi (a, b)) = b (i = 1, 2). The user u1 who wants to secretly transmit data P to the user u2 as a function has a memory unit for generating and storing an IV, a communication unit for notifying the user u2 of the IV, and C = f2 (E (K1, IV), E (K2, f1 (E (K1, I
V), P))), and the output C is used as ciphertext as u2
The user u2 who has received the initial value IV and the ciphertext C uses the secret keys K1 and K2 to transmit P = g1 (E (K1, IV), D (K2, g2 (E2 (K1, IV),
C))), obtains the decrypted text P as its output, uses two keys K1 and K2, and inputs and outputs E (K1, IV ) To perform encryption and decryption.

According to a second aspect, there is provided an encryption apparatus to which the encryption method according to the first aspect is applied.

According to a third aspect of the present invention, there is provided a recording medium storing a program for executing the method according to the first aspect.

[0009]

FIG. 1 shows an encryption / decryption method according to the present invention. Hereinafter, the encryption and decryption methods will be described with reference to FIG. Initial setting The user u1 sets the bit string having the same length as the block length to IV.
And notifies the user u2. u1 and u2 secretly share the secret keys K1 and K2 of the block cipher.

[0010] Encryption Step 1. Let a, b, and c be arbitrary values of m bits, and let f1 and f2 be functions of fi (a, b) = c (i = 1, 2). Step 2. The user u1 uses K1 to make the block length of DES or the like equal to the key length, or to use a longer block cipher to obtain I
V is encrypted, and the result is set to r. Step 3. r and data P to be encrypted, f1 (r,
P) is calculated, and the result is set as x. Step 4. Using K2, x is encrypted by the same block cipher used in Step 2, and the result is set to y. Step5. f2 (r, y) is calculated from r and y, and the result is set as C. Step6. C is transmitted as an encrypted text to the user u2.

Decoding Step 1. Let a, b, and c be arbitrary values of m bits, and let g1 and g2 be functions such that gi (a, fi (a, b)) = b (i = 1, 2). Step 2. User u1 uses K1 to encrypt the IV with the same block cipher that the sender used for encryption,
Let the result be r. Step 3. From r and data C to be decrypted, g2 (r, C)
Is calculated, and the result is set as y. Step 4. Using K2, y is decrypted by the same block cipher used in Step 2, and the result is defined as x. Step5. g1 (r, x) is calculated from r and x, and the result is set as P. Step6. Let P be a decrypted text.

The embodiment of FIG. 1 performs encryption or decryption by two existing block ciphers in each of the encryption and decryption processes. Since two keys, K1 and K2, which are different from each other, are used for the two encryptions or decryptions, the key as the system connects the two (K1, K2).
And the key size is doubled

In this embodiment, an IV encryption result and P by an existing block cipher using K1 are input to a function f1, and the output thereof is input to an existing block cipher using K2. Further, the result of encryption by the existing block cipher using K2 and the result of IV encryption by the existing block cipher using K1 are input to a function f2, and the output thereof is C. Therefore, the attacker cannot know the input / output value of the existing block cipher using K2 from the values IV, P, and C that can be observed from outside the system.

At this time, the attack that can be performed by the attacker is as follows. Step 1. Choose an arbitrary m-bit value A. Step 2. E (K, IV) is calculated for all k-bit values K, and a result that matches P is set as a candidate for K1. Step 3. E (K, f1) for all k-bit values K
(A, P)) is calculated, and a result that matches g2 (A, C) is determined as a candidate for K2. Step 4. Whether the obtained (K1, K2) is a correct key is verified by another plaintext and ciphertext. Step5. If the verification fails, change A and repeat in the same manner.

The maximum calculation amount of this attack is 2 × 2 ＾ k = 2 ＾ (k + 1) per 2 ＾ m A, so that 2 ＾ m
(m + k + 1). This is the computational complexity of exhaustive search 2 ＾ (2
This attack is effective when k) is smaller, that is, when 2 ＾ (m + k + 1) <2 ＾ (2k). At this time, the relationship between m and k is as follows: m <k−1. Therefore, when this relationship does not hold, that is, when an existing block cipher whose block length is equal to or longer than the key length -1 is used, this attack requires more computation than the exhaustive search of (K1, K2). Therefore, the embodiment of FIG. 1 maintains security according to the key size.

In the embodiment, it is possible to prove that the security is equal to or higher than that of the existing encryption by assuming an algorithm that performs an operation equivalent to the encryption using K1. This proof is as follows.

The time required for one encryption of the existing encryption is used as a unit of the certification time. It is assumed that n is an arbitrary integer, and that the difficulty of encryption processing n times and the difficulty of decryption using n sets of (plaintext, ciphertext) are equal. It is assumed that the attacker can freely use the algorithm A that outputs E (K1, X) when an arbitrary m-bit value X is input. Let P1 be the maximum success probability of an attack that seeks (K1, K2) in n hours without using A. P2
Is the maximum success probability of an attack that seeks (K1, K2) in n hours using A. At this time, since the attack using A is not more difficult than the attack not using A, P1 ≦ P2. Assuming that the attacker can know the IV, P, and C, the attacker inputs the IV to A to obtain E (K1, IV).
You can know. If this value is Y, then the attacker can calculate P '= f1 (Y, P) and C' = g2 (Y, C). These P 'and C' are respectively equal to the input and output values of the existing cipher using K2 in the embodiment. Therefore, if A is always used, it is sufficient for the attacker to obtain only K2 from this (P ', C').
Clearly, let P3 be the maximum success probability of an attack that seeks only K2 in n hours using A. P2≤P3. Now that K1 and K2 are independent, even if an attacker uses A, he cannot obtain information about K2 from the result. Therefore, using A, (P ', C')
An attack that seeks only 2 is equivalent to an attack that seeks K2 from ciphertext C ′ = E (K2, P ′) using existing encryption using arbitrary P ′ and K2 without using A. Assuming that the maximum success probability of this attack is P4, P3 = P4. Therefore, P1 ≦ P2 ≦ P3 = P4. Therefore, the embodiment has security equal to or higher than that of the existing encryption.

In the embodiment, when K1 = K2 and IV is an arbitrary value x and r is a value decoded by K1, such that f1 (r, x) = f2 (r, x) = x Compatible with encryption. This r is, for example, f1 (r, x) = x + r (mod 2 ^ m), f2 (r,
If f1 and f2 of x) = xr (mod2 ^ m) are used, r = 0.

In the embodiment, since the key size is doubled by performing the encryption twice, the efficiency is excellent.

[0020]

As described above, according to the present invention, in comparison with the conventional method, the key length is longer, the security according to the key size is provided, and the security of the existing encryption is improved. It is possible to configure a cryptographic system that simultaneously satisfies the five points of being able to prove the relationship, being compatible with the existing cryptography, and being excellent in efficiency, and doubling the key size of the existing cryptography, It has the security according to the key size, it can be proved that it has the security equal to or higher than the existing encryption, it is compatible with the existing encryption, and the efficiency is excellent due to the minimum configuration of two encryptions This has the effect.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of an embodiment.

FIG. 2 is a configuration diagram of a conventional example.

Claims (3)

[Claims] 1. K1 and K2 are secret keys of a block cipher, k is a key length of a block cipher, E and D are an encryption function and a decryption function of a block cipher, respectively, and m is a block length of the block cipher. M is equal to or longer than k, IV is an initial value of m bits, a, b,
Let c be an arbitrary value of m bits, f1 and f2 be functions of fi (a, b) = c (i = 1, 2), and g1 and g2 be gi (a, fi (a, b) ) = B (i = 1, 2), and the user u1 who wants to transmit the data P secretly to the user u2 has a memory unit for generating and storing the IV, and transfers the IV to the user u2. A communication unit for notifying, C = f2 (E (K1, IV), E (K2, f1 (E (K1, I
V), P))), and the output C is used as a ciphertext as u2
The user u2 who has received the initial value IV and the ciphertext C uses the secret keys K1 and K2 to transmit P = g1 (E (K1, IV), D (K2, g2 (E2 (K1, IV),
C))), obtains the decrypted text P as its output, uses two keys K1 and K2, and inputs and outputs E (K1, IV ) To perform encryption and decryption. 2. An encryption device to which the encryption method according to claim 1 is applied. 3. A recording medium storing a program for executing the method according to claim 1.