Source: http://www.patent-de.com/20060706/EP1052611.html
Timestamp: 2020-05-27 02:00:34
Document Index: 801267687

Matched Legal Cases: ['art 10', 'art 11', 'art 14', 'art 140', 'art 12', 'arts 141', 'art 14', 'art 14', 'art 15', 'art 15', 'art 11', 'art 12', 'art 1415', 'art 11', 'art 15', 'art 20', 'art 16', 'art 10', 'art 12', 'art 17', 'art 19', 'art 12', 'art 1415', 'art 14', 'art 20', 'art 20', 'art 21', 'arts 210', 'arts 220', 'arts 21', 'art 21', 'arts 21', 'art 23', 'art 21', 'art 22', 'art 21', 'art 23', 'art 22', 'art 21', 'art 22', 'art 210', 'art 220', 'art 211', 'arts 220', 'arts 210', 'arts 140', 'art 10', 'art 21', 'art 22', 'art 22', 'art 23', 'art 23', 'art 22', 'art 23', 'art 22', 'art 20', 'art 10', 'art 21', 'art 347', 'art 343', 'art 344', 'art 345', 'art 346', 'art 347', 'art 343', 'art 340', 'art 3431', 'art 3437', 'art 230', 'art 10', 'art 20', 'art 10', 'arts 380', 'art 38', 'art 304', 'art 12', 'art 305', 'art 306', 'art 304', 'art 322', 'art 304', 'art 305', 'art 306', 'art 381', 'arts 38', 'art 304', 'art 304', 'art 305', 'art 306', 'art 305', 'arts 380', 'art 307', 'art 308', 'art 322', 'art 309', 'art 308', 'art 302', 'art 38', 'art 304', 'art 322', 'art 341', 'art 342', 'arts 3430', 'art 344', 'art 344', 'arts 3450', 'art 346', 'art 347', 'art 344', 'art 304', 'art 304', 'art 343', 'art 344', 'art 345', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'arts 3450', 'art 346', 'art 347', 'art 304', 'arts 3430', 'arts 3430', 'arts 3450', 'art 304', 'arts 3430', 'art 304', 'art 322', 'art 321', 'art 320', 'art 20', 'art 321', 'art 21', 'art 21', 'art 302', 'art 308', 'arts 341', 'art 304', 'arts 3430', 'arts 3430', 'art 344', 'art 304', 'art 341', 'art 342', 'arts 3430', 'art 3430', 'art 3430', 'art 3430', 'art 3430', 'arts 3431', 'art 344', 'arts 3430', 'art 344', 'art 344', 'arts 3450', 'art 346', 'art 347', 'art 304', 'arts 3430', 'art 344', 'arts 3430', 'arts 3430', 'art 304', 'art 322', 'art 341', 'art 342', 'art 3430', 'art 51', 'art 53', 'art 3430', 'arts 3431', 'art 3450', 'art 51', 'art 53', 'arts 3451', 'arts 51', 'arts 3430', 'arts 3430', 'arts 51', 'arts 3430', 'art 304', 'arts 51', 'arts 51', 'art 304', 'art 341', 'art 344', 'art 347', 'arts 380', 'art 344', 'art 344', 'art 304', 'art 344', 'art 304', 'art 302', 'art 322', 'art 303', 'art 302', 'art 304', 'art 322', 'art 304', 'art 305', 'art 306', 'art 381', 'arts 38', 'art 304', 'art 304', 'art 305', 'art 306', 'art 305', 'art 308', 'art 302', 'art 304', 'art 322', 'art 341', 'art 342', 'arts 3430', 'art 344', 'art 344', 'arts 3450', 'art 346', 'art 347', 'art 344', 'art 344', 'art 345', 'art 343', 'art 343', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'arts 3450', 'art 346', 'art 304', 'arts 3430', 'arts 3430', 'arts 3450', 'arts 3430', 'art 304', 'art 344', 'art 344', 'art 304', 'art 320', 'art 321', 'art 322', 'art 321', 'art 21', 'art 304', 'arts 3430', 'art 304', 'arts 3430', 'art 344', 'art 304', 'art 322', 'art 341', 'art 342', 'arts 3430', 'art 3430', 'art 3430', 'art 3430', 'art 3431', 'arts 3432', 'art 3437', 'arts 3431', 'art 344', 'arts 3430', 'art 344', 'art 344', 'art 344', 'arts 3450', 'art 346', 'art 347', 'arts 3430', 'arts 3430', 'art 344', 'art 20', 'art 10', 'art 21', 'art 20', 'art 20', 'art 22', 'art 240', 'art 220', 'arts 22', 'art 22', 'art 22', 'art 22', 'art 22', 'art 22', 'art 221', 'art 224', 'art 224', 'art 224', 'art 230', 'art 220', 'art 250', 'art 22', 'art 221', 'art 224', 'art 250', 'art 224', 'art 224', 'art 250', 'art 260', 'art 611', 'art 621']

DATENWANDLER UND AUFZEICHNUNGSMEDIUM ZUR AUFNAHME EINES PROGRAMMS ZUR DATENUMWANDLUNG - Dokument EP1052611
Dokumentenidentifikation EP1052611 06.07.2006
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 L0 and R0. The block data R0 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 14i (i = 0, 1, ..., 15) in Fig. 2, wherein it is transformed to f(R0, k0) using a 48-bit subkey k0. The thus transformed data f(R0, k0) and the block data L0 are exclusive ORed in an XOR circuit 13, and its output and the block data R0 are swapped to obtain the next block data L1, R1. That is, R1 = L0 ⊕ f(R0, k0) L1 = R0 where ⊕ represents an exclusive OR. A 0-th round processing part 140 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 L1 and R1; similar round processing parts 141 to 1415 are provided in cascade. The processing by the i-th round processing part 14i will hereinafter be referred to as i-th processing, where i = 0, 1, ..., 15. That is, each round processing part 14i (where 0 ≤ i ≤ 15) performs the following processing Ri+1 = Li ⊕ f(Ri, ki) Li+1 = Ri And finally concatenation two pieces of data R16 and L16 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.
The decryption process can be executed following the same procedure as that for the encryption process except inputting subkeys k0, k1, ..., k14, k15 to the function f (the function operation part 12) in the order k15, k14, ..., k1, k0 which is reverse to that in the encryption process. In such an instance, the outputs L16 and R16 from the final round processing part 1415 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 16: 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 k0, k1, ..., k14, k15 which are provided to the corresponding round processing parts of the data diffusion part 10.
The processing in the function operation part 12 is performed as depicted in Fig. 2. To begin with, the 32-bit block data Ri is transformed to 48-bit data E(Ri) in an expanded permutation part 17. This output data and the subkey ki are exclusive ORed in an XOR circuit 18, whose output is transformed to 48-bit data E(Ri)⊕ki, 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 S0 to S7 to derive therefrom a 4-bit output, respectively. Incidentally, the S-box Sj (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 S0 to S7 are concatenated again to 32-bit data, which is applied to a permutation part 19 to provide the output f(Rj, ki) from the function operation part 12 as shown in Fig. 2. This output is exclusive ORed with Li to obtain Ri+1.
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 liner cryptanalysis proposed by Matsui, ( "Liner Cryptanalysis Method for DES cipher," Advances in Cryptology-EUROCRYPT' 93 (Lecture Notes in Computer Science 765), pp. 386-397.)
Assuming that a difference between two pieces of data X and X* is defined as ΔX = X ⊕ X*, differential cryptanalysis aims to obtain the subkey k15 in the final round processing part 1415 by applying to the following equations two sets of plaintext-ciphertext pair that an attacker possesses. In the encryption process of Fig. 1, let (Li, Ri) and (L*i, R*i) represent input data into the round processing part 14i for first and second plaintexts respectively. With the difference defined as mentioned above, the following equations hold. ΔLi= Li ⊕ L*i ΔRi = Ri ⊕ R*i In Fig. 1, since L15 = R14 , L*15 = R*14 , L16 = R15 and L*16 = R*15 , the following equations hold R16 = L15 ⊕ f(R15, k15) R*16 = L*15 ⊕ f(R*15, k15) and the exclusive OR of both sides of these two equations is obtained as follows: ΔR16 = ΔL15 ⊕ f(L16, k15) ⊕ f(L16⊕ΔL16, k15). The exclusive ORing of its both sides with ΔR14 = ΔL15 gives the following equation: f(L16, k15) ⊕ f(L16ΔL16, k15) = ΔR16 ⊕ ΔR14. At this time, since L16, ΔL16 and ΔR16 are data available from the ciphertext, they are known information. Hence, if the attacker can correctly obtain ΔR14, then only k15 in the above equation is an unknown constant; the attacker can find a correct k15 without fail by an exhaustive search for k15 using the known sets of plaintext-ciphertext pair. Accordingly, once the subkey k15 is found out, the remaining eight (i.e., 56-48) bits can easily be obtained even by another exhaustive search.
On the other hand, generally speaking, it is difficult to obtain ΔR14 since this value is an intermediate difference value. Then, assume that each round processing is approximated by the following equations with a probability pi in the 0-th to the last round but one (i.e.; the 14th): ΔRi+1 = ΔLi ⊕ Δ{f(ΔRi)} ΔLi+1 = ΔRi+1. The point is that, when certain ΔRi is input to the i-th round processing part, Δ{f(ΔRi)} can be predicted with the probability pi regardless of the value of the subkey ki. 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 S0, an input difference "110100(2)" is transformed to an output difference "0010(2)" 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 Psi and by combining them. Furthermore, the concatenation of such approximations in the respective rounds makes it possible to obtain ΔR14 from ΔL0 and ΔR0 (ΔL0 and ΔR0 are data derivable from the plaintext, and hence they are known) with a probability P = Πi=0 13p i. Incidentally, the higher the probability P, the easier the cryptanalysis. After the subkey k15 is thus obtained, a similar calculation is made of the subkey k14 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 k0.
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. (L0, R0) Γ (L0, R0) ⊕ (L16, R16) Γ (L16, R16) = (k0, k1, ..., k15) Γ (k0, k1, ..., k15) where Γ(X) represents the vector that chooses a particular bit position of X, and it is called a mask value.
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 (k0, k1, ..., k15) Γ (k0, k1, ..., k15) (one bit) from information (L0, R0) Γ (L0, R0) ⊕ (L16, R16) Γ (L16, R16). At this time, (L0, R0) and (L16, R16) are the plaintext and the ciphertext, respectively, and hence they are known. For this reason, if the attacker can correctly obtain Γ (L0, R0), Γ (L16, R16) and Γ (k0, k1, ..., k15), then he can obtain (k0, k1, ..., k15) Γ (k0, k1, ..., k15) (one bit).
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 psi. 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 psi. 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 S4, when the input mask value is "010000(2)," an output mask value "1111(2)" 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 pi, and by concatenating the linear representations of the respective rounds, Γ (L0, R0), Γ (L16, R16) and Γ (k0, k1, ..., k15) are obtained wit the following probability: P = 1/2 + 215Πi=0 15|pi-1/2|. The higher the probability P, the easier the cryptanalysis.
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 1/3. 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.
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. Patent 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 (fk), therefore it is expected that the main key cannot easily be derived from the subkeys.
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 210 to 21N/2-1 which have key diffusion parts 220 to 22N/2-1, respectively. The key processing parts 21j (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 21j+1. The key processing parts 21j, except the first round, each have an exclusive OR part 23j, which calculates the exclusive OR of the left input key data to the key processing part 21j-1 of the preceding round and the left output key data therefrom and provides the calculated data to the key diffusion part 22j. The left input key data of the key processing part 21j is diffused by the output from the exclusive OR part 23j in the key diffusion part 22j, 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 21j is output as left key data for input to the next round. The output from each key diffusion part 22j is bit-split into two subkeys Q2j and Q2j+1 (that is, ki and ki+1), which are provided to the corresponding ( i = 2j )-th round processing part and ( i+1 = 2j+1 )-th round processing part in Fig. 1.
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 210 the left key data is diffused by the right key data in the key diffusion part 220 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 211. The outputs from the key diffusion parts 220 to 22N/2-1 of the key processing parts 210 to 21N/2-1are applied as subkeys k0 to kN-1 to the corresponding round processing parts 140 to 14N-1 of the data diffusion part 10 depicted in Fig. 1.
In the expanded key generation part 21 of Fig. 3, however, each key diffusion part 22j is a function for generating a pair of key data (subkeys Q2j, Q2j+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 (Q2j-2 and Q2j-1), (Q2j and Q2j+1), (Q2j+1 and Q2j+3) are known, since the output (subkeys Q2j+2 and Q2j+3) from the (j+1)-th key diffusion part 22j+1 and the one input data (subkeys Q2j-2 and Q2j-1) thereto are known, the other input data (i.e., the output data from the exclusive OR part 23j+1) can be obtained; and it is possible to derive, from the thus obtained data and the subkeys Q2j and Q2j+1 which constitute the one input data to the exclusive OR part 23j+1, the input data to the preceding (j-th) key diffusion part 22j which constitute the other input data to the exclusive OR part 23j+1, that is, the subkeys Q2j-4 and Q2j-3 which constitute the output from the three-round-preceding ((j-2)-th) key diffusion part 22j-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.
Letting the final stage of the round processing in Fig. 1 be represented by i = N , subkeys kN and kN-1 are 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.
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.
According to the present invention, it is guaranteed that when the differential probability/liner probability in the first and second nonlinear transformation parts is p (< 1), the differential probability/liner probability of approximating each round is pi ≤ p2 (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 liner 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 ≤ pi2r ≤ p4r. 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 pi ≤ p4 and the probability of the cipher is P ≤ pi2r ≤ p8r. 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 pi ≤ p5 and the probability of the cipher is P ≤ pi2r ≤ p10r.
Moreover, the first and second nonlinear transformation parts are arranged so that their processing can be performed completely in parallel --this contributes to speedup.
Fig. 7 is a diagram depicting a concrete example of the second key-dependent linear transformation part 347 in Fig. 5.
Fig. 8A is a diagram depicting an equivalent functional configuration of a nonlinear transformation part 343 in the second embodiment.
Fig. 8B is a diagram depicting an equivalent functional configuration of a nonlinear transformation part 344 in the second embodiment.
Fig. 8C is a diagram depicting an equivalent functional configuration of a nonlinear transformation part 345 in the second embodiment.
Fig. 8D is a diagram depicting an equivalent functional configuration of a nonlinear transformation part 346 in the second embodiment.
Fig. 9 is a diagram showing the functional configuration of a second key-dependent linear transformation part 347 in the second embodiment.
Fig. 10 is a diagram showing the functional configuration of a nonlinear function part 343 in the third embodiment.
Fig. 15A is a diagram depicting a linear transformation part of a limited structure intended to reduce the computational complexity involved in search.
Fig. 15B is a diagram depicting configuration of one transformation box in Fig. 15A.
Fig. 20A is a diagram illustrating the functional configuration of a nonlinear transformation part 340' in the fifth embodiment.
Fig. 20B is a diagram illustrating the functional configuration of a nonlinear transformation part 3431'.
Fig. 20C is a diagram illustrating the functional configuration of a nonlinear transformation part 3437'.
Fig. 24 is a block diagram depicting an example of the functional configuration of an intermediate key generation part 230 in Fig. 23A or 23B.
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 380 to 38N-1 which sequentially perform round processing of left and right pieces of data after input data is split into left and right pieces L0, R0; each round processing part 38i (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.
{fk; k00, k01; k10, k11, k12; ...; k(N-1)0, k(N-1)1, k(N-1)2; ek}
The right block data R0 is provided to the nonlinear function part 304 which is characteristic of the present invention, together with the key data k00, k01 and k02 stored in the key storage part 322, and in the nonlinear function part 304 the right block data is nonlinearly transformed to data Y0. The data Y0 and the left block data L0 are transformed to data L0* through a linear operation in the liner operation part 305. The data L0* and the data R0 are swapped in the swapping part 306 to provide L1←R0, R1←L0*; and these pieces of data L1 and R1 are input to the next first round processing part 381.
Thereafter, in an i-th round processing parts 38i (where i = 0, 1, ..., N-1) the same processing as mentioned above is repeated for two pieces of input block data Li and Ri. That is, the right block data Ri is input to the nonlinear function part 304 together with the key data ki0, ki1 and ki2, and in the nonlinear function part 304 it is nonlinearly transformed to data Yi. The data Yi and the data Li are transformed to data Li* by a linear operation in the linear operation part 305. The data Li* and the data Ri are swapped in data position in the swapping part 306, that is, Li+1←Ri, Ri+1←Li*. The linear operation part 305 is to perform, for instance, an exclusive OR operation.
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 LN and RN are obtained as the result of such repeated processing by the round processing parts 380 to 38N-1. These pieces of data LN and RN are combined into a single piece of block data in a final combining part 307; for example, the two pieces of 32-bit data LN and RN are 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.
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, ..., k10, k11, k12, k00, k01, k02, fk.
The input block data Ri to the i-th round processing part 38i constitutes input data to the nonlinear function part 304, together with the key data ki0, ki1, ki2 stored in the key storage part 322. The block data Ri is subjected to, for example, exclusive ORing with the key data ki0 in a first key-dependent linear transformation part 341, by which it is linearly transformed to data Ri* = Ri⊕ki0 . Next, the thus transformed data Ri* is split into four pieces of, for instance, 8-bit data in0, in1, in2 and in3 in a splitting part 342. The four pieces of data in0, in1, in2 and in3 are nonlinearly transformed to four pieces of data mid00, mid01, mid02 and mid03 in nonlinear transformation parts 3430, 3431, 3432 and 3433, respectively, from which they are input to a second key-dependent liner transformation part 344.
The second key-dependent linear transformation part 344 performs linear transformation (XORing) among the pieces of input data mid00, mid01, mid02 and mid03 from four mutes 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 ki1 to provide output data mid10, mid11, mid12 and mid13 of the four routes. The four pieces of data are input to nonlinear transformation parts 3450, 3451, 3452 and 3453, wherein they are transformed to data out0, out1, out2 and out3, respectively. These four pieces of data are combined into data Yi* in a combining part 346; furthermore, in a third key-dependent liner transformation part 347 the data Yi* undergoes a linear operation with the key data ki2 to generate output data Yi.
The above-mentioned second key-dependent linear transformation part 344 is configured to perform an exclusive OR operation of data between data processing routes 300, 301, 302 and 303 provided corresponding to the pieces of data mid00, mid01, mid02 and mid03, 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 liner characteristic probabilities p, q. In this instance, a linear transformation part using the subkey ki1, which is contained in the second key-dependent liner 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.
Incidentally, what is intended to mean by the word "optimal" is to provide the highest resistance to differential and linear cryptanalysis in the liner 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 liner cryptanalysis and constructs the optimal linear transformation part 344A accordingly.
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:
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.
As a concrete example in the case of n = 4, a 4 × 4 matrix PE will be described which is expressed by the following equation:
The round function using the matrix PE has the following features. Let it be assumed, however, that the S-box is bijective. z'0, z'1, z'2 and z'3 defined by the above matrix represent the following operations, respectively. z'0 = 0&peseta;z0⊕1&peseta;z1⊕1&peseta;z2⊕1&peseta;z3 = z1⊕z2⊕z3 z'1 = 1&peseta;z0⊕0&peseta;z1⊕1&peseta;z2⊕1&peseta;z3 = z0⊕z2⊕z3 z'2 = 1&peseta;z0⊕1&peseta;z1⊕1&peseta;z2⊕0&peseta;z3 = z0⊕z1⊕z2 z'3 = 1&peseta;z0⊕1&peseta;z1⊕1&peseta;z2⊕1&peseta;z3 = z0⊕z1⊕z2⊕z3
The resistance of the round function to differential and liner cryptanalysis can be determined by the smallest numbers nd, n1 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.
In general, when given a certain matrix P, there exist a plurality of constructions of the liner transformation part 344A corresponding thereto. This is because the matrix P represents only the relationship between input and output data of the liner 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, liner 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 liner 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.
The elements of the n × n matrix P are determined by the following search algorithm taking the differential characteristic into account.
Step 1: Set a security threshold T (where T is an integer such that 2 ≤ T ≤ n).
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."
Step 3-1: Compute nd forte subset Pc of n column vectors. This is represented as nd(Pc).
Step 3-2: If nd(Pc) ≥ T, ten accept a matrix Pc consisting of the n column vectors as a candidate matrix.
If the candidate matrix by the above search algorithm is adopted, then it is guaranteed that the value nd is equal to or larger than T. The matrix P that maximizes nd can 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.
In the above search algorithm, if it is possible to obtain relatively satisfactory invulnerability against differential and linear cryptanalysis, then a matrix with nd(Pc) ≥ 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 tan T-1 selected in step 2 after step 1 may be used as the matrix P.
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 two conjectures were made.
Conjecture 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, Δz' = PΔz Γz = TPΓz'.
Conjecture 2: The minimum number nd of active s-boxes in the difference value path using the matrix P is equal to the minimum number n1 of active s-boxes in the mask value path using the transposed matrix TP.
Because of Conjecture 2, n1 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 PE, the matrix PE for the difference value path and the matrix TPE for the mask value path bear the following relationship.
It can be proven that nd = 3 and n1 = 3 for the two matrices (see Appendix).
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 mid00, mid01, mid02 and mid03 are input to the processing routes 300 to 303, respectively. In the processing route 300, mid00 and mid01 are XORed by an XOR circuit 310; in the processing route 302, mid02 and the output from the XOR circuit 310 are XORed by an XOR circuit 312; and the output from the XOR circuit 312 is XORed with mid01 by an XOR circuit 311.
In the processing route 303, the output from the XOR circuit 310 and the data mid03 are XORed by an XOR circuit 313; in the processing route 301, the outputs from the XOR circuits 311 and 313 are XORed by an XOR circuit 321; and in the processing route 300, the outputs from the XOR circuit 321 and 310 are XORed by an XOR circuit 320.
The outputs from the XOR circuits 320, 321, 312 and 313 and subkey data ki10, ki11, ki12 and ki13 are XORed by XOR circuits 350 to 353 of the key-dependent transformation part 344B, respectively, from which are provided mid10, mid11, mid12 and mid13. In other words, the pieces of data mid00, mid01, mid02 and mid03 are associated with one another and then undergo liner transformation dependent on the 8-bit subkey data ki10, ki11, ki12 and ki13, respectively. In short, logical operations given by the following logical expression are performed. mid10 = mid00⊕mid02⊕mid03⊕ki10 mid11 = mid01⊕mid02⊕mid03⊕ki11 mid12 = mid00⊕mid01⊕mid02⊕ki12 mid13 = mid00⊕mid01⊕mid03⊕ki13
Incidentally, the subkey ki1 is composed of four pieces of data ki10, ki11, ki12and ki13.
As depicted in Fig. 5, these pieces of data mid10, mid11, mid12 and mid13 are then nonlinearly transformed in the nonlinear transformation parts 3450, 3451, 3452 and 3453 into the data out0, out1, out2 and out3, respectively, which are combined into the single piece of data Yi* in the combining part 346. Finally, the data Yi* is linearly transformed into the data Yi by, for example, a ki2-bit left rotation in the third key-dependent linear transformation part 347 using the key data ki2, thereby generating the output data Yi from the nonlinear function part 304. The nonlinear transformation parts 3430 to 3433 and 3450 to 3453 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.
Since the four nonlinear transformation parts 3430 to 3433 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 3450 to 3453. 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 3430 to 3433 and 3450 to 3453, the nonlinear function part 304 provides a differential/linear probability p4 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 ≤ p8r; for example, when r =4 (12 rounds), P ≤ p32. In the case of DES cipher, this corresponds to 48 or more rounds, ensuring sufficiently secure against differential cryptanalysis and linear cryptanalysis.
Incidentally, the pieces of key data fk, k00, k01, k02, k10, k12, ..., 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.
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 liner 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 liner cryptanalysis.
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 3430, 3431, 3432 and 3433 in Fig. 5 are replaced with nonlinear transformation parts 3430' to 3433' which nonlinearly transform, for example, 8-bit inputs in0 to in3 into 32-bit expanded data MID00, MID01, MID02 and MID03 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.
As is the case with the Fig. 5, the data Ri is input to the nonlinear function part 304 together with the key data ki0, ki1 and ki2. The data Ri is linearly transformed into data Ri* = Ri⊕ki0 , for example, by being XORed with the key data ki0 in the first key-dependent linear transformation part 341. Next, the data Ri* is split into four pieces of data in0, in1, in2 and in3 in the splitting part 342. The four pieces of data in0, in1, in2 and in3 are nonlinearly transformed into data MID00, MID01, MID02 and MID03 in the nonlinear transformation parts 3430', 3431', 3432' and 3433' depicted in Figs. 8A to 8D, respectively. In the first embodiment the nonlinear transformation part 3430 outputs the in-bit data mid00 for the m-bit input in0, whereas in this embodiment the nonlinear transformation part 3430' has an S-box that outputs the same m-bit data mid00 as high-order m bits as does the nonlinear transformation part 3430 in the first embodiment of Fig. 5 and outputs fixed data "00 ... 0(2)" as low-order m bits; further, the nonlinear transformation part is designed to output the high-order m-bit data mid00 to three routes by duplicating and output the m-bit data "00 ... 0(2)." That is, the nonlinear transformation part 3430' is means for transforming the m-bit data in0 to 4m-bit data MID00 = [mid00, 00 ... 0(2), mid00, mid00] Similarly, the nonlinear transformation parts 3431', 3432' and 3433' are means for transforming the input data in1, in2 and in3 to MID01 = [00 ... 0(2), mid01, mid01, mid01] MID02 = [mid02, mid02, mid02, 00 ... 0(2)] MID03 = [mid03, mid03, 00 ... 0(2), mid03] The data MID00 expressed by Equation (8-1) can be determined by presetting as MID00 the entire data which is provided in the four output routes of the linear transformation part 344A when the pieces of data mid01, mid02 and mid03 except mid00 are each set as "00 ... 0(2)." Similarly, the data MID01, MID02 and MID03 expressed by Equations (8-2), (8-3) and (8-4) can also be easily determined. These nonlinear transformation parts 3430' to 3433' may be constructed in memory as transformation tables from which to read out the data MID00, MID01, MID02 and MID03 by using the data in0, in1, in2 and in3 as addresses.
Then, these pieces of data MID00 to MID03 are input to the second key-dependent linear transformation part 344 with the key data ki1 as depicted in Fig. 9. MID00 and MID01 are XORed by an XOR circuit 41; MID02 and MID03 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 ki1 are XORed by an XOR circuit 44. The output MID1 from the XOR circuit 44 is split into m-bit outputs mid10, mid11, mid12 and mid13. After all, the second key-dependent linear transformation part 344 linearly transforms the input data by the following operation: MID1 = MID00⊕MID01⊕MID02⊕MID03⊕ki1.
The components of the output MID1 = [mid10, mid11, mid12, mid13] by this linear transformation operation are expressed by the following equations, respectively: mid10 = mid00⊕mid02⊕mid03⊕ki10 mid11 = mid01⊕mid02⊕mid03⊕ki11 mid12 = mid00⊕mid01⊕mid02⊕ki12 mid13 =mid00⊕mid01⊕mid03⊕ki13 These linear transformation operations we equivalent to those in Fig. 7 given by Equations (7-1) to (7-4). In this way, the same pieces of data mid10, mid11, mid12 and mid13 as those in the first embodiment are generated. Incidentally, ki1 is composed of four pieces of data ki10, ki11, ki12 and ki13.
Then, the four pieces of data mid10, mid11, mid12 and mid13 are nonlinearly transformed into data out0, out1, out2 and out3 in the nonlinear transformation parts 3450, 3451, 3452 and 3453, respectively, as in the Fig. 5, and in the combining part 346 the four pieces of data out0, out1, out2 and out3 are combined into the single piece of data Yi*. Finally, the data Yi* is linearly transformed into the data Yi by, for example, a ki2-bit left rotation in the third key-dependent linear transformation part 347 using the key data ki2, thereby generating the output data Yi from the nonlinear function part 304.
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 3430 to 3433 of Figs. 8A to 8D by only S-boxes which output 8-bit data mid00 to mid03, 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 MID00 to MID03.
Furthermore, as is the case with the first embodiment, the four nonlinear transformation parts 3430 to 3433 and 3450 to 3453 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 3430 to 3433 and 3450 to 3453, the differential/linear probability of the nonlinear function 304 becomes p4 as a whole.
As depicted in fig. 5, for example, a 32-bit data Ri is input to the nonlinear function part 304 together with the key data ki0, ki1 and ki2 stored in the key storage part 322. The data R1 is linearly transformed into data Ri* = Ri⊕ki0 by, for example, XORing with the key data ki0 in the first key-dependent linear transformation part 341. Then the data Ri* is split into four pieces of, for example, 8-bit data in0, in1, in2 and in3 in the splitting part 342.
In the nonlinear transformation part 3430, as shown in Fig. 10, for instance, the data in0 is further split into two, for example, 4-bit subblocks in00 and in01; the subblock in00 is transformed to data mid000 in a sub-nonlinear transformation part 51 and, at the same time, it is XORed with the data in01 by an XOR circuit 52, whose output in00⊕in01 is transformed into data mid001 in a sub-nonlinear transformation part 53. Thereafter, these outputs mid000 and mid001 are XORed by an XOR circuit 54, and its output and the data mid001 are combined into the data mid00. That is, the nonlinear transformation part 3430 splits the input in0 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 in1, in2 and in3 are also transformed into the data mid01, mid02 and mid03 in the nonlinear transformation parts 3431, 3432 and 3433 each having the functional configuration shown in Fig. 10 which comprises two nonlinear transformation parts and two XOR circuits.
Then, the data mid10 is input to the nonlinear transformation part 3450 of the same functional consfiguration as shown in Fig. 10, wherein it is further split into two subblocks mid100 and mid101. The subblock mid100 is transformed into data out00 in the sub-nonlinear transformation part 51. The subblocks mid100 and mid101 are XORed by the XOR circuit 52, and its output mid100⊕mid101 is transformed into data out01 in the nonlinear transformation part 53. Then, the two pieces of data out00 and out01 are XORed by the XOR circuit 54, and its output out00⊕out01 and the data out01 are combined into out0. Similarly, the other remaining pieces of data mid11, mid12 and mid13 are also transformed into the data out1, out2 and out3 in the nonlinear transformation parts 3451, 3452 and 3453 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.
As described above, according to this embodiment, in each of the nonlinear transformation parts 3430 to 3433 and 3450 to 3453 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 3430 to 3433 and 3450 to 3453 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 3430 to 3433 and 3450 to 3453 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.
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/liner probability p4 as a whole.
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 liner transformation may be performed in subdata.
Step S4: Perform liner processing of the left block data Ri by the block data Yi to generate the block data Li*.
Step S31: Perform first key-dependent liner transformation of the right data Ri into the data Ri*.
Step S32: Split the data Ri* into n m-bit data in0, in1, ..., inn-1 (where m = 8 and n = 4, for instance).
Step S33: Read out data mid00, mid01, ..., mid0(n-1) from n first S-boxes using the data in0, in1, ..., inn-1 as addresses.
Step S34: Perform key-dependent linear transformation of the data mid00 to mid0(n-1) by the subkey ki1 to generate data mid10 to mid1(n-1).
Step S35: Read out data out0 to outn-1 from n second S-boxes using the data mid10 to mid1(n-1) as addresses.
Step S36: Combine the data out0 to outn-1 into data Y*i.
Step S37: Perform third key-dependent liner transformation of the data Y*i to generate data Yi and output it.
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 380 to 38N-1 shown in Fig. 3 may also be programmed intact to implement the data diffusion part according to the present invention.
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 liner 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.
Fig. 13 illustrates the function 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.
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 L0 and R0 in the initial splitting part 303. For example, 128-bit data is split into two pieces of 64-bit block data L0 and R0. The key-dependent initial transformation part 302 performs a liner 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.
The right block data R0 is provided to the nonlinear function part 304 together with the key data k00, k01 and k02 stored in the key storage part 322, and in the nonlinear function part 304 it is nonlinearly transformed to data Y0. The data Y0 and the data L0 are transformed by a linear operation to data L0* in the liner operation part 305. The data L0* and the data R0 undergo data-position swapping in the swapping part 306 to provide L1←R0 and R1←L0*, and the pieces of data L1 and R1 are fed to the next first round processing part 381.
Thereafter, in an i-th round processing parts 38i (where i = 0, 1, ..., N-1) the same processing as mentioned above is repeated for two pieces of input block data Li and Ri. That is, the right block data Ri is input to the nonlinear function part 304 together with the key data ki0, ki1 and ki2, and in the nonlinear function part 304 it is nonlinearly transformed to block data Yi. The block data Yi and the block data Li are transformed to data Li* by a linear operation in the linear operation part 305. The data Li* and the data Ri are swapped in data position in the swapping part 306, that is, Li+1←Ri, Ri+1←Li*. The linear operation part 305 is to perform, for instance, an exclusive OR operation.
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, ..., k10, k11, k12, k00, k01, k02, fk.
The right block data Ri is input to the nonlinear function part 304 together with the key data ki0, ki1 and ki2 stored in the key storage part 322. In the first key-dependent linear transformation part 341 the right block data Ri is transformed to data Ri* = Ri⊕ki0 , for example, by XORing with the subkey data ki0. The thus transformed data Ri* is split to n = 8 pieces of data in0, in1, in2, ..., in7 in the splitting part 342. The eight pieces of data in0 to in7 are nonlinearly transformed to data mid00 to mid07 in nonlinear transformation parts 3430 to 3437, thereafter being input to the second key-dependent linear transformation part 344 using the key data ki1.
The second key-dependent linear transformation part 344 performs linear transformation (XORing) among the pieces of data mid00, mid01, mid02, ..., mid07 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 ki1 to provide output data mid10, mid11, mid12, ..., mid17 of the eight routes. The eight pieces of data are input to nonlinear transformation parts 3450, 3451, 3452, ..., 3457, wherein they are transformed to data out0, out1, out2, ..., out7, respectively. These eight pieces of data are combined into data Yi* in a combining part 346; furthermore, in the third key-dependent linear transformation part 347 the data Yi* undergoes linear transformation with the key data ki2 to generate output data Yi.
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 nd as 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.
Step 1: Set the security threshold T (where T is an integer such that 2 ≤ T ≤ n).
Step 2: Prepare a set of column vectors C whose Hamming weights are equal to or larger than T-1.
Step 3: Select a subset Pc of eight column vectors from the set C. If rank(Pc) ≠ 8, then the subset Pc is not accepted as a candidate.
For any two columns (columns a, b):
For any three columns (columns a, b, c):
For any four columns (columns a, b, c, d):
nd = min{ndi | 0≤i≤9}
Intuitively, Equations nd0 to nd9 represent 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 fight-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 Δza and Δzb, respectively. At this time, [Δz'i] = [tiaΔza⊕tibΔzb] (0≤i<8) In particular, when Δza = Δzb , [Δz'i] = [(tia⊕tib)Δzn] (0≤i<8) Accordingly, the minimum number of active s-boxes in this case is given by nd0.
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 nd ≥ 6 = T but that there are 10080 candidate matrices with nd = 5 = T . Hence, the invulnerability of the round function using such a matrix P against differential cryptanalysis is p ≤ ps5. And the invulnerability against linear cryptanalysis is also q ≤ ps5.
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)16≈293 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 trough 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)4≈218, which is sufficiently small for the exhaustive search.
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.
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 n1 =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:
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 n1 = 5.
The key transformation part 344B calculates the XORs of the key data Ki10 ki11, Ki12, ..., ki17 and the outputs from the linear transformation part by XOR circuits 630, 631, 632, ..., 637, and yield output data mid10, mid11, mid12, ..., mid17. With such a functional construction as depicted in Fig. 17, the following operations are performed. mid10=mid01⊕mid02⊕mid03⊕mid04⊕mid05⊕mid06⊕ki10 mid11=mid00⊕mid02⊕mid03⊕mid05⊕mid06⊕mid07⊕ki11 mid12=mid00⊕mid01⊕mid03⊕mid04⊕mid06⊕mid07⊕ki12 mid13=mid00⊕mid01⊕mid02⊕mid04⊕mid05⊕mid07⊕ki13 mid14=mid00⊕mid01⊕mid03⊕mid04⊕mid05⊕ki14 mid15=mid00⊕mid01⊕mid02⊕mid05⊕mid06⊕ki15 mid16=mid01⊕mid02⊕mid03⊕mid06⊕mid07⊕ki16 mid17=mid00⊕mid02⊕mid03⊕mid04⊕mid07⊕ki17
The above operations generate the data mid10, mid11, mid12, ..., mid17. Incidentally, the subkey ki1 is composed of eight pieces of data ki10, ki11, ki12, ..., ki17. In Fig. 17, the pieces of data mid00 to mid07 are input to routes 600 to 607, respectively.
The XOR circuits 614, 615, 616, 617 on the routes 604, 605, 606, 607 calculate the XORs of the data mid04 and mid00, mid05 and mid01, mid06 and mid02, mid07 and mid03, respectively.
The XOR circuits 610, 611, 612, 613 on the routes 600, 601, 602, 603 calculate the XORs of the data mid00 and the output from the XOR circuit 616, the data mid01 and the output from the XOR circuit 617, the data mid02 and the output from the XOR circuit 614, the data mid03 and the output from the XOR circuit 615, respectively.
The XOR circuits 624, 625, 626, 627 on the routes 604, 605, 606, 607 calculate the XORs of the outputs from the XOR circuits 613 and 614, the outputs from the XOR circuits 610 and 615, the outputs from the XOR circuits 611 and 616, the outputs from the XOR circuits 612 and 617, respectively.
The XOR circuits 620, 621, 622, 623 on the routes 600, 601, 602, 603 calculate the XORs of the outputs from the XOR circuits 610 and 624, the outputs from the XOR circuits 611 and 625, the outputs from the XOR circuits 612 and 626, the outputs from the XOR circuits 613 and 627, respectively.
Furthermore, the XOR circuits 630 to 637 on the routes 600 to 607 XOR the outputs from the XOR circuits 620 to 627 and the key data ki10 to ki17, respectively, providing the outputs mid10 to mid17 from the routes 600 to 607. That is, the outputs mid10 to mid17 are the XORs of six pieces of data selected from the input data mid00 to mid07 and the key data, and the outputs mid14 to mid17 are the XORs of five pieces of data selected from the input data mid00 to mid07 and the key data.
Turning back to Fig. 14, the pieces of data mid10, mid11, mid12, ..., mid17 are nonlinearly transformed to pieces of data out0, out1, out2, ..., out7 in the nonlinear transformation parts 3450, 3451, 3452, ..., 3457, and in the combining part 346 the eight pieces of data out0, out1, out2, ..., out7 are combined into a single piece of data Yi*. Finally, the data Yi* is linearly transformed to data Yi, for example, by a ki2-bit left rotation in the third key-dependent linear transformation 347 using the key data ki2, thereby generating the output data Yi from the nonlinear function part 304.
The nonlinear transformation parts 3430 to 3437 and 3450 to 3457 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.
The eight nonlinear transformation parts 3430 to 3437 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 3450 to 3457. 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 3430 to 3437 and 3450 to 3457, the nonlinear function part 304 provides a differential/linear probability p5 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 ≤ p10r; for example, when r = 4 (12 rounds), P ≤ p40. 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. In this instance, the following operations are conducted. mid10=mid01⊕mid02⊕mid04⊕mid05⊕mid06⊕mid07⊕ki10 mid11=mid01⊕mid02⊕mid03⊕mid04⊕mid06⊕ki11 mid12=mid00⊕mid01⊕mid03⊕mid04⊕mid05⊕mid06⊕ki12 mid13=mid00⊕mid03⊕mid04⊕mid06⊕mid07⊕ki13 mid14=mid00⊕mid02⊕mid03⊕mid05⊕mid06⊕mid07⊕ki14 mid15=mid00⊕mid01⊕mid02⊕mid05⊕mid06⊕ki15 mid16=mid00⊕mid01⊕mid02⊕mid03⊕mid04⊕mid07⊕ki16 mid17=mid00⊕mid02⊕mid04⊕mid05⊕mid07⊕ki17
Alternatively, the circuit construction of Fig. 19 may be used, in which case the following operations are performed. mid10=mid00⊕mid01⊕mid04⊕mid05⊕mid06⊕ki10 mid11=mid01⊕mid03⊕mid04⊕mid05⊕mid07⊕ki11 mid12=mid00⊕mid02⊕mid04⊕mid06⊕mid07⊕ki12 mid13=mid02⊕mid03⊕mid05⊕mid06⊕mid07⊕ki13 mid14=mid00⊕mid01⊕mid03⊕mid05⊕mid06⊕mid07⊕ki14 mid15=mid01⊕mid02⊕mid03⊕mid04⊕mid06⊕mid07⊕ki15 mid16=mid00⊕mid01⊕mid02⊕mid04⊕mid05⊕mid07⊕ki16 mid17=mid00⊕mid02⊕mid03⊕mid04⊕mid05⊕mid06⊕ki17
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 mid10, mid11, mid12, ..., mid17, that is, four pieces of output data derived from six pieces of data selected from the eight pieces of input data mid00, mid01, mid02, ..., mid07 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 mid00, mid01, mid02, ..., mid07 each affect the output data of at least four or more other routes (for instance, in the Fig. 17 example the input data mid00 affects the six pieces of output data mid11, mid12, mid13, mid14, mid15 and mid17), the nonlinear function part 304 provides a differential/linear probability p5 a whole as described previously with reference to the Fig. 17.
The key data {fk, k00, k01, k02, k10, k11, k12, ..., 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.
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. Patent No. 4,850,019.
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 3430 to 3437 in the nonlinear function part 304 of Fig. 14 are modified like the nonlinear transformation parts 3430', 3431', 3432' and 3433' 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.
As depicted in Fig. 13, the right block data Ri is input to the nonlinear function part 304 together with the key data ki0, ki1, ki2 stored in the key storage part 322. In the first key-dependent liner transformation part 341 the data Ri is, for example, XORed with the key data ki0 and hence is linearly transformed to data Ri* = Ri⊕ki0 as in the case of Fig. 14. Then the data Ri* is split into eight pieces of data in0, in1, in2, ..., in7 in the splitting part 342. The eight pieces of data in0, in1, in2, ..., in7 are nonlinearly transformed to data MID00, MID01, MID02, ..., MID07 in the nonlinear transformation parts 3430', 3431', 3432', ..., 3437', respectively. The nonlinear transformation part 3430' is so designed as to transform the m-bit data in0 to the following 8×m-bit data. MID00=[00...0(2), mid00, mid00, mid00, mid00, mid00, 00...0(2), mid00] That is, the nonlinear transformation part 3430' has, for example, as shown in Fig. 20A, an S-box which outputs the data mid00 in high-order m bits as does the nonlinear transformation part 3430 in the fourth embodiment of Fig. 14 and outputs "00...0(2)" as low-order m bits; furthermore, it branches the output data mid00 in six routes and "00...0(2)" in two other routes.
The nonlinear transformation part 3431' has, as depicted in Fig. 20B, an S-box 3431 which outputs the data mid01 in high-order m bits and outputs "00...0(2)" as low-order m bits; furthermore, it branches the output data mid01 in six routes and m-bit data "00...0" in two other routes. The other nonlinear transformation parts 3432' to 3437' are also similarly constructed; in Fig. 20C there is depicted the construction of the nonlinear transformation part 3437' but no description will be repeated. These nonlinear transformation parts 3431' to 3437' transform data in1 to in7 to the following data MID01 to MID07, respectively. MID01=[mid01, 00...0(2), mid01, mid01, mid01, mid01, mid01, 00...0(2)] MID02=[mid02, mid02, 00... 0(2), mid02, 00...0(2), mid02, mid02, mid02] MID03=[mid03, mid03, mid03, 00...0(2), mid03, 00...0(2), mid03, mid03] MID04=[mid04, 00...0(2), mid04, mid04, mid04, 00...0(2), 00...0(2), mid04] MID05=[mid05, mid05, 00...0(2), mid05, mid05, mid05, 00...0(2), 00...0(2)] MID06=[mid06, mid06, mid06, 00...0(2), 00...0(2), mid06, mid06, 00...0(2)] MID07=[00...0(2), mid07, mid07, mid07, 00...0(2), 00...0(2), mid07, mid07]
These pieces of data MID00 to MID07 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 MID00 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 mid00 and mid02 to mid07 except mid01 are all set as "00...0(2)." The same goes for the data MID02 to MID07. These nonlinear transformation parts 3430' to 3437' may be formed by memory from which the pieces of data MID00 to MID07 are directly read out using the data in0 to in7 as addresses.
Then the pieces of data MID00 to MID07 are input to the second key-dependent linear transformation part 344 using the key data ki1 as shown in Fig. 21. The second key-dependent linear transformation part 344 is made up of XOR circuits 411 to 414 each of which XORs two pieces of input data, XOR circuits 421 and 422 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 ki1. With this construction, the following operation is conducted. MID1=MID00⊕MID01⊕MID02⊕MID03⊕MID04⊕MID05⊕MID06⊕MID07⊕ki1 This output MID1 is split into eight blocks, which are output as data mid10, mid11, mid12, ..., mid17. Eventually, the linear transformation by the second key-dependent linear transformation part 344, expressed in units of m-bit subblocks, becomes as follows: mid10 = mid01⊕mid02⊕mid03⊕mid04⊕mid05⊕mid06⊕ki10 mid11 = mid00⊕mid02⊕mid03⊕mid05⊕mid06⊕mid07⊕ki11 mid12 = mid00⊕mid01⊕mid03⊕mid04⊕mid06⊕mid07⊕ki12 mid13 = mid00⊕mid01⊕mid02⊕mid04⊕mid05⊕mid07⊕ki13 mid14 = mid00⊕mid01⊕mid03⊕mid04⊕mid05⊕ki14 mid15 = mid00⊕mid01⊕mid02⊕mid05⊕mid06⊕ki15 mid16 = mid01⊕mid02⊕mid03⊕mid06⊕mid07⊕ki16 mid17 = mid00⊕mid02⊕mid03⊕mid04⊕mid07⊕ki17 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 mid10, mid11, mid12, ..., mid17 are generated. Incidentally, the subkey data ki1 is composed of eight pieces of data ki10, ki11, ki12, ..., ki17.
Next, the eight pieces of data mid10, mid11, mid12, ..., mid17 are nonlinearly transformed to eight pieces of data out0, out1, out2, ..., out7 in the nonlinear transformation parts 3450, 3451, 3452, ..., 3457 in Fig. 14, and the eight pieces of data out0, out1, out2, ..., out7 are combined into a single piece of data Y1* in the combining part 346. Finally, the data Yi* is linearly transformed to data Yi by, for example, a ki2-bit left rotation in the third key-dependent linear transformation part 347 using the key data ki2.
Furthermore, as is the case with the fourth embodiment, the eight nonlinear transformation parts 3430 to 3433 and 3450 to 3453 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 3430' to 3437', the differential/linear probability of the nonlinear function 304 becomes p5 as a whole.
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 ki1. That is, the XOR circuits 630 to 637 in Fig. 17 and the circuits corresponding thereto in Figs. 18, 19 and 21 may be omitted.
Incidentally, when in each embodiment the key scheduling part 20 has the same construction as depicted in Fig. 3, the subkeys used as ki and ki+1 in the data diffusion part 10 become the outputs Q2j and Q2j+1 (where i = 2j ) from the key processing part 21j in the key scheduling part 20. On the other hand, since it is the subkeys kN and kN-1 that 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.
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 kN and kN-1 leads 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.
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.
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 function 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.
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 (Lj, Yj, vj), part of this value is used as the input ( Yj+1 = Yj , vJ+1 = vj ) to the G-function called a (j+1)-th time. Assume here that Y0 is a value containing K and that v0 is a predetermined value (0, for instance).
For the given master key K, the subkey ki (where i = 0, 1, 2, ..., N-1) is determined as follows: (Li, (Y1, v1)) = G(Y0, v0) (Lj+1, (Yj+1, vj+1)) = G(Yj, vj) (j = 1, 2, ..., M-1) ki = H(i, L1, L2, ..., LM) (i = 0, 1, 2, ..., N-1) where the H-function is means to extract from each component Li information 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.
This example is intended to increase the security of the key scheduling part shown in Fig. 8 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.
In Fig. 3 16 Q components are obtained by an 8 (= N/2) rounds of data diffusion parts. Here, let Qj represent the respective Q component. Each Qj component is 16-bit. The subkey generation part 240 constructs the subkey k0 from the value of a first bit of the respective Qj component, the subkey k1 from the value of a second bit of the respective Qj component, and in general, the subkey ki-1 from the value of an i-th bit of the Qj component. That is, letting Qj[i] represent the i-th bit of the Qj component, the subkey ki is expressed by the following equation. Ki-1 = (Q1[i], Q2[i], ..., Qj[i], ..., Q16[i]) where 1 ≤ i, j ≤ 16.
This processing method will be reviewed below in the framework of the G- and the H-function mentioned above. Here, Yj represents the value of 64 bits, YjL the value of high-order 32bits of Yj and YjR the value of low-order 32 bits of Yj.
Letting the output from the G-function for the input (Yj, vj) be represented by (Lj+1, (Yj+1, vj+1)) = G(Yj, vj) (0 ≤ j ≤ 7), the output (Lj+1, (Yj+1, vj+1)) is given by the following equations. Yj+1 L = Yj R Yj+1 R=Lj+1 = fk(Yj L, Yj R⊕vj) vj+1 = Yj L The subkey ki is given as a function of i and L1 to L8 by the following equation. Ki-1 = H(i, L1, L2, ..., L8) Letting each L1 be represented by (tj(1), tj(2), ..., tj(32)) the H-function constructed the subkey ki as follows: Ki = (t1 (i), t1 (16+i), t2 (16+i), ..., t8 (i), t8 (16+i)) (1 ≤ i ≤ 16)
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.
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 Y0 to the first-round G-function part 22-1 together with a constant v0, and Yj-1 and vj-1 are input to the G-function part 22-j of each j-th round; each G-function part randomizes Yi-1 and outputs Lj, Yj and vj. Lj is an intermediate key and Yj and vj are fed to the next G-function part 22-(j+1). That is, after setting Y0 = K and v0 =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.
Step 1: Upon input Yj and vj to the G-function part 22-(j+1), split Yj into two blocks (YjL, YjR) by a splitting part 221 in Fig. 25.
Step 2: Output YjL as vj+1. Input YjL to a data diffusion part (fk) 222.
Step 3: Input YjR to a data swapping part 224. Input YjR and vj to an XOR circuit 223 to compute YjR⊕vj and input the result of computation to the data diffusion part (fk) 222.
Step 4: Upon receiving YjL and YjR⊕vj as inputs thereto, the data diffusion part (fk) 222 outputs the result of computation as Lj+1 and, at the same time, input it to the swapping part 224.
Step 5: Upon receiving YjR and the result of computation Lj+1 by the data diffusion part (fk) 222, the swapping part 224 renders YjR to Yj+1L and Lj+1 to Yj+1R, then concatenates them to Yj+1 = (Yj+1 L, Yj+1 R) , and outputs it.
Step 1: Read out each component Li from the storage part 230 and input it to a bit splitter 241 to split it bitwise as follows: (tj (1), tj (2), ..., tj (32))=Lj (j = 1, 2, ..., 8)
Step 2: Input (t1(i), t1(16+i), t2(i), t2(16+i), ..., t8(i), t8(16+i) to a bit combiner 242 to obtain the subkey as follows: ki = (t1 (i), t1 (16+i), t2 (i), t2 (16+i), ..., t8 (i), t8 (16+i)) (i = 1, 2, .., 16)
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 sixth embodiment.
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.
Step 1: Upon input of Yj and vj to the G-function part 22-(j+1), split Yj into two blocks (YjL, YjR) by the splitting part 221.
Step 2: Output YjL as vj+1. And input YjL to the data diffusion part (fk) 222.
Step 3: Input YjR to the swapping part 224. And input YjR and vj to the XOR circuit 223 to calculate YjR⊕vj and input it to the data diffusion part (fk) 222.
Step 4: Upon receiving YjL and YjR⊕vj, the data diffusion part (fk) 222 inputs the result of its computation as Lj+1 to the subkey generation part 250 (Fig. 23B) and, at the same time, input it to the swapping part 224.
Step 5: Upon receiving YjR and the result of calculation Lj+1 from the data diffusion part (fk) 222, the swapping part 224 renders YjR to Yj+1L and Lj+1 to Yj+1R, then concatenates them to Yj+1 = (Yj+1 L, Yj+1 R) and outputs it.
Step 6: As depicted in Fig. 27, the subkey generation part 250 input Lj to a bit splitter 251 to split it bitwise as follows: (tj (1), tj (2), ..., tj (32)) = Lj (j = 1, 2, ..., 8) and then input tern to an information distributor 252.
Step 7: The bit string (tj(1), tj(2), ..., tj(32)) input to the information distributor 252 is information on the bit position of Lj determined by the bit position q of the subkey ki for a suffix i being used as information on the bit position q of the subkey ki, and is stored for each Lj in one of 16 storage areas of the storage part 260 divided for each subkey ki = (t1 (i), t1 (16+i), t2 (i), t2 (16+i), ..., t8 (i), t8 (16+i))
Step 8: When 16-bit information is set for each ki, that is, when the subkey ki generated, output its value (i = 1, 2, ..., 16).
This embodiment will also be described in the framework of the G-and H-function.
Let the output from the G-function for the input (Yj, vj) be represented by (Lj+1, (Yj+1, vj+1)) = G(Yj, vj) (0 ≤ j ≤ 7) and let the output be set as follows: ((Yj (1), Yj (2), Yj (3), Yj (4)), vj) → ((L(1)j+1,L(2)j+1,L(3)j+1,L(4)j+1),[(Y(1)j+1,Y(2)j+1,Y(3)j+1,Y(4)j+1),vj+1]) Here, the following definitions are given. Y(1)j+1 = f(Yj(i)) (i = 1, 2, 3, 4) L(0)j+1 = vj L(i)j+1 = f(L(i-1)j+1)⊕Y(i)j+1 (i = 1, 2, 3, 4) vj+1 = L(4)j+1 Further, in ki = H(i, L1, L2, ..., L8) the following definitions are given. qi+4j = L(i+1)j+1 (i = 0, 1, 2, 3) (ti(0), ti(1) ,..., ti(7))=qi (i = 0, 1, ..., 31) k(i+1) = (t([i/2])0+(i mod 2), t([i/2])2+(i mod 2),...,t([i/2])30+(i mod 2)) (i = 0, 1, ..., 15) Suppose that [i/2] in Equation (43) represents
Step 1: Set as v0 a value extracted from
0123456789abcdef101112....(hex) by the same number of bits as the bit length of the function f.
Generation of Intermediate Key: The following procedure is repeated for j = 0, 1, 2, ..., 7.
Step 1: Divide equally the input Yj into four (Yj(1), Yj(2), Yj(3), Yj(4)).
Step 2: For i = 1, 2, 3, 4, compute Yj+1 (i) = f(Yj (i)) by data diffusion part 611 to 614.
Step 3: set Lj+1= vj .
Step 4: For I = 1, 2, 3, 4, compute f(Lj+1(i-1)) by data diffusion part 621 to 624, and input the result of computation to an XOR circuit 63i to XOR it with Yj+1(i) to obtain Lj+1 (i) = f(Lj+1 (i-1)⊕Yj+1 (i) .
Step 5: set Yj+1 = (Yj+1 (1), Yj+1 (2), Yj+1 (3), Yj+1 (4)) .
Step 6: set Lj+1=Lj+1 (1), Lj+1 (2), Lj+1 (3), Lj+1 (4)) .
Step 7: Set vj+1 = Lj+1 (4) .
Generation of Subkey: As is the case with the sixth embodiment, Equation (43) is implemented to obtain k1, k2, ..., kN (where N ≤ 16).
Furthermore, according to the key scheduling of the present invention, even if k6, k7, k8, k9, k10 and k11 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 Li components 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.
A data transformation device which has key storage means for storing plural pieces of key data and a plurality of cascade-connected round processing parts each composed of a nonlinear function part supplied with said plural pieces of key data to perform key-dependent nonlinear transformation, whereby input data is transformed to different data in dependence on key data, said nonlinear function part of each of said round processing parts comprising:
wherein said second key-dependent linear transformation means contains a linear transformation layer wherein the input thereto is transformed linearly using XORs defined by an n × n matrix.
The data transformation device as claimed in claim 1, which further comprises:
The data transformation device as claimed in claim 2, which further comprises initial transformation means for transforming said input data and for supplying said transformed input data to said initial splitting means.
The data transformation device as claimed in claim 2 or 3, which further comprises final transformation means for transforming the output data from said final combining means to provide output data from said data transformation device.
The data transformation device as claimed in claim 3 or 4, wherein at least one of said initial transformation means and said final transformation means is key-dependent transformation means which performs transformation based on key data stored in said key storage means.
The data transformation device as claimed in any one of claims 1 to 5, wherein said nonlinear function part is provided with third key-dependent linear transformation means for linearly transforming the output data from said combining means based on third key data stored in said key storage means to provide the output from said nonlinear function part.
The data transformation device as claimed in any one of claims 1 to 6, wherein said first key-dependent liner transformation means, said second key-dependent linear transformation means and/or said third key-dependent linear transformation means is linear transformation means which performs fixed linear transformation.
The data transformation device as claimed in any one of claims 1 to 7, wherein said first nonlinear transformation means and said second nonlinear transformation means are each provided with: means for splitting the input subdata thereto into two subblocks; means for performing linear transformation and nonlinear transformation of each of said two split subblocks in cascade; and means for combining the transformed subblocks from said cascade transformation means to provide transformed output subdata corresponding to said input subdata.
The data transformation device as claimed in any one of claims 1 to 8, wherein said n × n matrix is formed by n column vectors whose Hamming weights are equal to or larger than T-1 for a predetermined security threshold T.
The data transformation device as claimed in claim 9, wherein said matrix is selected from a plurality of matrix candidates which provides a maximum value of nd, said nd being the minimum number of active s-boxes.
The data transformation device as claimed in any one of claims 1 to 10, wherein said n × n matrix is a 4 × 4 matrix.
The data transformation device as claimed in claim 11, wherein said second linear transformation means is means which inputs thereto four data A1, A2, A3 and A4 from said first nonlinear transformation means, computes B1 = A1⊕A3⊕A4 B2 = A2⊕A3⊕A4 B3 = A1⊕A2⊕A3 B4 = A1⊕A2⊕A4 and outputs data B1, B2, B3 and B4.
The data transformation device as claimed in claim 12, wherein said second liner transformation means is key-dependent linear transformation means, which is also supplied with key data k2=[k21, k22, k23, k24] from said key storage means and performs XOR operations by said key data k21, k22, k23 and k24 in the computations for said output data B1, B2, B3 and B4, respectively.
The data transformation device as claimed in claim 11, wherein:
said first nonlinear transformation means comprises: for four pieces of m-bit subdata in1, in2, in3 and in4 from said splitting means, for transforming said in1 to 4m-bit data MI1=[A1, 00...0(2), A1, A1] ; means for transforming said in2 to 4m-bit data MI2=[00...0(2), A2, A2, A2] ; means for transforming said in3 to 4m-bit data MI3=[A3, A3, A3, 00...0(2)] ; and means for transforming said in4 to 4m-bit data MI4=[A4, A4, 00...(2), A4] ; and
said second linear transformation means is means supplied with said data MI1, MI2, MI3 and MI4 from said first nonlinear transformation means, for computing B=MI1⊕MI2⊕MI3⊕MI4 and for outputting B=[B1, B2, B3, B4] .
The data transformation device as claimed in claim 14, wherein said second linear transformation means is a key-dependent linear transformation means, which is also supplied with 4m-bit key data k2 from said key storage means and performs an XOR operation by said key data k2 in the computation of said B.
The data transformation device as claimed in any one of claims 1 to 10, wherein said n × n matrix is an 8 × 8 matrix.
The data transformation device as claimed in claim 16, wherein said second linear transformation means is means which provides its eight pieces of output data B1 to B8 by obtaining four pieces of said output subdata B1, B2, B3 and B4 through XOR operations using six of eight pieces of subdata A1, A2, ..., A8 from said first nonlinear transformation means and by obtaining four pieces of said output subdata B5, B6, B7 and B8 through XORing using five of said eight pieces of subdata from said first nonlinear transformation means.
The data transformation device as claimed in claim 17, wherein said second linear transformation means is key-dependent linear transformation means, which is supplied with key data k2=[k21, k22, k23, k24, k25, k26, k27, k28] stored in said key storage means and performs XOR operations by said key data k21, k22, k23, k24, k25, k26, k27 and k28 for obtaining said output subdata [B1, B2, B3, B4, B5, B6, B7, B8].
The data transformation device as claimed in claim 16, wherein:
said first nonlinear means is means for transforming eight pieces of m-bit subdata in1 to in8 from said splitting means to eight pieces of 8m-bit data MI1=[00...0(2), A1, A1, A1, A1, A1, 00...0(2), A1], MI2=[A2, 00...0(2), A2, A2, A2, A2, A2, 00...0(2)] MI3=[A3, A3, 00...0(2), A3, 00...0(2), A3, A3, A3], MI4=[A4, A4, A4, 00...0(2), A4, 00...0(2), A4, A4], MI5=[A5, 00...0(2), A5, A5, A5, 00...0(2), 00...0(2), A5], MI6=[A6, A6, 00...0(2), A6, A6, A6, 00...0(2), 00...0(2)] MI7=[A7, A7, A7, 00...0(2), 00...0(2), A7, A7, 00...0(2)], and MI8=[00...0(2), A8, A8, A8, 00...0(2), 00...0(2), A8, A8]; and
said second liner transformation means is means supplied with said data MI1 to MI8 from said first nonlinear transformation means, for computing B=MI1⊕MI2⊕MI3⊕MI4⊕MI5⊕MI6⊕MI7⊕MI8 and for outputting B=[B1, B2, B3, B4, B5, B6, B7, B8] .
The data transformation device as claimed in claim 19, wherein said second linear transformation means is key-dependent liner transformation means, which is also supplied with 8m-bit key data k2 stored in said key storage means and performs an XOR operation by said key data k2 for obtaining said B.
A recording medium on which there is recorded a data transformation program by which round processing containing nonlinear function process of performing key-dependent nonlinear transformations based on plural pieces of key data stored in key storage means is executed a plurality of times in cascade to thereby transform input data to different data in dependent on key data, said nonlinear function process of said round processing comprises:
a second key-dependent liner transformation step of performing a linear transformation using second key data and output subdata by said nonlinear transformation step;
wherein said second key-dependent linear transformation step includes an XOR linear transformation step of performing, for the input thereto, XORing defined by an n × n matrix.
The recording medium as claimed in claim 21, wherein said data transformation program comprises:
The recording medium as claimed in claim 22, wherein said data transformation program includes an initial transformation step of transforming said input data and supplying said transformed input data to said initial splitting step.
The recording medium as claimed in claim 22 or 23, wherein said data transformation program includes a final transformation step of transforming the output data by said final combining step to provide output data.
The recording medium as claimed in claim 23 or 24, wherein at least one of said initial transformation step and said final transformation step of said data transformation program is a key-dependent transformation step of performing transformation based on key data.
The recording medium as claimed in any one of claims 21 to 25, wherein said nonlinear function processing step includes a third key-dependent linear transformation step of linearly transforming the output data by said combining step based on third key data stored in said key storage means to provide the output of said nonlinear function processing step.
The recording medium as claimed in any one of claims 21 to 28, wherein said first key-dependent liner transformation step, said second key-dependent liner transformation step and/or said third key-dependent liner transformation step is a liner transformation step of performing fixed liner transformation.
The recording medium as claimed in any one of claims 21 to 27, wherein said first nonlinear transformation step and said second nonlinear transformation step are each include: a step of splitting the input data thereto into two subblocks; a step of performing linear transformation of each of said two split subblocks; a step of performing liner transformation and nonlinear transformation of each of said two split subblocks in cascade; and a step of combining the transformed subblocks by said cascade transformation step into nonlinearly transformed output data corresponding to said input data.
The recording medium as claimed in any one of claims 21 to 28, wherein said n × n matrix is formed by n column vectors whose Hamming weights are equal to or larger than T-1 for a predetermined security threshold T.
The recording medium as claimed in claim 29, wherein said matrix is selected from a plurality of matrix candidates which provides a maximum value of nd, said nd being the minimum number of active s-boxes.
The recording medium as claimed in any one of claims 21 to 30,
wherein said n × n matrix is a 4 × 4 matrix.
The recording medium as claimed in claim 31, wherein said second linear transformation step is a step of inputting thereto four data A1, A2, A3 and A4 by said first nonlinear transformation step, computing B1 =A1⊕A3⊕A4 B2 = A2⊕A3⊕A4 B3 = A1⊕A2⊕A3 B4 = A1⊕A2⊕A4 and outputting data B1, B2, B3 and B4.
The recording medium as claimed in claim 32, wherein said second linear transformation step is a key-dependent liner transformation step of inputting key data k2=[k21, k22, k23, k24] in said key storage means and performing XOR operations by said key data k21, k22, k23 and k24 in the computations for said output data B1, B2, B3 and B4, respectively.
The recording medium as claimed in claim 32 or 33, wherein:
said first nonlinear transformation step comprises: for four pieces of m-bit subdata in1, in2, in3 and in4 from said splitting means a step of transforming said in1 to 4m-bit data MI1=[A1, 00...0(2), A1, A1] ; a step of transforming said in2 to 4m-bit data MI2=[00...0(2), A2, A2, A2] ; a step of transforming said in3 to 4m-bit data MI3=[A3, A3, A3, 00...0(2)] ; and a step of transforming said in4 to 4m-bit data MI4=[A4, A4, 00...(2), A4] ; and
said second linear transformation step is a step of inputting said data MI1, MI2, MI3 and MI4 by said first nonlinear transformation step, computing B=MI1⊕MI2⊕MI3⊕MI4 and outputting B=[B1, B2, B3, B4] .
The recording medium as claimed in claim 34, wherein said second linear transformation step is a key-dependent linear transformation step of inputting 4m-bit key data k2 in said key storage means and performing an XOR operation by said key data k2 in the computation of said B.
The recording medium as claimed in any one of claims 21 to 30, wherein said n × n matrix is an 8 × 8 matrix.
The recording medium as claimed in claim 36, wherein said second linear transformation step is a step of providing its eight pieces of output data B1 to B8 by obtaining four pieces of said output subdata B1, B2, B3 and B4 through XOR operations using six of eight pieces of subdata A1, A2, ..., A8 by said first nonlinear transformation step and by obtaining four pieces of said output subdata B5, B6, B7 and B8 through XORing using five of said eight pieces of subdata by said first nonlinear transformation step.
The recording medium as claimed in claim 37, wherein said second linear transformation step is a key-dependent linear transformation step of inputting key data k2=[k21, k22, k23, k24, k25, k26, k27, k28] stored in said key storage means and performing XOR operations by said key data k21, k22, k23, k24, k25, k26, k27 and k28 for obtaining said output subdata [B1, B2, B3, B4, B5, B6, B7, B8].
The recording medium as claimed in claim 37 or 38, wherein:
said first nonlinear step is a step of transforming eight pieces of m-bit subdata in1 to in8 by said splitting means to eight pieces of 8m-bit data MI1=[00...0(2), A1, A1, A1, A1, A1, 00...0(2), A1], MI2=[A2, 00...0(2), A2, A2, A2, A2, A2, 00...0(2)] MI3=[A3, A3, 00...0(2), A3, 00...0(2), A3, A3, A3], MI4=[A4, A4, A4, 00...0(2), A4, 00...0(2), A4, A4], MI5=[A5, 00...0(2), A5, A5, A5, 00...0(2), 00...0(2), A5], MI6=[A6, A6, 00...0(2), A6, A6, A6, 00...0(2), 00...0(2)] MI7=[A7, A7, A7, 00...0(2), 00...0(2), A7, A7, 00...0(2)], and MI8=[00...0(2), A8, A8, A8, 00...0(2), 00...0(2), A8, A8]; and
said second linear transformation step is a step of inputting said data MI1 to MI8 by said first nonlinear transformation step, computing B=MI1⊕MI2⊕MI3⊕MI4⊕MI5⊕MI6⊕MI7⊕MI8 and outputting B=[B1, B2, B3, B4, B5, B6, B7, B8] .
The recording medium as claimed in claim 39, wherein said second linear transformation step is a key-dependent linear transformation step of inputting 8m-bit key data k1 stored in said key storage means and performing an XOR operation by said key data k2 for obtaining said B.
The data transformation device as claimed in any one of claims 1 to 20, which further comprises:
G-function means composed of M rounds means which are supplied with a master key K and generate intermediate values Lj+1 (j = 0, 1, ..., M-1);
said G-function means takes said master key as at least one part of Y0, inputs Yj, and vj in the output (Lj, Yj, vj) from the j-th round, into its (j+1)-th round (where j = 0, 1, ..., M-1) diffuses the inputs and outputs Lj+1, Yj+1 and vj+1; and
said H-function means inputs i (where i = 1, 2, ..., N) and L1, L2, ..., LM stored in said intermediate value storage means, extracts information about bit positions of subkeys ki determined by said i from said L1, ..., LM, and outputs said subkeys, said subkeys being stored in said key storage means.
said H-function means inputs i, q and Lj (1 ≤ i ≤ N, 1 ≤ j ≤ M, 1 ≤ q ≤ the numbers of bits ki), and extracts bit position information defined by i and q from Lj to provide information about the bit position q of the subkeys ki, said subkeys being stored as said plurality of key data in said key storage means.
The data transformation device as claimed in claim 41 or 42, wherein said G-function means comprises:
data splitting means for splitting the input Yj into two blocks (YjL, YjR) and for outputting YjL as vj+1;
XOR means for computing YjR⊕vj from said YjR and said vj;
data diffusion means supplied with said YjL and the output from said XOR means, for diffusing them and for outputting the result as Lj+1; and
data swapping means for rendering said YjR into Yj+1L and said Lj+1 into Yj+1R and for concatenating said Yj+1L and said Vj+1R into an output Yj+1 = (Yj+1 L, Yj+1 R) .
The data transformation device as claimed in claim 41, wherein said H-function means comprises:
bit splitting means for splitting bitwise each Lj read out of said intermediate value storage means into (tj (1), tj (2), ..., tj (2N))=Lj (j = 1, 2, ..., M); and
bit combining means for combining the resulting (t1(i), t1(N+i), t2(i), t2(N+i), ..., tM(i), tM(N+i)) and for outputting subkeys ki = (t1 (i), t1 (N+i), t2 (i), t2 (N+i), ..., tM (i), tM (N+i)) (i = 1, 2, ..., N).
The data transformation device as claimed in claim 42, wherein said H-function means comprises:
bit splitting means for splitting said each Lj bitwise into (tj (1), tj (2), ..., tj (2N))=Lj (j = 1, 2, ..., M); and
bit combining means for combining said bits (tj(1), tj(2), ..., tj(2N)) so that information about the bit position defined by the bit position q of ki for i becomes the bit position of ki, and for outputting subkeys ki = (t1 (i), t1 (N+i), t2 (i), t2 (N+i), ..., tM (i), tM (N+i)) (i = 1, 2, ..., N).
The data transformation device as claimed in claim 41 or 42, wherein said G-function means is means for performing the following operation:
For (Lj+1, (Yj+1, vj+1)) = G(Yj, vj) (0 ≤ j ≤ M-1), the output result ((Yj (1), Yj (2), Yj (3), vj) → ((L(1)j+1, L(2)j+1, L(3)j+1, L(4)j+1),[(Y(1)j+1, Y(2)j+1, Y(3)j+1, Y(4)j+1), vj+1]) where: Y(i)j+1 = f(Yj(i)) (i = 1, 2, 3, 4) L(0)j+1 = vj L(i)j+1 = f(L(i-1)j+1)⊕Y(i)j+1 (i = 1, 2, 3, 4) vj+1 = L(4)j+1; and said H-function means is means for performing the following operation:
For ki = H(i, L1, L2, ..., LM) q4i+j = L(i+1) j+1 (i = 0, 1, 2, 3) (ti(0), ti(1),&peseta;&peseta;&peseta;, ti(7))=qi (i = 0, 1, ..., 31) k(i+1) = (t([i/2])0+(i mod 2), t([i/2])2+(i mod 2),&peseta;&peseta;&peseta;,t([i/2])30+(i mod 2)) (i = 0, 1, ..., N-1).
An encryption key scheduling device for scheduling subkeys from a master key, comprising:
G-function means composed of M rounds means which are supplied with a master key K and generate intermediate values Lj (j = 0, 1, ..., M-1);
said G-function means takes said master key as at least one part of Y0, inputs Yj and vj in the output (Lj, Yj, vj) from the j-th round, into its (j+1)-th round (where j = 0, 1, ..., M-1) diffuses the inputs and outputs Lj+1, Yj+1 and vj+1; and
said H-function means inputs i (where i = 1, 2, ..., N) and L1, L2, ..., LM stored in said intermediate value storage means, extracts information about bit positions of subkeys ki determined by said i from said L1, ..., LM and outputs said subkeys.
G-function means composed of M rounds means which are supplied with a master key K and generate intermediate values Lj+1 (j =0, 1, ..., M-1);
said H-function means inputs i, q and Lj (1 ≤ i ≤ N, 1 ≤ j ≤ M, 1 ≤ q ≤ the numbers of bits ki), and extracts bit position information defined by i and q from Lj to provide information about the bit position q of the subkeys ki.
The encryption key scheduling device as claimed in claim 47 or 48, wherein said G-function means comprises;
data swapping means for rendering said YjR into Yj+1L and said Lj+1 into Yj+1R and for concatenating said Yj+1L and said Yj+1R into an output Yj+1 = (Yj+1 L, Yj+1 R) .
The encryption key scheduling device as claimed in claim 47, wherein said H-function means comprises:
bit splitting means for splitting bitwise each Lj read out of said intermediate value storage means into (tj (1), tj (2), ..., tj (2N))=Lj (j=1, 2, ..., M); and
bit combining means for combining the resulting (t1(i), t1(N+i), t2(i), t2(N+i), ..., tM(i), tM(N+i)) and for outputting subkeys ki = (t1 (i), t1 (N+i), t2 (i), t2 (N+i), ..., tM (i), tM (N+i)) (i=1, 2, ..., N).
The encryption key scheduling device as claimed in claim 48,
wherein said H-function means comprises:
bit combining means for combining said bits (tj(1), tj(2), ..., tj(2N) so that information about the bit position defined by the bit position q of ki for i becomes the bit position of ki, and for outputting subkeys ki = (t1 (i), t1 (N+i), t2 (i), t2 (N+i), ..., tM (i), tM (N+i)) (i = 1, 2, ..., N).
The encryption key scheduling device as claimed in claim 47 or 48, wherein said G-function means is means for performing the following operation:
For (Lj+1, (Yj+1, vj+1)) = G(Yj, vj) (0 ≤ j ≤ M-1), the output result ((Yj (1), Yj (2), Yj (3)), vj} → ((L(1)j+1, L(2)j+1, L(3)j+1, L(4)j+1),[(Y(1)j+1, Y(2)j+1, Y(3)j+1, Y(4)j+1), vj+1]) where: Y(i)j+1 = f(Yj(i)) (i = 1, 2, 3, 4) L(0)j+1 = vj L(1)j+1 = f(L(i-1)j+1)⊕Y(i)j+1 (i = 1, 2, 3, 4) vj+1 = L(4)j+1; and said H-function means is means for performing the following operation:
For ki = H(i, L1, L2, ..., LM) q4i+j = L(i+1)j+1 (i = 0, 1, 2, 3) (ti(0), ti(1),&peseta;&peseta;&peseta;, ti(7))=qi (i = 0, 1, ..., 31) k(i+1)=(t([i/2])0+(i mod 2), t([i/2])2+(i mod 2),&peseta;&peseta;&peseta;,t([i/2])30+(i mod 2)) (i = 0, 1, ..., N-1).
A recording medium on which there is recorded a program for a computer to implement an encryption key scheduling device which inputs a master key K and generates therefrom a plurality of subkeys ki (i = 1, ..., N), said program comprising:
an intermediate key generation process in which said master key K as Y0 and a constant v0 are input, diffusion processing of said inputs is repeated in cascade a plurality of times and an intermediate value Lj (j = 1, 2, ..., M) is output for each diffusion processing;
a process in which, upon each generation of said intermediate value Lj, information about the bit position of said Lj defined by i of said subkeys kj and the bit position q of said ki is extracted as bit position information for said ki and is stored in an intermediate value storage part; and