Data security system and method

• US 6,028,939 A
• Filed: 01/03/1997
• Issued: 02/22/2000
• Est. Priority Date: 01/03/1997
• Status: Expired due to Fees

• Current Assignee: RedCreek Communications, Inc. (SonicWall Holdings Ltd.)
• Original Assignee: RedCreek Communications, Inc. (SonicWall Holdings Ltd.)
• Inventors: Yin, John
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/778,535
• Time in Patent Office: 1,145 Days
• Field of Search: 380/9, 380/28, 380/29, 380/33, 380/37, 380/43, 380/21, 380/30, 380/4, 380/49, 380/50
• US Class Current: 713/189
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/122 Hardware reduction or efficient architectures
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• 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 data security system and method for providing a cryptographic process such as the Data Encryption Standard comprises a microprocessor having a programmable hardware element such as a field programmable gate array interfaced to the processor bus. The predetermined ordered sequence of operations which form the cryptographic process are parsed into hardware-centric operations such as bit manipulations, table look-ups and logic operations which are efficiently performed in hardware, and into software-centric operations such as data processing and state machine control. Hardware-centric operations are performed in the programmable hardware device, and overall control of the system is performed under microprocessor control.

Claims

1. A data security system for performing a cryptographic process on data represented by bits, the cryptographic process comprising a predetermined repetitive sequence of steps which include bit manipulation operations comprising permutations of bits and substitutions of bits and logical operations, the system comprising a microprocessor;

a programmable hardware device connected to the microprocessor, the programmable hardware device comprising a plurality of elements connectable together under program control in different configurations of elements for performing different functions, the elements being connected to perform said bit manipulation and logical operations of said cryptographic processes;

program means within the microprocessor for moving data to and from the hardware device and for controlling the hardware device to repetitively perform said bit manipulation and logical operations in accordance with said predetermined sequence of steps so as to perform said cryptographic process; and

means for loading configuration information into the hardware device from the microprocessor upon start-up of the system to connect the elements to perform said operations.

2. The data security system of claim 1, wherein said cryptographic process comprises a predetermined number of iterations of said predetermined sequence of steps, and wherein said program means comprises means for controlling the hardware device to repeat said sequence of steps for the predetermined number of times.

3. The system of claim 1, wherein said programmable hardware device comprises a field programmable gate array, and said elements comprise logic blocks interconnectable to configure the elements for performing said bit manipulation and logical operations.

4. The system of claim 1, wherein said cryptographic process comprises the Data Encryption Algorithm in which said predetermined sequence of steps is iterated for a predetermined number of rounds, and wherein said microprocessor comprises means for deriving from a cryptographic key a different sub key for each of said predetermined number of rounds.

5. The system of claim 1, wherein said cryptographic process comprises a block cipher encryption process wherein each predetermined sequence of steps produces a block of ciphertext, and wherein said microprocessor comprises means for combining a block of ciphertext with a previous block of ciphertext to form a modified block of ciphertext, and means for iterating said combining operation as successive blocks of data are input into the system.

6. The system of claim 1 further comprising a buffer RAM connected to the hardware device for the temporary storage of data being processed by the hardware device and the results of said bit manipulation ad logical operations.

7. A data security system for performing a cryptographic process on data represented by bits, the cryptographic process comprising a predetermined sequence of repetitive operations including bit manipulation operations involving movements of different ones of said bits relative to other ones of said bits, and a plurality of data processing and control operations, the system comprising a microprocessor having a bus;

a programmable hardware element connected to the microprocessor by the bus, the programmable hardware element comprising a plurality of functional elements connectable together by the microprocessor in different configurations to perform predetermined functions;

first program means within the microprocessor for controlling data movement to and from the programmable hardware element over said bus; and

second program means for configuring the programmable hardware element such that said programmable hardware element performs said bit manipulation operations and the microprocessor performs said data processing and control operations.

8. The system of claim 7, wherein said bit manipulation operations comprise bit permutation and bit substitution operations, and said data processing and control operations comprise data movement over said bus and controlling the operating state of the programmable hardware element to perform said predetermined sequence of repetitive operations.

9. The system of claim 8, wherein said bit manipulation operations further comprise transposition of bits, and said bit substitution operations comprise memory addressing operations.

10. The system of claim 7, wherein said cryptographic process comprises a block cipher process, and wherein said programmable hardware element comprises means for initially permuting bits of a 64-bit block of data;

means for dividing the permutated bits into first and second portions;

means for expanding the first portion to increase the number of bits in said portion;

means for combining the expanded first portion with a sub key to produce a combined block of data;

means for converting said combined block into a substituted block having a smaller number of bits;

means for permutating the bits in the substituted block; and

means for combining the permutated bits with said second portion of the input block to produce a new first portion.

11. The system of claim 10, wherein said microprocessor has first means for controlling the programmable hardware element to produce a first block of ciphertext;

second means for combining said block of ciphertext with a vector to produce a first modified block of ciphertext;

third means for controlling the programmable hardware element to produce a second block of ciphertext; and

fourth means for combining said second block of ciphertext with said first modified block of ciphertext to produce a second modified block of ciphertext.

12. The system of claim 7, wherein said cryptographic process comprises a block cipher process, and wherein said programmable hardware element comprises means for separating the bits of an input block of data into multiple portions;

and means for combining predetermined ones of the bits within each portion and between different portions in response to a key using logic operations.

13. The system of claim 7, wherein said bus is a data bus, and the microprocessor further has a control bus for controlling devices connected to the data bus, and wherein said programmable hardware element has first functional elements configured for interfacing to said data bus and for operating at an operating speed of said data bus;

and has second functional elements for interfacing to the control bus for controlling the devices connected to said data bus.

14. The system of claim 7, wherein said programmable hardware element has functional elements configured to generate random bits.

15. The system of claim 7, wherein said programmable hardware element has functional elements configured to perform a network communications function.

16. A method of performing a cryptographic process on data represented by bits in a system comprising a microprocessor and a programmable hardware device having a plurality of elements which are connectable together under program control by the microprocessor to perform predetermined functions, the cryptographic process comprising a predetermined sequence of repetitive operations including bit manipulation operations involving movement of different ones of said bits relative to other ones of said bits and a plurality of different data processing and control operations, the method comprising configuring the elements of the programmable hardware device using the microprocessor to perform said bit manipulation operations;

controlling, using said microprocessor, data flow to and from said programmable hardware device; and

controlling the programmable hardware device to perform said predetermined repetitive sequence of steps for a predetermined number of iterations in order to perform said cryptographic process, wherein data flow to and from said programmable hardware device is in blocks comprising multiple bits, and wherein said method comprises performing in said programmable hardware device steps comprising permutating bits of a block of data to rearrange the order of the bits;

dividing the permutated bits into first and second portions;

expanding the first portion to increase a number of bits in such portion;

combining the expanded first portion with a sub key from the microprocessor to produce a combined block of data;

converting the combined block into a block having a smaller number of bits;

permutating the bits in the smaller block; and

combining the permutated bits with the second portion of the block to produce a new first portion.

17. The method of claim 16 further comprising providing in a memory tables of stored bits having predetermined values, using the programmable hardware device for addressing the memory to retrieve stored bits, and substituting the retrieved bits for predetermined bits in said data.

18. The method of claim 16, wherein said cryptographic process comprises the Data Encryption Algorithm in which said predetermined sequence of steps is iterated for a predetermined number of rounds, and wherein the method comprises deriving in said microprocessor from a cryptographic key different subkeys for each of said predetermined number of rounds, applying the subkeys to data from said programmable hardware device, and controlling the programmable hardware device to perform said repetitive operations for said predetermined number of rounds.

19. A data security system for performing a cryptographic process on data represented by bits, the cryptographic process comprising a predetermined repetitive sequence of steps which include bit manipulation operations comprising permutations of bits and substitutions of bits and logical operations on groups of bits, the system comprising a microprocessor;

a hardware device connected to the microprocessor by a first bus over which data is provided to and from said hardware device, the hardware device comprising a plurality of elements connected to perform said bit manipulation and logical operations of said cryptographic processes;

a memory connected to said first bus;

means connected to a second bus connected to the microprocessor for inputting and outputting data;

means for controlling the inputting and outputting means for the input and output of data to the memory and from the memory to the hardware device; and

program means within the microprocessor for moving data to and from the hardware device and for controlling the hardware device to repetitively perform said bit manipulation and logical operations in accordance with said predetermined sequence of steps so as to perform said cryptographic process.

20. A system comprising multiple data security systems for performing a cryptographic process on data represented by bits, the cryptographic process comprising a predetermined repetitive sequence of steps which include bit manipulation operations comprising permutations of bits and substitutions of bits and logical operations on groups of bits, each data security system comprising a microprocessor;

a hardware device connected to the microprocessor, the hardware device comprising a plurality of elements connected to perform said bit manipulation and logical operations of said cryptographic processes; and

program means within the microprocessor for moving data to and from the hardware device and for controlling the hardware device to repetitively perform said bit manipulation and logical operations in accordance with said predetermined sequence of steps so as to perform said cryptographic process; and

the system further comprising a control microprocessor connected to respective ones of the microprocessors of said data security systems for controlling said microprocessors;

means for performing public key operations to generate session keys for respective ones of said data security systems; and

means for supplying the session keys to the data security systems to afford simultaneous data security microprocessing operations.