JP2012129920A - Compression and encryption apparatus, decoding and decompression apparatus, method therefor, and program - Google Patents

Abstract

A ciphertext of compressed data with high confidentiality is generated.
A compression encryption apparatus generates compressed data obtained by compressing data, generates padded compressed data obtained by concatenating padding data having a secret length to the compressed data, and encrypts the padded compressed data. Generate ciphertext. The decryption / decompression apparatus 20 decrypts the ciphertext to obtain padded compressed data, extracts a part of the padded compressed data as compressed data, and decompresses the compressed data.
[Selection] Figure 1

Description

  The present invention relates to a data compression / encryption technique and a ciphertext decryption / decompression technique obtained thereby.

  Data compression processing that reduces the amount of data while maintaining the meaning of the data is known (see, for example, Patent Documents 1 to 3, Non-Patent Document 1, etc.). Data compression methods are roughly classified into lossless compression processing and lossy compression processing, and there are various methods. Many data compression methods take a method of reducing the amount of data by using information that depends on the data content (that is, information specified from the data content) such as the number of repetitions of data, appearance frequency, and correlation between data. . In this case, the compression rate according to the data compression process differs depending on the data content, and the information of the data before compression may be obtained from the length (data length) of the compressed data (compressed data).

  In addition, an encryption process for encrypting data (plain text) and generating a cipher text in which the data is concealed is known (see, for example, Non-Patent Document 2). There are various encryption methods, and depending on the encryption method, information on the length of data (plaintext) may be obtained from the length of the ciphertext.

U.S. Pat. No. 4,464,650 U.S. Pat. No. 4,814,746 U.S. Pat. No. 4,558,302

P. Deusch, "RFC1951: DEFLATE Compressed Data Format Specification version 1.3" "ISO / IEC 10116: Information technology-Security techniques-Modes of operation for an n-nit block cipher"

  As a method of concealing data while reducing the amount of data, there is a compression / encryption method that further performs encryption processing on compressed data obtained by performing data compression processing on data (plain text). However, in the conventional compression / encryption method, information on data before compression may be known from the length of the ciphertext obtained by the encryption process. This is because information on the length of the compressed data may be obtained from the length of the ciphertext, and information on the data before compression may be obtained from the length of the compressed data.

  The present invention has been made in view of these points, and an object of the present invention is to provide a technique capable of generating a ciphertext of compressed data with high confidentiality.

  The compression / encryption technology of the present invention generates compressed data obtained by compressing data, generates padded compressed data obtained by concatenating padding data of a secret length to the compressed data, and encrypts the padded compressed data. Generate a statement.

  In the decryption / decompression technique of the present invention, the ciphertext is decrypted to obtain padded compressed data, a part of the padded compressed data is extracted as compressed data, and the compressed data is decompressed.

  Since the length of the padding data of the present invention is kept secret, the attacker cannot obtain the data information before compression from the length of the padded compressed data. Therefore, it is also impossible to obtain data information before compression from the length of ciphertext obtained by encrypting padded compressed data. As described above, in the present invention, it is possible to generate a ciphertext of compressed data with high confidentiality.

The block diagram for demonstrating the structure of the compression encryption apparatus of an embodiment, and a decoding expansion | extension apparatus. The block diagram for demonstrating the structure of the padded compressed data of embodiment. The block diagram for demonstrating the compression encryption method and decryption expansion method of embodiment.

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

<Configuration>
FIG. 1 is a block diagram for explaining the functional configuration of the compression / encryption device and the decryption / decompression device of this embodiment.

  As illustrated in FIG. 1, the compression / encryption device 10 of this embodiment includes a key memory 11, a memory 12, a control unit 13, a compression unit 14, a padding unit 15, an encryption unit 16, a positive integer input unit 17, and data. And an input unit 18. As illustrated in FIG. 1, the decryption / decompression apparatus 20 according to this embodiment includes a key memory 21, a memory 22, a control unit 23, a decryption unit 24, a compressed data extraction unit 25, and an expansion unit 26.

  The compression / encryption device 10 and the decryption / decompression device 20 read a predetermined program into a known or dedicated computer including, for example, a central processing unit (CPU), a random-access memory (RAM), a read-only memory (ROM), and the like. It is a special device that is configured by being executed. The processing unit such as the control unit 13, the compression unit 14, the padding unit 15, the encryption unit 16, the control unit 23, the decryption unit 24, the compressed data extraction unit 25, and the decompression unit 26 is, for example, a CPU that executes a predetermined program Or an integrated circuit. The key memories 11 and 21 and the memories 12 and 22 are, for example, a part of an auxiliary storage device, a RAM, a cache memory, a register, an integrated circuit, or a storage area obtained by combining at least a part of them. The positive integer input unit 17 and the data input unit 18 are, for example, an input terminal, an input interface, a data reading device, a CPU that executes a predetermined program, an integrated circuit, and the like. Although not described below, the compression / encryption apparatus 10 executes each process under the control of the control unit 13, and the decryption / decompression apparatus 20 executes each process under the control of the control unit 23. Data output from each processing unit is stored in the memories 12 and 22 one by one, and is read out from other processing units and used as necessary.

<Pre-processing>
As pre-processing for compression encryption processing and decryption / decompression processing of the present embodiment, a key for encryption is stored in the key memory 11 of the compression / encryption device 10, and a key for decryption is stored in the key memory 21 of the decryption / decompression device 20. Is stored. These keys correspond to the encryption methods used in the compression / encryption device 10 and the decryption / decompression device 20. For example, when the encryption method used is a public key encryption method such as RSA or ElGamal encryption, the public key is stored in the key memory 11 of the compression / encryption device 10 and the key memory 21 of the decryption / decompression device 20. Stores a secret key corresponding to the public key. For example, when the encryption method used is a common key encryption method such as Camellia (registered trademark) or AES, the key memory 11 of the compression encryption device 10 and the key memory 21 of the decryption expansion device 20 are the same. A common key is stored.

<Compression encryption processing>
The compression / encryption processing of this embodiment will be described with reference to FIG. 3A.

  An arbitrary positive integer N is input to the positive integer input unit 17 of the compression encryption apparatus 10 (FIG. 1). For example, the positive integer N may be a value that is randomly selected every time compression / encryption processing is performed, or may be a value that is commonly used for multiple compression / encryption processings. A fixed value common to all compression / encryption processes may be used. From the viewpoint of safety, it is desirable that the positive integer N is a fixed value. Further, from the viewpoint of safety, it is desirable that the positive integer N is a secret value independent of data M and its compressed data, which will be described later, and that the positive integer N does not include information on the data M and its compressed data. In this way, an arbitrary positive integer N given to the positive integer input unit 17 is sent to the padding unit 15 (step S11).

  Data M to be processed is input to the data input unit 18 and sent to the compression unit 14 (step S12).

  The compressing unit 14 compresses the data M to generate compressed data. The compression method used may be a lossy compression encoding method or a lossless compression encoding method. The compressed data is sent to the padding unit 15 (step S13).

  The padding unit 15 generates padded compressed data obtained by concatenating the compressed data with padding data having a secret length. “Secret length padding data” means padding data whose length is concealed outside the compression encryption apparatus 10. In this embodiment, it is assumed that the sum of the length of the compressed data and the length of the padding data is an arbitrary positive integer multiple (step S14).

[Specific example of step S14]
The padding unit 15 calculates the length C of the sent compressed data, encodes the data representing the length C with a fixed length, and sets the compressed data as length data. The length data of the compressed data is data of a fixed length L (L is a positive integer), and the fixed length L is determined in advance. An example of the data length is the bit length or octet length of the data.

  Next, the padding unit 15 calculates the length P of padding data (P is a positive integer) using the positive integer N and the length C of the compressed data. The length P of the padding data is determined such that P + C is a multiple N · A of a positive integer N (A is a positive integer) (P + C = N · A). If P + C is equal to or longer than the length of the data M, it is not meaningful to compress the data M in step S13. Therefore, P is preferably determined so that P + C is less than the length of the data M. For example, the padding unit 15 calculates the length P of the padding data according to the following formula.

P = N− {C mod N} (1)
Here, mod is a remainder operation, and N is 2 or more. In the case of equation (1), the greater the value of N, the higher the safety.

  Next, the padding unit 15 generates padding data having a length P. The padding data may be arbitrary data. Examples of padding data are data of length P consisting of continuous “0” bits, data of length P consisting of continuous “1” bits, and length P where “0” bits and “1” bits are mixed. Data.

  The padding unit 15 connects the length data of the compressed data, the compressed data, and the padding data in a predetermined order to generate padded compressed data. In this embodiment, for example, the compressed data is connected after the length data of the compressed data, and the padding data is connected after the compressed data. FIG. 2 is an example of the padded compressed data generated in this way. The padded compressed data 100 in this example is data obtained by concatenating length data 101 of length L compressed data, compressed data 102 of length C, and padding data 103 of length P. The length of data obtained by concatenating the compressed data 102 and the padding data 103 is N · A (end of description of [specific example of step S14]).

  The padded compressed data is sent to the encryption unit 16. The encryption unit 16 extracts a key for encryption from the key memory 11, encrypts the padded compressed data using the key, and generates a ciphertext E (M). The encryption unit 16 outputs the ciphertext E (M) (step S15).

<Decryption / decompression process>
The decryption / decompression process of this embodiment will be described with reference to FIG. 3B.

  The ciphertext E (M) is input to the decryption unit 24 of the decryption / decompression apparatus 20 (FIG. 1). The decryption unit 24 extracts a key for decryption from the key memory 21, and decrypts the ciphertext E (M) using the key to obtain padded compressed data. The padded compressed data is sent to the compressed data extracting unit 25 (step S21).

  The compressed data extraction unit 25 extracts a part of the padded compressed data as compressed data (step S22).

[Specific example of step S22]
The compressed data extraction unit 25 decodes the length data of the compressed data included in the padded compressed data to obtain the length C of the compressed data. In this embodiment, the order of connecting the compressed data length data, the compressed data, and the padding data is determined in advance, and the compressed data length data is a fixed length (length L). Therefore, it is possible to extract the length data of the compressed data from the padded compressed data and decode it to obtain the length C of the compressed data. For example, in the case of the padded compressed data 100 in FIG. 2, the compressed data extraction unit 25 extracts the data of length L from the head of the padded compressed data 100 as the compressed data length data 101 and decodes it. Thus, the length C of the compressed data can be obtained.

  Next, the compressed data extraction unit 25 uses the length C of the compressed data to extract the compressed data included in the padded compressed data. In this embodiment, since the order of connecting the compressed data length data, the compressed data, and the padding data is determined in advance, the compressed data can be extracted using the compressed data length C. For example, in the case of the padded compressed data 100 in FIG. 2, the compressed data extraction unit 25 can extract data having a length C that follows the length data 101 of the compressed data as the compressed data 102 ([specific example of step S22]). End of description).

  The compressed data 102 is sent to the decompression unit 26. The decompressing unit 26 decompresses the compressed data to obtain data M ′ and outputs it.

<Features of this embodiment>
In this embodiment, padding data whose length is secret is added to the compressed data, so even if the length information of the padded compressed data is obtained from the length of the ciphertext, the length information of the compressed data is obtained. This can be suppressed, and it can be suppressed that information relating to the content of the data before compression is obtained. Thereby, in this embodiment, a highly confidential ciphertext can be generated.

  In particular, when the length P of the padding data is determined as in Expression (1), the length P of the padding data can be limited to N or less. On the other hand, in this case, the greater the value of N, the higher the safety. That is, when the length P of the padding data is determined as in the expression (1), the balance between the safety and the length of the padded compressed data can be adjusted by adjusting the size of the positive integer N. .

  The present invention is not limited to the embodiment described above. For example, in the above description, step S11 is executed for each compression / encryption process. However, step S11 may be executed for each of a plurality of compression / encryption processes, or step S11 may be executed in advance processing. . Further, step S11 may be executed between steps S12 and S13, or between steps S13 and S14. Further, the encryption target data may include other data.

  When the positive integer N is a fixed value and the length P of the padding data is determined as in equation (1), the length P of the padding data is determined for each data M. Therefore, when the same data M is processed a plurality of times, the data M and the length P of the padding data calculated for the data M are stored in the storage unit in association with each other, and the data M is processed again. May be processed using the length P of the padding data stored in the storage area without calculating equation (1). On the other hand, when the length P of the padding data is determined every time as shown in Expression (1), such a storage area is not necessary.

  In the above example, the sum of the length of the compressed data and the length of the padding data is an arbitrary multiple of a positive integer. However, if the length of the padding data is concealed outside the compression encryption apparatus 10, Any length of padding data may be used. Needless to say, other modifications are possible without departing from the spirit of the present invention.

  Further, when the above-described configuration is realized by a computer, processing contents of functions that each device should have are described by a program. The processing functions are realized on the computer by executing the program on the computer.

  The program describing the processing contents can be recorded on a computer-readable recording medium. A computer-readable recording medium is a non-transitory recording medium. Examples of such a recording medium are a magnetic recording device, an optical disk, a magneto-optical recording medium, a semiconductor memory, and the like.

  The program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.

  A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, this computer reads the program stored in its own recording device and executes the process according to the read program. As another execution form of the program, the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).

  In this embodiment, the present apparatus is configured by executing a predetermined program on a computer. However, at least a part of these processing contents may be realized by hardware.

10 Compression / Encryption Device 20 Decryption / Decompression Device

Claims (7)

A compression unit that generates compressed data obtained by compressing data;
A padding unit for generating padded compressed data obtained by concatenating padding data of a secret length to the compressed data;
An encryption unit for generating ciphertext obtained by encrypting the padded compressed data;
A compression encryption apparatus. The compression encryption device according to claim 1,
When the length of the padding data is P, the length of the compressed data is C, and an arbitrary positive integer is N, P = N− {C mod N} is satisfied.
The compression encryption apparatus characterized by the above-mentioned. A decryption unit that decrypts the ciphertext and obtains padded compressed data;
A compressed data extraction unit that extracts a part of the padded compressed data as compressed data;
A decompression unit for decompressing the compressed data;
A decoding and decompressing apparatus. A compression step for generating compressed data obtained by compressing the data;
A padding step for generating padded compressed data obtained by concatenating padding data of a secret length to the compressed data;
An encryption step for generating a ciphertext obtained by encrypting the padded compressed data;
A compression encryption method. Decrypting the ciphertext to obtain padded compressed data;
A compressed data extraction step of extracting a part of the padded compressed data as compressed data;
A decompressing step for decompressing the compressed data;
A decoding / decompressing method comprising: A compression step for generating compressed data obtained by compressing the data;
A padding step for generating padded compressed data obtained by concatenating padding data of a secret length to the compressed data;
An encryption step for generating a ciphertext obtained by encrypting the padded compressed data;
A program that causes a computer to execute. Decrypting the ciphertext to obtain padded compressed data;
A compressed data extraction step of extracting a part of the padded compressed data as compressed data;
A decompressing step for decompressing the compressed data;
A program that causes a computer to execute.

Images