Data converter and recording medium on which program for...

Details Data converter and recording medium on which program for... Data converter and recording medium on which program for...

2000-09-14

2004-07-27

Morse, Gregory (Department: 2137)

Electrical computers and digital processing systems: support

Data processing protection using cryptography

By stored data protection

C380S029000

Reexamination Certificate

active

06769063

ABSTRACT:

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.
FIG. 1
illustrates the functional configuration of DES. DES uses a 64-bit secret key (8 bits being used for parity), and encrypts or decrypts data in blocks of 64 bits. In
FIG. 1
the encryption process is executed in a data diffusion part
10
, which begins with initial permutation of 64 bits of a plaintext M in an initial permutation part
11
, followed by splitting the permuted data into two pieces of 32-bit block data L
0
and R
0
. The block data R
0
is input to a function operation part (referred to also as a round function)
12
which is a data transformation part shown as an i-th round processing part
14
i
(i=0, 1, . . . , 15) in
FIG. 2
, wherein it is transformed to f(R
0
, k
0
) using a 48-bit subkey k
0
. The thus transformed data f(R
0
, k
0
) and the block data L
0
are exclusive ORed in an XOR circuit 13, and its output and the block data R
0
are swapped to obtain the next block data L
1
, R
1
. That is,
R
1
=L
0
⊕f
(
R
0
, k
0
)
L
1
=R
0
where ⊕ represents an exclusive OR. A 0-th round processing part
14
0
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
1
and R
1
; similar round processing parts
14
1
to
14
15
are provided in cascade. The processing by the i-th round processing part
14
i
will hereinafter be referred to as i-th processing, where i=0, 1, . . . , 15. That is, each round processing part
14
i
(where 0≦i≦15) performs the following processing
R
i+1
L
i
⊕f
(
R
i
, k
i
)
L
i+1
=R
i
And finally concatenation two pieces of data R
16
and L
16
into 64-bit data, which is permuted in a final permutation part
15
to provide a 64-bit ciphertext. Incidentally, the operation of the final permutation part
15
corresponds to an inverse transform of the operation of the initial permutation part
11
.
The decryption process can be executed following the same procedure as that for the encryption process except inputting subkeys k
0
, k
1
, . . . , k
14
, k
15
to the function f (the function operation part
12
) in the order k
15
, k
14
, . . . , k
1
, k
0
which is reverse to that in the encryption process. In such an instance, the outputs L
16
and R
16
from the final round processing part
14
15
are further swapped as depicted, and in the decryption process the ciphertext is input to the initial permutation part
11
for execution of the process of
FIG. 1
, by which the plaintext is provided intact at the output of the final permutation part
15
. In a key scheduling part
20
an expanded key generation part
21
: splits a master key of 64 bits, except 8 bits used for parity, into two pieces of 28-bit right and left key data; then performs 16-round swapping of the two pieces of 28-bit right and left key data; and performs reduced permutation of the permuted right and left data (a total of 56 bits) provided from the respective rounds to generate 16 48-bits subkeys k
0
, k
1
, . . . , k
14
, k
15
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
i
is transformed to 48-bit data E(R
i
) in an expanded permutation part
17
. This output data and the subkey k
i
are exclusive ORed in an XOR circuit
18
, whose output is transformed to 48-bit data E(R
i
)⊕k
i
, which is then split to eight pieces of 6-bit sub-block data. The eight pieces of sub-block data are input to different S-boxes S
0
to S
7
to derive therefrom a 4-bit output, respectively. Incidentally, the S-box S
j
(where j=0, 1, . . . , 7) is a nonlinear transformation table that transforms the 6-bit input data to the 4-bit output data, and is an essential part that provides security of DES. The eight pieces of output data from the S-boxes S
0
to S
7
are concatenated again to 32-bit data, which is applied to a permutation part
19
to provide the output f(R
i
, k
i
) from the function operation part
12
as shown in FIG.
2
. This output is exclusive ORed with L
i
to obtain R
i+1
.
Next, a description will be given of cryptanalysis techniques. A variety of cryptanalysis techniques have been proposed for DES and other traditional secret-key encryption algorithms; extremely effective cryptanalysis techniques among them are differential cryptanalysis proposed by E. Biham and A. Shmir, (“Differential Cryptanalysis of DES-like Cryptosystems,” Journal of Cryptology, Vol. 4, No. 1, pp.3-72) and 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
&Dgr;
X=X⊕X*,
differential cryptanalysis aims to obtain the subkey k
15
in the final round processing part
14
15
by applying to the following equations two sets of plaintext-ciphertext pair that an attacker possesses. In the encryption process of
FIG. 1
, let (L
i
, R
i
) and (L*
i
, R*
i
) represent input data into the round processing part
14
i
for first and second plaintexts respectively. With the difference defined as mentioned above, the following equations hold.
&Dgr;L
i
=L
i
⊕L*
i
&Dgr;R
i
=R
i
⊕R*
i
In
FIG. 1
, since L
15
=R
14
, L*
15
=R*
14
, L
16
=R
15
and L*
16
=R*
15
, the following equations hold
R
16
=L
15
⊕f
(
R
15
, k
15
)
R*
16
=L*
15
⊕f
(
R*
15
, k
15
)
and the exclusive OR of both sides of these two equations is obtained as follows:
&Dgr;
R
16
=&Dgr;L
15
⊕f
(
L
16
, k
15
)⊕
f
(
L
16
⊕&Dgr;L
16
,k
15
).
The exclusive ORing of its both sides with &Dgr;R
14
=&Dgr;L
15
gives the following equation:
 
f
(
L
16
, k
15
)⊕
f
(
L
16
&Dgr;L
16
, k
15
)=&Dgr;
R
16
⊕&Dgr;R
14
.
At this time, since L
16
, &Dgr;L
16
and &Dgr;R
16
are data available from the ciphertext, they are known information. Hence, if the attacker can correctly obtain &Dgr;R
14
, then only k
15
in the above equation is an unknown constant; the attacker can find a correct k
15
without fail by an exhaustive search for k
15
using the known sets of plaintext-ciphertext pair. Accordingly, once the subkey k
15
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 &Dgr;R
14
since this value is an intermediate difference value. Then, assume that each round processing is approximated by the following equations with a probability p
i
in the 0-th to the last round but one (i.e.; the 14-th):
&Dgr;R
i+1
=&Dgr;L
i
⊕&Dgr;{f
(&Dgr;
R
i
)&

Affiliated with

Also associated with

Rating

Data converter and recording medium on which program for... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data converter and recording medium on which program for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data converter and recording medium on which program for... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3205238