Cryptography – Communication system using cryptography – Symmetric key cryptography
Reexamination Certificate
1998-02-04
2001-02-20
Barrón, Jr., Gilberto (Department: 2767)
Cryptography
Communication system using cryptography
Symmetric key cryptography
C380S037000, C380S029000
Reexamination Certificate
active
06192129
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to cryptography, and deals more particularly with a symmetric key cipher for encryption and decryption, using a block cipher algorithm. This algorithm allows the block size, key size, and number of rounds of ciphering to vary.
2. 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”.
Mathematical algorithms are used to describe the functioning of ciphers. The goal of a cipher is to be computationally infeasible to “break”—that is, it must be nearly impossible to “guess” or derive the original data content from any series of computations that can be performed on the transformed data, absent knowledge of how the encryption was accomplished. Use of a “key” during the encryption and decryption processes helps make the cipher more difficult to break. A key is a randomly-generated number factored into operation of the encryption to make the result dependent on the key. The value used for the key in effect “personalizes” the algorithm, so that the same algorithm used on the same input data produces a different output for each different key value. When the value of this key is unknown to the unauthorized persons, they will not be able to duplicate or to reverse the encryption. Provided that the key is kept secret, the algorithm that performs the ciphering can be made public. The key will be known to the parties intended to encrypt and decrypt the data: they can use the key to “lock” and “unlock” the data contents, whereas unauthorized persons cannot. When the same key is used for encrypting and for decrypting, the key is referred to as being “symmetric”.
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.
A commonly used cipher is known as the Data Encryption Algorithm (“DEA”). This algorithm was developed by scientists of the International Business Machines Corporation (“IBM”), and formed the basis of a United States federal standard known as the Data Encryption Standard (“DES”), which was adopted in 1977. DES has been in use since that time. A variant of the DES algorithm, known as “Triple DES”, was developed to increase the strength of the result over that available with DES. Triple DES uses three rounds of ciphering, with different keys for each of the rounds.
After twenty years, many believe that a new stronger, more flexible algorithm is needed. One way to make a cipher stronger is to increase the number of rounds of ciphering performed: with each successive transformation, the resulting encryption becomes more difficult to break. Another way to increase the strength is to increase the size of the key. Since the contents of the key remain secret, increasing the size adds another level of difficulty for anyone trying to deduce what transformations may have been performed on the original data, because they are unlikely to guess the random number combination making up the key. Yet another way to increase algorithm strength is to increase the size of the “block” on which the cipher performs its transformations. A block is the unit of original data processed during one ciphering operation. The larger the block size, the more difficult it becomes for an adversary to construct a dictionary of plaintext and matching ciphertext, for a given key, large enough to pose a threat to the security of the algorithm. Further, different keys can be used for each round, increasing the number of random number combinations that would have to be correctly guessed in order to break the cipher. These keys are referred to herein as “sub-keys”.
It will be appreciated that when a cipher allows varying the number of rounds, the key size, the key values, and the block size at the same time, an incredibly difficult challenge is presented to a person attempting to discover the original data contents from an encrypted result. It will also be appreciated that the computations involved to cipher the data are quite complex, and that while performing more rounds of ciphering increases the strength of the result, it also causes computation time to increase. When data is very sensitive, this time spent in ciphering will be warranted. It may be, however, that less sensitive data does not warrant the added time and expense of many rounds of ciphering. By providing an algorithm where the number of rounds, the key size and values, and the block size are variable, the ultimate choice between the level of security required and the amount of computation time utilized rests with the user. By allowing the number of rounds, key size, and block size to vary, the cipher of the present invention becomes, in effect, scalable in three dimensions.
The existing DES and Triple DES algorithms use the secret key approach described above, but do not provide for variation in the key size, the block size, or the number of rounds of ciphering. As stated earlier, it is desired to have a more flexible, scalable algorithmic solution, that increases the strength of the result.
Accordingly, a need exists for an improved and more flexible cryptographic algorithm. More particularly, a need exists for a method and apparatus for an improved cryptographic algorithm that is block-oriented and uses a secret key. The cipher should use a variable length key, a variable length block, and a variable number of rounds. The cipher should provide for use of a different key during each round, and the key should be symmetric. The technique of the present invention achieves these objectives while using the simple operations of table lookup, exclusive OR, and key-dependent substitution, thereby minimizing the time required to encrypt and decrypt data. The data-independent sub-keys can be precomputed, further minimizing the time required for encryption and decryption. A minimal amount of computer storage is required for data used in the operation of the algorithm.
SUMMARY
Coppersmith Don
Gennaro Rosario
Halevi Shai
Jutla Charanjit S.
Matyas, Jr. Stephen M.
Barron Jr. Gilberto
Doubet Marcia L.
International Business Machines - Corporation
Ray-Yarletts Jeanine S.
LandOfFree
Method and apparatus for advanced byte-oriented symmetric... 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 advanced byte-oriented symmetric..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for advanced byte-oriented symmetric... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2609367