Method apparatus and system of performing one or more encryption and/or decryption operations

Embodiments of the present invention provide a method and apparatus of performing on one or more bytes of an input data block at least one predetermined encryption or decryption operation.

BACKGROUND OF THE INVENTION

Methods of encrypting/decrypting a data block may include performing one or more encryption or decryption operations. Some of these methods may include iteratively performing one or more of the encryption or decryption operations. For example the Advanced Encryption Standard (AES) defines an encryption/decryption cipher including iteratively performing a plurality of predetermined AES operations on a state array representing the data block.

Some conventional encryption/decryption devices may use a conventional processor to perform one or more computations including a predetermined sequence of “standard” arithmetical operations, e.g., including addition, subtraction, multiplication and/or division, in order to achieve a result equivalent to the predetermined encryption or decryption operations. Such computations, e.g., when performed on a relatively large data block, may be time consuming and/or may require relatively high utilization of the processor computational resources, and thus may be power consuming.

Other conventional devices may implement an encryption accelerator, e.g., one or more hardware elements associated with a processor and dedicated to performing one or more of the encryption/decryption operations on an input data block, e.g., received form the processor. The use of such devices may be time and/or power consuming, since the input data block must be transferred from the processor to the encryption accelerator and the output of the encryption accelerator must be transferred back to the processor after performing each encryption or decryption operation.

It will be appreciated that for simplicity and clarity of illustration, elements shown in the drawings have not necessarily been drawn accurately or to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity or several physical components included in one functional block or element. Further, where considered appropriate, reference numerals may be repeated among the drawings to indicate corresponding or analogous elements. Moreover, some of the blocks depicted in the drawings may be combined into a single function

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

It should be understood that the present invention may be used in any computing platform including a processor. Although the present invention is not limited in this respect, the computing platform may be a portable device. Non-limiting examples of such portable devices include laptop and notebook computers, mobile telephones, personal digital assistants (PDA), and the like. Alternatively, the computing platform may be a non-portable device, such as, for example, a desktop computer.

Reference is made toFIG. 1, which schematically illustrates a computing platform100according to exemplary embodiments of the invention.

According to the exemplary embodiments ofFIG. 1, computing platform100may include a processor104able to perform at least one predetermined encryption/decryption operation on at least part of an input data block, as described in detail below.

According to some exemplary embodiments of the invention, platform100may optionally include a network connection108adapted to interact with a communication network, for example, a local area network (LAN), wide area network (WAN), or a global communication network, for example, the Internet. According to some embodiments the communication network may include a wireless communication network such as, for example, a wireless LAN (WLAN) communication network. Types of WLAN communication systems intended to be within the scope of the present invention include, although are not limited to, WLAN communication systems as described by “IEEE-Std 802.11, 1999 Edition (ISO/IEC 8802-11: 1999)” standard, and more particularly in “IEEE-Std 802.11i Supplement to 802.11-1999: Wireless LAN MAC and PHY specifications: Enhanced MAC layer security” (“the 802.1 μl standard”) and the like.

Although the scope of the present invention is not limited in this respect, the communication network may include a cellular communication network, with platform100being, for example, a base station, or a mobile station. The cellular communication network, according to some embodiments of the invention, may be a 3rdGeneration Partnership Project (3GPP), such as, for example, Frequency Domain Duplexing (FDD), Global System for Mobile cormnunications (GSM), Wideband Code Division Multiple Access (WCDMA) cellular communication network and the like.

According to some exemplary embodiments of the invention, although the invention is not limited in this respect, network connection108may be adapted to interact with a WLAN communication network, e.g., in accordance with the 802.11i standard, and processor104may be able to perform one or more encryption/decryption operations on a data block received via connection108or a data block to be transmitted via connection108, as described below.

According to some exemplary embodiments of the invention, computing platform100may also include an input unit132, an output unit133, a memory unit134, and a storage unit135. Computing platform100may additionally include other suitable hardware components and/or software components.

Input unit132may include, for example, a keyboard, a mouse, a touch-pad, or other suitable pointing device or input device. Output unit133may include, for example, a Cathode Ray Tube (CRT) monitor, a Liquid Crystal Display (LCD) monitor, or other suitable monitor or display unit. Storage unit135may include, for example, a hard disk drive, a floppy disk drive, a Compact Disk (CD) drive, a CD-Recordable (CD-R) drive, or other suitable removable and/or fixed storage unit. Memory unit134may include, for example, a Random Access Memory (RAM), a Read Only Memory (ROM), a Dynamic RAM (DRAM), a Synchronous DRAM (SD-RAM), a Flash memory, a volatile memory, a non-volatile memory, a cache memory, a buffer, a short term memory unit, a long term memory unit, or other suitable memory units or storage units.

Reference is made toFIG. 2, which schematically illustrates a processor200according to some exemplary embodiments of the invention. Although the invention is not limited in this respect, processor200may be used to perform the functionality of processor104ofFIG. 1.

According to exemplary embodiments of the invention, processor200may be able to perform one or more encryption or decryption operations in accordance with the ″Advanced Encryption Standard—Federal Information Processing Standards Publication 197 of Nov. 26, 2001 (“the AES standard”), and/or the ″Data Encryption Standard—Federal Information Processing Standards Publication 46-3 of Oct. 25, 1999 (“the DES standard”), as described below. However, it will be appreciated by those skilled in the art, that processor200may be modified to enable performing encryption and/or decryption operations in accordance with any other desired encryption and/or decryption cipher, for example, as described by the RC4 standard, the triple DES (3DES) standard and the like.

According to some exemplary embodiments of the invention, processor200may include a register file212adapted to store, for example, one or more data blocks, e.g., 64-bit, 128-bit or 256-bit data blocks, as known in the art. Processor200may also include a memory controller202, a load/store module204, a Program Counter (PC)208, a result module209and/or any other suitable software and/or hardware, as are known in the art.

According to exemplary embodiments of the invention, processor200may also include an instruction decoder218and an Arithmetic Logic Unit (ALU)210able to perform at least one predetermined encryption or decryption operation on one or more bytes, e.g., of the data block stored by register file212, as described in detail below.

According to exemplary embodiments of the invention, memory controller202may be able to retrieve (“fetch”) from a memory (not shown) one or more predetermined encryption or decryption instructions, e.g., from a memory location provided by program counter208. Memory controller202may also retrieve an input data block from the memory and transfer the input data block, e.g., via load/store module204, to register file212. Instruction decoder218may be adapted to translate (“decode”) the one or more encryption or decryption instructions fetched by memory controller202and to provide ALU210with one or more corresponding operation instructions235. For example, instruction decoder218may include a command list including the one or more predetermined encryption or decryption instructions and one or more respective operation instructions to be provided to ALU210, e.g., via signal235, as described below. Instruction decoder may also control register file212, e.g., based on the decoded instructions, to provide ALU210with a first ALU input230and/or a second ALU input231, e.g., including one or more bytes of the input data block.

According to exemplary embodiments of the invention, ALU210may receive instruction235and execute an encryption or decryption operation corresponding to operation instruction235, i.e., by performing on input230and/or input231the encryption or decryption operation corresponding to operation instruction235, as described below.

According to some exemplary embodiments of the invention, ALU210may include one or more operation modules for performing one or more encryption/decryption operations, e.g., AES and/or DES encryption/decryption operations, on the data received via input230and/or input231. For example, ALU210may include an AES S-box module266, an AES mix-column module261, an AES shift-row module262, a DES initial-permutation module263, a DES inverse-initial-permutation module264, a DES F-permutation module265, and/or any other module adapted to perform a predetermined encryption or decryption operation, as described below.

According to some exemplary embodiments of the invention, ALU210may also include a selector, e.g., a multiplexer211, able to selectively provide one of modules261,262,263,264,265and266with an input corresponding to input230and/or input231in accordance with operation instruction235. For example, multiplexer211may provide AES shift-row module262with an input213corresponding to input230and/or input231, e.g., if operation instruction235includes an AES shift-row operation instruction. It will be appreciated by those skilled in the art that other embodiments of the invention may include any suitable hardware and/or circuitry for selectively providing one of the operation modules with an input corresponding to one or more inputs provided by register file212to ALU210, e.g., in accordance with operation instruction235.

According to some exemplary embodiments of the invention, ALU210may be able to perform on one or more bytes of the data block stored in register file212one or more AES encryption or decryption operations, as described below.

The AES defines an input state array, s, including, for example, 128 bits divided into sixteen 8-bit bytes (“words”), denoted Sr,ce.g., arranged in four columns and four rows, wherein sr,cdenotes the word of the r-th row and c-th column of s, and wherein r=0 . . . 3 and c=0 . . . 3.

According to some exemplary embodiments of the invention, the input data block retrieved by memory controller202may include an AES data block, e.g., including 128 bits, representing the state array s. For example, bits0-31of the AES data block may correspond to the first row of s, bits32-63of the 128-bit data block may correspond to the second row of s, bits64-95of the 128-bit data block may correspond to the third row of s, and bits96-127of the 128-bit data block may correspond to the first row of s. Accordingly, bits0-7,32-39,64-71and96-103may correspond to the first column of s; bits8-15,40-47,72-79and104-111may correspond to the second column of s; bits16-23,48-55,80-87and112-119may correspond to the third column of s; and bits24-31,56-63,88-95and120-127may correspond to the fourth column of s.

Although some exemplary embodiments of the invention described herein may refer to devices and/or methods of performing encryption and/or decryption operations on an AES state array including 128 bits, it will be appreciated by those skilled in the art that devices and/or methods according to embodiments of the invention may enable performing the encryption and/or decryption operations on a state array of any other configuration, for example, a state array including 256 bits.

According to exemplary embodiments of the invention, AES s-box module266may be able to receive, e.g., via input230and/or input231, at least one bit of the AES data block, and to provide an ALU output271corresponding to a result of the AES s-box operation performed on the at least one bit of the AES data block.

According to some exemplary embodiments of the invention, module266may be able to perform the AES shift-row operation on two or more bits of the AES data block simultaneously. For example, module262may be adapted to receive from register file212all 128 bits of the AES data block and perform the AES s-box operation simultaneously on substantially all bits of the AES data block, e.g., according to the following AES s-box table:

TABLE 1y0123456789abcdefx0637c777bf26b6fc53001672bfed7ab761ca82c97dfa5947f0add4a2af9ca472c02b7fd9326363ff7cc34a5e5f171d83115304c723c31896059a071280e2eb27b275409832c1a1b6e5aa0523bd6b329e32f84553d100ed20fcb15b6acbbe394a4c58cf6d0efaafb434d338545f9027f503c9fa8751a3408f929d38f5bcb6da2110fff3d28cd0c13ec5f974417c4a77e3d645d1973960814fdc222a908846eeb814de5e0bdbae0323a0a4906245cc2d3ac629195e479be7c8376d8dd54ea96c56f4ea657aae08cba78252e1ca6b4c6e8dd741f4bbd8b8ad703eb5664803f60e613557b986c11d9eee1f8981169d98e949b1e87e9ce5528dff8ca1890dbfe6426841992d0fb054bb16
wherein the value of output of module266corresponding to an input bit having a hexadecimal value {xy}, may be determined by the value located at the intersection of x-th row and y-th column of Table 1. For example, output271may have a value {ed} if the input the module266has a value {53}.

According to these exemplary embodiments, the command list of instruction decoder218may include, for example, the instruction AESSBOX xmm1,xmm2/m128. Upon receiving this instruction, e.g., from memory controller202, instruction decoder218may be adapted to control register file212to provide ALU with a 128-bit data block stored at a memory location xmm2, e.g., of register file212, to control ALU210, e.g., using instruction235, to execute the AES s-box operation, and to store output271at a memory location xmm1, e.g., of register file212.

According to exemplary embodiments of the invention, module266may include any suitable hardware implementation for performing the AES s-box operation on one or more rows of the AES data block, e.g., as describe below.

Reference is made toFIG. 3, which schematically illustrates a S-box module300in accordance with some exemplary embodiments of the invention. Although the invention is not limited in this respect, S-box module300may be used to perform the functionality of S-box module266ofFIG. 2.

According to exemplary embodiments of the invention, S-box module300may include a plurality of s-box transform elements, each able to receive a byte of an input data block302and provide an output byte having a value corresponding to the S-box transformation of the value of the input byte. For example, input data block302may include a 128-bit data block including sixteen 8-bit bytes330-345, and S-box module300may include sixteen s-box transformation elements310-325, able to receive bytes330-345and produce sixteen output bytes350-365of an output data block304, respectively. Elements310-325may include any suitable circuitry and/or hardware for producing an output byte having a value corresponding to an S-box transformation of a value of a received input byte. For example, one or more of elements310-325may include a Look Up Table (LUT) including the 256 values of Table 1 and adapted to produce an 8-bit output byte having one of the 256 values corresponding to the value of an 8-bit input byte.

Referring back toFIG. 2, according to exemplary embodiments of the invention, AES shift-row module262may be able to receive, e.g., via input230and/or input231, at least one row of the AES data block, and to provide an ALU output271corresponding to a result of the AES shift-row operation performed on the at least one row of the AES data block.

According to some exemplary embodiments of the invention, module262may be able to perform the AES shift-row operation on two or more rows of the AES data block simultaneously. For example, module262may be adapted to receive from register file212all 128 bits of the AES data block and perform the AES shift-row operation simultaneously on substantially all rows of the AES data block, e.g., according to the following pseudo code:DEST[31-0]<--SRC[31-0]DEST[63-32]<--SRC[63-32]<<<8DEST[95-64]<--SRC[95-64]<<<16DEST[127-96]<--SRC[127-96]<<<24
wherein SRC[31-0], SRC[63-32], SRC[95-64] and SRC[127-96] denote bits0-31,32-63,64-95and96-127of the input to module262, respectively, DEST[31-0], DEST [63-32], DEST [95-64] and DEST [127-96] denote bits0-31,32-63,64-95and96-127of output271, respectively, and <<<8, <<<16, <<<24 denote a cyclic shift left of 8 bits, 16 bits and 24 bits, respectively, as known in the art.

According to these exemplary embodiments, the command list of instruction decoder218may include, for example, the instruction AESSHIFTROW xmm1,xmm2/m128. Upon receiving this instruction, e.g., from memory controller202, instruction decoder218may be adapted to control register file212to provide ALU with a 128-bit data block stored at memory location xmm2, to control ALU210, e.g., using instruction235, to perform the AES shift-row operation, and to store output271at memory location xmm1.

According to exemplary embodiments of the invention, module262may include any suitable hardware implementation for performing the AES shift-row operation on one or more rows of the AES data block, e.g., as known in the art.

According to exemplary embodiments of the invention, AES mix-column module261may be able to receive, e.g., via input230and/or input231, at least one column of the AES data block, and to provide ALU output271corresponding to a result of the AES mix-column operation performed on the at least one row of the AES data block. According to some exemplary embodiments of the invention, module261may be able to perform the AES mix-column operation on two or more columns of the AES data block simultaneously. For example, module261may be adapted to receive from register file212all 128 bits of the AES data block and perform the AES mix-column operation simultaneously on substantially all columns of the AES data block, e.g., according to the following equation set:
S″0,c=({02}·S0,c)⊕({03}·S1,c)⊕S2,c⊕S3,c
S″1,c=S0,c⊕({02}·S1,c)⊕({03}·S2,c)⊕S3,c
S″2,c=S0,3⊕S1,c⊕({02}·S2,c)⊕({03}·S3,c)
S″3,c=({03}·S0,c)⊕S1,c⊕S2,c⊕({02}·S3,c)  (1)
wherein s′r,cdenotes the value of byte sr,cof the state array after performing the ShiftRow operation, wherein the symbol “⊕” denotes an addition modulo2operation, i.e., a bitwise XOR, and wherein the symbol “·” denotes a polynomial multiplication modulo m(x)=x8+x4+x3+x+1.

According to these exemplary embodiments, the command list of instruction decoder218may include, for example, the instruction AESMIXCOL xmm1,xmm2/m128. Upon receiving this instruction, e.g., from memory controller202, instruction decoder218may be adapted to control register file212to provide ALU with a 128-bit data block stored at memory location xmm2, to control ALU210, e.g., using instruction235, to perform the AES mix-column operation, and to store output271at memory location xmm1.

According to exemplary embodiments of the invention, module261may include any suitable hardware implementation for performing the AES mix-column operation, e.g., as known in the art.

According to some exemplary embodiments of the invention, ALU210may be able to perform one or more DES encryption or decryption operations, as described below.

The DES defines encryption and decryption algorithms, which may include iteratively performing on a 64-bit data block a plurality of encryption and/or decryption operations, e.g., including the DES initial permutation operation, the DES inverse initial permutation operation, and the F-permutation operation.

According to some exemplary embodiments of the invention, the 64-bit data block may be represented using a DES data block, which may be, for example, stored by register file212.

According to exemplary embodiments of the invention, DES initial permutation module263may be able to receive, e.g., via input230and/or input231, one or more bits of the DES data block and provide ALU output271corresponding to a result of the DES initial permutation operation performed on the one or more bits of the DES data block. For example, module263may be adapted to simultaneously receive all 64 bits of the DES block and simultaneously perform the DES initial permutation operation on substantially all 64 bits of the DES block. For example, module263may provide output271by replacing each bit of the DES data block with another bit of the DES data block, e.g., according to the following permutation table (“the DES IP table”):

TABLE 2IP58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157
wherein each number in Table 2 relates to the location in the DES data block of the bit to be outputted by module263. For example, the first, second and third bits of output271may include the 58th, 50th, and 42ndbits of the DES data block, respectively.

According to these exemplary embodiments, the command list of instruction decoder218may include, for example, the instruction DESINITPER xmm1,xmm2/nz64. Upon receiving this instruction, e.g., from memory controller202, instruction decoder218may be adapted to control register file212to provide ALU with a 64-bit data block stored at memory location xmm2, to control ALU210, e.g., using instruction235, to perform the DES initial permutation operation, and to store output271at memory location xmm1.

According to exemplary embodiments of the invention, module263may include any suitable hardware implementation for performing the DES initial permutation operation, e.g., as known in the art.

According to exemplary embodiments of the invention, DES inverse initial permutation module264may be able to receive, e.g., via input230and/or input231, one or more bits of the DES data block and provide ALU output271corresponding to a result of the DES inverse initial permutation operation performed on the one or more bits of the DES data block. For example, module264may be adapted to simultaneously receive all 64 bits of the DES block and simultaneously perform the DES inverse initial permutation operation on substantially all 64 bits of the DES block. For example, module264may provide output271by replacing each bit of the DES data block with another bit of the DES data block, e.g., according to the following permutation table (“the DES IP−1table”):

TABLE 3IP−140848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725
wherein each number in Table 3 relates to the location in the DES data block of the bit to be outputted by module264. For example, the first, second and third bits of output271may include the 40th, 8th, and 48thbits of the DES data block, respectively.

According to these exemplary embodiments, the command list of instruction decoder218may include, for example, the instruction DESINVINITPER xmm1,xmm2/m64. Upon receiving this instruction, e.g., from memory controller202, instruction decoder218may be adapted to control register file212to provide ALU with a 64-bit data block stored at memory location xmm2, to control ALU210, e.g., using instruction235, to perform the DES inverse-initial permutation operation, and to store output271at memory location xmm1.

According to exemplary embodiments of the invention, module264may include any suitable hardware implementation for performing the DES inverse initial permutation operation, e.g., as known in the art.

According to exemplary embodiments of the invention, DES F-permutation module265may be able to receive, e.g., via input230and/or input231, one or more bits of the DES data block and provide ALU output271corresponding to a result of the DES F-permutation operation performed on the one or more bits of the DES data block. For example, module265may be adapted to simultaneously receive all 64 bits of the DES block and simultaneously perform the DES F-permutation operation on substantially all 64 bits of the DES block. For example, module265may provide output271according to the following pseudo code:DEST[63-32]=SRC[31-0]DEST[31-0]=f(SRC[63-32],K)
wherein K denotes 48 bits of a predetermined Key array as defined by the DES, and wherein f(SRC[63-32], K) denotes a cipher function as defined by the DES. For example, f(SRC[63-32], K) may be provided by the following pseudo code:

TABLE 4E BIT-SELECTION TABLE3212345456789891011121312131415161716171819202120212223242524252627282928293031321
wherein S(A) denotes a permutation transforming 48 bit data block A into a 32 bit data block B, e.g., using a set of eight sub-permutations each for transforming six bits of A into 4 bits, as defined by the DES, and wherein P(B) denotes a P permutation, e.g., according to the following “P permutation table”, wherein each number in the “P permutation table” relates to the location in the data block B of the bit to be outputted:

According to these exemplary embodiments, the command list of instruction decoder218may include, for example, the instruction DESFPERM xmm1, xmm2, xmm3/m64. Upon receiving this instruction, e.g., from memory controller202, instruction decoder218may be adapted to control register file212to provide ALU with a 64-bit data block stored at memory location xmm2 and a 48 bit data block corresponding to the DES key and stored at memory location xmm3, to control ALU210, e.g., using instruction235, to perform the DES F-permutation operation, and to store output271at memory location xmm1.

According to exemplary embodiments of the invention, module265may include any suitable hardware implementation for performing the DES F-permutation operation., e.g., as known in the art.

Reference is now made toFIG. 4, which schematically illustrates a method of executing one or more encryption or decryption operations according to some exemplary embodiments of the invention.

As indicated at block402, the method may include generating an instruction operation based on a predetermined encryption or decryption instruction, e.g., using an instruction decoder as described above with reference toFIG. 2.

As indicated at block404, the method may also include performing on at least part of an input data block a predetermined encryption or decryption operation according to the instruction operation. Performing the predetermined operation may include, for example, simultaneously performing the predetermined operation on one or more bits of the input data block, e.g., as described above.

According to some exemplary embodiments of the invention, the input data block may include an input state array, and the predetermined operation may include an encryption or decryption operation according to the advanced encryption standard, e.g., a shift rows operation, a mix-column operation or an s-box transformation operation as described above with reference toFIG. 2. According to other exemplary embodiments of the invention, the predetermined operation may include an encryption or decryption operation according to the data encryption standard, and the predetermined operation may include an initial permutation operation, an inverse initial permutation operation, or an F-permutation operation.

Embodiments of the present invention may be implemented by software, by hardware, or by any combination of software and/or hardware as may be suitable for specific applications or in accordance with specific design requirements. Embodiments of the present invention may include units and sub-units, which may be separate of each other or combined together, in whole or in part, and may be implemented using specific, multi-purpose or general processors, or devices as are known in the art. Some embodiments of the present invention may include buffers, registers, storage units and/or memory units, for temporary or long-term storage of data and/or in order to facilitate the operation of a specific embodiment.