JP2002175008A - Encryption method, encryption unit, and encryption and decoding system - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide an encryption and decoding system enabling configuration of a speedy and easy cryptographic system. SOLUTION: This encryption and decoding system is provided with an encryption unit, which has a dividing device 1 for dividing a plain text M into r-pieces of divided plaintexts (r is an integer larger than one); an encryption device 2 for ciphering n-pieces of the divided plain texts among the r-prices of divided plain texts (n<r) into n-pieces of ciphertexts according to an arbitrary encryption method, and which outputs the remaining (r-n) pieces of divided plain texts and the n-pieces of ciphertexts as output ciphertexts; and a decoding unit 20 for receiving the output ciphertexts as in put ciphertexts, and the decoding unit 20 comprises a decoding device 3 for decoding the n-pieces of ciphertexts of the input ciphertexts into the n-pieces of divided plaintexts, and a restoring device 4 for restoring the plaintexts M from the remaining (r-n) pieces of divided plaintexts of the input ciphertexts and the n-pieces of divided plain texts from the decoding device 3.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an encryption method, an encryptor, and an encryption and decryption system, and more particularly to a method for encrypting and decrypting an electronic document using a public key and a private key, thereby providing secret communication. And an encryption / decryption system (encryption information conversion device).

[0002]

2. Description of the Related Art In a conventional encryption method, a center having a conversion unit for converting encryption information used for decrypting cipher text is provided between a sender and a receiver, and the sender indicates the receiver. The receiver transmits the receiver information, the cipher text obtained by encrypting the information to be transmitted, and the first cipher information used for restoring the cipher text to the center. Respectively, and converts the first cipher information into second cipher information which can be restored by the receiver indicated by the receiver information by the conversion unit, and converts the second cipher information and the ciphertext into the receiver. And the receiver receives the second cipher information and the cipher text from the center, and obtains the original information by decrypting the cipher text based on the second cipher information. .

Further, an encryption / decryption system (encryption information conversion device) inputs an encryption information input section for inputting first encryption information encrypted using its own public key, and inputs an encryption key for its own secret key. Secret key input unit for decrypting, first decryption unit for decrypting the first encryption information using its own private key, receiver public key input unit for inputting the recipient's public key, and disclosure of this recipient An encryption unit that generates the second encryption information by encrypting the output from the decryption unit using the key.

[0004]

The problem with the conventional technology is that the amount of calculation required for encryption / decryption processing is orders of magnitude greater than that of symmetric key cryptography in public key cryptosystems that have been put into practical use. Largely, consequently, the use of public key cryptography is mainly limited to digital signatures or key distribution.

SUMMARY OF THE INVENTION It is therefore an object of the present invention to provide an encryption method, an encryptor, and an encryption and decryption system which can constitute a high-speed and simple encryption system.

Another object of the present invention is to propose a method for constructing a high-speed and simple meta-encryption system including any secure public key cryptosystem as a constituent element based on the Chinese Remainder Theorem. .

Another object of the present invention is to propose a method for configuring a high-speed and simple meta-cryptographic system including any secure public key cryptosystem as a component based on the Hadamard transform.

[0008]

According to a first aspect of the present invention, a step of dividing a plaintext M into r (r is an integer of 2 or more) divided plaintexts; n (n
<R) encrypting the divided plaintext into n ciphertexts, and outputting the remaining (rn) divided plaintexts and the n ciphertexts as output ciphertexts. Is obtained.

According to a second aspect of the present invention, the plaintext M is represented by r
(R is an integer of 2 or more) divided device for dividing into plaintexts, and an encryption device for encrypting n (n <r) divided plaintexts out of r divided plaintexts into n ciphertexts And outputting the remaining (rn) divided plaintexts and the n ciphertexts as output ciphertexts.

According to a third aspect of the present invention, the plaintext M is represented by r
(R is an integer equal to or greater than 2) a dividing device that divides the plaintext into n divided plaintexts, and converts n (n <r) divided plaintexts out of the r divided plaintexts into n encrypted plaintexts by an arbitrary encryption method. An encryption device for encrypting a sentence, and an encryptor for outputting the remaining (rn) divided plaintexts and the n ciphertexts as output ciphertexts; A decryptor that receives as ciphertext; the decryptor decrypts the n ciphertexts of the input ciphertext into the n divided plaintexts. A decryption device, and a restoration device for restoring the plaintext M from the remaining (rn) divided plaintexts of the input ciphertext and the n divided plaintexts from the decryption device. And an encryption and decryption system characterized by

According to a fourth aspect of the present invention, the above-mentioned third aspect is provided.
In the encryption and decryption system according to the above aspect, the dividing device converts the r divided plaintexts into C1, C2, ..., C (r-1), Cr
Then, there are r natural numbers N _i (i = 1, 2,..., R) that have no common divisor with each other, that is, gcd
_{(N i, N j)} If = 1 is the greatest common divisor of _{N i} and _{N j} denote the it is 1, gcd _{(N i, N j)} = 1
R natural numbers N satisfying (i ≠ j, i, j = 1, 2,..., R)
_i (i = 1, 2,..., r), expressed as follows: C 1 = M mod N ₁ , C 2 = M mod N ₂ ,..., C (r−1) = M mod According to N _r−1 , Cr = M mod N _r , the plaintext M is divided into r divided plaintexts C1, C2,..., C (r−
1) An encryption and decryption system characterized by dividing into Cr is obtained.

According to a fifth aspect of the present invention, the above-mentioned fourth aspect is provided.
In the encryption and decryption system according to the aspect, the product N of the r natural numbers N _i (i = 1, 2,..., R) is represented by N = N ₁ · N ₂ ···· N _r−1 · N _r Where, the plain division M is an integer satisfying log ₂ M ≦ log ₂ N, the encryption function Er () of any public key cryptosystem modulo Nr is the public key, and the encryption function Er () An encryption / decryption system characterized by using the decryption function Dr () as a secret key is obtained.

According to a sixth aspect of the present invention, the fifth aspect
In the encryption and decryption system according to the aspect, the encryption device encrypts Cr, which is a part of the plaintext M, to Br by Br = Er (Cr), and the encryptor performs C =
(C1, C2,..., C (r-1), Br) is output as an output ciphertext.

According to a seventh aspect of the present invention, the above-mentioned sixth aspect is provided.
In the encryption and decryption system according to the aspect, the decryption device obtains Cr by Cr = Dr (Br), and the decompression device obtains C1 = M mod N ₁ , C 2 = M mod N ₂ ,. , C (r−1) = M mod N _r−1 , Cr = M mod N _r to obtain an encryption and decryption system characterized by restoring the plaintext M.

According to an eighth aspect of the present invention, the above-mentioned sixth aspect is provided.
In the encryption and decryption system according to the aspect, the decryption device obtains Cr by Cr = Dr (Br), and the decompression device obtains C1 = M mod N ₁ , C 2 = M mod N ₂ ,. , C (r−1) = M mod N _r−1 , Cr = M mod N _r , and applying the Chinese remainder theorem to restore said plain M, A decoding system is obtained.

According to a ninth aspect of the present invention, the third aspect
In the encryption and decryption system according to the aspect, the dividing device divides the plaintext M into r plaintexts U1, U2,..., Ur, and converts U1, U2,. .., Vr expressed as H (r, r) · (U1, U2,..., Ur) = (V1, V2,..., Vr) by V1, V2,.
Is output as the r divided plaintexts, thereby obtaining an encryption / decryption system.

According to a tenth aspect of the present invention, in the encryption and decryption system according to the ninth aspect described above, the encryption device performs encryption using any public key encryption method modulo Vr. Using the function Er () as a public key, Br = Er (Vr) encrypts Vr, which is a part of the plaintext M, to Br, and the encryptor encrypts V = (V1, V2,..., V (r- 1), Br) is output as an output ciphertext, thereby obtaining an encryption and decryption system.

According to an eleventh aspect of the present invention, in the encryption and decryption system according to the tenth aspect,
The decryption device uses the decryption function Dr () for the encryption function Er () as a secret key and obtains Vr by Vr = Dr (Br). The decompression device obtains V1, V2,..., V (r− 1), Vr is expressed as H ⁻¹ (r, r) · (V 1, V 2,..., Vr) = (U ¹ ) by the inverse matrix H ⁻¹ (r, r) of the Hadamard transform matrix H (r, r). U2,..., Ur represented by U2,..., Ur) and restore the plaintext M to obtain an encryption and decryption system.

[0019]

Next, the present invention will be described in detail.

In the present invention, the average M is represented by C1, C2,.
(r-1), Cr and r, and only Cr is Br = Er (Cr) by an arbitrary encryption method (encryption function Er ()).
And C = (C1, C2,..., C (r-1), Br) as an encrypted text.

At this time, M is not decoded from C.

Further, Cr = Dr (Br) is obtained by a decoding function Dr () for Er (), and the above-mentioned plain M is restored.

Assume that the encryption function Er () is a one-way function. At this time, M cannot be obtained from (C1, C2,... C (r-1), Br) by the Chinese remainder theorem (or Hadamard transform).

Thus, the scheme is proven to be secure in the sense that it will not be completely decrypted. Part of the information of M is more informational than C1, C2, ..., C (r-1).
Although it is leaked, a part of the average is not explicitly decrypted.

The larger the value of r, the smaller the amount of treatment per bit of the average M and the higher the speed. r is determined in consideration of an appropriate size as an average.

Next, embodiments of the present invention will be described with reference to the drawings.

Referring to FIG. 1, an encryption and decryption system according to a first embodiment of the present invention comprises an encryptor 10;
And a decoder 20.

The encryptor 10 is configured to divide the plaintext M into r (r is an integer of 2 or more) divided plaintexts, and to divide n (n <r) of the r divided plaintexts. An encryption device 2 for encrypting the plaintext into n ciphertexts by an arbitrary encryption method, and output encryption of the remaining (rn) divided plaintexts and the n ciphertexts Output as a statement.

The decryptor 20 receives an output ciphertext as an input ciphertext. Then, the decryptor 20 decrypts the n ciphertexts of the input ciphertext into the n divided plaintexts, and the remaining (r−n) of the input ciphertext.
A restoring device 4 for restoring the plaintext M from the divided plaintexts and the n divided plaintexts from the decryption device.

In the following, the description will be made assuming that the encryptor 10 divides the average M into r pieces and encrypts one of them by the encryption device 2 using an arbitrary encryption method.

The encryptor 10 comprises a dividing device 1 and an encrypting device 2 as shown in FIG.

The dividing device 1 calculates gcd (N _i , N _j ) = 1 (i
R natural numbers N _i (i that satisfy ≠ j, i, j = 1, 2,..., R)
= 1,2, ..., r) N = N ₁ · N ₂ · · · · N _r-1
Against · _{N r,} the plaintext M is an integer satisfying _{log 2 M ≦ log 2 N,} C1 = M mod N 1, C2 = M mod N 2, ···, C (r-1) = M mod N the plaintext M as _{r-1, Cr = M mod} N r is divided into r pieces.

However, gcd (N _i , N _j ) = 1 means that _Ni and N
It means that the greatest common divisor with _j is 1. Gc
d stands for Greatest Common Divisor.

That is, gcd (N _i , N _j ) = 1 (i ≠
j, i, j = 1, 2,..., r) r natural numbers N _i (i =
1, 2,..., R) can also be referred to as r natural numbers N _i (i = 1, 2,..., R) that have no common divisor with each other.

The encryption device 2 uses an encryption function Er () of an arbitrary public key cryptosystem using Nr as a public key, and Br
= Er (Cr) encrypts Cr, which is a part of the plaintext M, into Br.

Finally, the encryptor 10 calculates C = (C1, C2,
.., C (r-1), Br) are output as ciphertext.

The decoder 20 comprises a decoding device 3 and a restoration device 4, as shown in FIG.

The decryption device 3 decrypts Cr by Cr = Dr (Br) using the decryption function Dr () for the encryption function Er () as a secret key.

The recovery unit _{4, C1 = M mod N 1,} C2 = M mod N 2, ···, C (r-1) = M mod N r-1, Chinese remainder to Cr = M mod N _r Restore the equivalence M by applying the Chinese remainder theorem. The Chinese Remainder Theorem is also called the Sun Tzu Remainder Theorem in China. Using the Chinese remainder _{theorem, C1 = M mod N 1,} C2 = M mod N 2, ·
.., Cr = M modN M is uniquely determined from _r .

Next, the operation of the first embodiment will be described.

As a specific example, when r = 3, M = 1
A case where 024 is divided, encrypted, decrypted, and restored will be described.

N ₁ = 7, N ₂ = 11, N ₃ = 15 (= 3 * 5) N = 7 * 11 * 15 = 1155 M = 1024.

C1 = M mod N ₁ = 1024 mod 7 = 2 mod 7 C2 = M mod N ₂ = 1024 mod 11 = 1 mod 11 C3 = M mod N ₃ = 1024 mod 15 = 4 mod 15 Encrypt with key encryption.

B3 = E3 (C3) C = (C1, C2, B3) is sent as a ciphertext.

Decode B3 into C3.

C3 = D3 (B3) C1 = 2 mod 7 C2 = 1 mod 11 C3 = 4 mod 15 By using the Chinese remainder theorem, M = 1024 is restored.

The Chinese Remainder Theorem will be described below.

Ni = N / N _i where n1 = N / N ₁ = 1155/7 = 165 n2 = N / N ₂ = 1155/11 = 105 n3 = N / N ₃ = 1155/15 = 77 ni * xi = 1 mod N _i where x1 = 2, x2 = 2, x3 = 8 M = C1 * n1 * x1 + C2 * n2 * x2 + ... + Cr * nr * xr (mod N) = 2 * 165 * M = 1024 is obtained from 2 + 1 * 105 * 2 + 4 * 77 * 8 (mod 1155) = 3334 (mod 1155) = 1024 (mod 1155).

Next, an encryption and decryption system according to a second embodiment of the present invention will be described.

This encryption and decryption system comprises an encryptor 10 'shown in FIG. 4 and a decryptor 20' shown in FIG.
And

In FIG. 4, the encryptor 10 'is a
Is divided into r (r is an integer of 2 or more) divided plaintexts, and n (n <r) divided plaintexts out of the r divided plaintexts are divided by an arbitrary encryption method. and an encryption device 2 ′ for encrypting into n ciphertexts, and the remaining (r−
The n) divided plaintexts and the n ciphertexts are output as output ciphertexts.

In FIG. 5, a decryptor 20 'receives an output cipher text as an input cipher text. And the decoder 2
0 ′ is a decryption device 3 ′ for decrypting the n ciphertexts of the input ciphertext into the n divided plaintexts, and the remaining (r−n) divided plaintexts of the input ciphertext. A restoring device 4 'for restoring the plaintext M from the n divided plaintexts from the decoding device.

In the following, the description will be made assuming that the encryptor 10 'divides the average M into r pieces, and encrypts one of them by the encryption apparatus 2' using an arbitrary encryption method.

In FIG. 4, an encryptor 10 'includes a dividing device 1' and an encrypting device 2 '.

The dividing device 1 ′ converts the plaintext M into r plaintexts U.
.., Ur, and U1, U2,.
Is converted to V1, V2,..., Vr expressed as H (r, r) · (U1, U2,..., Ur) = (V1, V2,..., Vr) by the Hadamard transformation matrix H (r, r). , V1, V2, ..., Vr
Is output as r divided plaintexts.

The encryption device 2 ′ uses an encryption function Er () of an arbitrary public key cryptosystem using Vr as a public key, and Br
= Er (Vr) encrypts Vr that is part of the plaintext M.

Finally, the encryptor 10 'determines that V = (V1, V
2,..., V (r-1), Br) are output as output ciphertext.

In FIG. 5, the decryption device 3 'uses the decryption function Dr () for the encryption function Er () as a secret key,
Vr is obtained by Vr = Dr (Br).

.., V (r-1), Vr
By the inverse matrix H ⁻¹ (r, r) of the Hadamard transform matrix H (r, r), H ⁻¹ (r, r) · (V1, V2,..., Vr) = (U1, U2,. , Ur expressed as U1, U2,..., Ur, and the plaintext M is restored.

Next, the operation of the second embodiment will be described.

As a specific example, assuming that r = 4, M = 1234 is divided,
Encrypt, decrypt and restore.

The division is made such that U1 = 1, U2 = 2, U3 = 3, U4 = 4.

According to the Hadamard transformation matrix H (r, r), H (r, r) ・ (U1, U2, U3, U4) = (V1, V2, V3, V4).

Since r = 4, the Hadamard transform matrix H
(r, r) is H (4,4) = ((1, 1, 1, 1), (1, -1, 1, -1), (1, 1, -1,-
1), (1, -1, -1, 1)).

[0065] V4 = -4 is encrypted by an arbitrary public key cryptosystem.

B4 = E4 (-4) V = (V1, V2, V3, B4) = (10, -2, 0, B4) is sent as a ciphertext.

Decode B4 to V4.

V 4 = D 4 (B 4) = − 4 By the inverse matrix H ⁻¹ (4,4) of the Hadamard transform matrix H (4,4), H ⁻¹ (4,4) · (V 1, V 2, V 3, V4) = (U1, U2, U3, U4).

Since r = 4, the inverse matrix H ⁻¹ (4,4) is H ⁻¹ (4,4) = (1/4) ((1, 1, 1, 1), (1, − 1, 1, -1), (1,
1, -1, -1), (1, -1, -1,1)).

H ⁻¹ (r, r) · (V1, V2, V3, V4) = H ⁻¹ (4,4) · (10, −2,0, −4) = (1,2,3) 4) M = 1234 is obtained from = (U1, U2, U3, U4).

[0071]

As described above, the first embodiment according to the present invention is described.
The effect is safety.

The plaintext M is confidential to anyone other than the decryptor with uncertainty of only Nr (or Vr).

Further, since the complete unidirectionality of Er () is not actually guaranteed, for example, RSA (Rivest-Shamir-Adle
It is also conceivable to use two or more types of public key cryptosystems, such as man) cryptography and elliptic ElGamal cryptography, while considering the trade-off between complexity and processing speed.

The second effect of the present invention is high speed.

If r = 10, the encryption / decryption processing speed is 1
It is expected to improve by almost 0 times.

[Brief description of the drawings]

FIG. 1 is a block diagram of an encryption and decryption system according to a first embodiment of the present invention.

FIG. 2 is a block diagram of an encryptor 10 in the encryption and decryption system of FIG.

FIG. 3 is a block diagram of a decryptor 20 in the encryption and decryption system of FIG.

FIG. 4 is a block diagram of an encryptor 10 ′ in an encryption and decryption system according to a second embodiment of the present invention.

FIG. 5 is a block diagram of a decryptor 20 ′ in the encryption and decryption system according to the second embodiment described above.

[Explanation of Code] 1 Dividing device 2 Encrypting device 3 Decrypting device 4 Restoring device 10 Encrypting device 20 Decrypting device 1 'Dividing device 2' Encrypting device 3 'Decrypting device 4' Restoring device 10 'Encrypting device 20 'decoder

Continued on the front page (71) Applicant 000006297 Murata Machinery Co., Ltd. 3 Minami-Ochiai-cho, Kichijo-in, Minami-ku, Kyoto-shi, Kyoto (72) Inventor Shigeo Tsujii 4-2-19-1 Jingumae, Shibuya-ku, Tokyo (72) Inventor Matsuoka Kenshi 1-18-6 Shinkiba, Koto-ku, Tokyo NFC Soft Co., Ltd. F term (reference) 5J104 AA18 JA26 NA02

Claims (11)

[Claims] 1. A step of dividing a plaintext M into r (r is an integer of 2 or more) divided plaintexts, and dividing n (n <r) divided plaintexts of the r divided plaintexts into n encrypted plaintexts An encryption method, comprising: encrypting a sentence; and outputting the remaining (rn) divided plaintexts and the n ciphertexts as output ciphertexts. 2. A dividing device for dividing a plaintext M into r (r is an integer of 2 or more) divided plaintexts, and n divided plaintexts (n <r) out of the r divided plaintexts are divided into n divided plaintexts. An encryption device comprising: an encryption device for encrypting a ciphertext; and outputting the remaining (rn) divided plaintexts and the n ciphertexts as output ciphertexts. 3. A dividing device for dividing a plaintext M into r (r is an integer of 2 or more) divided plaintexts, and an n (n <r) divided plaintexts out of the r divided plaintexts are arbitrarily set. An encryption device for encrypting into n ciphertexts by an encryption method, and outputting the remaining (rn) divided plaintexts and the n ciphertexts as output ciphertexts A decryptor that receives the output ciphertext as an input ciphertext; and wherein the decryptor converts the n ciphertexts of the input ciphertext to the n ciphertexts. a decryption device that decrypts the encrypted text into n divided plaintexts; and the remaining (rn) divided plaintexts of the input ciphertext and the n divided plaintexts from the decryption device, the plaintext M
And a restoring device for restoring the data. 4. The encryption and decryption system according to claim 3, wherein the dividing device divides the r divided plaintexts into C1, C2,..., C (r-1),
Assuming that Cr is r, natural numbers N _i (i = 1, 2,..., R) that do not have a common divisor with respect to any two are expressed by the following equation: C 1 = M mod N ₁ , C2 = M mod N ₂ ,..., C (r−1) = M mod N _r−1 , Cr = M mod N _r , the plaintext M is divided into r divided plaintexts C1, C2,. r-
1) An encryption and decryption system characterized by being divided into Cr. 5. The encryption and decryption system according to claim 4, wherein a product N of the r natural numbers N _i (i = 1, 2,..., R) is N = N ₁ · N ₂ ···. - when the _{N r-1} · N _r, the plaintext M is an integer satisfying log ₂ M ≦ log ₂ N, modulo Nr, encryption function Er any public key cryptosystem
An encryption and decryption system characterized in that () is a public key and a decryption function Dr () for the encryption function Er () is a secret key. 6. The encryption and decryption system according to claim 5, wherein the encryption device calculates the average of M by Br = Er (Cr).
, And encrypts Cr as Br, and the encryptor outputs C = (C1, C2,..., C (r-1), Br) as an output ciphertext. And decryption system. 7. The of Claim 6 encryption and decryption system, the decoding device obtains a Cr by Cr = Dr (Br), the restoration _{apparatus, C1 = M mod N 1,} C2 = _{M mod N 2, ···, C} (r-1) = M from _{mod N r-1, Cr =} M mod N r, encryption and decryption system, characterized by restoring the plaintext M. 8. A according to claim 6 encryption and decryption system, the decoding device obtains a Cr by Cr = Dr (Br), the restoration _{apparatus, C1 = M mod N 1,} C2 = M mod N ₂ ,..., C (r−1) = M mod N _r−1 , Cr = M mod N _r , and apply the Chinese remainder theorem to restore the equivalence M An encryption and decryption system, characterized in that: 9. The encryption and decryption system according to claim 3, wherein the dividing device converts the plaintext M into r plaintexts U1, U2,.
, And U1, U2,..., And Ur are transformed by the Hadamard transformation matrix H (r, r) into H (r, r) · (U1, U2,..., Ur) = (V1, V2,. .., Vr, and V1, V2,.
Is output as the r divided plaintexts. 10. The encryption and decryption system according to claim 9, wherein the encryption device uses an encryption function Er () of an arbitrary public key encryption method modulo Vr as a public key, and Br = Er (Vr)
And encrypts Vr, which is a part of the plaintext M, into Br, and the encryptor outputs V = (V1, V2,..., V (r-1), Br) as an output ciphertext. Encryption and decryption system. 11. The encryption and decryption system according to claim 10, wherein the decryption device uses a decryption function Dr () for the encryption function Er () as a secret key and Vr = Dr (Br). seeking vr, the restoration device, V1, V2, ..., V (r-1), the vr, the inverse matrix H Hadamard transform matrix ^{H (r, r) -1 (} r, r), H -1 (r1, r) · (V1, V2,..., Vr) = (U1, U2,..., Ur) expressed as (U1, U2,..., Ur) and restore the plaintext M. Encryption and decryption system.