Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1999-12-29
2001-10-16
Hayes, Gail (Department: 2131)
Cryptography
Particular algorithmic function encoding
C380S029000, C380S259000
Reexamination Certificate
active
06304657
ABSTRACT:
This application is based on an application No. H11-146079 filed in Japan, the content of which is hereby incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a data encryption apparatus and method, and in particular relates to a data encryption technique that employs shift-rotations.
2. Description of the Prior Art
With the rapid proliferation of digital communications in recent years, there has been the growing demand for highly secure data cryptosystems that can ensure confidentiality of data in communication, for the sake of development of sound industries and privacy protection. Not only high security but also high cryptographic speed and easy implementation in hardware and software are required of such cryptosystems.
First Conventional Technique
A pseudorandom number additive cipher is introduced below as the first example of conventional data cryptosystems.
In this cipher, the transmitter and the receiver share a secret key (hereinafter simply referred to as a “key”). Plaintext data M is divided into plaintext data blocks Mi of fixed length, and random number data R of the fixed length is generated for each plaintext data block Mi using the key as a seed.
Following this, an exclusive-OR operation is performed for corresponding bits in each plaintext data block Mi and the random number data R to generate a ciphertext data block Ci. This operation is expressed as
Ci=Mi(+)R
where “(+)” denotes an exclusive-OR operation for corresponding bits.
Lastly, generated ciphertext data blocks Ci are linked together to form ciphertext data C.
This cipher can perform extremely fast encryption and therefore lends itself for cryptographic processing in real-time image and audio data communications.
However, the level of security afforded by the cipher is quite low. Given that the same key is used for all plaintext data blocks Mi, acquiring a pair of plaintext data block Mi and ciphertext data block Ci enables an unauthorized party to derive the random number data R from the following equation, as a result of which the other ciphertext data blocks Ci will be broken.
R=Mi(+)Ci
Second Conventional Technique
A block cipher is presented below as the second example of conventional data cryptosystems. Representatives of block ciphers are the Data Encryption Standard (DES) and the Fast Data Encipherment Algorithm (FEAL). For details on DES and FEAL, see Eiji Okamoto,
An Introduction to Encryption Theory
, Kyoritsu (1993).
Block ciphers handle 64-bit input and output data with their strong data shuffling abilities. One of such block ciphers is the MULTI2 cipher disclosed in Japanese Laid-Open Patent Application No. H1-276189.
FIG. 1
is a block diagram showing the construction of a data converting unit
40
as one of three data converting units equipped in a data encryption apparatus that employs the MULTI2 cipher.
This data converting unit
40
is roughly made up of a key adding unit
401
, a first data substituting unit
402
, and a second data substituting unit
403
, and converts 32-bit input data A to 32-bit output data D based on 32-bit subkey data Ki.
To be more specific, once the input data A and the subkey data Ki have been inputted in the key adding unit
401
, the key adding unit
401
performs an arithmetic addition modulo 23
2
on the input data A and subkey data Ki and outputs the result as 32-bit data B. This is expressed as
B=(A+Ki) mod 2
32
where “+” denotes an arithmetic addition and “&agr; mod &bgr;”
0
denotes the remainder after dividing &agr; by &bgr;.
The first data substituting unit
402
receives the data B from the key adding unit
401
and performs an arithmetic addition modulo 2
32
for data Rot2(B) obtained by shift-rotating the data B by 2 bits toward higher-order bit positions, the data B itself, and constant data “1”. As a result, 32-bit data C is obtained. This can be written as
C=(Rot2(B)+B+1) mod 2
32
where “Rot&agr;(X)” denotes a shift-rotation of 32-bit data X by &agr; bits toward higher-order positions (and its result).
The second data substituting unit
403
receives the data C outputted from the first data substituting unit
402
and takes an exclusive-OR for corresponding bits in the data C and data Rot4(C) obtained by shift-rotating the data C by 4 bits toward higher-order positions, thereby generating the 32-bit output data D. This is expressed as
D=Rot4(C) (+)C
Consequently, the 32-bit data D is outputted from the data converting unit
40
.
Thus, the conventional data converting unit
40
performs data shuffling at high speed through the use of operations combined with various shift-rotations.
Nevertheless, the data converting unit
40
has the following security problems.
Suppose input data M1 and input data M2 that satisfy the relationship
M1(+)M2=55555555h
are each inputted in the second data substituting unit
403
, “h” representing hexadecimal notation.
Then
Rot4(M1)(+)Rot4(M2)=Rot4(M1(+)M2)
due to linearity of the shift-rotation.
Also
Rot4(55555555h)=55555555h
since the data “55555555h” per se is symmetric.
Hence the equation
Rot4(M1)(+)Rot4(M2)=55555555h
holds.
Accordingly
Rot4(M1)(+)M1(+)Rot4(M2)(+)M2=000000000h
i.e.
Rot (M1)(+)M1=Rot4(M2)(+)M2
is true.
Which is to say, the output data generated from the input data M1 will be identical to the output data generated from the input data M2 in the second data substituting unit
403
. This signifies that the conversion performed by the second data substituting unit
403
is not a bijection (that is both a surjection and an injection). Therefore, the overall conversion by the data converting unit
40
is not a bijection.
FIG. 2
illustrates the property of the mapping in the second data substituting unit
403
(i.e. the data converting unit
40
) that is a non-bijective map. In the figure, two different input values in the domain X are being mapped to the same output value in the range Y.
Such a property of the data converting unit
40
is undesirable in terms of cryptographic security, because a decrease in the number of elements of the range Y as compared with the number of elements of the domain X renders the data shuffling strength of the data converting unit
40
deficient.
Here, it may be conceivable to modify the second data substituting unit
403
in such a way that instead of “Rot4(X) (+)X” it outputs the data Rot2(X) obtained by shift-rotating the input data X by 2 bits toward higher-order positions, so as to make the conversion by the second data substituting unit
403
bijective.
However, such a conversion Rot2(X) lacks a desired degree of security, since it will not produce a sufficient bit avalanche effect. The bit avalanche effect referred to here is the observed property of a cipher on how many bits in the output data change as a result of the change of a single bit in the input data.
SUMMARY OF THE INVENTION
In view of the above problems, the present invention aims to provide a data encryption apparatus and method which employ shift-rotations to perform such a data conversion that is a bijection with a strong data shuffling ability and that produces a sufficient bit avalanche effect.
To fulfill the stated object, the data encryption apparatus of the present invention is a data encryption apparatus for encrypting n-bit plaintext data to obtain n-bit ciphertext data, the data encryption apparatus including: a shift-rotating unit for generating k sets of data by shift-rotating the n-bit plaintext data respectively by S
1
bits, S
2
bits, . . . , and Sk bits, S
1
, S
2
, . . . , and Sk being nonnegative integers less than n, and k being an odd number no less than 3; and a data combining unit for combining together the k sets of data to generate the n-bit ciphertext data.
With this construction, the data encryption apparatus first converts the plaintext data into an odd number of sets of data no fewer than 3 by means of shift-rotations and then combines the sets
Miyaji Atsuko
Ohmori Motoji
Yokota Kaoru
Hayes Gail
Leaning Jeffrey S.
Matsushita Electric - Industrial Co., Ltd.
Price and Gess
LandOfFree
Data encryption apparatus using odd number of... 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 encryption apparatus using odd number of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data encryption apparatus using odd number of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2570432