Design principles of the shade cipher

• US 5,949,884 A
• Filed: 10/24/1997
• Issued: 09/07/1999
• Est. Priority Date: 11/07/1996
• Status: Expired due to Fees

• Current Assignee: Entrust Technologies Limited
• Original Assignee: Entrust Technologies Limited
• Inventors: Wiener, Michael J., Adams, Carlisle M.
• Primary Examiner(s): CAIN, DAVID C
• Application Number:
  US08/950,416
• Time in Patent Office: 683 Days
• Field of Search: 380/23, 380/25, 380/29, 380/37, 380/49
• US Class Current: 380/29
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• 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 method of encrypting or decrypting an input message block of binary data of predetermined length 2n into an output message block by dividing the message block into two equal size halves, performing one or more transformation rounds on the message block halves, each transformation round further comprising the steps of determining a key, processing the first half data block using a hash function to obtain a modified first half data block of length n, and combining the modified first half data block with the second half data block to obtain a modified second half data block of length n; and, lastly, appending the first modified half data block to the second modified half data block to obtain the output message block.

Claims

1. A method of automatically transforming an input message block of binary data of predetermined length 2n into an output message block, where n is a positive integer, comprising steps of:

dividing the message block into a first and a second half data block of equal length;

processing the message block by one or more transformation rounds, each transformation round further comprising the steps of;

determining a key;

processing the first half data block using a hash function to obtain a modified first half data block of length n;

combining the modified first half data block with the second half data block to obtain a modified second half data block of length n; and

appending the modified first half data block to the modified second half data block to obtain the output message block.

2. The method according to claim 1, wherein the step of processing the first half data block using a hash function, further includes the steps of:

combining the key with the first half data block to obtain an intermediate data block; and

processing the intermediate data block to obtain a modified first half data block of length n.

3. The method according to claim 2, wherein the step of processing the intermediate data block further includes the step of substituting the intermediate data block with a pseudorandomly chosen block of binary data of length n.

4. The method according to claim 2, wherein the step of processing the intermediate data block further comprises the steps of:

dividing the intermediate data block into k smaller data blocks of equal length, wherein k is a positive integer greater than one;

initializing a first k temporary variables d_i to constants, for i=0 . . . k-1;

performing the following determination;

space="preserve" listing-type="equation">d.sub.(-i)mod k =(d.sub.(-i)mod k +f(i,d.sub.(1-i)mod k, d.sub.(2-i)mod k, d.sub.(3-i)mod k)+m.sub.i +T.sub.(i+1))S(i,i mod

     4))+d.sub.1-i)mod k

where i is a positive integer greater than 1 and i equals the number of iterations minus one; and

concatenating the last k temporary variables to obtain the modified first half data block of length n.

5. The method according to claim 4, further including the step of combining the temporary variables with the intermediate data block using an arithmetic/logical function.

6. The method according to claim 2, wherein the step of combining the key with the first half data block further comprises the steps of:

dividing the key into k pieces of equal length, where k is a positive integer greater than 1;

dividing the first half data block into k pieces of equal length;

combining the k pieces of the key with the k pieces of the first half data block using an arithmetic/logical function to obtain k pieces of intermediate data; and

concatenating the k pieces of intermediate data to form one intermediate data block of length n.

7. The method according to claim 2, wherein the step of combining the key with the first half data block further comprises the steps of:

dividing the key, K, into four pieces of equal length;

dividing the first half data block, R, into four pieces of equal length; and

combining the four pieces of the key with the four pieces of the first half data block to obtain four pieces of an intermediate data block, M, according to the following;

space="preserve" listing-type="equation">for i=0 . . . 3, M.sub.i ((((R.sub.i K.sub.(i+1)mod

     4)+K.sub.(i+2)mod

     4)⊕

K.sub.(i+3)mod

     4)K.sub.(i+4)mod

     4).

8. The method according to claim 2, wherein the step of processing the intermediate data block further includes the steps of:

dividing the intermediate data block into two smaller data blocks of equal length;

performing a nonlinear function on a subset of the smaller data blocks to obtain a result;

generating a temporary data block from the intermediate data block;

combining the result and the temporary data block with one of the remaining smaller data blocks and a constant to obtain a second result;

shifting the second result a variable number of places; and

combining one or more of the smaller data blocks and the second result to obtain the modified first half data block of length n.

9. The method according to claim 8, wherein the step of combining further comprises the step of using an arithmetic/logical function.

10. The method according to claim 8, further including the step of combining each smaller data block with a constant using an arithmetic/logical function.

11. The method according to claim 8, wherein the step of performing a nonlinear function further includes the step of:

combining the smaller data blocks using the function, f(t, x, y, z), where f is the mapping f;

{0,1 }ⁿ →

{0,1}ⁿ and f may be further defined as;

##EQU3## where x, y, and z are the smaller data blocks and t is a positive integer less than 20 indicating the number of the current iteration.

12. The method according to claim 8, wherein the step of shifting the second result a variable number of places further includes the step of:

shifting the second result S(t,i) places wherein for the tth iteration, i=t mod 4 and ##EQU4##

13. The method according to claim 8, wherein the constant for iteration i is T_i, wherein T_i = 2³² | sin i|!, for i=0 . . . 19.

14. The method according to claim 8, wherein the step of generating the temporary data block, further includes the steps of:

combining the smaller data blocks of the intermediate data block to obtain an outcome; and

shifting the outcome a variable degree of places to generate the temporary data block.

15. The method according to claim 8, wherein the step of generating the temporary data block, further includes the step of

generating the temporary data block for the ith iteration, m_i, according to the following:

##EQU5## wherein M_i is the ith section of the intermediate data block, M.

16. The method according to claim 1, wherein n is one of either 128, 160 or 192.

17. The method according to claim 1, wherein the step of determining a key further includes the step of generating two or more round keys from an original key of length 2n.

18. The method according to claim 17, wherein the step of generating two or more round keys further includes the steps of:

dividing the original key into a first key and a second key of equal length;

processing the first key using a hash function to obtain a first set of intermediate keys; and

processing the second key using a hash function to obtain a second set of intermediate keys.

19. The method according to claim 18, wherein the step of generating round keys further includes the step of:

combining the first and second sets of intermediate keys to obtain a set of round keys, and the step of combining further comprises the substep of involving an arithmetic/logical function.

20. A data encryption system for transforming an input message block of binary data of predetermined length 2n into an output message block, where n is a positive integer, comprising:

a divider for dividing the message block into a first and a second half data block of equal length;

a key generator;

a hashing processor for processing the first half data block using a hash function to obtain a modified first half data block of length n;

a data processor for combining the modified first half data block with the second half data block to obtain a modified second half data block of length n; and

a concatenator for appending the modified first half data block to the modified second half data block to obtain an output message block.

21. The system according to claim 20, wherein the hashing processor, further includes:

a data processor for combining the key with the first half data block to obtain an intermediate data block; and

a transformer for processing the intermediate data block to obtain a modified first half data block of length n.

22. The system according to claim 21, wherein the transformer further includes a pseudorandom data generator for substituting the intermediate data block with a pseudorandomly chosen block of binary data of length n.

23. The system according to claim 21, wherein the transformer further comprises:

a block separator for dividing the intermediate data block into k smaller data blocks of equal length, wherein k is a positive integer greater than one;

a first data processor for initializing a first k temporary variables, d_i, to constants, for i=0 . . . k-1;

a second data processor for performing the following determination;

space="preserve" listing-type="equation">d.sub.(-i)mod k =(d.sub.(-i)mod k +f(i,d.sub.(1-i)mod k, d.sub.(2-i)mod k, d.sub.(3-i)mod k)+m.sub.i +T.sub.(i+1))S(i,imod

     4))+d.sub.1-i)mod k

where i is a positive integer greater than 1 and i equals a number of iterations minus one; and

a concatenator for concatenating the last k temporary variables to obtain a modified first half data block of length n.

24. The system according to claim 23, further comprising a third data processor for modifying the temporary variables by combining them with the intermediate data block using an arithmetic/logical function.

25. The system according to claim 21, wherein the data processor for combining the key with the first half data block further comprises:

a key separator for dividing the key into k pieces of equal length, k a positive integer greater than 1;

a data separator for dividing the first half data block into k pieces of equal length;

a processor for combining the k pieces of the key with the k pieces of the first half data block using an arithmetic/logical function to obtain k pieces of intermediate data; and

a concatenator for concatenating the k pieces of intermediate data to form one intermediate data block of length n.

26. The system according to claim 21, wherein the data processor for combining the key with the first half data block further comprises:

a key separator for dividing the key, K, into four pieces of equal length;

a data separator for dividing the first half data block, R, into four pieces of equal length; and

a processor for combining the four pieces of the key with the four pieces of the first half data block to obtain four pieces of an intermediate data block, M, according to the following;

space="preserve" listing-type="equation">for i=0 . . . 3, M.sub.i =((((R.sub.i K.sub.(i+1)mod

     4)+K.sub.(i+2)mod

     4)⊕

K.sub.(i+3)mod

     4)K.sub.(i+4)mod

     4).

27.

27. The system according to claim 21, wherein the transformer further includes:

a block separator for dividing the intermediate data block into smaller data blocks of equal length;

a first data processor for performing a nonlinear function on a subset of the smaller data blocks to obtain a result;

a temporary data block generator for generating a temporary data block from the intermediate data block;

a second data processor for combining the result and the temporary data block with one of the remaining smaller data blocks and a constant to obtain a second result;

a shift register for shifting the second result a variable number of places; and

a third data processor for combining one of the smaller data blocks and the second result to obtain a modified first half data block of length n.

28. The system according to claim 27, wherein the second data processor further comprises arithmetic/logical gates.

29. The system according to claim 27, further comprising a fourth data processor for modifying each of the smaller data blocks by combining each smaller data block with a constant using an arithmetic/logical function.

30. The system according to claim 27, wherein the first data processor further comprises:

a plurality of gates for combining the smaller data blocks using the function, f(t, x, y, z), where f is the mapping f;

{0,1}ⁿ →

{0,1}ⁿ and f may be further defined as;

##EQU6## where x, y, and z are the smaller data blocks and t is a positive integer less than 20 indicating the number of the current iteration.

31. The system according to claim 27, wherein the shift register further comprises:

a means for shifting the second result S(t,i) places wherein for the tth iteration, ##EQU7##

32. The system according to claim 27, wherein the constant for iteration i is T_i, wherein T_i = 2³² | sin i|!, for i=0 . . . 19.

33. The system according to claim 27, wherein the temporary data block generator further includes:

a processor for combining two of the smaller data blocks of the intermediate data block to obtain an outcome; and

a shift register for shifting the outcome a variable degree of places to generate a temporary data block.

34. The system according to claim 27, wherein the temporary data block generator further comprises a processor for generating the temporary data block for the ith iteration, m_i, according to the following:

##EQU8## wherein M_i is the ith section of the intermediate data block, M.

35. The system according to claim 20, wherein n is one of either 128, 160 or 192.

36. The system according to claim 20, wherein the key generator further comprises a key processor for generating two or more round keys from an original key of length 2n.

37. The system according to claim 36, wherein the key processor further comprises:

a key separator for dividing the original key into a first key and a second key of equal length;

a first hashing processor for processing the first key using a hash function to obtain a first set of two or more intermediate keys; and

a second hashing processor for processing the second key using a hash function to obtain a second set of two or more intermediate keys.

38. The system according to claim 37 further comprising a processor for combining the first and second sets of intermediate keys to obtain a set of two or more round keys, wherein the processor for combining further comprises one or more gates performing arithmetic/logical functions.