Electrical computers and digital processing systems: support – Multiple computer communication using cryptography
Reexamination Certificate
1998-02-23
2001-02-06
Hayes, Gail O. (Department: 2766)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
C380S037000
Reexamination Certificate
active
06185679
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Related Invention
IBM application Ser. No. 09/027,765 entitled “Method and Apparatus for a Symmetric Block Cipher using Multiple Stages”, filed Feb. 23, 1998.
2. Field of the Invention
The present invention relates to cryptography, and deals more particularly with a system and method for a symmetric key block cipher. This cipher uses multiple stages, where the stages have different structures and different subround functions. The cipher allows the block size, key size, and number of rounds per stage of ciphering to vary.
3. Description of the Related Art
Cryptography is a security mechanism for protecting information from unintended disclosure by transforming the information into a form that is unreadable to humans, and unreadable to machines that are not specially adapted to reversing the transformation back to the original information content. The cryptographic transformation can be performed on data that is to be transmitted electronically, such as an electronic mail message, and is equally useful for data that is to be securely stored, such as the account records for customers of a bank or credit company.
In addition to preventing unintended disclosure, cryptography also provides a mechanism for preventing unauthorized alteration of data transmitted or stored in electronic form. After the data has been transformed cryptographically, an unauthorized person is unlikely to be able to determine how to alter the data, because the specific data portion of interest cannot be recognized. Even if the unauthorized user knew the position of the data portion within a data file or message, this position may have been changed by the transformation, preventing the unauthorized person from merely substituting data in place. If an alteration to the transformed data is made by the unauthorized user despite the foregoing difficulties, the fact of the alteration will be readily detectable, so that the data will be considered untrustworthy and not relied upon. This detection occurs when the transformation is reversed: the encrypted data will not reverse to its original contents properly if it has been altered. The same principle prevents unauthorized addition of characters to the data, and deletion of characters from the data, once it has been transformed.
The transformation process performed on the original data is referred to as “encryption”. The process of reversing the transformation, to restore the original data, is referred to as “decryption”. The terms “encipher” and “decipher” are also used to describe these processes, respectively. A mechanism that can both encipher and decipher is referred to as a “cipher”.
Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption operation on a plaintext input block, using an encryption key, to produce a ciphertext output block. “Plaintext” refers to the fact that the data is in plain, unencrypted form. “Ciphertext” indicates that the data is in enciphered, or encrypted, form. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the original plaintext block.
A cipher to be used in a computer system can be implemented in hardware, in software, or in a combination of hardware and software. Hardware chips are available that implement various ciphers. Software algorithms are known in the art as well.
Encryption systems fall into two general categories. Symmetric (or secret key) encryption systems use the same secret key for both encrypting and decrypting messages. An example of a symmetric encryption system is the Data Encryption Standard (DES) system, which is a United States federal standard described in NBS FIPS Pub 46. In the DES system, a key having 56 independently specifiable bits is used to convert 64-bit plaintext blocks to ciphertext blocks, or vice versa.
Asymmetric (or public key) encryption systems, on the other hand, use different keys that are not feasibly derivable from one another for encryption and decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver's public key. Only the receiver may decrypt the message, however, since only he has the private key. Perhaps the best-known asymmetric encryption system is the RSA encryption system, named after its originators Rivest, Shamir, and Adleman.
The category of symmetric encryption systems can be further subdivided into those which operate on fixed size blocks of data (block ciphers), and those which operate on arbitrary length streams of data (stream ciphers).
While there are many methods of symmetric key block encryption, most popular methods (for example, DES, CAST, RC5, and Blowfish) are based on Type-2 Feistel Networks. A Type-2 Feistel Network consists of dividing the data to be encrypted into two halves, and then performing some number of rounds, where each round consists of transforming the left half of the data based on the right half of the data, and then transforming the right half based on the modified left half. The two transformations are called subrounds; in the case of RC5, for example, there are two subrounds in each of 16 full rounds. These transformations must be invertible. That is, it must be possible to perform some set of operations during decryption that will reverse the transformations performed during encryption. In a standard Feistel network, some non-invertible function of one half of the data is simply exclusive-OR'd with the other half, as the exclusive OR operation provides invertibility, but any invertible function may be used in the general case.
Feistel Networks are not limited to this case of dividing the data into two equal halves. Alternatively, in a Type-1 Feistel the data is divided into n equal words, where n>2. If these words are labeled A(
1
) to A(n), then a full round consists of n subrounds, where each subround consists of transforming word A(i) based on the value of word A(i−1) (with A(
1
) transformed by A(n)).
Similarly, a Type-3 Feistel can be constructed in which the data is divided into n equal words, where n>2, but in which each word is used to transform more than one (possibly all) of the other words. For example, A(
1
) could be used to transform A(
2
), A(
3
), and A(
4
) in one subround. A full round consists of n such subrounds.
Feistel based ciphers typically add additional invertible transformations before, and/or after, each full round. For example, some ciphers exclusive or the entire data block with subkey data before the first round, to complicate certain attacks. “Subkey” refers to using a different key during different rounds, where the subkey values are derived from an input key.
The distinguishing features of different Feistel based ciphers are determined by the choice of the function used to modify a given data word in each subround. Different functions provide different tradeoffs between speed, data size, and security.
Many ciphers, such as DES and CAST, base their subround functions on a construct called a substitution box, or S-box, which is an array of data elements. In operation, a cipher block data word is used as an index into the S-box, and the value at that location is then used as the output value. The entries in the S-box are carefully chosen to have good properties for resistance to various attacks, including differential and linear analysis. Some desirable properties of S-boxes include that if the input words vary by one bit, on average, half the output bits should change, so that even small changes in the input data rapidly spread to all the output bits. Also, the entries in the S-box should be chosen to have little correlation to the index, to provide good resistance to linear attacks. While S-box based functions may provide excellent security, they tend to be slow in software implementation
Coppersmith Don
Gennaro Rosario
Halevi Shai
Jutla Charanjit S.
Matyas, Jr. Stephen M.
Doubet Marcia L.
Hayes Gail O.
International Business Machines - Corporation
Ray-Yarletts Jeanine S.
Seal James
LandOfFree
Method and apparatus for a symmetric block cipher using... 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 a symmetric block cipher using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for a symmetric block cipher using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2604762