Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1998-06-15
2001-07-31
Peeso, Thomas R. (Department: 2767)
Cryptography
Particular algorithmic function encoding
C380S001000, C380S042000, C380S043000, C380S037000, C380S028000, C380S029000
Reexamination Certificate
active
06269163
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to cryptography, and more particularly to block ciphers for implementing encryption and decryption operations in cryptographic applications.
BACKGROUND OF THE INVENTION
In a conventional block cipher cryptographic system, a plaintext message is encrypted using a secret key, and is transmitted in its encrypted form. A receiver decrypts the encrypted message using the same secret key in order to recover the plaintext message. An example of a conventional block cipher is the Data Encryption Standard (DES) cipher. DES and other conventional block ciphers are described in B. Schneier, Applied Cryptography, pp. 154-185 and 219-272, John Wiley & Sons, New York, 1994, which is incorporated by reference herein. An improved block cipher utilizing data-dependent rotations is described in U.S. Pat. No. 5,724,428, issued Mar. 3, 1998 in the name of inventor R. L. Rivest, which is incorporated by reference herein. This improved cipher is referred to as RC5™, which is a trademark of RSA Data Security, Inc. of Redwood City, Calif., the assignee of U.S. Pat. No. 5,724,428. The RC5™ block cipher in an illustrative embodiment provides improved performance in part through the use of data-dependent rotations in which a given word of an intermediate encryption result is cyclically rotated by an amount determined by low-order bits of another intermediate result.
The security of the RC5™ block cipher is analyzed in, for example, in B. S. Kaliski Jr. and Y. L. Yin, “On Differential and Linear Cryptanalysis of the RC5™ Encryption Algorithm,” in D. Coppersmith, ed., Advances in Cryptology—Crypto '95, Vol. 963 of Lecture Notes in Computer Science, pp. 171-184, Springer Verlag, 1995; L. R. Knudsen and W. Meier, “Improved Differential Attacks on RC5™,” in N. Koblitz, ed., Advances in Cryptology—Crypto '96, Vol. 1109 of Lecture Notes in Computer Science, pp. 216-228, Springer Verlag, 1996; A. A. Selcuk, “New Results in Linear Cryptanalysis of RC5™,” in S. Vaudenay, ed., Fast Software Encryption, Vol. 1372 of Lecture Notes in Computer Science, pp. 1-16, Springer Verlag, 1998; and A. Biryukov and E. Kushelevitz, “Improved Cryptanalysis of RC5™,” to appear in proceedings of Advances in Cryptology—Eurocrypt '98, Lecture Notes in Computer Science, Springer Verlag, 1998; all of which are incorporated by reference herein. These analyses have provided a greater understanding of how the structure and operations of RC5™ contribute to its security. Although no practical attack on RC5™ has been found, the above-cited references describe a number of interesting theoretical attacks.
It is therefore an object of the present invention to provide a further improved block cipher which not only exhibits additional security by thwarting one or more of the above-noted theoretical attacks, but also exhibits an enhanced implementability in a wide variety of cryptographic applications.
SUMMARY OF THE INVENTION
The present invention provides an improved block cipher in which data-dependent rotations are influenced by an additional primitive operation which is in the form of an integer multiplication. The use of such an integer multiplication greatly increases the diffusion achieved per round of encryption, allowing for higher security per round, and increased throughput. The integer multiplication is used to compute rotation amounts for data-dependent rotations, such that the rotation amounts are dependent on substantially all of the bits of a given register, rather than just low-order bits as in the above-described embodiment of the RC5™ block cipher.
In an illustrative embodiment of the invention, a plaintext message to be encrypted is segmented into four words stored in registers A, B, C and D, and an integer multiplication function is applied to two of the words in registers B and D. The integer multiplication function may be a quadratic function of the form ƒ(x)=x(ax+b), where a is an even integer and b is an odd integer. Other types of functions, including polynomials with degree greater than two, may be used in alternative embodiments. The results of the integer multiplication function in the illustrative embodiment are rotated by lg w bits, where lg denotes log base
2
and w is the number of bits in a given word, to generate a pair of intermediate results t and u. An exclusive-or of the contents of another register, e.g., A, and one of the intermediate results, e.g., t, is rotated by an amount determined by the other intermediate result u. Similarly, an exclusive-or of the contents of the remaining register D and the intermediate result u is rotated by an amount determined by the other intermediate result t. An element of a secret key array is applied to each of these rotate results, and the register contents are then transposed. This process is repeated for a designated number of rounds to generate a ciphertext message. Pre-whitening and post-whitening operations may be included to ensure that the input or output does not reveal any internal information about any encryption round. For example, the values in registers B and D may be pre-whitened before starting the first round by applying elements of the secret key array to these values. Similarly, the values in registers A and C may be post-whitened after completion of the designated number of rounds by applying elements of the secret key array to these values. Corresponding decryption operations may be used to recover the original plaintext message.
REFERENCES:
patent: 4078152 (1978-03-01), Tuckerman, III
patent: 4157454 (1979-06-01), Becker
patent: 4249180 (1981-02-01), Eberle et al.
patent: 4255811 (1981-03-01), Adler
patent: 4724541 (1988-02-01), Mallick
patent: 4982429 (1991-01-01), Takaragi et al.
patent: 5003597 (1991-03-01), Merkle
patent: 5054067 (1991-10-01), Moroney et al.
patent: 5214704 (1993-05-01), Mittenthal
patent: 5297206 (1994-03-01), Orton
patent: 5351299 (1994-09-01), Matsuzaki et al.
patent: 5454039 (1995-09-01), Coppersmith et al.
patent: 5675653 (1997-10-01), Nelson, Jr.
patent: 5724428 (1998-03-01), Rivest
patent: 5740250 (1998-04-01), Moh
patent: WO 91/18459 (1991-11-01), None
Biryukov, Alex et al., “Improved Cryptanalysis of RC5,” 8 pages presented at Eurocrypt '98, May 31-Jun. 4, 1998, http://www.cs.technion.ac.il/~eyalk/pub.html.
Kaliski, Jr., B. et al., “On Differential and Linear Cryptanalysis of RC5 Encryption Algorithm,” pp. 171-184, in D. Coppersmith ed.,Advances in Cryptology—CRYPTO '95, LNCS No. 963, 1995.
Knudsen, L. et al., “Improved Differential Attacks of RC5,” pp. 216-228, presented at CRYPTO '96, Aug. 18-22, 1996, http://www.cs.technion.ac.il/~/pub.html.
Madryga, W.E., “A High Performance Encryption Algorithm,” in J. H. Finch and E.G. Dougall eds.,Computer Security: A Global Challenge, pp. 557-570, 1984.
Matsui, Mitsuru, “Linear Cryptanalysis Method for DES Cipher,” in T. Helleseth ed.,Advances in Cryptology—Eurocrypt '93, pp. 386-396, 1994.
Rivest, Ronald, “The RC5 Encryption Algorithm,”Dr. Dobb's Journal, Jan. 1995, pp. 146-148.
Rivest, Ronald, “The RC5 Encryption Algorithm,” 11 pages, inFast Software Encryption, Second International Workshop, pp. 86-96, 1995.
Rivest, Ronald, et al., “The RC6™ Block Cipher,” pp. 1-20, http://theory.lcs.mit.edu/~rivest/publications.html, downloaded Jun. 19, 1998.
Rivest, Ronald, “Further Notes on RC6, Last updated Jun. 20, 1998,” 1 page http://theory.lcs.mit.edu/~rivest/publications.html, downloaded Sep. 25, 1998.
Selcuk, Ali Aydin, “New Results in Linear Cryptanalysis of RC5,” pp. 1-16, Fast Software Encryption Conference, Paris, Mar. 1998.
Schneier, Bruce, “Applied Cryptography, Protocols, Algorithms, and Source Code in C,” John Wiley & Sons, Inc., 1994, pp. 154-185; 219-272.
Rivest Ronald L.
Robshaw Matthew John Barton
Sidney Raymond Mark
Yin Yiqun Lisa
Jack Todd
Peeso Thomas R.
RSA Security Inc.
Testa Hurwitz & Thibeault LLP
LandOfFree
Enhanced block ciphers with data-dependent rotations does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced block ciphers with data-dependent rotations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced block ciphers with data-dependent rotations will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2476005