WO2004070510A2

WO2004070510A2 - Device and method of manipulating masked data

Info

Publication number: WO2004070510A2
Application number: PCT/IL2004/000116
Authority: WO
Inventors: Shay Gueron; Ori Parzanchevski; Or Zuk
Original assignee: DISCRETIX TECHNOLOGIES Ltd
Current assignee: DISCRETIX TECHNOLOGIES Ltd
Priority date: 2003-02-06
Filing date: 2004-02-05
Publication date: 2004-08-19
Anticipated expiration: 2005-08-06
Also published as: JP2006517036A; WO2004070510A3; EP1595357A2; EP1595357A4

Abstract

Embodiments of the invention provide a method and a device for manipulating data (108) by converting masked data in a first representation of a finite field into converted data in a second representation of the finite field (102), and manipulating the converted data (106) to obtain manipulated masked data.

Description

DEVICE AND METHOD OF MANIPULATING MASKED DATA

FIELD OF THE INVENTION

[001] The present invention relates generally to computations in finite fields and, more particularly, to masked data manipulation in finite fields.

BACKGROUND

[002] Data manipulation algorithms may include performing an inverse operation on data elements of finite fields. For example, an Advanced Encryption Standard (AES) provides a Rijndael Block Cipher Algorithm ("the Rijndael algorithm"), which includes a ByteSub bit level operation on input data including a vector, e.g., byte, x. The ByteSub operation includes an encryption mode and a decryption mode. The encryption mode includes an inverse operation and an affine transformation, e.g., x is converted into Ax^" +b, wherein A and b are predetermined parameters. The •decryption mode includes an affine transformation followed by an inverse operation, e.g., x is transformed into (A¹ (x+b))^"1. According to the AES, the inverse operation is preformed over a Galois Field, GF(2⁸). The field is represented by a polynomial form, using a reduction polynomial, p(t) =t⁸+t⁴+t³+t+l .

[003] There are other known block cipher algorithms, which implement an inversion operation in the GF(2⁸). These algorithms include, for example, a Camelia cipher algorithm described by K. Aoki et al. in "Specification of Camellia - a 128-bit Block Cipher", http://info.isl.ntt.co.jp/camellia/, and a Zodiac cipher algorithm described by C. H. Lee in "Zodiac: Block Cipher Proposal", http://www.safedigm.com/productpds/download/Safedigm_Zodiac.pdf.

[004] A Differential Power Analysis (DP A) attack may use a correlation between an input and an output of the data manipulation algorithm to reveal a secret key implemented by the algorithm. In order to protect the manipulation algorithm, e.g., the AES algorithm, from a DPA attack, a random input mask, denoted R, may be added, e.g., over GF(2), to the input vector (e.g., byte), x, before performing the algorithm, to obtain masked data. The random mask may include a random vector having a bit-length equal to the length of x. Thus, the algorithm is performed on the sum x+R rather than on x, such that an attacker may not know the actual input to the -Jgorithm.

[005] It may be required to remove the mask, e.g., after performing the algorithm on the masked data, in order to be able to use the unmasked output of the algorithm.

[006] A method described by Trichina, E. et al in "Simplified Adaptive Multiplicative Masking for AES and its Securized Implementation ", CHES 2002, includes the steps of multiplying the masked input vector, x+R, by R to obtain xR+R², adding R² to the result to obtain XR, inverting XR to obtain ⁷R^";, adding 1 to ^;R^'7 to obtain X^;R^";+1, and multiplying the result by R to obtain AR.

[007] Performing a masked inversion of AES data using the method described by Trichina, E. et al may require two multiplications, one squaring, and two additions over the GF(2 ). A hardware implementation of such an inversion may be relatively complex and/or power consuming. For example, the hardware implementation may require using a square Look Up Table (LUT) having a size of 256 bytes, and two multiplication circuits for multiplication in the GF(2⁸).

SUMMARY OF EMBODIMENTS OF THE INVENTION

[008] Embodiments of the invention provide a method and a device for efficiently manipulating masked data provided in a first representation of a finite field, e.g., for implementing an inversion of masked input data provided in the first representation, by converting the masked input data into a second representation and performing in the second representation operations equivalent to operations of the first representation to obtain masked manipulated data.

[009] The method of manipulating masked data, according to embodiments of the invention, may include converting the masked input data in the first representation into converted data in the second representation of the finite field, and manipulating the converted data to obtain masked manipulated data.

[0010] According to some embodiments, the method may also include converting an input mask of the masked input data into an updated mask in the second representation. Manipulating the converted data may include manipulating the converted data using the updated mask.

[0011] According to embodiments of the invention, converting the input data may result in the converted data being masked by the updated mask. Manipulating the converted data may result in the manipulated data being masked by the updated mask.

[0012] According to some embodiments of the invention, manipulating the converted data may include performing at least one operation equivalent to at least one desired operation in the first representation.

[0013] According to some exemplary embodiments, manipulating the converted data may include multiplying the converted data by the updated mask to obtain first intermediate data, adding to the first intermediate data a square of the updated mask to obtain second intermediate data, inverting the second intermediate data to obtain third intermediate data, adding a unit data bit to the third intermediate data to obtain fourth intermediate data, and multiplying the fourth intermediate data by the updated mask to obtain masked inverted data in the second representation.

[0014] According to some embodiments of the invention, the method may include de-converting the manipulated data to obtain de-converted data in the first representation. De-converting the manipulated data may result in the de-converted data being masked by a linear transformation of the input mask. [0015] According to some embodiments of the invention, the finite field may include a Galois Field (GF).

[0016] According to some exemplary embodiments, the first representation may include a GF(2^2s) and the second representation may include a GF((2^S)²). According to some of these embodiments, s may equal four, i.e., the first representation may include a GF(2⁸) and the second representation may include a GF((2⁴)²).

[0017] Accordmg to some embodiments of the invention, a device for manipulating masked input data may include a conversion block to convert the masked input data in the first representation into converted data in the second representation. The conversion block may also convert an input mask of the masked input data into an updated mask. The device may also include a manipulation block to manipulate the converted data in the second representation, and a de-conversion block to convert the manipulated data into de-converted data in the first representation. The manipulation block may include an inversion block to invert the converted data in the second representation. The de-converted data may be masked by an affine transformation of the input mask.

[0018] According to exemplary embodiments of the invention, the conversion block may include an input conversion module to convert the masked input data in the first representation into corresponding converted data in the second representation. The conversion block may also include a mask conversion module to convert the input mask into the updated mask. According to some embodiments, the conversion of the input mask performed by the mask conversion module may be related to the conversion performed by the input conversion module.

[0019] According to exemplary embodiments, the inversion block may include a first multiplier to multiply an output of the input conversion module with an output of the mask conversion module, and a squaring module to provide a square of the output of the mask conversion module. The inversion block may also include a first adder to add an output of the squaring module to an output of the first multiplier, a zero detector to provide an output of a zero value if an output of the first adder is non-zero, and an AND gate to provide an output corresponding to a logical AND of an output of the zero detector and an output of the mask conversion module. The inversion block may further include a second adder to add an output of the AND gate to an output of the first adder, an inversion module to invert an output of the second adder, a third adder to add a unit value to an output of the inversion module, a second multiplier to multiply the output of the mask conversion module with an output of the second adder, and a fourth adder to add an output of the second multiplier to an output of the AND gate.

[0020] According to exemplary embodiments of the invention, the de-conversion block may include an output de-conversion module to de-convert the manipulated data in the second representation into corresponding de-converted data in the first representation. The de-conversion block may also include a mask de-conversion module to de-convert the updated mask. According to some embodiments, the de-conversion of the updated mask performed by the mask de-conversion module may be related to the conversion performed by the output de-conversion module.

BRIEF DESCRIPTION OF THE DRAWINGS

[0021 ] The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanied drawings in which:

[0022] Fig. 1 is a flow chart illustration of a method of manipulating masked data, in accordance with embodiments of the invention;

[0023] FIG. 2 is a schematic illustration of a circuit implementation of a device for manipulating masked data, in accordance with some exemplary embodiments of the invention;

[0024] Fig. 3A is a schematic illustration of a circuit implementation of a multiplier, in accordance with some exemplary embodiments of the invention;

[0025] Fig. 3B is a schematic illustration of a circuit implementation of a squaring module, in accordance with some exemplary embodiments of the invention; [0026] Fig. 3C is a schematic illustration of a circuit implementation of an inversion module, in accordance with some exemplary embodiments of the invention;

[0027] FIG. 4 is a schematic illustration of a circuit implementation of an AES compatible device for encrypting/decrypting masked data, in accordance with some exemplary embodiments of the present invention;

[0028] Fig. 5A is a schematic illustration of a circuit implementation of a data conversion module, in accordance with some exemplary embodiments of the invention;

[0029] Fig. 5B is a schematic illustration of a circuit implementation of a mask conversion module, in accordance with some exemplary embodiments of the invention;

[0030] Fig. 6A is a schematic illustration of a circuit implementation of an output de-conversion module, in accordance with some exemplary embodiments of the invention; and

[0031] Fig. 6B is a schematic illustration of a circuit implementation of a mask de-conversion module, in accordance with some exemplary embodiments of the invention.

[0032] It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures 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 element. Further, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements. It will be appreciated that these figures present examples of embodiments of the present invention and are not intended to limit the scope of the invention. DETAILED DESCRIPTION OF EMBODIMENTS OF THE iNVENTlON

[0033] In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the invention. However, it will be understood by those of ordinary skill in the art that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, and components have not been described in detail so as not to obscure the present invention.

[0034] In the following detailed description, the notation GF(2^2s) refers to a representation of a Galois Field (GF) of order 2^2s as an extension field of GF(2) consisting a plurality of polynomials over GF(2) modulo p(t), wherein p(t) is an irreducible polynomial of the degree 2s over GF(2). A polynomial may be represented in the GF(2^2s) representation, by a string of 2s bits. An element, u, in the GF(2^2s) representation may be defined by a 2s-digit binary number U=[U_2S-_Ϊ^_2S-2— UIUQ]_. wherein u, is the coefficient of t in a corresponding polynomial, e.g.

U2s-lt^2S'1 + 2s-2t^2S'2 + ■■■ +Ujt+Uo.

[0035] The notation GF((2^S)²) refers to a representation of a GF of order 2^2s as an extension field of GF(2³) consisting of a plurality of polynomials over GF(2^S) modulo r(t), wherein r(t) is an irreducible polynomial of a second degree over GF(2^S); i.e., r(t)=Aat+β, wherein α and β are elements of GF(2^S). The GF(2^S) is represented as an extension field of GF(2) consisting of a plurality of polynomials over GF(2) modulo q(t), wherein q(t) is an irreducible polynomial of a second degree over GF(2). An element, z, in the GF((2^S)²) representation may be defined by a 2s-digit binary number

representing a linear polynomial z_<m>t+z<ι>, wherein

and

are elements of GF(2^S) represented by polynomials modulo q(t).

[0036] Some exemplary embodiments of the invention described herein, may refer to data in a binary field representation, e.g., a GF(2 ^s) representation, of a finite field, e.g., a GF. However, it will be appreciated by those skilled in the art, that embodiments of the invention may be implemented for data in any other representations, e.g., a GF(g^h) representation, wherein g and h may have any desired value. [0037] Masking input data including a vector, x, of a predetermined finite field, may include adding to x an input random mask, denoted R, wherein R is an element randomly chosen from the predetermined finite field, i.e., to obtain masked input data, e.g., x+R.

[0038] Reference is made to Fig. 1, which schematically illustrates a flow chart of a method of manipulating masked data, in accordance with some embodiments of the invention.

[0039] As indicated at block 102, the method may include converting masked input data, e.g., including a combination of input data and an input random mask, in a first representation of a predetermined finite field, e.g., a GF, into masked converted data in a second representation of the predetermined finite field, e.g., by applying to the masked input data in the first representation a conversion operator, as described in detail below.

[0040] As indicated at block 104, the method may include converting the input random mask in the first representation into an updated mask in the second representation, as described in detail below.

[0041] As indicated at block 106, the method may also include manipulating the converted data, e.g., using the updated mask, to obtain masked manipulated data in the second representation, as described in detail below.

[0042] As indicated at block 108, the method may further include de-converting the manipulated data back into the first representation by applying a de-conversion operator to obtain masked de-converted data in the first representation, as described in detail below.

[0043] As indicated at block 109, the method may also include unmasking the masked de-converted data, e.g., as described below.

[0044] As indicated at block 101, the method may also include generating the input random mask, e.g., as described below.

[0045] As indicated at block 103, the method may also include masking input data, e.g., using the input mask to obtain the masked input data, for example, by adding the input mask may be added to the input data, as is known in the art. [0046] According to some embodiments of the invention the conversion operator may include any suitable operator for converting data in the first representation into corresponding data in the second representation. According to some exemplary embodiments, the conversion operator may include a representation-transformation matrix corresponding to the desired transformation, e.g., as described in International Application PCT/IL03/00647, entitled "Method and device of manipulating data in Finite Fields", filed August 6, 2003 and assigned to the assignee of the present application, the disclosure of which is incorporated herein by reference. According to some exemplary embodiments of the invention, the conversion operator may include a combination of the representation-transformation matrix and an affine transformation, e.g., a decryption or an encryption affine transformation, as described below.

[0047] Since, as is known in the art, any two finite fields of the same size may be isomorphic, an isomorphism may exist between two representations of a predetermined finite field, e.g., a GF(2"), denoted Rej-»; and Rep₂, respectively. Each of the two representations may be a linear space of dimension n over GF(2) , and each isomorphism may be a linear transformation between the representations. Thus, as part of some embodiments of the present invention, an nxn binary representation-transformation matrix, M, may be computed for transforming, e.g. by matrix multiplication, elements in Repi into corresponding elements in Rep₂. Since the transformation between the two field representations is invertible, an inverse representation-transformation matrix, M¹ , may exist for each representation-transformation. An irreducible polynomial, po, having n roots may represent Repi. Each root of po is a generator of the GF(2ⁿ) and invariant under field isomorphism. Thus, there are n corresponding representation-transformation matrices for each field extension. A pair of corresponding generators of representations Repi and Rep₂, respectively, may uniquely determine an isomorphism between Repi and Rep₂, since a multiplicative group of the GF(2") is cyclic. Thus, for a generator vector, rj, of Rep_/, and a generator vector, r₂, of Rep_∑, the corresponding representation-transformation matrix, M, must satisfy iWr;=r₂. Since the two field representations are isomorphic, and since r; and r^ are generators of the GF(2ⁿ), the following equation system must be satisfied by M for any k (k=l ...2ⁿ):

M(r ^k=(r₂)^k (1) wherein (n)^k denotes field generator r,- raised to the k-th power in representation Rep,-, to produce an element (rjf in representation Rep*; and wherein field element (rj)^k in representation Repi may be treated as a vector in a linear space of dimension n over GF(2), and may be multiplied by representation-transformation matrix, M to provide

M(n)^k.

[0048] Equation System 1 includes 2ⁿ linear equations, which may be solved to determine the representation-transformation matrix, M, corresponding to the pair of generators π and r₂. Equation System 1 may include redundant equations, which may be ignored in order to reduce the number of computations. For example, only the first n equations may be used to provide one representation-transformation matrix. Another representation-transformation matrix may be provided by a solution of Equation System 1 using a different pair of generators rj and r₂. Thus, there may be n different equation systems corresponding to the n different generators in Rep₂, each defining an "image" of , thereby providing n different representation-transformation matrices from Repi to Rej_>₂.

[0049] In exemplary embodiments of the invention, each root of the irreducible polynomial over GF(2^S) , e.g., p(t)=t⁸+t⁴+t³+t+l; may be a generator of the GF(2^S) field. Thus, eight possible representation-transformation matrices ^• corresponding to the eight roots of the irreducible polynomial, respectively, may be computed for each field extension of GF(2^S) . Polynomial representations of GF(2⁴) over GF(2) may be defined by each of three irreducible reduction polynomials over GF(2⁴ ) , e.g., 1 + t + t⁴, 1 + t³ + t⁴ , 1 + t + 1² + t³ + t⁴ . Field extensions of one or more of the polynomial representations of GF(2⁴) in GF(2^S) may be computed using irreducible extension polynomials, e.g., polynomials of the type t² +αt + β , wherein β and α may be elements of GF(2⁴), such that t² +αt + β \^'s irreducible over GF(2⁴).

Accordmg to exemplary embodiments of the invention, there may be fifteen different β values and 8 different α values providing 120 possible irreducible extension polynomials of the form t² +αt + β . The three different reduction polynomials and the 120 irreducible extension polynomials result in 360 different GF((2⁴)²) representations of GF(2⁸) as an extension of GF(2). Therefore, according to these exemplary embodiments, there may be 2880 possible representation-transformation matrices, corresponding to the 360 field extensions. According to some embodiments of the present invention, each of the possible representation-transformation matrices may enable transformation from the standard AES representation into a different GF((2⁴)²) representation of GF(2^S) corresponding to a different extension of GF(2⁴) . Thus, the representation-transformation matrix, M, may be pre-selected according to any desired criteria, e.g., complexity of a hardware implementation corresponding to the selected M.

[0050] Input data including vector x in a first representation may be converted into a second representation by applying the representation-transformation, e.g., representation-transformation matrix M. An operation x > x^"1, denoted T(x), in the second representation may be performed on the converted data, e.g., M ^■ x. A de-conversion of the manipulated data back to the first representation, F(x), may be obtained by applying an inverse of the representation-transformation, e.g., M¹. Thus, according to exemplary embodiments of the invention, F(x) and T(M ^• x) may be provided by the following nonlinear equation:

F(x) = M^l- T(M- x) (2)

[0051] According to exemplary embodiments of the invention, masked input data, x+R, in the first representation may be converted into converted data, Mx+MR, in the second representation. The representation-transformation matrix, M, is a regular matrix because the conversion between the first representation and the second representation is an invertible transformation, as described above. Thus, MR may have, in correspondence to R, any non-zero value of the finite field. And thus, the converted data, Mx+MR may include masked converted data wherein the mask includes an updated mask, e.g., MR.

[0052] According to exemplary embodiments of the invention, the input mask,

R, may have a non-zero value. Any suitable non-zero random mask generator, e.g., as described below, may be implemented in order to obtain the non-zero random mask.

[0053] According to some exemplary embodiments of the invention, manipulating the converted data may include inverting the converted data, e.g., as described below. Inverting the converted data may include using the updated mask, e.g., as described below. [0054] According to exemplary embodiments of the invention inverting the masked converted data may include multiplying the converted data, e.g., Mx+MR, by the updated mask, MR, to obtain first intermediate data, e.g., MxMR+(MR)². Inverting the masked converted data may also include adding a square, e.g., (MR)², of the updated mask to the first intermediate data to obtain second intermediate data, e.g., MxMR. Inverting the converted data may further include inverting the second intermediate data, MxMR, to obtain third intermediate data, e.g., (MxMR)^"1. Inverting the converted data may further include adding a unit data bit, i.e., 1, to the third intermediate data to obtain fourth intermediate data, e.g., (MxMRj^+l. Inverting the converted data may further include multiplying the fourth intermediate data by the updated mask MR to obtain masked inverted data in the second representation, e.g., (MX)AMR. At least some of the operations, e.g., addition, multiplication and/or inversion, may be performed in the second representation. The operations in the second representation may be implemented by any suitable circuitry and/or Look Up Tables (LUTs), e.g., as described below.

[0055] According to some embodiments of the invention the de-conversion operator may include any suitable operator for de-converting data in the second representation back into corresponding data in the first representation. According to exemplary embodiments of the invention, the de-conversion operator may include multiplication by the matrix M , as described above. It will be noted that the result of applying the de-conversion operator may be calculated in accordance with Equation 2, e.g., M^"1[(Mx)^"1J=^:x^"1. Thus, masked inverted data in the first representation, e.g., x^";+ R, may be obtained by applying the de-conversion operator to the masked inverted data in the second representation, e.g., (Mx)A MR. According to some exemplary embodiments of the invention, the de-conversion operator may include a combination of the matrix M¹ and an affine transformation, e.g., a decrypt or an encrypt affine transformation, e.g., as described below.

[0056] Reference is made to Fig. 2, which schematically illustrates a circuit implementation of a device 200 for manipulating masked data, in accordance with some exemplary embodiments of the invention.

[0057] According to exemplary embodiments of the invention, device 200 may include a conversion block 202 to convert masked input data in a first representation into corresponding masked data in a second representation. Block 202 may also be adapted to convert the mask R into an updated mask in the second representation. Device 200 may also include a manipulation block, e.g., inversion block 204, to manipulate, e.g., invert, the converted data in the second representation, and a de-conversion block 206 to de-convert the manipulated data into de-converted data in the first representation.

[0058] According to exemplary embodiments of the invention, block 202 may include an input conversion module 208 to convert the masked input data, x+R, in the first representation into corresponding converted data in the second representation. Block 202 may also include a mask conversion module 210 to convert input mask R into the updated mask. In order to obtain an updated mask related to the converted masked data, the conversion of the mask performed by module 210 may be related to the conversion performed by module 208, e.g., as described below. Module 208 and/or module 210 may include any circuitry, Look-Up Tables (LUTs) and/or any suitable hardware and/or software to convert data in a first representation into corresponding data in a second representation, e.g., as described below. It will be appreciated by those skilled in the art that, according to some other embodiments of the invention, modules 208 and 210 may be implemented in one combined-conversion module, e.g., to convert the masked input data and the input mask sequentially.

[0059] Accordmg to exemplary embodiments of the invention, block 204 may include a first multiplier 212 associated with an output 226 of module 210 and with an output 228 of module 208. Block 204 may also include a squaring module 214 associated with output 226, and a first adder 216 associated with an output 230 of module 214 and with an output 232 of multiplier 212. Block 204 may further include an inversion module 218 associated with an output 234 of adder 216, and a second adder 220 associated with an output 236 of module 218 and having an input 240 to receive a signal having the unit value, i.e., the value 1. Block 204 may further include a second multiplier 222 associated with output 228 and with an output 242 of adder 220. Multiplier 212 and/or multiplier 222 may include any circuitry, Look-Up Tables (LUTs) and/or any suitable hardware and/or software to multiply two elements of the first representation using the second representation, e.g., as described below. Unit 214 may include any circuitry, Look-Up Tables (LUTs) and/or any suitable hardware and/or software to provide a square of an element of the first representation using the second representation, e.g., as described below. Inversion module 218 may include any circuitry, Look-Up Tables (LUTs) and/or any suitable hardware and/or software to invert data of the first representation using the second representation, e.g., as described below. Adders 216 and 220 may include any software and/or hardware to implement an addition of two elements. For example, adder 216 and/or adder 220 may include a XOR gate, as is known in the art.

[0060] According to exemplary embodiments of the invention, block 206 may include a de-conversion module 224 associated with an output 243 of block 204. Module 224 may include any circuitry, Look-Up Tables (LUTs) and/or any suitable hardware and/or software to de-convert data in the second representation into corresponding de-converted data in the first representation, e.g., as described below.

[0061] According to an exemplary embodiment of the invention, modules

208, 210 and/or 224 may include a multiplier, e.g., as described below, to^" implement a multiplication by M, M and M^"1, respectively. Thus, output 228 may have a value corresponding to Mx+MR, and output 226 may have a value corresponding to MR. Accordingly, output 243 may have a value corresponding to (Mx)^"]+MR, and an output 244 of block 206 may have a value corresponding to x^"7+R. According to this embodiment, the outputs of blocks 202 and 204 may be masked by the updated mask MR, and the output of block 206 may be masked by input mask R. Thus, it will be appreciated that the outputs of blocks 202, 204, 206 may be masked by either the input mask or the updated mask.

[0062] According to exemplary embodiments, device 200 may include at least two XOR gates 216 and 220, two multiplication circuits 212 and 222 in the second representation, one squaring circuit or LUT 214 in the second representation, and three multiplication circuits 208, 210 and 224 for multiplying an nxn bit matrix, e.g., M, by a vector, e.g., as described below.

[0063] It will be appreciated by those skilled in the art, that a hardware implementation of a device for manipulating masked data according to embodiments of the invention, e.g., device 200, may be less complex, and thus more compact, in comparison with conventional masked-inversion devices. For example, if the first representation includes a GF(2^2s) representation and the second representation includes a GF((2^S)²) representation, a squaring LUT in the second representation may include 2^s s bits. The bit size of the squaring LUT, according to embodiments of the invention, may be much smaller compared to the bit-size, e.g., 2^2s+1s, of a squaring LUT in the first representation. Furthermore, conventional masked-inversion devices may require implementing multiplication circuits to perform multiplications in the first representation. These circuits may be more complex in comparison with the multipliers implemented by embodiments of the invention.

[0064] According to some exemplary embodiments, the method and/or device described above may be implemented for encryption and/or decryption of masked input data, x+R, for example, by performing masked AES S-box encryption decryption operations, as described below.

[0065] Although the scope of the present invention is not limited in this respect, for clarity, as part of the description of some embodiments of the present invention, reference may be made to a device and/or a method of encrypting data. Further embodiments of the present invention may be described with reference to a device and/or a method of decrypting data. However, it would be apparent to those with ordinary skill in the art how to modify and/or adapt the methods and/or devices of the present invention, as described herein, in order to implement encryption devices, decryption devices and/or devices combining both encryption and decryption. Unless specifically stated otherwise, the principles of the methods and devices described herein are intended for implementation in conjunction with any such modifications and/or adaptations.

[0066] In some exemplary embodiments of the invention, 5 equals four. These embodiments are useful for converting data in a GF(2 ) representation into a GF((2⁴)²) representation.

[0067] Although the scope of the present invention is not limited in this respect, for clarity, the description of some exemplary embodiments of the present invention relates to methods and/or devices wherein s equals four, i.e., for converting data in a GF(2⁸) representation into a GF((2⁴)²) representation. However, it would be apparent to those with ordinary skills in the art how to accordingly modify the methods and/or devices described herein for any other suitable value of s.

[0068] As part of some embodiments of the present invention, the method and/or device may be implemented in a variety of combinations and adaptations. According to an exemplary embodiment of the present invention, an encryption block to perform encryption, and/or a decryption block to perform decryption, may be implemented in embedded electrical circuitry, e.g., of the type that may be used in a smartcard. The conversion operator that may be used for converting the data to and from the AES GF(2^S) representation to and from the GF((2⁴)²) representation may be pre-programmed, e.g., into a smart card. Other configurations may be used additionally or alternatively.

[0069] A conventional AES S-box may perform affine transformations according to the following equations: sbσx[x] =^> A ^χF[x\ θ b (3) sboAfxJ = F[A x (x θ b)] ^' (4) wherein sboxfxj denotes an encryption-related transformation, sboAfx] denotes a decryption-related transformation, and A and b are AES S-box parameter matrices, as are known in the art.

[0070] Thus, according to embodiments of the invention, substituting

Equation 2 in Equations 3 and 4, respectively, and substituting (x+R) for x in both equations, may yield the following modified equations to convert masked data, x+R, into the second representation, to perform operations in the second representation, and to de-convert the resulting data into corresponding data into the first, e.g., AES, representation: sbox[(x+R)J =AM¹ T[M ^χ (xθ Rj] θ b (5) sbox^"1 [(x+R)] = M¹ 7T 4-¹ x ((x θ R) θ b)] (6)

[0071] In accordance with some embodiments of the present invention, the conversion circuitry or software may include circuitry implementing the representation-transformation matrix M. According to some of these embodiments, the circuitry or software implementing the representation-transformation matrix M may be combined with the circuitry or software implementing a linear transformation, e.g., A. According to further embodiments of the invention, the conversion circuitry or software may include four multiplication modules, e.g., as described below, for multiplication by AM^{1 '}, MA^{'1 '}, M, and Λf¹, respectively. Thus, the conversion circuitry may consist of a combination of applying an affine transformation, e.g., multiplication by A and/or addition of b, and the predetermined representation-transformation, e.g. multiplication by M. The use of such operation modules may enhance the efficiency of the conversion circuitry.

[0072] A hardware implementation of matrix multiplication may include any hardware implementation of matrix multiplication, as is known in the art. For example, values y_t of a block y defined by y=Dx, wherein i=l...n and wherein D is a fixed nxn binary matrix, may be computed using the following equation:

[0073] Thus, values of v may be computed using Equation 7. This may be achieved by determining which of the elements of row are nonzero and performing a XOR operation of the corresponding values of x₇.

[0074] According to exemplary embodiments of the invention, operations, e.g. inversion, addition, and/or multiplication operations, equivalent to AES operations may be defined in the second representation, e.g., a GF((2⁴)²) representation, as described below.

[0075] An element x of a GF(2⁸) may be defined by an eight-digit binary number

and an element z of a GF(2⁴) may be defined by a four-digit binary number

[0076] As is known in the art, GF(2⁴) may have a polynomial representation defined by a reduction polynomial over GF(2), e.g.,

may be represented by the polynomial zo+zjt+Z₂t²+z₃t³. Multiplication of elements in the GF may be defined by multiplying the polynomials representing the elements and reducing the result modulo the reduction polynomial.

[0077] According to embodiments of the invention, a bit octet,

of GF(2 ) may be analogous to a linear polynomial z_<m>t+∑_<ι_>, wherein

and

are elements of GF(2⁴). Thus, the second representation may include elements _?_<,„_> and _._</> ofGF(2⁴).

[0078] As part of some embodiments of the present invention, multiplication and addition operations in the second representation may be defined in terms of operations on GE(2⁴) . Provided below is one possible definition of multiplication and addition in the second representation in terms of operations over GF(2⁴ ) . It will be appreciated that other definitions may also be used as part of some embodiments of the present invention.

[0079] Addition and subtraction of two elements of the first representation, e.g., a,d e GF(2^S) , in the second representation may be defined as a bitwise XOR of the two elements, as is known in the art. The product of the two elements, a and d, may be defined as a polynomial product

(^Ω _<m> ^{? + Ω} _{< >}) ^x (^_<m>^ + ^_{< >})^m°d(^² + cd + β) , wherein multiplication and addition of the polynomial coefficients may be defined by operations over GF(2 ) using a given representation. Thus, the product of elements a and d may be calculated using the following equation:

(*_<»_>' + ^a _<ι_> ) ^x (^d _<m>t + ^d _<t> )(mod t² + at + β) =

(^a _<ι_> ^d _<m> - a_<m>d_<m>a + a_<m>d_<ι_>)t ~ a_<m>d_<m>β + ^β _</>^_<;> ≡ r_<m>t + r _l>

wherein:

(A_> ^d _<m> - a_<m>d_<m>a + a_<m>d_<t> ) ≡ r_<m> ≡ [r_ηr₆r₅r ] A_n>^d<m>β + ^a<ι>^d<ι> ^{≡ r}<ι> ≡ fcWoJ

[0080] Thus, the product of elements a and d in the AES, i.e., GF(2^S) , representation may be defined as

. Thus, the product of elements a and d in the AES representation may be calculated using a series of addition and multiplication operations over GF(2⁴), e.g., according to Equation Set 9. It will be appreciated by those skilled in the art, that in the GF(2⁴) the minus sign and the plus sign are interchangeable. Thus, the minus sign of the first equation of Equation Set 9 may be replaced with a plus sign, e.g., as described below.

[0081 ] Reference is made to Fig. 3 A, which schematically illustrates a circuit implementation of a multiplier 302, in accordance with some exemplary embodiments of the invention.

[0082] Multiplier 302 may include multiplication units 304, 306 and 316 for multiplying two GF(2⁴) elements, and a β-multiplication unit 308 for multiplying two GF(2⁴) elements and for multiplying the product of the two elements by β. Units 304, 306, 308 and 316 may include any suitable LUTs and/or circuitry for performing a multiplication of two GF(2⁴) elements, e.g., as described below. Multiplier 302 may also include XOR gates 310, 312 and 314, as are known in the art.

[0083] A square of an element a in the AES representation may be calculated by substituting a=d in Equation Set 9. For example, the following Equation Set may be used, e.g., if the minus sign of the first equation of Equation Set 9 is replaced by a plus sign, as described above:

^a _<ιA_<m> + a_<m a ≡ r_<m> ≡ [r₇r₆r₅r ]

[0084] Reference is made to Fig. 3B, which schematically illustrates a circuit implementation of a squaring unit 320, in accordance with some exemplary embodiments of the invention.

[0085] Squaring unit 320 may include square LUTs 322 and 324 including values corresponding to a square of a GF(2⁴) element, respectively, and a β-square LUT 326 including values corresponding to a multiplication by β of square of a GF(2⁴) element. LUTs 322, 324 and 326 may include any suitable LUTs, e.g., as described below. Squaring unit 320 may also include XOR gate 328 as is known in the art.

[0086] Determining an inverse x^";=(c_<m>t + c_</:>)of data element

(x_<m>x + x_<;> ) χ= (a_<m>t + a_4> ) , may require solving the following set of equations:

Ox + 1 = (c_<m>t + _C<1>) x (a_<m>t + α_<7>) =

0x + l = (c_<m>t + c_<1>) x (a_<m>t + a_<l>)mod(t² +at + β) = (11)

Ox + 1 = (c_<m>a_<m>a + c_<m>a_<t> + c_<;>-._<m>)t + c_<l>a<l> + c_<m>a_<m>β

[0087] Equation Set 11 may be translated into the following system of liner equations over GF(2) :

c_<„_;> = a_<m> (a_< ² _m>β + a; + _a<l>a_<m>aγ

A_> = 0_</> + a_<m>a)(a;_m>β + a² _l> + a_<l>a<m>a

[0088] Thus, in order to calculate an inverse x^"1 of data element x, the values of C_<m> and C_{< >} may be calculated, as described above. Thus, the inverse of element x in the AES representation may be calculated using a series of addition, multiplication, squaring and inversion operations over GF(2 ), e.g., in accordance with Equation Set 12.

[0089] Reference is made to Fig. 3C, which schematically illustrates a circuit implementation of an inversion module 330, in accordance with some exemplary embodiments of the invention.

[0090] Inversion module 330 may include multiplication units 334, 342 and

346 for multiplying two GF(2⁴) elements, e.g., as described below. Module 330 may also include a square LUT 331 including values corresponding to a square of a GF(2⁴) element, and a β-square LUT 332 including values corresponding to a multiplication by β of a square of a GF(2⁴) element, e.g., as described below. Module 330 may further include an inverse LUT 344 including values corresponding to an inverse of a GF(2⁴) element, e.g., as described below. Module 330 may also include XOR gates 340 and 338, as are known in the art.

[0091] According to embodiments of the invention, multiplication over

GE(2⁴ ) may be performed more efficiently by defining GF(2⁴) multipliers and selecting the appropriate multiplier in each case, as explained below.

[0092] According to these exemplary embodiments, a multiplication a xd = [θ3, a aj, OQ] ^X [d₃, d₂, dj, do] over C7E(2⁴), of two elements, e.g., a = [03, (2. o-i, ct-o] and b = [d.3, d2, di, do], of GF(2⁴), may be defined as a sequence of bitwise operations, e.g., additions (XOR) and multiplications (AND), for a given reduction polynomial, e.g., as described above. Thus, for example, the solutions of the multiplication of two elements may be as follows:

Reduction polynomial: t⁴ + 1 + 1

[a₃,a₂,aι,a₀] * [d₃,d₂,dι,d₀] =

[aιd₂+a₃d₃+a₃do+a₂dι+a₀d₃,a₂d₃+aod₂+a₃d₃+a do+aιdι+d₂a₃, aιd₃+d a₃+aodι+a₂d₂+a₂d₃+aιdo+a₃dι , aodo+aιd₃+a₂d₂+a₃dι]

Reduction polynomial: t⁴ + 1³ + 1

[a₃,a₂,aι,a₀] * [d₃,d₂,dι,d₀] = aod +aιd +a₃d₂+a₂d₃+a₃dι+a₂dι+aιd₂+a₃d₃+a do+a₂d₂,aod₂+a₃d₃+aιdι+a₂do,aodι+a₃d₂+a ₃d₃+aιdo+a₂d₃,aιd₃+aodo+a d₃+a₃d₂+a₂d₂+a₃dι+a₃d₃] Reduction polynomial: t⁴ + 1³ + 1² + 1 + 1

[a₃,a₂,aι,a₀] * [d₃,d₂,dι,d₀] =

[a₂dι+a₃do+a₃dι+aιd₂+aιd₃+a d₂+a₀d₃,a₃dι+a₂d₂+aιdι+a₂do+a₀d₂+aιd₃, aodι+aιd₃+aιdo+a₃dι+a d₃+a₂d₂, a₃d₂+aιd₃+aodo+a₂d₃+a₂d₂+a₃dι]

[0093] It should be noted that some of the multiplications of elements in each of the solutions may be similar for two or more output bits. For example, the expression aid₃+a₂d₂+a di, appearing twice in the solutions listed above, may be computed only once in order to minimize hardware requirements, e.g., using XOR and AND gates. It will be appreciated by those skilled in the art that the solutions for multiplication of two elements in GE(2⁴), using each of the three quadratic reduction polynomials discussed above, may be used to construct a GF(2⁴) multiplier for each of the quadratic reduction polynomials. Such multiplier may be implemented in hardware and/or software as is known in the art. An appropriate GF(2⁴) multiplier may be constructed for a given representation-transformation matrix. Since each representation-transformation matrix may be defined by one of the three irreducible reduction polynomials over GF(2⁴) in combination with an extension polynomial, as described above, theGE(2⁴) multipliers may be predetermined. It will be appreciated by persons skilled in the art that other suitable implementations of GE(2⁴) multipliers may be used additionally or alternatively in accordance with exemplary embodiments of the invention.

[0094] Inversion, denoted INV, and squaring, denoted SQR, in GF(2⁴) may be implemented by two respective, relatively small, Look-Up-Tables (LUTs), for example, having a size of 8-bytes each, e.g., 16 nibbles. According to some embodiments of the present invention, coefficient β may be predetermined. Thus, the value β g² for an element g e GF(2⁴) may also be stored in an 8-byte LUT, which may be denoted βSQR, thereby eliminating one multiplication fiom the set of computations required for computing Equation Set 12. According to alternative embodiments, SQR, INV and/or β SQR in GE(2⁴) may be implemented by any suitable circuit, as is known in the art. For example, an SQR circuit may be implemented by substituting a=d in the solutions for multiplication of two elements, as described above. Thus, for example, the SQR circuits may implement the following solutions, for =l :

Reduction polynomial: t⁴ + 1 + 1

[a₃,a₂,aι,a₀]² = [a₃, aι+a₃, a₂, ao +a₂]

Reduction polynomial: t⁴ + 1³ + 1

[a₃,a₂,aι,a₀] ^:=:[a₂+a₃, aι+ a₃, a₃, a₀+a₂+a₃]

Reduction polynomial: t⁴ + 1³ + 1² + 1 + 1

[a ,a₂,aι,ao] =[a₂, aι+a₂, a₂+a₃, a₀+a₂]

[0095] It may be noted that the circuitry implementation of embodiments of the invention, may be more compact than the corresponding LUT implementation. However, in some S-box implementations, a LUT may provide more efficient processing of the data.

[0096] Reference is made to Fig. 4, which schematically illustrates a circuit implementation of an AES compatible device 400 for encrypting/decrypting masked data, in accordance with some exemplary embodiments of the present invention.

[0097] According to exemplary embodiments of the invention, device 400 may include an input conversion block 412, a manipulation block, e.g., e.g., an inversion block 414, and an output de-conversion block 416. Device 400 may have an encryption mode of operation and/or a decryption mode of operation, e.g., as described below.

[0098] According to exemplary embodiments of the invention, block 412 may include an input conversion module 418 to receive a masked input data signal 438, e.g., corresponding to a 32-bit column vector of x+R, in AES representation, e.g., in a GF(2⁸) representation, and to convert this data into data in a GF((2⁴)²) representation. In the decrypt mode of operation, conversion module 418 may also apply the decrypt affine transformation to x+R, e.g., according to Equation 6 above. Thus, for example, an output signal 440 of module 418 may have a value corresponding to the value X;+Rz, wherein x_t=Mx and R_t=MR in the encryption mode of operation, and wherein x_t=MA^"1x+MA^~Ib and R_t=MA^'1R in the decryption mode of operation. [0099] Block 412 may also include a mask conversion module 420 to convert input mask R into an updated mask. In order to obtain an updated mask corresponding to the converted masked data, the conversion of the mask performed by module 420 may include a linear transformation corresponding to the linear transformation performed by module 418. For example, in the encrypt mode of operation, conversion module 420 may multiply R by M, i.e., to obtain MR. In the decrypt mode of operation, conversion module 420 may multiply R by MA^"1, i.e., to obtain MA^"!R.

[00100] Module 418 and/or module 420 may include any circuitry, Look-Up

Tables (LUTs) and/or any suitable hardware and or software to convert data in a first representation into corresponding data in a second representation and/or to perform an affine transformation, e.g., as described below.

[00101] Reference is made to Fig. 5 A which schematically illustrates a circuit implementation of an input conversion module 500, in accordance with some exemplary embodiments of the invention.

[00102] According to exemplary embodiments, module 500 may include a multiplier 506 to implement a multiplication of the x+R by M. Module 500 may also include a XOR gate 508 to implement a XOR operation of x+R and b, and a multiplier 510 to implement a multiplication of an output 518 of XOR gate 508 by MA^'1. Multipliers 506 and/or 510 may include any suitable multiplier for multiplying an nxn matrix by a vector, e.g., as described above. Module 500 may also include a multiplexer 512, as is known in the art, to select between the encryption and decryption modes of operation, e.g., by selecting between an output signal 514 of multiplier 506 and an output signal 516 of multiplier 510.

[00103] Reference is made to Fig. 5B which schematically illustrates a circuit implementation of a mask conversion module 530, in accordance with some exemplary embodiments of the invention.

[00104] According to exemplary embodiments, module 530 may include a multiplier 532 to implement a multiplication of R by M. Module 530 may also include a multiplier 534 to implement a multiplication of R by MA^"1. Multipliers 532 and/or 534 may include any suitable multiplier for multiplying an nxn matrix by a vector, e.g., as described above. Module 530 may also include a multiplexer 536, as is known in the art, to select between the encryption and decryption modes of operation, e.g., by selecting between an output signal 533 of multiplier 532 and an output signal 535 of multiplier 534.

[00105] Referring back to Fig. 4, Inversion block 414 may include any circuitry and/or LUTs and/or any suitable hardware and or software to invert the converted data in the second representation.

[00106] According to an exemplary embodiment of the invention, block 414 may include a first multiplier 470 to receive signal 440 and signal 442, and to provide a signal 471, e.g., corresponding to the value (x_t+R)Rt. Block 414 may also include a squaring unit 472 to receive signal 472 and to provide a signal 473, e.g., corresponding to the value R ², and a first adder 474 to receive signal 471 and signal 473 and to provide a signal 475, e.g., corresponding to the value oϊx_tR_t. Block 414 may further include a Zero Detection (ZD) module 480 to receive signal 475 and to provide a signal, e.g., having a zero value if x_tR_t?0, and a non-zero value, e.g., 1, if x_tR_t-0. Block 414 may also include an AND gate 482, e.g., as is known in the art, to receive signal 442 and signal 481 and to provide a signal 483. For example, signal 483 may have zero value if x_tR_t?0, and a non-zero value, e.g., R_t, if x_tR_t=0. Block 414 may further include a second adder 476 to receive signal 475 and signal 483 and to provide a signal 485, e.g., corresponding to the value oϊx_tR_t iϊx_tR_t?0, and to the value of R_t if x_tR_t=0. Block 414 may further include an inversion module 478 to receive signal 485 and to provide a signal 487, e.g., corresponding to a value of (xtR)^'1 if x_tR_t?0 and to the value of R ¹ if x_.R_.=0, and a third adder 479 to receive signal 487 and a signal having the unit value, i.e., the value 1, and to provide a signal 489, e.g., corresponding to a value of (x_tR^+l if x_tR_t?0 and to the value of R_. ^";+i if x_tR_τ=0. Block 414 may further include a second multiplier 486 to receive signal 486 and signal 489 and to provide a signal 491, e.g., corresponding to a value of x_t ^" +R. if x_tR_t?0 and to the value of 1+R_t if x,R,=0. Block 414 may further include a fourth adder 484 to receive signals 491 and 483 and to provide a signal 444, e.g., corresponding to a value of x^+R_t if x_.R_.?0 and to the value of R, if x_tR_t=0. Multiplier 470 and/or multiplier 486 may include any circuitry, Look-Up Tables (LUTs) and/or any suitable hardware and/or software to multiply two elements of the first representation using the second representation, e.g., as described above. Unit 472 may include any circuitry, Look-Up Tables (LUTs) and/or any suitable hardware and/or software to provide a square of an element of the first representation using the second representation, e.g., as described above. Inversion module 478 may include any circuitry, Look-Up Tables (LUTs) and/or any suitable hardware and/or software to invert data of the first representation using the second representation, e.g., as described above. Adder 474, adder 476, adder 479, and/or adder 484 may include any software and/or hardware to implement an addition of two elements. For example, adder 474, adder 476, adder 479, and or adder 484 may include a XOR gate, as is known in the art. Module 480 may include, for example, any circuitry, Look-Up Tables (LUTs) and/or any suitable hardware and/or software to implement a logical NOT followed by a logical AND of signal 481.

[00107] According to these exemplary embodiments, the input to inversion module 478, i.e., signal 485, has a non-zero value, e.g., even if x_tR_t=0 since R_t?0. Thus, a zero input, i.e., x_t=0, is masked by block 414, e.g., such that the input to the inversion module has a non-zero mask value, e.g., R_t.

[00108] Thus, it will be appreciated by those skilled in the art that inversion block 414 may be implemented to inhibit a DPA attack, e.g., using a zero input, on the AES device.

[00109] According to other embodiments of the invention, block 414 may include any other suitable configuration, e.g., a configuration analogous to the configuration of inversion block 204, as described above with reference to Fig. 2.

[001 10] According to the exemplary embodiments described above, signal 444 may have, for example, a value corresponding to ((MX)ΑMR) in the encryption mode of operation, and a value corresponding to ((MA)^'1 (x+b)^'1 +MA^'1 R) in the decryption mode of operation, as described above.

[001 1 1] According to exemplary embodiments of the invention, block 416 may include an output de-conversion module 424 to receive the output of block 414, e.g., signal 444, in the second representation, e.g., in a GF((2⁴)²) representation, and to de-convert this data into de-converted data in the first, e.g., GF(2⁸), representation. In the encrypt mode of operation, conversion module 424 may also apply the encrypt affine transformation, e.g., according to Equation 7 above. Thus, for example, an output signal 434 of module 424 may have a value corresponding to x '+R ', wherein A=Ax^"!+b and R '=AR in the encryption mode of operation, and wherein x '=A^"' (x+b)^' and R'=_4^";R in the decryption mode of operation. According to these embodiments, R ' may be used as a mask, since R' may correspond to a regular linear transformation of the mask R.

[00112] Block 416 may also include a mask de-conversion module 422 to de-convert the updated mask. In order to de-convert the updated mask in correspondence to the de-conversion of the data, the de-conversion performed by module 422 may include a linear transformation corresponding to the linear transformation performed by module 420. For example, in the decrypt mode of operation, de-conversion module 422 may multiply A^'1 MR by ¹, i.e., to obtain A^'!R. In the encrypt mode of operation, de-conversion module 422 may multiply MR by AM¹, i.e., to obtain AR. Thus, an output mask signal 432 may include a value corresponding to R'. Module 422 and/or module 424 may include any circuitry, Look-Up Tables (LUTs) and/or any suitable hardware and/or software to convert data in a first representation into corresponding data in a second representation and/or to perform an affine transformation, e.g., as described below.

[00113] Reference is made to Fig. 6 A which schematically illustrates a circuit implementation of an output de-conversion module 600, in accordance with some exemplary embodiments of the invention.

[00114] According to exemplary embodiments, module 600 may include a multiplier 602 to implement a multiplication of the manipulated data, e.g., signal 444, by M¹. Module 600 may also include a multiplier 604 to implement a multiplication of the manipulated data by AM¹, and a XOR gate 606 to implement a XOR operation of an output of multiplier 604 and b. Multipliers 602 and/or 604 may include any suitable multiplier for multiplying an nxn matrix by a vector, e.g., as described above. Module 600 may also include a multiplexer 608, as is known in the art, to select between the decryption and encryption modes of operation, e.g., by selecting between an output signal 614 of multiplier 602 and an output signal 616 of multiplier 606.

[00115] Reference is made to Fig. 6B which schematically illustrates a circuit implementation of a mask de-conversion module 630, in accordance with some exemplary embodiments of the invention.

[00116] According to exemplary embodiments, module 630 may include a multiplier 632 to implement a multiplication of the updated mask, e.g., signal 442, by AM¹. Module 630 may also include a multiplier 634 to implement a multiplication of the updated mask by Λf⁷. Multipliers 632 and/or 634 may include any suitable multiplier for multiplying an nxn matrix by a vector, e.g., as described above. Module 630 may also include a multiplexer 636, as is known in the art, to select between the decryption and encryption modes of operation, e.g., by selecting between an output signal 633 of multiplier 632 and an output signal 635 of multiplier 634.

[001 17] Referring back to Fig. 4, device 400 may also include a mix-column module 455 to provide a signal 456 corresponding to a mix-column operation on signal 434. The mix-column operation may include multiplying signal 434, e.g., including the 32-bit column vector x'+R ', with a Rijndael mix-column matrix, as is known in the art. For example, the mix-column operation may be calculated as follows:

wherein X '_I+R ' , x'₂+R ₂, x'5+R 5, and x^+R are masked data elements of the column vector x '+R .

[001 18] It will be appreciated by those skilled in the art that all the elements of vector (R 'ι, R ' , R'₃, and R '₄) have non-zero values, i.e., R 'tf O, R '₂?0, R '₃?0, and R '₄?0, since R '₁, R '₂, R '₃, and R '₄ correspond to a linear transformation of respective elements, e.g., R_/, R₂, R_3. and R₄, of R. However, the product of the vector (R 'ι, R '2, R '₃, R '₄) with the Rijndael column-mix matrix may have a zero value. This may have the undesired result of distorting the mask of a subsequent AES round. To prevent this potential problem, according to some exemplary embodiments of the invention, Ri, R₂, R₃, and R₄, of R may have pre-set equal values, i.e., R_/=R₂=R₅=R₄(. It will be appreciated by those skilled in the art that pre-set equal values

may ensure that the product of the vector (R ';, R '_>, R '₃, R '₄) with the Rijndael column-mix matrix is always non-zero. Other pres-set values may also be used to ensure non-zero result of the Rijndael column-mix multiplication in accordance with embodiments of the invention.

[001 19] The AES round may also include performing a shift-row operation, as is known in the art. The shift-row operation may include shifting between elements of each row of a 4x4 data matrix representing 4 columns of masked data, as is known in the art. The data matrix may include 16 elements each corresponding to a sum x '_k+R '_k, wherein k=1..16. According to some exemplary embodiments of the invention, all sixteen elements of R may have pre-set equal values, i.e.,

in order to ensure the mask of the subsequent round is not distorted. Other pres-set values may also be used to ensure non-zero result of the Rijndael row-mix multiplication in accordance with embodiments of the invention. It will be appreciated by those skilled in the art that pre-setting all sixteen elements of the mask R as described above may have a relatively negligible effect on the brute-force required for a DPA attack.

[00120] It will be appreciated by those skilled in the art that the vector (1, I, 1, 1) is an eigenvector of the Rijndael mix-column matrix, i.e., as expressed by the following equation:

(14)

[00121] Thus, according to exemplary embodiments of the invention the value of signal 432 may not be updated in correspondence to the mix-column operation performed on signal 432.

[00122] According to some exemplary embodiments of the invention device

400 may further include a mask-removing module 460 for unmasking the masked de-converted data, e.g., after a final AES round. According to exemplary embodiments, module 460 may include a XOR gate 462 to provide an output signal 464 corresponding to a sum of a first input corresponding to signal 456 and a second input. After the final AES round the second input of gate 462 may be associated with signal 432. Thus, the value of the updated mask may be XORed with the masked de-converted data after the last round, such that the mask is removed from the manipulated data.

[00123] According to some exemplary embodiments of the invention, since output signal 464 is masked by R ', mask R ' may be used as the input mask in succeeding AES rounds, as described below. [00124] According to some exemplary embodiments of the invention, device 400 may further include a mask-input module 450 capable of using a new mask in a succeeding AES round, as described below. Module may include a first XOR gate 428 to provide a sum of a first input corresponding to the value, e.g., x"+R ', of a signal 465 of a previous AES round, and a second input corresponding to a value, e.g., R, of a random mask signal 452. Thus, for example, an output signal 454 of XOR gate 428 may correspond to the value x"+R '+R. Configuration 450 may also include a second XOR gate 426 to provide block 412 with signal 438 corresponding to a sum of signal 454 and signal 432. Thus, signal 438 may have a value corresponding to x"+R.

[00125] It will be appreciated by those skilled in the art that the input and output of each of the XOR gates of configuration 450 may include a mask, i.e., R and/or R '.

[00126] According to exemplary embodiments of the invention, the representation-transformation matrix M implemented by device 400, may be predetermined based on desired optimization criteria, e.g., minimal circuit area for implementing device 400, as described below.

[00127] According to exemplary embodiments of the invention, a set of circuits, e.g. 192 circuits corresponding to 192 possible transformation matrices when a=l, may be fabricated to implement device 400. For example, each one of the circuits may be synthesized using a DC Shell 2001.08-spl (DC Expert) available from Synopsis. A target library TSMC 0.18μ (SAAG-X Artisane) may be used. The synthesis may be performed for various timings, e.g., time propagation delays, for example, ranging from 12nSec to 6nSec. These parameters may enable using different respective frequencies, e.g., in the range of 66.7MHz to 111MHz by adding a margin, for example, a 3 -nanosecond margin. According to the results of the synthesis, a reduction of approximately 45% in the circuit area compared to the circuit area of a conventional AES device may be achieved if the representation-transformation matrix [01 0c 50 ed 42 35 67 92] is implemented.

[00128] According to exemplary embodiments of the invention, a random bit generator may be implemented to produce the non-zero mask, R, e.g., as described below. However, it will be appreciated by those skilled in the art that any other suitable device and/or method may be implemented to produce non-zero mask R. [00129] According to exemplary embodiments of the invention, the random bit generator may be used to produce non-zero mask R having v bits, wherein v is a power of two, e.g., v=8. The generator may generate log v +v-l bits. The first log v bits may be used to define a first number, w, wherein 0?w<v. The remaining v-1 bits may be used to define a second number, p. The v-bit mask may be generated by setting the value of the w-th bit of R to 1, and by substituting the other v-1 bits of R with the v-1 bits ofp, respectively. For example, if v=8, the random bit generator may generate log 8 +8-1=10 random bits, e.g., 1011100101. Accordingly, w=_O2₂=5, pAlOOΪOl, and R=l 1100101.

[00130] It will be appreciated by those skilled in the art that the method described above may provide a non-zero mask, since a value of one may always by substituted at the w-th bit of the mask. Furthermore, the above method may be implemented to provide any one of the possible non-zero v-bit masks. Furthermore, Masks having equal Hamming Weights may be generated at equal probabilities by a mask generator implementing the method described above. A conditional entropy value corresponding to generating a specific mask if a previously generated mask may be calculated, for example, as follows:

[00131] Thus, the method described above may be implemented to provide a relatively high entropy value, e.g., of approximately 7.90244 if v=8.

[00132] It will be appreciated by persons skilled in the art that the present invention is not limited to the exemplary embodiments of the invention shown and described herein with reference to the accompanying drawings. While certain features of the invention have been illustrated and described, many modifications, substitutions, changes, and equivalents may occur to those skilled in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.

Claims

[00133] What is claimed is:

1. A method of manipulating data comprising: converting masked input data in a first representation of a finite field into converted data in a second representation of said finite field; and manipulating said converted data to obtain masked manipulated data.

2. The method of claim 1 comprising converting an input mask of said masked input data into an updated mask in said second representation.

3. The method of claim 2, wherein converting said masked input data comprises performing an affine transformation.

4. The method of claim 3, wherein said affine transformation comprises a linear transformation, and wherein converting said input mask comprises performing said linear transformation.

5. The method of any one of claims 2-4, wherein manipulating said converted data comprises manipulating said converted data using said updated mask.

6. The method of anyone of claims 2-5, wherein converting said masked input data results in said converted data being masked by said updated mask.

7. The method of any one of claims 2-6, wherein manipulated said converted data results in said manipulated data being masked by said updated mask.

8. The method of any one of claims 2-7, wherein manipulating said converted data comprises: multiplying said converted data by said updated mask to obtain first intermediate data; adding to said first intermediate data a square of said updated mask to obtain second intermediate data; inverting said second intermediate data to obtain third intermediate data; adding a unit data bit to the third intermediate data to obtain fourth intermediate data; and multiplying said fourth intermediate data by said updated mask to obtain masked inverted data in said second representation. 9. The method of any one of claims 1-8 comprising de-converting said manipulated data to obtain masked de-converted data in said first representation. lO.The method of claim 9, wherein de-converting said manipulated data results in said de-converted data being masked by a linear transformation of said input mask:

1 l.The method of claim 9 or 10 comprising unmasking said de-converted masked data.

12.The method of any one of claims 9-11 comprising de-converting said updated mask.

13. The method of any one of claims 9-12, wherein de-converting said manipulated data comprises performing an affine transformation.

14.The method of claim 13 comprising de-converting said updated mask, wherein said affine transformation comprises a linear transformation, and wherein de-converting said updated mask comprises performing said linear transformation.

15. The method of any one of claims 1-14 wherein manipulating said converted data comprises performing at least one operation equivalent to at least one desired operation in said first representation.

16.The method of claim 15 wherein said at least one operation comprises an inversion operation.

17.The method of any one of claims 1-16 wherein said finite field comprises a Galois Field.

18. The method of claim 17 wherein said finite field comprises a GF(g^h).

19. The method of claim 18 wherein g equals two.

20.The method of claim 19 wherein said first representation comprises a GF(2^2s) and wherein said second representation comprises a GF((2^S)²).

2 l.The method of claim 20 wherein s equals four.

22.The method of any one of claims 2-21, comprising masking input data using said input mask to provide said masked input data.

23.The method of any one of claims 2-22, comprising generating said input mask.

24.The method of claim 23 comprising: generating a first set of log v bits and a second set of v-1 bits; defining a number w based on said first set of bits; •setting the value of a w-th bit of said input mask to equal one; and substituting v-1 bits of said input mask with the v-1 bits of said second set, respectively. 25. The method of any one of claims 2-24, wherein at least some bits of said input mask have pre-set values.

26.A device for manipulating data comprising: a conversion block to convert masked input data in a first representation of a finite field into converted data in a second representation of said finite field; and a manipulation block to manipulate said converted data to obtain masked manipulated data. 27.The device of claim 26, wherein said conversion block converts an input mask of said masked input data into an updated mask in said second representation.

28.The device of claim 27, wherein said conversion block comprises: an input conversion module to convert said masked input data in said first representation into said converted data; and a mask conversion module to convert said input mask into said updated mask. 29. The device of claim 28, wherein said input conversion module comprises a multiplier to multiply said masked input data by a representation-transformation matrix, and wherein said mask conversion module comprises a multiplier to multiply said input mask by said representation-transformation matrix.

30. The device of claim 29, wherein said input conversion module is adapted to perform on said masked input data an affine transformation. 3 l.The device of claim 30, wherein said mask conversion module is adapted to perform on said mask a linear transformation corresponding to said affine transformation.

32.The device of any one of claims 26-31 wherein said manipulating block performs at least one operation equivalent to at least one desired operation in said first representation.

33.The device of claim 32, wherein said manipulation block comprises an inversion block to invert said converted data in said second representation to provide masked inverted data.

34.The device of any one of claims 28-33, wherein said manipulation block comprises: a first multiplier to multiply an output of said input conversion module with an output of said mask conversion module; a squaring module to provide a square of the output of said mask conversion module; a first adder to add an output of said squaring module to an output of said first multiplier; a zero detector to provide an output of a zero value if an output of said first adder is non-zero; an AND gate to provide an output corresponding to a logical AND of an output of said zero detector and an output of said mask conversion module; a second adder to add an output of said AND gate to an output of said first adder; an inversion module to invert an output of said second adder; ^• a third adder to add a unit value to an output of said inversion module; a second multiplier to multiply the output of said mask conversion module with an output of said second adder; and a fourth adder to add an output of said second multiplier to an output of said AND gate.

35.The device of any one of claims 28-33, wherein said manipulation block comprises: a first multiplier to multiply an output of said input conversion module with an output of said mask conversion module; a squaring module to provide a square of the output of said mask conversion module; a first adder to add an output of said squaring module to an output of said first multiplier; an inversion module to invert an output of said first adder; a second adder to add a unit value to an output of said inversion module; and a second multiplier to multiply the output of said mask conversion module with an output of said second adder. 36. The device of any one of claims 26-35 comprising a de-conversion block to de-convert said manipulated data to obtain masked de-converted data in said first representation.

37.The device of any one of claims 27-35 comprising a de-conversion block to de-convert said manipulated data to obtain masked de-converted data in said first representation, the de-conversion block comprising: an output de-conversion module to de-convert said manipulated data into said first representation; and a mask de-conversion module to de-convert said updated mask. 38. The device of claim 37, wherein said output de-conversion module is adapted to perform on said manipulated data an affine transformation.

39.The device of claim 38, wherein said mask de-conversion module is adapted to perform on said updated mask a linear transformation corresponding to said affine transformation.

40. The device of any one of claims 36-39 comprising a mask-removing module to unmask said masked de-converted data.

4 l.The device of any one of claims 27-40 comprising a mask generator to generate said input mask.

42. The device of claim 41, wherein said mask generator is able to generate a first set of log(v) bits and a second set of v-1 bits, define a number w based on said first set of bits, set the value of a w-th bit of said input mask to equal one, and substitute v-1 bits of said input mask with the v-1 bits of said second set of bits, respectively.

43.The device of any one of claims 27-42, wherein at least some bits of said input mask have pre-set values.

44.A method of generating a non-zero mask having v bits, the method comprising: generating a first set of log v bits and a second set of v-1 bits; defining a number w based on said first set of bits; setting the value of a w-th bit of said mask to equal one; and substituting v-1 bits of said mask with the v-1 bits of said second set, respectively. 45. A method of encrypting data comprising: converting masked input data in a first representation of a finite field into converted data in a second representation of said finite field; converting an input mask of said masked input data into an updated mask in said second representation; manipulating said converted data using said updated mask by performing at least one operation equivalent to a desired encryption operation in said first representation to obtain manipulated data; and de-converting said manipulated data to obtain manipulated data in said first representation. 46. A method of decrypting data comprising: converting masked input data in a first representation of a finite field into converted data in a second representation of said finite field; converting an input mask of said masked input data into an updated mask in said second representation; manipulating said converted data using said updated mask by performing at least one operation equivalent to a desired decryption operation in said first representation to obtain manipulated data; and de-converting said manipulated data to obtain manipulated data in said first representation.