Note: Descriptions are shown in the official language in which they were submitted.
CA 02421142 2003-03-20
-2-
DATA TRANSFORMATION DEVICE
AND RECORDING MEDIUM HAVING RECORDED THEREON
A PROGRAM FOR IMPLEMENTING THE SAME
This is a division of copending Canadian Patent Application Serial
No. 2,319,135 filed January 27, 1999 from PCT/JP99/00337 filed
January 27, 1999.
TECHNICAL FIELD
The present invention relates to a transformation device that is used
in a cryptographic device for concealing data in data communication or
storage and, more particularly, to a data transformation device suitable for
use in an encryption device of a secret-key encryption algorithm which
encrypts or decrypts data blocks using a secret key, and a recording medium
on which there is recorded a program for execution by the data
transformation device.
PRIOR ART
With a view to constructing a fast and secure secret-key encryption
algorithm, a block cipher is used according to which data for encryption is
split into blocks of a suitable length and encrypted for each block. Usually,
the block cipher comprises a data diffusion part which randomizes input data
to be encrypted, and a key scheduling part which is supplied with a secret
common key (hereinafter referred to as a master key) input to the encryption
device and generates a sequence of subkeys for use by the data diffusion
part. A typical secret-key encryption algorithm, which is used in the data
transformation device to conceal data, is DES (Data Encryption Standard)
that was FIPS-approved algorithm for encryption.
CA 02421142 2003-03-20
-3-
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 Lo and Ro. The block data
R« is input to a function operation part (referred to also as a round
function)
12 which is a data transformation part shown as an i-th round processing part
14; (i = 0, 1, ..., 15) in Fig. 2, wherein it is transformed to f(R0, k0)
using a
I 0 48-bit subkey ko. The thus transformed data f(R0, k0) and the block data
Lo
are exclusive ORed in an XOR circuit 13, and its output and the block data
R0 are swapped to obtain the next block data L~, R~. That is,
R~ = Lo ~ f(Ro~ ko)
L, = R0
where O+ 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
L, and R,; similar round processing parts 14, to 14,5 are provided in cascade.
The processing by the i-th round processing part 14; will hereinafter be
referred to as i-th processing, where i = 0, 1, ..., 15. That is, each round
processing part 14; (where 0 _< i <_ 15) performs the following processing
R,+1 = L; D f(R;, k;)
L.+ ~ = R.
And finally concatenation two pieces of data R,6 and L,6 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.
CA 02421142 2003-10-27
-4-
The decryption process can be executed following the same
procedure as that for the encryption process except inputting subkeys k0, k~,
..., k,4, kls to the function f (the function operation part 12) in the order
k~s,
k~4, ..., k~, k0 which is reverse to that in the encryption process. In such
an
instance, the outputs L~6 and R~6 from the final round processing part 14~s
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 expansion key
generation part 21: splits a master key of 64 bits, except 8 bits used for
parity, into two pieces of 28-bit right and left key data; then performs 16-
round swapping of the two pieces of 28-bit right and left key data; and
performs reduced permutation of the permuted right and left data (a total of
56 bits) provided from the respective rounds to generate 16 48-bits subkeys
ko, k1, ..., k14, kis 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 R; is transformed to
48-bit data E(R;) in an expanded permutation part 17. This output data and
the subkey k; are exclusive ORed in an XOR circuit 18, whose output is
transformed to 48-bit data E(R;)O+k;, 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 So to S~ to derive therefrom a 4-bit output, respectively.
Incidentally, the S-box S~ (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 So to S~ are concatenated again to 32-bit data, which is
CA 02421142 2003-03-20
-5-
applied to a permutation part 19 to provide the output f(R;, k;) from the
function operation part 12 as shown in Fig. 2. This output is exclusive ORed
with L; to obtain R;.,., .
Next, a description will be given of cryptanalysis techniques. A
variety of cryptanalysis techniques have been proposed for DES and other
traditional secret-key encryption algorithms; extremely effective
cryptanalysis techniques among them are differential cryptanalysis proposed
by E. Biham and A. Shmir, ("Differential Cryptanalysis of DES-like
Cryptosystems," Journal of Cryptology, Vol. 4, No. 1, pp.3-72) and linear
cryptanalysis proposed by Matsui, ( "Linear Cryptanalysis Method for DES
cipher," Advances in Cryptology-EUROCRYPT' 93 (Lecture Notes in
Computer Science 765), pp. 386-397.)
Assuming that a difference between two pieces of data X and X* is
defined as
0X=XO+X*,
differential cryptanalysis aims to obtain the subkey k, 5 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 (L;, R;) and (L*;, R*;) represent input data into the round
processing part 14; for first and second plaintexts respectively. With the
difference defined as mentioned above, the following equations hold.
0L; = L; O+ L*;
0R; = R; O+ R*;
In Fig. 1, since Lis = R,4, L*,5 = R*,4, L,6 = R,5 and L*,6 = R*,5, the
following equations hold
R~6 = Las ~ f~R~s~ kIS)
R*~6 = L*~5 ~ f(R*~s~ kis)
CA 02421142 2003-03-20
-6-
and the exclusive OR of both sides of these two equations is obtained as
follows:
OR,6 = OL,S O+ f(L~6~ kis) ~ f(Li6~OL,6~ kis).
The exclusive ORing of its both sides with OR,~ = OL,S gives the following
equation:
f(L~6~ kis) ~ f(Li60Li6~ ki;) = ORn ~ ~R,4.
At this time, since L,6, OL,6 and ~R,~ are data available from the ciphertext,
they are known information. Hence, if the attacker can correctly obtain
OR,4, then only k,5 in the above equation is an unknown constant; the
attacker can find a correct k, 5 without fail by an exhaustive search for k, 5
using the known sets of plaintext-ciphertext pair. Accordingly, once the
subkey k,5 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 OR,4
since this value is an intermediate difference value. Then, assume that each
round processing is approximated by the following equations with a
probability p; in the 0-th to the last round but one (i.e.; the 14-th):
OR;+, = 0L; O+ 4{f(OR;)}
DL;+~ = 0R;+,.
The point is that, when certain 0R; is input to the i-th round processing
part,
0 { f(4R;) } can be predicted with the probability p; regardless of the value
of
the subkey k;. 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 So, 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
CA 02421142 2003-03-20
-7-
each capable of predicting the relationship between the input difference and
the output difference with a probability Ps; and by combining them.
Furthermore, the concatenation of such approximations in the respective
rounds makes it possible to obtain OR,4 from ~L,~ and ~R~ (~Lo and ORo are
data derivable from the plaintext, and hence they are known) with a
probability P = Tj;_o'3p;. Incidentally, the higher the probability P, the
easier
the cryptanalysis. After the subkey k,s is thus obtained, a similar
calculation
is made of the subkey k~,~ regarding it as a 15-round DES that is one round
fewer than in the above; such operations are repeated to obtain the subkeys
one by one to ko.
It depends on the probability P whether this cryptanalysis succeeds;
the higher the probability P, the more likely the success. Biham et al. say
that DES could be broken by this cryptanalysis if 2'" sets of chosen
plaintext-ciphertext pair are available.
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.
(Lo~ Ro) r (Lo~ Ro) ~ (L~6~ R~6) r (L~6~ Rn)
= (ko, ki, ..., k,s) T (ko, k~, ..., k,s)
where r(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
CA 02421142 2003-03-20
_g_
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
(ko, k,, ..., k,5) r (ko, k1, ..., k,5) (one bit)
from information
(Lo~ Ro) r (Lo~ Ro) ~ (L~6~ Rib) r (Li6~ R~6).
At this time, (Lo, Ro) and (L,6, R,h) are the plaintext and the ciphertext,
respectively, and hence they are known. For this reason, if the attacker can
correctly obtain I-' (Lo, Ro), T (L,6, R,~) and r (ko, k,, ..., k~5), then he
can
obtain (ko, k~, ..., k,5) T (ko, k,, ..., k,5) (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 ps;. 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 ps;. 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 p;, and by concatenating the linear representations of
the respective rounds,
r (Lo, Ro), r (L,6, R,6) and r (ko, k~, ..., k,5) are obtained wit the
following
probability:
P = 1 /2 + 2 ~' ~;-o' S ~ p; - 1 /2 ~ .
CA 02421142 2003-03-20
-9-
The higher the probability P, the easier the cryptanalysis.
According to Matsui, he has succeeded in the analysis of DES by this
cryptanalysis using 243 sets of known plaintext-ciphertext pair.
To protect ciphers against the above cryptanalysis techniques, the
probability P needs only to be reduced to be sufficiently small. A wide
variety of proposals have been made to lessen the probability P, and the
easiest way to provide increased security in the conventional cryptosystems
is to increase the number of rounds. For example, Triple-DES with three
DESs concatenated is an algorithm that essentially increases the number of
rounds from 16 to 48, and it provides a far smaller probability P than does
DES.
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 master 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
CA 02421142 2003-03-20
-10-
correspondence between the subkeys and the master 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 master
key by data diffusion parts (f;), therefore it is expected that the master 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 expansion key generation part 21 comprises N/2
(N = 16, for example) rounds of key processing parts 21o to 21N,2_, which
have key diffusion parts 22o to 22,"2_,, respectively. The key processing
parts
21_; (where j = 0, l, ..., N/2-1) each perform diffusion processing of two
pieces of 32-bit right and left key data, and interchange them to provide two
pieces of right and left key data for input to the next-round key processing
part 21~+~. The key processing parts 21~, except the first round, each have an
exclusive OR part 23_;, which calculates the exclusive OR of the left input
key data to the key processing part 21.;_, of the preceding round and the left
output key data therefrom and provides the calculated data to the key
diffusion part 22~. The left input key data of the key processing part 21; is
diffused by the output from the exclusive OR part 23~ in the key diffusion
part 22,;, from which the diffused data is output as right key data for input
to
the next round, and the right input key data of the key processing part 21_;
is
output as left key data for input to the next round. The output from each key
diffusion part 22; is bit-split into two subkeys Q2~ and QZ_;+i (that is, k;
and
k;+, ), which are provided to the corresponding (i = 2,;)-th round processing
part and (i+1 = 2j+1)-th round processing part in Fig. 1.
CA 02421142 2003-03-20
-11-
The 64-bit master key is split into two pieces of 32-bit right and left
key data, then in the first-round key processing part 21 o the left key data
is
diffused by the right key data in the key diffusion part 22o to obtain
diffused
left key data, and this diffused left key data and the right key data are
interchanged and provided as right and left key data next to the key
processing part 21, . The outputs from the key diffusion parts 22o to 22N,a-~
of the key processing parts 21,~ to 21Ni2-i are applied as subkeys ko to kN_~
to
the corresponding round processing parts 14o to 14~;_, of the data diffusion
part 10 depicted in Fig. 1.
In the expansion key generation part 21 of Fig. 3, however, each key
diffusion part 22,; is a function for generating a pair of key data (subkeys
QZ_;,
Q2~+,) 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 (Q2~_2 and Q2~_, ),
(Q2; and Q2~+~), (QZ_;+~ and Q2,;+3) are known, since the output (subkeys
Q2~+~
and Q~~+3) from the (j+1 )-th key diffusion part 22~+, and the one input data
(subkeys Q2_;_2 and Q2~_~) thereto are known, the other input data (i.e., the
output data from the exclusive OR part 23,;+,) can be obtained; and it is
possible to derive, from the thus obtained data and the subkeys Q2~ and Q2_;+~
which constitute the one input data to the exclusive OR part 23~+,, the input
data to the preceding (j-th) key diffusion part 22~ which constitute the other
input data to the exclusive OR part 23_;+,, that is, the subkeys Q2~_a and
Q2.~_3
which constitute the output from the three-round-preceding ((j-2)-th) key
diffusion part 22_x_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
CA 02421142 2003-03-20
-12-
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_, are easy to obtain by differential
and linear cryptanalysis. By analyzing the key data in the expansion key
scheduling part 21 as described above using the obtained subkeys, there is
the possibility of obtaining all the subkeys concerned.
A first object of the present invention is to provide a data
transformation device in which the round function f (the function operation
part) is so configured as to simultaneously meet the requirements of security
and speedup to thereby ensure security and permit fast encryption processing
without involving a substantial increases in the number of rounds, and a
recording medium having recorded thereon a program for implementing the
data transformation.
A second object of the present invention is to implement a key
scheduling part which does not allow ease in determining other subkeys and
the master key by a mere analysis of the key scheduling part even if some of
the subkeys are known.
DISCLOSURE OF THE INVENTION
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
CA 02421142 2003-03-20
-13-
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 x n matrix.
According to the present invention, it is guaranteed that when the
differential probability/linear probability in the first and second nonlinear
transformation parts is p (< 1), the differential probability/linear
probability
of approximating each round is p; <_ 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 linear cryptanalysis). And when the function f is objective, if
the
number of rounds of the cryptographic device is set at 3r, then the
probability of the cipher becomes P 5 p;2~ < pa~. Furthermore, if the second
key-dependent linear transformation part in the case of n = 4, in particular,
has a configuration that exclusive ORs combination of three of four pieces of
subdata with one of four pieces of key data, the probability of approximating
each round is p; _< p4 and the probability of the cipher is P <_ p;2' <_ per.
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
CA 02421142 2003-03-20
-14-
approximating each round is p; <_ p' and the probability of the cipher is
P~p2r~plor.
Moreover, the first and second nonlinear transformation parts are
arranged so that their processing can be performed completely in parallel --
this contributes to speedup.
It is possible, therefore, to construct a fast and source nonlinear
function against differential and linear cryptanalysis, and to permit the
implementation of a data transformation device which copes with both
security and speedup.
To attain the second object of the present invention, the key
scheduling part is provided with: a G-function parts which perform the same
function as that of the key diffusion part (the function fk), L components
which are output from the G-function parts being once stored in a storage
part; and an H-function part which reads out a required number of L
components from the storage part and generates subkeys by extracting the
respective L components as uniformly as possible. Furthermore, in the
H-function part partial information, which is used as subkeys, is extracted
from the L components which are outputs from the G-function parts, then the
extracted information is stored in a storage part, and the subkeys are
generated by extracting the partial information from the required number of
L components.
In accordance with one aspect of the present invention there is
provided 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 L~
( j = 0, 1, . . . , M-1 ); intermediate value storage means for temporarily
storing
said each intermediate value L~ from said G-function means; and H-function
CA 02421142 2003-03-20
-15-
means equipped with a partial information extracting function of generating
N subkeys from a plurality of L;; wherein: said G-function means takes said
master key as at least one part of Y~, inputs Y; and v_; in the output (L;,
Y,;, v,;)
from the j-th round, into its (j+1)-th round (where j = 0, 1, ..., M-1)
diffuses
the inputs and outputs L_;+,, Y;+, and v.;+~; and said H-function means inputs
i
(where i = 1, 2, ..., N) and L~, L2, ..., LM stored in said intermediate value
storage means, extracts information about bit positions of subkeys k;
determined by said i from said L,, ..., L~,, and outputs said subkeys.
In accordance with another aspect of the present invention there is
provided 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
L~+~ (j = 0, 1, ..., M-1); H-function means equipped with a partial
information extracting function of generating subkeys from a plurality of L;
generated by said G-function means; and intermediate value storage means
for storing outputs from said ~-I-function means as values corresponding to
said subkeys k;; wherein: said G-function means takes said master key as at
least one part of Yo, inputs Y; and v_; in the output (L~, Y.;, v~) from the j-
th
round, into its (j+1)-th round, diffuses the inputs and outputs L.;+1, Y;+,
and
v~+,; and said H-function means inputs i, q and L_; ( 1 <_ i <_ N, 1 <_ j <_
M, 1 S q
<_ the numbers of bits k;), and extracts bit position information defined by
i and q from L.; to provide information about the bit position q of the
subkeys k;.
In accordance with yet another aspect of the present invention there
is provided 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 k; (i = 1, ...,
N),
CA 02421142 2003-03-20
-16-
said program comprising: an intermediate key generation process in which
said master key K as Yo and a constant vo are input, diffusion processing of
said inputs is repeated in cascade a plurality of times and an intermediate
value L,~ (j = 1, 2, ..., M) is output for each diffusion processing; a
process of
storing said intermediate key L~ in a storage part; and a subkey generation
process in which, upon storage of a part predetermined number of
intermediate value L, to Ln,, in said intermediate value storage part a
process
in which information about bit positions of subkeys k; determined by i from
said L, to LM is extracted and said subkeys k; are generated.
In accordance with still yet another aspect of the present invention
there is provided 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 k;
(i = 1, ..., N), said program comprising: an intermediate key generation
process in which said master key K as Y~ and a constant v~ are input,
diffusion processing of said inputs is repeated in cascade a plurality of
times
and an intermediate value L~ (j = l, 2, ..., M) is output for each diffusion
processing; a process in which, upon each generation of said intermediate
value L~, information about the bit position of said L~ defined by i of said
subkeys k; and the bit position q of said k; is extracted as bit position
information for said k; 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 k; in said storage part, said subkey k; is
output.
CA 02421142 2003-10-27
-1 /-
BRIEF DESCRIPTION OF THE DRAWINGS
Fig. 1 is a diagram depicting the functional configuration of a
conventional DES cryptographic device.
Fig. 2 is a diagram depicting a concrete functional configuration of a
function operation part 12 in Fig. 1.
Fig. 3 is a diagram depicting an example of an expansion key
generation part 21 in Fig. 2.
Fig. 4 is a diagram illustrating the functional configuration of the first
embodiment of the present invention.
Fig. 5 is a diagram showing in detail an example of the functional
configuration of a nonlinear function part 304 in the first embodiment.
Fig. 6 is a diagram showing a basic configuration of a nonlinear
function part for determining an optimal linear transformation part in Fig. 5.
Fig. 7 is a diagram depicting a concrete example of the second key-
dependent linear transformation part 344 in Fig. 5.
Fig. 8A is a diagram depicting an equivalent functional configuration
of a nonlinear transformation part 3430' in the second embodiment.
Fig. 8B is a diagram depicting an equivalent functional configuration
of a nonlinear transformation part 343,' in the second embodiment.
Fig. 8C is a diagram depicting an equivalent functional configuration
of a nonlinear transformation part 3432' in the second embodiment.
Fig. 8D is a diagram depicting an equivalent functional configuration
of a nonlinear transformation part 3433' in the second embodiment.
Fig. 9 is a diagram showing the functional configuration of a second
key-dependent linear transformation part 344 in the second embodiment.
Fig. 10 is a diagram showing the functional configuration of a
nonlinear function part 3430(3450) in the third embodiment.
CA 02421142 2003-10-27
-18-
Fig. 11 is a flowchart showing the procedure for implementing a data
transformation by a computer.
Fig. 12 is a flowchart showing in detail the procedure of step S3 in
Fig. 11.
Fig. 13 is a diagram depicting the functional configuration of the
fourth embodiment of the present invention.
Fig. 14 is a diagram depicting the functional configuration of a
nonlinear function part 304 in Fig. 13.
Fig. 15A is a diagram depicting a linear transformation part 334A of a
limited structure intended to reduce the computational complexity involved
in search.
Fig. 15B is a diagram depicting an example of configuration of one
transformation box in Fig. 15A.
Fig. 16 is a diagram depicting an example of the configuration of a
linear transformation part 344A determined by the search algorithm.
Fig. 17 is a diagram depicting an example of the functional
configuration of a second key-dependent linear transformation part 344 in
Fig. 14 in the fourth embodiment.
Fig. 18 is a diagram depicting another example of the functional
configuration of a second key-dependent linear transformation part 344 in
Fig. 14 in the fourth embodiment.
Fig. 19 is a diagram depicting still another example of the functional
configuration of a second key-dependent linear transformation part 344 in
Fig. 14 in the fourth embodiment.
Fig. 20A is a diagram illustrating the functional configuration of a
nonlinear transformation part 3430' in the fifth embodiment.
CA 02421142 2003-10-27
-19-
Fig. 20B is a diagram illustrating the functional configuration of a
nonlinear transformation part 343'.
Fig. 20C is a diagram illustrating the functional configuration of a
nonlinear transformation part 343'.
Fig. 21 is a diagram showing the functional configuration of a second
key-dependent linear transformation part 344 in the fifth embodiment.
Fig. 22 is a diagram showing a configuration for executing a data
processing program recorded on a recording medium.
Fig. 23A is a block diagram depicting the basic functional
configuration of a key generation part according to the present invention.
Fig. 23B is a block diagram depicting the basic functional
configuration of another key generation part according to the present
invention.
Fig. 24 is a block diagram depicting an example of the functional
configuration of an intermediate key generation part 220 in Fig. 23A or 23B.
Fig. 25 is a block diagram depicting the functional configuration of a
G-functional part in Fig. 24 when the present invention is applied to a key
scheduling part in Fig. 3.
Fig. 26 is a block diagram depicting the functional configuration of a
subkey generation part 240 in Fig. 23A when the present invention is applied
to a key scheduling part in Fig. 3.
Fig. 27 is a block diagram depicting an example of the functional
configuration of a subkey generation part 250 in Fig. 23B when the present
invention is applied to a key scheduling part in Fig. 3 (In this embodiment
the subkey generation part contains an H-function part equipped with a bit
extraction function).
CA 02421142 2003-03-20
-20-
Fig. 28 is a block diagram depicting the functional configuration of
the G-function part 22 designed for the application of the present invention
to a Feistel cipher which uses 128 bits as one block.
BEST MODE FOR CARRYING OUT THE INVENTION
First Embodiment
An embodiment of the present invention will be described below
with reference to the accompanying drawings.
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 38o to 38N_i which
sequentially perform round processing of left and right pieces of data after
input data is split into left and right pieces Lo, Ro; each round processing
part
38; (where i = 0, 1, ..., N-I) 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.
Input data M, which corresponds to a plaintext, is entered into the
cryptographic device via an input part 301. The key scheduling part 20
comprises a key input part 320, a expansion key generation part 321 and a
key storage part 322. Based on input data (a master key K) from the key
input part 320, the expansion key generation part 321 generates plural pieces
of key data (subkeys)
{~.~ kook koa k~o~ km kl2o ...; k(N_,)o~ k(N-1>1~ k(N-1)2p ~'~k~
CA 02421142 2003-03-20
-21-
which are stored in the key storage part 322. The input data M is
transformed in a key-dependent initial transformation part 302 with the key
data flc stored in the key storage part 322, thereafter being split in an
initial
splitting part 303 into two pieces of left and right block data Lo and Ro. For
example, 64-bit data is split into two pieces of 32-bit block data Lo and Ra.
The key-dependent initial transformation part 302 performs a linear
transformation such as exclusive ORing of the key data fk and the input data
M or bit rotation of the input data M by the key data flc, or nonlinear
transformation by a combination of multiplications.
The right block data R~ is provided to the nonlinear function part 304
which is characteristic of the present invention, together with the key data
k~o, ko~ and ko2 stored in the key storage part 322, and in the nonlinear
function part 304 the right block data is nonlinearly transformed to data Y«.
The data Yo and the left block data L~ are transformed to data L~* through a
1 S linear operation in the linear operation part 305. The data L~* and the
data
R~ are swapped in the swapping part 306 to provide L;E-R~, R,f--L~*; and
these pieces of data L, and R~ are input to the next first round processing
part 38~.
Thereafter, in an i-th round processing parts 38; (where i = 0, l, ...,
N- I ) the same processing as mentioned above is repeated for two pieces of
input block data L; and R;. That is, the right block data R; is input to the
nonlinear function part 304 together with the key data k;o, k;, and k;2, and
in
the nonlinear function part 304 it is nonlinearly transformed to data Y;. The
data Y; and the data L; are transformed to data L;* by a linear operation in
the
linear operation part 305. The data L;* and the data R; are swapped in data
position in the swapping part 306, that is, L;+~E-R;, R;+~f--L;*. The
CA 02421142 2003-03-20
-22-
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 L~, and RN are obtained as the result of such repeated
processing by the round processing parts 38o to 38N_,. 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_m, k~N-m, k(N_I)2~ ..., k~o, k», kiz, koo, kon
ko2~ ~.
Next, a detailed description will be given of the internal
configuration of the nonlinear function part 304. Fig. 5 is a diagrammatic
showing of the internal functional configuration of the nonlinear function
part 304.
The input block data R; to the i-th round processing part 38;
constitutes input data to the nonlinear function part 304, together with the
key data k;o, k;,, k;2 stored in the key storage part 322. The block data R;
is
subjected to, for example, exclusive ORing with the key data k;o in a first
CA 02421142 2003-03-20
-23-
key-dependent linear transformation part 341, by which it is linearly
transformed to data R;* = R;O+k;o. Next, the thus transformed data R;* is
split
into four pieces of, for instance, 8-bit data ino, in,, in2 and in3 in a
splitting
part 342. The four pieces of data in~~, in,, in2 and in3 are nonlinearly
transformed to four pieces of data mid~o, mido,, mid~2 and mido3 in nonlinear
transformation parts 343, 343 ~, 3432 and 3433, respectively, from which they
are input to a second key-dependent linear transformation part 344.
The second key-dependent linear transformation part 344 performs
linear transformation (XORing) among the pieces of input data mido~, mido,,
mido2 and mido3 from four routes to provide new data of four routes, and
further performs linear transformation (XORing) among these pieces of data
of the four routes with four pieces of the key data k;~ to provide output data
mid,, mid, ~, mid,2 and mid,3 of the four routes. The four pieces of data are
input to nonlinear transformation parts 3450, 345,, 3452 and 3453, wherein
they are transformed to data onto, out,, out2 and out3, respectively. These
four pieces of data are combined into data Y;* in a combining part 346;
furthermore, in a third key-dependent linear transformation part 347 the
data Y;* undergoes a linear operation with the key data k;2 to generate output
data Y;.
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, 30,, 302 and 303 provided corresponding to the
pieces of data midoQ, mido~, mid~2 and mido3, 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
CA 02421142 2003-03-20
-24-
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 x n matrix P over {0, 1 }, and the optimal linear transformation
part 344A is constructed by determining elements of the matrix P in such a
manner as to minimize the maximum differential and linear characteristic
probabilities p, q. In this instance, a linear transformation part using the
subkey k;,, 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.
Incidentally, what is intended to mean by the word "optimal" is to
provide the highest resistance to differential and linear cryptanalysis in the
linear transformation part 344A of the above configuration, but it does not
necessarily mean the optimum for other criteria, for example, an avalanche
property. Empirically speaking, however, attacks other than differential and
linear cryptanalysis can easily be avoided by only increasing the number of
rounds, while it is not certain whether only some increase in the number of
rounds serves to prevent differential and linear cryptanalysis unless a
careful
CA 02421142 2003-03-20
-25-
study is made of the round function used. In view of this, the present
invention attaches the most importance to the resistance of the round
function to differential and linear cryptanalysis and constructs the optimal
linear transformation part 344A accordingly.
According to the present invention, the linear transformation part
344A in Fig. 6 is represented as the n x n matrix P over f 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:
n-I
z';=Qt;;Z.,. (1)
=o
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 x 4 matrix PE will be
described which is expressed by the following equation:
z'~ 0 1 1 1 z~
z'1 1 0 1 1 z1
z'2 1 1 1 0 zz (2)
z'; 1 1 1 1 z3
The round function using the matrix PE has the following features. Let it be
assumed, however, that the S-box is bijective. z'o, z',, z'2 and z'3 defined
by
the above matrix represent the following operations, respectively.
z'« = O~z~O+ 1 ~z,0+ 1 ~z2+O 1 ~z3 = z,Oz20+z~ (3-1 )
z', = 1 ~zo0+O~z,O+ 1 ~z2+O 1 ~z3 = z~0+z20+z3 (3-2)
z'2= l~zo0+1~z,0+1~Z2OOO~Z3=zo0+z~0+z2 (3-3)
z'3 = 1 ~zo0+ 1 ~zl +O 1 ~z2+O1 ~z3 = zo0+z~0+z~0+z3 (3-4)
CA 02421142 2003-10-27
-26-
The resistance of the round function to differential and linear
cryptanalysis can be determined by the smallest numbers nd, n, of active
s-boxes, and these values are those determined at the time of determining the
matrix P. In differential cryptanalysis an s-box whose input difference value
Ox is nonzero is called an active s-box, and in linear cryptanalysis an s-box
whose output mask value ry is nonzero is called an active box.
In general, when given a certain matrix P, there exist a plurality of
constructions of the linear transformation part 344A corresponding thereto.
This is because the matrix P represents only the relationship between input
and output data of the linear transformation part 344A and does not define its
concrete construction. That is, if it is common in the matrix P which
represents the relationship between their input and output data, linear
transformation parts can be considered to have the same characteristic
regardless of their individual constructions. Accordingly, in the following
description, the matrix P is determined first which provides high
invulnerability against differential and linear cryptanalysis and good
avalanche effect, followed by determining the construction of the linear
transformation part 344A. This method is more effective in finding out a
linear transformation part 344A of an optimal characteristic than a method of
checking individual constructions of linear transformation parts to see if
they
have the optical characteristic.
The elements of the n x 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).
CA 02421142 2003-10-27
-27-
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: Select a subset P~ of n column vectors from the set C. Repeat
the following steps until all subsets have been checked.
Step 3-1: Compute nd for the subset P~ of n column vectors. This is
represented as nd(P~).
Step 3-2: If nd(P~) >- T, then accept a matrix P~ consisting of the n
column vectors as a candidate matrix.
Step 4: Output matrices P and a value na(P) that yields the maximum
value of nd among all candidate matrices.
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(P~) >_ T obtained by performing steps up to 3-2 may be used
as the desired matrix P. Alternatively, the matrix Pc composed of n vectors
whose Hamming weights are equal to or larger than T-1 selected in step 2
after step 1 may be used as the matrix P.
The input mask values of the linear transformation part 344A can be
represented by exclusive ORs of its output mask values, and hence they can
be expressed by a certain matrix as is the case with differential
characteristic.
As the result of our checking the relationship between the matrix for
differential characteristic and the matrix for linear expression in several
linear transformation parts of different constructions, the following theorem
CA 02421142 2003-10-27
-28-
were made.
Theorem 1: Assume that an n x 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 0z and 0z' of the linear transformation part
344A (a difference path) is given by the matrix P, and the relationship
between input and output mask values Tz and rz' (a mask value path) is
given by a transposed matrix TP. That is,
Oz' = POz (4)
Tz = TPhz'. (5)
The following is an algorithm for determining the construction of the
linear transformation part 344A when given the matrix P Here, the
following conditions are to be met.
( 1 ) Minimization of the number of exclusive ORs (XORs), or
(2) Repeated appearance of the similar subconstruction.
CA 02421142 2003-03-20
-29-
Step 1: In the matrix P, choose two rows and XOR the one row
(row a) with the other row (row b) (hereinafter referred to as a primitive
operation).
Step 2: Transform the matrix P into a unit matrix I by repeating the
primitive operation, count the number of times the primitive operation was
performed, and find a matrix transformation procedure that yields the
minimum number of primitive operations.
Step 3: To construct the linear transformation part 344A, lines A and
B, which correspond to the rows a and b chosen in step 2, are XORed in the
order reverse to the transformation procedure.
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 midoo, mido,, mido2 and mido3 are input to the
processing routes 30~ to 303, respectively. In the processing route 300, mid~o
and mido, are XORed by an XOR circuit 310; in the processing route 302,
mido2 and the output from the XOR circuit 31o are XORed by an XOR
circuit 312; and the output from the XOR circuit 31 Z is XORed with mido, by
an XOR circuit 31,.
In the processing route 303, the output from the XOR circuit 31 o and
the data mido3 are XORed by an XOR circuit 313; in the processing route
30,, the outputs from the XOR circuits 31, and 313 are XORed by an XOR
circuit 32,; and in the processing route 300, the outputs from the XOR circuit
32, and 31~> are XORed by an XOR circuit 320.
The outputs from the XOR circuits 32n, 32,, 312 and 313 and subkey
data k;i~, k;", k;,2 and k;~3 are XORed by XOR circuits 35o to 353 of the key-
dependent transformation part 344B, respectively, from which are provided
CA 02421142 2003-03-20
- ..
mid~o, mid", mid,2 and mid,3. In other words, the pieces of data midoo,
mido,, mido2 and mido3 are associated with one another and then undergo
linear transformation dependent on the 8-bit subkey data k;,a, k;,~, k;,2 and
k;;3, respectively. In short, logical operations given by the following
logical
expression are performed.
mid;« = midoo~mido20+mido3O+k;,o (7-I )
mid, i = mid«,~mido20+mido30+k;~~ (7-2)
rnid,2 = midooCtmido,0+mid~20+k;,2 (7-3)
mid~3 = midoo+Omido,~mid«3~k;,3 (7-4)
I 0 Incidentally, the subkey k;, is composed of four pieces of data
k~,o, k,n, kn2 and k;~3.
As depicted in Fig. ~, these pieces of data mid,o, mid", mid,2 and
midl3 are then nonlinearly transformed in the nonlinear transformation parts
3450, 345,, 3452 and 3453 into the data outo, outs, out2 and out3,
respectively,
I 5 which are combined into the single piece of data Y;* in the combining part
346. Finally, the data Y;* is linearly transformed into the data Y; by, for
example, a k;2-bit left rotation in the third key-dependent linear
transformation part 347 using the key data k;2, thereby generating the output
data Y; from the nonlinear function part 304. The nonlinear transformation
20 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
25 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
CA 02421142 2003-03-20
-31-
steps in the nonlinear function part 304). Letting p represent the
differential/liner probability of the nonlinear transformation parts 3430 to
3433 and 345 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 <_ pgr; 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, ko~, ko~, k~2, k,~, kit, ..., k~N-
,>,,
k;N-,~2, ek are data stored in the key storage part 322 in Fig. 4 after being
transformed in the expansion 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 expansion key generation part 321 may be the same as in the
expansion key generation part 21 for DES cipher in Fig. l, or as in the
expansion key generation part 21 by Miyaguchi et al. depicted in Fig. 3.
The initial key-dependent transformation 302 and the final key-
dependent transformation part 308 shown in Fig. 4 and the key-dependent
linear transformation parts 341, 344 and 347 in each nonlinear function part
304 shown in Fig. 5 are linear transformation parts which depend on keys;
therefore, the device of this embodiment is a cryptographic device which is
sufficiently secure against both of differential cryptanalysis and linear
cryptanalysis and hence attaches primary importance to security.
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
CA 02421142 2003-03-20
-32-
transformation part 308 and the key-dependent linear transformation parts
341, 344 and 347 to a key-independent transformation part. In this case, the
encryption speed can be increased without significantly diminishing the
security against differential cryptanalysis and the linear cryptanalysis.
Second Embodiment
A description will be given of another embodiment of the nonlinear
function part 304 of Fig. 5 in a data transformation device of the same
construction as that of the first embodiment depicted in Fig. 4. In this
embodiment the nonlinear transformation parts 343, 343,, 343' and 3433 in
Fig. 5 are replaced with nonlinear transformation parts 343' to 3433' which
nonlinearly transform, for example, 8-bit inputs ins to in3 into 32-bit
expanded data MIDoo, MIDo,, MIDo2 and MID~3 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 R; is input to the nonlinear
function part 304 together with the key data k;~y, k;; and k;2. The data R; is
linearly transformed into data R;* = R;+Ok;o, for example, by being XORed
with the key data k;o in the first key-dependent linear transformation part
341. Next, the data R;* is split into four pieces of data in~, in,, in2 and
in3 in
the splitting part 342. The four pieces of data in~, in,, in2 and in3 are
nonlinearly transformed into data MID~o, MIDo;, MIDo2 and MID~3 in the
nonlinear transformation parts 343«', 343,', 3432' and 3433' depicted in Figs.
8A to 8D, respectively. In the first embodiment the nonlinear transformation
part 3430 outputs the m-bit data midoQ for the m-bit input ino, whereas in
this
embodiment the nonlinear transformation part 3430' has an S-box that
outputs the same m-bit data mid~,~> as high-order m bits as does the nonlinear
CA 02421142 2003-03-20
-33-
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 midoo to three routes by
duplicating and output the m-bit data "00 ... Ot~~." That is, the nonlinear
transformation part 3430' is means for transforming the m-bit data in0 to 4m-
bit data
MIDoo = [midoo, 00 . . . 0~2~, midoo, midoo~ (8-1 )
Similarly, the nonlinear transformation parts 343,', 3432' and 3433' are
means for transforming the input data inl, in2 and in3 to
MIDoi = [00 ... 0~2~, mido,, mido~, mido~] (8-2)
MIDo2 = [mido2, mido2, mid02, 00 ... 0~2~~ (8-3)
MID~3 = [mido3, mido3, 00 ... 0~2~, mido3] (8-4)
The data MIDoo expressed by Equation (8-1) can be determined by presetting
as MIDoo the entire data which is provided in the four output routes of the
linear transformation part 344A when the pieces of data mido~, mido2 and
mido3 except midoo are each set as "00 ... 0~2~." Similarly, the data MIDo,,
MIDo2 and MIDO~ 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 MIDoo, MIDo,, MID02 and MIDo3 by using the data ino, in,, in2 and
in3 as addresses.
Then, these pieces of data MIDo~ to MIDo3 are input to the second
key-dependent linear transformation part 344 with the key data k;, as
depicted in Fig. 9. MIDoo and MIDo, are XORed by an XOR circuit 41;
MIDo2 and MIDo3 are XORed by an XOR circuit 42; the outputs from the
XOR circuits 41 and 42 are XORed by an XOR circuit 43; and the output
from the XOR circuit 43 and the key data k;, are XORed by an XOR
CA 02421142 2003-03-20
-34-
circuit 44. The output MIDI from the XOR circuit 44 is split into m-bit
outputs mid~o, mid", mid~2 and midt3. After all, the second key-dependent
linear transformation part 344 linearly transforms the input data by the
following operation:
MIDI = MIDoo~MID~,C-0MID~2+OMIDo3mk;,. (9)
The components of the output MID, _ [mid,«, midi,, mid~2, mid,3] by
this linear transformation operation are expressed by the following
equations, respectively:
mid,o = mid,~o0+mido2~mid~3C~+k;,~ (10-1)
mid" = mido~0+mido20+mido3~k;~, (10-2)
mid~2 = midoo0+mid~r4mido20+k;,2 (10-3)
mid,3 =mid~o0+mido,0+mido30+k;~3 (10-4)
These linear transformation operations are equivalent to those in Fig. 7 given
by Equations (7-1 ) to (7-4). In this way, the same pieces of data mid,o,
mid~l, midl2 and mid,3 as those in the first embodiment are generated.
Incidentally, k;, is composed of four pieces of data k;,0, k;", k;~2 and k;,3.
Then, the four pieces of data mid,, mid", mid,2 and mid~3 are
nonlinearly transformed into data outo, out,, out2 and out3 in the nonlinear
transformation parts 3450, 345, 3452 and 3453, respectively, as in the Fig. 5,
and in the combining part 346 the four pieces of data outo, outs, out2 and
out3
are combined into the single piece of data Y;*. Finally, the data Y;* is
linearly transformed into the data Y; by, for example, a k;2-bit left rotation
in
the third key-dependent linear transformation part 347 using the key data k;2,
thereby generating the output data Y; 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 343, to 3433 of Figs. 8A to 8D by only S-boxes which
CA 02421142 2003-03-20
-3 5-
output 8-bit data midoo to mido3, 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
MIDoo to MIDo3.
The second key-dependent linear transformation part 344 in this
embodiment implements linear transformation equivalent to that shown in
Fig. 7 through the use of four XOR circuits as depicted in Fig. 9 (in Fig. 7
ten XORs), and hence permits faster transformation than in the first
embodiment.
Furthermore, as is the case with the first embodiment, the four
nonlinear transformation parts 343 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 343« to 3433 and 345" to 3453, the differentialllinear probability of
the
nonlinear function 304 becomes p'' as a whole.
Third Embodiment
A description will be given of another embodiment of the nonlinear
function part 304 of still another functional configuration in the data
transformation device that has the functional configuration depicted in Fig. 4
as in the first embodiment.
As depicted in fig. 5, for example, a 32-bit data R; is input to the
nonlinear function part 304 together with the key data k;~, k;~ and k;2 stored
in the key storage part 322. The data R; is linearly transformed into data
R;* = R;O+k;p by, for example, XORing with the key data k;~ in the first key-
dependent linear transformation part 341. Then the data R;* is split into four
CA 02421142 2003-03-20
-3 6-
pieces of, for example, $-bit data in0, in,, in2 and in3 in the splitting part
342.
In the nonlinear transformation part 3430, as shown in Fig. 10, for
instance, the data ino is further split into two, for example, 4-bit subblocks
inoo and ino,; the subblock inoo is transformed to data midooo in a sub-
s nonlinear transformation part 51 and, at the same time, it is XORed with the
data in0; by an XOR circuit 52, whose output in000+ino~ is transformed into
data midoo~ in a sub-nonlinear transformation part 53. Thereafter, these
outputs midooo and midoo, are XORed by an XOR circuit 54, and its output
and the data mid0o; are combined into the data midoo. That is, the nonlinear
transformation part 3430 splits the input ino into two subblocks, then
performs linear transformation and nonlinear transformation of the two
subblocks, and combines the two resulting output subblocks into the output
from the nonlinear transformation part. Similarly, the other remaining pieces
of data in;, in2 and in3 are also transformed into the data mido;, mido2 and
mido3 in the nonlinear transformation parts 343,, 3432 and 3433 each having
the functional configuration shown in Fig. 10 which comprises two nonlinear
transformation parts and two XOR circuits.
These pieces of transformed data midoo, mido,, mido2 and mid03 input
to the second key-dependent linear transformation part 344 depicted in Fig. 7
which uses the key data k;;. The transformation part 344 performs the afore
mentioned operations of Equations (7-1) to (7-4).
Then, the data mid,o is input to the nonlinear transformation part 3450
of the same functional constiguration as shown in Fig. 10, wherein it is
further split into two subblocks mid,oo and mid~o,. The subblock mid,oo is
transformed into data outgo in the sub-nonlinear transformation part 51. The
subblocks mid,oo and mid,0, are XORed by the XOR circuit 52, and its
output mid,00+Omid,O, is transformed into data out0, in the nonlinear
CA 02421142 2003-03-20
-3 7-
transformation part 53. Then, the two pieces of data outgo and onto, are
XORed by the XOR circuit 54, and its output outoo0+outo~ and the data outo,
are combined into outo. Similarly, the other remaining pieces of data mid, ~,
mid,2 and mid,3 are also transformed into the data out,, out2 and out3 in the
nonlinear transformation parts 345,, 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.
The four pieces of thus nonlinearly transformed data outs, outs, out2
and out3 are combined into a single piece of data Y;* in the combining part
346. Finally, the data Y;* is linearly transformed into data Y;, for example,
by a k;2-bit left rotation in the third key-dependent linear transformation
part
347 using the key data k;2, by which the output data Y; from the nonlinear
function part 304 is generated.
As described above, according to this embodiment, in each of the
nonlinear transformation parts 343 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 343 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.
CA 02421142 2003-03-20
-3 8-
The sub-nonlinear transformation parts 51 and 53 are arranged in
parallel in groups of eight and their nonlinear transformation processes are
not associated with one another, and hence they can be executed in parallel.
Further, letting p represent the differential/linear probabilities of the
sub-nonlinear transformation parts 51 and 53, the nonlinear function part 304
provides a differential/linear probability p'' as a whole.
In the above, the first key-dependent linear transformation part 341,
the second key-dependent transformation part 344 and the third key-
dependent transformation part 347 need not always be key-dependent, i.e.,
the linear transformation may be performed in subdata.
While in the above the data processing has been described to be
performed using a hardware structure, it may also be implemented by
software that follows a program. For example, Fig. 11 is a flowchart
showing the principal part of the procedure for data processing. Fig. 11
I S shows the procedure corresponding to the entire procedure of Fig. 4.
Step S 1: Initialize to 0 a variable i representing the repeat count of
processing.
Step S2: Perform initial transformation of an input plaintext and split
it into left and right block data L; and R;.
Step S3: Process the right block data R; by a nonlinear function using
the subkey k; to generate the block data Y;.
Step S4: Perform linear processing of the left block data R; by the
block data Y; to generate the block data L;*.
Step S5: Change the right block data R; to new left block data L; and
the block data L;* to new right block data R;.
Sep S6: Increment the variable i by one.
CA 02421142 2003-10-27
-3 9-
Step S7: Check to see if i has reached N, and if not, return to step S3
and repeat steps S3 to S7.
Step S8: If it is decided in step S7 that the variable i has reached N,
combine the left and right data L; and R; and output the result of final
transformation as output data C.
Details of the process by step S3 in Fig. 11 correspond to the process
by the nonlinear function part 304 shown in Fig. 5, and the procedure is
depicted in Fig. 12.
Step S31: Perform first key-dependent linear transformation of the
right data R; into the data R;*
Step S32: Split the data R;* into n m-bit data ino, inl, ..., ln"_~ (where
m = 8 and n = 4, for instance).
Step 533: Read out data midoo, mido,, ..., mido~"-,~ from n first S-
boxes using the data ino, ins, ..., in"_1 as addresses.
Step 534: Perform key-dependent linear transformation of the data
midoo to mido~n_,~ by the subkey k;1 to generate data midlo to mid,~"_>>.
Step 535: Read out data outo to out"_i from n second S-boxes using
the data midlo to mid~~"_~~ as addresses.
Step 536: Combine the data outo to out"_, into data Y*;.
Step S37: Perform third key-dependent linear transformation of the
data Y*; to generate data Y; 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 38o to 38N_, shown in Fig. 4 may also be programmed intact to
implement the data diffusion part according to the present invention.
CA 02421142 2003-03-20
-40-
Fourth Embodiment
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 x 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 x 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
I 5 transformation part 302 using the key data fk stored in the key storage
part
322 and is split to left and right block data Lo and Rn in the initial
splitting
part 303. For example, 128-bit data is split into two pieces of 64-bit block
data Lo and Ro. The key-dependent initial transformation part 302 performs
a linear transformation such as exclusive ORing of the key data fk and the
input data M or bit rotation of the input data M by the key data fk, or
nonlinear transformation by a combination of multiplications.
The right block data Ko is provided to the nonlinear function part 304
together with the key data koo, k~~ and k~2 stored in the key storage part
322,
and in the nonlinear function part 304 it is nonlinearly transformed to data
Ya. The data Y,> and the data L~ are transformed by a linear operation to data
Lo* in the linear operation part 305. The data L~* and the data R.o undergo
data-position swapping in the swapping part 306 to provide LSE--Ro and
CA 02421142 2003-10-27
-41-
R,~Lo*, and the pieces of data L1 and R, are fed to the next first round
processing part 38~.
Thereafter, in an i-th round processing parts 38; (where i = 0, 1, ...,
N-1) the same processing as mentioned above is repeated for two pieces of
input block data L; and R;. That is, the right block data R; is input to the
nonlinear function part 304 together with the key data k;0, k;~ and k;2, and
in
the nonlinear function part 304 it is nonlinearly transformed to block data
Y;.
The block data Y; and the block data L; are transformed to data L;* by a
linear operation in the linear operation part 305. The data L;* and the data
R;
are swapped in data position in the swapping part 306, that is, L;+l~R;,
R;+,~-L;*. The linear operation part 305 is to perform, for instance, an
exclusive OR operation.
Letting N represent the number of rounds suitable to provide security
of a data transformation device, two pieces of left and right data LN and RN
are obtained as the result of such repeated processing. These pieces of data
LN and RN are combined into a single piece of block data in the final
combining part 307; for example, the two pieces of 64-bit data LN and RN are
combined to 128-bit data. Then the thus combined data is transformed in a
final linear transformation part 308 using the key data ek stored in the key
storage part 322, and output data C is provided as a ciphertext from the
output part 309.
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
CA 02421142 2003-03-20
-42-
in Fig. 13, that is, ek, k~N_~~o, k~N_,u, k~N_>>z, ..., k~o, ka, k~z, kook kou
koz~ ~.
Next, a detailed description will be given of the internal
configuration of the nonlinear function part 304. Fig. 14 is a diagrammatic
showing of the internal functional configuration of the nonlinear function
part 304.
The right block data R; is input to the nonlinear function part 304
together with the key data k;0, k;, and k;2 stored in the key storage part
322.
In the first key-dependent linear transformation part 341 the right block data
R; is transformed to data R;* = R;O+k;0, for example, by XORing with the
subkey data k;0. The thus transformed data R;* is split to n = 8 pieces of
data
in0, inl, in2, ..., ins in the splitting part 342. The eight pieces of data
in0 to
ins are nonlinearly transformed to data mid00 to mido~ in nonlinear
transformation parts 3430 to 343, thereafter being input to the second key-
dependent Linear transformation part 344 using the key data k;,.
The second key-dependent Linear transformation part 344 performs
linear transformation (XORing) among the pieces of data mid00, mido~,
mid02, ..., mido~ input from eight routes to provide new data of eight routes,
and further performs linear transformation (XORing) among these pieces of
data of the eight routes with eight parts of the key data k;, to provide
output
data mid,0, midi,, mid,2, ..., mid, of the eight routes. The eight pieces of
data are input to nonlinear transformation parts 3450, 345,, 3452, ..., 345,
wherein they are transformed to data out0, out,, out2, ..., outs,
respectively.
These eight pieces of data are combined into data Y;* in a combining part
346; furthermore, in the third key-dependent linear transformation part 347
the data Y;* undergoes linear transformation with the key data k;2 to generate
output data Y;.
CA 02421142 2003-03-20
-43-
The second key-dependent linear transformation part 344 contains
the linear transformation part 344A expressed by an n x 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 x 8
matrix P that yield a maximum value of na 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 P~ of eight column vectors from the set C. If
rank(P~) ~ 8, then the subset P~ is not accepted as a candidate.
Step 3-I: Compute na for P~ as follows.
For any two columns (columns a, b):
nao 2 + 111111 # ~ (tia~tib~ ~ tia0tib~~~ ~~l~g
(a,6)
For any three columns (columns a, b, c):
nay 3 + min#~(t~a~tib~tic~ ~ tia~tib~tic#~~ ~~l< $~
(a,b,c)
na2 = 3 + min # ~ (t~a~t,b,t~~) ~ Exception of (0,0,0),( 1,1,1 ), 0<_i< 8 }
(a,b,c)
For any four columns (columns a, b, c, d):
na3=4+mlri #f (t~a~t~b~t~~~taa) ~ ( ~p,~jl~~~(1 01,01), (10,1,0 ~ ))(11100) >'
0~1~8
(a,b,c,d)
na4=4+rillri#{(t~a~t~b,t~~,t,a) I Exception of
co.o,o,o~.n.~.o,o>,co,~,~,a,u.o.~.n, 0<_i< 8}
(a,b,c,d)
CA 02421142 2003-03-20
-44-
nds=4+min#{(t~a~t~b,t~~,t~d) I Exception of
(o,o,o,o).o,o,i.o>,co,i.i.o.o.i.o,a, 0<_i< 8}
(a, b,c,d )
nd6=4+min#{~tia~tib~tic~tid) I Exception of
co,o.o,o).u.o.o.n.co.~.~.a,o,~,~.o>, 0-i< 8}
(a,b,c,d)
nd~-4+1111ri#{~tia~tib~tic~tid~ I Exception of
co,o.o.o>,co.i.i.o>.n.o.~.n.n.i.o,u, 0<_i< 8}
(a.b.c.a)
ndg-4+111111#{(t~a~t~h,t,~,t~a) ~ Exception of co.o.o.o~.~o. i,o,
u.n.o,~,a.n.i.i.o~, 0<_i< 8}
(a,b,c,d)
n~9=4+min#{~t~a~tib~tic~tid) ~ Exception of
(o.o.o.o).co.o.~.n,n.~,o,n,n.i.i,o~, 0_<i< 8}
(a,b,c,d)
~t~, = min{nd; ~ 0<_i<_9}
Intuitively, Equations ndo to n~9 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 right-hand side) is determined. For
example, when there are two active s-boxes in the first nonlinear
transformation part 343, its difference values can be represented as Oza and
dzb, respectively. At this time,
[Oz' ~~ - LtiaOZaOt;bOZb~ O~l<g) C 1 1 )
In particular, when ~za = Ozb,
[dz'u - UtiaOt~b)Ozn~ ~0~~~8) ~12)
Accordingly, the minimum number of active s-boxes in this case is given by
ndo.
As a result of our search for the matrix P through of the above search
algorithm, it has been found that there is no matrix with n~ >_ 6 = T but that
there are 10080 candidate matrices with n~ = 5 = T. Hence, the
invulnerability of the round function using such a matrix P against
differential cryptanalysis is p _< p~5. And the invulnerability against linear
CA 02421142 2003-03-20
-45-
cryptanalysis is also q <_ p~5.
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 (8x7)~6~29~ 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 B I to B4 with 8
inputs and 4 outputs as depicted in Fig. 1 SA. 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 (4x3x2x 1 )4~2~g, which is
sufficiently small for the exhaustive search.
While in Fig. 15A four transformation boxes are alternately inserted
in the lines of left and right four routes, these lines may be determined to
be
arbitrarily selected four lines and the other remaining four lines. Each
transformation box is supplied with inputs from the four lines in which it is
inserted and inputs from the remaining four lines and outputs the results of
transformation to the former four lines.
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.
CA 02421142 2003-10-27
-46-
0 1 1 1 1 1 0
1
1 0 1 1 0 1 1
1
1 1 0 1 1 1 1
0
P 1 1 1 0 1 0 1 (13)
- 1
1 1 0 1 1 0 0
1
1 1 1 0 0 1 0
1
0 1 1 1 0 1 1
0
1 0 1 1 1 0 1
0
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 B 1
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 x 4 matrix in the first embodiment, it can be
ascertained as mentioned below whether the matrix for the mask value path
is a transposed matrix of the matrix P in the linear transformation part 344A
of Fig. 16 and whether n, = 5 correctly holds. By constructing a mask value
path in the linear transformation part 344A of Fig. 16 using concatenation
rules defined by Theorem 2, the matrix TP for the mask value path can be
computed as follows:
0 1 1 1 1 1 0 1
1 0 1 1 1 1 1 0
1 1 0 1 0 1 1 1
TP = 1 1 1 0 1 0 1 1 ( 14)
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
CA 02421142 2003-03-20
-47-
This indicates that the matrix ~rP is a transposed matrix of the matrix P.
Further, it can be confirmed that the minimum number of active s-boxes
is n, =5.
Fig. 17 illustrates concrete examples of the second key-dependent
linear transformation part 344 which comprises the linear transformation
part 344A of the construction determined above and a key transformation
part 3448.
The key transformation part 3448 calculates the XORs of the key
data k;,o k;,~, k;,~, ..., k;,~ and the outputs from the linear transformation
part
by XOR circuits 63«, 63,, 63~, ..., 63~, and yield output data mid,, mid",
mid,2, ..., mid». With such a functional construction as depicted in Fig. 17,
the following operations are performed.
mid,o=mido,O+mido20+mid«30+mida40+mido50+mid«60+k;,o (15-1)
mid»=midoo0+mido20+mid~30+mido50+mido60+mid«~O+k;,~ (15-2)
mid,2=midoo0mido,O+mid~30+mid~40+mido60+mid«~O+k;~~ (15-3)
mid~3=midoo0+mido,O+mido20++mido40+mido50+midp~0+k;~3 (15-4)
mid,4=midoo0+mido,0+mid~30+mido40+mido50+k;,~ (15-5)
mid~5=midoo0+mido,O+midoz0+mido50+mido60+k;,s (15-6)
mid,6=mido~0+mido20++mido30+mido60+mid~~0+k;,~, (15-7)
mid=midoo0+mido2+Omido30+mido40+mido~0+k;,~ (15-8)
The above operations generate the data mid,o, mid", mid~2, ..., mid,.
Incidentally, the subkey k;, is composed of eight pieces of data k;,o, k;1,,
k;i2,
..., k;l~. In Fig. 17, the pieces of data mid~o to mido~ are input to routes
60o to 60~, respectively.
The XOR circuits 614, 615, 61 ~, 61 ~ on the routes 604, 605, 606, 60~
calculate the XORs of the data mido4 and midoo, midos and midi,, mid~6 and
mido2, mido~ and mido3, respectively.
CA 02421142 2003-03-20
-48-
The XOR circuits 610, 61,, 612, 613 on the routes 600, 60,, 602, 603
calculate the XORs of the data mid~~ and the output from the XOR circuit
616, the data mido, and the output from the XOR circuit 61 ~, the data mido2
and the output from the XOR circuit 614, the data mid~3 and the output from
the XOR circuit 615, respectively.
The XOR circuits 624, 625, 626, 62~ on the routes 604, 605, 606, 60~
calculate the XORs of the outputs from the XOR circuits 613 and 614, the
outputs from the XOR circuits 61 ~ and 615, the outputs from the XOR
circuits 61 ~ and 616, the outputs from the XOR circuits 612 and 61 ~,
respectively.
The XOR circuits 62«, 62,, 622, 623 on the routes 60~, 60~, 602, 603
calculate the XORs of the outputs from the XOR circuits 61 ~ and 624, the
outputs from the XOR circuits 61, and 625, the outputs from the XOR
circuits 612 and 626, the outputs from the XOR circuits 613 and 62~,
respectively.
Furthermore, the XOR circuits 63o to 63~ on the routes 60o to 60~
XOR the outputs from the XOR circuits 62~ to 62~ and the key data k;,« to
k;l~, respectively, providing the outputs mid, to mid, from the routes 600
to 60~. That is, the outputs mid»~ to mid, are the XORs of six pieces of data
selected from the input data mido~ to mido~ and the key data, and the outputs
mid,4 to mid, are the XORs of five pieces of data selected from the input
data midoo to mid~~ and the key data.
Turning back to Fig. 14, the pieces of data mid,, mid", mid,2, ...,
mid, are nonlinearly transformed to pieces of data outo, out,, out2, ..., outs
in the nonlinear transformation parts 345«, 345,, 3452, ..., 345, and in the
combining part 346 the eight pieces of data outo, out,, out2, ..., outs are
combined into a single piece of data Y;*. Finally, the data Y;* is linearly
CA 02421142 2003-03-20
-49-
transformed to data Y;, for example, by a k;z-bit left rotation in the third
key-
dependent linear transformation 347 using the key data k;2, thereby
generating the output data Y; from the nonlinear function part 304.
The nonlinear transformation parts 343« to 343 and 345° to 345
function just like S-boxes for DES cipher, and they are 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 343° to 343 are arranged
in
parallel and their transformation processes are not associated with one
another, and hence they can be executed in parallel. The same goes for the
nonlinear transformation parts 345, to 345. Thus, the linear transformation
operations can be executed in one step for each group (a total of two steps).
Letting p represent the differential/liner probability of the nonlinear
transformation parts 343° to 343 and 345« to 345, the nonlinear
function
part 304 provides a differential/linear probability 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 <_ p~°r; for example, when r = 4 ( 12 rounds), P <_
p~°. In the case
of DES cipher, this corresponds to 60 or more rounds, making it possible to
provide a data transformation device sufficiently secure against differential
cryptanalysis and linear cryptanalysis. Incidentally, the second key-
dependent linear transformation part 344 is not limited specifically to the
linear transformation part depicted in Fig. 17 but may be modified as shown
in Fig. 18, for instance. In this instance, the following operations are
conducted.
CA 02421142 2003-10-27
-50-
mid,o=mido,O+mido20+mido40++mido50+mido60+mido~+Ok;,o(16-1)
mid~l=midol0+mido20++mido3+Omido40+mido6+Ok;~l (16-2)
mid,2=midooOmido,Omido30mido40mido50mido60+k;12 (16-3)
midl3=midoo0+mido30++mido4+Omido60+mido~+Ok;~3 (16-4)
midl4=midoo0+mido20+mido30+mido50+mido60+mido~0+k;14(16-5)
mid,5=midoo0+midol0+mido20+mido;0+mido60+k;ls (16-6)
mid~6=midoo0+midol0+mido20++mido30+mido40+mido~0+k;~6(16-7)
midl~=midoo0+mido20++mido4C~+mido50+mido~0+k;l~ (16-8)
Alternatively, the circuit construction of Fig. 19 used,
may be in
which case the following operations are performed.
mid~o=midoo0+mido,O+mido40+midos0+mido60+k;,a (17-1)
mid,~=midol0+mido30++mido40+midoSC~+mido~0+k;~l (17-2)
mid~2=midoo0+mido20++mido40+mido60+mido~0+k;12 (17-3)
mid,3=mido2+Omido3+Omido50+mido60+mido~+Ok;~3 (17-4)
midl4=midoo+Omido~0+mida30+mido50+mido60+mido~0+k;14(17-5)
mid~5=midol0+midoz+Omido30+mido40+mido6+Omido~0+k;ls (17-6)
midl6=midoo0+midal0+mido20++mido40+mido50+mido~0+k;16 (17-7)
midl~=midoo0+mido20+mido30++mido40+mido50+mida60+k;l~ (17-8)
As is evident from the operations in Figs. 17 to 19, the second key-
dependent linear transformation part 344 performs key-dependent linear
transformation which yields a total of eight pieces of output data mid~o,
midi,, mid~2, ..., mid,, that is, four pieces of output data derived from six
pieces of data selected from the eight pieces of input data midoo, midol,
mido2, .. ., mido~ and four pieces of output data derived from five pieces of
data selected from the eight pieces of input data. In such cases, the
nonlinear
function part 304 provides a differential/linear probability p5 as a whole as
CA 02421142 2003-10-27
-51-
described previously with reference to the Fig. 17.
The key data f fk, koo, ko~, koa~ kio~ km kia~ ..., k~_I~o, k~"_~~~, k~_1~2,
ek} is data provided by inputting the master key via the key input part 320 to
the expansion key generation part 321, transforming it to key data and
storing it in the key storage part 322.
The expansion key generation part 321 may be made identical in
construction with the expansion key generation part 21 for DES cipher
shown in Fig. 1, or an expansion key generation part disclosed in U.S. Patent
No. 4,850,019.
Since the initial key-dependent transformation part 302, the final key-
dependent transformation part 308 and the key-dependent linear
transformation parts 341, 344 and 347 are key-dependent linear
transformation means, the data transformation device is also sufficiently
secure against other cryptanalysis techniques than differential and linear
cryptanalysis.
The fourth embodiment is not limited specifically to the above
constructions; if speedup is desired, any one of the initial key-dependent
transformation part 302, the final key-dependent transformation part 308 and
the key-dependent linear transformation parts 341, 344 and 347 may be
omitted or modified to key-independent transformation means. In this case,
the encryption speed can be increased without significantly diminishing the
security against differential cryptanalysis and linear cryptanalysis.
CA 02421142 2003-03-20
-52-
Fifth Embodiment
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 343, in the nonlinear function part 304 of Fig. 14 are modified like the
nonlinear transformation parts 3430', 343,', 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 R; is input to the
nonlinear function part 304 together with the key data k;o, k;,, k;2 stored in
the key storage part 322. In the first key-dependent linear transformation
part 341 the data R; is, for example, XORed with the key data k;o and hence
is linearly transformed to data R;* = R;mk;o as in the case of Fig. 14. Then
the data R;* is split into eight pieces of data ino, in,, in2, ..., ins in the
splitting part 342. The eight pieces of data ino, in,, in2, ..., ins are
nonlinearly transformed to data MIDoo, MIDo,, MIDo2, ..., MIDo~ in the
nonlinear transformation parts 3430', 343,', 3432', ..., 343', respectively.
The nonlinear transformation part 3430' is so designed as to transform the m-
bit data ino to the following 8xm-bit data.
MIDoo=[00. . .0~2~, midoo, midoo, midoo, midoo, midoo, 00. . .0~2~, midoo] (
18-1 )
That is, the nonlinear transformation part 3430' has, for example, as shown
in Fig. 20A, an S-box which outputs the data midoo in high-order m bits as
does the nonlinear transformation part 3430 in the fourth embodiment of
Fig. 14 and outputs "00...02," as low-order m bits; furthermore, it branches
CA 02421142 2003-03-20
-53-
the output data midoo in six routes and "00. ..0~2~" in two other routes.
The nonlinear transformation part 343 ~' has, as depicted in Fig. 20B,
an S-box 343, which outputs the data mido~ in high-order m bits and outputs
"OO...Ot2~" as low-order m bits; furthermore, it branches the output data
midi>,
in six routes and m-bit data "00...0" in two other routes. The other nonlinear
transformation parts 3432' to 343' are also similarly constructed; in Fig.
20C there is depicted the construction of the nonlinear transformation part
343' but no description will be repeated. These nonlinear transformation
parts 343,' to 343' transform data in, to ins to the following data MIDo, to
MID~~, respectively.
MID~,=[mido,, 00.. .0~2~, mido,, mido~, midi", midi,, mido,, 00...0~2~] ( 18-
2)
MIDo2=[mido2, mida2, 00...0~2~, mido2, 00. . .0~2~, mido2, midq2, midoz] ( 18-
3)
MIDo3=[mido3, mido3, mido3, 00. . .0~2~, mid~3, 00. . . 0~2~, mido3, mid~3] (
18-4)
MIDo4=[mido4, 00...0~2~, mido4, mido4, midoa, 00...0~2~, 00...0~2~, mido4] (18-
S)
MIDoS=[midos, mido~, 00. . .0~2~, mid«5, mido5, mido5, 00. . .0~2~, 00. .
.0~2~] ( 18-6)
MIDo6=[mido6, mid~6, mida6, 00. . .0~2~, 00. . .0~2~, mid~6, mido6, 00. .
.0~2~] ( 18-7)
MIDo~=[00.. .0~~~, mido~, mido~, mido~, 00. . .0~2~, 00. . .0~2~, mid~~,
mido7] ( 18-8)
These pieces of data MIDo~ to MIDo~ 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 MIDo~ 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 midoo and mido2 to
mido~ except midi, axe all set as "00. . .0~2~." The same goes for the data
MIDo2 to MIDo~. These nonlinear transformation parts 3430' to 343' may be
formed by memory from which the pieces of data MID~o to MIDo~ are
directly read out using the data ino to ins as addresses.
CA 02421142 2003-03-20
-54-
Then the pieces of data MIDoo to MIDo~ are input to the second key-
dependent linear transformation part 344 using the key data k;, as shown in
Fig. 21. The second key-dependent linear transformation part 344 is made
up of XOR circuits 41 ~ to 414 each of which XORs two pieces of input data,
XOR circuits 42, 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 k;,. With this construction, the following
operation is conducted.
MID,=MIDooO+MIDo, O+MIDo2~MIDo3mMIDo4C~+ MIDo50+ MIDo6~MIDo~+Ok;,
(19)
This output MIDI is split into eight blocks, which are output as data mid,o,
mid", mid,2, ..., midl~. Eventually, the linear transformation by the second
key-dependent linear transformation part 344, expressed in units of m-bit
subblocks, becomes as follows:
I S mid,o = mido~0+mido2+Omido3+Omido4+Omidos~mido60+k;,o (20-1 )
mid" = midoo0+mido20+mid~30+mido5+Omido64mido~0+k;~, (20-2)
mid~2 = midoo0+mido, +Omido30+mido4+Omido6+Omido~0+k;,2(20-3)
mid,3 = midoo0+mido~0mido2~mido4+Omido50+mido~Ok;~3 (20-4)
mid,4 = midoo0+mido,U+mido3~mido40+mido50+k;,4 (20-5)
mid,; = midooOmido,U+mido20+mido5n+mido60+k;,5 (20-6)
mid,6 = mido,O+mido2+Omido3~mido~0+mido~0+k;,6 (20-7)
mid, = midoo0+mido20++mido3U+mido40+mido~+Ok;,~ (20-8)
The above equations express a linear transformation equivalent to that by
Equations ( 15-1 ) to ( 15-8) described previously with reference to Fig. 17.
As a result, the same pieces of data mid,o, mid", mid,2, ..., mid, are
generated. Incidentally, the subkey data k;, is composed of eight pieces of
data k;,o, k;i,, k;,2, ..., k;m.
CA 02421142 2003-03-20
-55-
Next, the eight pieces of data mid,o, mid", mid,2, ..., mid, are
nonlinearly transformed to eight pieces of data outo, out,, out2, ..., outs in
the
nonlinear transformation parts 345«, 345,, 3452, ..., 345 in Fig. 14, and the
eight pieces of data outo, out,, out2, ..., outs are combined into a single
piece
of data Y;* in the combining part 346. Finally, the data Y;* is linearly
transformed to data Y; by, for example, a k;2-bit left rotation in the third
key-
dependent linear transformation part 347 using the key data k;2.
As depicted in Fig. 21, the second key-dependent linear
transformation part 344 uses eight XOR circuits but implements the linear
transformation equivalent to that in Fig. 17 (which uses 24 XOR circuits),
and hence it permits faster transformation than the fourth embodiment.
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 343' to 343', the differential/linear probability of the nonlinear
function 304 becomes p' 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 k;,. That is, the XOR circuits 63~, to 63~ in Fig. 17 and
the circuits corresponding thereto in Figs. 18, 19 and 21 may be omitted.
Moreover, in the above, the first key-dependent linear transformation
part 341, the second key-dependent transformation part 344 and the third
key-dependent transformation part 347 need not always be key-dependent,
that is, the linear transformation may be performed in subdata without
inputting the key data to them.
CA 02421142 2003-03-20
The data transformation processing in the fourth and fifth
embodiments described above may also be implemented by executing a
program of its procedure by a computer. The procedure is the same as
shown in Figs. 11 and 12; hence, no description will be repeated.
Fig. 22 illustrates an example of the system configuration wherein
the program for the data transformation processing described in connection
with the first to fifth embodiment is prerecorded on a recording medium and
is read out therefrom to perform the data transformation according to the
present invention. A central processing unit (CPU) 110, a read-only memory
(ROM) 120, a random access memory (RAM) 130, a storage device (a hard
disk HD, for instance) 140, an I/O interface 150 and a bus interconnecting
them constitute an ordinary computer 100. The program for implementing
the data transformation process according to the present invention is
prestored on the recording medium such as the hard disk HD. In the ROM
120 there are stored respective S-boxes in tabular form. In the execution of
the data transformation the program is read into the RAM 130 from the hard
disk HD 140, and upon input of the plaintext M via the interface 150, then
the program is executed under the control of the CPU 110, and the resulting
output data C is output via the interface 150.
The program for the data transformation process may be one that is
prestored in an arbitrary external storage device 180. In such an instance,
the program can be used after once transferred via a driver 170 from the
external storage device 180 to the hard disk 140 or the RAM 130.
Though not shown, when the output data C is sent over a
communication line or the Internet, only a person who has a common secret
key is qualified to decrypt the output data C. Since the data C transformed
according to the present invention is highly resistant to differential
CA 02421142 2003-03-20
-5 -
cryptanalysis and linear cryptanalysis, it is possible to achieve transmission
of information with increased security.
Incidentally, when in each embodiment the key scheduling part 20
has the same construction as depicted in Fig. 3, the subkeys used as k;
and k;+, in the data diffusion part 10 become the outputs Q2~ and Q2~+, (where
i = 2j) from the key processing part 21_; in the key scheduling part 20. On
the
other hand, since it is the subkeys kN and kN_~ 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_, 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 flc 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
CA 02421142 2003-03-20
- -
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 fj, and a plurality of intermediate values L are
generated by repeatedly using the G-function.
The G-function is adapted to operate on two input components (Y, v)
and generate three output components (L, Y, v). The bits of the component
Y is equal to or larger than the bits of the master key K.
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 S
M-1). Letting the output from the G-function called a j-th time be
represented by (L~, Yi, v,i), part of this value is used as the input (Yi+, =
Y_i,
v~+, = v~) to the G-function called a (j+1 )-th time. Assume here that Yo is a
value containing K and that v0 is a predetermined value (0, for instance).
For the given master key K, the subkey k; (where i = 0, 1, 2, ..., N-1)
is determined as follows:
(L;, (Y~, v,)) = G(Yo, vo) (21)
(L.i+a (Y.i+n vi+t)) _ (,T(Y~, v~)
(j = l, 2, ..., M-1) (22)
CA 02421142 2003-10-27
-59-
k; = H(i, L1, L2, ..., LM)
(i = 0, 1, 2, ..., N-1) (23)
where the H-function is means to extract from each component L;
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.
Sixth Embodiment
In Fig. 23A there is depicted the basic construction of the key
scheduling part of this embodiment for application to the key scheduling part
shown in Fig. 4A. The master key K is input to an intermediate key
generation part 220; the intermediate key generation part 220 has a plurality
(M rounds) of G-function parts which operate in cascade, and generates
intermediate keys L, to LM, which are stored in a storage part 230. The
15 intermediate keys L~ to LM stored in the storage part 230 are provided to a
subkey generation part 240, wherein subkeys k; are generated based on an H-
function part. The structure and operation of each part will be concretely
described below.
This example is intended to increase the security of the key
20 scheduling part shown in Fig. 3 using a data randomization part disclosed
in
the afore-mentioned 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 Q~ represent the respective Q component.
Each Q~ component is 16-bit. The subkey generation part 240 constructs the
subkey ko from the value of a first bit of the respective Q~ component, the
CA 02421142 2003-03-20
-6
subkey k~ from the value of a second bit of the respective Q,; component, and
in general, the subkey k;_, from the value of an i-th bit of the Qj component.
That is, letting Qj[i] represent the i-th bit of the Q; component, the subkey
k;
is expressed by the following equation.
Ki-i = (Qi[i], QZ[i~, ..., Qj[i], ..., Q,6[i~) (24)
where 1 _< i, j S 16.
This processing method will be reviewed below in the framework of
the G- and the H-function mentioned above. Here, Y; represents the value of
64 bits, Y,;~ the value of high-order 32bits of Yj and Yj~ the value of low-
order 32 bits of Y;.
Letting the output from the G-function for the input (Y;, v,;) be
represented by
(L.i+a (Yj+n vi+i)) - G(Yy Vii) (0 ~ j ~ ~)~ (25)
the output (L_;+i, (Yj+~, vj+i)) is given by the following equations.
Y;+, ~. - YiR (26)
Y,+t~ - L.i+t - fi;(1'.iL~ ~'.i~j~v.i) (2~)
vj+1 - YjL (2g~
The subkey k; is given as a function of i and L ~ to L8 by the following
equation.
K;_, = H(i, L,, L2, ..., L~) (29)
Letting each L; be represented by (t;(~), t;(2), ..., t_;~32)) the H-function
constructed the subkey k; as follows:
K' _ (tI(i)' t'(16+i)' t2(16+i)~ ..., tg(~), tg(~6+~)) (1 ~ 1 ~ 16) (3~)
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.
CA 02421142 2003-10-27
-61-
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 Yo
to the first-round G-function part 22-1 together with a constant vo, and Y~_,
and v~_~ are input to the G-function part 22-j of each j-th round; each G-
function part randomizes Y~_~ and outputs L~, Y~ and v~. L~ is an intermediate
key and Y~ and v~ are fed to the next G-function part 22-(j+1). That is, after
setting Yo = K and vo =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 Y~ and v~ to the G-function part 22-(j+1), split Y~
into two blocks (Y~L, Y~R) by a splitting part 221 in Fig. 25.
Step 2: Output Y~L as v~+1. Input Y~L to a data diffusion part (fk) 222.
Step 3: Input Y~R to a data swapping part 224. Input Y~R and v~ to an
XOR circuit 223 to compute Y~RO+v~ and input the result of computation to
the data diffusion part (fk) 222.
Step 4: Upon receiving Y~L and Y~RO+v~ as inputs thereto, the data
diffusion part (fk) 222 outputs the result of computation as L~+1 and, at the
same time, input it to the swapping part 224.
Step 5: Upon receiving Y~R and the result of computation L~+1 by the
data diffusion part (fk) 222, the swapping part 224 renders Y~R to Y~+,L and
L~+1 to Y~+~R, then concatenates them to Y~+~ _ (Y~+1L, Yj+1R), and outputs
it.
The eight L; components output from the G-function part 22-1 to
22-8 are once stored in the storage part 230 (Fig. 23A).
Next, a description will be given, with reference to Fig. 26, of the
construction of the H-function part serving as the subkey generation part
240. The H-function part 240 performs the following steps after reading out
CA 02421142 2003-03-20
-62-
the eight L components L, to Lg from the storage part 230.
Step I : Read out each component L; from the storage part 230 and
input it to a bit splitter 24I to split it bitwise as follows:
(t;(~), t ~2~, ..., t (32~) - L (j - I, 2, , . ., 8) (31 )
J .I .I
Step 2: Input (t~(~~, t~()6+~~, t2(~~, t2()6+'~, ..., t~(~), tg()6+i)) to a
blt combiner
242 to obtain the subkey as follows:
k' - (t)(i)' t)(16+i)' t2(i)~ t2(16+i)~ ,.., tg(~~, t~()6+i)) (i = I~ 2~ .,~
16) (32)
Seventh Embodiment
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.
As shown in Fig. 23B, a plurality of intermediate keys L_; are
generated in the intermediate key generation part 220. The intermediate key
generation part 220 is identical in construction with that depicted in
Fig. 23A; that is, it comprises the plurality of G-function parts 22 as shown
in Fig. 24. Upon each generation of the intermediate key L_; in the
G-function part 22, the intermediate key L; is fed to the subkey generation
part 250, from which bit position information, which is determined by the
suffix i of the subkey k; and its bit position q, is output as information k;~
and
is stored in the storage part 260.
That is, the intermediate key generation part 220 and the subkey
generation part 250 repeat the following steps 1 through 7 for each value
fromj=Otoj=7.
Step I : Upon input of Y; and v_; to the G-function part 22-(j+I ), split
Y~ into two blocks (Y~L, Y~R) by the splitting part 221.
CA 02421142 2003-03-20
-63-
Step 2: Output Y~~' as v~+, . And input Y;'' to the data diffusion part
(fk) 222.
Step 3: Input Y;'z to the swapping part 224. And input Y;R and v_; to
the XOR circuit 223 to calculate Y,;'t0+v,; and input it to the data diffusion
part
(fk) 222.
Step 4: Upon receiving Y.;'' and Y;'~O+v~, the data diffusion part (f;;)
222 inputs the result of its computation as L;+, to the subkey generation part
250 (Fig. 23B) and, at the same time, input it to the swapping part 224.
Step 5: Upon receiving Yap and the result of calculation L~+, from the
data diffusion part (fk) 222, the swapping part 224 renders Y~~ to Y~+'~ and
L_~+, to Y~+, R, then concatenates them to Y;+, _ (Y~+, L', Y_;+ 'R) and
outputs it.
Step 6: As depicted in Fig. 27, the subkey generation part 250 input
L,; to a bit sputter 251 to split it bitwise as follows:
(t;('), t;(2), ..., t~(3z)) = L~ (~ = 1, 2, ..., 8) (33)
and then input them to an information distributor 252.
Step 7: The bit string (t,;('~, t;(2), ..., t.;(32)) input to the information
distributor 252 is information on the bit position of L~ determined by the bit
position q of the subkey k; for a suffix i being used as information on the
bit
position q of the subkey k;, and is stored for each L_; in one of 16 storage
areas of the storage part 260 divided for each subkey
k' - (t'(i)' t'(16+i)' t~(i)' t2(~6+i)~ ..., tgi~), tg('~+~)) (34)
Step 8: When 16-bit information is set for each k;, that is, when the
subkey k; generated, output its value (i = 1, 2, ..., 16).
CA 02421142 2003-03-20
-64-
Eighth Embodiment
With a view to reducing the device size or the number of program
steps, this embodiment uses in key scheduling an f function used for
encryption.
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 (Y~, vi) be
represented by
(Li+t ~ (Y~+> > v.i+~ )) ~ G(Yi~ vi) (0 ~ J ~ 7)
and let the output be set as follows:
> >
((~'~~1~ Yi(2~ YJ(3~ yJ'a~) v~) -~
~Lc ~ Lc > L' > L'4' ~~~Y'~) ~~'o y':~) Y'di ~~m y (35)
j+I' ~+1~ ,~+I~ j+I ~+1~ ~+I> '+I~
Here, the following definitions are given.
Y~+; = f(Y~'' ) (i = l, 2, 3, 4) (36)
IS L'oy = v~ (37)
L';+. =f(L';+~')~Y;~~ (i ' 1~ 2~ 3~ 4) (38)
v . Lc4>
i+~ ~+i (39)
Further, in
k; = H(i, L,, L2, . .., Lg) (40)
the following definitions are given.
qi+4; = L';+.' (i = 0, l, 2, 3) (41)
(t~~>,ty',...,t;'')=qi (i = 0, l, ..., 31) (42)
k = ~tcli'')~ tc(i'2~> . t(~i'z~~ ) i = 0 1 15 43
(i+1) 0+(imod2)~ 2+(imod2~,.. a 30+(imod2) ( > >
Suppose that [i/2] in Equation (43) represents Li~2~.
This procedure will be described below with reference to Figs. 28
and 26.
CA 02421142 2003-03-20
-65-
Preparation
Step I : Set as v~ a value extracted from
0123456789abcdef101112....(hex) by the same number of bits as the bit
length of the function ~
Step 2: Set the master key K at Y~.
Generation of Intermediate Key: The following procedure is repeated for
j=0,1,2,...,7.
Step 1: Divide equally the input Y,i into four (Yi~~~, Y~~''~, y~~3~, Y,ic~~).
Step 2: For i = l, 2, 3, 4, compute Y~+~~'~ = f(Yi~'~) by data diffusion
part 611 to 614.
Step 3: set L~+~= va.
Step 4: For I = l, 2, 3, 4, compute f(Li+,~'-'~) by data diffusion part
621 to 624, and input the result of computation to an XOR circuit 63i to
XOR it with Y,i+~t'~ to obtain L~.,1~'~ = f(L,i+y' ~~)+OY,i+,~'~.
Step 5: set Y~+~ =(Yi+t ~~~~ Yi+i2~~ Y.i+n3~~ ~'.i+na~).
Step 6: set L~+~= L~+~ ~~>> L~+t~2~~ L.i+n3>> L.i+~~4~)~
Step 7: Set v_i+, = L~+~~4~.
Generation of Subkey: As is the case with the sixth embodiment, Equation
(43) is implemented to obtain k~, k~, ..., kN (where N <_ 16).
This embodiment is not limited specifically to the above but can also
be carried out in the following manner:
( 1 ) When the size of Yo is larger than K, K is used as part of Y« and
the remaining part is filled with a constant.
(2) An arbitrary constant is used as v~.
(3) The bit length of respective characters are arbitrarily set in the
ranges in which they are harmonized with one another.
(4) Functions other than that for encryption are used as f.
CA 02421142 2003-03-20
-66-
(5) Part of L; is not used to compute H, that is, this occurs when the
number of subkeys k; is small and the bits of L,~ is large.
(6) H is computed in the same manner as in the sixth embodiment.
(7) G is computed in the same manner as in the sixth embodiment.
(8) As is the case with the seventh embodiment, upon each generation
of one intermediate key, not on the generation of all the intermediate keys,
the result of computation is stored in the storage part 260 in the
corresponding bit position of k;.
The intermediate key generation part 220, the subkey generation
I 0 parts 240 and 250 may be adapted to be operated under program control by
the computer depicted in Fig. 22.
EFFECT OF THE INVENTION
As described above in detail, according to the present invention, the
I 5 data transformation device for use in an encryption device to conceal data
is
designed to simultaneously meet the requirements of security and speedup,
thereby ensuring security and permitting fast encryption procedure without
causing a significant increase in the number of rounds. Hence, the device of
the present invention suitable for use in an encryption device of the
20 common-key cryptosystem which encrypts or decrypts data in blocks using a
secret key.
Furthermore, according to the key scheduling of the present invention,
even if k6, k~, kg, k9, k~o and k" are known in the sixth and seventh
embodiment, only 12bits (for example, 6th, 7th, 8th, 9th, 10th, 11 th, 22nd,
23rd,
25 24th 25th, 26th and 27th bits) of the respective L; 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.
