Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-01-19
2003-06-10
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C380S028000
Reexamination Certificate
active
06578061
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and apparatus for efficient implementation of data permutation and division processing in the field of cryptography and a recording medium with a data permutation/division program recorded thereon.
Data encryption is intended to conceal data. Data encryption techniques fall into a common key cryptosystem and a public key cryptosystem.
The public key cryptosystem uses different keys for data encryption and for decryption; usually, the encryption key is made public and the decryption key is held by a user in secrecy. It is believed that the description key could not be derived from the encryption key within a practical amount of time even with modern mathematical theories and the computing power of the present-day computer.
On the other hand, the common key cryptosystem uses the same key for data encryption and decryption. To implement a fast and secure common key cipher, there is proposed a block encipherment scheme that divides data to be enciphered into blocks of an appropriate length and enciphers them one by one. Many of the block ciphers have a structure called a Feistel network. With this structure, an input of 2n bits is divided to right and left pieces of n-bit data, a function f is operated on the right n-bit data, then its output is exclusive ORed with the left n-bit data, then the right and left pieces of data are swapped, and the same operation is repeated. This structure is shown in, “Bruce Schneier, Applied Cryptography, 2
nd
edition, John-Wiley and Sons, p347, 1996.”
The common key cryptosystem is smaller in computational complexity than the public key cryptosystem, and the amount of data that can be encrypted per unit time in the former cryptosystem is tens to hundreds of times larger than in the latter cryptosystem. For this reason, there are tendencies to use the common key cryptosystem when fast encryption processing is necessary.
The common key cryptosystem is required to have security against cryptanalysis as well as the above-mentioned high-speed performance. In recent years there have been proposed several methods of cryptanalysis for common key encryption algorithms. It is necessary, therefore, that a common key encryption algorithm to be newly developed be always secure against such cryptanalysis methods. These cryptanalysis methods are described, for example, in “Bruce Schneier, Applied Cryptography, 2nd edition, John-Wiley and Sons, pp.285-293, 1996.”
There have also been studied schemes that would not allow easy application of the cryptanalysis methods, and it can be expected that such preventive schemes will increase the security of the common key encryption algorithm. According to one of such preventive schemes, a value of some kind available from an encryption key is exclusive ORed with input and output data so as to protect the input and output data for the basic encryption, algorithm from an attacker. This scheme is described in “Bruce Schneier, Applied Cryptography, 2nd edition, John-Wiley and Sons, pp.366-367, 1996.” Many of common key encryption algorithms proposed in recent years are designed using this scheme.
With the above scheme, the input data exclusive ORed with the value of some kind available from the encryption key is used as input data of the basic encryption algorithm. In the case of using the afore-mentioned Feistel network, the input data needs to be divided to right and left data. Some of recently developed common key encryption algorithms are intended to provide increased security not only by dividing the input data to right and left but also by dividing the input data to right and left even after permutation. An example of such algorithms is an E2 cipher (Masayuki KANDA, et al., “A New 128-bit Block Cipher E2,” Technical Report of IEICE, ISEC98-12 (hereinafter referred to simply as literature E2). In the E2 algorithm, a permutation processing called a BP function is defined and then the input data is divided to right and left for input into the Feistel network.
FIG. 1
depicts a basic configuration of an E2 cryptographic device, in which no key scheduling part is shown for brevity. The E2 cryptographic device is made up of an initial transformation part
10
, twelve round processing stages RND
1
to RND
12
, and a final transformation part
30
. The size of each key is, for instance, 128-bit. The initial transformation part
10
comprises: an XOR operation part
11
that exclusive ORs an input plaintext M of, for example, 128 bits with a subkey k
13
; a multiplication part
12
that calculates the product of the output from the XOR operation part
11
and a subkey k
14
; and a byte permutation part (hereinafter referred to as a BP function part)
13
that performs byte permutation of the multiplied output from the multiplication part
12
. To increase the operation efficiency, setting the computation size of a CPU of the computer used, for example, at 32 bits, the operation is carried out for each of four 32-bit subblocks divided from the 128-bit data.
The initial transformation part (hereinafter referred to as an IT function part)
10
performs the following operation for an input X=M using the subkeys k
13
and k
14
.
A=IT
(
X, k
13
, k
14
) (1)
More specifically, letting
X=
(
x
1
, x
2
, x
3
, x
4
)
Y=
(
y
1
, y
2
, y
3
, y
4
)
Z=
(
z
1
, z
2
, z
4
, z
4
)
the following operation is performed by the XOR operation part
11
and the multiplication part
12
.
Z
=(
X⊕k
13
){circle around (×)}
k
14
=Y{circle around (×)}k
14
(2)
In the above, if k
14
=(K
1
, K
2
, K
3
, K
4
), the multiplication Y{circle around (×)}k
14
by the multiplication part
12
is performed as follows:
z
i
=y
i
(
K
i
1
(hex)
)mod 2
32
for
i=
1,2,3,4 (3)
The operation symbol a
b represents the OR of a and b for every corresponding bit. Setting
(
z
i
(1)
, z
i
(2)
, z
i
(3)
, z
i
(4)
)=
z
i
for
i=
1,2,3,4 (4)
Z′
=(
z
1
′, z
2
′, z
3
′, z
4
′)
The operation processing of the BP function part
13
is expressed by the following equation:
z
i
′=(
z′
i
(1)
, z′
i+1
(2)
, z′
i+2
(3)
, z′
i+3
(4)
), i=1,2,3,4, (5)
where
z′
i+4
(j)
=z′
i
(j)
, j=
1,2,3,4 (6)
where i represents the subblock number for each 32 bits and j the data number of each byte in the subblock. In
FIG. 3
there are shown permutations expressed by Eqs. (5) and (6). The four bytes of each piece of data z
1
, z
2
, z
3
and z
4
are distributed to four different output data groups.
The output from the byte permutation part (that is, the BP function part)
13
is divided to right data R
0
and left data L
0
, which are provided to the round processing stage RND
1
. The i-th round processing stage RND
i
performs substitution-permutation processing of right data R
i−1
in a round function part
22
by using a subkey k
i
, and provides the substitution result to an XOR operation part
21
, wherein it is exclusive ORed with left data L
i−1
fed thereto. The right data R
i−1
input to the i-th stage and the output from the XOR operation part
21
are exchanged in position, and they are provided as left data L
i
and right data R
i
to the next round processing stage RND
i+1
.
This is expressed as follows:
R
i
=L
i−1
⊕F
(
R
i−1
, k
i
) (7)
L
i
=R
i−1
, i
=1, 2, . . . , 12 (8)
Each round function part
22
comprises, as depicted in
FIG. 2
, eight XOR operation parts
22
X
1
, eight S-boxes (S function)
22
S
1
, a linear permutation part (a P function part)
22
P, eight XOR operation parts
22
X
2
, and eight S-boxes
22
S
2
. 64-bit right data R is input to the i-th round processing stage RND
i
. In the round function part
22
, setting the input R
i−1
R
i−1
=(
r
1
, r
2
, r
3
, r
4
, r
5
, r
6
, r
7
, r
8)
k
i
=(
K
Aoki Kazumaro
Kanda Masayuki
Ueda Hiroki
Connolly Bove & Lodge & Hutz LLP
Mai Tan V.
Nippon Telegraph and Telephone Corporation
LandOfFree
Method and apparatus for data permutation/division and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for data permutation/division and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for data permutation/division and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3108586