Data converter and recording medium on which program for executing data conversion is recorded

[0002] The present invention relates to a transformation device that is used in a cryptographic device for concealing data in data communication or storage and, more particularly, to a data transformation device suitable for use in an encryption device of a secret-key encryption algorithm which encrypts or decrypts data blocks using a secret key, and a recording medium on which there is recorded a program for execution by the data transformation device.

[0003] With a view to constructing a fast and secure secret-key encryption algorithm, a block cipher is used according to which data for encryption is split into blocks of a suitable length and encrypted for each block. Usually, the block cipher comprises a data diffusion part which randomizes input data to be encrypted, and a key scheduling part which is supplied with a secret common key (hereinafter referred to as a master key) input to the encryption device and generates a sequence of subkeys for use by the data diffusion part. A typical secret-key encryption algorithm, which is used in the data transformation device to conceal data, is DES (Data Encryption Standard) that was FIPS-approved algorithm for encryption.

[0004] FIG. 1 illustrates the functional configuration of DES. DES uses a 64-bit secret key (8 bits being used for parity), and encrypts or decrypts data in blocks of 64 bits. In FIG. 1 the encryption process is executed in a data diffusion part 10, which begins with initial permutation of 64 bits of a plaintext M in an initial permutation part 11, followed by splitting the permuted data into two pieces of 32-bit block data L₀and R₀. The block data R₀is input to a function operation part (referred to also as a round function) 12 which is a data transformation part shown as an i-th round processing part 14_i(i=0, 1, . . . , 15) in FIG. 2, wherein it is transformed to f(R₀, k₀) using a 48-bit subkey k₀. The thus transformed data f(R₀, k₀) and the block data L₀are exclusive ORed in an XOR circuit 13, and its output and the block data R₀are swapped to obtain the next block data L₁, R₁. That is,

[0005] R₁=L₀⊕f(R₀, k₀)

[0006] L₁=R₀

[0007] where ⊕ represents an exclusive OR. A 0-th round processing part 14₀comprises the function operation part 12 and the XOR circuit 13 and swaps the two pieces of block data to provide the two pieces of output block data L₁and R₁; similar round processing parts 14₁to 14₁₅are provided in cascade. The processing by the i-th round processing part 14_iwill hereinafter be referred to as i-th processing, where i=0, 1, . . . , 15. That is, each round processing part 14_i(where 0≦i≦15) performs the following processing

[0008] R_i+1L_i⊕f(R_i, k_i)

[0009] L_i+1=R_i

[0010] And finally concatenation two pieces of data R₁₆and L₁₆into 64-bit data, which is permuted in a final permutation part 15 to provide a 64-bit ciphertext. Incidentally, the operation of the final permutation part 15 corresponds to an inverse transform of the operation of the initial permutation part 11.

[0011] The decryption process can be executed following the same procedure as that for the encryption process except inputting subkeys k₀, k₁, . . . , k₁₄, k₁₅to the function f (the function operation part 12) in the order k₁₅, k₁₄, . . . , k₁, k₀which is reverse to that in the encryption process. In such an instance, the outputs L₁₆and R₁₆from the final round processing part 14₁₅are further swapped as depicted, and in the decryption process the ciphertext is input to the initial permutation part 11 for execution of the process of FIG. 1, by which the plaintext is provided intact at the output of the final permutation part 15. In a key scheduling part 20 an expanded key generation part 21: splits a master key of 64 bits, except 8 bits used for parity, into two pieces of 28-bit right and left key data; then performs 16-round swapping of the two pieces of 28-bit right and left key data; and performs reduced permutation of the permuted right and left data (a total of 56 bits) provided from the respective rounds to generate 16 48-bits subkeys k₀, k₁, . . . , k₁₄, k₁₅which are provided to the corresponding round processing parts of the data diffusion part 10.

[0012] The processing in the function operation part 12 is performed as depicted in FIG. 2. To begin with, the 32-bit block data R_iis transformed to 48-bit data E(R_i) in an expanded permutation part 17. This output data and the subkey k_iare exclusive ORed in an XOR circuit 18, whose output is transformed to 48-bit data E(R_i)⊕k_i, which is then split to eight pieces of 6-bit sub-block data. The eight pieces of sub-block data are input to different S-boxes S₀to S₇to derive therefrom a 4-bit output, respectively. Incidentally, the S-box S_j(where j=0, 1, . . . , 7) is a nonlinear transformation table that transforms the 6-bit input data to the 4-bit output data, and is an essential part that provides security of DES. The eight pieces of output data from the S-boxes S₀to S₇are concatenated again to 32-bit data, which is applied to a permutation part 19 to provide the output f(R_i, k_i) from the function operation part 12 as shown in FIG. 2. This output is exclusive ORed with L_ito obtain R_i+1.

[0013] Next, a description will be given of cryptanalysis techniques. A variety of cryptanalysis techniques have been proposed for DES and other traditional secret-key encryption algorithms; extremely effective cryptanalysis techniques among them are differential cryptanalysis proposed by E. Biham and A. Shmir, (“Differential Cryptanalysis of DES-like Cryptosystems,” Journal of Cryptology, Vol. 4, No. 1, pp.3-72) and linear cryptanalysis proposed by Matsui, (“Linear Cryptanalysis Method for DES cipher,” Advances in Cryptology-EUROCRYPT' 93 (Lecture Notes in Computer Science 765), pp. 386-397.)

[0014] Assuming that a difference between two pieces of data X and X* is defined as

[0015] ΔX=X⊕X*,

[0016] differential cryptanalysis aims to obtain the subkey k₁₅in the final round processing part 14₁₅by applying to the following equations two sets of plaintext-ciphertext pair that an attacker possesses. In the encryption process of FIG. 1, let (L_i, R_i) and (L*_i, R*_i) represent input data into the round processing part 14_ifor first and second plaintexts respectively. With the difference defined as mentioned above, the following equations hold.

[0017] ΔL_i=L_i⊕L*_i

[0018] ΔR_i=R_i⊕R*_i

[0019] In FIG. 1, since L₁₅=R₁₄, L*₁₅=R*₁₄, L₁₆=R₁₅and L*₁₆=R*₁₅, the following equations hold

[0020] R₁₆=L₁₅⊕f(R₁₅, k₁₅)

[0021] R*₁₆=L*₁₅⊕f(R*₁₅, k₁₅)

[0022] and the exclusive OR of both sides of these two equations is obtained as follows:

[0023] ΔR₁₆=ΔL₁₅⊕f(L₁₆, k₁₅)⊕f(L₁₆⊕ΔL₁₆,k₁₅).

[0024] The exclusive ORing of its both sides with ΔR₁₄=ΔL₁₅gives the following equation:

[0025] f(L₁₆, k₁₅)⊕f(L₁₆ΔL₁₆, k₁₅)=ΔR₁₆⊕ΔR₁₄.

[0026] At this time, since L₁₆, ΔL₁₆and ΔR₁₆are data available from the ciphertext, they are known information. Hence, if the attacker can correctly obtain ΔR₁₄, then only k₁₅in the above equation is an unknown constant; the attacker can find a correct k₁₅without fail by an exhaustive search for k₁₅using the known sets of plaintext-ciphertext pair. Accordingly, once the subkey k₁₅is found out, the remaining eight (i.e., 56-48) bits can easily be obtained even by another exhaustive search.

[0027] On the other hand, generally speaking, it is difficult to obtain ΔR₁₄since this value is an intermediate difference value. Then, assume that each round processing is approximated by the following equations with a probability p_iin the 0-th to the last round but one (i.e.; the 14-th):

[0028] ΔR_i+1=ΔL_i⊕Δ{f(ΔR_i)}

[0029] ΔL_i+1=ΔR_i+1.

[0030] The point is that, when certain ΔR_iis input to the i-th round processing part, Δ{f(ΔR_i)} can be predicted with the probability p_iregardless of the value of the subkey k_i. The reason why such approximations can be made is that, the S-boxes, which are nonlinear transformation tables, provide an extremely uneven distribution of output differences for same input differences. For example, in the S-box S₀, an input difference “110100₍₂₎” is transformed to an output difference “0010₍₂₎” with a probability of 1/4. Then, the approximation for each round is obtained by assuming that the S-boxes are each capable of predicting the relationship between the input difference and the output difference with a probability P_siand by combining them. Furthermore, the concatenation of such approximations in the respective rounds makes it possible to obtain ΔR₁₄from ΔL₀and ΔR₀(ΔL₀and ΔR₀are data derivable from the plaintext, and hence they are known) with a probability P=Π_i=0¹³p_i. Incidentally, the higher the probability P, the easier the cryptanalysis. After the subkey k₁₅is thus obtained, a similar calculation is made of the subkey k₁₄regarding it as a 15-round DES that is one round fewer than in the above; such operations are repeated to obtain the subkeys one by one to k₀.

[0031] It depends on the probability P whether this cryptanalysis succeeds; the higher the probability P, the more likely the success. Biham et al. say that DES could be broken by this cryptanalysis if 2⁴⁷sets of chosen plaintext-ciphertext pair are available.

[0032] Linear cryptanalysis aims to obtain subkeys by constructing the following linear approximate equation and using the maximum likelihood method with sets of known plaintext-ciphertext pair possessed by an attacker.

[0033] (L₀, R₀)Γ(L₀, R₀)⊕(L₁₆, R₁₆)Γ(L₁₆, R₁₆)=(k₀, k₁, . . . , k₁₅)Γ(k₀, k₁, . . . , k₁₅)

[0034] where Γ(X) represents the vector that chooses a particular bit position of X, and it is called a mask value.

[0035] The role of the linear approximation expression is to approximately replace the cryptographic algorithm with a linear expression and separate it into a part concerning the set of plaintext-ciphertext pairs and a part concerning the subkeys. That is, in the set of plaintext-ciphertext pairs, the all exclusive Ors between the values at particular bit positions of the plaintext and those of the ciphertext take a fixed value, which indicates that it equals the exclusive OR of the values at particular positions of the subkeys. This means that the attacker gets information

[0036] (k₀, k₁, . . . , k₁₅)Γ(k₀, k₁, . . . , k₁₅) (one bit)

[0037] from information

[0038] (L₀, R₀)Γ(L₀, R₀)⊕(L₁₆, R₁₆)Γ(L₁₆, R₁₆).

[0039] At this time, (L₀, R₀) and (L₁₆, R₁₆) are the plaintext and the ciphertext, respectively, and hence they are known. For this reason, if the attacker can correctly obtain Γ(L₀, R₀), Γ(L₁₆, R₁₆) and Γ(k₀, k₁, . . . , k₁₅), then he can obtain (k₀, k₁, . . . , k₁₅)Γ(k₀, k₁, . . . , k₁₅) (one bit).

[0040] In DES only S-boxes perform nonlinear transformation; hence, if linear representations can be made for only the S-boxes, the linear approximation expression can easily be constructed. Then, assume that the each S-box can be linearly represented with a probability p_si. The point here is that when the input mask value for the S-box is given, its output mask value can be predicted with the probability p_si. The reason for this is that the S-boxes, which form a nonlinear transformation table, provide an extremely uneven distribution of output mask values according to the input mask values. For example, in the S-box S₄, when the input mask value is “010000₍₂₎,” an output mask value “1111₍₂₎” is predicted with a probability 3/16. By combining the mask values in these S-boxes, a linear representation of each round with the input and output mask values can be made with a probability p_i, and by concatenating the linear representations of the respective rounds, Γ(L₀, R₀), Γ(L₁₆, R₁₆)and Γ(k₀, k₁, . . . , k₁₅) are obtained wit the following probability:

[0041] P=1/2+2¹⁵Π_i=0¹⁵|p_i−1/2|.

[0042] The higher the probability P, the easier the cryptanalysis.

[0043] According to Matsui, he has succeeded in the analysis of DES by this cryptanalysis using 2⁴³sets of known plaintext-ciphertext pair.

[0044] To protect ciphers against the above cryptanalysis techniques, the probability P needs only to be reduced to be sufficiently small. A wide variety of proposals have been made to lessen the probability P, and the easiest way to provide increased security in the conventional cryptosystems is to increase the number of rounds. For example, Triple-DES with three DESs concatenated is an algorithm that essentially increases the number of rounds from 16 to 48, and it provides a far smaller probability P than does DES.

[0045] However, to increase the number of rounds with a view to avoiding the cryptanalysis techniques described above inevitably sacrifices the encryption speed. For example, if the number of rounds is tripled, the encryption speed is reduced down to ⅓. That is, since the encryption speed of the present DES is about 10 Mbps on the Pentium PC class, the encryption speed of Triple-DES goes down to around 3.5 Mbps. On the other hand, networks and computers are becoming increasingly faster year by year, and hence there is also a demand for data transformation devices that keep up with such speedups. With conventional data transformation devices, it is extremely difficult, therefore, to simultaneously meet the requirements of security and speedup.

[0046] Moreover, according to differential and linear cryptanalysis, the subkey in the final round is obtained as described above. Since DES has a defect that the main key can easily be derived from the subkey in the final round, there is proposed in U.S. Pat. No. 4,850,019: a method which provides increased security by increasing the complexity of the correspondence between the subkeys and the main key in the key scheduling part 20. Its fundamental configuration is shown in FIG. 3. In the above-mentioned U.S. patent, the subkeys are generated from the main key by data diffusion parts (f_k), therefore it is expected that the main key cannot easily be derived from the subkeys.

[0047] Next, a description will be given, with reference to FIG. 3, of the general outlines of a key scheduling part 20 disclosed in the above-mentioned U.S. patent. An expanded key generation part 21 comprises N/2 (N=16, for example) rounds of key processing parts 21₀to 21_N/2−1which have key diffusion parts 22₀to 22_N/2−1, respectively. The key processing parts 21_j(where j=0, 1, . . . , N/2−1) each perform diffusion processing of two pieces of 32-bit right and left key data, and interchange them to provide two pieces of right and left key data for input to the next-round key processing part 21_j+1. The key processing parts 21_j, except the first round, each have an exclusive OR part 23_j, which calculates the exclusive OR of the left input key data to the key processing part 21_j−1of the preceding round and the left output key data therefrom and provides the calculated data to the key diffusion part 22_j. The left input key data of the key processing part 21_jis diffused by the output from the exclusive OR part 23_jin the key diffusion part 22_j, from which the diffused data is output as right key data for input to the next round, and the right input key data of the key processing part 21_jis output as left key data for input to the next round. The output from each key diffusion part 22_jis bit-split into two subkeys Q_2jand Q_2j+1(that is, k_iand k_i+1), which are provided to the corresponding (i=2_j)-th round processing part and (i+1=2j+1)-th round processing part in FIG. 1.

[0048] The 64-bit main key is split into two pieces of 32-bit right and left key data, then in the first-round key processing part 21₀the left key data is diffused by the right key data in the key difflusion part 22₀to obtain diffused left key data, and this diffused left key data and the right key data are interchanged and provided as right and left key data next to the key processing part 21₁. The outputs from the key diffusion parts 22₀to 22_N/2−1of the key processing parts 21₀to 21_N/2−1are applied as subkeys k₀to k_N−1to the corresponding round processing parts 14₀to 14_N−1of the data diffusion part 10 depicted in FIG. 1.

[0049] In the expanded key generation part 21 of FIG. 3, however, each key diffusion part 22_jis a function for generating a pair of key data (subkeys Q_2j, Q_2j+1) from two pieces of input data. In the case where when one of the two pieces of input data and the output data are known the other input data can be found out, if it is assumed that three pairs of subkeys (Q_2j−2and Q_2j−1), (Q_2jand Q_2j+1), (Q_2j+1and Q_2j+3) are known, since the output (subkeys Q_2j+2and Q_2j+3) from the (j+1)-th key diffusion part 22_j+1and the one input data (subkeys Q_2j−2and Q_2j−1) thereto are known, the other input data (i.e., the output data from the exclusive OR part 23_j+1) can be obtained; and it is possible to derive, from the thus obtained data and the subkeys Q_2jand Q_2j+1which constitute the one input data to the exclusive OR part 23_j+1, the input data to the preceding j-th) key diffusion part 22_jwhich constitute the other input data to the exclusive OR part 23_j+1, that is, the subkeys Q_2j−4and Q_2j−3which constitute the output from the three-round-preceding ((j−2)-th) key diffusion part 22_j−2. By repeating such operations in a sequential order, it is possible to determine all subkeys through data analysis only in the key scheduling part 20 without involving data analysis in the data diffusion part 10. It has been described just above that when subkeys of three consecutive rounds are known, all the subkeys concerned can be obtained, but when subkeys of two consecutive rounds, cryptanalysis will succeed even by estimating subkeys of the remaining one round by an exhaustive search.

[0050] Letting the final stage of the round processing in FIG. 1 be represented by i=N, subkeys k_Nand k_N−1are easy to obtain by differential and linear cryptanalysis. By analyzing the key data in the expanded key scheduling part 21 as described above using the obtained subkeys, there is the possibility of obtaining all the subkeys concerned.

[0051] A first object of the present invention is to provide a data transformation device in which the round function f (the function operation part) is so configured as to simultaneously meet the requirements of security and speedup to thereby ensure security and permit fast encryption processing without involving a substantial increases in the number of rounds, and a recording medium having recorded thereon a program for implementing the data transformation.

[0052] A second object of the present invention is to implement a key scheduling part which does not allow ease in determining other subkeys and the master key by a mere analysis of the key scheduling part even if some of the subkeys are known.

[0053] To attain the first object of the present invention, a nonlinear function part, in particular, comprises: a first key-dependent linear transformation part which linearly transforms input data of the nonlinear function part based on first key data stored in a key storage part; a splitting part which splits the output data of the first key-dependent linear transformation part into n pieces of subdata; first nonlinear transformation parts which nonlinearly transform these pieces of subdata, respectively; a second key-dependent linear transformation part which linearly transforms respective pieces of output subdata of the first nonlinear transformation parts based on second key data; second nonlinear transformation parts which nonlinearly transform respective pieces of output subdata of the second key-dependent linear transformation part; and a combining part which combines output subblocks of the second nonlinear transformation part into output data of the nonlinear function part; and the second key-dependent linear transformation part contains a linear transformation part which performs exclusive ORing of its inputs which is defined by an n×n matrix.

[0054] According to the present invention, it is guaranteed that when the differential probability/linear probability in the first and second nonlinear transformation parts is p (<1), the differential probability/linear probability of approximating each round is p_i≦p²(when the input difference to the function f(the nonlinear function part) is not 0 in the case of differential cryptanalysis, and when the output mask value from the function is not 0 in the case of linear cryptanalysis). And when the function f is objective, if the number of rounds of the cryptographic device is set at 3r, then the probability of the cipher becomes P≦p_i^2r≦p^4r. Furthermore, if the second key-dependent linear transformation part in the case of n=4, in particular, has a configuration that exclusive ORs combination of three of four pieces of subdata with one of four pieces of key data, the probability of approximating each round is p_i≦p⁴and the probability of the cipher is P≦p_i^2r≦p^8r. If the second key-dependent linear transformation part in the case of n=8 has a configuration that exclusive ORs combination of six or five of eight pieces of subdata with one of eight pieces of key data, the probability of approximating each round is p_i≦p⁵and the probability of the cipher is P≦p_i^2r≦p^10r.

[0055] Moreover, the first and second nonlinear transformation parts are arranged so that their processing can be performed completely in parallel—this contributes to speedup.

[0056] It is possible, therefore, to construct a fast and source nonlinear function against differential and linear cryptanalysis, and to permit the implementation of a data transformation device which copes with both security and speedup.

[0057] To attain the second object of the present invention, the key scheduling part is provided with: a G-function parts which perform the same function as that of the key diffusion part (the function f_k), L components which are output from the G-function parts being once stored in a storage part; and an H-function part which reads out a required number of L components from the storage part and generates subkeys by extracting the respective L components as uniformly as possible. Furthermore, in the H-function part partial information, which is used as subkeys, is extracted from the L components which are outputs from the G-function parts, then the extracted information is stored in a storage part, and the subkeys are generated by extracting the partial information from the required number of L components.

[0058] FIG. 1 is a diagram depicting the functional configuration of a conventional DES cryptographic device.

[0059] FIG. 2 is a diagram depicting a concrete functional configuration of a function operation part 12 in FIG. 1.

[0060] FIG. 3 is a diagram depicting an example of an expanded key generation part 21 in FIG. 2.

[0061] FIG. 4 is a diagram illustrating the functional configuration of the first embodiment of the present invention.

[0062] FIG. 5 is a diagram showing in detail an example of the functional configuration of a nonlinear function part 304 in the first embodiment.

[0063] FIG. 6 is a diagram showing a basic configuration of a nonlinear function part for determining an optimal linear transformation part in FIG. 5.

[0064] FIG. 7 is a diagram depicting a concrete example of the second key-dependent linear transformation part 344 in FIG. 5.

[0065] FIG. 8A is a diagram depicting an equivalent functional configuration of a nonlinear transformation part 343₀′ in the second embodiment.

[0066] FIG. 8B is a diagram depicting a equivalent functional configuration of a nonlinear transformation part 343₁′ in the second embodiment.

[0067] FIG. 8C is a diagram depicting an equivalent functional configuration of a nonlinear transformation part 343₂′ in the second embodiment.

[0068] FIG. 8D is a diagram depicting an equivalent functional configuration of a nonlinear transformation part 343₂′ in the second embodiment.

[0069] FIG. 9 is a diagram showing the functional configuration of a second key-dependent linear transformation part 344 in the second embodiment.

[0070] FIG. 10 is a diagrqm showing the functional configuration of a nonlinear function part 343₀(345₀) in the third embodiment.

[0071] FIG. 11 is a flowchart showing the procedure for implementing a data transformation by a computer.

[0072] FIG. 12 is a flowchart showing in detail the procedure of step S3 in FIG. 11.

[0073] FIG. 13 is a diagram depicting the functional configuration of the fourth embodiment of the present invention.

[0074] FIG. 14 is a diagram depicting the functional configuration of a nonlinear function part 304 in FIG. 13.

[0075] FIG. 15A is a diagram depicting a linear transformation part 334A of a limited structure intended to reduce the computational complexity involved in search.

[0076] FIG. 15B is a diagram depicting an example of configuration of one transformation box in FIG. 15A.

[0077] FIG. 16 is a diagram depicting an example of the configuration of a linear transformation part 344A determined by the search algorithm.

[0078] FIG. 17 is a diagram depicting an example of the functional configuration of a second key-dependent linear transformation part 344 in FIG. 14 in the fourth embodiment.

[0079] FIG. 18 is a diagram depicting another example of the functional configuration of a second key-dependent linear transformation part 344 in FIG. 14 in the fourth embodiment.

[0080] FIG. 19 is a diagram depicting still another example of the functional configuration of a second key-dependent linear transformation part 344 in FIG. 14 in the fourth embodiment.

[0081] FIG. 20A is a diagram illustrating the functional configuration of a nonlinear transformation part 343₀′ in the fifth embodiment.

[0082] FIG. 20B is a diagram illustrating the functional configuration of a nonlinear transformation part 343₁′.

[0083] FIG. 20C is a diagram illustrating the functional configuration of a nonlinear transformation part 343₇′.

[0084] FIG. 21 is a diagram showing the functional configuration of a second key-dependent linear transformation part 344 in the fifth embodiment.

[0085] FIG. 22 is a diagram showing a configuration for executing a data processing program recorded on a recording medium.

[0086] FIG. 23A is a block diagram depicting the basic functional configuration of a key generation part according to the present invention.

[0087] FIG. 23B is a block diagram depicting the basic functional configuration of another key generation part according to the present invention.

[0088] FIG. 24 is a block diagram depicting an example of the functional configuration of an intermediate key generation part 220 in FIGS. 23A or 23B.

[0089] FIG. 25 is a block diagram depicting the functional configuration of a G-functional part in FIG. 24 when the present invention is applied to a key scheduling part in FIG. 3.

[0090] FIG. 26 is a block diagram depicting the functional configuration of a subkey generation part 240 in FIG. 23A when the present invention is applied to a key scheduling part in FIG. 3.

[0091] FIG. 27 is a block diagram depicting an example of the functional configuration of a subkey generation part 250 in FIG. 23B when the present invention is applied to a key scheduling part in FIG. 3 (In this embodiment the subkey generation part contains an H-function part equipped with a bit extraction function).

[0092] FIG. 28 is a block diagram depicting the functional configuration of the G-function part 22 designed for the application of the present invention to a Feistel cipher which uses 128 bits as one block.

[0093] First Embodiment

[0094] An embodiment of the present invention will be described below with reference to the accompanying drawings.

[0095] FIG. 4 illustrates the functional configuration for an encryption process in the data transformation device according to an embodiment of the present invention. The data transformation device comprises a data diffusion part 10 and a key scheduling part 20. In the data transformation device according to the present invention, too, the data diffusion part 10 comprises N rounds of cascade-connected round processing parts 38₀to 38_N−1which sequentially perform round processing of left and right pieces of data after input data is split into left and right pieces L₀, R₀; each round processing part 38_i(where i=0, 1, . . . , N−1) is made up of a nonlinear function part 304 corresponding to the function operation part 12 in FIG. 1, a linear operation part 305 corresponding to the XOR circuit 13 in FIG. 1 and a swapping part 306.

[0096] Input data M, which corresponds to a plaintext, is entered into the cryptographic device via an input part 301. The key scheduling part 20 comprises a key input part 320, a expanded key generation part 321 and a key storage part 322. Based on input data (a master key K) from the key input part 320, the expanded key generation part 321 generates plural pieces of key data (subkeys)

[0097] {fk; k₀₀, k₀₁; k₁₀, k₁₁, k₁₂; . . . ; k_(N−1)0, k_(N−1)1, k_(N−1)2; ek}

[0098] which are stored in the key storage part 322. The input data M is transformed in a key-dependent initial transformation part 302 with the key data fk stored in the key storage part 322, thereafter being split in an initial splitting part 303 into two pieces of left and right block data L₀and R₀. For example, 64-bit data is split into two pieces of 32-bit block data L₀and R₀. The key-dependent initial transformation part 302 performs a linear transformation such as exclusive ORing of the key data fk and the input data M or bit rotation of the input data M by the key data fk, or nonlinear transformation by a combination of multiplications.

[0099] The right block data R₀is provided to the nonlinear function part 304 which is characteristic of the present invention, together with the key data k₀₀, k₀₁and k₀₂stored in the key storage part 322, and in the nonlinear function part 304 the right block data is nonlinearly transformed to data Y₀. The data Y₀and the left block data L₀are transformed to data L₀* through a linear operation in the linear operation part 305. The data L₀* and the data R₀are swapped in the swapping part 306 to provide L₁←R₀, R₁←L₀*; and these pieces of data L₁and R₁are input to the next first round processing part 38₁.

[0100] Thereafter, in an i-th round processing parts 38_i(where i=0, 1, . . . , N−1) the same processing as mentioned above is repeated for two pieces of input block data L_iand R_i. That is, the right block data R_iis input to the nonlinear function part 304 together with the key data k_i0, k_i1and k_i2, and in the nonlinear function part 304 it is nonlinearly transformed to data Y_i. The data Y_iand the data L_iare transformed to data L_i* by a linear operation in the linear operation part 305. The data L_i* and the data R_iare swapped in data position in the swapping part 306, that is, L_i+1←R_i, R_i+1←L_i*. The linear operation part 305 is to perform, for instance, an exclusive OR operation.

[0101] Letting N represent the repeat count (the number of rounds) suitable to provide security of a data transformation device for encryption, two pieces of left and right data L_Nand R_Nare obtained as the result of such repeated processing by the round processing parts 38₀to 38_N−1. These pieces of data L_Nand R_Nare combined into a single piece of block data in a final combining part 307; for example, the two pieces of 32-bit data L_Nand R_Nare combined to 64-bit data. Then the thus combined data is transformed in a final linear transformation part 308 using the key data ek stored in the key storage part 322, and output data C is provided as a ciphertext from an output part 309.

[0102] In decryption, the plaintext M can be derived from the ciphertext C by reversing the encryption procedure. In particular, when the key-dependent final transformation part 308 is one that performs a transformation inverse to that of the key-dependent initial transformation part 302, the decryption can be done by inputting ciphertext data in place of the input data in FIG. 4 and then inputting the key data in a sequential order reverse to that in FIG. 4, that is, ek, k_(N−1)0, k_(N−1)1, k_(N−1)2, . . . , k₁₀, k₁₁, k₁₂, k₀₀, k₀₁, k₀₂, fk.

[0103] Next, a detailed description will be given of the internal configuration of the nonlinear function part 304. FIG. 5 is a diagrammatic showing of the internal functional configuration of the nonlinear function part 304.

[0104] The input block data R_ito the i-th round processing part 38_iconstitutes input data to the nonlinear function part 304, together with the key data k_i0, k_i1, k_i2stored in the key storage part 322. The block data R_iis subjected to, for example, exclusive ORing with the key data k_i0in a first key-dependent linear transformation part 341, by which it is linearly transformed to data R_i*=R_i⊕k_i0. Next, the thus transformed data R_i* is split into four pieces of, for instance, 8-bit data in₀, in₁, in₂and in₃in a splitting part 342. The four pieces of data in₀, in₁, in₂and in₃are nonlinearly transformed to four pieces of data mid₀₀, mid₀₁, mid₀₂and mid₀₃in nonlinear transformation parts 343₀, 343₁, 343₂and 343₃, respectively, from which they are input to a second key-dependent linear transformation part 344.

[0105] The second key-dependent linear transformation part 344 performs linear transformation (XORing) among the pieces of input data mid₀₀, mid₀₁, mid₀₂and mid₀₃from four routes to provide new data of four routes, and further performs linear transformation (XORing) among these pieces of data of the four routes with four pieces of the key data k_i1to provide output data mid₁₀, mid₁₁, mid₁₂and mid₁₃of the four routes. The four pieces of data are input to nonlinear transformation parts 345₀, 345₁, 345₂and 345₃, wherein they are transformed to data out₀, out₁, out₂and out₃, respectively. These four pieces of data are combined into data Y_i* in a combining part 346; furthermore, in a third key-dependent linear transformation part 347 the data Y_i* undergoes a linear operation with the key data k_i2to generate output data Y_i.

[0106] The above-mentioned second key-dependent linear transformation part 344 is configured to perform an exclusive OR operation of data between data processing routes 30₀, 30₁, 30₂and 30₃provided corresponding to the pieces of data mid₀₀, mid₀₁, mid₀₂and mid₀₃, respectively, through the use of an algorithm according to the present invention, thereby providing increased security without increasing the number of rounds of the data transformation device depicted in FIG. 4. The security of he data transformation device of FIG. 4 against differential cryptanalysis and linear cryptanalysis is dependent on the configuration of the nonlinear function part 304 of each round; in particular, when the nonlinear function part 304 in FIG. 5 has such a basic configuration as shown in FIG. 6, the security depends on a first nonlinear transformation part 343 composed of n nonlinear transformation parts (S-boxes) with m-bit input data, a linear transformation part 344A for linearly transforming the n outputs and a second nonlinear transformation part 345 composed of n nonlinear transformation parts (S-boxes) for nonlinearly transforming the n m-bit outputs, respectively. It is particularly important how an optimal linear transformation part 344A is constructed which is secure against differential and linear cryptanalysis. According to the present invention, the linear transformation part 344A is represented as an n×n matrix P over {0, 1}, and the optimal linear transformation part 344A is constructed by determining elements of the matrix P in such a manner as to minimize the maximum differential and linear characteristic probabilities p, q. In this instance, a linear transformation part using the subkey k_i1, which is contained in the second key-dependent linear transformation part 344, is added as a key-dependent transformation part 344B to the linear transformation part 344A determined by the matrix P as depicted in FIG. 7.

[0107] Incidentally, what is intended to mean by the word “optimal” is to provide the highest resistance to differential and linear cryptanalysis in the linear transformation part 344A of the above configuration, but it does not necessarily mean the optimum for other criteria, for example, an avalanche property. Empirically speaking, however, attacks other than differential and linear cryptanalysis can easily be avoided by only increasing the number of rounds, while it is not certain whether only some increase in the number of rounds serves to prevent differential and linear cryptanalysis unless a careful study is made of the round function used. In view of this, the present invention attaches the most importance to the resistance of the round function to differential and linear cryptanalysis and constructs the optimal linear transformation part 344A accordingly.

[0108] According to the present invention, the linear transformation part 344A in FIG. 6 is represented as the n×n matrix P over {0. 1} as referred to above. This means that the matrix P performs a linear transformation in units of m bits, and that the linear transformation part 344A can be formed by only exclusive ORs. That is, this transformation can be expressed by the following equation: $\begin{array}{cc}{z}_i^{\prime }=\underset{j=0}{\overset{n-1}{\oplus }}{t}_{\mathrm{ij}}{z}_j.& \left(1\right)\end{array}$

[0109] In particular, when m=8, the linear transformation is made in units of bytes, and can be efficiently implemented on any platforms where the word width is 8-bit or more.

[0110] As a concrete example in the case of n=4, a 4×4 matrix P_Ewill be described which is expressed by the following equation: $\begin{array}{cc}\left[\begin{array}{c}{z}_0^{\prime }\\ z_1^{\prime }\\ z_2^{\prime }\\ z_3^{\prime }\end{array}\right]=\left[\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 1& 0\\ 1& 1& 1& 1\end{array}\right]\left[\begin{array}{c}{z}_0\\ z_1\\ z_2\\ z_3\end{array}\right].& \left(2\right)\end{array}$

[0111] The round function using the matrix P_Ehas the following features. Let it be assumed, however, that the S-box is bijective. z′₀, z′₁, z′₂and z′₃defined by the above matrix represent the following operations, respectively.

[0112] z′₀=0·z₀⊕1·z₁⊕1·z₂⊕1·z₃=z₁⊕z₂⊕z₃  (3-1)

[0113] z′₁=1·z₀⊕0·z₁⊕1·z₂⊕1·z₃=z₀⊕z₂⊕z₃  (3-2)

[0114] z′₂=1·z₀⊕1·z₁⊕1·z₂⊕0·z₃=z₀⊕z₁⊕z₂  (3-3)

[0115] z′₃=1·z₀⊕1·z₁⊕1·z₂⊕1·z₃=z₀⊕z₁⊕z₂⊕z₃  (3-4)

[0116] The resistance of the round function to differential and linear cryptanalysis can be determined by the smallest numbers n_d, n₁of active s-boxes, and these values are those determined at the time of determining the matrix P (see Appendix). In differential cryptanalysis an s-box whose input difference value Δx is nonzero is called an active s-box, and in linear cryptanalysis an s-box whose output mask value Γy is nonzero is called an active box.

[0117] In general, when given a certain matrix P, there exist a plurality of constructions of the linear transformation part 344A corresponding thereto. This is because the matrix P represents only the relationship between input and output data of the linear transformation part 344A and does not define its concrete construction. That is, if it is common in the matrix P which represents the relationship between their input and output data, linear transformation parts can be considered to have the same characteristic regardless of their individual constructions. Accordingly, in the following description, the matrix P is determined first which provides high invulnerability against differential and linear cryptanalysis and good avalanche effect, followed by determining the construction of the linear transformation part 344A. This method is more effective in finding out a linear transformation part 344A of an optimal characteristic than a method of checking individual constructions of linear transformation parts to see if they have the optical characteristic.

[0118] The elements of the n×n matrix P are determined by the following search algorithm taking the differential characteristic into account.

[0119] Step 1: Set a security threshold T (where T is an integer such that 2≦T≦n).

[0120] Step 2: Prepare a set C of column vectors whose Hamming weights are equal to or larger than T−1. More specifically, prepare n or more n-dimensional column vectors which have T−1 or more elements “1.”

[0121] Step 3: Select a subset P_cof n column vectors from the set C. Repeat the following steps until all subsets have been checked.

[0122] Step 3-1: Compute n_dfor the subset P_cof n column vectors. This is represented as n_d(P_c).

[0123] Step 3-2: If n_d(P_c)≧T, then accept a matrix P_cconsisting of the n column vectors as a candidate matrix.

[0124] Step 4: Output matrices P and a value n_d(P) that yields the maximum value of n_damong all candidate matrices.

[0125] If the candidate matrix by the above search algorithm is adopted, then it is guaranteed that the value n_dis equal to or larger than T. The matrix P that maximizes n_dcan efficiently be found by incrementing T by one in the order T=n, n−1, . . . , 3, 2 upon each execution of the above search algorithm.

[0126] In the above search algorithm, if it is possible to obtain relatively satisfactory invulnerability against differential and linear cryptanalysis, then a matrix with n_d(P_c)≧T obtained by performing steps up to 3-2 may be used as the desired matrix P. Alternatively, the matrix Pc composed of n vectors whose Hamming weights are equal to or larger than T−1 selected in step 2 after step 1 may be used as the matrix P.

[0127] The input mask values of the linear transformation part 344A can be represented by exclusive ORs of its output mask values, and hence they can be expressed by a certain matrix as is the case with differential characteristic. As the result of our checking the relationship between the matrix for differential characteristic and the matrix for linear expression in several linear transformation parts of different constructions, the following theorem were made.

[0128] Theorem 1: Assume that an n×n matrix P over {0, 1} is given for the linear transformation part 344A. At this time, the relationship between input and output difference values Δz and Δz′ of the linear transformation part 344A (a difference path) is given by the matrix P, and the relationship between input and output mask values Γz and Γz′ (a mask value path) is given by a transposed matrix ^TP. That is,

[0129] Δz′=PΔz  (4)

[0130] Γz=^TPΓz′.  (5)

[0131] (See Appendix) The minimum number n_dof active s-boxes in the difference value path using the matrix P is equal to the minimum number n₁of active s-boxes in the mask value path using the transposed matrix ^TP.

[0132] Because of (See Appendix) n₁is also equal to or larger than T when the candidate matrices by the search algorithm are adopted. For example, in the case of the afore-mentioned matrix P_E, the matrix P_Efor the difference value path and the matrix ^TP_Efor the mask value path bear the following relationship. $\begin{array}{cc}{P}_E=\left[\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 1& 0\\ 1& 1& 1& 1\end{array}\right]\iff {}^{T}P_E=\left[\begin{array}{cccc}0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 0& 1\end{array}\right]& \left(6\right)\end{array}$

[0133] It can be proven that n_d=3 and n₁=3 for the two matrices (see Appendix).

[0134] The following is an algorithm for determining the construction of the linear transformation part 344A when given the matrix P. Here, the following conditions are to be met.

[0135] (1) Minimization of the number of exclusive ORs (XORs), or

[0136] (2) Repeated appearance of the similar subconstruction.

[0137] Step 1: In the matrix P, choose two rows and XOR the one row (rwo a) with the other row (row b) (hereinafter referred to as a primitive operation).

[0138] Step 2: Transform the matrix P into a unit matrix I by repeating the primitive operation, count the number of times the primitive operation was performed, and find a matrix transformation procedure that yields the minimum number of primitive operations.

[0139] Step 3: To construct the linear transformation part 344A, lines A and B, which correspond to the rows a and b chosen in step 2, are XORed in the order reverse to the transformation procedure.

[0140] In FIG. 7 there is depicted a concrete example of the second key-dependent linear transformation part 344 which has the linear transformation part 344A determined as described above. In the linear transformation part 344A, the four pieces of data mid₀₀, mid₀₁, mid₀₂and mid₀₃are input to the processing routes 30₀to 30₃, respectively. In the processing route 30₀, mid₀₀and mid₀₁are XORed by an XOR circuit 31₀; in the processing route 30₂, mid₀₂and the output from the XOR circuit 31₀are XORed by an XOR circuit 31₂; and the output from the XOR circuit 31₂is XORed with mid₀₁by an XOR circuit 31₁.

[0141] In the processing route 30₃, the output from the XOR circuit 31₀and the data mid₀₃are XORed by an XOR circuit 31₃; in the processing route 30₁, the outputs from the XOR circuits 31₁and 31₃are XORed by an XOR circuit 32₁; and in the processing route 30₀, the outputs from the XOR circuit 32₁and 31₀are XORed by an XOR circuit 32₀.

[0142] The outputs from the XOR circuits 32₀, 32₁, 31₂and 31₃and subkey data k_i10, k_i11, k_i12and k_i13are XORed by XOR circuits 35₀to 35₃of the key-dependent transformation part 344B, respectively, from which are provided mid₁₀, mid₁₁, mid₁₂and mid₁₃. In other words, the pieces of data mid₀₀, mid₀₁, mid₀₂and mid₀₃are associated with one another and then undergo linear transformation dependent on the 8-bit subkey data k_i10, k_i11, k_i12and k_i13, respectively. In short, logical operations given by the following logical expression are performed.

[0143] mid₁₀=mid₀₀⊕mid₀₂⊕mid₀₃⊕k_i10  (7-1)

[0144] mid₁₁=mid₀₁⊕mid₀₂⊕mid₀₃⊕k_i11  (7-2)

[0145] mid₁₂=mid₀₀⊕mid₀₁⊕mid₀₂⊕k_i12  (7-3)

[0146] mid₁₃=mid₀₀⊕mid₀₁⊕mid₀₃⊕k_i13  (7-4)

[0147] Incidentally, the subkey k_i1is composed of four pieces of data k_i10, k_i11, k_i12and k_i13.

[0148] As depicted in FIG. 5, these pieces of data mid₁₀, mid₁₁, mid₁₂and mid₁₃are then nonlinearly transformed in the nonlinear transformation parts 345₀, 345₁, 345₂and 345₃into the data out₀, out₁, out₂and out₃, respectively, which are combined into the single piece of data Y_i* in the combining part 346. Finally, the data Y_i* is linearly transformed into the data Y_iby, for example, a k_i2-bit left rotation in the third key-dependent linear transformation part 347 using the key data k_i2, thereby generating the output data Y_ifrom the nonlinear function part 304. The nonlinear transformation parts 343₀to 343₃and 345₀to 345₃function just like S-boxes for DES cipher, and they are constructed by, for example, ROM, which receives input data as an address to read out therefrom the corresponding data.

[0149] Since the four nonlinear transformation parts 343₀to 343₃are arranged in parallel and their transformation processes are not associated with one another, hence they can be executed in parallel. The same goes for the nonlinear transformation parts 345₀to 345₃. Thus, the each linear transformation part can be executed in one step for each group (a total of two steps in the nonlinear function part 304). Letting p represent the differential/liner probability of the nonlinear transformation parts 343₀to 343₃and 345₀to 345₃, the nonlinear function part 304 provides a differential/linear probability p⁴as a whole when the second key-dependent linear transformation 344 has such a construction as shown in FIG. 7. Accordingly, when the number of rounds of the entire data transformation device is 3r, an approximate representation is obtained with a probability P≦p^8r; for example, when r=4 (12 rounds), P≦p³². In the case of DES cipher, this corresponds to 48 or more rounds, ensuring sufficiently secure against differential cryptanalysis and linear cryptanalysis.

[0150] Incidentally, the pieces of key data fk, k₀₀, k₀₁, k₀₂, k₁₀, k₁₂, . . . , k_(N−1)1, k_(N−1)2, ek are data stored in the key storage part 322 in FIG. 4 after being transformed in the expanded key generation part 321 from the master key Key input via the key input part 320 of the key scheduling part 20. The generation of key data in the expanded key generation part 321 may be the same as in the expanded key generation part 21 for DES cipher in FIG. 1, or as in the expanded key generation part 21 by Miyaguchi et al. depicted in FIG. 3.

[0151] The initial key-dependent transformation 302 and the final key-dependent transformation part 308 shown in FIG. 4 and the key-dependent linear transformation parts 341, 344 and 347 in each nonlinear function part 304 shown in FIG. 5 are linear transformation parts which depend on keys; therefore, the device of this embodiment is a cryptographic device which is sufficiently secure against both of differential cryptanalysis and linear cryptanalysis and hence attaches primary importance to security.

[0152] The present invention is not limited specifically to this example; for example, if speedup is demanded, it is feasible to omit or modify any one of the initial key-dependent transformation part 302, the final key-dependent transformation part 308 and the key-dependent linear transformation parts 341, 344 and 347 to a key-independent transformation part. In this case, the encryption speed can be increased without significantly diminishing the security against differential cryptanalysis and the linear cryptanalysis.

[0153] Second Embodiment

[0154] A description will be given of another embodiment of the nonlinear function part 304 of FIG. 5 in a data transformation device of the same construction as that of the first embodiment depicted in FIG. 4. In this embodiment the nonlinear transformation parts 343₀, 343₁, 343₂and 343₃in FIG. 5 are replaced with nonlinear transformation parts 343₀′ to 343₃′ which nonlinearly transform, for example, 8-bit inputs in₀to in₃into 32-bit expanded data MID₀₀, MID₀₁, MID₀₂and MID₀₃as equivalently shown in FIGS. 8A to 8D, respectively; furthermore, the key-dependent linear transformation part 344 has such a construction as depicted in FIG. 9.

[0155] As is the case with the FIG. 5, the data R_iis input to the nonlinear function part 304 together with the key data k_i0, k_i1and k_i2. The data R_iis linearly transformed into data R_i*=R_i⊕k_i0, for example, by being XORed with the key data k_i0in the first key-dependent linear transformation part 341. Next, the data R_i* is split into four pieces of data in₀, in₁, in₂and in₃in the splitting part 342. The four pieces of data in₀, in₁, in₂and in₃are nonlinearly transformed into data MID₀₀, MID₀₁, MID₀₂and MID₀₃in the nonlinear transformation parts 343₀′, 343₁′, 343₂′ and 343₃′ depicted in FIGS. 8A to 8D, respectively. In the first embodiment the nonlinear transformation part 343₀outputs the m-bit data mid₀₀for the m-bit input in₀, whereas in this embodiment the nonlinear transformation part 343₀′ has an S-box that outputs the same m-bit data mid₀₀as high-order m bits as does the nonlinear transformation part 343₀in the first embodiment of FIG. 5 and outputs fixed data “00 . . . 0₍₂₎” as low-order m bits; further, the nonlinear transformation part is designed to output the high-order m-bit data mid₀₀to three routes by duplicating and output the m-bit data “00 . . . 0₍₂₎.” That is, the nonlinear transformation part 343₀′ is means for transforming the m-bit data in₀to 4m-bit data

[0156] MID₀₀=[mid₀₀, 00 . . . 0₍₂₎, mid₀₀, mid_00]  (8-1)

[0157] Similarly, the nonlinear transformation parts 343₁′, 343₂′ and 343₃′ are means for transforming the input data in1, in2 and in3 to

[0158] MID₀₁=[00 . . . 0₍₂₎, mid₀₁, mid₀₁, mid_01]  (8-2)

[0159] MID₀₂=[mid₀₂, mid₀₂, mid₀₂, 00 . . . 0_(2)]  (8-3)

[0160] MID₀₃=[mid₀₃, mid₀₃, 00 . . . 0₍₂₎, mid_03]  (8-4)

[0161] The data MID₀₀expressed by Equation (8-1) can be determined by presetting as MID₀₀the entire data which is provided in the four output routes of the linear transformation part 344A when the pieces of data mid₀₁, mid₀₂and mid₀₃except mid₀₀are each set as “00 . . . 0₍₂₎.” Similarly, the data MID₀₁, MID₀₂and MID₀₃expressed by Equations (8-2), (8-3) and (8-4) can also be easily determined. These nonlinear transformation parts 343₀′ to 343₃′ may be constructed in memory as transformation tables from which to read out the data MID₀₀, MID₀₁, MID₀₂and MID₀₃by using the data in₀, in₁, in₂and in₃as addresses.

[0162] Then, these pieces of data MID₀₀to MID₀₃are input to the second key-dependent linear transformation part 344 with the key data k_i1as depicted in FIG. 9. MID₀₀and MID₀₁are XORed by an XOR circuit 41; MID₀₂and MID₀₃are XORed by an XOR circuit 42; the outputs from the XOR circuits 41 and 42 are XORed by an XOR circuit 43; and the output from the XOR circuit 43 and the key data k_i1are XORed by an XOR circuit 44. The output MID1 from the XOR circuit 44 is split into m-bit outputs mid₁₀, mid₁₁, mid₁₂and mid₁₃. After all, the second key-dependent linear transformation part 344 linearly transforms the input data by the following operation:

[0163] MID₁=MID₀₀⊕MID₀₁⊕MID₀₂⊕MID₀₃⊕k_i1.  (9)

[0164] The components of the output MID₁=[mid₁₀, mid₁₁, mid₁₂, mid₁₃] by this linear transformation operation are expressed by the following equations, respectively:

[0165] mid₁₀=mid₀₀⊕mid₀₂⊕mid₀₃⊕k_i10  (10-1)

[0166] mid₁₁=mid₀₁⊕mid₀₂⊕mid₀₃⊕k_i11  (10-2)

[0167] mid₁₂=mid₀₀⊕mid₀₁⊕mid₀₂⊕k_i12  (10-3)

[0168] mid₁₃=mid₀₀⊕mid₀₁⊕mid₀₃⊕k_i13  (10-4)

[0169] These linear transformation operations are equivalent to those in FIG. 7 given by Equations (7-1) to (7-4). In this way, the same pieces of data mid₁₀, mid₁₁, mid₁₂and mid₁₃as those in the first embodiment are generated. Incidentally, k_i1is composed of four pieces of data k_i10, k_i1, k_i12and k_i13

[0170] Then, the four pieces of data mid₁₀, mid₁₁, mid₁₂and mid₁₃are nonlinearly transformed into data out₀, out₁, out₂and out₃in the nonlinear transformation parts 345₀, 345₁, 345₂and 345₃, respectively, as in the FIG. 5, and in the combining part 346 the four pieces of data out₀, out₁, out₂and out₃are combined into the single piece of data Y_i*. Finally, the data Y_i* is linearly transformed into the data Y_iby, for example, a k_i2-bit left rotation in the third key-dependent linear transformation part 347 using the key data k_i2, thereby generating the output data Y_ifrom the nonlinear function part 304.

[0171] In the second embodiment depicted in FIGS. 8A to 8D and 9, it is also possible to form, as is the case with the first embodiment, the nonlinear transformation parts 343₀to 343₃of FIGS. 8A to 8D by only S-boxes which output 8-bit data mid₀₀to mid₀₃, respectively, and to provide the wirings shown in FIGS. 8A to 8D and a register which outputs 8-bit data “00 . . . 0” in the key-dependent linear transformation part 344 to generate therein the data MID₀₀to MID₀₃.

[0172] The second key-dependent linear transformation part 344 in this embodiment implements linear transformation equivalent to that shown in FIG. 7 through the use of four XOR circuits as depicted in FIG. 9 (in FIG. 7 ten XORs), and hence permits faster transformation than in the first embodiment.

[0173] Furthermore, as is the case with the first embodiment, the four nonlinear transformation parts 343₀to 343₃and 345₀to 345₃are arranged in parallel and their nonlinear transformation processes are not associated with one another, and hence they can be executed in parallel. Besides, letting p represent the differential/liner probability of the nonlinear transformation parts 343₀to 343₃and 345₀to 345₃, the differential/linear probability of the nonlinear function 304 becomes p⁴as a whole.

[0174] Third Embodiment

[0175] A description will be given of another embodiment of the nonlinear function part 304 of still another functional configuration in the data transformation device that has the functional configuation depicted in FIG. 4 as in the first embodiment.

[0176] As depicted in FIG. 5, for example, a 32-bit data R_iis input to the nonlinear function part 304 together with the key data k_i0, k_i1and k_i2stored in the key storage part 322. The data R_iis linearly transformed into data R_i*=R_i⊕k_i0by, for example, XORing with the key data k_i0in the first key-dependent linear transformation part 341. Then the data R_i* is split into four pieces of, for example, 8-bit data in₀, in₁, in₂and in₃in the splitting part 342.

[0177] In the nonlinear transformation part 343₀, as shown in FIG. 10, for instance, the data in₀is further split into two, for example, 4-bit subblocks in₀₀and in₀₁; the subblock in₀₀is transformed to data mid₀₀₀in a sub-nonlinear transformation part 51 and, at the same time, it is XORed with the data in₀₁by an XOR circuit 52, whose output in₀₀⊕in₀₁is transformed into data mid₀₀₁in a sub-nonlinear transformation part 53. Thereafter, these outputs mid₀₀₀and mid₀₀₁are XORed by an XOR circuit 54, and its output and the data mid₀₀₁are combined into the data mid₀₀. That is, the nonlinear transformation part 343₀splits the input in₀into two subblocks, then performs linear transformation and nonlinear transformation of the two subblocks, and combines the two resulting output subblocks into the output from the nonlinear transformation part. Similarly, the other remaining pieces of data in₁, in₂and in₃are also transformed into the data mid₀₁, mid₀₂and mid₀₃in the nonlinear transformation parts 343₁, 343₂and 343₃each having the functional configuration shown in FIG. 10 which comprises two nonlinear transformation parts and two XOR circuits.

[0178] These pieces of transformed data mid₀₀, mid₀₁, mid₀₂and mid₀₃input to the second key-dependent linear transformation part 344 depicted in FIG. 7 which uses the key data k_i1. The transformation part 344 performs the aforementioned operations of Equations (7-1) to (7-4).

[0179] Then, the data mid₁₀is input to.the nonlinear transformation part 345₀of the same functional consfiguration as shown in FIG. 10, wherein it is further split into two subblocks mid₁₀₀and mid₁₀₁. The subblock mid₁₀₀is transformed into data out₀₀in the sub-nonlinear transformation part 51. The subblocks mid₁₀₀and mid₁₀₁are XORed by the XOR circuit 52, and its output mid₁₀₀⊕mid₁₀₁is transformed into data out₀₁in the nonlinear transformation part 53. Then, the two pieces of data out₀₀and out₀₁are XORed by the XOR circuit 54, and its output out₀₀⊕out₀₁and the data out₀₁are combined into out₀. Similarly, the other remaining pieces of data mid₁₁, mid₁₂and mid₁₃are also transformed into the data out₁, out₂and out₃in the nonlinear transformation parts 345₁, 345₂and 345₃each having the functional configuration shown in FIG. 10 which comprises the two sub-nonlinear transformation parts 51, 53 and the two XOR circuits 52, 54.

[0180] The four pieces of thus nonlinearly transformed data out₀, out₁, out₂and out₃are combined into a single piece of data Y_i* in the combining part 346. Finally, the data Y_i* is linearly transformed into data Y_i, for example, by a k_i2-bit left rotation in the third key-dependent linear transformation part 347 using the key data k_i2, by which the output data Y_ifrom the nonlinear function part 304 is generated.

[0181] As described above, according to this embodiment, in each of the nonlinear transformation parts 343₀to 343₃and 345₀to 345₃the input data is split to two pieces of data, which are nonlinearly transformed in the two sub-nonlinear transformation parts (51 and 53 in FIG. 10). Hence, it is possible to input to the nonlinear transformation parts 343₀to 343₃and 345₀to 345₃data of a bit length twice larger than that of data that the 16 sub-nonlinear transformation parts can handle. For example, assuming that the sub-nonlinear transformation parts 51 and 53 are 8-bit S-boxes, each input data to the nonlinear transformation parts 343₀to 343₃and 345₀to 345₃is 16 bits length and the input data to the nonlinear function part 304 is 64 bits length. As a result, the block length in the data transformation device of FIG. 4 can be made 128 bits length.

[0182] The sub-nonlinear transformation parts 51 and 53 are arranged in parallel in groups of eight and their nonlinear transformation processes are not associated with one another, and hence they can be executed in parallel. Further, letting p represent the differential/linear probabilities of the sub-nonlinear transformation parts 51 and 53, the nonlinear function part 304 provides a differential/linear probability p⁴as a whole.

[0183] In the above, the first key-dependent linear transformation part 341, the second key-dependent transformation part 344 and the third key-dependent transformation part 347 need not always be key-dependent, i.e., the linear transformation may be performed in subdata.

[0184] While in the above the data processing has been described to be performed using a hardware structure, it may also be implemented by software that follows a program. For example, FIG. 11 is a flowchart showing the principal part of the procedure for data processing. FIG. 11 shows the procedure corresponding to the entire procedure of FIG. 4.

[0185] Step S1: Initialize to 0 a variable i representing the repeat count of processing.

[0186] Step S2: Perform initial transformation of an input plaintext and split it into left and right block data L_iand R_i.

[0187] Step S3: Process the right block data R_iby a nonlinear function using the subkey k_ito generate the block data Y_i.

[0188] Step S4: Perform linear processing of the left block data R_iby the block data Y_ito generate the block data L_i*.

[0189] Step S5: Change the right block data R_ito new left block data L_iand the block data L_i* to new right block data R_i.

[0190] Sep S6: Increment the variable i by one.

[0191] Step S7: Check to see if i has reached N, and if not, return to step S3 and repeat steps S3 to S7.

[0192] Step S8: If it is decided in step S7 that the variable i has reached N, combine the left and right data L_iand R_iand output the result of final transformation as output data C.

[0193] Details of the process by step S3 in FIG. 11 correspond to the process by the nonlinear function part 304 shown in FIG. 5, and the procedure is depicted in FIG. 12.

[0194] Step S31: Perform first key-dependent linear transformation of the right data R_iinto the data R_i*.

[0195] Step S32: Split the data R_i* into n m-bit data in₀, in₁, . . . in_n−1(where m=8 and n=4, for instance).

[0196] Step S33: Read out data mid₀₀, mid₀₁, . . . , mid_0(n−1)from n first S-boxes using the data in₀, in₁, . . . , in_n−1as addresses.

[0197] Step S34: Perform key-dependent linear transformation of the data mid₀₀to mid_0(n−1)by the subkey k_i1to generate data mid₁₀to mid_1(n−1).

[0198] Step S35: Read out data out₀to out_n−1from n second S-boxes using the data mid₁₀to mid_1(n−1)as addresses.

[0199] Step S36: Combine the data out₀to out_n−1into data Y*_i.

[0200] Step S37: Perform third key-dependent linear transformation of the data Y*_ito generate data Y_iand output it.

[0201] The operations in step S34 may be the operations by Equations (7-1) to (7-4) or Equation (9) using the definitions by Equations (8-1) to (8-4). While FIG. 11 depicts the procedure that repeats steps S3 to S7 by the number of rounds involved, the individual processes by the round processing parts 38₀to 38_N−1shown in FIG. 4 may also be programmed intact to implement the data diffusion part according to the present invention.

[0202] Fourth Embodiment

[0203] The first embodiment depicted in FIG. 4 is an embodiment in which the basic linear transformation part 344A of FIG. 6, which constitutes the second key-dependent linear transformation part 344 of the nonlinear function part 304 (FIG. 5), is represented by a 4×4 matrix (that is, four inputs-four outputs). The fourth embodiment will be described below in connection with the case where the linear transformation part 344A is represented by an 8×8 matrix.

[0204] FIG. 13 illustrates the fimction configuration of the encryption procedure in the data transformation device according to the fourth embodiment of the present invention. This configuration itself is identical with that of the first embodiment but differs from the latter in the data length and the split number n of data to be split in the nonlinear function part 304.

[0205] The input data M is transformed in the initial key-dependent transformation part 302 using the key data fk stored in the key storage part 322 and is split to left and right block data L₀and R₀in the initial splitting part 303. For example, 128-bit data is split into two pieces of 64-bit block data L₀and R₀. The key-dependent initial transformation part 302 performs a linear transformation such as exclusive ORing of the key data fk and the input data M or bit rotation of the input data M by the key data fk, or nonlinear transformation by a combination of multiplications.

[0206] The right block data R₀is provided to the nonlinear function part 304 together with the key data k₀₀, k₀₁and k₀₂stored in the key storage part 322, and in the nonlinear function part 304 it is nonlinearly transformed to data Y₀. The data Y₀and the data L₀are transformed by a linear operation to data L₀* in the linear operation part 305. The data L₀* and the data R₀undergo data-position swapping in the swapping part 306 to provide L₁←R₀and R₁←L₀*, and the pieces of data L₁and R₁are fed to the next first round processing part 38₁.

[0207] Thereafter, in an i-th round processing parts 38_i(where i=0, 1, . . . , N−1) the same processing as mentioned above is repeated for two pieces of input block data L_iand R_i. That is, the right block data R_iis input to the nonlinear function part 304 together with the key data k_i0, k_i1and k_i2, and in the nonlinear function part 304 it is nonlinearly transformed to block data Y_i. The block data Y_iand the block data L_iare transformed to data L_i* by a linear operation in the linear operation part 305. The data L_i* and the data R_iare swapped in data position in the swapping part 306, that is, L_i+1←R_i, R_i+1←L_i*. The linear operation part 305 is to perform, for instance, an exclusive OR operation.

[0208] Letting N represent the number of rounds suitable to provide security of a data transformation device, two pieces of left and right data L_Nand R_Nare obtained as the result of such repeated processing. These pieces of data L_Nand R_Nare combined into a single piece of block data in the final combining part 307; for example, the two pieces of 64-bit data L_Nand R_Nare combined to 128-bit data. Then the thus combined data is transformed in a final linear transformation part 308 using the key data ek stored in the key storage part 322, and output data C is provided as a ciphertext from the output part 309.

[0209] In decryption, the plaintext M can be derived from the ciphertext C by reversing the encryption procedure. In particular, when the key-dependent final transformation part 308 is one that performs transformation inverse to that of the key-dependent initial transformation part 302, the decryption can be done by inputting ciphertext data in place of the input data in FIG. 13 and then inputting the key data in a sequential order reverse to that in FIG. 13, that is, ek, k_(N−1)0, k_(N−1)1, k_(N−1)2, . . . , k₁₀, k₁₁, k₁₂, k₀₀, k₀₁, k₀₂, fk.

[0210] Next, a detailed description will be given of the internal configuration of the nonlinear function part 304. FIG. 14 is a diagrammatic showing of the internal functional configuration of the nonlinear function part 304.

[0211] The right block data R_iis input to the nonlinear function part 304 together with the key data k_i0, k_i1and k_i2stored in the key storage part 322.

[0212] In the first key-dependent linear transformation part 341 the right block data R_iis transformed to data R_i*=R_i⊕k_i0, for example, by XORing with the subkey data k_i0. The thus transformed data R_i* is split to n=8 pieces of data in₀, in₁, in₂, . . . , in₇in the splitting part 342. The eight pieces of data in₀to in₇are nonlinearly transformed to data mid₀₀to mid₀₇in nonlinear transformation parts 343₀to 343₇, thereafter being input to the second key-dependent linear transformation part 344 using the key data k_i1.

[0213] The second key-dependent linear transformation part 344 performs linear transformation (XORing) among the pieces of data mid₀₀, mid₀₁, mid₀₂, . . . , mid₀₇input from eight routes to provide new data of eight routes, and further performs linear transformation (XORing) among these pieces of data of the eight routes with eight parts of the key data k_i1to provide output data mid₁₀, mid₁₁, mid₁₂, . . . , mid₁₇of the eight routes. The eight pieces of data are input to nonlinear transformation parts 345₀, 345₁, 345₂, . . . , 345₇, wherein they are transformed to data out₀, out₁, out₂, . . . , out₇, respectively. These eight pieces of data are combined into data Y_i* in a combining part 346; furthermore, in the third key-dependent linear transformation part 347 the data Y_i* undergoes linear transformation with the key data k_i2to generate output data Y_i.

[0214] The second key-dependent linear transformation part 344 contains the linear transformation part 344A expressed by an n×n matrix as described previously with respect to FIG. 6; in this embodiment n=8. In this instance, assume that the linear transformation part is bijective. That is, rank(P)=8. A description will be given of the determination of an 8×8 matrix P that yield a maximum value of n_das described in the embodiment 1. In this instance, the security threshold T is reduced one by one in the order T=8, 7. . . . , and the following algorithm is executed for each value.

[0215] Step 1: Set the security threshold T (where T is an integer such that 2≦T≦n).

[0216] Step 2: Prepare a set of column vectors C whose Hamming weights are equal to or larger than T−1.

[0217] Step 3: Select a subset P_cof eight column vectors from the set C. If rank(P_c)≠8, then the subset P_cis not accepted as a candidate.

[0218] Step 3-1: Compute n_dfor P_cas follows.

[0219] For any two columns (columns a, b): $n_{\mathrm{d0}}=2+{\underset{\left(a,b\right)}{\min }}^{\#\left\{\left(t_{\mathrm{ia}},t_{\mathrm{ib}}\right)❘t_{\mathrm{ia}}\oplus t_{\mathrm{ib}}\ne 0,0\le i\le 8\right\}}$

[0220] For any three columns (columns a, b, c): $n_{\mathrm{d1}}=3+{\underset{\left(a,b,c\right)}{\min }}^{\#\left\{\left(t_{\mathrm{ia}},t_{\mathrm{ib}},t_{\mathrm{ic}}\right)❘t_{\mathrm{ia}}\oplus t_{\mathrm{ib}}\oplus t_{\mathrm{ic}}\ne 0,0\le i\le 8\right\}}$ $n_{\mathrm{d2}}=3+{\underset{\left(a,b,c\right)}{\min }}^{\#\{\left(t_{\mathrm{ia}},t_{\mathrm{ib}},t_{\mathrm{ic}}\right)❘}$

[0221] Exception of (0,0,0),(1,1,1), 0≦i≦8}

[0222] For any four columns (columns a, b, c, d): $n_{\mathrm{d3}}=4+{\underset{\left(a,b,c,d\right)}{\min }}^{\#\left\{\left(t_{\mathrm{ia}},t_{\mathrm{ib}},t_{\mathrm{ic}},t_{\mathrm{id}}\right)❘\begin{array}{c}\left(0,0,0,1\right),\left(0,0,1,0\right),\left(1,0,0,0\right)\\ \left(0,1,1,1\right),\left(1,0,1,1\right),\left(1,1,1,0\right)\end{array},0\le i<8\right\}}$ $n_{\mathrm{d4}}=4+{\underset{\left(a,b,c,d\right)}{\min }}^{\#\{\left(t_{\mathrm{ia}},t_{\mathrm{ib}},t_{\mathrm{ic}},t_{\mathrm{id}}\right)❘}$

[0223] Exception of (, 0≦i<8} $n_{\mathrm{d5}}=4+{\underset{\left(a,b,c,d\right)}{\min }}^{\#\{\left(t_{\mathrm{ia}},t_{\mathrm{ib}},t_{\mathrm{ic}},t_{\mathrm{id}}\right)❘}$

[0224] Exception of (, 0≦i<8} $n_{\mathrm{d6}}=4+{\underset{\left(a,b,c,d\right)}{\min }}^{\#\{\left(t_{\mathrm{ia}},t_{\mathrm{ib}},t_{\mathrm{ic}},t_{\mathrm{id}}\right)❘}$

[0225] Exception of (, 0≦i<8} $n_{\mathrm{d7}}=4+{\underset{\left(a,b,c,d\right)}{\min }}^{\#\{\left(t_{\mathrm{ia}},t_{\mathrm{ib}},t_{\mathrm{ic}},t_{\mathrm{id}}\right)❘}$

[0226] Exception of (, 0≦i<8} $n_{\mathrm{d8}}=4+{\underset{\left(a,b,c,d\right)}{\min }}^{\#\{\left(t_{\mathrm{ia}},t_{\mathrm{ib}},t_{\mathrm{ic}},t_{\mathrm{id}}\right)❘}$

[0227] Exception of (, 0≦i<8} $n_{\mathrm{d9}}=4+{\underset{\left(a,b,c,d\right)}{\min }}^{\#\{\left(t_{\mathrm{ia}},t_{\mathrm{ib}},t_{\mathrm{ic}},t_{\mathrm{id}}\right)❘}$

[0228] Exception of (, 0≦i<8}

[0229] n_d=min{n_di|0≦i≦9}

[0230] Intuitively, Equations n_d0to n_d9represent the minimum number of active s-boxes in the second nonlinear transformation part 345 (second term on the right-hand side) and the total number of active s-boxes (the left-hand side) at that time, when the number of active s-boxes in the first nonlinear transformation part 343 (first term on he right-hand side) is determined. For example, when there are two active s-boxes in the first nonlinear transformation part 343, its difference values can be represented as Δz_aand Δz_b, respectively. At this time,

[0231] [Δz′_i]=[t_iaΔz_a⊕t_ibΔz_b](0≦i<8)  (11)

[0232] In particular, when Δz_a=Δz_b,

[0233] [Δz′_i]=[(t_ia⊕t_ib)Δz_n](0≦i<8)  (12)

[0234] Accordingly, the minimum number of active s-boxes in this case is given by n_d0.

[0235] As a result of our search for the matrix P through of the above search algorithm, it has been found that there is no matrix with n_d≧6=T but that there are 10080 candidate matrices with n_d=5=T. Hence, the invulnerability of the round function using such a matrix P against differential cryptanalysis is p≦p_s⁵. And the invulnerability against linear cryptanalysis is also q≦p_s⁵.

[0236] The construction of the linear transformation part is determined among the above-mentioned 10080 candidate matrices P. The determination of the construction by an exhaustive search involves a computational complexity of approximately (8×7)¹⁶≈2⁹³when 16 XORs are used—this is impossible to perform. Then, the construction is limited to one that the linear transformation part 344A is composed of four boxes B1 to B4 with 8 inputs and 4 outputs as depicted in FIG. 15A. The boxes are each formed by four XOR circuits. as shown in FIG. 15B and designed so that every input line passes through one of the XOR circuit. Accordingly, the linear transformation part 344A comprises a total of 16 XOR circuits. In this instance, the computational complexity is around (4×3×2×1)⁴≈2¹⁸, which is sufficiently small for the exhaustive search.

[0237] While in FIG. 15A four transformation boxes are alternately inserted in the lines of left and right four routes, these lines may be determined to be arbitrarily selected four lines and the other remaining four lines. Each transformation box is supplied with inputs from the four lines in which it is inserted and inputs from the remaining four lines and outputs the results of transformation to the former four lines.

[0238] As the result of searching the 10080 matrices obtained by the above search algorithm for matrices which constitute the unit matrix I with 16 primitive operations (XORs) while satisfying the construction of FIG. 15, it was found that there are 57 constructions. The matrix P of one of such construction is shown below. $\begin{array}{cc}P=\left[\begin{array}{cccccccc}0& 1& 1& 1& 1& 1& 1& 0\\ 1& 0& 1& 1& 0& 1& 1& 1\\ 1& 1& 0& 1& 1& 0& 1& 1\\ 1& 1& 1& 0& 1& 1& 0& 1\\ 1& 1& 0& 1& 1& 1& 0& 0\\ 1& 1& 1& 0& 0& 1& 1& 0\\ 0& 1& 1& 1& 0& 0& 1& 1\\ 1& 0& 1& 1& 1& 0& 0& 1\end{array}\right]& \left(13\right)\end{array}$

[0239] In FIG. 16 there is depicted an example of the construction of the linear transformation part 344A using this matrix, together with the nonlinear transformation parts 343 and 345. As shown, four transformation boxes B1 to B4 are alternately inserted in lines of four left and right routes from eight S-boxes forming the first linear transformation part 343, and consequently, two XOR circuits are inserted in each line.

[0240] As is the case with the 4×4 matrix in the first embodiment, it can be as certained as mentioned below whether the matrix for the mask value path is a transposed matrix of the matrix P in the linear transformation part 344A of FIG. 16 and whether n₁=5 correctly holds. By constructing a mask value path in the linear transformation part 344A of FIG. 16 using concatenation rules defined by Theorem 2 in the Appendix, the matrix ^TP for the mask value path can be computed as follows: $\begin{array}{cc}{\hspace{0.17em}}^{T}P=\left[\begin{array}{cccccccc}0& 1& 1& 1& 1& 1& 0& 1\\ 1& 0& 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1& 1& 1\\ 1& 1& 1& 0& 1& 0& 1& 1\\ 1& 0& 1& 1& 1& 0& 0& 1\\ 1& 1& 0& 1& 1& 1& 0& 0\\ 1& 1& 1& 0& 0& 1& 1& 0\\ 0& 1& 1& 1& 0& 0& 1& 1\end{array}\right]& \left(14\right)\end{array}$

[0241] This indicates that the matrix ^TP is a transposed matrix of the matrix P. Further, it can be confirmed that the minimum number of active s-boxes is n₁=5.

[0242] FIG. 17 illustrates concrete examples of the second key-dependent linear transformation part 344 which comprises the linear transformation part 344A of the construction determined above and a key transformation part 344B.

[0243] The key transformation part 344B calculates the XORs of the key data k_i10, k_i11, k_i12, . . . , k_i17and the outputs from the linear transformation part by XOR circuits 63₀, 63₁, 63₂, . . . , 63₇, and yield output data mid₁₀, mid₁₁, mid₁₂, . . . , mid₁₇. With such a functional construction as depicted in FIG. 17, the following operations are performed.

[0244] mid₁₀=mid₀₁⊕mid₀₂⊕mid₀₃⊕mid₀₄⊕mid₀₅⊕mid₀₆⊕k_i10  (15-1)

[0245] mid₁₁=mid₀₀⊕mid₀₂⊕mid₀₃⊕mid₀₅⊕mid₀₆⊕mid₀₇⊕k_i11  (15-2)

[0246] mid₁₂=mid₀₀⊕mid₀₁⊕mid₀₃⊕mid₀₄⊕mid₀₆⊕mid₀₇⊕k_i12  (15-3)

[0247] mid₁₃=mid₀₀⊕mid₀₁⊕mid₀₂⊕mid₀₄⊕mid₀₅⊕mid₀₇⊕k_i13  (15-4)

[0248] mid₁₄=mid₀₀⊕mid₀₁⊕mid₀₃⊕mid₀₄⊕mid₀₅⊕k_i14  (15-5)

[0249] mid₁₅=mid₀₀⊕mid₀₁⊕mid₀₂⊕mid₀₅⊕mid₀₆⊕k_i15  (15-6)

[0250] mid₁₆=mid₀₁⊕mid₀₂⊕mid₀₃⊕mid₀₆⊕mid₀₇⊕k_i16  (15-7)

[0251] mid₁₇=mid₀₀⊕mid₀₂⊕mid₀₃⊕mid₀₄⊕mid₀₇⊕k_i17  (15-8)

[0252] The above operations generate the data mid₁₀, mid₁₁, mid₁₂, . . . , mid₁₇. Incidentally, the subkey k_i1is composed of eight pieces of data k_i10, k_i11, k_i12, . . . , k_i17. In FIG. 17, the pieces of data mid₀₀to mid₀₇are input to routes 60₀to 60₇, respectively.

[0253] The XOR circuits 61₄, 61₅, 61₆, 61₇on the routes 60₄, 60₅, 60₆, 60₇calculate the XORs of the data mid₀₄and mid₀₀, mid₀₅and mid₀₁, mid₀₆and mid₀₂, mid₀₇and mid₀₃, respectively.

[0254] The XOR circuits 61₀, 61₁, 61₂, 61₃on the routes 60₀, 60₁, 60₂, 60₃calculate the XORs of the data mid₀₀and the output from the XOR circuit 61₆, the data mid₀₁and the output from the XOR circuit 61₇, the data mid₀₂and the output from the XOR circuit 61₄, the data mid₀₃and the output from the XOR circuit 61₅, respectively.

[0255] The XOR circuits 62₄, 62₅, 62₆, 62₇on the routes 60₄, 60₅, 60₆, 60₇calculate the XORs of the outputs from the XOR circuits 61₃and 61₄, the outputs from the XOR circuits 61₀and 61₅, the outputs from the XOR circuits 61₁and 61₆, the outputs from the XOR circuits 61₂and 61₇, respectively.

[0256] The XOR circuits 62₀, 62₁, 62₂, 62₃on the routes 60₀, 60₁, 60₂, 60₃calculate the XORs of the outputs from the XOR circuits 61₀and 62₄, the outputs from the XOR circuits 61₁and 62₅, the outputs from the XOR circuits 61₂and 62₆, the outputs from the XOR circuits 61₃and 62₇, respectively.

[0257] Furthermore, the XOR circuits 63₀to 63₇on the routes 60₀to 60₇XOR the outputs from the XOR circuits 62₀to 62₇and the key data k_i10to k_i17, respectively, providing the outputs mid₁₀to mid₁₇from the routes 60₀to 60₇. That is, the outputs mid₁₀to mid₁₇are the XORs of six pieces of data selected from the input data mid₀₀to mid₀₇and the key data, and the outputs mid₁₄to mid₁₇are the XORs of five pieces of data selected from the input data mid₀₀to mid₀₇and the key data.

[0258] Turning back to FIG. 14, the pieces of data mid₁₀, mid₁₁, mid₁₂, . . . , mid₁₇are nonlinearly transformed to pieces of data out₀, out₁, out₂, . . . , out₇in the nonlinear transformation parts 345₀, 345₁, 345₂, . . . , 345₇, and in the combining part 346 the eight pieces of data out₀, out₁, out₂, . . . , out₇are combined into a single piece of data Y_i*. Finally, the data Y_i* is linearly transformed to data Y_i, for example, by a k_i2-bit left rotation in the third key-dependent linear transformation 347 using the key data k_i2, thereby generating the output data Y_ifrom the nonlinear function part 304.

[0259] The nonlinear transformation parts 343₀to 343₇and 345₀to 345₇function just like S-boxes for DES cipher, and they are each formed by, for example, ROM, which receives input data as an address to read out therefrom the corresponding data.

[0260] The eight nonlinear transformation parts 343₀to 343₇are arranged in parallel and their transformation processes are not associated with one another, and hence they can be executed in parallel. The same goes for the nonlinear transformation parts 345₀to 345₇. Thus, the linear transformation operations can be executed in one step for each group (a total of two steps). Letting p represent the differential/liner probability of the nonlinear transformation parts 343₀to 343₇and 345₀to 345₇, the nonlinear function part 304 provides a differential linear probability p⁵as a whole when the second key-dependent linear transformation 344 has such a construction as shown in FIG. 17. Accordingly, when the number of rounds of the entire data transformation device is 3r, an approximate representation is obtained with a probability P≦p^10r; for example, when r=4 (12 rounds), P≦p⁴⁰. In the case of DES cipher, this corresponds to 60 or more rounds, making it possible to provide a data transformation device sufficiently secure against differential cryptanalysis and linear cryptanalysis. Incidentally, the second key-dependent linear transformation part 344 is not limited specifically to the linear transformation part depicted in FIG. 17 but may be modified as shown in FIG. 18, for instance.

[0261] In this instance, the following operations are conducted.

[0262] mid₁₀=mid₀₁⊕mid₀₂⊕mid₀₄⊕mid₀₅⊕mid₀₆⊕mid₀₇⊕k_i10  (16-1)

[0263] mid₁₁=mid₀₁⊕mid₀₂⊕mid₀₃⊕mid₀₄⊕mid₀₆⊕k_i11  (16-2)

[0264] mid₁₂=mid₀₀⊕mid₀₁⊕mid₀₃⊕mid₀₄⊕mid₀₅⊕mid₀₆⊕k_i12  (16-3)

[0265] mid₁₃=mid₀₀⊕mid₀₃⊕mid₀₄⊕mid₀₆⊕mid₀₇⊕k_i13  (16-4)

[0266] mid₁₄=mid₀₀⊕mid₀₂⊕mid₀₃⊕mid₀₅⊕mid₀₆⊕mid₀₇⊕k_i14  (16-5)

[0267] mid₁₅=mid₀₀⊕mid₀₁⊕mid₀₂⊕mid₀₅⊕mid₀₆⊕k_i15  (16-6)

[0268] mid₁₆=mid₀₀⊕mid₀₁⊕mid₀₂⊕mid₀₃⊕mid₀₄⊕mid₀₇⊕k_i16  (16-7)

[0269] mid₁₇=mid₀₀⊕mid₀₂⊕mid₀₄⊕mid₀₅⊕mid₀₇₆⊕k_i17  (16-8)

[0270] Alternatively, the circuit construction of FIG. 19 may be used, in which case the following operations are performed.

[0271] mid₁₀=mid₀₀⊕mid₀₁⊕mid₀₄⊕mid₀₅⊕mid₀₆⊕k_i10  (17-1)

[0272] mid₁₁=mid₀₁⊕mid₀₃⊕mid₀₄⊕mid₀₅⊕mid₀₇⊕k_i11  (17-2)

[0273] mid₁₂=mid₀₀⊕mid₀₂⊕mid₀₄⊕mid₀₆⊕mid₀₇⊕k_i12  (17-3)

[0274] mid₁₃=mid₀₂⊕mid₀₃⊕mid₀₅⊕mid₀₆⊕mid₀₇⊕k_i13  (17-4)

[0275] mid₁₄=mid₀₀⊕mid₀₁⊕mid₀₃⊕mid₀₅⊕mid₀₆⊕mid₀₇⊕k_i14  (17-5)

[0276] mid₁₅=mid₀₁⊕mid₀₂⊕mid₀₃⊕mid₀₄⊕mid₀₆⊕mid₀₇⊕k_i15  (17-6)

[0277] mid₁₆=mid₀₀⊕mid₀₁⊕mid₀₂⊕mid₀₄⊕mid₀₅⊕mid₀₇⊕k_i16  (17-7)

[0278] mid₁₇=mid₀₀⊕mid₀₂⊕mid₀₃⊕mid₀₄⊕mid₀₅⊕mid₀₆⊕k_i17  (17-8)

[0279] As is evident from the operations in FIGS. 17 to 19, the second key-dependent linear transformation part 344 performs key-dependent linear transformation which yields a total of eight pieces of output data mid₁₀, mid₁₁, mid₁₂, . . . , mid₁₇, that is, four pieces of output data derived from six pieces of data selected from the eight pieces of input data mid₀₀, mid₀₁, mid₀₂, . . . , mid₀₇and four pieces of output data derived from five pieces of data selected from the eight pieces of input data. If this linear transformation is one that the eight pieces of input data mid₀₀, mid₀₁, mid₀₂, . . . , mid₀₇each affect the output data of at least four or more other routes (for instance, in the FIG. 17 example the input data mid₀₀affects the six pieces of output data mid₁₁, mid₁₂, mid₁₃, mid₁₄, mid₁₅and mid₁₇), the nonlinear function part 304 provides a differential/linear probability p⁵as a whole as described previously with reference to the FIG. 17.

[0280] The key data {fk, k₀₀, k₀₁, k₀₂, k₁₀, k₁₁, k₁₂, . . . , k_(N−1)0, k_(n−1)1, k_(N−1)2, ek} is data provided by inputting the master key via the key input part 320 to the expanded key generation part 321, transforming it to key data and storing it in the key storage part 322.

[0281] The expanded key generation part 321 may be made identical in construction with the expanded key generation part 21 for DES cipher shown in FIG. 1, or an expanded key generation part disclosed in U.S. Pat. No. 4,850,019.

[0282] Since the initial key-dependent transformation part 302, the final key-dependent transformation part 308 and the key-dependent linear transformation parts 341, 344 and 347 are key-dependent linear transformation means, the data transformation device is also sufficiently secure against other cryptanalysis techniques than differential and linear cryptanalysis.

[0283] The fourth embodiment is not limited specifically to the above constructions; if speedup is desired, any one of the initial key-dependent transformation part 302, the final key-dependent transformation part 308 and the key-dependent linear transformation parts 341, 344 and 347 may be omitted or modified to key-independent transformation means. In this case, the encryption speed can be increased without significantly diminishing the security against differential cryptanalysis and linear cryptanalysis.

[0284] Fifth Embodiment

[0285] A description will be given of a modified form of the functional configuration of the nonlinear function part 304 in the same data transformation device as the fourth embodiment depicted in FIG. 13. The basic construction of this embodiment is the same as that of the fourth embodiment of FIG. 13 except that the nonlinear transformation parts 343₀to 343₇in the nonlinear function part 304 of FIG. 14 are modified like the nonlinear transformation parts 343₀′, 343₁′, 343₂′ and 343₃′ in the second embodiment depicted in FIGS. 8A through 8D so that they output expanded data. The second key-dependent linear transformation part 344 is similar construction to that shown in FIG. 9.

[0286] As depicted in FIG. 13, the right block data R_iis input to the nonlinear function part 304 together with the key data k_i0, k_i1, k_i2stored in the key storage part 322. In the first key-dependent linear transformation part 341 the data R_iis, for example, XORed with the key data ko and hence is linearly transformed to data R_i*=R_i⊕k_i0as in the case of FIG. 14. Then the data R_i* is split into eight pieces of data in₀, in₁, in₂, . . . , in₇in the splitting part 342. The eight pieces of data in₀, in₁, in₂, . . . , in₇are nonlinearly transformed to data MID₀₀, MID₀₁, MID₀₂, . . . , MID₀₇in the nonlinear transformation parts 343₀′, 343₁′, 343₂′, . . . , 343₇′, respectively. The nonlinear transformation part 343₀′ is so designed as to transform the m-bit data in₀to the following 8×m-bit data.

[0287] MID₀₀=[00 . . . 0₍₂₎, mid₀₀, mid₀₀, mid₀₀, mid₀₀, mid₀₀, 00 . . . 0₍₂₎, mid₀₀]  (18-1)

[0288] That is, the nonlinear transformation part 343₀′ has, for example, as shown in FIG. 20A, an S-box which outputs the data mid₀₀in high-order m bits as does the nonlinear transformation part 343₀in the fourth embodiment of FIG. 14 and outputs “00 . . . 0₍₂₎” as low-order m bits; furthermore, it branches the output data mid₀₀in six routes and “00 . . . 0₍₂₎” in two other routes.

[0289] The nonlinear transformation part 343₁′ has, as depicted in FIG. 20B, an S-box 343₁which outputs the data mid₀₁in high-order m bits and outputs “00 . . . 0₍₂₎” as low-order m bits; furthermore, it branches the output data mid₀₁in six routes and m-bit data “00 . . . 0” in two other routes. The other nonlinear transformation parts 343₂′ to 343₇′ are also similarly constructed; in FIG. 20C there is depicted the construction of the nonlinear transformation part 343₇′ but no description will be repeated. These nonlinear transformation parts 343₁′ to 343₇′ transform data in₁to in₇to the following data MID₀₁to MID₀₇, respectively.

[0290] MID₀₁=[mid₀₁, 00 . . . 0₍₂₎, mid₀₁, mid₀₁, mid₀₁, mid₀₁, mid₀₁, 00 . . . 0₍₂₎]  (18-2)

[0291] MID₀₂=[mid₀₂, mid₀₂, 00 . . . 0₍₂₎, mid₀₂, 00 . . . 0₍₂₎, mid₀₂, mid₀₂, mid₀₂]  (18-3)

[0292] MID₀₃=[mid₀₃, mid₀₃, mid₀₃, 00 . . . 0₍₂₎, mid₀₃, 00 . . . 0₍₂₎, mid₀₃, mid₀₃]  (18-4)

[0293] MID₀₄=[mid₀₄, 00 . . . 0₍₂₎, mid₀₄, mid₀₄, mid₀₄, 00 . . . 0₍₂₎, 00 . . . 0₍₂₎, mid₀₄]  (18-5)

[0294] MID₀₅=[mid₀₅, mid₀₅, 00 . . . 0₍₂₎, mid₀₅, mid₀₅, mid₀₅, 00 . . . 0₍₂₎, 00 . . . 0₍₂₎]  (18-6)

[0295] MID₀₆=[mid₀₆, mid₀₆, mid₀₆, 00 . . . 0₍₂₎, 00 . . . 0₍₂₎, mid₀₆, mid₀₆, 00 . . . 0₍₂₎]  (18-7)

[0296] MID₀₇=[00 . . . 0₍₂₎, mid₀₇, mid₀₇, mid₀₇, 00 . . . 0₍₂₎, 00 . . . 0₍₂₎, mid₀₇, mid₀₇]  (18-8)

[0297] These pieces of data MID₀₀to MID₀₇can be predetermined in the same manner as described previously in connection with Equations (8-1) to (8-4) in the second embodiment. That is, the data MID₀₀is a set of data which is obtained at the outputs of the eight routes of the linear transformation part 344A in FIG. 17 when pieces of data mid₀₀and mid₀₂to mid₀₇except mid₀₁are all set as “00 . . . 0₍₂₎.” The same goes for the data MID₀₂to MID₀₇. These nonlinear transformation parts 343₀′ to 343₇′ may be formed by memory from which the pieces of data MID₀₀to MID₀₇are directly read out using the data in₀to in₇as addresses.

[0298] Then the pieces of data MID₀₀to MID₀₇are input to the second key-dependent linear transformation part 344 using the key data k_i1as shown in FIG. 21. The second key-dependent linear transformation part 344 is made up of XOR circuits 41₁to 41₄each of which XORs two pieces of input data, XOR circuits 42₁and 42₂each of which XORs the outputs from two of them, an XOR circuit 43 which XORs their outputs, and an XOR circuit 44 which XORs its output and the key data k_i1. With this construction, the following operation is conducted.

[0299] MID₁=MID₀₀⊕MID₀₁MID₀₂⊕MID₀₃⊕MID₀₄⊕MID₀₅⊕MID₀₆⊕MID₀₇⊕k_i1  (19)

[0300] This output MID₁is split into eight blocks, which are output as data mid₁₀, mid₁₁, mid₁₂, . . . , mid₁₇. Eventually, the linear transformation by the second key-dependent linear transformation part 344, expressed in units of m-bit subblocks, becomes as follows:

[0301] mid₁₀=mid₀₁⊕mid₀₂⊕mid₀₃⊕mid₀₄⊕mid₀₅⊕mid₀₆⊕k_i10  (20-1)

[0302] mid₁₁=mid₀₀⊕mid₀₂⊕mid₀₃⊕mid₀₅⊕mid₀₆⊕mid₀₇⊕k_i11  (20-2)

[0303] mid₁₂=mid₀₀⊕mid₀₁⊕mid₀₃⊕mid₀₄⊕mid₀₆⊕mid₀₇⊕k_i12  (20-3)

[0304] mid₁₃=mid₀₀⊕mid₀₁⊕mid₀₂⊕mid₀₄⊕mid₀₅⊕mid₀₇⊕k_i13  (20-4)

[0305] mid₁₄=mid₀₀⊕mid₀₁⊕mid₀₃⊕mid₀₄⊕mid₀₅⊕k_i14  (20-5)

[0306] mid₁₅=mid₀₀⊕mid₀₁⊕mid₀₂⊕mid₀₅⊕mid₀₆⊕k_i15  (20-6)

[0307] mid₁₆=mid₀₁⊕mid₀₂⊕mid₀₃⊕mid₀₆⊕mid₀₇⊕k_i16  (20-7)

[0308] mid₁₇=mid₀₀⊕mid₀₂⊕mid₀₃⊕mid₀₄⊕mid₀₇⊕k_i17  (20-8)

[0309] The above equations express a linear transformation equivalent to that by Equations (15-1) to (15-8) described previously with reference to FIG. 17. As a result, the same pieces of data mid₁₀, mid₁₁, mid₁₂, . . . , mid₁₇are generated. Incidentally, the subkey data k_i1, is composed of eight pieces of data k_i10, k_i11, k_i12, . . . , k_i17.

[0310] Next, the eight pieces of data mid₁₀, mid₁₁, mid₁₂, . . . , mid₁₇are nonlinearly transformed to eight pieces of data out₀, out₁, out₂, . . . , out₇in the nonlinear transformation parts 345₀, 345₁, 345₂, . . . , 345₇in FIG. 14, and the eight pieces of data out₀, out₁, out₂, . . . , out₇are combined into a single piece of data Y_i* in the combining part 346. Finally, the data Y_i* is linearly transformed to data Y_iby, for example, a k_i2-bit left rotation in the third key-dependent linear transformation part 347 using the key data k_i2.

[0311] As depicted in FIG. 21, the second key-dependent linear transformation part 344 uses eight XOR circuits but implements the linear transformation equivalent to that in FIG. 17 (which uses 24 XOR circuits), and hence it permits faster transformation than the fourth embodiment.

[0312] Furthermore, as is the case with the fourth embodiment, the eight nonlinear transformation parts 343₀to 343₃and 345₀to 345₃are arranged in parallel and their nonlinear transformation processes are not associated with one another, and hence they can be executed in parallel. Besides, letting p represent the differential/liner probability of the nonlinear transformation parts 343₀′ to 343₇′, the differential/linear probability of the nonlinear function 304 becomes p⁵as a whole.

[0313] In the above, the second (key-dependent) linear transformation part 344 may perform the transformation by XORing of the input subdata without depending on the key k_i1. That is, the XOR circuits 63₀to 63₇in FIG. 17 and the circuits corresponding thereto in FIGS. 18, 19 and 21 may be omitted.

[0314] Moreover, in the above, the first key-dependent linear transformation part 341, the second key-dependent transformation part 344 and the third key-dependent transformation part 347 need not always be key-dependent, that is, the linear transformation may be performed in subdata without inputting the key data to them.

[0315] The data transformation processing in the fourth and fifth embodiments described above may also be implemented by executing a program of its procedure by a computer. The procedure is the same as shown in FIGS. 11 and 12; hence, no description will be repeated.

[0316] FIG. 22 illustrates an example of the system configuration wherein the program for the data transformation processing described in connection with the first to fifth embodiment is prerecorded on a recording medium and is read out therefrom to perform the data transformation according to the present invention. A central processing unit (CPU) 110, a read-only memory (ROM) 120, a random access memory (RAM) 130, a storage device (a hard disk HD, for instance) 140, an I/O interface 150 and a bus interconnecting them constitute an ordinary computer 100. The program for implementing the data transformation process according to the present invention is prestored on the recording medium such as the hard disk HD. In the ROM 120 there are stored respective S-boxes in tabular form. In the execution of the data transformation the program is read into the RAM 130 from the hard disk HD 140, and upon input of the plaintext M via the interface 150, then the program is executed under the control of the CPU 110, and the resulting output data C is output via the interface 150.

[0317] The program for the data transformation process may be one that is prestored in an arbitrary external storage device 180. In such an instance, the program can be used after once transferred via a driver 170 from the external storage device 180 to the hard disk 140 or the RAM 130.

[0318] Though not shown, when the output data C is sent over a communication line or the Internet, only a person who has a common secret key is qualified to decrypt the output data C. Since the data C transformed according to the present invention is highly resistant to differential cryptanalysis and linear cryptanalysis, it is possible to achieve transmission of information with increased security.

[0319] Incidentally, when in each embodiment the key scheduling part 20 has the same construction as depicted in FIG. 3, the subkeys used as k_iand k_i+1in the data diffusion part 10 become the outputs Q_2jand Q_2j+1(where i=2j) from the key processing part 21 in the key scheduling part 20. On the other hand, since it is the subkeys k_Nand k_N−1that are very likely to be analyzed by differential cryptanalysis or linear cryptanalysis, a combination of data diffusion parts with these pieces of information allows ease in finding other subkeys.

[0320] The embodiment described below is intended to solve this problem by using a more complex key scheduling algorithm in the key scheduling part 20 for generating subkeys in the data transformation device of FIG. 4 that is typical of the embodiments described above. With a view to preventing that success in analyzing the subkeys k_Nand k_N−1leads to the leakage of much information about the outputs from other data diffusion parts, the following embodiment employs a G-function part which performs the same function as that of the key diffusion part 22 depicted in FIG. 3 (the function fk in FIG. 3); furthermore, there is provided an H-function part which possesses a data extracting function by which information necessary for generating subkeys is extracted from a required number of L components as uniformly as possible which were selected from L components once stored in a storage part after being output from the G-function part according to a first aspect of key generation. According to a second aspect, partial information that is used as subkeys is extracted in the H-function part from the L-components output from the G-function part and is stored in a storage part, and necessary information is extracted from a required number of L-components to thereby generate the subkeys.

[0321] In the case of DES, since the subkeys are generated by only swapping bit positions of the master key, the key scheduling process is fast. However, there is a problem that if the some subkeys is known, the corresponding master key can be obtained immediately.

[0322] To provide increased complexity in the relationship between the master key and the subkeys without involving a substantial increase in the computational complexity for key scheduling and without increasing the size program of the key scheduling part, the G-function is constructed as the data diffusion fumction through the use of the F-function to be used in the data diffusion part or a subroutine forming the F-function (which functions will hereinafter be denoted by f), and a plurality of intermediate values L are generated by repeatedly using the G-function.

[0323] The G-function is adapted to operate on two input components (Y, v) and generate three output components (L, Y, v). The bits of the component Y is equal to or larger than the bits of the master key K.

[0324] To supply subkeys to the data diffusion part, the G-function is called a required number (M) of times to generate M components L (where 0≦j≦M−1). Letting the output from the G-function called a j-th time be represented by (L_j, Y_j, v_j), part of this value is used as the input (Y_j+1=Y_j, v_J+1=v_j) to the G-function called a (j+1)-th time. Assume here that Y₀is a value containing K and that v₀is a predetermined value (0, for instance).

[0325] For the given master key K, the subkey k_i(where i=0, 1, 2, . . . , N−1) is determined as follows:

[0326] (L_i, (Y₁, v₁))=G(Y₀, v₀)  (21)

[0327] (L_j+1, (Y_j+1, v_j+1))=G(Y_j, v_j) (j=1, 2, . . . , M−1)  (22)

[0328] k_i=H(i, L₁, L₂, . . . , L_M) (i=0, 1, 2, . . . , N−1)  (23)

[0329] where the H-function is means to extract from each component L_iinformation about the bit position determined by the suffix i as required according to the suffix i of the subkey and the M components L output from the G-function.

[0330] Sixth Embodiment

[0331] In FIG. 23A there is depicted the basic construction of the key scheduling part of this embodiment for application to the key scheduling part 20 shown in FIG. 4A. The master key K is input to an intermediate key generation part 220; the intermediate key generation part 220 has a plurality (M rounds) of G-function parts which operate in cascade, and generates intermediate keys L₁to L_M, which are stored in a storage part 230. The intermediate keys L₁to L_Mstored in the storage part 230 are provided to a subkey generation part 240, wherein subkeys k_iare generated based on an H-function part. The structure and operation of each part will be concretely described below.

[0332] This example is intended to increase the security of the key scheduling part shown in FIG. 3 using a data randomization part disclosed in the aforementioned U.S. patent issued to Miyaguchi et al. This embodiment will be described as being applied to the key scheduling part (FIG. 3) in the U.S. patent of Miyagushi et al. when N=16.

[0333] In FIG. 3 16 Q components are obtained by an 8 (=N/2) rounds of data diffision parts. Here, let Q_jrepresent the respective Q component. Each Q_jcomponent is 16-bit. The subkey generation part 240 constructs the subkey k₀from the value of a first bit of the respective Q_jcomponent, the subkey k₁from the value of a second bit of the respective Q_jcomponent, and in general, the subkey k_i−1from the value of an i-th bit of the Q_jcomponent. That is, letting Q_j[i] represent the i-th bit of the Q_jcomponent, the subkey k_iis expressed by the following equation.

[0334] K_i−1=(Q₁[i], Q₂[i], . . . , Q_j[i], . . . , Q₁₆[i])  (24)

[0335] where 1≦i,j≦16.

[0336] This processing method will be reviewed below in the framework of the G- and the H-function mentioned above. Here, Y_jrepresents the value of 64 bits, Y_j^Lthe value of high-order 32bits of Y_jand Y_j^Rthe value of low-order 32 bits of Y_j.

[0337] Letting the output from the G-function for the input (Y_j, v_j) be represented by

[0338] (L_j+1, (Y_j+1, v_j+1))=G(Y_j, v_j) (0≦j≦7),  (25)

[0339] the output (L_j+1, (Y_j+1, v_j+1)) is given by the following equations.

[0340] Y_j+1^L=Y_j^R  (26)

[0341] Y_j+1^R=L_j+1=f_k(Y_j^L, Y_j^R⊕v_j)  (27)

[0342] v_j+1=Y_j^L  (28)

[0343] The subkey k_iis given as a function of i and L₁to L₈by the following equation.

[0344] K_i−1=H(i, L₁, L₂, . . . , L₈)  (29)

[0345] Letting each L_ibe represented by (t_j⁽¹⁾, t_j⁽²⁾, . . . ,t_j⁽³²⁾) the H-function constructed the subkey k_ias follows:

[0346] K_i=(t₁⁽ⁱ⁾, t₁⁽¹⁶⁺ⁱ⁾, t₂⁽¹⁶⁺ⁱ⁾, . . . , t₈⁽ⁱ⁾, t₈⁽¹⁶⁺ⁱ⁾) (1≦i≦16)  (30)

[0347] Since this method provides 16 subkeys at the maximum, the encryption algorithm described in the U.S. patent by Miyaguchi et al. can be used for the structure with a maximum of eight rounds of F-functions.

[0348] The construction of the intermediate key generation part 220 shown in FIG. 23A will be described below with reference to FIG. 24. G-function parts 22-1 to 22-8 are provided in cascade. The master key K is input as Y₀to the first-round G-function part 22-1 together with a constant v₀, and Y_j−1and v_j−1are input to the G-function part 22-j of each j-th round; each G-function part randomizes Y_j−1and outputs L_j, Y_jand v_j. L_jis an intermediate key and Y_jand v_jare fed to the next G-function part 22-(j+1). That is, after setting Y₀=K and v₀=0, the G-function part 22 is called eight times. The construction of the G-function part is depicted in FIG. 25, for which the following process is repeated from j=0 to j=7.

[0349] Step 1: Upon input Y_jand v_jto the G-function part 22-(j+1), split Y_jinto two blocks (Y_j^L, Y_j^R) by a splitting part 221 in FIG. 25.

[0350] Step 2: Output Y_j^Las v_j+1. Input Y_j^Lto a data diffusion part (f_k) 222.

[0351] Step 3: Input Y_j^Rto a data swapping part 224. Input Y_j^Rand v_jto an XOR circuit 223 to compute Y_j^R⊕v_jand input the result of computation to the data diffusion part (f_k) 222.

[0352] Step 4: Upon receiving Y_j^Land Y_j^R⊕v_jas inputs thereto, the data diffuision part (f_k) 222 outputs the result of computation as L_j+1and, at the same time, input it to the swapping part 224.

[0353] Step 5: Upon receiving Y_j^Rand the result of computation L_j+1by the data diffusion part (f_k) 222, the swapping part 224 renders Y_j^Rto Y_j+1^Land L_j+1to Y_j+1^R, then concatenates them to Y_j+1=(Y_j+1^L, Y_j+1^R), and outputs it.

[0354] The eight L_icomponents output from the G-function part 22-1 to 22-8 are once stored in the storage part 230 (FIG. 23A).

[0355] Next, a description will be given, with reference to FIG. 26, of the construction of the H-function part serving as the subkey generation part 240. The H-function part 240 performs the following steps after reading out the eight L components L₁to L₈from the storage part 230.

[0356] Step 1: Read out each component L_ifrom the storage part 230 and input it to a bit splitter 241 to split it bitwise as follows:

[0357] (t_j⁽¹⁾, t_j⁽²⁾, . . . , t_j⁽³²⁾)=L_j(j=1, 2, . . . , 8)  (31)

[0358] Step 2: Input (t₁⁽ⁱ⁾, t₁⁽¹⁶⁺ⁱ⁾, t₂⁽ⁱ⁾, t₂⁽¹⁶⁺ⁱ⁾, . . . , t₈⁽ⁱ⁾, t₈⁽¹⁶⁺ⁱ⁾) to a bit combiner 242 to obtain the subkey as follows:

[0359] k_i=(t₁⁽ⁱ⁾, t₁⁽¹⁶⁺ⁱ⁾, t₂⁽ⁱ⁾, t₂⁽¹⁶⁺ⁱ⁾, . . . , t₈⁽ⁱ⁾, t₈⁽¹⁶⁺ⁱ⁾)(i=1, 2, . . . , 16)   (32)

[0360] Seventh Embodiment

[0361] A description will be given, with reference to FIGS. 23B, 24, 25 and 27, of another embodiment which outputs the same subkey as does the six embodiment.

[0362] As shown in FIG. 23B, a plurality of intermediate keys L_jare generated in the intermediate key generation part 220. The intermediate key generation part 220 is identical in construction with that depicted in FIG. 23A; that is, it comprises the plurality of G-function parts 22 as shown in FIG. 24. Upon each generation of the intermediate key L_jin the G-function part 22, the intermediate key L_jis fed to the subkey generation part 250, from which bit position information, which is determined by the suffix i of the subkey k_iand its bit position q, is output as information k_iqand is stored in the storage part 260.

[0363] That is, the intermediate key generation part 220 and the subkey generation part 250 repeat the following steps 1 through 7 for each value from j=0 to j=7.

[0364] Step 1: Upon input of Y_jand v_jto the G-function part 22-(j+1), split Y_jinto two blocks (Y_j^L, Y_j^R) by the splitting part 221.

[0365] Step 2: Output Y_j^Las v_j+1. And input Y_j^Lto the data diffusion part (f_k) 222.

[0366] Step 3: Input Y_j^Rto the swapping part 224. And input Y_j^Rand v_jto the XOR circuit 223 to calculate Y_j^R⊕v_jand input it to the data diffusion part (f_k) 222.

[0367] Step 4: Upon receiving Y_j^Land Y_j^R⊕v_j, the data diffusion part (f_k) 222 inputs the result of its computation as L_j+1to the subkey generation part 250 (FIG. 23B) and, at the same time, input it to the swapping part 224.

[0368] Step 5: Upon receiving Y_j^Rand the result of calculation L_j+1from the data diffulsion part (f_k) 222, the swapping part 224 renders Y_j^Rto Y_j+1^Land L_j+1to Y_j+1^R, then concatenates them to Y_j+1=(Y_j+1^L, Y_j+1^R) and outputs it.

[0369] Step 6: As depicted in FIG. 27, the subkey generation part 250 input L_jto a bit splitter 251 to split it bitwise as follows:

[0370] (t_j⁽¹⁾, t_j⁽²⁾, . . . , t_j⁽³²⁾)=L_j(j=1, 2, . . . , 8)  (33)

[0371] and then input them to an information distributor 252.

[0372] Step 7: The bit string (t_j⁽¹⁾, t_j⁽²⁾, . . . , t_j⁽³²⁾) input to the information distributor 252 is information on the bit position of L_jdetermined by the bit position q of the subkey k_ifor a suffix i being used as information on the bit position q of the subkey k_i, and is stored for each L_jin one of 16 storage areas of the storage part 260 divided for each subkey

[0373] k_i=(t₁⁽ⁱ⁾, t₁⁽¹⁶⁺ⁱ⁾, t₂⁽ⁱ⁾, t₂⁽¹⁶⁺ⁱ⁾, . . . , t₈⁽ⁱ⁾, t₈⁽¹⁶⁺ⁱ⁾)  (34)

[0374] Step 8: When 16-bit information is set for each k_i, that is, when the subkey k_igenerated, output its value (i=1, 2, . . . , 16).

[0375] Eighth Embodiment

[0376] With a view to reducing the device size or the number of program steps, this embodiment uses in key scheduling an f-function used for encryption.

[0377] This embodiment will also be described in the framework of the G- and H-function.

[0378] Let the output from the G-function for the input (Y_j, v_j) be represented by

[0379] (L_j+1, (Y_j+1, v_j+1))=G(Y_j, v_j) (0≦j≦7)

[0380] and let the output be set as follows: $\begin{array}{cc}\left(\left(Y_j^{\left(1\right)},Y_j^{\left(2\right)},Y_j^{\left(3\right)},Y_j^{\left(4\right)}\right),v_j\right)\to \left(\left(L_{j+1}^{\left(1\right)},L_{j+1}^{\left(2\right)},L_{j+1}^{\left(3\right)},L_{j+1}^{\left(4\right)}\right),\left[\left(Y_{j+1}^{\left(1\right)},Y_{j+1}^{\left(2\right)},Y_{j+1}^{\left(3\right)},Y_{j+1}^{\left(4\right)}\right),v_{j+1}\right]\right)& \left(35\right)\end{array}$

[0381] Here, the following definitions are given. $\begin{array}{cc}{Y}_{j+1}^{\left(i\right)}=f\left(Y_j^{\left(i\right)}\right)\left(i=1,2,3,4\right)& \left(36\right)\\ L_{j+1}^{\left(0\right)}=v_j& \left(37\right)\\ L_{j+1}^{\left(i\right)}=f\left(L_{j+1}^{\left(i-1\right)}\right)\oplus Y_{j+1}^{\left(i\right)}\left(i=1,2,3,4\right)& \left(38\right)\\ v_{j+1}=L_{j+1}^{\left(4\right)}& \left(39\right)\end{array}$

[0382] Further, in

[0383] k_i=H(i, L₁, L₂, . . . L₈)  (40)

[0384] the following definitions are given. $\begin{array}{cc}{q}_{i+4j}=L_{j+1}^{\left(i+1\right)}\left(i=0,1,2,3\right)& \left(41\right)\\ \left(t_i^{\left(0\right)},t_i^{\left(1\right)},\dots ,t_i^{\left(7\right)}\right)=q_i\left(i=0,1,\dots ,31\right)& \left(42\right)\\ k_{\left(i+1\right)}=\left(t_{0+\left(i\mathrm{mod}2\right)}^{\left(\left[i/2\right]\right)},t_{2+\left(i\mathrm{mod}2\right)}^{\left(\left[i/2\right]\right)},\dots ,t_{30+\left(i\mathrm{mod}2\right)}^{\left(\left[i/2\right]\right)}\right)\left(i=0,1,\dots ,15\right)& \left(43\right)\end{array}$

[0385] Suppose that [i/2] in Equation (43) represents └i/2┘.

[0386] This procedure will be described below with reference to FIGS. 28 and 26.

[0387] Preparation

[0388] Step 1: Set as v₀a value extracted from 0123456789abcdef101112. . . (hex) by the same number of bits as the bit length of the function f.

[0390] Step 2: Set the master key K at Y₀.

[0391] Generation of Intermediate Key: The following procedure is repeated for j=0,1, 2, . . . , 7.

[0392] Step 1: Divide equally the input Y_jinto four (Y_j⁽¹⁾, Y_j⁽²⁾, Y_j⁽³⁾, Y_j⁽⁴⁾).

[0393] Step 2: For i=1, 2, 3, 4, compute Y_j+1⁽ⁱ⁾=f(Y_j⁽ⁱ⁾) by data diffusion part 611 to 614.

[0394] Step 3: set L_j+1=v_j.

[0395] Step 4: For I=1, 2, 3, 4, compute f(L_j+1⁽ⁱ⁻¹⁾) by data diffusion part 621 to 624, and input the result of computation to an XOR circuit 63ito XOR it with Y_j+1⁽ⁱ⁾to obtain L_j+1⁽ⁱ⁾=f(L_j+1⁽ⁱ⁻¹⁾)⊕Y_j+1⁽ⁱ⁾.

[0396] Step 5: set Y_j+1=(Y_j+1⁽¹⁾, Y_j+1⁽²⁾, Y_j+1⁽³⁾, Y_j+1⁽⁴⁾).

[0397] Step 6: set L_j+1=L_j+1⁽¹⁾, L_j+1⁽²⁾, L_j+1⁽³⁾, L_j+1⁽⁴⁾).

[0398] Step 7: Set v_j+1=L_j+1⁽⁴⁾.

[0399] Generation of Subkey: As is the case with the sixth embodiment, Equation (43) is implemented to obtain k₁, k₂, . . . , k_N(where N≦16).

[0400] This embodiment is not limited specifically to the above but can also be carried out in the following manner:

[0401] (1) When the size of Y₀is larger than K, K is used as part of Y₀and the remaining part is filled with a constant.

[0402] (2) An arbitrary constant is used as v₀.

[0403] (3) The bit length of respective characters are arbitrarily set in the ranges in which they are harmonized with one another.

[0404] (4) Functions other than that for encryption are used as f.

[0405] (5) Part of L_iis not used to compute H, that is, this occurs when the number of subkeys k_iis small and the bits of L_jis large.

[0406] (6) H is computed in the same manner as in the sixth embodiment.

[0407] (7) G is computed in the same manner as in the sixth embodiment.

[0408] (8) As is the case with the seventh embodiment, upon each generation of one intermediate key, not on the generation of all the intermediate keys, the result of computation is stored in the storage part 260 in the corresponding bit position of k_i.

[0409] The intermediate key generation part 220, the subkey generation parts 240 and 250 may be adapted to be operated under program control by the computer depicted in FIG. 22.

[0410] As described above in detail, according to the present invention, the data transformation device for use in an encryption device to conceal data is designed to simultaneously meet the requirements of security and speedup, thereby ensuring security and permitting fast encryption procedure without causing a significant increase in the number of rounds. Hence, the device of the present invention suitable for use in an encryption device of the common-key cryptosystem which encrypts or decrypts data in blocks using a secret key.

[0411] Furthermore, according to the key scheduling of the present invention, even if k₆, k₇, k₈, k₉, k₁₀and k₁₁are known in the sixth and seventh embodiment, only 12bits (for example, 6th, 7th, 8th, 9th, 10th, 11th, 22nd, 23rd, 24th 25th, 26th and 27th bits) of the respective L_icomponents are known. Thus, the problems concerning the security of the key scheduling part raised in DES and the U.S. patent issued to Miyaguchi et al. have been solved.