METHOD AND SYSTEM FOR BLOCK CIPHER ENCRYPTION

FIELD OF THE INVENTION

The present invention relates to methods of encryption, and more particularly, to Feistel based block cipher methods of encryption

BACKGROUND OF THE INVENTION

Many encryption methods are known in the art. Of the known methods, many methods are block methods in which a block of plain text is iteratively altered according to a predefined rule; each such iteration is also known as a "round".

Many block encryption methods can be viewed as specific cases of Feistel networks, also termed herein "Feistel cipher methods", or "Feistel-like cipher methods"; a single round of a Feistel cipher method is termed herein a "Feistel cipher round".

Feistel ciphers are described in the Handbook of Applied

Cryptography (A. Menezes, P. van Oorschot, and S. Vanstone, CRC Press, 1996.

The Handbook of Applied Cryptography (HAC) is available on the Internet at www.cacr.math.uwaterloo.ca/hac). The discussion of Feistel ciphers in HAC, on pages 250 - 259, is incorporated herein by reference.

A Feistel cipher is an iterated block cipher mapping a plaintext (comprising two parts, LQ and RQ), for t-bit blocks LQ and RQ, to a ciphertext (R _r and Ly), through an r-round process where r > 1. For 1 < i < r, round I maps (Lf _], Ri-]) using key Kf to (Lf, Rf) as follows: Lf = Rf_], Rf = Lf_] ®f(Rf_j, Kj), where each subkey Kf is derived from the cipher key K (HAC, page 251).

Those skilled in the art will appreciate that although the definition above is for blocks LQ and RQ of equal sizes, equality of the sizes is not mandatory.

Decryption of a Feistel cipher is often achieved using the same r- round process but with subkeys used in reverse order, K _r through K^ .

Throughout the present specification and claims, the terms "first half and "second half are used to mean one of either: "right half or "left half.

Types of block ciphers which are cases of Feistel networks include the following well-known methods: DES, Lucifer, FEAL, Khufu, Khafre, LOKI, GOST, CAST, and Blowfish.

Feistel ciphers are also discussed in Applied Cryptography, Second Edition (B. Schneier, John Wiley and Sons, Inc., 1996) on pages 347 - 351. The discussion of Feistel ciphers in Applied Cryptography, Second Edition is hereby incorporated herein by reference. DES is specified in FIPS 46-3, available on the Internet at: csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf. FIPS 46-3 is hereby incorporated herein by reference.

FOX: A New Family of Block Ciphers, (Pascal Junod and Serge Vaudenay, Selected Areas in Cryptography 2004: Waterloo, Canada, August 9-10, 2004. Revised papers, Lecture Notes in Computer Science. Springer- Verlag.) describes the design of a new family of block ciphers based on a Lai-Massey scheme, named FOX. The main features of the design, besides a very high security level, are a large implementation flexibility on various platforms as well as high performances. In addition, a new design of strong and efficient key-schedule algorithms is proposed. Evidence is provided that FOX is immune to linear and differential cryptanalysis.

How to Construct Pseudorandom Permutations From Pseudorandom Functions (M. Luby and C. Rackoff, SIAM Journal on Computing, 17:2, pp. 373— 386, April 1988), describes a method to efficiently construct a pseudorandom invertible permutation generator from a pseudorandom function generator. A practical result described in Luby- Rackoff is that any pseudorandom bit generator can be used to construct a block private key cryptosystem which is secure against chosen plaintext attacks, which is one of the strongest known attacks against a cryptosystem. The Serpent Cipher, specified at: www.ftp.cl. cam.ac.uk/ftp/users/rjal4/serpent.pdf, was an Advanced Encryption Standard (AES) candidate. The design of the serpent cipher design is highly

conservative, yet still allows a very efficient implementation. The serpent cipher uses S-boxes similar to those of DES in a new structure that simultaneously allows a more rapid avalanche, and a more efficient bitslice implementation.

Unpublished PCT application, PCT/IL2006/001167, filed 5 October 2006, of NDS Ltd. describes one preferred implementation of a Feistel-like cipher and a method of encrypting a block of data, the method including providing a combining unit operative to combine a key with a block of data, the block of data expressed as a block of bits, providing a mix and condense unit operative to mix bits included in the block of bits among themselves, receiving an input including the block of data expressed as the block of bits, combining, at the combining unit, the block of bits with a key, and mixing, at the mixing and condensing unit, the combined block of bits, wherein the mix and condense unit includes a plurality of layers, each layer among the plurality of layers including a plurality of mini- functions. Related apparatus and methods are described. The disclosure of Unpublished PCT application, PCT/IL2006/001167 is incorporated herein by reference.

The disclosures of all references mentioned above and throughout the present specification, as well as the disclosures of all references mentioned in those references, are hereby incorporated herein by reference.

SUMMARY OF THE INVENTION

The present invention seeks to provide an improved encryption method, and in particular an improved encryption method related to Feistel encryption methods. A Feistel-like cipher, described herein, is preferably designed to be easily implemented in hardware and difficult to implement in software.

There is thus provided in accordance with a preferred embodiment of the present invention a method of encrypting a block of data, the method including providing a combining unit operative to combine a key with a block of data, the block of data expressed as a block of bits, providing a mix and condense unit (MAC) operative to mix bits included in the block of bits among themselves, providing a plurality of layers of S-boxes, the S-boxes operative to receive an input including an input which has not yet been input into the mix and condense unit and to provide an output including an input to the mix and condense unit, receiving an input including the block of data expressed as the block of bits, combining, at the combining unit, the block of bits with a key, receiving an output of the combining unit as an input, substituting bits including the input to the plurality of layers of S-boxes with bits including the output of the plurality of layers of S-boxes, outputting the output of the plurality of layers of S-boxes to the mix and condense unit, and mixing, at the mix and condense unit, the output of the plurality of layers of S-boxes, thereby producing an encrypted block of bits.

Further in accordance with a preferred embodiment of the present invention the plurality of layers of S-boxes includes two layers of S-boxes.

Still further in accordance with a preferred embodiment of the present invention a diffusion layer, disposed between each layer of the plurality of S-boxes, routes the output of a first layer of S-boxes to a second layer of S-boxes, the output of the first layer of S-boxes including an input of the second layer of S- boxes.

Additionally in accordance with a preferred embodiment of the present invention each S-box of the plurality of S-boxes includes one S-box described in the Serpent cipher specification.

Moreover in accordance with a preferred embodiment of the present invention the two layers of S-boxes include a first layer of S-boxes including 25 S- boxes and a second layer of S-boxes including 25 S-boxes.

Further in accordance with a preferred embodiment of the present invention the combining unit is operative to perform a XOR operation.

Still further in accordance with a preferred embodiment of the present invention the method of encrypting cannot be efficiently implemented except on specialized hardware.

Additionally in accordance with a preferred embodiment of the present invention the MAC comprises a plurality of layers of mini-functions.

Moreover in accordance with a preferred embodiment of the present invention the plurality of layers of the MAC includes between 30 layers and 50 layers, inclusive.

Further in accordance with a preferred embodiment of the present invention a mini-function layer includes two micro-functions one balanced micro- function, and one non-linear micro-function.

Still further in accordance with a preferred embodiment of the present invention the mini-function layer is operative to perform the following receiving an input, splitting the input, at a splitter, into a block of balancing bits and a block of remaining input bits, executing the method of the non-linear micro- function on the block of remaining input bits, inputting the result of the non-linear micro-function into the balanced micro-function, executing the method of the balanced micro-function on the result of the non-linear micro-function and the balancing bits, and outputting a result. Additionally in accordance with a preferred embodiment of the present invention the method further including performing an invertible transformation on the block of balancing bits prior to the executing the method of the balanced micro-function.

Moreover in accordance with a preferred embodiment of the present invention the invertible transformation includes an invertible transformation S- box.

Further in accordance with a preferred embodiment of the present invention and wherein the invertible transformation S-box includes a 2bit-to-2bit S-box.

Still further in accordance with a preferred embodiment of the present invention the method further including providing a first function Fj and a second function Fj, providing a round key generation function, the round key generation function being operative to utilize, in any given round, exactly one of the first function Fj, and the second function Fj, providing a round mixing function, the round mixing function being operative to utilize, in any given round, exactly one of the first function Fj, and the second function Fi, utilizing the round key generation function in at least a first round to generate a second round key for use in a second round, and utilizing the round mixing function in at least the first round to mix a first round key with a cipher state, wherein one of the following is performed in the first round the round key generation function utilizes the first function Fj to generate the second round key for use in the second round, substantially simultaneously with the round key mixing function utilizing the second function Fi to mix the first round key with the cipher state, and the round key generation function utilizes the second function Fi to generate the second round key for use in the second round, substantially simultaneously with the round key mixing function utilizing the first function Fj to mix the first round key with the cipher state.

There is also provided with another preferred embodiment of the present invention a method of encrypting a block of data, the method including providing an expansion unit operative to expand the block of data, expressed as a block of bits, from a first bit size to a second bit size, the second bit size being greater than the first bit size, providing a combining unit operative to combine an expanded block of data with a key, providing a mix and condense unit (MAC) operative to mix the bits of a combined expanded block of data of the second bit size and condense the bit size of the input to a third bit size, the third bit size being less than the second bit size, providing a plurality of layers of S-boxes, the S- boxes operative to receive an input including an input which has not yet been input

into the mix and condense unit and to provide an output including an input, expressed as a block of data, to the mix and condense unit, receiving an input including the block of data expressed as the block of bits, inputting the block of bits into the expansion unit, and therein expanding the block of bits to a block of bits of the second bit size, combining, at the combining unit, the block of bits of the second bit size with a key, substituting bits including the input to the plurality of layers of S-boxes with bits including the output of the plurality of layers of S- boxes, outputting the output of the plurality of layers of S-boxes to the mix and condense unit, and mixing, at the mix and condense unit, the output of the plurality of layers of S-boxes, the output of the plurality of layers of S-boxes including a block of bits of the second bit size, and condensing, at the mix and condense unit, the block of bits of the second bit size to a block of bits of the third size, thereby producing an encrypted block of data, the encrypted block of data being expressed as a block of bits of the third bit size, wherein the mix and condense unit includes a plurality of layers, each layer among the plurality of layers including a plurality of mini-functions.

Further in accordance with a preferred embodiment of the present invention the plurality of layers of S-boxes includes two layers of S-boxes.

Still further in accordance with a preferred embodiment of the present invention a diffusion layer, disposed between each layer of the plurality of S-boxes, routes the output of a first layer of S-boxes to a second layer of S-boxes, the output of the first layer of S-boxes including an input of the second layer of S- boxes.

Additionally in accordance with a preferred embodiment of the present invention each S-box of the plurality of S-boxes includes one S-box described in the Serpent cipher specification.

Moreover in accordance with a preferred embodiment of the present invention the two layers of S-boxes include a first layer of S-boxes including 25 S- boxes and a second layer of S-boxes including 25 S-boxes. Further in accordance with a preferred embodiment of the present invention the first bit size is equal to the third bit size.

Still further in accordance with a preferred embodiment of the present invention the first bit size is equal to 64 bits.

Additionally in accordance with a preferred embodiment of the present invention the second bit size is equal to 100 bits. Moreover in accordance with a preferred embodiment of the present invention the third bit size is equal to 64 bits.

Further in accordance with a preferred embodiment of the present invention the combining unit is operative to perform a XOR operation.

Still further in accordance with a preferred embodiment of the present invention the expansion unit includes a linear transformation.

Additionally in accordance with a preferred embodiment of the present invention the linear transformation includes an operation wherein each input bit influences at least two output bits.

Moreover in accordance with a preferred embodiment of the present invention the linear transformation includes an operation wherein each bit of the key influences one output bit.

Further in accordance with a preferred embodiment of the present invention the linear transformation includes an operation wherein any small set of input bits influences a larger set of output bits. Still further in accordance with a preferred embodiment of the present invention the linear transformation includes an operation wherein indices are selected so as to be spread equally between input bits and output bits.

Additionally in accordance with a preferred embodiment of the present invention the expansion unit includes two layers of gates operative to combine two inputs.

Moreover in accordance with a preferred embodiment of the present invention the gates include XOR operation gates.

Further in accordance with a preferred embodiment of the present invention the method further includes a NOT operation gate after the XOR operation gates.

Still further in accordance with a preferred embodiment of the present invention the method of encrypting cannot be implemented except on specialized hardware.

Still further in accordance with a preferred embodiment of the present invention the MAC comprises a plurality of layers of mini-functions.

Additionally in accordance with a preferred embodiment of the present invention the plurality of layers of the MAC includes between 30 layers and 50 layers, inclusive.

Moreover in accordance with a preferred embodiment of the present invention a mini-function layer includes two micro-functions one balanced micro- function, and one non-linear micro-function.

Further in accordance with a preferred embodiment of the present invention the mini-function layer is operative to perform the following receiving an input, splitting the input, at a splitter, into a block of balancing bits and a block of remaining input bits, executing the method of the non-linear micro-function on the block of remaining input bits, inputting the result of the non-linear micro- function into the balanced micro-function, executing the method of the balanced micro-function on the result of the non-linear micro-function and the balancing bits, and outputting a result. Still further in accordance with a preferred embodiment of the present invention the method further includes performing an invertible transformation on the block of balancing bits prior to the executing the method of the balanced micro-function.

Additionally in accordance with a preferred embodiment of the present invention the invertible transformation includes an invertible transformation S-box.

Moreover in accordance with a preferred embodiment of the present invention the invertible transformation S-box includes a 2bit-to-2bit S-box.

Further in accordance with a preferred embodiment of the present invention the method further includes providing a first function Fj and a second function Fj, providing a round key generation function, the round key generation function being operative to utilize, in any given round, exactly one of the first

function Fj, and the second function Fi, providing a round mixing function, the round mixing function being operative to utilize, in any given round, exactly one of the first function Fj, and the second function Fi, utilizing the round key generation function in at least a first round to generate a second round key for use in a second round, and utilizing the round mixing function in at least the first round to mix a first round key with a cipher state, wherein one of the following is performed in the first round the round key generation function utilizes the first function Fj to generate the second round key for use in the second round, substantially simultaneously with the round key mixing function utilizing the second function Fi to mix the first round key with the cipher state, and the round key generation function utilizes the second function Fi to generate the second round key for use in the second round, substantially simultaneously with the round key mixing function utilizing the first function Fj to mix the first round key with the cipher state. There is also provided with still another preferred embodiment of the present invention a method of encrypting a block of data, the method including an emulation resistant combine key method included in a Feistel-like structure.

Further in accordance with a preferred embodiment of the present invention the method is implemented in hardware. Still further in accordance with a preferred embodiment of the present invention the method further includes mixing and condensing, the mixing and condensing including receiving an input of a block of data expressed as a block of bits, and mixing the bits of the block of data with a round key.

Additionally in accordance with a preferred embodiment of the present invention the method further includes providing an expansion unit operative to expand the block of data, expressed as a block of bits, from a first bit size to a second bit size, the second bit size being greater than the first bit size, providing a combining unit operative to combine an expanded block of data with a key, providing a mix and condense unit (MAC) operative to mix the bits of a combined expanded block of data of the second bit size and condense the bit size of the input to a third bit size, the third bit size being less than the second bit size,

providing a plurality of layers of S-boxes, the S-boxes operative to receive an input including an input which has not yet been input into the mix and condense unit and to provide an output including an input to the mix and condense unit, receiving an input including the block of data expressed as the block of bits, inputting the block of bits into the expansion unit, thereby expanding the block of bits to a block of bits of the second bit size, combining, at the combining unit, the block of bits of the second bit size with a key, substituting bits including the input to the plurality of layers of S-boxes with bits including the output of the plurality of layers of S-boxes, outputting the output of the plurality of layers of S-boxes to the mix and condense unit, and mixing, at the mix and condense unit, the block of bits of the second bit size, and condensing, at the mix and condense unit, the block of bits of the second bit size to a block of bits of the third size, thereby producing an encrypted block of data, the encrypted block of data being expressed as a block of bits of the third bit size. Moreover in accordance with a preferred embodiment of the present invention the plurality of layers of S-boxes includes two layers of S-boxes.

Further in accordance with a preferred embodiment of the present invention a diffusion layer, disposed between each layer of the plurality of S- boxes, routes the output of a first layer of S-boxes to a second layer of S-boxes, the output of the first layer of S-boxes including an input of the second layer of S- boxes.

Still further in accordance with a preferred embodiment of the present invention each S-box of the plurality of S-boxes includes one S-box described in the Serpent cipher specification. Additionally in accordance with a preferred embodiment of the present invention the two layers of S-boxes include a first layer of S-boxes including 25 S-boxes and a second layer of S-boxes including 25 S-boxes.

Moreover in accordance with a preferred embodiment of the present invention the first bit size is equal to the third bit size. Further in accordance with a preferred embodiment of the present invention the first bit size is equal to 64 bits.

Still further in accordance with a preferred embodiment of the present invention the second bit size is equal to 100 bits.

Additionally in accordance with a preferred embodiment of the present invention the third bit size is equal to 64 bits. Moreover in accordance with a preferred embodiment of the present invention the combining unit is operative to perform a XOR operation.

Further in accordance with a preferred embodiment of the present invention the expansion unit includes a linear transformation.

Still further in accordance with a preferred embodiment of the present invention the linear transformation includes an operation wherein each input bit influences at least two output bits.

Additionally in accordance with a preferred embodiment of the present invention the linear transformation includes an operation wherein each bit of the key influences one output bit. Moreover in accordance with a preferred embodiment of the present invention the linear transformation includes an operation wherein any small set of input bits influences a larger set of output bits.

Further in accordance with a preferred embodiment of the present invention the linear transformation includes an operation wherein indices are selected so as to be spread equally between input bits and output bits.

Still further in accordance with a preferred embodiment of the present invention the mix and condense unit includes a plurality of layers, each layer among the plurality of layers including a plurality of mini-functions.

Additionally in accordance with a preferred embodiment of the present invention and wherein the plurality of layers of the MAC includes between 30 layers and 50 layers, inclusive.

Moreover in accordance with a preferred embodiment of the present invention a mini-function layer includes two micro-functions one balanced micro- function, and one non-linear micro-function. Further in accordance with a preferred embodiment of the present invention the mini-function layer is operative to perform the following receiving an input, splitting the input, at a splitter, into a block of balancing bits and a block

of remaining input bits, executing the method of the non-linear micro-function on the block of remaining input bits, inputting the result of the non-linear micro- function into the balanced micro-function, executing the method of the balanced micro-function on the result of the non-linear micro-function and the balancing bits, and outputting a result.

Still further in accordance with a preferred embodiment of the present invention the method further includes performing an invertible transformation on the block of balancing bits prior to the executing the method of the balanced micro-function. Additionally in accordance with a preferred embodiment of the present invention the invertible transformation includes an invertible transformation S-box.

Moreover in accordance with a preferred embodiment of the present invention the invertible transformation S-box includes a 2bit-to-2bit S-box. Further in accordance with a preferred embodiment of the present invention The method further includes providing a first function Fj and a second function Fi, providing a round key generation function, the round key generation function being operative to utilize, in any given round, exactly one of the first function Fj, and the second function Fi, providing a round mixing function, the round mixing function being operative to utilize, in any given round, exactly one of the first function Fj, and the second function Fi, utilizing the round key generation function in at least a first round to generate a second round key for use in a second round, and utilizing the round mixing function in at least the first round to mix a first round key with a cipher state, wherein one of the following is performed in the first round the round key generation function utilizes the first function Fj to generate the second round key for use in the second round, substantially simultaneously with the round key mixing function utilizing the second function Fi to mix the first round key with the cipher state, and the round key generation function utilizes the second function Fi to generate the second round key for use in the second round, substantially simultaneously with the round

key mixing function utilizing the first function Fj to mix the first round key with the cipher state.

There is also provided in accordance with still another preferred embodiment of the present invention a method of encrypting a block of data, the method including providing a combining unit operative to combine the block of data with a key, providing a mixing unit operative to mix the bits of a combined key and block of data, providing a plurality of layers of S-boxes, the S-boxes operative to receive an input including an input which has not yet been input into the mixing unit and to provide an output including an input to the mixing unit, receiving an input including the block of data expressed as a block of bits, combining, at a combining unit, the block of bits with a key, substituting bits including the input to the plurality of layers of S-boxes with bits including the output of the plurality of layers of S-boxes, outputting the output of the plurality of layers of S-boxes as a second block of bits to the mixing unit, and mixing, at the mixing unit, the second block of bits, thereby producing an encrypted block of data, wherein the mixing unit includes a plurality of layers, each layer including a plurality of mini-functions.

Further in accordance with a preferred embodiment of the present invention the plurality of layers of S-boxes includes two layers of S-boxes. Still further in accordance with a preferred embodiment of the present invention a diffusion layer, disposed between each layer of the plurality of S-boxes, routes the output of a first layer of S-boxes to a second layer of S-boxes, the output of the first layer of S-boxes including an input of the second layer of S- boxes. Additionally in accordance with a preferred embodiment of the present invention each S-box of the plurality of S-boxes includes one S-box described in the Serpent cipher specification.

Moreover in accordance with a preferred embodiment of the present invention the two layers of S-boxes include a first layer of S-boxes including 25 S- boxes and a second layer of S-boxes including 25 S-boxes.

Further in accordance with a preferred embodiment of the present invention the plurality of layers of the mixing unit includes between 30 and 50 layers, inclusive.

Still further in accordance with a preferred embodiment of the present invention the combining unit is operative to perform a XOR operation.

Additionally in accordance with a preferred embodiment of the present invention a mini-function layer includes two micro-functions one balanced micro-function, and one non-linear micro-function.

Moreover in accordance with a preferred embodiment of the present invention the mini-function layer is operative to perform the following receiving an input, splitting the input, at a splitter, into a block of balancing bits and a block of remaining input bits, executing the method of the non-linear micro-function on the block of remaining input bits, inputting the result of the non-linear micro- function into the balanced micro-function, executing the method of the balanced micro-function on the result of the non-linear micro-function and the balancing bits, and outputting a result.

Further in accordance with a preferred embodiment of the present invention The method further includes performing an invertible transformation on the block of balancing bits prior to the executing the method of the balanced micro-function.

Still further in accordance with a preferred embodiment of the present invention the invertible transformation includes an invertible transformation S-box.

Additionally in accordance with a preferred embodiment of the present invention the invertible transformation S-box includes a 2bit-to-2bit S-box.

Moreover in accordance with a preferred embodiment of the present invention the method further includes providing an expansion unit operative to expand the block of data, expressed as a block of bits, from a first bit size to a second bit size, the second bit size being greater than the first bit size, and prior to the combining, inputting the block of bits into the expansion unit, and therein expanding the block of bits to a block of bits of the second bit size.

Further in accordance with a preferred embodiment of the present invention the method further includes after the mixing, condensing, at the mix and condense unit, the block of bits of the second bit size to a block of bits of a third size, thereby producing an encrypted block of data, the encrypted block of data being expressed as a block of bits of the third bit size.

Still further in accordance with a preferred embodiment of the present invention the method further includes providing a first function Fj and a second function Fj, providing a round key generation function, the round key generation function being operative to utilize, in any given round, exactly one of the first function Fj, and the second function Fj, providing a round mixing function, the round mixing function being operative to utilize, in any given round, exactly one of the first function Fj, and the second function Fj, utilizing the round key generation function in at least a first round to generate a second round key for use in a second round, and utilizing the round mixing function in at least the first round to mix a first round key with a cipher state, wherein one of the following is performed in the first round the round key generation function utilizes the first function Fj to generate the second round key for use in the second round, substantially simultaneously with the round key mixing function utilizing the second function Fj to mix the first round key with the cipher state, and the round key generation function utilizes the second function Fi to generate the second round key for use in the second round, substantially simultaneously with the round key mixing function utilizing the first function Fj to mix the first round key with the cipher state.

There is also provided in accordance with still another preferred embodiment of the present invention a method including combining a control input derived from a right part of a Feistel-like structure with a transformation input including a left part of the Feistel-like structure, and producing an output including a combination of bits included in the control input and bits included in the transformation input, wherein no bit of the combination of bits includes a linear combination of bits from the control input and bits from the transformation input.

Further in accordance with a preferred embodiment of the present invention, with respect to a fixed control input, the method includes an invertible method.

Still further in accordance with a preferred embodiment of the present invention the inverse of the method is not identical to the method.

Additionally in accordance with a preferred embodiment of the present invention the method includes a non-linear layer including at least one S- box.

Moreover in accordance with a preferred embodiment of the present invention the method also including a linear transformation of the control input and the transformation input.

Further in accordance with a preferred embodiment of the present invention the method also including splitting, at a control input splitter, the control input, into a plurality of control input sub-blocks, splitting, at a transformation input splitter, the transformation input, into a plurality of transformation input sub-blocks, linearly combining each one of the plurality of control input sub-blocks with a corresponding one of the plurality of transformation input sub-blocks, and joining the result of the linear combing at a output joiner. Still further in accordance with a preferred embodiment of the present invention each one of the plurality of control input sub-blocks and a corresponding one of the plurality of transformation input sub-blocks include sub- blocks of the same size.

Additionally in accordance with a preferred embodiment of the present invention a first sub-block of the plurality of control input sub-blocks includes a sub-block of a different size than a second sub-block of the plurality of control input sub-blocks.

Moreover in accordance with a preferred embodiment of the present invention the transformation input splitter permutes the transformation input prior to the splitting at the transformation input splitter.

Further in accordance with a preferred embodiment of the present invention the output joiner permutes an output after the joining operation.

Still further in accordance with a preferred embodiment of the present invention the linearly combining includes (A(C) x I) θ C, where C represents the control input sub-block, I represents the transformation input sub- block, and A(C) includes a matrix depending on C, of size mxm, where m is a size of the control input sub-block.

Additionally in accordance with a preferred embodiment of the present invention A(C)

where C[O...3] include bits included in the control input. Moreover in accordance with a preferred embodiment of the present invention the method also including a non-linear layer including at least one S- box.

Further in accordance with a preferred embodiment of the present invention an output from the linear transformation includes an input for the non- linear layer.

Still further in accordance with a preferred embodiment of the present invention an output from the non-linear layer includes a transformation input for the linear transformation.

Additionally in accordance with a preferred embodiment of the present invention at least one of the S-boxes includes an S-box according to the Serpent Cipher specification.

Moreover in accordance with a preferred embodiment of the present invention the S-box layer includes S-boxes which are simple to implement in hardware. Further in accordance with a preferred embodiment of the present invention the method is cryptographically secure and non-involutable.

There is also provided in accordance with still another preferred embodiment of the present invention an encryptor for encrypting a block of data, the encryptor including a combining unit operative to combine a key with a block

of data, the block of data being expressed as a block of bits, a mix and condense unit operative to mix bits included in the block of bits among themselves, and a plurality of layers of S-boxes, the S-boxes operative to receive an input including an input which has not yet been input into the mix and condense unit and to provide an output including an input to the mix and condense unit, wherein a received input including the block of data expressed as the block of bits is combined, at the combining unit, with a key, and bits included in the combined block of bits are, in each layer of the plurality of layers of S-boxes, substituted for other bits, thereby providing output bits, bits in the output bits are mixed among themselves at the mix and condense unit, and the mix and condense unit includes a plurality of layers, each layer among the plurality of layers including a plurality of mini-functions.

Further in accordance with a preferred embodiment of the present invention the encrypting cannot be efficiently implemented except on specialized hardware.

There is also provided in accordance with still another preferred embodiment of the present invention an encryptor for encrypting a block of data, the encryptor including an expansion unit operative to expand the block of data, expressed as a block of bits, from a first bit size to a second bit size, the second bit size being greater than the first bit size, thereby producing an expanded block of data, a combining unit operative to receive the expanded block of data from the expansion unit and combine the expanded block of data with a key thereby producing a combined expanded block of data of the second bit size, a mix and condense unit operative to mix the bits of the combined expanded block of data of the second bit size and condense the bit size of the combined expanded block of data of the second bit size to a third bit size, the third bit size being less than the second bit size, and a plurality of layers of S-boxes, the S-boxes operative to receive an input including an input which has not yet been input into the mix and condense unit and to provide an output including an input to the mix and condense unit, wherein the mix and condense unit includes a plurality of layers, each layer among the plurality of layers including a plurality of mini-functions.

Further in accordance with a preferred embodiment of the present invention the encryptor cannot be implemented except on specialized hardware.

There is also provided in accordance with still another preferred embodiment of the present invention an encryptor operative to encrypt a block of data, the encryptor including a combining unit operative to combine the block of data with a key and produce a combined key and block of data, a mixing unit operative to mix the bits of the combined key and block of data, and a plurality of layers of S-boxes, the S-boxes operative to receive an input including an input which has not yet been input into the mix and condense unit and to provide an output including an input to the mix and condense unit, wherein the mixing unit includes a plurality of layers, each layer including a plurality of mini-functions.

There is also provided in accordance with still another preferred embodiment of the present invention an apparatus including a combiner operative to combine a control input derived from a right part of a Feistel-like structure with a transformation input including a left part of the Feistel-like structure, an outputter operative to producing an output including a combination of bits included in the control input and bits included in the transformation input, and a plurality of layers of S-boxes, the S-boxes operative to receive an input including an input which has not yet been input into the mix and condense unit and to provide an output including an input to the mix and condense unit, wherein no bit of the combination of bits includes a linear combination of bits from the control input and bits from the transformation input.

There is also provided in accordance with still another preferred embodiment of the present invention a cipher device including a combine key right (CKR) unit, operative to receive a first portion of a message and to combine the first portion of the message with a key, the CKR including an expansion unit operative to expand the first portion of the message to a number of bits appropriate to a key size, thereby producing an expanded first portion of the message, a combining function unit operative to receive the expanded first portion of the message and combine the expanded first portion of the message with the key, thereby producing a combined output, a mixing and condensing function unit operative to receive the combined output and condensing the combined output,

and a plurality of layers of S-boxes disposed at least one of before the mixing and condensing function unit, each S-box among the plurality of S-boxes included in each of the plurality of layers of the S-boxes being operative to receive an input string of bits and substitute the input string of bits with an output string of bits, and a combine right - left (CRL) unit, operative to combine an output of the CKR with a second portion of the message.

Further in accordance with a preferred embodiment of the present invention the first portion of the message includes a right portion of the message, and the second portion of the message includes a left portion of the message. Still further in accordance with a preferred embodiment of the present invention the first portion of the message includes a left portion of the message, and the second portion of the message includes a right portion of the message.

Additionally in accordance with a preferred embodiment of the present invention the plurality of layers of S-boxes includes two layers of S-boxes. Moreover in accordance with a preferred embodiment of the present invention a diffusion layer, disposed between each layer of the plurality of S-boxes routes the output of a first layer of S-boxes to a second layer of S-boxes, the output of the first layer of S-boxes including an input of the second layer of S-boxes. There is also provided in accordance with still another preferred embodiment of the present invention in a cipher device including a combine key right (CKR) unit, operative to receive a first portion of a message and to combine the first portion of the message with a key, the CKR including an expansion unit operative to expand the first portion of the message to a number of bits appropriate to a key size, thereby producing an expanded first portion of the message, a combining function unit operative to receive the expanded first portion of the message and combine the expanded first portion of the message with the key, thereby producing a combined output, a mixing and condensing function unit operative to receive the combined output and condensing the combined output, and a combine right - left (CRL) unit, operative to combine an output of the CKR with a second portion of the message, an improvement including adding a plurality of layers of S-boxes disposed before the mixing and condensing function unit,

thereby increasing a level of confusion of an output ciphertext and making the ciphertext more resistant to a differential cryptographic attack.

Further in accordance with a preferred embodiment of the present invention the first portion of the message includes a right portion of the message, and the second portion of the message includes a left portion of the message.

Still further in accordance with a preferred embodiment of the present invention the first portion of the message includes a left portion of the message, and the second portion of the message includes a right portion of the message. Additionally in accordance with a preferred embodiment of the present invention the plurality of layers of S-boxes includes two layers of S-boxes. Moreover in accordance with a preferred embodiment of the present invention a diffusion layer disposed between each layer of the plurality of S-boxes routes the output of a first layer of S-boxes to a second layer of S-boxes, the output of the first layer of S-boxes including an input of the second layer of S-boxes.

BRIEF DESCRIPTION OF THE DRAWINGS AND APPENDICES

The present invention will be understood and appreciated more fully from the following detailed description, taken in conjunction with the drawings in which: Fig. 1 is an illustration of a hardened Feistel-like structure constructed and operative in accordance with a preferred embodiment of the present invention;

Fig. 2A is an illustration of a Combine Key RightPart function comprised in the hardened Feistel-like structure of Fig. 1; Fig. 2B is an illustration of an alternative preferred embodiment of the Combine Key RightPart function comprised in the hardened Feistel-like structure of Fig. 1;

Fig. 3 is an illustration of a preferred implementation of hardware for a RightPart Expansion Function comprised in the Combine Key RightPart function of Figs. 2A and 2B;

Fig. 4 is an illustration of a preferred embodiment of a mini- function, the mini-function serving as a building block for a Mix and Condense function comprised in the Combine Key RightPart function of Figs. 2A and 2B;

Fig. 5 is an illustration of a Combine RightPart Combine LeftPart function comprised in the hardened Feistel-like structure of Fig. 1 ;

Fig. 6 is an illustration of one preferred implementation of a linear layer in the Combine RightPart Combine LeftPart function of Fig. 5;

Fig. 7 is an illustration of one preferred implementation of an S- boxes layer in the Combine RightPart Combine LeftPart function of Fig. 5; Fig. 8 is an illustration of one preferred implementation of a key expansion function comprised in the hardened Feistel-like structure of Fig. 1;

Fig. 9 is an illustration of one preferred implementation of round key generation utilizing the Mix and Condense function in the key expansion function of Fig. 8; Figs. 10 - 13 are simplified flowchart illustrations of preferred alternative methods of operation of the hardened Feistel-like structure of Fig. 1 , in accordance with preferred embodiments thereof;

Fig. 14 is a simplified block diagram illustration of a system for robust cipher design constructed and operative in accordance with a preferred embodiment of the invention described in Appendix B;

Fig. 15 is a time line showing one preferred implementation of the relationship between key expansion and encryption rounds in a cipher designed according to the method of Fig. 14;

Fig. 16 is a simplified block diagram illustration depicting the use of MUX and DEMUX modules in a preferred implementation of the method of Fig. 14; Fig. 17 is a simplified block diagram illustration of a preferred implementation of a round key generation function operative to generate round keys in a cipher designed according to the method of Fig. 14;

Fig. 18 is a simplified block diagram illustration of four rounds of a typical Feistel block cipher constructed and operative in accordance with the system of Fig. 14;

Fig. 19 is a simplified block diagram illustration of four rounds of a typical AES-like block cipher constructed and operative in accordance with the system of Fig. 14;

Fig. 20 is a simplified block diagram illustration of eight rounds of a typical Feistel block cipher constructed and operative in accordance with an alternative preferred embodiment of the system of Fig. 14;

Fig. 21 is a simplified block diagram illustration of eight rounds of a typical AES-like block cipher constructed and operative in accordance with an alternative preferred embodiment of the system of Fig. 14; Fig. 22 is a simplified block diagram illustration of eight rounds of a typical Feistel block cipher constructed and operative in accordance with yet another alternative preferred embodiment of the system of Fig. 14;

Fig. 23 is a simplified block diagram illustration of eight rounds of a typical AES-like block cipher constructed and operative in accordance with yet another alternative preferred embodiment of the system of Fig. 14;

Fig. 24 is an illustration of a hardened Feistel-like structure constructed and operative in accordance with a preferred embodiment of the present invention;

Fig. 25 is an illustration of an alternative preferred embodiment of the hardened Feistel-like structure of Fig. 24;

Fig. 26 is a simplified block diagram of a preferred implementation of a MixKey function of the system of Fig. 24; and

Fig. 27 is a simplified block diagram of a CombParts function of the system of Fig. 24.

The following Appendices may be helpful in understanding certain preferred embodiments of the present invention:

Appendix A comprises table describes one implementation of the relationship between bits output from the first layer of S-boxes and input into the second layer of S-boxes in the system of Fig. 2B.

Appendix B is a description of a method for robust cipher design, comprising a preferred method of key expansion and set up and a preferred implementation of a round key encryption function, the method of Appendix B comprising a preferred implementation of the Feistel-like structure of Fig. 1; Appendix C is a copy of Appendix A.5 of the Serpent Cipher specification, describing S-boxes SQ through Sγ of the Serpent Cipher; and

Appendix D comprises a description of certain alternative preferred embodiments of the present invention.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

Reference is now made to Fig. 1, which is an illustration of a hardened Feistel-like structure 100 constructed and operative in accordance with a preferred embodiment of the present invention. It is appreciated that Fig. 1 provides an illustration of data structures and methods for implementing an encryption network, the illustration being drawn in a format which is well known in the art. Fig. 1 depicts two rounds of the hardened Feistel-like structure 100, it being appreciated that a plurality of rounds comprising more than two rounds is preferred, similarly to the plurality of rounds known in the prior art in the case of Feistel-like networks.

The Feistel-like structure 100 of Fig. 1 comprises a Combine Key RightPart (CKR) function 110, a preferred implementation of which is described below with reference to Figs. 2A and 2B, and a Combine RightPart Combine LeftPart (CRL) function 120, a preferred implementation of which is described below described below with reference to Fig. 5. A preferred implementation of a key expansion function (not depicted in Fig. 1), operative to provide a round key (RKj, RKj+ 1) for each round of the Feistel-like structure 100 is described below with reference to Fig. 8.

In each round of the hardened Feistel-like structure 100, two halves of a plaintext, left and right, depicted as L and R, are operated on by the CKR function 110 and the CRL function 120. It is appreciated that in each round, L and R preferably have an identical size of 64 bits. It is nevertheless appreciated that L and R may be any equal size, and 64 bits is used herein as an example. It is further appreciated that the size of the round key, RK ₁ , is described herein as 100 bits by way of example, only. RKj may be any appropriate size.

It is appreciated that the plurality of rounds may preferably be preceded by preprocessing of L and R. For example, L and R may preferably be permuted according to a pre-defined permutation in the same manner the DES block cipher permutes the input before the first round (refer to FIPS 46-3). It is further appreciated that after the plurality of rounds are completed, an encrypted output of the hardened Feistel-like structure 100 may be post-processed. For example, output may preferably be further permuted according to a pre-defined

permutation in the same manner the DES block cipher permutes the state after the 16 ^th round (refer to FIPS 46-3).

For any given n rounds of the hardened Feistel-like structure 100, a particular round (first round, last round, or any other round) may preferably differ from the other n-1 rounds.

The Feistel-like structure 100 preferably uses a 128-bit key to encrypt and decrypt 128-bit blocks. The number of rounds (RN) is preferably RN between 40 and 50, inclusive.

It is appreciated that the Feistel-like structure 100 is preferably less efficient if implemented in software.

The Feistel-like structure 100 preferably utilizes CKR 110 to integrate a round key with a right half of a state and the function CRL 120 to combine the result of the key integration with a left half of the state. The left and right halves of the state are referred below as L and R, respectively. Reference is now made to Fig. 2 A, which is an illustration of a

Combine Key RightPart (CKR) function 110 comprised in the hardened Feistel- like structure of Fig. 1.

The CKR function 110 preferably comprises the following operations: 1. RExp (Right Part Expansion) 210 preferably expands the right half R from 64 to 100 bits;

2. Using a XOR operation 220, a 100 bit round key, RKj, is preferably combined with the expanded 100 bit right half;

3. MCF (Mix and Condense Function) 230 preferably mixes the 100 bit result of RExp 210 and, preferably in a pseudorandom fashion, preferably condenses the mixed 100 bits to 64 bits.

Reference is now made to Fig. 2B, which is an illustration of an alternative preferred embodiment of the Combine Key RightPart function comprised in the hardened Feistel-like structure of Fig. 1. In the preferred embodiment of the CKR depicted in Fig. 2B, a plurality of layers of S-boxes 310, 330 is added, before the MCF 230. The plurality of layers of S-boxes 310, 330 is operative to receive the output of the 100 bit result of the XOR operation 220. As

is well known in the art, S-boxes substitute bits comprising a set of input bits with a set of output bits, the substitution preferably increasing a level of confusion of an output ciphertext.

In one preferred embodiment of the present invention, depicted in Fig. 2B, the plurality of layers of S-boxes 310, 330 comprises a first layer of S- boxes 310, a diffusion layer 320, and a second layer of S-boxes 330. Each of the first layer of S-boxes 310 and the second layer of S-boxes 330 comprises 25 S- boxes, each S-box operative to receive a 4 bit input, and produce a 4 bit output.

The diffusion layer 320 connects the first layer of S-boxes 310 and the second layer of S-boxes 330, such that a large number of S-boxes in the second layer of S-boxes 330 are affected by substitutions in the first layer of S-boxes 310.

Those skilled in the art will appreciate that, in principle, as many layers of S-boxes as desired may be added. However, each additional layer slows down processing time. In one preferred embodiment of the present invention, the 25 S-boxes are S-boxes from the Serpent Cipher, as discussed below. The Serpent Cipher and the S-boxes thereof are discussed at greater length below, with reference to Fig. 7.

Those skilled in the will appreciate that any appropriate S-boxes may be used in the preferred embodiment depicted in Fig. 2B. The above discussion wherein the S-boxes in the preferred embodiment depicted in Fig. 2B are described as the Serpent Cipher S-boxes is by way of example, and not meant to be limiting.

Reference is now made to Appendix A, which comprises a table describing one implementation of the relationship between bits output from the first layer of S-boxes 310 and input into the second layer of S-boxes 330 in the system of Fig. 2B

Reference is now made to Fig. 3, which is an illustration of a preferred implementation of hardware for a RightPart Expansion Function comprised in the Combine Key RightPart function of Figs. 2A and 2B. It is appreciated that Fig. 3 provides an illustration of a preferred implementation of hardware structures and methods for implementing an expansion function, the illustration being drawn in a format which is well known in the art. RExp 210

(Figs. 2A and 2B) preferably uses a linear transformation to expand the 64 bit R into a 100 bit expanded RightPart, where each of the 100 bit output bits is the result of a XORing of 2 or 3 input bits.

Indices implemented in the proposed hardware of Fig. 3 are preferably selected pseudo-randomly with the following constraints:

1. Each one of the 64 input bits of the R preferably influences at least two output bits;

2. Each bit of the 100 bit round key preferably influences exactly one output bit; 3. Indices are preferably selected so as to be spread equally between the input and output bits, thereby avoiding a situation where a small number of input bits influence only a small number of output bits; and

4. Any small set of input bits preferably influences a larger set of output bits. Those skilled in the art will appreciate that error correcting codes, such as the well known Hamming error correcting code, share similar design criteria with the indices implemented in the proposed hardware and thus, error correcting codes may be well suited for use as the indices implemented in the proposed hardware. It is preferable that the RExp function 210 (Figs. 2A and 2B) and the subsequent XOR 220 operation (with the round key) balance between a proper mixing of the round key with the right part and a time-efficient implementation of the mixing, thereby allowing a hardware implementation of both the RExp function 210 (Figs. 2 A and 2B) and the XOR 220 operation that preferably comprises only two layers of XOR operations (and, in some preferred embodiments, an additional layer of NOT gates).

Returning to the discussion of Fig. 2A, the MCF function 230 is now discussed. The 100 bit expanded right half, after XORing with the 100 bit round key RKj, is preferably input into the MCF function 230. A 100 bit result of the XORing is preferably reduced and condensed into a 64-bit temporary result, which is used later as a control input of the CRL function (described with

reference to Fig. 5). The MCF function 230 is preferably critical in making the Feistel-like structure 100 (Fig. 1) emulation resistant.

Reference is now made to Fig. 4, which is an illustration of a preferred embodiment of the mini- function, the mini-function serving as a building block for the MCF function 230 (Figs. 2A and 2B) comprised in the CKR function 110 of Figs. 2A and 2B.

The MCF function preferably uses between round key generation function and 50, inclusive, layers of mini-functions 400, where each of the mini- functions 400 preferably comprises two micro-functions, a balanced micro- function BF 410 and a non-linear micro-function NLF 420.

A balanced micro-function BF 410 is defined as follows: a set of the input bits for the balanced function are denoted as the balancing set and for every selection of the other input bits, a uniform distribution on the balancing set guarantees uniform distribution on the output (i.e., a uniform distribution of zeros and ones input guarantees a uniform distribution of zeros and ones output). For example and without limiting the generality of the foregoing, a XOR operation is a balanced function for which each of the input bits is a balancing set.

The mini-functions 400 are preferably designed as follows: the input bits are preferably input into a splitter 415, which splits the balancing set of bits from the other input bits;

NLF 420 is preferably executed on the other input bits; and afterwards BF 410 is preferably executed on the output of NLF 420 and on the balancing set of bits, received from the splitter 415.

In some preferred embodiments of the present invention, the balancing set of bits goes through a third type of micro-functions, comprising an invertible transformation, such as a 2bit-to-2bit S-box, where the balancing set comprises 2 bits. Putting the balancing set through the invertible transformation is preferably performed simultaneously with the NLF, and thus, employing the third micro-function can be performed preferably without cost in execution time. For example and without limiting the generality of the foregoing, the following functions process 3-bit inputs (according to the design criteria stated immediately above):

(input 1 v input2) θ input3; NOT ((inputl λ input2) θ input3); The Majority function; and

MUX, where a single bit selects which of the two other input bits to output.

The mini-functions 400 in layer i preferably receive inputs from the outputs of the mini-functions 400 in layer i-1. Selection of which output of layer i-1 goes to which input of layer i is preferably performed in a manner that preferably maximizes the mixing between layers and thus preferably avoids localization effects.

It is preferable that the exact MCF 230 (Figs. 2 A and 2B) utilized is automatically generated during design. However, the MCF utilized preferably passes several statistical tests measuring correlation between output bits (in particular, linear correlations). The statistical tests are preferably not restricted to input and output, but preferably also measure correlations in internal layers between inputs and outputs. In addition, it is preferable that it is not possible to express any small set of output bits of MCF 230 (Figs. 2A and 2B) as a short expression of input bits of MCF 230 (Figs. 2A and 2B).

Reference is now made to Appendix B, which is a description of a method for robust cipher design, comprising a preferred method of key expansion and set up and a preferred implementation of a round key encryption function, the method of Appendix B comprising a preferred implementation of the Feistel-like structure of Fig. 1. In order to harden the Feistel-like structure 100 (Fig. 1) and prevent single points of failure, MCF 230 (Figs. 2A and 2B) preferably is implemented in two versions. The two versions are preferably used in an alternating manner throughout the rounds of the Feistel-like structure 100 (Fig. 1).

It is appreciated that even if one of the two versions is found to be "faulty", the

Feistel-like structure 100 (Fig. 1) as a whole preferably remains strong. A "faulty" function in the present context is either a cryptographically weak function (e.g., having strong linear or differential properties) or a function that is easy to emulate in software.

Reference is now made to Fig. 5, which is an illustration of a

Combine RightPart Combine LeftPart (CRL) function 120 comprised in the hardened Feistel-like structure 100 of Fig. 1. The CRL 120 function combines the

64-bit result of the MCF 230 as the last stage of the CKR 110 with the unchanged 64-bit left half Lj to get a new 64-bit pseudo-random right half, Rj+ \.

The CRL function 120 preferably complies with the following design criteria:

1. CRL 120 is preferably invertible in a second parameter when fixing a first parameter. That is, there shall be ICRL, such that, for every X, Y, ICRL(X, CRL(X, Y))=Y, where the CKR 110 result is used as the first parameter X (also denoted hereinafter as the "control input") and the left half, L ₁ , is used as the second parameter Y (also denoted hereinafter as the "transform input").

2. CRL 120 is preferably not an involution. That is, ICRL preferably differs significantly from CRL 120 (as opposed, for example, to the XOR function that is used in DES).

The CRL function 120 preferably comprises two stages, each stage working on small sub-blocks. In preferred embodiment of the present invention, each sub-block comprises 4 bits. After each of the stages, a permutation is preferably applied to the result, breaking any locality effect of working on small sub-blocks.

The first stage comprises a linear layer LL 510 that mixes the control input with the transform input.

After LL 510, a bit-permutation PL 520 is preferably applied to the result of the LL 510. Afterwards, the output of PL 520 is preferably input into an S-boxes layer SL 530, comprised of sixteen 4-bit to 4-bit S-boxes.

Finally, a bit-permutation (not depicted) is preferably applied to the output of SL 530.

Reference is now made to Fig. 6, which an illustration of one preferred implementation of the linear layer 510 in the Combine RightPart

Combine LeftPart (CRL) function 120 of Fig. 5. LL 510 comprises a first splitter

610 which splits transform input, Lj, into 4-bit micro-blocks. Similarly, a second

splitter splits control input into 4-bit micro-blocks. The 4-bit micro-blocks resulting from the control input are preferably used to determine a linear transformation (LT). The determined transformation is preferably applied to the input 4-bit micro-blocks, thereby producing a 4-bit output micro-block. Linear transform operations of the control data 4-bit micro-blocks and the transform data 4-bit micro-blocks are depicted in Fig.6 as "LT".

For the control bits C[O..3] and the input bits I[0..3] the linear transformation preferably O = (A(C) x I) θ C where A(C) is a linear transformation depending on control input C: A(C) = A ₂₁ ⁽ C ⁾ A ₂₂ ⁽ C ⁾ A ₂₃ ⁽ C ⁾ A ₂₄ ⁽ C ⁾

A ₃₁ ⁽ C ⁾ A ₃₂ ⁽ C ⁾ A ₃₃ ⁽ C ⁾ A ₃₄ ⁽ C ⁾

AJC ⁾ A ₄₂ ⁽ C ⁾ A ₄₃ ⁽ C ⁾ A ₄₄ ⁽ C ⁾ for A _y S which are 4bit-to-lbit functions which are applied to the control input, and

O is the resulting output.

A(C) is invertible; that is there exists B(C), such that:

Bn ⁽ C ⁾ B ₁₂ ⁽ C ⁾ Bn ⁽ C ⁾ Bu ⁽ C ⁾

B(C) = B ₂₁ ⁽ C ⁾ B ₂₂ ⁽ C ⁾ B ₂₃ ⁽ C ⁾ B ₂₄ ⁽ C ⁾

B ₃₁ ⁽ C ⁾ B ₃₂ ⁽ C ⁾ B ₃₃ ⁽ C ⁾ B ₃₄ ⁽ C ⁾

B ₄₁ ⁽ C ⁾ B ₄₂ ⁽ C ⁾ B ₄₃ ⁽ C ⁾ B ₄₄ ⁽ C ⁾

1 0 0 0 0 1 0 0 such that for every control input C: A(C) x B(C) = that is A(C) is the 0 0 1 0 0 0 0 1 inverse of B(C).

In preferred embodiments of the present invention A(C) comprises:

^' A _n (C) A _n (C) Ai ₃ (Q Au(C) A ₂₁ (Q A ₂₂ (C) A ₂₃ (C) A ₂₄ (C) A ₃ i(C) A ₃₂ (C) A ₃₃ (C) A ₃₄ (C) A ₄ i(C) A ₄₂ (C) A ₄₃ (C) A ₄₄ (C)

"C[O] θ C[3] C[O] C[2]C[3] C[3]

C[3] C[I] C[I] 0

C[0]C[2] C[I] C[2] C[2]

C[O] 0 C[2] 1

(equation 1)

It is appreciated that if the transformation A(C) is used during decryption, then during encryption the inverse transformation of A(C) is used. In particular, if A(C) is as described in equation 1, then, since both matrices comprising control bits used in equation 1 are involutions, the inverse transformation B(C) is the composition of the transformations in reversed order. The results of all linear transformations are preferably input into join function 630. Join function 630 preferably joins the results of all 16 linear transformations into one 64 bit value.

The 64 bit output of join function 630 is preferably input into bit- permutation PL 520, thereby producing a 64 bit permuted output. Bit- permutations are well known cryptographic structures.

Reference is now made to Fig. 7, which is an illustration of one preferred implementation of an S-boxes layer in the Combine RightPart Combine LeftPart (CRL) function 120 of Fig. 5. The layer of S-boxes SL 530 (Fig. 5) preferably comprises 4-bit to 4-bit S-boxes, which are preferably simple to implement in hardware and still comprise a significant contribution to non- linearity of the hardened Feistel-like structure 100 (Fig. 1). The 64-bit input is input into an S-box splitter 710. The S-box splitter 710 preferably divides the 64- bit input into 16 4-bit micro-blocks. The 16 4-bit micro-blocks go through sixteen

S-boxes 720. Output from the sixteen S-boxes 720 is all mixed in a bit permutation join function 730.

The specification of the Serpent cipher (refer to www.ftp.cl. cam.ac.uk/ftp/users/rjal4/serpent.pdf) describes eight 4bit-to-4bit S- boxes, which were optimized against linear and differential attacks. It is the opinion of the inventors of the present invention that the S-boxes described in the specification of the Serpent cipher should preferably be used in the hardened

Feistel structure 100 (Fig. 1) described herein. Reference is now made to

Appendix C which is a copy of Appendix A.5 of the Serpent Cipher specification, describing S-boxes SQ through S7 of the Serpent Cipher.

Reference is now made to Fig. 8, which is an illustration of one preferred implementation of a key expansion function 800 comprised in the hardened Feistel-like structure 100 of Fig. 1. The key setup function 800 preferably extends a 128-bit key to RN 100-bit round keys (RN is the number of rounds). The key expansion function is preferably designed according to the following principles:

1. Preferably reuse available hardware functions.

2. Preferably enhance robustness of the hardened Feistel-like structure 100 (Fig. 1), as discussed above, with reference to the discussion of Appendix B.

3. Preferably allow both forward and backward generation of the round keys.

As discussed above, with reference to the discussion of Appendix B, the key expansion function 800 takes advantage of the fact that the MCF preferably comprises two variations; one variation is preferably active during any round in the MCF function for the CKR 110 (Figs. 2A and 2B), while the other variation is preferably available for use. The key expansion function 800 therefore preferably uses the available MCF function in order to generate the round keys in a cryptographically secure manner. Imitating a typical design for stream ciphers, the key setup function

800 preferably employs two functions; a first function, state update 810, is preferably operative to update a state. The second function, round key generation

830, preferably derives a new round key 840 from the new state. The state update 810 and round key generation 830 functions are executed in an alternating order generating round keys 840 which are preferably cryptographically decoupled from the key itself, as well as from each other. The state of the key setup is preferably a 128-bit shift register. The

128-bit shift register is initialized 850 with the 128-bit key. The state update function 810 preferably comprises a circular rotation of the 128-bit register. It is appreciated that the number of rounds (RN) is preferably smaller than the size of the 128-bit register, and thus the state update function preferably does not loop during a round.

During decryption, in order to get the round keys in the proper order (reverse order from the order used during encryption), a decrypter preferably receives the state in reverse order used during encryption. In some preferred embodiments of the present invention, decryption preferably begins with shifting the shift register as many times as needed in order to get the state appropriate for the last round key. Each subsequent round then preferably shifts the state in the opposite direction to the direction used to circularly shift the state during encryption.

It is appreciated that replacement of a short LFSR (left shift register) with 2-3 smaller LFSRs may be preferable. If 2-3 smaller LFSRs are utilized, the decryption key is the result of applying a linear transformation (calculated in advance and hard-wired) on the encryption key, and then the LFSRs are preferably rolled back to get the round keys in the reverse order.

In order to avoid weak keys and slide attacks, an additional XOR with a predefined round string may preferably be applied after the state update function 810.

Reference is now made to Fig. 9, which is an illustration of one preferred implementation of round key generation 830 utilizing the Mix and Condense function (MCF) 230 (Figs. 2A and 2B) in the key expansion function 800 of Fig. 8. The round key generation 830 function inputs the 128-bit state into the MCF 230 (Figs. 2A and 2B) and takes the 100-bit output as the next round key, as discussed above with reference to Appendix B.

The following are design principles for selecting the order of using the MCF variations in the key setup and the round operation:

1. Preferably allow a smooth pipeline between the round operation and the key setup. Specifically, have both functions active together where one generates the key for the next round and the other is used for the round operation itself.

2. Preferably use as many different combinations as possible, maximizing the distribution of the "responsibility" for both security and emulation resistance. As discussed in greater detail in Appendix B, for two MCF functions A and B, the round operation preferably uses A and B in the following order: A A B B A A B B A A B B A A B B ...

The key setup operation uses the function that is left available, i.e., B on rounds 1, 2 (preparing the keys for round 2, 3), A on round 3, 4 (preparing the key for round 4, 5) etc.

Thus the rounds of the hardened Feistel-like structure 100 (Fig. 1) have the following combinations as round key derivation and round operation: Round 4t+l: AA; Round 4t+2: BA; Round 4t+3: BB; and

Round 4t+4: AB. Alternative preferred implementations are discussed at length in Appendix B.

The implementation of MCF 230 (Figs. 2A and 2B) that is preferably used in the round operation and the MCF that is used in the key expansion have different sizes of inputs and outputs. Specifically, a 128 bit value is preferably input in order to produce a 100 bit output for key setup, and a 100 bit value is preferably input in order to produce a 64 bit output for a round operation.

In order to use the same hardware for both operations, the implemented MCFs are preferably implantations of 100 bits going to 128 bits going to 100 bits going to 64 bits, where most of the layers are in the 128 bits going to 100 bits part. Thus, the round operation uses the whole function and the key expansion uses only the middle part of the function. The blowing effect herein

described also contributes to preferably making the function hard to emulate in software.

Reference is now made to Figs. 10 - 13, which are simplified flowchart illustrations of preferred alternative methods of operation of the hardened Feistel-like structure of Fig. 1, in accordance with preferred embodiments thereof. The methods of Figs. 10 - 13 are believed to be self explanatory with reference to the above discussion.

Reference is now made to Appendix D, which comprises a description of certain alternative preferred embodiments of the present invention. It is appreciated that software components of the present invention may, if desired, be implemented in ROM (read only memory) form. The software components may, generally, be implemented in hardware, if desired, using conventional techniques.

It is appreciated that various features of the invention which are, for clarity, described in the contexts of separate embodiments may also be provided in combination in a single embodiment. Conversely, various features of the invention which are, for brevity, described in the context of a single embodiment may also be provided separately or in any suitable subcombination.

It will be appreciated by persons skilled in the art that the present invention is not limited by what has been particularly shown and described hereinabove. Rather the scope of the invention is defined only by the claims which follow: