Method and device for replacing/dividing data, and recording medium recording data replacement/division program

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to a data replacement / division method and an apparatus for efficiently performing data replacement processing and division processing, which are used in the field of cryptographic technology, and a recording medium on which a data replacement / division program is recorded.

【0002】

[Conventional technology]

Conventionally, data is encrypted in order to conceal the data. There are two types of encryption technology for encrypting this data: common key cryptography and public key cryptography.

【0003】

In the public key encryption method, the key for encrypting data and the key for decrypting are different. Normally, the key used for encryption is open to the public, and the key used for decryption is kept secret by the user. It is believed that finding the key used for decryption from the key used for public encryption will not be completed in a realistic time even with the current mathematical theory and the computing power of computers.

【0004】

On the other hand, in the common key cryptosystem, the key for encrypting data and the key for decrypting data are the same. In order to construct a high-speed and secure common key cryptography, a method of dividing the data to be encrypted into blocks of an appropriate length and encrypting each block is called a block cipher. Most block ciphers have a structure called Feistel network. In this structure, the 2n-bit input is divided into n-bits and distributed to the left and right, the function f is applied to the n-bit data on the right side, and the output is exclusively ORed with the n-bit data on the left side, and the left and right data. Is replaced and the same operation is repeated. This structure is shown in "Bruce Schneier, Applied Cryptography, 2nd edition, John-Wiley and Sons, p.347, 1996".

【0005】

In addition, the common key cryptosystem requires less processing amount for calculation than the public key cryptosystem, and the amount of data that can be encrypted per unit time is tens to hundreds of times larger. Therefore, the common key cryptosystem tends to be often used in situations where high-speed encryption processing is required.

【0006】

The common key cryptosystem requires not only the high speed described above but also its security. In recent years, decryption methods for several common key cryptographic algorithms have been proposed. Therefore, newly developed common key algorithms must always be secure against such decryption methods. These decoding methods are described in "Bruce Schneier, Applied Cryptography, 2nd edition, John-Wiley and Sons, pp.285-293, 1996".

【0007】

Methods that make it difficult to apply these decryption methods are also being researched, and it is expected that the security of the common key cryptographic algorithm will be enhanced by using these methods. One way to do this is to protect the input and output data from the underlying cryptographic algorithm from an attacker by using an exclusive logical sum of some value from the cryptographic key and the input and output data. There is a method to calculate. This method is described in "Bruce Schneier, Applied Cryptography, 2nd edition, John-Wiley and Sons, pp.366-367, 1996". In recent years, many of the proposed common key cryptographic algorithms are designed using this method.

【0008】

Using the above method, the input data obtained by exclusive-ORing with a certain value obtained from the encryption key becomes the input data of the underlying encryption algorithm. When using the above Feistel network, it is necessary to divide this input data into left and right. Some recently designed common key cryptographic algorithms not only divide the input data to the left and right, but also try to improve security by dividing the input data to the left and right after performing replacement processing. To do. An example of this is the E2 cipher (see Kanda et al., "Proposal for 128-bit Block Cipher E2", IECC 98-12). The E2 cipher defines a replacement process called the BP function, and then divides the input data to the left and right for the Feistel network.

【0009】

[Problems to be Solved by the Invention]

However, the following problems have been pointed out when implementing this BP function. That is, the BP function requires byte-by-byte replacement processing, but the word-based registers implemented in recent MPUs require mask processing and shift processing, which requires processing time, and is copied once to memory. Even if the replacement process can be performed after that, the time required for memory access becomes large and the processing time is long. This makes it difficult to satisfy the high speed of the common key cryptosystem as shown above.

【0010】

The present invention is based on this background, and uses word-based registers to process E2 cipher substitution with the BP function and division to the left and right with the Feistel network at high speed. In E2 cryptography, the basic cryptographic processing unit performs byte-by-byte processing, so for example, the data sequence on the right side does not necessarily have to comply with the specifications. That is, the implementation part of the encryption processing part inside may correspond to the changed byte string.

【0011】

Further, in the present invention, the set of bytes that is divided into left and right after the replacement process is correctly divided into left and right sets in a column order different from the specifications. In recent MPUs, two built-in registers are concatenated and regarded as one register virtually, and an instruction to perform shift processing and store the upper or lower data in the register may be implemented. It is even more effective if various devices are available.

【0012】

That is, an object of the present invention is to provide a data replacement / division method capable of performing processing in a common key cryptosystem at high speed, and a recording medium on which an apparatus and a data replacement / division program are recorded.

【0013】

[Means for solving problems]

In order to achieve the above-mentioned object, the invention according to claim 1 of the present invention has k as an integer, has a register having a length of 4 kbits, and has 16 kbit data {a._{4i + j}} (0 i 3, 0 j 3) is set {a_{4 (i + j mod 4) + j}} (0 i 1, 0 j 3) and set {a_{4 (i + j mod 4) + j}} This is a data replacement / division method in which the data is replaced with (2 i 3,0 j 3) and divided, and in each 0 i 3, the register T_iTo {a_{4i + j}} The step of substituting (0 j 3) and the register T₀With the value of (2^3k-2^kThe data obtained by ANDing with) is registered in the register T.₀Substitute in and register T₂With the value of (2^4k-2^3k+2^kRegister T the data that is ANDed with -1)₂Substitute in and register T₀ Value and register T₂Register T with the logical sum with the value of ₄Steps to assign to and register T₁With the value of (2^2kRegister T the data that is ANDed with -1)₁Substitute in and register T₃With the value of (2^4k-2^2kThe data obtained by ANDing with) is registered in the register T.₃Substitute in and register T₁ Value and register T₃Register the logical sum with T₅Steps to assign to and register T₀With the value of (2^4k-2^3k+2^kRegister T the data that is ANDed with -1)₀Substitute in and register T₂With the value of (2^3k-2^kThe data obtained by ANDing with) is registered in the register T.₂Substitute in and register T₀ Value and register T₂Register T for the logical sum with ₆Steps to assign to and register T₁With the value of (2^4k-2^2kThe data obtained by ANDing with) is registered in the register T.₁Substitute in and register T₃With the value of (2^2kRegister T the data that is ANDed with -1)₃Substitute in and register T₁ Value and register T₃Register T for the logical sum with ₇Steps to assign to and register T₄, Register T₅And register T₆, Register T₇The gist is to have a step to output and as two groups.

【0014】

Further, the invention according to claim 2 of the present invention has 16 k-bit data {a, in which k is an integer and has a register having a length of 4 k-bits._{4i + j}} (0 i 3, 0 j 3) is set {a_{4 (i + j mod 4) + j}} (0 i 1, 0 j 3) and set {a_{4 (i + j mod 4)}_{+ j}} This is a data replacement / division method in which the data is replaced with (2 i 3,0 j 3) and divided, and in each 0 i 3, the register T_iTo {a_{4i + j}} The step of substituting (0 j 3) and the register T₀Value and register T₂Step to rotate the value of to k bits in one direction, and register T₀And register T₂Are concatenated and regarded as a register with a length of 8 kbits, and 4 kbits from one end after shifting 2 kbits to one end are registered as a register T.₄And the register T₁And register T₃Are concatenated and regarded as a register with a length of 8 kbits, and 4 kbits from one end after shifting 2 kbits to one end are registered as a register T.₅And the register T₂And register T₀Are concatenated and regarded as a register of 8 kbit length, and 4 k bits from the other end after shifting to the other by 2 k bits are registered in the register T.₆And the register T₃And register T₁Are concatenated and regarded as a register of 8 kbit length, and 4 k bits from the other end after shifting to the other by 2 k bits are registered in the register T.₇And the register T₄, Register T₅And register T₆, Register T₇The gist is to have a step to output and as two groups.

【0015】

Further, the invention according to claim 3 of the present invention has 16 k-bit data {a, in which k is an integer and has a register having a length of 4 k-bits._{4i + j}} (0 i 3, 0 j 3) is set {a_{4 (i + j mod 4) + j}} (0 i 1, 0 j 3) and set {a_{4 (i + j mod 4)}_{+ j}} (2 i 3,0 j 3) This is a data replacement / division device that replaces and divides, and in each 0 i 3, the register T_iTo {a_{4i + j}} (0 j 3) substituting means and register T₀With the value of (2^3k-2^kThe data obtained by ANDing with) is registered in the register T.₀Substitute in and register T₂With the value of (2^4k-2^3k+2^kRegister T the data that is ANDed with -1)₂Substitute in and register T₀ Value and register T₂Register the logical sum with T₄Means to assign to and register T₁With the value of (2^2kRegister T the data that is ANDed with -1)₁Substitute in and register T₃With the value of (2^4k-2^2kThe data obtained by ANDing with) is registered in the register T.₃Substitute in and register T₁ Value and register T₃Register the logical sum with T₅Means to assign to and register T₀With the value of (2^4k-2^3k+2^kRegister T the data that is ANDed with -1)₀Substitute in and register T₂With the value of (2^3k-2^kThe data obtained by ANDing with) is registered in the register T.₂Substitute in and register T₀ Value and register T₂Register T for the logical sum with ₆Means to assign to and register T₁With the value of (2^4k-2^2kThe data obtained by ANDing with) is registered in the register T.₁Substitute in and register T₃With the value of (2^2kRegister T the data that is ANDed with -1)₃Substitute in and register T₁ Value and register T₃Register T for the logical sum with ₇Means to assign to and register T₄, Register T₅And register T₆, Register T₇The gist is to have a means to output and as two groups.

【0016】

Further, the invention according to claim 4 of the present invention has 16 k-bit data {a, in which k is an integer and has a register having a length of 4 k-bits._{4i + j}} (0 i 3, 0 j 3) is set {a_{4 (i + j mod 4) + j}} (0 i 1, 0 j 3) and set {a_{4 (i + j mod 4)}_{+ j}} (2 i 3,0 j 3) This is a data replacement / division device that replaces and divides, and in each 0 i 3, the register T_iTo {a_{4i + j}} (0 j 3) substituting means and register T₀Value and register T₂Means to rotate the value of to k bits in one direction, and register T₀And register T₂Are concatenated and regarded as a register with a length of 8 kbits, and 4 kbits from one end after shifting 2 kbits to one end are registered as a register T.₄And the register T₁And register T₃Are concatenated and regarded as a register with a length of 8 kbits, and 4 kbits from one end after shifting 2 kbits to one end are registered as a register T.₅And the register T₂And register T₀Are concatenated and regarded as a register of 8 kbit length, and 4 k bits from the other end after shifting to the other by 2 k bits are registered in the register T.₆And the register T₃And register T₁Are concatenated and regarded as a register of 8 kbit length, and 4 k bits from the other end after shifting to the other by 2 k bits are registered in the register T.₇And the register T₄, Register T₅And register T₆, Register T₇The gist is to have a means to output and as two groups.

【0017】

The invention according to claim 5 of the present invention is the register T._iAnd register T_jIs concatenated with and regarded as a register of 8 kbit length, and 4 k bits from one end or the other end after shifting 2 k bits to one or the other is registered T._kAnd some of these means, register T_iWith the value of (2^2kRegister T the data that is ANDed with -1)_iSubstitute in and register T_jWith the value of (2^4k-2^2kThe data obtained by ANDing with) is registered in the register T._jSubstitute in and register T_i Value and register T_jRegister T with the logical sum with the value of _kThe gist is to have a means to substitute for.

【0018】

Further, the invention according to claim 6 of the present invention has 16 k-bit data {a, in which k is an integer and has a register having a length of 4 k-bits._{4i + j}} (0 i 3, 0 j 3) is set {a_{4 (i + j mod 4) + j}} (0 i 1, 0 j 3) and set {a_{4 (i + j mod 4)}_{+ j}} (2 i 3, 0 j 3) is a recording medium on which a data replacement / partition program is recorded, and the register T is set to 0 i 3._iTo {a_4i_{+ j}} The step of substituting (0 j 3) and the register T₀With the value of (2^3k-2^kThe data obtained by ANDing with) is registered in the register T.₀Substitute in and register T₂With the value of (2^4k-2^3k+2^kRegister T the data that is ANDed with -1)₂Substitute in and register T₀ Value and register T₂Register T with the logical sum with the value of ₄Steps to assign to and register T₁With the value of (2^2kRegister T the data that is ANDed with -1)₁Substitute in and register T₃With the value of (2^4k-2^2kThe data obtained by ANDing with) is registered in the register T.₃Substitute in and register T₁ Value and register T₃Register the logical sum with T₅Steps to assign to and register T₀With the value of (2^4k-2^3k+2^kRegister T the data that is ANDed with -1)₀Substitute in and register T₂With the value of (2^3k-2^kThe data obtained by ANDing with) is registered in the register T.₂Substitute in and register T₀ Value and register T₂Register T for the logical sum with ₆Steps to assign to and register T₁With the value of (2^4k-2^2kThe data obtained by ANDing with) is registered in the register T.₁Substitute in and register T₃With the value of (2^2kRegister T the data that is ANDed with -1)₃Substitute in and register T₁ Value and register T₃Register T for the logical sum with ₇Steps to assign to and register T₄, Register T₅And register T₆, Register T₇The gist is that we recorded a program that causes a computer to execute a step that outputs and as two groups.

【0019】

Further, the invention according to claim 7 of the present invention has 16 k-bit data {a, in which k is an integer and has a register having a length of 4 k-bits._{4i + j}} (0 i 3, 0 j 3) is set {a_{4 (i + j mod 4) + j}} (0 i 1, 0 j 3) and set {a_{4 (i + j mod 4)}_{+ j}} (2 i 3, 0 j 3) is a recording medium on which a data replacement / partition program is recorded, and the register T is set to 0 i 3._iTo {a_4i_{+ j}} The step of substituting (0 j 3) and the register T₀Value and register T₂Step to rotate the value of to k bits in one direction, and register T₀And register T₂Are concatenated and regarded as a register with a length of 8 kbits, and 4 kbits from one end after shifting 2 kbits to one end are registered as a register T.₄And the register T₁And register T₃Are concatenated and regarded as a register with a length of 8 kbits, and 4 kbits from one end after shifting 2 kbits to one end are registered as a register T.₅And the register T₂And register T₀Are concatenated and regarded as a register of 8 kbit length, and 4 k bits from the other end after shifting to the other by 2 k bits are registered in the register T.₆And the register T₃And register T₁Are concatenated and regarded as a register of 8 kbit length, and 4 k bits from the other end after shifting to the other by 2 k bits are registered in the register T.₇And the register T₄, Register T₅And register T₆, Register T₇The gist is that we recorded a program that causes a computer to execute a step that outputs and as two groups.

【0020】

That is, in the present invention, k is an integer and a register with a length of 4 k bits is a register T._i16 k-bit data {a_{4i + j}} (0 i 3, 0 j 3) is used as the input to the BP function, and the register T at each 0 i 3_iTo {a_{4i + j}} (0 j 3), [Number 1]

<img file="JP2000214769A_D0001.tif" />Substitute as.

【0021】

After that, it is assigned in this format T_i= [a_{4i + 0} a_{4i + 1} a_{4i + 2} a_{4i + 3}] Describe as.

【0022】

Here, the set [L] and the set [R], [Number 2]

[L] = {a_{4 (i + j mod 4) + j}| 0 i 1, 0 j 3} = {a₀, a₃, a₄, a₅, a₉, a₁₀, a₁₄, a₁₅} [R] = {a_{4 (i + j mod 4) + j}| 2 i 3,0 j 3} = {a₁, a₂, a₆, a₇, a₈, a₁₁, a₁₂, a₁₃} Each is defined as.

【0023】

Register T₀And register T₂In the data sequence of, the data belonging to the set [L] or the set [R] is arranged at both ends, and the data belonging to the set [R] or the set [L] is arranged in the central two.

【0024】

With this arrangement, it is difficult to separate the data using the shift instruction, so register T₁Or register T₃The data of the set [L] or the set [R] is put together on one side, for example, the right side or the other side, that is, the left side. Therefore, first register T₀And register T₂Rotate k bits in one direction, that is, clockwise.

【0025】

As a result, the data is arranged as follows.

【0026】

T₀= [a₃ a₀ a₁ a₂] T₁= [a₄ a₅ a₆ a₇] T₂= [a₁₁ a₈ a₉ a₁₀] T₃= [a₁₂ a₁₃ a₁₄ a₁₅] This results in register T_iThe data belonging to the set [L] is arranged in the upper 2k bits of (0i1), and the data belonging to the set [R] is arranged in the lower 2k bits. Also, register T_iThe data belonging to the set [R] is arranged in the upper 2k bits of (2i3), and the data belonging to the set [L] is arranged in the lower 2k bits.

【0027】

Then register T₀And register T₂Are concatenated and regarded as an 8k-bit long register, and the 4k-bit register from the right after shifting 2k-bit to the right is the register T.₄And register T₁And register T₃Are concatenated and regarded as an 8k-bit long register, and the 4k-bit register from the right after shifting 2k-bit to the right is the register T.₅And.

【0028】

That is, T₄= [a₁ a₂ a₁₁ a₈] T₅= [a₆ a₇ a₁₂ a₁₃] And from this, register T_i(4 i 5) holds the data belonging to the set [R] in just proportion.

【0029】

Similarly, register T₂And register T₀Are concatenated and regarded as an 8k-bit long register, and the 4k-bit register from the left after shifting 2k-bit to the left is the register T.₆And register T₃And register T₁Are concatenated and regarded as an 8k-bit long register, and the 4k-bit register from the left after shifting 2k-bit to the left is the register T.₇And.

【0030】

That is, T₆= [a₉ a₁₀ a₃ a₀] T₇= [a₁₄ a₁₅ a₄ a₅] And from this, register T_i(6 i 7) holds the data belonging to the set [L] in just proportion.

【0031】

BEST MODE FOR CARRYING OUT THE INVENTION

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

【0032】

FIG. 1 is a block diagram showing a configuration of a data replacement / division device according to an embodiment of the present invention.

【0033】

As shown in FIG. 1, the control unit 1 controls each processing unit, the processing unit, and the like in the processing of the present embodiment. Input data {a in advance in the data storage unit 11_{4i + j}} (0 i 3, 0 j 3) is stored, and the output data is stored at the end of processing. The arithmetic calculation unit 13 is provided with registers and can perform rotation and shift processing.

【0034】

Fig. 2 and Fig. 3 illustrate the data replacement process of the BP function in the E2 cipher. Figure 2 shows how the first 4 bytes of the output data are configured by the replacement process. Figure 3 shows the elements of the set [L] by this process.

【0035】

In FIG. 4, the register T is executed by executing the present embodiment.₆And register T₇Shows the sequence of data stored in. Register T by comparison with Figure 3₆And register T₇It can be seen that all the elements of the set [L] are included in, and the BP function and the Feistel network are distributed to the left and right.

【0036】

Here, when the method using the rotation and shift according to claims 2, 5 and 7 is selected, the register T₆And register T₇The data sequence in the data is such that the right 2 bytes and the left 2 bytes are interchanged. That is, the register T shown in FIG.₄Data column [a₉ a₁₀ a₃ a₀] Is [a₃ a₀ a₉ a₁₀]. However, there is no excess or deficiency as an element of the set [L], and thus the purpose is achieved.

【0037】

As described above, according to the present embodiment, if the input / output of the BP function is collectively assigned to the register by 4 bytes from the left in the E2 encryption specification, the 4 bytes in one register of the input is the output. One byte is assigned to each of the four registers. As a result, many instructions in the MPU, such as performing an operation on one register and storing the result in one register, can process only one byte for one operation instruction.

【0038】

Therefore, a minimum of 16 instructions are required to implement the BP function. Actually, 16 or more instructions are required for mask processing and logical sum processing.

【0039】

If each byte of the register is used for a direct input instruction, 16 instructions may be sufficient, but some MPUs have a structural penalty and take more than the usual 16 instructions. It turns out.

【0040】

Furthermore, there is also a method of writing the input data to the memory once and then reading the data in byte units in consideration of the replacement of the BP function, but in recent MPUs, there are many cases where a penalty is incurred for accessing the memory, and Similar to the above, a structural penalty may occur, and it can be seen that the processing time for 16 instructions or more is still required.

【0041】

According to this embodiment, the BP part of the E2 cipher can be composed of two rotate instructions and four instructions that concatenate two registers, shift them to the right or left, and assign the corresponding data on the right or left to the registers. The instructions that perform the latter half of the processing are, for example, the instructions that are installed as standard in MPUs of Intel 80386 or later, and there is no problem in their implementation. Therefore, the BP function can be executed faster than the existing method.

【0042】

Also, in MPUs that do not specifically implement this instruction, two mask instructions and one OR instruction can be used instead. That is, the register T after rotation₀And register T₂Are concatenated and regarded as an 8k-bit long register, and the 4k-bit register from the right after shifting 2k-bit to the right is the register T.₅In the means of₀And (2^2kRegister T the data that is ANDed with -1)₀Substitute in and register T₂And (2^4k-2^2kThe data obtained by ANDing with) is registered in the register T.₂Substitute in and register T₀ And register T₂Register the logical sum with T₄You can substitute for.

【0043】

That is, T₀ = [0 0 a₁ a₂] T₂ = [A₁₁ a₈ 0 0] T₄ = [a₁₁ a₈ a₁ a₂] Will be.

【0044】

Even in this case, since the two rotate instructions can be described in a total of 14 instructions, the BP function can be executed faster than the existing method.

【0045】

The register T in this case₄Is the above-mentioned register T₄Compared to the values held by, the difference is that the top two values and the bottom two values are misplaced. But register T₄The value held by is a₁, a₂, a₈, a₁₁There is no change in the four, so register T₄And register T₅It is guaranteed that the value of the set [R] is held in just proportion.

【0046】

As described above, the present embodiment can satisfy the high-speed implementation of the BP function part of the E2 encryption with respect to the data replacement processing and the division processing used in the encryption technology.

【0047】

Further, the data replacement / division operation in such an E2 encryption BP function or the like is realized by the above-mentioned data replacement / division program, and the program is provided by recording on a recording medium. By using a recording medium in which such a data replacement / division program is recorded, it is possible to improve the circulation of the data replacement / division program.

【0048】

[Effect of the invention]

As described above, the present invention has an effect that the data replacement process and the division process in the common key cryptosystem can be performed at high speed.

[Simple explanation of drawings]

[Figure 1]

It is a block diagram which shows the schematic structure of one Embodiment of the data replacement / division apparatus which concerns on this invention.

[Figure 2]

It is a figure explaining the replacement process of the BP function part of the E2 cipher.

[Fig. 3]

It is a figure which showed a part of the output data of a BP function.

[Fig. 4]

Register T₄And register T₅It is a figure which showed the output data of.

[Explanation of symbols]

1 Control unit 11 Data storage 13 Arithmetic calculation unit 13a register group