Electrical computers and digital processing systems: support – Data processing protection using cryptography
Reexamination Certificate
2000-03-31
2004-05-04
Wright, Norman M. (Department: 2134)
Electrical computers and digital processing systems: support
Data processing protection using cryptography
C713S152000, C713S168000, C380S029000, C380S030000
Reexamination Certificate
active
06732271
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a cryptosystem in which ciphering/deciphering at one block influences ciphering/deciphering at the next block, for example, in as a CBC (Cipher Block Chaining) mode or a CFB (Cipher Feedback) mode, and more particularly to a method of deciphering ciphered data at high speed and an apparatus therefor.
Encryption is one of fundamental techniques for protecting data flowing on a data communications network or data stored in a computer system, and it means conversion of data so that a third party cannot use the data illegally. When data is transmitted, “encryption” is performed at a transmission side to change a common communication message “plaintext” into a “ciphertext” which cannot be read directly. At the reception side, “decryption” is performed to recover the original plaintext from the ciphertext. In this case, a parameter for controlling enciphering and deciphering is called a “key”. By using this key, the reception side can easily decipher the ciphertext.
In cipher communications, it is important that a cipher strength is high, i.e., the communications contents are hard to be deciphered by a third party and that enciphering and deciphering can be executed at high speed in order not to make ordinary senders and receivers feel any practical trouble.
DES (Data Encryption Standard) is a cryptosystem most widely prevailed in the fields of data communications. DES is not only used with a standard data cryptosystem by institutes of the federal government of the U.S. but also is widely prevailing in private organizations. DES provides such a cryptosystem that a plaintext is divided into blocks each having 64 bits and a plaintext of 64 bits is enciphered by using a key of 56 bits to form a ciphertext of 64 bits. In order to realize this, a main portion (cipher core portion) of a DES cipher mechanism is constituted of 16-round DES cipher stages which output a ciphertext of 64 bits by dividing a plaintext of 64 bits into a 32-bit portion and another 32-bit portion and by sequentially generating keys K
1
to K
16
of 48 bits from a key of 56 bits to repeat a permutation process sixteen times.
The American National Standards Institute (ANSI) defines four operation modes of DES (Specification: ANSI X3. 106-1983). Namely, these modes are an ECB (Electronic Codebook) mode, a CBC (Cipher Block Chaining) mode, a CFB (Cipher Feedback) mode, and an OFB (Output Feedback) mode. Of these modes, the ECB mode ciphers each set of 64 bits independently. Therefore, the ECB mode can perform parallel processing with a plurality of DES cipher operators or pipelining a DES cipher operator, so that although the ECB mode can execute enciphering/deciphering at higher speed than the other three modes, the cipher strength is lower. On the other hand, in the CBC, CFB and OFB modes, enciphering/deciphering of one block influences enciphering/deciphering of the next block. Namely, the result of the previous enciphering/deciphering is reflected as a chaining value. By using this chaining value, the next enciphering/deciphering is performed. Therefore, although the cipher strength becomes higher than the ECB mode, parallel processing cannot be effectively utilized so that a high speed operation is more difficult than the ECB mode.
Generally, in all the modes of ECB, CBC, CFB and OFB for DES enciphering and deciphering, a long processing time is taken by 16-round DES cipher stages which are a nuclei of the cryptosystem, and a very short processing time relative to that by the 16-round DES cipher stages is taken by the processes to be executed before and after the operations by the 16-round DES cipher stages. According to a conventional speed-up approach, a process requiring a short process time other than the process by the DES cipher stages is speeded up to speed up the DES cipher mechanism. For example, the publication of JP-A-10-74044 discloses a method of outputting enciphered/deciphered data to an output register after a proper number of cycles after data is input to the cipher stage. With this method, it becomes possible to operate a circuit portion other than the DES cipher stages at a higher clock frequency than that corresponding to the processing time taken by the DES cipher stages. Enciphering and deciphering can therefore be executed at high speed in all the operation modes of the DES cipher mechanism.
However, in conventional deciphering in the CBC and CFB modes (also in the OFB mode), ciphertext data A is sequentially transited to an input data generation stage, to a cipher core portion execution stage, and to an output data and chaining value generation stage, and thereafter by using a generated chaining value, next ciphertext data B is sequentially transited in a similar manner to the input data generation stage, to the cipher core portion execution stage, and to the output data and chaining value generation stage. It is therefore impossible to make a plaintext output interval shorter than a cipher core portion execution time.
More specifically, if a clock frequency is raised, it is possible to shorten the time from when plaintext data is input to when ciphertext data is output, or the time from when ciphertext data is input to when plaintext data is output. However, in the CBC, CFB and OFB modes hard to execute parallel processing, data throughput has an upper limit corresponding to the throughput of the DES cipher stages which take the longest processing time in the DES cipher mechanism.
SUMMARY OF THE INVENTION
Of the CBC, CFB and OFB modes, only the OFB mode requires output data of the cipher core portion in order to generate the chaining value for next calculation of deciphering, and the CBC and CFB modes do not require output data of the cipher core portion in order to generate the chaining value because these modes incorporate the algorithm that the chaining value for next calculation is generated from input data and/or a previous chaining value. The present invention therefore pays attention to the algorithm of the CBC and CFB modes and provides a method and apparatus for improving data throughput for deciphering in the CBC and CFB modes.
According to the present invention, in deciphering in the CBC and CFB modes of a DES cipher mechanism or the like, while cipher data is deciphered, a chaining value necessary for deciphering next cipher data is generated in advance. It is therefore possible for one or more DES operators to continuously decipher data or decipher a plurality set of data at the same time, to thereby provide an improved data throughput. Generally, a time taken to generate a chaining value for deciphering next data is very short as compared to the execution time taken by 16-round DES cipher stages. Therefore, by generating a chaining value at a proper timing, if one DES operator can execute one deciphering process at a time, for example, two DES operators ensure a two-fold throughput.
The invention is not limited only to the DES cipher mechanism but is applicable to various cipher mechanisms having an operation mode such as CBC mode and CFB mode not requiring output data of the cipher core portion in order to generate the chaining value for next calculation.
REFERENCES:
patent: 6324286 (2001-11-01), Lai et al.
patent: 6504930 (2003-01-01), Enari
patent: 6542607 (2003-04-01), Euchner et al.
Hirayama Naoki
Oguni Satoshi
Sako Kazuhiko
Tamura Takushi
Antonelli Terry Stout & Kraus LLP
Hitachi , Ltd.
Wright Norman M.
LandOfFree
Method of deciphering ciphered data and apparatus for same 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 of deciphering ciphered data and apparatus for same, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of deciphering ciphered data and apparatus for same will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3249263