Encryption/decryption instruction set enhancement

A structure and associated method to implement encryption/decryption under the Data Encryption Standard (DES). Several additional instructions are included in the instruction set of a general purpose microprocessor to operate in conjunction with hardware included in a data path of the general purpose microprocessor. The additional instructions perform a portion of the DES algorithm, in particular, a portion of a DES round. The state information used at each step of the encryption portion of the DES algorithm is provided in various general purpose registers of the general purpose microprocessor. In one embodiment, all sixteen subkeys are selected prior to the DES step in the general processor after a DES key is known. In another embodiment, each subkey is selected during the round it is used. In yet another embodiment, each subkey is selected during the round it is used, as part of an additional instruction executed by the general purpose microprocessor.

FIELD OF THE INVENTION

This invention relates to encryption and decryption, and in particular to an encryption/decryption method under the Data Encryption Standard.

BACKGROUND OF THE INVENTION

The Data Encryption Standard (DES) algorithm is a block cipher and specifies a cryptographic algorithm that encrypts, using a key, a 64-bit block of plaintext to a 64-bit block of ciphertext. DES is a symmetric algorithm—i.e., the same algorithm and same key are used to decrypt the 64-bit block of ciphertext back to a 64-bit block of plaintext. DES is described in detail in a book by BRUCE SCHNEIER, APPLIED CRYPTOGRAPHY (1996), incorporated by reference herein.

The goal of DES is to encrypt the data such that every bit of the ciphertext depends on every bit of the data and every bit of the key. DES is intended to achieve, after a number of “rounds”, zero correlation between the ciphertext and the original data or key. DES accomplishes this goal using two basic techniques of cryptography—confusion and diffusion. At the simplest level, diffusion is achieved through numerous permutations and confusion is achieved through XOR operations.

In DES, a 56-bit key is derived from a 64-bit key by omitting every eighth bit (The omitted bits can be used as parity to enhance data integrity). Security in DES relies upon the 56-bit key, which can be any 56-bit number and can be changed at any time. From this 56-bit key, 16 different 48-bit subkeys are created for use in 16 DES rounds.FIG. 1shows a DES algorithm operating on 64-bit of plaintext110. As shown inFIG. 1, the DES algorithm consists of an initial permutation (IP) operation112and a final permutation (IP−1) operation120, and16rounds of encryption operations114-1to114-16. After IP operation112, plaintext110is divided into 32-bit right portion R0and 32-bit left portion L0. Thereafter, 16 rounds of an identical operation (including “Function f”, explained below) are applied on permuted plaintext110using subkeys K1through K16(subkeys are explained in further detail below). IP−1operation120provides ciphertext122, thereby completing the DES algorithm.

IP operation112and IP−1operation120provide no additional security. During IP operation112, a DES integrated circuit loads a 64-bit datum. IP−1operation120is an inverse operation for IP operation112. Although IP operation112and IP−1120can be easily implemented in hardware, these operations cannot be efficiently implemented in software. Hence, due to performance considerations, a software implementation of DES often omits IP operation112and IP−1operation120. While omitting these operations does not compromise security, this modified DES algorithm deviates from the DES standard.

FIG. 2shows a DES round in further detail. As shown inFIG. 2, a 56-bit key210is divided into two 28-bit key portions210aand210b, which are then stored. Then, depending on which of the sixteen rounds is currently being executed, stored key portions210aand210bare circularly shifted left by either one or two bits. Forty-eight (48) bits of shifted key portions210aand210bare selected in compression permutation operation212as the subkey Kifor that round. Simultaneously, a 64-bit block of text from either IP operation112(first round), or the previous round (i.e., (i−1)th round) is divided into 32-bit left portion Li−1and 32-bit right portion Ri−1. Using expansion permutation operation220, right portion Ri−1is expanded to 48 bits. Like IP operation112, expansion permutation operation220can be implemented readily in hardware but cannot be efficiently implemented in software. The 48-bit output value of expansion permutation operation220is then combined with the 48-bit key Kiusing XOR operation225. The 48-bit result of XOR operation225is then processed by 8 substitution box (S-box) operations222, which results in a 32-bit value226. 32-bit value226is then permuted by a permutation box (P-box) operation224to provide a 32-bit value228. Expansion permutation operation220, XOR operation225, S-box substitution operation222and P-box permutation224together constitute Function f, which is a building block of the DES algorithm. 32-bit output value228of Function f is then combined with left portion Li−1using an XOR operation227. The result of XOR operation227is to be used as right portion Riin the next round. Right portion Ri−1is provided as left portion Liin the next round, using a swap operation indicated by reference numeral230. At the end of the 16th round, right portion R15of the 15th round becomes the left 32 bits, and right portions R16becomes the right 32 bits, for IP−1operation120.

As the encryption/decryption process of the DES algorithm ofFIG. 1is too computationally demanding for a software implementation on a general purpose microprocessor, the DES algorithm is often implemented by an array of identical special purpose modules outside of the microprocessor. However, several drawbacks are inherent in such an approach. First, partitioning the encryption/decryption tasks between the microprocessor and the special purpose modules is complex, especially since different instruction sets are executed by the microprocessor and the special purpose modules. Second, the total silicon area devoted in the integrated circuit for the special-purpose modules is large and costly. Third, the shear number of special purpose modules on the integrated circuit causes decentralization of data flow.

Due to the complexity of the DES algorithm, especially expansion and permutation operations, a software DES implementation is prohibitively slow.

Therefore, a method for implementing the DES algorithm is needed which (a) does not require special purpose modules, (b) combines all data flow into a unified data path, and (c) executes the DES algorithm quickly and inexpensively.

SUMMARY OF THE INVENTION

In accordance with the present invention, several additional instructions are included in the instruction set of a general purpose microprocessor to operate in conjunction with hardware included in a data path of the general purpose microprocessor. The additional instructions perform a portion of the DES algorithm, in particular, a portion of a DES round. The state information used at each step of the encryption portion of the DES algorithm is provided in various general purpose registers of the general purpose microprocessor.

In one embodiment, all sixteen 48-bit subkeys are selected prior to the DES step in the general processor after a 56-bit DES key is known. In another embodiment, each subkey is selected during the round it is used. In yet another embodiment, each subkey is selected during the round it is used, as part of an additional instruction executed by the general purpose microprocessor.

Hence, the present invention implements the DES algorithm without the special purpose modules of the prior art. In addition, because hardware is used to implement the part of the DES algorithm which cannot be efficiently implemented in software, the present invention provides improved performance over a software implementation of the prior art. Furthermore, because the general purpose registers store attributes and parameters of the added instruction of the present invention, data flow is unified.

The present invention is more fully understood in light of the following detailed description taken together with the accompanying drawings.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

In one embodiment, the present invention provides, in a general purpose microprocessor, a DES instruction “DSTEP” which carries out Function f in a small amount of additional hardware in a data path, while storing the states of the DES algorithm, i.e., the Li's, Ri's and the subkeys Ki's, in general purpose registers. The remainder of the DES algorithm is carried out by general purpose instructions of the general purpose microprocessor. The present invention eliminates the special purpose modules of the prior art and achieves high performance by executing a part of the DES instruction in the general purpose hardware (e.g., the general purpose registers for storing attributes and parameters, datapath and control) and performing repetitious tasks in the small amount of additional hardware. Under this approach, the present invention can achieve a speed improvement by an order of magnitude over software implementations of the DES algorithm in the prior art. Data flow is unified by placing the additional hardware in the data path of the general purpose processor. Instruction DSTEP is defined in Appendix A.

FIG. 3is a block diagram showing instruction execution in a general purpose processor adapted with additional hardware for execution of the “DSTEP” instruction, in accordance with the present invention. The general purpose processor executes multiple instructions in parallel using pipelining. As shown inFIG. 3, an instruction is fetched initially from memory at pipeline stage31(labeled “F”). In this embodiment, the general processor supports instructions of various lengths. Thus, pipeline stage32is provided to allow alignment of the fetched instruction to the proper byte boundary. Pipeline stage33performs target prediction for a branch instruction. Branch prediction is carried out in a special “branch” arithmetic logic unit307. In addition, pipeline stage33is provided also to allow an instruction of a selected group of instructions of the instruction set to be converted to another instruction or instructions for more efficient execution. At pipeline stage34, the loaded instruction is decoded. At pipeline stage35, operands for the decoded instructions are read from general purpose register file330. For example, general purpose registers are allocated at run-time to store the Li's, Ri's and the subkeys Ki's for each round of the DES algorithm. The DES round input and the DES round output are stored in a byte-interleaved form.

The general purpose processor has three arithmetic logic units (“ALUs”, shown inFIG. 3as ALUs302,304and306) with overlapping execution in pipeline stages36,37and38, which are provided for address generation, memory access and instruction execution stages, respectively. Arrows311,321and325represent 192 bits, 256 bits and 256 bits of input data fetched from register file330or the bypass mechanism into ALU302, ALU304and ALU306, respectively. ALU302includes an adder308, a 2-input arithmetic logic unit310and a shifter314. Adder308and ALU310operate independently. Adder308and ALU310are synchronized to address generation pipeline stage36, which generates addresses for memory access (e.g., fetching an operand from memory). Within the timing of address generation pipeline stage36, is provided a logic circuit309, which is adapted for executing the DSTEP instruction. Logic circuit309performs Function f and XOR operation227described above and is shown in detail inFIG. 4. Logic circuit309operates in parallel with ALU310.

Referring toFIG. 4, first operand Src1and second operand Src2represent two 64-bit registers obtained directly from the register file or on the fly from the bypass structure. Byte0through Byte7represent the bytes in first operand Src1and second operand Src2. For example, Byte0contains bits0through7of first operand Src1and second operand Src2; Byte1contains bits8through15of first operand Src1and second operand Src2; Byte2contains bits16through23of first operand Src1and second operand Src2; Byte3contains bits24through31of first operand Src1and second operand Src2; and so on. Each byte has identical associated circuitry and is cascaded to the circuitry before and after it. For example, circuitry associated with Byte3is cascaded to the circuitry associated with Byte2and the circuitry associated with Byte4. Therefore, only the circuitry associated with one byte, i.e., Byte3, is explained in detail below.

First operand Src1is the combined left portion Liand right portion Riwhich are interleaved. For example, first operand Src1contains right portion R0, left portion L0, through right portion R3and left portion L3. It is noted that right portion Rigoes through an expansion permutation220(FIG. 2) which expands the right portion Rifrom 32 to 48 bits. Two bits of second operand Src2are discarded to perform the compression permutation212(FIG. 2) which compresses each byte to six bits (e.g., bits24through29), which are part of a subkey Ki. The set of six XOR operations, representing XOR operation225inFIG. 2, XOR the portion of subkey Kigenerated above and the expanded right portions R0through R3. The result of XOR operation225is then processed by a 64×4 ROM which represents S-box substitution222inFIG. 2. The result of S-box substitution222is then processed by P-box permutation224which is represented by 32 wires on the bottom of the expanded view inFIG. 4. The result228of P-box permutation224is XORed with left portion L0through L3by XOR operation227which is represented by four XOR operations. The result229of XOR operation227becomes the right portion R1through R4for the next round and the right portion R0through R3become the left portion L1through L4for the next round. The new right portions and left portions are stored in a 64-bit destination register Dest. The combined Byte3of first operand Src1and second operand Src2is stored as Byte3, i.e., bits24through31, of destination register Dest.

Referring back toFIG. 3, memory access pipeline stage37generates memory access requests using the address generated at stage36from adder308. If the memory access can be satisfied from conventional cache312, the requested data are provided as output values at the end of memory access pipeline stage37, aligned appropriately via shifter314. ALU310or logic circuit309provide a second result at the end of the address generation pipeline stage36, which is piped through memory access pipeline stage37to instruction execution pipeline stage38. The results of ALU302are written back into register file330according to the timing of instruction execution pipeline stage38.

Second ALU304includes a conventional variable shifter (composed of a shift amount decoder316feeding a shift array318) and 2-input ALU320. Thus, the execution in shift amount decoder316is aligned to memory access pipeline stage37and the executions of shift array318and 2-input ALU320are aligned with instruction execution pipeline stage38. The results of shift array318and 2-input ALU320are written back into register330within the timing of instruction execution pipeline stage38. Shift array318and 2-input ALU320execute independently.

ALU306includes a conventional multiplier322and a conventional 4-input ALU324. Multiplier322has a latency that spans pipeline stages36and37. The output value of multiplier322is provided to ALU324, which provides a 128-bit output value. Thus, execution of multiplier322is aligned to both address generation pipeline36and memory access pipeline37, and execution of ALU324and writing back of results into register file330are aligned to instruction execution pipeline stage38.

In one embodiment, instruction DSTEP is executed in ALU302. In the particular configuration described above, processing within the first stage of ALU302is not necessary but advantageous because the output value is available earlier in the pipeline. Further, the latency of address generation pipeline stage36closely matches the timing of logic circuit309, so that no modification of timing control of address generation pipeline stage36or any other pipeline stage is necessary.

In this embodiment, subkey Kiis selected using instructions of the general purpose processor. The programmer can choose to select all 16 subkey Ki's when the key value is received, or just before executing the DSTEP instruction. The instructions for key selection can be executed in ALU302or304. Thus, some benefits of parallel execution can be achieved in some instances, as key selection operations can overlap—while DSTEP executes in ALU302, key selection for the next round can execute in ALU304. Alternatively, a logic circuit for subkey selection can be included in logic circuit309to provide even higher performance. In this embodiment, in the DSTEP instruction, left and right portions Liand Riand subkey Kiare passed using three general purpose registers. In the alternative, 32-bit registers can be used because 64-bit registers are no longer required.

IP operation112and IP−1operation120can be executed in either one of ALUs302and304.

In this embodiment, bypass mechanisms are provided in ALU302, so that the results of logic circuit309and shifter314can each be provided back as input values to ALU302. If the programmer uses the same corresponding general purpose registers for sources and destinations, all sixteen rounds of DSTEP can be executed using the bypass mechanism—i.e., no register write back time (i.e., latency of instruction execution pipeline stage38) is required, thereby providing even higher performance. Bypass mechanisms are also provided elsewhere in ALUs302,304, and306, so results may be immediately used as operands without delaying through instruction execution pipeline stage38.

Although the invention has been described with reference to particular embodiments, the description is only an example of the invention's application and should not be taken as a limitation. Various other adaptations and combinations of features of the embodiments disclosed are within the scope of the invention as defined by the following claims.