Cryptography – Communication system using cryptography – Time segment interchange
Reexamination Certificate
1998-06-12
2001-10-09
Barron, Jr., Gilberto (Department: 2131)
Cryptography
Communication system using cryptography
Time segment interchange
C380S259000, C380S029000
Reexamination Certificate
active
06301362
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method and apparatus for cryptographically transforming an input block into an output block and, more particularly, to a method and apparatus for encrypting or decrypting an input block using a symmetric block encryption procedure.
2. Description of the Related Art
Cryptographic 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. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the plaintext block.
Encryption systems fall into two general categories: asymmetric encryption systems and symmetric encryption systems. Asymmetric (or public key) encryption systems 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 privately 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 and described in B. Schneier,
Applied Cryptography
(1996), pages 466-474, incorporated herein by reference.
Symmetric (or private key) encryption systems, on the other hand, use the same secret key for both encrypting and decrypting messages. Although symmetric encryption systems require some secure means for distributing or agreeing upon secret encryption keys, they continue to be preferred for many applications because of their relative computational efficiency.
Perhaps the best-known symmetric encryption system is the Data Encryption Algorithm (DEA), implementing the Data Encryption Standard (DES) as described in the National Institute of Standards and Technology (NIST) publications “Data Encryption Standard (DES)”, FIPS PUB 46-2 (1980), and “DES Modes of Operation”, FIPS PUB 81 (1988). In the DES system, a 64-bit key is used to transform a plaintext message comprising one or more 64-bit plaintext blocks into a ciphertext message comprising a like number of 64-bit ciphertext blocks, or vice versa. (56 bits of the key are independently specifiable, while the remaining 8 bits provide a parity check.)
As described in the latter FIPS publication, there are several defined modes of DES encryption. In the Electronic Codebook (ECB) mode, each plaintext block is encrypted independently of any other plaintext block. In the Cipher Block Chaining (CBC) mode of operation, on the other hand, each plaintext block is XORed with the previous ciphertext block (or with an initialization vector in the case of the first block) before being encrypted to hide plaintext patterns and thus provide more resistance to certain types of cryptanalytic attacks.
At the time of its initial promulgation, the 56-bit key length and 64-bit block length of DES were thought to provide adequate protection against cryptographic attacks, including key exhaustion attacks based upon systematically testing all possible keys and dictionary attacks based upon building a “dictionary” of corresponding plaintext and ciphertext blocks. However, continued advances in computing speed make such brute-force attacks increasingly more feasible.
The National Institute of Standards and Testing (NIST) has called for a complete replacement of DES, to be deployed sometime in the future. In the meantime, however, there is a significant investment by users in cryptographic hardware and software based on DES. Any replacement cryptosystem that is deployed in the interim would desirably build upon this existing DES infrastructure.
SUMMARY OF THE INVENTION
One object of the present invention is to provide a symmetric-key block encryption system that is compact.
Another object of the present invention is to provide a symmetric-key block encryption system that is highly resistant to cryptographic attacks, including key exhaustion attacks and dictionary attacks.
Another object of the present invention is to provide a symmetric-key block encryption system whose cryptographic strength can be readily evaluated.
Another object of the present invention is to provide a symmetric-key block encryption system that uses independent design components to achieve each of its goals.
Another object of the present invention is to provide a symmetric-key block encryption system that is compatible with existing cryptographic hardware and software.
In general, the present invention uses a non-secret mixing function surrounded by two strong substitution functions. In effect, the substitution functions hide the mixing function so that manipulation of the bits supplied to or generated by the mixing function should be difficult.
More particularly, the present invention contemplates a method and apparatus for cryptographically transforming an input block into an output block. The input block has a first block size and is partitionable into a plurality of input subblocks having a second block size that is a submultiple of the first block size. To encrypt or decrypt, the input subblocks are passed through respective first substitution functions controlled by one or more keys to generate a first plurality of modified subblocks. The first plurality of modified subblocks are then passed through a mixing function to generate a second plurality of modified subblocks, each of which depends on each of the first plurality of modified subblocks. Finally, the second plurality of modified subblocks are passed through respective second substitution functions controlled by one or more keys to generate a plurality of output subblocks that are combinable into an output block.
In a preferred implementation, the input block is a 256-bit block that is partitioned into four 64-bit subblocks that are passed through the respective substitution functions. Each substitution function in the preferred embodiment is realized by four modular arithmetic operations (mod 2
64
addition for encryption, mod 2
64
subtraction for decryption) inter-leaved with three DES operations (single-DES encryption for encryption, single-DES decryption for decryption), using four different DES keys for an effective key length of 224 bits.
The 224-bit effective key length provides a high work factor (e.g., on the order of 2
224
) against key exhaustion attacks, while the 256-bit block size protects against dictionary attacks. At the same time, since the preferred implementation uses standard DES operations as functional building blocks, it is able to use existing DES hardware and software.
REFERENCES:
patent: 6185304 (2001-02-01), Coppersmith
Coppersmith et al, A proposed mode for triple-DES encryption, IBM J. Research & Development, Mar 96, vol. 40, Issue 2, pp. 253-262.*
Schneier, Applied Cryptography, 2nd Edition, Oct. 18, 1995, pp. 319-325.*
FIPS PUB 46-2 Dec. 30, 1993—“Data Encryption Standard (DES)”.
FIPS PUB 81—Dec. 2, 1980—DES Modes Of Operation.
Information Processing Letters 41, vol. 41, No.2 —Feb. 14, 1992, “On Immunity Against Biham . . . Cryptanalysis”, pp. 77-80.
Fast Software Encryption—Cambridge Security Workshop—Dec. 9-Nov. 1993, “On Modes Of Operation”—Feb. 22, 1994 by E. Biham—pp. 116-120.
USENIX Assoc., Proc. of the Summer '94 USENIX Conf.—Jun.6-Oct. 1994, “Key Management In An Encrypting File System” by M. Blaze, pp. 27-35.
Advances In Cryptology-CRYPTO '90—“The REDOC II Cryptosystem” by T.W. Cusick et al—pp. 545-563.
Fast Software Encryption—Cambridge Security Workshop—Dec.9-Nov. 1993, “A New Approach To Block Cipher Design” by J. Daemen et al, pp. 18-32 .
Fast Software Encryption—Cambridge Security Workshop—Dec. 9-Nov., 1993, “VINO: A Block Cipher . . . Permutations” by A. DiPorto, pp. 205-210.
Coppersmith Don
Johnson Donald B.
Matyas, Jr. Stephen M.
Barron Jr. Gilberto
International Business Machines - Corporation
Kinnaman, Jr. William A.
Leaning Jeffrey S.
LandOfFree
Method and apparatus for cryptographically transforming an... 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 cryptographically transforming an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for cryptographically transforming an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2574621