Methods for generating variable S-boxes from arbitrary keys of arbitrary length including methods which allow rapid key changes

• US 5,778,074 A
• Filed: 06/28/1996
• Issued: 07/07/1998
• Est. Priority Date: 06/29/1995
• Status: Expired due to Term

• Current Assignee: Teledyne Technologies Incorporated
• Original Assignee: Teledyne Industries Incorporated (Teledyne Technologies Incorporated)
• Inventors: Kisylia, Andrew Philip, Garcken, Knute T., Strawbridge, Charles E.
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US08/673,437
• Time in Patent Office: 739 Days
• Field of Search: 380/21, 380/37, 380/42, 380/28, 380/29
• US Class Current: 380/37
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation

Abstract

A system for generating variable substitution boxes from arbitrary keys for use in a block cipher system utilizes an initial set of linearly independent numbers to generate substitution tables. The initial set of linearly independent numbers is modulated with the bits of an arbitrary key through operations that result in final sets of linearly independent numbers to form the substitution tables. The system also includes an implementation which allows for rapid key changes for the crypto system by only generating portions of the substitution tables as needed for specific blocks of input data to be encrypted or decrypted,

Claims

1. A block cipher system, in which sub-blocks of data are replaced by other sub-blocks as defined by one or more mappings, wherein each snapping can be expressed as a substitution table, said system comprising:

a first complete set of linearly independent numbers selected from a plurality of complete sets of linearly independent numbers;

a key; and

means for generating at least portions of a resulting n-bit encryption table (E) and a resulting n-bit decryption table (D) from a fixed n-bit source substitution table (R) stored in memory and said first complete set of linearly independent n-bit numbers.

2. The block cipher system of claim 1, wherein said first complete set of linearly independent n-bit numbers is used to form a linear transformation for the source substitution table (R).

3. The block cipher system of claim 2, wherein the linear transformation comprises a second complete set of linearly independent numbers generated by modulating the first complete set of linearly independent numbers with said key.

4. The block cipher system of claim 3, wherein said linear transformation (T) is used as follows:

For K from 0 through 2ⁿ -1;

space="preserve" listing-type="equation">E T(K)!=T(R K!),

and

space="preserve" listing-type="equation">D T(R K!)!=T(K).

5. The block cipher system of claim 4, wherein the transformation (T) comprises a right multiplication by a matrix formed from the second complete act of linearly independent numbers.

6. The block cipher system of claim 3, wherein said linear transformation is used as follows:

For K from 0 through 2ⁿ -1;

space="preserve" listing-type="equation">E T(K)!=T(R K!⊕

F ),

and

space="preserve" listing-type="equation">D T(R K!⊕

F)!=T(K),

where F is an n-bit value determined from the key.

7. The block cipher system of claim 1, wherein said means for generating comprises a means for performing a linear transformation (T) on said source substitution table (R), said transformation (T) comprising a second complete set of linearly independent numbers generated from said key and said first complete set of linearly independent numbers.

8. The block cipher system of claim 1, wherein said means for generating comprises means for concurrently generating a second complete set of linearly independent n-bit numbers to form a first linear transformation (T), and a third complete set of linearly independent n-bit numbers to form a second linear transformation (T^-1) which is the inverse of the first linear transformation (T).

9. The block cipher system of claim 1, wherein said means for generating comprises means for generating the specific n-bit output which correspond to outputs for the encryption substitution table or the decryption substitution table on an as needed basis, for each n-bit input value (U) without generating the entire encryption substitution table (E) or entire substitution table (D).

10. The block cipher system of claim 9, wherein said means for generating further comprises encryption and decryption source substitution tables, R_E and R_D, stored in memory, and further comprises means for performing an n-bit transformation, T, and its inverse, T^-1, as follows:

space="preserve" listing-type="equation">E U!=T(R.sub.E T.sup.-1 (U)!),

and

space="preserve" listing-type="equation">D U!=T(R.sub.D T.sup.-1 (U)!).

11. A block cipher system comprising:

a first complete set of linearly independent numbers, each of a selected bit length;

a key;

a source substitution table stored in memory;

a modulation module responsive to selected bits from said key to control operations on said first complete set of linearly independent numbers to obtain a second complete set of linearly independent numbers;

a transformation module which transforms the source substitution table stored in memory using said second complete set of linearly independent numbers to obtain a resulting substitution table; and

a decryption substitution module which has an input and an output, said input comprising data blocks for which substitution is desired and said output comprising the substitution blocks for said input data blocks, said substitution blocks obtained from said resulting substitution table.

12. The block cipher system of claim 11, further comprising an encryption module with an input and an output, said input comprising data blocks for which substitution is desired and said output comprising substitution blocks for said input data blocks, said substitution blocks obtained from said resulting substitution table.

13. The block cipher system of claim 11, further comprising a plurality of complete sets of linearly independent numbers stored in memory, wherein said modulation module is responsive to selected key bits to select said first complete set of linearly independent numbers from said plurality of complete sets.

14. The block cipher system of claim 13, wherein said modulation module is responsive to other key bits to select certain numbers from said first complete set of linearly independent numbers for XOR operations with other numbers from said first complete set of linearly independent numbers to form said second set of linearly independent numbers.

15. The block cipher system of claim 11, wherein said modulation module is responsive to selected key bits to select certain numbers of said first set of linearly independent numbers for an XOR operation with other numbers of said first set of linearly independent numbers to form said second set of linearly independent numbers.

16. The block cipher system of claim 11, wherein said transformation module forms a matrix of the second set of linearly independent numbers and uses this matrix as a transformation of the source substitution table to form said resulting substitution table.

17. The block cipher system of claim 16, wherein said transformation module right multiplies data from said source substitution table by said matrix to form said resulting substitution table.

18. The block cipher system of claim 17, wherein said source substitution table comprises a plurality of data blocks of a predetermined bit length, and wherein said transformation comprises two inputs, said first input being an index input and said second input being said data blocks from said source substitution table, wherein said transformation module right multiplies said index by said matrix and right multiplies said data blocks by said matrix in order to obtain said resulting substitution table.

19. The block cipher system of claim 18, wherein said transformation module comprises outputs, said outputs comprising a transformed index and a transformed data block, said index providing an address for the transformed data block.

20. A block cipher system comprising:

a first complete set of linearly independent numbers, each of a selected bit length;

a key;

a source substitution table stored in memory;

a transformation module which transforms the source substitution table stored in memory using a transformation from said first complete set of linearly independent numbers and said key to obtain a temporary portions of a resulting substitution table on an as needed basis, without generating entire substitution tables for encryption and decryption; and

a crypto module which has an input and an output, sad input comprising data blocks to be encrypted or decrypted and said output comprising substitution blocks for said input data blocks, said substitution blocks obtained from said temporary portions of the resulting substitution table.

21. The block cipher system of claim 20, wherein said transformation module comprises an n-bit transformation logic and an n-bit inverse transformation logic.

22. The block cipher system of claim 21, wherein said n-bit linear transformation logic and said n-bit inverse linear transformation logic have variable portions which are configured simultaneously.

23. The block cipher system of claim 21, wherein said transformation module performs the following transformation:

space="preserve" listing-type="equation">E U!=T(R.sub.E T.sup.-1 (U)!),

and

space="preserve" listing-type="equation">D U!=T(R.sub.D T.sup.-1 (U)!),

where R_E is the source encryption substitution table, R_D is the source decryption substitution table, T^-1 is the inverse n-bit linear transformation, T is the n-bit linear transformation, E U! is the temporary portion of the resulting encryption substitution table and D U! is the temporary portion of the resulting decryption table and U is the input data block.