Source: http://www.google.com/patents/US6769063?dq=7,634,557
Timestamp: 2016-02-09 00:20:19
Document Index: 275879980

Matched Legal Cases: ['art 14', 'art 14', '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', 'arts 345', 'art 346', 'art 347', 'art 304', 'art 344', 'art 344', 'art 304', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'art 344', 'arts 343', 'art 343', 'art 344', 'art 344', 'art 304', 'art 322', 'art 341', 'art 342', 'arts 343', 'art 343']

Patent US6769063 - Data converter and recording medium on which program for executing data ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA plurality of round processing parts (38) are provided each of which contains a nonlinear function part (304), and each nonlinear function part (304) comprises: a first key-dependent linear transformation part (341) which performs a linear transformation based on a subkey; a splitting part (342) which...http://www.google.com/patents/US6769063?utm_source=gb-gplus-sharePatent US6769063 - Data converter and recording medium on which program for executing data conversion is recordedAdvanced Patent SearchPublication numberUS6769063 B1Publication typeGrantApplication numberUS 09/600,955PCT numberPCT/JP1999/000337Publication dateJul 27, 2004Filing dateJan 27, 1999Priority dateJan 27, 1998Fee statusPaidAlso published asCA2319135A1, CA2319135C, DE69931606D1, DE69931606T2, DE69931606T8, EP1052611A1, EP1052611A4, EP1052611B1, EP1052611B9, WO1999038143A1Publication number09600955, 600955, PCT/1999/337, PCT/JP/1999/000337, PCT/JP/1999/00337, PCT/JP/99/000337, PCT/JP/99/00337, PCT/JP1999/000337, PCT/JP1999/00337, PCT/JP1999000337, PCT/JP199900337, PCT/JP99/000337, PCT/JP99/00337, PCT/JP99000337, PCT/JP9900337, US 6769063 B1, US 6769063B1, US-B1-6769063, US6769063 B1, US6769063B1InventorsMasayuki Kanda, Youichi Takashima, Kazumaro Aoki, Hiroki Ueda, Kazuo Ohta, Tsutomu MatsumotoOriginal AssigneeNippon Telegraph And Telephone CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (2), Non-Patent Citations (8), Referenced by (57), Classifications (8), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetData converter and recording medium on which program for executing data conversion is recorded
a first key-dependent linear transformation step of linearly transforming input data to a round processing part based on first key data stored in said key storage means; a splitting step of splitting output data by said first key-dependent linear transformation step into n pieces of subdata, said n being an integer equal to or larger than 4; a first nonlinear transformation step of nonlinearly transforming each of said n pieces of subdata; a second key-dependent linear transformation step of performing a linear transformation using second key data and output subdata by said nonlinear transformation step; a second nonlinear transformation step of performing a second nonlinear transformation of each of said n pieces of output subdata by said second key-dependent linear transformation step; and combining step of combining n pieces of output subdata by said second nonlinear transformation means into a single data for outputting as the result of said nonlinear function process; 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. 22. The recording medium as claimed in claim 21, wherein said data transformation program comprises:
an initial splitting step of splitting said input data into two pieces of data; a step of performing said nonlinear function process using one of said two pieces of data as the input thereto; a linear operation step of causing the output data by said nonlinear function processing step to act on the other piece of said data; and a final combining step of combining two pieces of data into a single piece of output data. 23. 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.
29. The recording medium as claimed in any one of claims 21, 22 or 23, 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.
31. The recording medium as claimed in any one of claims 21, 22 or 23, wherein said n�n matrix is a 4�4 matrix.
B 1=A 1⊕A 3⊕A 4 B 2=A 2⊕A 3⊕A 4 B 3=A 1⊕A 2⊕A 3 B 4=A 1⊕A 2⊕A 4 and outputting data B1, B2, B3 and B4.
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 4 m-bit data MI1=[A1, 00 . . . 0(2), A1, A1]; a step of transforming said in2 to 4 m-bit data MI2=[00 . . . 0(2), A2, A2, A2]; a step of transforming said in3 to 4 m-bit data MI3=[A3, A3, A3, 00 . . . 0(2)]; and a step of transforming said in4 to 4 m-bit data MI4=[A4, A4, 00 . . . 0(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]. 35. 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.
36. The recording medium as claimed in any one of claims 21, 22 or 23, wherein said n�n matrix is an 8�8 matrix.
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 8 m-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]. 40. The recording medium as claimed in claim 39, wherein said second linear transformation step is a key-dependent linear transformation step of inputting 8 m-bit key data k1 stored in said key storage means and performing an XOR operation by said key data k2 for obtaining said B.
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); intermediate value storage means for temporarily storing said each intermediate value Lj from said G-function means; and H-function means equipped with a partial information extracting function of generating N subkeys from a plurality of Lj and for storing them as said plural pieces of key data in said key storage means; wherein: 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. 42. The data transformation device as claimed in any one of claims 1, 2 or 3, which further comprises:
G-function means composed of M rounds means which are supplied with a master key K and generate intermediate values Lj+1j=0, 1, . . . , M−1); H-function means equipped with a partial information extracting function of generating subkeys from a plurality of Lj generated by said G-function means; and intermediate value storage means for storing outputs from said H-function means as values corresponding to said subkeys ki; wherein: 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, diffuses the inputs and outputs Lj+1, Yj+1 and vj+1; and 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. 43. The data transformation device as claimed in claim 41, wherein said G-function means comprises:
data splitting means for splitting the input Yj into two blocks (Yj L, Yj R) and for outputting Yj L as vj+1; XOR means for computing Yj R⊕vj from said Yj R and said vj; data diffusion means supplied with said Yj L 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 Yj R into Yj+1 L and said Lj+1 into Yj+1 R and for concatenating said Yj+1 L and said Yj+1 R into an output Yj+1=(Yj+1 L, Yj+1 R). 44. 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 (t j (1) , t j (2) , . . . , t j (2N))=L j(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 k i=(t 1 (i) , t 1 (N+i) , t 2 (i) , t 2 (N+i) , . . . , t M (i) , t M (N+i)) (i=1, 2, . . . , N). 45. 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 (t j (1) , t j (2) , . . . , t j (2N))=L j(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 k i=(t 1 (i) , t 1 (N+i) , t 2 (i) , t 2 (N+i) , . . . t M (i) , t M (N+i)) (i=1, 2, . . . , N). 46. The data transformation device as claimed in claim 41, 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 ( ( Y j ( 1 ) , Y j ( 2 ) , Y j ( 3 ) , v j ) → ( ( L j + 1 ( 1 ) , L j + 1 ( 2 ) , L j + 1 ( 3 ) , L j + 1 ( 4 ) ) , [ ( Y j + 1 ( 1 ) , Y j + 1 ( 2 ) , Y j + 1 ( 3 ) , Y j + 1 ( 4 ) ) , v j + 1 ] ) where: Y j + 1 ( i ) = f  ( Y j ( i ) ) (i=1, 2, 3, 4) L j + 1 ( 0 ) = v j L j + 1 ( i ) = f  ( L j + 1 ( i - 1 ) ) ⊕ Y j + 1 ( i ) (i=1, 2, 3, 4) v j + 1 = L j + 1 ( 4 ) ; and said H-function means is means for performing the following operation:
For ki=H(i, L1, L2, . . . , LM) q 4  i + j = L j + 1 ( i + 1 ) (i=0, 1, 2, 3, 4) (t i (0) , t i (1) , . . . , t i (7))=qi(i=0, 1, . . . , 31) k
(i=0, 1, . . . , N−1). 47. 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); intermediate value storage means for temporarily storing said each intermediate value Lj from said G-function means; and H-function means equipped with a partial information extracting function of generating N subkeys from a plurality of Lj; wherein: 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. 48. 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+1(j=0, 1, . . . , M−1); H-function means equipped with a partial information extracting function of generating subkeys from a plurality of Lj generated by said G-function means; and intermediate value storage means for storing outputs from said H-function means as values corresponding to said subkeys ki; wherein: 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, diffuses the inputs and outputs Lj+1, Yj+1 and vj+1; and 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. 49. The encryption key scheduling device as claimed in claim 47 or 48, wherein said G-function means comprises:
data splitting means for splitting the input Yj into two blocks (Yj L, Yj R) and for outputting Yj L as vj+1; XOR means for computing Yj R⊕vj from said Yj R and said vj; data diffusion means supplied with said Yj L 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 Yj R into Yj+1 L and said Lj+1 into Yj+1 R and for concatenating said Yj+1 L and said Yj+1 R into an output Yj+1=(Yj+1 L, Yj+1 R). 50. 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 (t j (1) , t j (2) , . . . , t j (2N))=L j (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 k i=(t 1 (i) , t 1 (N+i) , t 2 (i) , t 2 (N+i) , . . . , t M (i) , t M (N+i)) (i=1, 2, . . . ,N). 51. The encryption key scheduling device as claimed in claim 48, wherein said H-function means comprises:
bit splitting means for splitting said each Lj bitwise into (t j (1) , t j (2) , . . . , t j (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 k i=(t 1 (i) , t 1 (N+i) , t 2 (i) , t 2 (N+i) , . . . , t M (i) , t M (N+i)) (i=1, 2, . . . , N). 52. 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 ( ( Y j ( 1 ) , Y j ( 2 ) , Y j ( 3 ) ) , v j } → ( ( L j + 1 ( 1 ) , L j + 1 ( 2 ) , L j + 1 ( 3 ) , L j + 1 ( 4 ) , ) , [ ( Y j + 1 ( 1 ) , Y j + 1 ( 2 ) , Y j + 1 ( 3 ) , Y j + 1 ( 4 ) ) , v j + 1 ] ) where: Y j + 1 ( i ) = f  ( Y j ( i ) ) (i=1, 2, 3, 4) L
(i=1, 2, 3, 4) v j + 1 = L j + 1 ( 4 ) ; and said H-function means is means for performing the following operation:
For ki=H(i, L1, L2, . . . , LM) q 4  i + j = L j + 1 ( i + 1 ) (i=0, 1, 2, 3) ti (0) , t i (1) , . . . , t i (7))=q 1 (i=0, 1, . . . , 31) k
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 of storing said intermediate key Lj in a storage part; and a subkey generation process in which, upon storage of a part predetermined number of intermediate value L1 to LM in said intermediate value storage part a process in which information about bit positions of subkeys ki determined by i from said L1 to LM is extracted and said subkeys ki are generated. 54. 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 Li, information about the bit position of said Lj defined by i of said subkeys ki 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 a process in which, upon determination of the information about each bit position of each of said subkeys ki in said storage part, said subkey ki is output. Description
ΔX=X⊕X*, differential cryptanalysis aims to obtain the subkey k15 in the final round processing part 14 15 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 14 i for first and second plaintexts respectively. With the difference defined as mentioned above, the following equations hold.
⊕L*
⊕R*
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.
The above-mentioned second key-dependent linear transformation part 344 is configured to perform an exclusive OR operation of data between data processing routes 30 0, 30 1, 30 2 and 30 3 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 linear characteristic probabilities p, q. In this instance, a linear transformation part using the subkey ki1, which is contained in the second key-dependent linear transformation part 344, is added as a key-dependent transformation part 344B to the linear transformation part 344A determined by the matrix P as depicted in FIG. 7.
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: z i ′ = ⊕ j = 0 n - 1   t ij   z j . ( 1 ) 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: [ z 0 ′ z 1 ′ z 2 ′ z 3 ′ ] = [ 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 ]  [ z 0 z 1 z 2 z 3 ] . ( 2 ) 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�z 0⊕1�z 1⊕1�z 2⊕1�z 3 =z 1 ⊕z 2 ⊕z 3 (3-1)
z′ 1=1�z 0⊕0�z 1⊕1�z 2⊕1�z 3 =z 0 ⊕z 2 ⊕z 3 (3-2)
z′ 2=1�z 0⊕1�z 1⊕1�z 2⊕0�z 3 =z 0 ⊕z 1 ⊕z 2 (3-3)
z′ 3=1�z 0⊕1�z 1⊕1�z 2⊕1�z 3 =z 0 ⊕z 1 ⊕z 2 ⊕z 3 (3-4)
The elements of the n�n matrix P are determined by the following search algorithm taking the differential characteristic into account.
Theorem 1: Assume that an n�n matrix P over {0, 1} is given for the linear transformation part 344A. At this time, the relationship between input and output difference values Δz and Δz′ of the linear transformation part 344A (a difference path) is given by the matrix P, and the relationship between input and output mask values Γz and Γz′ (a mask value path) is given by a transposed matrix TP. That is,
Because of (See Appendix) 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. P E = [ 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 ] ⇔ P E T = [ 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 ] ( 6 ) It can be proven that nd=3 and n1=3 for the two matrices (see Appendix).
These linear transformation operations are equivalent to those in FIG. 7 given by Equations (7-1) to (7-4). In this way, the same pieces of data mid10, mid11, mid12 and mid13 as those in the first embodiment are generated. Incidentally, ki1 is composed of four pieces of data ki10, ki1, 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 345 0, 345 1, 345 2 and 345 3, 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.
The first embodiment depicted in FIG. 4 is an embodiment in which the basic linear transformation part 344A of FIG. 6, which constitutes the second key-dependent linear transformation part 344 of the nonlinear function part 304 (FIG. 5), is represented by a 4�4 matrix (that is, four inputs-four outputs). The fourth embodiment will be described below in connection with the case where the linear transformation part 344A is represented by an 8�8 matrix.
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.
For any two columns (columns a, b): n d0 = 2 + min ( a , b ) #  { ( t ia , t ib )  t ia ⊕ t ib ≠ 0 , 0 ≤ i ≤ 8 } For any three columns (columns a, b, c): n d1 = 3 + min ( a , b , c ) #  { ( t ia , t ib , t ic )  t ia ⊕ t ib ⊕ t ic ≠ 0 , 0 ≤ i ≤ 8 } n d2 = 3 + min ( a , b , c ) #  { ( t ia , t ib , t ic )  Exception of (0,0,0),(1,1,1), 0≦i≦8}
For any four columns (columns a, b, c, d): n d3 = 4 + min ( a , b , c , d ) #  { ( t ia , t ib , t ic , t id )  ( 0 , 0 , 0 , 1 ) , ( 0 , 0 , 1 , 0 ) , ( 1 , 0 , 0 , 0 ) ( 0 , 1 , 1 , 1 ) , ( 1 , 0 , 1 , 1 ) , ( 1 , 1 , 1 , 0 ) , 0 ≤ i < 8 } n d4 = 4 + min ( a , b , c , d ) #  { ( t ia , t ib , t ic , t id )  Exception of (0,0,0,0),(1,1,0,0),(0,1,1,1),(1,0,1,1), 0≦i<8} n d5 = 4 + min ( a , b , c , d ) #  { ( t ia , t ib , t ic , t id )  Exception of (0,0,0,0),(1,0,1,0),(0,1,1,1),(1,1,0,1), 0≦i<8} n d6 = 4 + min ( a , b , c , d ) #  { ( t ia , t ib , t ic , t id )  Exception of (0,0,0,0),(1,0,0,1),(0,1,1,1),(1,1,1,0), 0≦i<8} n d7 = 4 + min ( a , b , c , d ) #  { ( t ia , t ib , t ic , t id )  Exception of (0,0,0,0),(0,1,1,0),(1,0,1,1),(1,1,0,1), 0≦i<8} n d8 = 4 + min ( a , b , c , d ) #  { ( t ia , t ib , t ic , t id )  Exception of (0,0,0,0),(0,1,0,1),(1,0,1,1),(1,1,1,0), 0≦i<8} n d9 = 4 + min ( a , b , c , d ) #  { ( t ia , t ib , t ic , t id )  Exception of (0,0,0,0),(0,0,1,1),(1,1,0,1),(1,1,1,0), 0≦i<8}
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 through one of the XOR circuit. Accordingly, the linear transformation part 344A comprises a total of 16 XOR circuits. In this instance, the computational complexity is around (4�3�2�1)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. P = [ 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 ] ( 13 ) In FIG. 16 there is depicted an example of the construction of the linear transformation part 344A using this matrix, together with the nonlinear transformation parts 343 and 345. As shown, four transformation boxes B1 to B4 are alternately inserted in lines of four left and right routes from eight S-boxes forming the first linear transformation part 343, and consequently, two XOR circuits are inserted in each line.
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: T  P = [ 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 ] ( 14 ) 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.
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 linear transformation part 341 the data Ri is, for example, XORed with the key data ko 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 343 0′, 343 1′, 343 2′, . . . , 343 7′, respectively. The nonlinear transformation part 343 0′ is so designed as to transform the m-bit data in0 to the following 8�m-bit data.
and let the output be set as follows: ( ( Y j ( 1 ) , Y j ( 2 ) , Y j ( 3 ) , Y j ( 4 ) ) , v j ) → ( ( L j + 1 ( 1 ) , L j + 1 ( 2 ) , L j + 1 ( 3 ) , L j + 1 ( 4 ) ) , [ ( Y j + 1 ( 1 ) , Y j + 1 ( 2 ) , Y j + 1 ( 3 ) , Y j + 1 ( 4 ) ) , v j + 1 ] ) ( 35 ) Here, the following definitions are given. Y j + 1 ( i ) = f   ( Y j ( i ) )   ( i = 1 , 2 , 3 , 4 ) ( 36 ) L j + 1 ( 0 ) = v j ( 37 ) L j + 1 ( i ) = f   ( L j + 1 ( i - 1 ) ) ⊕ Y j + 1 ( i )   ( i = 1 , 2 , 3 , 4 ) ( 38 ) v j + 1 = L j + 1 ( 4 ) ( 39 ) Further, in
the following definitions are given. q i + 4  j = L j + 1 ( i + 1 )   ( i = 0 , 1 , 2 , 3 ) ( 41 ) ( t i ( 0 ) , t i ( 1 ) , …  , t i ( 7 ) ) = q i   ( i = 0 , 1 , …  , 31 ) ( 42 ) k ( i + 1 ) = ( t 0 + ( i   mod   2 ) ( [ i / 2 ] ) , t 2 + ( i   mod   2 ) ( [ i / 2 ] ) , …  , t 30 + ( i   mod   2 ) ( [ i / 2 ] ) )   ( i = 0 , 1 , …  , 15 ) ( 43 ) Suppose that [i/2] in Equation (43) represents └i/2┘.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4850019Nov 3, 1986Jul 18, 1989Nippon Telegraph And Telephone CorporationData randomization equipmentEP0719007A2Dec 21, 1995Jun 26, 1996Nec CorporationSmall size product cipher apparatusNon-Patent CitationsReference1A. Shimizu, et al., "Fast Data Encipherment Algorithm FEAL," Lecture Notes in Computer Science, vol. 304, (1987), p. 276-278.2Hikaru Morita et al: "FEAL-LSI and its Application" NTT Review, Telecommunications Association, Tokyo, JP, vol. 3, No. 6, Nov. 1, 1991, pp. 57-63, XP000270157 ISSN: 0915-2334.3M. Kanda, et al, A New 128-bit Block Cipher E2, Technical Report of IEICE, vol. 98, No. 227, (Sep. 30, 1998), p. 13-24 (ISEC98-12).4M. Kanda, et al. A round function structure consisting of few S-boxes (Part II), The 1998 Symposium on Cyptography and Information Security, (Jan. 28, 1998), 2.2.D, (in Japanese).5M. Kanda, et al., A round function structure consisting of few s-boxes (Part III), Technical Report of IEICE, vol. 98, No. 48, (May 15, 1998), p. 21-30 (ISEC98-3) (in Japanese).6M. Matsui, "New Structure of Block Ciphers with Provable Security Against Defferential and Linear Cryptanalysis," Lecture Notes in Computer Science, vol. 1039, (1996), p. 205-218.7Matsui M: "New Structure of Block Ciphers with Provaable Security Against Differential and Linear Cryptanalysis" Lecture Notes in Computer Science, Springer Verlag, New York, NY, US, vol. 1039, 1996, pp. 205-218,XP002914985 ISSN: 0302-9743.8V. Rijmen, et al., "The Cipher SHARK," Lecture Notes in Computer Science, vol. 1039, (1996), p. 99-111.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7054445 *Mar 28, 2001May 30, 2006Vdg, Inc.Authentication method and schemes for data integrity protectionUS7142671 *Jun 26, 2001Nov 28, 2006Broadcom CorporationMethods and apparatus for implementing a cryptography engineUS7305085 *Jun 29, 2001Dec 4, 2007Kabushiki Kaisha ToshibaEncryption apparatus and method, and decryption apparatus and method based on block encryptionUS7366300 *Jun 26, 2001Apr 29, 2008Broadcom CorporationMethods and apparatus for implementing a cryptography engineUS7502463 *Jun 26, 2001Mar 10, 2009Broadcom CorporationMethods and apparatus for implementing a cryptography engineUS7599490 *Mar 3, 2004Oct 6, 2009Harris CorporationMethod and apparatus for data encryptionUS7613295 *Feb 18, 2004Nov 3, 2009Harris CorporationCryptographic device and associated methodsUS7681245Aug 30, 2002Mar 16, 2010Avaya Inc.Remote feature activator feature extractionUS7698225Aug 30, 2002Apr 13, 2010Avaya Inc.License modes in call processingUS7707116Aug 30, 2002Apr 27, 2010Avaya Inc.Flexible license file feature controlsUS7707405Sep 21, 2004Apr 27, 2010Avaya Inc.Secure installation activationUS7747851Jun 29, 2010Avaya Inc.Certificate distribution via license filesUS7814023 *Sep 8, 2005Oct 12, 2010Avaya Inc.Secure download managerUS7844572Oct 30, 2007Nov 30, 2010Avaya Inc.Remote feature activator feature extractionUS7870399Feb 7, 2007Jan 11, 2011Arxan Defense SystemsSoftware trusted platform module and application security wrapperUS7885896Jul 9, 2002Feb 8, 2011Avaya Inc.Method for authorizing a substitute software license serverUS7890997Jan 20, 2003Feb 15, 2011Avaya Inc.Remote feature activation authentication file systemUS7913301Oct 30, 2006Mar 22, 2011Avaya Inc.Remote feature activation authentication file systemUS7966520Aug 30, 2002Jun 21, 2011Avaya Inc.Software licensing for spare processorsUS8036379 *Mar 15, 2006Oct 11, 2011Microsoft CorporationCryptographic processingUS8041642Jul 10, 2002Oct 18, 2011Avaya Inc.Predictive software license balancingUS8098816 *Jan 17, 2012Qualcomm IncorporatedApparatus and method for evaluating a cipher structure's resistance to cryptanalysisUS8165288 *Aug 29, 2007Apr 24, 2012Sony CorporationCryptographic processing apparatus and cryptographic processing method, and computer programUS8213607 *Oct 18, 2006Jul 3, 2012Qualcomm IncorporatedMethod for securely extending key stream to encrypt high-entropy dataUS8229858Feb 4, 2005Jul 24, 2012Avaya Inc.Generation of enterprise-wide licenses in a customer environmentUS8295478 *Jul 17, 2007Oct 23, 2012Sony CorporationCryptographic processing apparatus, algorithm constructing method, processing method, and computer program applying an extended feistel structureUS8437470 *Oct 5, 2006May 7, 2013Nds LimitedMethod and system for block cipher encryptionUS8619976 *Dec 11, 2008Dec 31, 2013Nec CorporationEncryption method, decryption method, device, and programUS8620819Oct 30, 2009Dec 31, 2013Avaya Inc.Remote feature activator feature extractionUS8687800 *Sep 29, 2006Apr 1, 2014Alcatel LucentEncryption method for message authenticationUS8731188Mar 30, 2012May 20, 2014Sony CorporationCryptographic processing apparatus and cryptographic processing method, and computer programUS8787568 *Aug 29, 2007Jul 22, 2014Sony CorporationData transformation apparatus, data transformation method, and computer programUS8995666 *Mar 21, 2012Mar 31, 2015Kabushiki Kaisha ToshibaKey scheduling device and key scheduling methodUS20010046292 *Mar 28, 2001Nov 29, 2001Gligor Virgil DorinAuthentication method and schemes for data integrity protectionUS20020016773 *Jun 29, 2001Feb 7, 2002Kenji OhkumaEncryption apparatus and method, and decryption apparatus and method based on block encryptionUS20020021801 *Mar 21, 2001Feb 21, 2002Takeshi ShimoyamaComputing apparatus using an SPN structure in an F function and a computation method thereofUS20020106078 *Jun 26, 2001Aug 8, 2002Broadcom CorporationMethods and apparatus for implementing a cryptography engineUS20020106080 *Jun 26, 2001Aug 8, 2002Broadcom CorporationMethods and apparatus for implementing a cryptography engineUS20020108048 *Jun 26, 2001Aug 8, 2002Broadcom CorporationMethods and apparatus for implementing a cryptography engineUS20020116624 *Jan 28, 2002Aug 22, 2002International Business Machines CorporationEmbedded cryptographic systemUS20040044629 *Aug 30, 2002Mar 4, 2004Rhodes James E.License modes in call processingUS20040054930 *Aug 30, 2002Mar 18, 2004Walker William T.Flexible license file feature controlsUS20050180565 *Feb 18, 2004Aug 18, 2005Harris CorporationCryptographic device and associated methodsUS20050195974 *Mar 3, 2004Sep 8, 2005Harris Corporation, Corporation Of The State Of DelawareMethod and apparatus for data encryptionUS20070094710 *Oct 30, 2006Apr 26, 2007Avaya Technology Corp.Remote feature activation authentication file systemUS20070192864 *Feb 7, 2007Aug 16, 2007Bryant Eric DSoftware root of trustUS20070237324 *Mar 15, 2006Oct 11, 2007Microsoft CorporationCryptographic processingUS20080095370 *Oct 18, 2006Apr 24, 2008Rose Gregory GMethod for securely extending key stream to encrypt high-entropy dataUS20080137837 *Sep 29, 2006Jun 12, 2008Sarvar PatelEncryption method for message authenticationUS20090052656 *Oct 5, 2006Feb 26, 2009Nds LimitedMethod and System for Block Cipher EncryptionUS20100002872 *Aug 29, 2007Jan 7, 2010Kyoji ShibutaniData transformation apparatus, data transformation method, and computer programUS20100014659 *Aug 29, 2007Jan 21, 2010Kyoji ShibutaniCryptographic processing apparatus and cryptographic processing method, and computer programUS20100061548 *Jul 17, 2007Mar 11, 2010Taizo ShiraiCryptographic processing apparatus, cryptographic-processing-algorithm constructing method, and cryptographic processing method, and computer programUS20100098242 *Oct 17, 2008Apr 22, 2010Qualcomm IncorporatedApparatus and method for evaluating a cipher structure's resistance to cryptanalysisUS20100266122 *Dec 11, 2008Oct 21, 2010Nec CorporationEncryption method, decryption method, device, and programUS20120079462 *Feb 1, 2011Mar 29, 2012SoftKrypt LLCSystems and methods of source software code obfuscationUS20120237035 *Sep 20, 2012Kabushiki Kaisha ToshibaKey scheduling device and key scheduling method* Cited by examinerClassifications U.S. Classification713/193, 380/29International ClassificationH04L9/06Cooperative ClassificationH04L2209/24, H04L9/002, H04L9/0625, H04L2209/12European ClassificationH04L9/06RLegal EventsDateCodeEventDescriptionJul 25, 2000ASAssignmentOwner name: NIPPON TELEGRAPH AND TELEPHONE CORPORATION, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:KANDA, MASAYUKI;TAKASHIMA, YOUICHI;AOKI, KAZUMARO;AND OTHERS;REEL/FRAME:011010/0447Effective date: 20000711Sep 7, 2004CCCertificate of correctionNov 5, 2007FPAYFee paymentYear of fee payment: 4Sep 21, 2011FPAYFee paymentYear of fee payment: 8RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services