Construction symmetric ciphers using the cast design procedure

• US 5,825,886 A
• Filed: 12/05/1996
• Issued: 10/20/1998
• Est. Priority Date: 12/08/1995
• Status: Expired due to Term

• Current Assignee: Entrust Incorporated (Entrust Corp.)
• Original Assignee: Entrust Technologies Limited
• Inventors: Lockhart, Roland Thomas, Adams, Carlisle Michael, Wiener, Michael James
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/761,763
• Time in Patent Office: 684 Days
• Field of Search: 380/6, 380/9, 380/28, 380/29, 380/30, 380/33, 380/37, 380/43, 380/49, 380/50
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/046 of operations, operands or results of the operations
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI

Abstract

A new design procedure for constructing a family of DES-like Substitution-Permutation Network (SPN) cryptosystems with desirable cryptographic properties including provable resistance to differential cryptanalysis, linear cryptanalysis, and related-key cryptanalysis is described. New cryptosystems called CAST ciphers, constructed according to the procedure, are also described. Details of the design choices in the procedure are given, including those regarding the component substitution boxes (s-boxes), the overall framework, the key schedule, and the round function. A fully specified example CAST cipher, an output of this design procedure, is presented as an aid to understanding the concepts and to encourage detailed analysis by the cryptologic community.

Claims

1. In a data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of a predetermined bitlength comprising a plurality of consecutive transformation rounds of half of each data block, each consecutive transformation round comprising steps of:

combining the half data block with a first masking key of predetermined length using a first binary operation to generate a first modified half data block;

combining the first modified half data block with a second masking key of predetermined length using a second and different binary operation to generate a second modified half data block;

processing the second modified half data block by a plurality of (m×

n) mutually different substitution boxes to generate a third modified half data block, m and n being positive integers; and

XORing the third modified half data block with the remaining half of the data block to generate a transformed half data block of a transformation round.

2. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 1, wherein the first binary operation is addition modulo 2ⁿ, or subtraction modulo 2ⁿ, or bitwise XOR, and the second binary operation is multiplication modulo (2ⁿ -1), or multiplication modulo (2ⁿ +1).

3. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 1, wherein the first binary operation is addition modulo 2ⁿ, or subtraction modulo 2ⁿ, or bitwise XOR, and the second binary operation is a circular shift by a number of bits specified by the second masking key.

4. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 1, wherein all first masking keys and all second masking keys for all the transformation rounds are generated before the first transformation round is performed.

5. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 4, wherein all first masking keys and all second masking keys for all the transformation rounds are generated by a plurality of partially bent-function-based (m×

n) substitution boxes from the key bits, where the key bits comprise a key pattern of z bytes in the following order;

k1, k2, k3, . . . , k(z-1), kz, z being a positive integer.

6. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 5, wherein each data block contains 64 bits, the substitution boxes are eight partially bent-function-based 8×

32 s-boxes, S1, S2, S3, . . . , S8, and the key bits comprise a key pattern of 10 bytes in the following order;

k1, k2, k3, . . . , k9, k0.

7. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 6, wherein the transformation round function means has a first plurality of partially bent-function-based (m×

n) s-boxes for processing key bits to generate a first masking key and a second masking key, and a second plurality of partially bent-function-based (m×

n) s-boxes for processing the second modified data half.

8. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 7, wherein the first plurality of s-boxes comprises four partially bent-function-based 8×

32 s-boxes and the second plurality of s-boxes comprises four partially bent-function-based 8×

32 s-boxes.

9. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 5, wherein the transformation round function means has a first plurality of partially bent-function-based (m×

n) s-boxes for processing key bits to generate a first masking key and a second masking key, and a second plurality of partially bent-function-based (m×

n) s-boxes for processing the second modified data half.

10. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 1, wherein one or more consecutive transformation rounds include mutually different sets of first and second binary operations.

11. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 10, wherein particular binary operations for use in any particular round are chosen in dependence upon the value of certain predetermined bits of the first masking key or the second masking key, or upon the value of certain predetermined bits of the half data block being operated upon.

12. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 10, wherein particular binary operations for use in each transformation round are fully specified for all implementations of the method and is independent of any key bits or data bits.

13. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 12, wherein the binary operations addition modulo 2ⁿ, subtraction modulo 2ⁿ, and bitwise XOR can be used to combine the half data block with the first masking key and to combine the s-box outputs which result from the processing of the second modified half data block.

14. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 13, wherein three different transformation rounds are used:

Type 1;

I=((Kmi+D)<

<

<

Kri) O=((S1 Ia! S2 Ib!)-S3 Ic!)+S4 Id!

Type 2;

I=((Kmi D)<

<

<

Kri) O=((S1 Ia!-S2 Ib!)+S3 Ic!) S4 Id!

Type 3;

I=((Kmi-D)<

<

<

Kri) O=((S1 Ia!+S2 Ib!) S3 Ic!)-S4 Id!

where "D" is the original input to the transformation round, "Ia",-"Id", are the most significant byte through least significant byte of I, respectively, and "O", is the output of the transformation round and "+", and "-", are addition and subtraction modulo 2³², " ", is bitwise XOR, and "<

<

<

", is the circular left-shift operation.

15. The data encryption method of cryptographically transforming plaintext into ciphertext in data blocks of predetermined bitlength according to claim 14, wherein twelve transformation rounds are used in total and

rounds 1, 4, 7, and 10 use transformation round Type 1,

rounds 2, 5, 8, and 11 use transformation round Type 2, and

rounds 3, 6, 9, and 12 use transformation round Type 3.