Method of cryptographically transforming electronic digital data from one form to another

• US 5,003,596 A
• Filed: 08/17/1989
• Issued: 03/26/1991
• Est. Priority Date: 08/17/1989
• Status: Expired due to Term

• Current Assignee: Moab Arches LLC (Intellectual Ventures LLC)
• Original Assignee: Cryptech Incorporated
• Inventors: Wood, Michael C.
• Primary Examiner(s): Buczinski, Stephen C.
• Assistant Examiner(s): Gregory, Bernarr Earl
• Application Number:
  US07/395,448
• Time in Patent Office: 586 Days
• Field of Search: 380/9, 380/23, 380/25, 380/28-30, 380/43, 380/49, 380/50, 380/37, 380/42, 380/21
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/043 of tables, e.g. lookup, substitution or mapping
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• 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 cryptographic system creates a key table from a single key such that the relationship between the keys in the key table cannot be determined even if the system implementation is known. The system uses variable functions in which the determinants are changed by the variable function chosen by the determinant. Thus, the functions used in creating the key table do not have to be one-to-one functions. From the key table, four blocks of bytes of additional key based determinants are formed which are called masks. The original key does not exist in either the key table or the mask table. The system preferably uses the key table in a multiple round encryption process. The keys chosen from the table for a key addition operation are a function of the plaintext, the current state of the ciphertext, and the mask values. Therefore, the order in which the keys are chosen is not predetermined or patterned. The system also selects the other encryption functions, including permutations and substitutions, by the plaintext, current state of the ciphertext and the mask values. The cryptographic system also can include a function referred to as the enclave function. This function operates on lookup tables and creates complete inter-symbol dependency on the block of bytes.

Claims

1. A method of cryptographically transforming electronic digital data from one form to another comprising the steps of:

a. establishing in memory at least one transformation table associated with a predetermined cryptographic function, said table including a plurality of addressable entries which each direct a predetermined transformation of data in accordance with said function;

b. establishing in memory one or more key based determinants;

c. selecting one of said entries in said transformation table based upon certain information in one of said data key based determinants; and

d. cryptographically transforming said data by said function in accordance with the directions of said selected entry in said transformation table.

2. A method of generating a table of keys for use in cryptographically transforming electronic digital data from one form to another comprising the steps of:

a. establishing an initial key;

b. establishing in memory at least one transformation table associated with a predetermined cryptographic function, said table including a plurality of addressable entries which each direct a predetermined transformation of data in accordance with said function;

c. selecting at least one of said entries in said transformation table based upon certain information in said initial key;

d. transforming said initial key by said function in accordance with the directions of said selected entry in said transformation table;

e. storing said transformed initial key as an entry in the key table memory;

f. selecting at least one of said entries in said transformation table based upon certain information in the initial key or in a key stored in the key table memory;

g. transforming the key used in step (f) above by said function in accordance with the directions of said selected entry in said transformation table;

h. storing said transformed key as another entry in the key table memory; and

i. performing steps (f)-(h) above repetitively until said key table memory has a desired plurality of keys stored therein.

3. The method of claim 2 wherein said initial key is not stored as an entry in the key table memory.

4. The method of claim 2 wherein said transformation table entry selected in step (f) above is based upon certain information in the latest key stored in the key table memory.

5. A method of generating a table of keys for use in cryptographically transforming electronic digital data from one form to another comprising the steps of:

a. establishing an initial key having a plurality of bytes;

b. establishing in memory a plurality of transformation tables, each associated with a predetermined cryptographic function, each of said tables including a plurality of addressable entries which direct a predetermined transformation of data in accordance with said function;

c. selecting, in turn, at least one of said entries in each of said transformation tables based upon certain information in said initial key;

d. transforming said initial key by said functions in accordance with the directions of said selected entries in said transformation tables;

e. storing said transformed initial key as an entry in the key table memory;

f. selecting, in turn, at least one of said entries in each of said transformation tables based upon certain information in at least one of the keys stored in the key table memory;

g. transforming the key used in step (f) above by said functions in accordance with the directions of said selected entries in said transformation tables;

h. storing said transformed key as another entry in the key table memory; and

i. performing steps (f)-(h) above repetitively until said key table memory has a desired plurality of keys stored therein.

6. The method of claim 5 wherein said initial key is not stored as an entry in the key table memory.

7. The method of claim 5 wherein the entries in the transformation tables selected in step (f) above are based upon certain information in the latest key stored in the key table memory.

8. The method of claim 5 wherein said transformation tables include a substitution table with a plurality of entries for directing a particular substitution on said key undergoing transformation.

9. The method of claim 5 wherein said transformation tables include a permutation table with a plurality of entries for directing a particular permutation on said key undergoing transformation.

10. The method of claim 5 wherein said transformation tables include an enclave table with a plurality of entries for directing a particular transformation on said key undergoing transformation in which each byte in said key becomes a function of itself and of every other byte in the key.

11. The method of claim 5 wherein said transformation tables include a substitution table with a plurality of entries for directing a particular substitution on said key undergoing transformation and a permutation table with a plurality of entries for directing a particular permutation on said key undergoing transformation.

12. The method of claim 5 wherein said transformation tables include a substitution table with a plurality of entries for directing a particular substitution on said key undergoing transformation, a permutation table with a plurality of entries for directing a particular permutation on said key undergoing transformation, and an enclave table with a plurality of entries for directing a particular transformation on said key undergoing transformation in which each byte in said key becomes a function of itself and of every other byte in the key.

13. The method of claim 12 wherein the substitution table entry, the permutation table entry and the enclave table entry selected is determined by an arithmetic combination of the values of a portion of the bytes in the key undergoing transformation.

14. The method of claim 12 wherein said key undergoing transformation is first substituted in accordance with the selected entry in the substitution table, is then permutated in accordance with the selected entry in the permutation table, and is then transformed in accordance with the selected entry in the enclave table.

15. The method of claim 14 wherein the substitution and permutation table entries selected are determined by an arithmetic combination of the values of a portion of the bytes in the key undergoing transformation, and the enclave table entry selected is determined by an arithmetic combination of the values of a portion of the bytes in the key after it has been substituted and permutated.

16. The method of claim 15 wherein the substitution table entry selected is determined by an arithmetic combination of the values of one-half of the bytes in the key undergoing transformation and the permutation table entry selected is determined by an arithmetic combination of the values of the other half of the bytes in the key undergoing transformation.

17. A method cryptographically transforming electronic data from one form to another comprising the steps of:

a. establishing in memory a key table with a plurality of multi-byte key entries;

b. selecting a multi-byte block of data for transformation;

c. selecting an entry from the key table based on information in at least one of the bytes of the data block;

d. arithmetically combining each byte in the selected key with a corresponding byte in the data block, except that the bytes in the data block used to select the entry from the key table remain unchanged; and

e. repeating steps (c) and (d) above for a plurality of rounds and using a different byte of the data block in each round for selecting the entry from the key table.

19. The method of claims 17 or 18 further including the steps of generating from the key table a determinant table having a plurality of entries which are each the result of an arithmetic combination of two or more values in the key table, and then combining an entry from said determinant table with said one of the values in the data block undergoing transformation to select an entry from the key table.

20. The method of claim 19 wherein a different entry from said determinant table is used during each round.

21. The method of claim 19 wherein the entry from the determinant table and said one of the bytes in the data block are combined by an Exclusive OR operation.

22. The method of claim 19 wherein the value of the entry from the determinant table is added to the value of said one of the bytes in the data block.

24. The method of claims 17, 18 or 23 wherein the bits in the selected key are arithmetically combined with the corresponding bits in the data block undergoing transformation by an Exclusive OR operation.

25. The method of claims 17, 18 or 23 wherein the values of the bytes in the selected key are added to the values of the corresponding bytes in the data block undergoing transformation.

26. The method of claims 17, 18 or 23 wherein said key table is established by the steps of:

f. establishing an initial key;

g. establishing in memory at least one transformation table associated with a predetermined cryptographic function, said table including a plurality of addressable entries which each direct a predetermined transformation of data in accordance with said function;

h. selecting at least one of said entries in said transformation table based upon certain information in said initial key;

i. transforming said initial key by said function in accordance with the directions of said selected entry in said transformation table;

j. storing said transformed initial key as an entry in the key table memory;

k. selecting at least one of said entries in said transformation table based upon certain information in the initial key or in a key stored in the key table memory;

l. transforming the key used in step (k) above by said function in accordance with the directions of said selected entry in said transformation table;

m. storing said transformed key as another entry in the key table memory; and

n. performing steps (k)-(m) above repetitively until said key table memory has a desired plurality of keys stored therein.

27. The method of claim 26 wherein said initial key is not stored as an entry in the key table memory.

28. The method of claim 26 wherein said transformation table entry selected in step (k) above is based upon certain information in the latest key stored in the key table memory.

29. The method of claims 17, 18 or 23 wherein said key table is generated by the steps of:

f. establishing an initial key having a plurality of bytes;

g. establishing in memory a plurality of transformation tables, each associated with a predetermined cryptographic function, each of said tables including a plurality of addressable entries which direct a predetermined transformation of data in accordance with said function;

h. selecting, in turn, at least one of said entries in each of said transformation tables based upon certain information in said initial key;

i. transforming said initial key by said functions in accordance with the directions of said selected entries in said transformation tables;

j. storing said transformed initial key as an entry in the key table memory;

k. selecting, in turn, at least one of said entries in each of said transformation tables based upon certain information in at least one of the keys stored in the key table memory;

1. transforming the key used in step (k) above by said functions in accordance with the directions of said selected entries in said transformation tables;

m. storing said transformed key as another entry in the key table memory; and

n. performing steps (k)-(m) above repetitively until said key table memory has a desired plurality of keys stored therein.

30. The method of claim 29 wherein said initial key is not stored as an entry in the key table memory.

31. The method of claim 29 wherein the entries in the transformation tables selected in step (k) above are based upon certain information in the latest key stored in the key table memory.

32. The method of claim 29 wherein said transformation tables include a substitution table with a plurality of entries for directing a particular substitution on said key undergoing transformation and a permutation table with a plurality of entries for directing a particular permutation on said key undergoing transformation.

33. The method of claim 29 wherein said transformation tables include a substitution table with a plurality of entries for directing a particular substitution on said key undergoing transformation, a permutation table with a plurality of entries for directing a particular permutation on said key undergoing transformation, and an enclave table with a plurality of entries for directing a particular transformation on said key undergoing transformation in which each byte in said key becomes a function of itself and of every other byte in the key.

18. A method of cryptographically transforming electronic data from one form to another comprising the steps of:

a. establishing in memory a key table with a plurality of multi-byte key entries;

b. selecting a multi-byte block of data for transformation;

c. selecting an entry from the key table based on information in at least one of the bytes of the data block;

d. arithmetically combining each byte in the selected key with a corresponding byte in the data block, except that the bytes in the data block used to select the entry from the key table remain unchanged; and

e. repeating steps (c) and (d) above for a plurality of rounds.

23. A method of cryptographically transforming electronic data from one form to another comprising the steps of:

a. establishing in memory a key table with a plurality of multi-byte key entries;

b. establishing in memory one or more multi-byte key based determinants;

c. selecting a multi-byte block of data for transformation;

d. selecting an entry from the key table based on information in at least one of the bytes of one of said key based determinants;

e. arithmetically combining each byte in the selected key with a corresponding byte in the data block; and

f. repeating steps (d) and (e) above for a plurality of rounds.

34. A method cryptographically transforming electronic data from one form to another comprising the steps of:

a. establishing in memory at least one transformation table associated with a predetermined cryptographic function, said table including a plurality of addressable entries which direct a predetermined transformation of data in accordance with said function;

b. selecting at least one of the entries in said transformation table based upon certain information in the data undergoing transformation;

c. cryptographically transforming the data by said function in accordance with the directions of the entry in the transformation table selected in step (b);

d. arithmetically combining the data transformed in step (c) above with a key;

e. selecting at least one other entry in said transformation table based upon certain information in the data transformed in step (d) above; and

f. cryptographically transforming the data transformed in step (d) above by said function in accordance with the directions of the entry in the transformation table selected in step (e).

35. The method of claim 34 wherein steps (b) through (f) are carried out repetitively in a predetermined number of rounds.

36. A method of cryptographically transforming electronic data from one form to another comprising the steps of:

a. establishing in memory a first transformation table associated with a first cryptographic function and a second transformation table associated with a second cryptographic function, said tables each including a plurality of addressable entries which direct a predetermined transformation of data in accordance with said functions;

b. selecting at least one of the entries in said first transformation table based upon certain information in said data undergoing transformation;

c. cryptographically transforming said data by said first function in accordance with the directions of the entry in the first transformation table selected in step (b);

d. arithmetically combining the data transformed in step (c) above with a key;

e. selecting at least one of the entries in the second transformation table based upon certain information in the data transformed in step (d) above; and

f. cryptographically transforming the data transformed in step (d) above by the second function in accordance with the directions of the entry in the second transformation table selected in step (e).

37. The method of claim 36 wherein steps (b) through (f) are carried out repetitively in a predetermined number of rounds.

38. An enclave function for cryptographically transforming electronic digital data from one form to another comprising the steps of:

a. establishing in memory an enclave table with a plurality of entries for directing an autoclave function on a portion of the data undergoing transformation;

b. selecting a block of data having an even number of bytes;

c. dividing said data block into a first half-block including one-half of the bytes of the data block and into a second half-block including the remaining bytes of the data block;

d. transforming the first half-block by said autoclave function as directed by a first entry in said enclave table;

e. transforming the resultant first half-block after step (d) above by said autoclave function as directed by a second entry in said enclave table;

f. combining the second half-block with the resultant first half-block after step (e) above by an Exclusive OR operation to generate resultant second half-block;

g. transforming the resultant second half-block after step (f) above by said autoclave function as directed by a third entry in said enclave table;

h. transforming the resultant second half-block after step (g) above by said autoclave function as directed by a fourth entry in said enclave table;

i. combining the resultant second half-block after step (h) above with the resultant first half-block after step (e) above by an Exclusive OR operation to generate a resultant first half-block; and

j. joining said resultant first half-block after step (i) above to said resultant second half-block after step (h) above to form the transformed data block.

39. The method of claim 38 wherein the autoclave function used includes the steps of modifying a byte in the half-block undergoing transformation by adding said byte to at least two other bytes in the half-block, and sequentially repeating this addition process on each of the other bytes in the half-block, using different bytes in each repetition to be added to the byte, undergoing transformation.

40. A method of cryptographically transforming electronic data from one form to another comprising the steps of:

a. establishing in memory a permutation table with a plurality of addressable entries for directing a particular permutation of said data undergoing transformation;

b. establishing in memory a substitution table with a plurality of addressable entries for directing a particular substitution on said data undergoing transformation;

c. selecting at least one of the entries in one of said permutation and substitution tables based upon certain information in said data undergoing transformation;

d. cryptographically transforming said data in accordance with the table entry selected in step (c) above and the function associated therewith;

e. arithmetically combining the data transformed in step (d) with a key;

f. selecting at least one of the entries in the other of said permutation and substitution tables; and

g. cryptographically transforming the data transformed in step (e) in accordance with the table entry selected in step (f) and the function associated therewith.

41. The method of claim 40 wherein the substitution table entry selected is determined by the value of one of the bytes in the data undergoing transformation and the substitution function is carried out on all bytes in the data except for the byte used to select the entry from the substitution table, which byte remains unchanged.

42. The method of claims 40 or 41 further including the steps of establishing an enclave table with a plurality of entries for directing an enclave transformation in which each byte in the data undergoing transformation becomes a function of itself and of every other byte in the data, selecting at least one of said entries in said enclave table, and transforming the data in accordance with the directions of the selected entry in the enclave table.

43. The method of claim 40 further including the steps of generating from said key a determinant table having a plurality of entries which are the result of an arithmetic combination of two or more values in the key, and then using one entry in said determinant table to select the entry from the enclave table used in the enclave function transformation of the data.

44. The method of claim 40 wherein steps (b) through (g) are carried out repetitively in a predetermined number of rounds.

45. The method of claim 44 wherein the substitution table entry selected is determined by the value of one of the bytes in the data undergoing transformation, the substitution function is carried out on all bytes in the data except for the byte used to select the entry from the substitution table, which byte remains unchanged, and a different byte in the data undergoing transformation is used in each round to select the substitution table entry.

46. The method of claim 45 further including the steps of selecting a second entry in the substitution table based upon certain information in the data undergoing transformation after it has been subjected to said substitution function, and then cryptographically transforming said data by a second substitution function in accordance with the second entry selected.

47. The method of claim 46 wherein the substitution table entry selected for the second substitution is determined by the value of one of the bytes in the data undergoing transformation, excluding the byte used in claim 62 for determining the substitution table entry for the initial substitution function.

48. The method of claim 44 wherein the step of combining the transformed data with a key includes the steps of:

h. establishing in memory a key table with a plurality of multi-byte key entries;

i. selecting an entry from the key table based on information in at least one of the bytes in the data undergoing transformation; and

j. arithmetically combining each byte in the selected key with a corresponding byte in the data undergoing transformation, except that the data bytes used to select the key from the table entry remain unchanged, with a different byte in the data undergoing transformation used in each round to select the entry from the key table.

49. The method of claim 44 wherein the step of combining the transformed data with a key includes the steps of:

p1 h. establishing in memory a key table with a plurality of multi-byte key entries;

i. selecting an entry from the key table based on information in at least one of the bytes in the data undergoing transformation; and

j. arithmetically combining each byte in the selected key with a corresponding byte in the data undergoing transformation, except that the data bytes used to select the key from the table entry remain unchanged.

50. The method of claim 44 wherein the step of combining the transformed data with a key includes the steps of:

h. establishing in memory a key table with a plurality of multi-byte key entries;

i. selecting an entry from the key table based on information in at least one of the bytes in the data undergoing transformation; and

j. arithmetically combining each byte in the selected key with a corresponding byte in the data undergoing transformation.

51. The method of claims 48, 49 or 50 wherein bits in the selected key are arithmetically combined with the corresponding bits in the data undergoing transformation by an Exclusive OR operation.

52. The method of claims 48, 49, or 50 further including the steps of generating from the key table a determinant table having a plurality of entries which are each the result of an arithmetic combination of two or more values in the key table, and then combining an entry from said determinant table with said one of the values in the data undergoing transformation to select an entry from the key table.

53. The method of claim 52 wherein a different entry from said determinant table is used during each round.

54. The method of claim 52 wherein the entry from the determinant table and said one of the bytes in the data undergoing transformation are combined by an Exclusive OR operation.

55. The method of claims 48, 49 or 50 wherein said key table is established by the steps of:

k. establishing an initial key having a plurality of bytes;

l. selecting, in turn, at least one of said entries in each of said permutation and substitution tables based upon certain information in said initial key;

m. transforming said initial key by said substitution and permutation functions in accordance with the directions of said selected entries in said tables;

n. storing said transformed initial key as an entry in the key table memory;

o. electing, in turn, at least one of said entries in each of said substitution and permutation tables based upon certain information in at least one of the keys stored in the key table memory.

p. transforming the key used in step (o) above by said substitution and permutation functions in accordance with the directions of said selected entries in said tables;

q. storing said transformed key as another entry in the key table memory; and

r. performing steps (o)-(q) above repetitively until said key table memory has a desired plurality of keys stored therein.

56. The method of claim 55 wherein said initial key is not stored as an entry in the key table memory.

57. The method of claim 55 wherein the entries in the substitution and permutation tables selected in step (o) above are based upon certain information in the latest key stored in the key table memory.

58. The method of claims 48, 49 or 50 further including the steps of establishing an enclave table with a plurality of entries for directing an enclave transformation in which each byte in the data undergoing transformation in which each byte in the data undergoing transformation becomes a function of itself and of every other byte in the data, selecting at least one of said entries in said enclave table, and transforming the data in accordance with the directions of the selected entry in the enclave table.

59. The method of claim 58 further including the steps of generating from said key table a determinant table having a plurality of entries which are the result of an arithmetic combination of two or more values in the key table, and then using one entry in said determinant table to select the entry from the enclave table used in the enclave function transformation of the data.

60. The method of claim 59 wherein a different entry from said determinant table is used during each round.

61. The method of claims 48, 49 or 50 further including the steps of selecting a second key from the key table memory based on the value of one of the bytes in the data undergoing transformation, excluding the byte used in claims 48, 49 or 50 and arithmetically combining each byte in the selected second key with a corresponding byte in the data undergoing transformation, except that the byte used to select the second key remains unchanged, with a different byte in the data undergoing transformation used in each round to select the second key.

62. The method of claims 40 or 44 wherein the permutation table entry selected is determined by an arithmetic combination of the values of the bytes in the data undergoing transformation.