A COMPUTATION DEVICE AND METHOD

Abstract

Some embodiments are directed to an electronic computation device (100) arranged for obfuscated execution of a multiplication. The device comprises a storage (120) arranged for storing multiple variables used in the execution of an arithmetic operation, a variable (x: y; 2) of the multiple variables being represented as multiple multiplicative shares (X=(x.sub.0, x.sub.1, . . . , x.sub.m1); Y=(y.sub.0, y.sub.1, . . . , y.sub.m1); 20), said multiplicative shares being represented in the storage as multiple additive shares (x.sub.i=(x.sub.i,0,x.sub.i,1, . . . , x.sub.i,n1); Yi=(y.sub.i,0,y.sub.i,1, . . . , y.sub.i,n1); 210, 220).

Claims

1. An computation device arranged for obfuscated execution of a multiplication, comprising: a memory circuit, wherein the memory circuit is arranged to store a plurality of variables, wherein each variable (x;y) of the plurality of variables are represented as one or more multiplicative shares (X=(x.sub.0, x.sub.1, . . . , x.sub.m1); Y=(y.sub.0,y.sub.1, . . . , y.sub.m1)), wherein the multiplicative shares are represented as a plurality of additive shares (X.sub.i=(x.sub.i,0, x.sub.i,1, . . . , x.sub.i,n1); Y.sub.i=(y.sub.i,0, y.sub.i,1, . . . , y.sub.i,n1)) a processor circuit, wherein the processor circuit is configured to multiply a first variable of the plurality of variables with a second variable of the plurality of variables to obtain a multiplication result (z=xy), the multiplying comprising: for each multiplicative share of the first variable, computing a convolution (Z.sub.i=X.sub.i*Y.sub.i) of the additive shares representing the multiplicative share of the first variable (X.sub.i) and the additive shares representing the corresponding multiplicative shares of the second variable (Y.sub.i), storing the result of the convolutions as a plurality of additive shares (Z.sub.i) in the memory circuit as a representation in additive shares of at least one multiplicative share of the multiplication result (z).

2. The computation device as in claim 1, further comprising a communication interface, wherein the communication interfaces arranged to obtain at least one of the first variable of the plurality of variables and the second variable of the plurality of variables.

3. The computation device as in claim 1, wherein the computation device is arranged for the obfuscated execution of a cryptographic operation, wherein the cryptographic operation comprises at least an arithmetic operation.

4. computation device as in claim 3, wherein the arithmetic operation comprises at least one multiplication and at least one conditional assignment, wherein the processor circuit is configured to assign either a first variable of the plurality of variables (x) to a third variable (z) or a second variable of the plurality of variables (y) to the third variable (z) depending on a binary condition (d), wherein the processor circuit is arranged to obtain a first selection number (R) and a second selection number (R) in dependence on the binary condition, wherein the first selection number and the second selection number are represented as a plurality of additive shares, wherein the processor circuit is arranged to, for each multiplicative share of the first variable, compute a first convolution (R*X.sub.i) of a first selection number (R) and the additive shares representing the multiplicative share of the first variable of the plurality of variables (X.sub.i), wherein the processor circuit is arranged to, for each multiplicative share of the first variable compute, a second convolution (R*Y.sub.i) of a second selection number (R) and the additive shares representing the corresponding multiplicative share of the second variable of the plurality of variables (Y.sub.i), wherein the processor circuit is arranged to, for each multiplicative share of the first variable, add the results of the first convolution and the second convolution (Z.sub.i=R*X.sub.i+R*Y.sub.i), wherein the processor circuit is arranged to store the resulting plurality of additive shares (Z.sub.i) in the memory circuit as a representation in additive shares of a multiplicative share of the assignment result (z).

5. The computation device as in claim 4, wherein the first selection number and the second selection number are additive representations of 0 or 1.

6. The computation device as in claim 4, wherein the arithmetic operation comprises a conditional assignment followed by a multiplication with the conditional assignment result.

7. The computation device as in claim 3, wherein the arithmetic operation comprises a first exponentiation, wherein the first exponentiation comprises repeated obfuscated multiplications.

8. The computation device as in claim 6, wherein the arithmetic operation comprises an exponentiation, wherein the exponentiation comprises repeated multiplications, wherein the multiplications depend on bits in an exponent, wherein a conditional assignment is executed in dependency on the bits in the exponent followed by a multiplication.

9. The computation device as in claim 3, wherein the arithmetic operation comprises an exponentiation, wherein the exponentiation is executed according to a Montgomery ladder, wherein multiplications and conditional assignments in the Montgomery ladder are obfuscated.

10. The computation device as in claim 9, wherein the Montgomery ladder is implemented according to: TABLE-US-00006 s 1 t h For i = 1 to 0 do u (1d.sub.i)s + d.sub.it mod N (I) s su mod N (II) t tu mod N (II) End for, wherein h represents the base of the exponentiation, and wherein bits d.sub.i represent bits of the exponent, wherein the conditional assignments (I) and the multiplications (II) are obfuscated.

11. The computation device as in claim 7 wherein the processor circuit is arranged to perform a second exponentiation by obtaining a first exponent and a second exponent, wherein the first exponent has fewer bits than the second exponent, wherein the second exponentiation by the first exponent and second exponent is equal to exponentiation by a product exponent, wherein the product exponent is equal to first exponent multiplied by the second exponent, wherein the exponentiation with the first exponent comprises obfuscated multiplication and/or conditional assignments.

12. The computation device as in claim 1, wherein the additive shares representing multiplicative shares are stored in encoded form.

13. The computation device as in claim 1, wherein the number of multiplicative share is at least one.

14. A computation method for obfuscated execution of a multiplication, the method comprising: storing plurality of variables, wherein each variable (x;y) of the plurality of variables are represented as one or more multiplicative shares (X=(x.sub.0, x.sub.1, . . . , x.sub.m1); Y=(y.sub.0, y.sub.1, . . . , y.sub.m1), wherein the multiplicative shares are represented as plurality of additive shares (X.sub.i=(x.sub.i,0, x.sub.i,1, . . . , x.sub.i,n1); Y.sub.i=(y.sub.i,0, y.sub.i,1, . . . , y.sub.i,n1); and multiplying a first variable with a second variable to obtain a multiplication result (z=xy), the multiplying comprising: for each multiplicative share of the first variable, computing a convolution (Z.sub.i=X.sub.i*Y.sub.i) of the additive shares representing the multiplicative share of the first variable (X.sub.i) and the additive shares representing the corresponding multiplicative shares of the second variable (Y.sub.i); and storing the result of the convolutions as a plurality of plurality of additive shares (Z.sub.i) in the memory circuit as a representation in additive shares of at least one multiplicative share of the multiplication result (z).

15. A computer program stored on a non-transitory medium, wherein the computer program when executed on a processor performs the method as claimed in claim 14.

16. The computation device as in claim 5, wherein the arithmetic operation comprises a conditional assignment followed by a multiplication with the conditional assignment result.

17. The method as in claim 14, further comprising obfuscating execution of a cryptographic operation, wherein the cryptographic operation comprises at least an arithmetic operation.

18. The method as in claim 17, further comprising: assigning a first variable of the plurality of variables (x) to a third variable (z) or a second variable of the plurality of variables (y) to the third variable (z) depending on a binary condition (d); obtaining a first selection number (R) and a second selection number (R) in dependence on the binary condition, wherein the first selection number and the second selection number are represented as a plurality of additive shares; for each multiplicative share of the first variable, computing a first convolution (R*X.sub.i) of a first selection number (R) and the additive shares representing the multiplicative share of the first variable of the plurality of variables (X.sub.i); for each multiplicative share of the first variable computing, a second convolution (R*Y.sub.i) of a second selection number (R) and the additive shares representing the corresponding multiplicative share of the second variable of the plurality of variables (Y.sub.i); for each multiplicative share of the first variable, adding the results of the first convolution and the second convolution (Z.sub.i=R*X.sub.i+R*Y.sub.i); and storing the resulting plurality of additive shares (Z.sub.i) in a memory circuit as a representation in additive shares of a multiplicative share of the assignment result (z), wherein the arithmetic operation comprises at least one multiplication and at least one conditional assignment.

19. The method as in claim 18, wherein the first selection number and the second selection number are additive representations of 0 or 1.

20. The method as in claim 18, wherein the arithmetic operation comprises a conditional assignment followed by a multiplication with the conditional assignment result.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0024] Further details, aspects, and embodiments of the invention will be described, by way of example only, with reference to the drawings. Elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. In the Figures, elements which correspond to elements already described may have the same reference numerals. In the drawings,

[0025] FIG. 1 schematically shows an example of an embodiment of a computation device,

[0026] FIG. 2 schematically shows an example of an embodiment of a representation of a variable,

[0027] FIG. 3a schematically shows an example of an embodiment of a multiplication,

[0028] FIG. 3b schematically shows an example of an embodiment of a conditional assignment,

[0029] FIG. 4 schematically shows an example of an embodiment of a computation method,

[0030] FIG. 5a schematically shows a computer readable medium having a writable part comprising a computer program according to an embodiment,

[0031] FIG. 5b schematically shows a representation of a processor system according to an embodiment.

LIST OF REFERENCE NUMERALS IN FIGS. 1-3b, 5a-5b:

[0032] 100 a computation device

[0033] 110 a communication interface

[0034] 120 a storage

[0035] 132 a convolution unit

[0036] 134 an addition unit

[0037] 142 a multiplication unit

[0038] 144 a conditional assignment unit

[0039] 150 an exponentiation unit

[0040] 2 a number

[0041] 20 multiple multiplicative shares

[0042] 21-22 a multiplicative share

[0043] 210, 220 multiple additive shares

[0044] 211-213, 221-223 an additive share

[0045] 30, 40 multiple multiplicative shares

[0046] 31-33, 41-43 a set of additive shares

[0047] 51, 52 a selection number represented as multiple additive shares

[0048] 350, 351, 352 a convolution unit

[0049] 353 an addition unit

[0050] 1000 a computer readable medium

[0051] 1010 a writable part

[0052] 1020 a computer program

[0053] 1110 integrated circuit(s)

[0054] 1120 a processing unit

[0055] 1122 a memory

[0056] 1124 a dedicated integrated circuit

[0057] 1126 a communication element

[0058] 1130 an interconnect

[0059] 1140 a processor system

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0060] While this invention is susceptible of embodiment in many different forms, there are shown in the drawings and will herein be described in detail one or more specific embodiments, with the understanding that the present disclosure is to be considered as exemplary of the principles of the invention and not intended to limit the invention to the specific embodiments shown and described.

[0061] In the following, for the sake of understanding, elements of embodiments are described in operation. However, it will be apparent that the respective elements are arranged to perform the functions being described as performed by them.

[0062] Further, the invention is not limited to the embodiments, and the invention lies in each and every novel feature or combination of features described herein or recited in mutually different dependent claims.

[0063] FIG. 1 schematically shows an example of an embodiment of a computation device 100. The computation device is arranged for the obfuscated execution of a multiplication. The multiplication is executed on a representation using multiple shares so that it is hard for an attacker to analyze the multiplication. In particular, it is hard to analyze the multiplication from a side channel. For example, the computation device is particularly suitable for operations that operate on secret information, which should be protected from attack. For example, the device is suitable for cryptographic operations, especially cryptographic operations which use secret information, such as a secret key. Particular examples of such a cryptographic operation are RSA decryption operation, RSA signature operation, and Diffie-Hellman key agreement. These operations comprise an exponentiation which uses a secret input; in this case a secret exponent.

[0064] The inventors have realized that a particular representation of the variables involved in the multiplication is particularly advantageous. The representation combines two different types of obfuscated representation to achieve additional advantages. In particular, the representation allows efficient computation of multiplications and of conditional assignments. More in particular, the representation does not require the re-encoding of variables from one representation to another, or the computation of compensating data to correct the effect of operating on obfuscated representation, rather than on a regular representation.

[0065] In general, the computations indicated herein will be modulo some modulus, e.g., depending on the variables being modulo some number, e.g., as is required in RSA exponentiation operations. For example, modulo operations may be inserted at suitable points to avoid number becoming too large, e.g., after each multiplication, etc. It is not necessary that each integer is kept below the modulus at all times. For example, an embodiment may employ so-called pseudo-residues which are only occasionally reduced modulo the modulus. The modulus may, e.g., be a prime number p, or a composite number, e.g., a product of two primes pq.

[0066] Computation device 100 comprises storage 120 which comprises variables on which computation device 100 operates in encoded form. A number x, e.g., an integer, e.g., an integer modulo a modulus is initially represented as multiple multiplicative shares X=(x.sub.0,x.sub.1, . . . ,x.sub.m1). That is the product of the numbers x.sub.i equals the number x being represented. We will denote sequence of multiple numbers, e.g., tuples, with capital letters, and particular numbers with small case letters. We will refer to the number x.sub.i as multiplicative shares. Note that the multiplicative shares will typically not be stored in storage 120, and in fact will typically not be present at all in storage 120possibly with some temporary exceptions, e.g., during encoding or decoding of a variable to or from the special representation herein defined. In other words, in an embodiment, an attacker performing, say, a memory scraping attack on device 100, in which the memory is combed to find variables relating to the operation, will not find the multiplicative shares themselves. Instead, the multiplicative shares are represented themselves as additive shares. For example, the multiplicative share x.sub.i may be represented in storage 120, e.g., in a memory of device 100, as multiple additive shares, e.g., as a tuple X.sub.i=(x.sub.i,0,x.sub.i,1, . . . , x.sub.i,n1). Assuming that a number is represented using m multiplicative shares, which are each represented as n additive shares, the number may thus be represented as nm shares. Representation as shares is desirable since even perfect knowledge of any number of the shares, except all shares, does not reveal any information about the underlying number.

[0067] FIG. 2 schematically shows an example of an embodiment of a representation of a variable 2. For example, assume the number 2 is the number 94 modulo the prime 113. This number is first represented as multiple multiplicative shares 20. FIG. 2 shows the multiplicative shares 21 and 22, but there may be more. For example, the multiplicative shares may be the numbers: 55, 40, and 70, since their product modulo 113 is 94. Generating a multiplicative representation of an integer can be done by generating m1 random non-zero numbers, e.g., modulo the modulus, and computing the final one so that the product of all multiplicative shares equals the number being represented, e.g., number 2. Note that none of the multiplicative shares 20, are present as such in storage 120. Each of the multiplicative shares is further represented using additive shares. FIG. 2 shows that multiplicative share 21 is represented with multiple additive shares 210, e.g., as at least three additive shares: 211, 212 and 213; and multiplicative share 22 is represented as multiple additive shares 210, e.g., as at least three additive shares: 221, 222 and 223. There may be 2 or more than 3 additive shares. In general, numbers which are to be multiplied with each other are represented using an equal number of multiplicative and an equal number of additive shares. The number of additive shares per multiplicative share might differ though. For example, in an embodiment, a first multiplicative share is represented with a first number of additive shares, and a second multiplicative share is represented with a second number of additive shares. The first and second number are preferably larger than 1. Typically, the first and second number are equal but this is not necessary as they may be unequal. In an embodiment, the additive shares, e.g., additive shares 210 and 220, may be stored in storage 120.

[0068] For example, the numbers: 55, 40, and 70 may be represented as the tuples (78, 105, 98), (34, 40, 79), (12, 81, 90), since their sums are 55, 40, and 70 respectively modulo 113. In an embodiment, the number 94 modulo 113 may thus be represented as the sequence 78, 105, 98, 34, 40, 79, 12, 81, 90. Further obfuscation techniques may be further applied to this sequence. For example, the sequence need not be stored in this particular order, but may be permuted or scattered throughout storage 120. For example, the additive shares may be encoded.

[0069] Returning to FIG. 1. Computation device 100 may comprise a communication interface 110. For example, the communication interface 110 may be arranged to obtain at least one of the variables in storage 120, or at least an initial value thereof. For example, the communication interface 110 may be arranged to receive an encrypted message, e.g., encrypted with RSA, or for receiving a message for signing, e.g., with RSA signing. For example, RSA decryption or signing as defined in RFC 3447 may be used. For example, the communication interface 110 may be arranged to receive a public key for us in a Diffie-Hellman protocol, e.g., as defined in RFC 2631. In each of these three examples, an exponentiation is performed with an exponent that (at least in part) is secret.

[0070] The communication interface 110 may be arranged to communicate with other devices over a computer network. The computer network may be an internet, an intranet, a LAN, a WLAN, etc. The computer network may be the Internet. The computer network may be wholly or partly wired, and/or wholly or partly wireless. For example, the computer network may comprise Ethernet connections. For example, the computer network may comprise wireless connections, such as Wi-Fi, ZigBee, and the like. The connection interface may be arranged to communicate with other devices as needed. For example, the connection interface may comprise a connector, e.g., a wired connector, e.g., an Ethernet connector, or a wireless connector, e.g., an antenna, e.g., a Wi-Fi, 4G or 5G antenna. Communication interface 110 may be used to receive transactions to operate upon, or for receiving secret information, e.g., secret keys. Messages may be digital messages, e.g., received in electronic form.

[0071] Computation device 100 may comprise various units, e.g., one or more of a convolution unit 132, an addition unit 134, a multiplication unit 142, a conditional assignment unit 144, and an exponentiation unit 150. If, e.g., exponentiation is not needed, then exponentiation unit 150 may be omitted, etc. If no conditional assignment is needed, then, addition unit 134 and conditional assignment unit 144 may be omitted, etc.

[0072] The execution of the computation device, e.g., of an embodiment of a computation method may be implemented in one or more processor circuits, examples of which are shown herein. FIG. 1 shows functional units that may be functional units of the processor circuit. For example, FIG. 1 may be used as a blueprint of a possible functional organization of the processor circuit. The processor circuit is not shown separate from the units in FIG. 1. For example, the functional units shown in FIG. 1 may be wholly or partially implemented in computer instructions that are stored at device 100, e.g., in an electronic memory of device 100, and are executable by a microprocessor of device 100. In hybrid embodiments, functional units are implemented partially in hardware, e.g., as coprocessors, e.g., arithmetic coprocessors, and partially in software stored and executed on device 100.

[0073] The inventors had the insight that numbers represented as indicated above can be multiplied using convolutions. To this end, one or more convolution units 132 are arranged to convolute two sets of multiple additive shares, e.g., that together represent one multiplicative share.

[0074] Multiplicative unit 142 may be arranged to multiply a first variable in the storage with a second variable in the storage. For example, the first variable may be the number x represented as multiple multiplicative shares X=(x.sub.0,x.sub.1, . . . , x.sub.m1), which in turn are represented in the storage as multiple additive shares X.sub.i=(x.sub.i,0,x.sub.i,1, . . . , x.sub.i,n1), with 0x<m. For example, the second variable may be the number y represented as multiple multiplicative shares Y=(y.sub.0,y.sub.1, . . . , y.sub.m1), said multiplicative shares being represented in the storage as multiple additive shares Y.sub.i=(y.sub.i,o,y.sub.i,1, . . . , y.sub.i,n), with 0i<m.

[0075] To obtain a multiplication result z=xy, represented as above, the multiplying unit 142 is configured to [0076] for each multiplicative share of the first variable, [0077] computing a convolution (Z.sub.i=X.sub.i*Y.sub.i) of the additive shares representing said multiplicative share of the first variable (X.sub.i) and the additive shares representing the corresponding multiplicative shares of the second variable (Y.sub.i), [0078] storing the resulting multiple additive shares (z.sub.i) in the storage as a representation in additive shares of a multiplicative share of the multiplication result (z). In other words, each multiple of additive shares X.sub.i corresponds to a multiple of additive shares Y.sub.i. Corresponding multiples of additive shares are convoluted to obtain a representation of the multiplication result. In other words, one may regard the variable z to be represented as multiple multiplicative shares Z=(z.sub.0,z.sub.1, . . . , z.sub.m1), which in turn are represented in the storage as multiple additive shares Z.sub.i=(z.sub.i,0,z.sub.i,1, . . . , z.sub.i,n1), with 0i<m.
Further details of multiplying by convolution are given below.

[0079] FIG. 3a schematically shows an example of an embodiment of a multiplication. Shown in FIG. 3a are two numbers. The first is represented by multiple multiplicative shares 30. The second by multiple multiplicative shares 40. Each multiplicative share is represented by a set of additive shares. In FIG. 3a, each of the references 31-33, and 41-43 denotes a set of additive shares. In this case 3 multiplicative shares are shown, but two or more than 3 is also possible. The number of shares in the additive sets is not shown, but this could be two or more.

[0080] FIG. 3a also shows a convolution unit 350. At the moment shown in FIG. 3a, convolution unit 350 performs a convolution between an additive set of the first number, e.g., set 31, and an additive set of the second number, e.g., set 41. After this convolution, convolution unit 350 may perform a convolution between sets 32 and 42. There is no reason that a share in a first set of additive shares needs to correspond to the share in a second set of additive shares which has the same index, so long the correspondence relation forms a bijection between the shares. For example, convolution unit 350 may also convolute 31 with 42, 32 with 43 and 33 with 41, etc. The convolutions can well be parallelized, e.g., 31 may be convoluted with 41, at the same time that 32 is convoluted with 42, etc.

[0081] Returning to FIG. 1. In an embodiment, computation device 100 may comprise a conditional assignment unit 144. In addition to the convolution unit 132, the conditional assignment unit 144 in this embodiment also uses an addition unit 134. Addition unit 134 is configured to add two sets of additive shares, for example, by adding corresponding elements to each other. By adding two additive sets, one obtains an additive representation of the sum. In case only one multiplicative share is used, then addition unit 134 may be used to add two variables in general. In case more than one multiplicative share is used, more care is needed. However, if needed a so-called circuit may be used to add numbers having multiple multiplicative shares.

[0082] Conditional assignment unit 144 takes input two variables, say, a first variable x and a second variable y, and a binary condition d. One may take for d a regular binary variable having the values 0 or 1. The operations which depend on d could be integrated with the computer program code which computed the condition d. Furthermore, the variable d could be obfuscated, e.g., encoded. Conditional assignment unit 144 either assigns the first variable to its output, e.g., to a third variable z, or assigns the second variable to its output, depending on the condition d. In an embodiment, the conditional assignment unit 144 uses two selection numbers to do this, e.g., R and R. The selection numbers may be constants and may be stored in storage 120, or may be hardcoded in the unit 144, etc. The selection numbers are represented as a set of additive shares. A representation using multiplicative shares as well as additive shares is possible for the selection numbers, but it is not needed. However, using multiple multiplicative shares for the selection numbers may require an addition circuit, which is preferably avoided. The conditional assignment unit is configured to [0083] for each multiplicative share of the first variable, [0084] computing a first convolution R*X.sub.i of a first selection number R and the additive shares representing the multiplicative share of the first variable X.sub.i, [0085] computing a second convolution R*Y.sub.i of a second selection number R and the additive shares representing the corresponding multiplicative share of the second variable Y.sub.i, [0086] adding the results of the first and second convolution Z.sub.i=R*X.sub.i+R*Y.sub.i, and storing the resulting multiple additive shares Z.sub.i in the storage as a representation in additive shares of a multiplicative share of the assignment result z.

[0087] Which selection numbers are used, depends on the conditional d. For example, if storage 120 stores two selection numbers R.sub.1 and R.sub.2, then the unit 144 may set R=R.sub.1, R=R.sub.2 if d is true, e.g., d=1, and R=R.sub.2, R=R.sub.1 if d is false, e.g., d=0. In an embodiment, the selection numbers are additive representations of either 0 or 1. For example, one of the selection numbers may be an additive representation of 0 or 1, while the other selection number represents the other of 0 and 1.

[0088] FIG. 3b schematically shows an example of an embodiment of a conditional assignment unit 144. Shown are two numbers represented as multiple multiplicative shares 30 and 40. Each multiplicative share is represented by a set of additive shares. In FIG. 3b each of the references 31-33, 41-43 represents a set of additive shares. Two selection numbers are shown, represented by additive share sets 51 and 52. A first convolution unit 351 is shown convolution set 31 with selection number 51. A second convolution unit 352 is shown convoluting set 41 with selection number 52. The result of units 351 and 352 are added by addition unit 353. The result is one element of the assignment result. After this iteration, sets 32 and 51, sets 42 and 52 are convoluted and the results added.

[0089] It is not needed that each iteration uses the same selection numbers, different numbers may be used instead. In particular, different representations that represent the same value, for example, the value 0 may be used in each iteration, but represented each time, or some time as with a different representation. It is also not needed that the computations are performed in the order indicated herein. Both the multiplication and assignment are highly parallel. This may be exploited in embodiments by permuting the order of the calculations, e.g., depending on a random variable, as a further obfuscation step. Randomization helps against averaging attacks. Note that the selection numbers could be generated randomly before an operation, before an assignment, or even before each or some iterations.

[0090] Both multiplication and assignment may be further obfuscated by adding dummy operations. For example, a suitable dummy operation is to do a multiplication with a representation of the number 1. For example, a suitable dummy operation is to add an additive representation of the number 0, to one or more additive share sets. Including one or more dummy operations will randomize the timing between iterations, and/or between different calls of the operation. Especially, if the dummy operations are inserted in dependence on a random process, e.g., a call to a random number generator. Randomized timing thwarts averaging attacks, moreover if the dummy operations are alike to regular operations as above, re-syncing by the attacker is hard.

[0091] Note that the obfuscated multiplication, e.g., using multiplication unit 142 and the obfuscated assignment, e.g., using assignment unit 144, can operate on numbers in the same representation. No re-encoding to move from the unit 142 to 144 or vice versa is needed. This means that these operations can be stringed together with ease. For example, in an embodiment, an operation, e.g., a cryptographic operation comprises a conditional assignment followed by a multiplication with the conditional assignment result. For example, in an embodiment, an operation, e.g., a cryptographic operation comprises conditional assignment followed by a multiplication with the assignment result. In an embodiment, an exponentiation comprises repeated obfuscated multiplications.

[0092] An even better obfuscated exponentiation can be obtained by also using obfuscated assignments. For example, exponentiation operations can be effectively performed using multiplication and conditional assignments. For example, the exponentiation may comprise repeated multiplications, wherein the multiplications depend on bits in an exponent. A conditional assignment is executed in dependency on the bits in the exponent followed by a multiplication. For example, to effectively perform the exponentiation, a so-called Montgomery ladder may be used.

[0093] The Montgomery ladder may be implemented according to:

TABLE-US-00001 s 1 t h For i = 1 to 0 do u (1d.sub.i)s + d.sub.it mod N (I) s su mod N (II) t tu mod N (II) End for,

[0094] wherein h represents the base of the exponentiation, and the bits d.sub.i represent bits of the exponent, the conditinoal assignments (I) and the multiplications (II) being obfuscated as in an embodiment. Note that an exponentiation algorithm that uses an obfuscated assignment, and includes an equal number of multiplications in each iteration has increased resistance against side channel attacks, since it is hard to determine the exponent from either the assignment, nor from the multiplications. The above Montgomery ladder has this property since both the assignment and the multiplications are protected by shares. Furthermore, the multiplications are independent from the secret exponent bits.

[0095] If the number of multiplicative shares, and/or the number of additive shares is large then the exponentiation, which is already an expensive operation can become quite expensive indeed. This can be avoided by performing a protected exponentiation with a smaller protected exponent, and a regular exponentiation with an unprotected exponent. The protected exponent, and the unprotected exponent can be chosen such that their combined result equals exponentiation with the intended exponent, in case of RSA, with the secret exponent, e.g., the secret key. For example, in an embodiment, the exponentiation unit 150 may be configured to perform an exponentiation by obtaining a first exponent and a second exponent, a first exponent having fewer bits than the second exponent, said subsequent exponentiation by the first and second exponent being equal to exponentiation by the exponent, wherein the exponentiation with the first exponent comprises obfuscated multiplication and/or conditional assignments. For example, the first and second exponents may be chosen during key generation, and stored in device 100, e.g., in storage 120.

[0096] In the various embodiments of device 100, the communication interface may be selected from various alternatives. For example, the interface may be a network interface to a local or wide area network, e.g., the Internet, a storage interface to an internal or external data storage, a keyboard, an application interface (API), etc.

[0097] The device 100 may have a user interface, which may include well-known elements such as one or more buttons, a keyboard, display, touch screen, etc. The user interface may be arranged for accommodating user interaction for performing a computation, e.g., a cryptographic operation, e.g., a decrypt or sign operation.

[0098] Storage 120 may be implemented as an electronic memory, say a flash memory, or magnetic memory, say hard disk or the like. Storage 120 may comprise multiple discrete memories together making up storage 110. Storage 120 may also be a temporary memory, say a RAM. In the case of a temporary storage 120, storage 120 contains some means to obtain data before use, say by obtaining them over an optional network connection (not shown).

[0099] Typically, the device 100 comprises a microprocessor (not separately shown) which executes appropriate software stored at the device 100; for example, that software may have been downloaded and/or stored in a corresponding memory, e.g., a volatile memory such as RAM or a non-volatile memory such as Flash (not separately shown). Alternatively, the device 100 may, in whole or in part, be implemented in programmable logic, e.g., as field-programmable gate array (FPGA). Device 100 may be implemented, in whole or in part, as a so-called application-specific integrated circuit (ASIC), i.e. an integrated circuit (IC) customized for their particular use. For example, the circuits may be implemented in CMOS, e.g., using a hardware description language such as Verilog, VHDL etc.

[0100] In an embodiment, the computation device comprises one, or more, or all of a convolution circuit, an addition circuit, a multiplication circuit, a conditional assignment circuit, an exponentiation circuit, a communication interface circuit. The circuits implement the corresponding units described herein. The circuits may be a processor circuit and storage circuit, the processor circuit executing instructions represented electronically in the storage circuits.

[0101] A processor circuit may be implemented in a distributed fashion, e.g., as multiple sub-processor circuits. A storage may be distributed over multiple distributed sub-storages. Part or all of the memory may be an electronic memory, magnetic memory, etc. For example, the storage may have volatile and a non-volatile part. Part of the storage may be read-only.

[0102] Thus, a device and method are disclosed to perform modular exponentiation with a secret exponent with increased resistance against leaking the exponent through a side channel. Embodiments combine, e.g., a Montgomery ladder, multiplicative sharing and additive sharing. Applications include the RSA algorithm, and the DiffieHellman algorithm in Z*.sub.p. In the RSA application, the secret exponent typically is large, e.g., 2048 of 4096 bits. An optimization is shown to reduce the size of the exponent used which greatly speeds up the calculations. Below these and further embodiments are discussed, in a more mathematical language.

1 Terminology and Notation

[0103] If a number x=.sub.i=0.sup.n1x.sub.i, then the n numbers x.sub.0, x.sub.1, K, x.sub.n1 are an additive n-share representation of x. Notation: x=A(x.sub.0, x.sub.1, K, x.sub.n1). If a number x=.sub.i=0.sup.m1x.sub.i, then the m numbers x.sub.0, x.sub.1, K, x.sub.m1 are a multiplicative m-share representation of x. Notation:

x=M(x.sub.0, x.sub.1, K, x.sub.m1).

[0104] If x=A(x.sub.0, K, x.sub.n1) and y=A(y.sub.0, y.sub.1, K, y.sub.n1), then the per-share addition gives an additive n-share representation of the sum x+y:

A(x.sub.0+y.sub.0, x.sub.1+y.sub.1, K, x.sub.n1+y.sub.n1)=x+y. If x=M(x.sub.0, K, x.sub.m1) and y=M(y.sub.0, y.sub.1, K, y.sub.m1), then the per-share multiplication gives a multiplicative m-share representation of the product xy: M(x.sub.0y.sub.0, x.sub.1y.sub.1, K, x.sub.n1, y.sub.n1)=xy.

[0105] Let X=(x.sub.0, K, x.sub.n1) and Y=(y.sub.0, K, y.sub.n1) be two n-tuples of numbers, then the convolution of X and Y, denoted X*Y, is defined as the n-tuple Z=(z.sub.0, K, z.sub.n1) where

[00002]$z_i=\underset{j=0}{\overset{n-1}{.Math.}}.Math.x_j.Math.y_{\left(i-j\right).Math.\mathrm{modn}},$

for 0in1. Example for n=3: if X =(x.sub.0, x.sub.1, x.sub.2) and Y=(y.sub.0, y.sub.1, y.sub.2), then X*Y=(x.sub.0y.sub.0+x.sub.1y.sub.2+x.sub.2y.sub.1, x.sub.0y.sub.1+x.sub.1y.sub.0+x.sub.2y.sub.2, x.sub.0y.sub.2+x.sub.1y.sub.1+x.sub.2y.sub.0).

[0106] It holds for all X and Y that A(X*Y)=A(X)A(Y). In other words: the convolution of two additive share representations results in an additive share representation of the product. Let x=M(x.sub.0, K, x.sub.m1) and y=M(y.sub.0, K, y.sub.m1).

[0107] It would be advantageous if there existed a linear operation which plays an analogous role for multiplicative share representations: such a hypothetical operation of two multiplicative share representations would result in a multiplicative share representation of the sum, i.e., for all X and Y, the operation, denoted XY , would satisfy M(XY)=M(X)+M(Y). It turns out, that is can be proven through mathematical argument, that such a hypothetical operation cannot exist in general. Nevertheless, even though it is not possible to create multiplicative shares of an arbitrary weighted sum (1)x+y from the multiplicative shares of x and y by taking linear combinations, it is possible when =0 or =1: z.sub.i=(1)x.sub.i+y.sub.i for 0im1 satisfies

M(z.sub.0, K, z.sub.m1)=(1)M(x.sub.0, K, x.sub.m1)+M(y.sub.0, K, y.sub.m1)when {0,1}.

[0108] Note that each share of x and y is multiplied by either zero or one. This can be camouflaged, e.g., in the following way. [0109] 1. Construct a number (K1) of additive share sets O.sub.0, O.sub.1, K, O.sub.K1 that represent 0, i.e.,

O.sub.1=(o.sub.i,0, K, o.sub.i,n1) with A(o.sub.i,0, K, o.sub.i,n1)=0for0iK1. [0110] 2. Construct a number (K1) of additive share sets J.sub.0, J.sub.1, K, J.sub.K1 that represent 1, i.e.,

J.sub.i=(j.sub.i,0, K, j.sub.i,n1) with A(j.sub.i,0, K, j.sub.i,n1)=1for0iK1. [0111] 3. Represent each multiplicative share x.sub.i of x by an additive share set X.sub.i=(x.sub.i,0, K, x.sub.i,n1), such that

x.sub.i=A(x.sub.i,0, K, x.sub.i,n1). [0112] 4. Represent each multiplicative share y.sub.i of y by an additive share set Y.sub.i=(y.sub.i,0, K, y.sub.i,n1), such that

y.sub.i=A(y.sub.i,0, K, y.sub.i,n1). [0113] 5. If =0 , calculate an additive share set Z.sub.i of the multiplicative share z.sub.i of z as

Z.sub.i=J.sub.k.sub.i*X.sub.i+O.sub.l.sub.i*Y.sub.i,

where k.sub.i and l.sub.i are arbitrarily chosen integers satisfying 0k.sub.i, l.sub.iK1.

[0114] If =1, Z.sub.i is calculated as

Z.sub.i=O.sub.k.sub.i*X.sub.i+J.sub.l.sub.i*Y.sub.i.

[0115] The two cases can be summarized in the single equation

Z.sub.i=R(1d.sub.i).sub.k.sub.i*X.sub.i+R(d.sub.i).sub.l.sub.i*Y.sub.i,

where R(0) stands for O and R(1) stands for J.

2 Exponentiation Using a Montgomery Ladder

[0116] In RSA and in the Diffie-Hellman protocol it is often required to perform a modular exponentiation of a public number h and a secret exponent d modulo a public modulus N:

s=h.sup.d mod N.

[0117] For example, In RSA signing, we may have: h is the padded message digest, d is the private key and s is the resulting signature. Let denote the bit-length of N (and d), and write the binary expansion of d as d=.sub.i=0.sup.1d.sub.i2.sup.i, with d.sub.i {0,1}. A simple algorithm for calculating s is the following:

TABLE-US-00002 Straightforward exponentiation s 1 for i = 1 to 0 do s s.sup.2 mod N if d.sub.i = 1 then s sh mod N end if end for

[0118] This algorithm is side-channel sensitive, because the pattern of squarings and multiplications reveals the exponent d. This holds also when the if-statement is unrolled for a given d.

[0119] The Montgomery ladder calculates s in the following way:

TABLE-US-00003 Montgomery ladder s 1 t h for i = 1 to 0 do if d.sub.i = 0 then a s.sup.2 mod N b st mod N else a st mod N b t.sup.2 mod N end if s a t b end for

[0120] The Montgomery ladder offers some protection against side-channel attacks, because in each step both a squaring and a multiplication occur. However, any side channel that allows the attacker to observe whether s or t is squared in each step, still reveals the key.

[0121] The same results are obtained with the following variant of the Montgomery ladder:

TABLE-US-00004 Montgomery ladder, variation s 1 t h for i = 1 to 0 do u (1d.sub.i)s + d.sub.it mod N s su mod N t tu mod N end for

[0122] This variant of the Montgomery ladder uses multiplications and an addition, but no squarings. A side channel that allows an attacker to observe in each step whether s is multiplied by zero or by one, or, equivalently, whether u=s or u=t, leaks the key.

[0123] In order to make it even harder for an attacker to obtain the key from a side-channel attack, we the obfuscation techniques from the first section may be used to make it harder to see whether u=s or u=t, or whether something is multiplied by zero or by one.

[0124] The implementer chooses numbers m1 (number of multiplicative shares representing a Montgomery ladder variable) and n2 (number of additive shares of a multiplicative share). A Montgomery ladder variable is thus represented by mn shares. Preferably both m and n are large.

[0125] The implementer chooses a set of numbers {A.sub.,v}.sub.=0,v=0.sup.m1,n1 and {B.sub.,v}.sub.=0,v=0.sup.m1,n1 such that

[00003]$\underset{=0}{\overset{m-1}{.Math.}}.Math.\left(\underset{v=0}{\overset{n-1}{.Math.}}.Math.A_{,v}\right).Math.\mathrm{mod}.Math..Math.N=1.Math..Math.\mathrm{and}$$\underset{=0}{\overset{m-1}{.Math.}}.Math.\left(\underset{v=0}{\overset{n-1}{.Math.}}.Math.B_{,v}\right).Math.\mathrm{mod}.Math..Math.N=h,$

to initialize the ladder. The ladder works with mn numbers S.sub.,v, T.sub.,v and U.sub.,nu, the n shares (S.sub.,0, K, S.sub.,n1) are denoted S.sub., and similarly for the T and U shares. The numbers k.sub.i, and l.sub.i,, with 0i1 and 0m1 may be arbitrarily chosen integers from [0,K).

[0126] Protected Montgomery ladder with multiplicative and additive shares

TABLE-US-00005 for = 0 to m1 do for v = 0 to n1 do S.sub.,v A.sub.,v T.sub.,v B.sub.,v end for end for for i = 1 to 0 do for = 0 to m1 do U.sub. R(1d.sub.i).sub.k.sub.i,*S.sub. + R(d.sub.i).sub.l.sub.i,*T.sub. mod N end for for = 0 to m1 do S.sub. S.sub.*U.sub. mod N T.sub. T.sub.*U.sub. mod N end for end for s .sub.=0.sup.m1(.sub.v=0.sup.n1S.sub.,v ) mod N

[0127] In an embodiment, the dummy transformations may be performed on the shares that leave the underlying value invariant, e.g., he may choose to apply a random permutation of the n additive shares, or a random permutation of the m multiplicative shares (represented by additive share sets). Preferably, these transformations are chosen during run time, not at compile time. For example, they may be chosen dependent upon the input h. For example, the input h may be used to seed a random number generator.

[0128] In some applications, e.g., signing it is primarily the exponent in an exponentiation which is secret, but neither the input nor the output of the algorithms is confidential. In such a case, intermediate results may still be sensitive since they rely on only part of the key, and may thus allow brute forcing of part of the key.

[0129] To mask an input variable h as multiple shares one may first compute multiplicative shares, and then represent each of the multiplicative shares as additive shares. For example, in an embodiment, the variable h is used as a seed to a random number generator which in turn generates all multiplicative or additives shares but one, after which the final shares are computed. Alternatively, a set of random multiplicative functions .sub.i or additive functions g.sub.i may be selected at compile time. The functions satisfy that .sub.i(x)=x and g.sub.i(x)=x, in both cases modulo the public modulus. Thus the product or sum of these functions is independent of the input, at least modulo the modulus. The number of functions is equal to the number of multiplicative shares or additive shares per multiplicative share. If there is only one multiplicative share, the multiplicative functions may be omitted. To represent any variable as shares, e.g., the variable h, one may first compute (.sub.0(h), .sub.1(h), . . . , .sub.m1(h)). To represent a multiplicative share s, one may compute (y.sub.0(s), . . . , y.sub.n1(s)).

[0130] One may also use this approach in part. For example, the multiplicative shares may be computed on the fly at runtime, e.g., using a random number generator, computing the final share using an inverse algorithm. Each of the multiplicative shares is then mapped to a set of multiple additive shares using a set of additive functions. Note that the additive functions may be different for some or each of the set of additive shares. For example, at compile time all the additive functions but one may be chosen as random polynomials, after which the final polynomial can be computed.

[0131] For example, to generate shares one may do the following. Suppose we wish to represent (l) on input I, then let r.sub.i(I) be functions providing random shares on input I for i=1 . . . n1 and let r.sub.n(I) be defined as (I)r.sub.1(I) . . . r.sub.n1(I). Now x.sub.i=r.sub.i(I) gives an additive n-sharing of (I). Similarly let R.sub.i(I) be functions providing random shares on input I for i=1 . . . n1 and let R.sub.n(I) be defined as (I)/(R.sub.0(I)* . . . *R.sub.n1(I)), then X.sub.i=R.sub.i(I) gives an n-multiplicative sharing of f(I). The functions r and R may be pseudo random functions.

[0132] The Montgomery ladder with mn multiplicative and additive shares takes approximately mn times as many operations as the Montgomery ladder without shares. This may be a high price to pay for the extra side-channel security. The following method may reduce the number of operations significantly, without compromising on security. Consider the following: [0133] 1. An attacker who can factor N can find the private key d without much additional effort. The best currently known method for factoring N, using the number field sieve, takes asymptotically

[00004]$\exp \left(\left(\sqrt[3]{\frac{6.Math.4}{9}}+o\left(1\right)\right).Math.{\left(\ln \left(N\right)\right)}^{1.Math.\text{/}.Math.3}.Math.{\left(\ln \left(\ln \left(N\right)\right)\right)}^{2.Math.\text{/}.Math.3}\right)$

operations. For N2.sup.2048 this translates to roughly 112 bits of security, for N2.sup.4096 about 150 bits. [0134] 2. Finding d from s , h and N amounts to solving a discrete logarithm problem, for which the best solution methods take asymptotically O({square root over (N)}) operations. This is much more expensive than factoring N. [0135] 3. If it is known that the exponent in the discrete logarithm problem is small, say t bits, a brute-force attack takes O(2.sup.t) operations. As long as t is larger than the security level of RSA, factorization of N is the best attack on d.

[0136] The secret exponent d may split in a secret part and a public part. For example, choose a random t-bit number d.sub.s, the secret part of d, and calculate d.sub.p=d.sub.s.sup.1d mod(N), the -bit public part of d. This uses the Euler function (N) of the modulus N, e.g., obtained from a factorization of N. Here, is the Euler function

[0137] The exponentiation is done in two steps:

s=h.sup.d mod N=h.sup.d.sup.s.sup.d.sup.p mod N=(h.sup.d.sup.s mod N).sup.d.sup.p P mod N.

[0138] The inner modular exponentiation with exponent d.sub.s is done using mn multiplicative and additive shares using the protected Montgomery ladder above, the outer modular exponentiation with exponent d.sub.p is done using a less secure Montgomery ladder. The exponent d.sub.p is likely to leak through a side channel, but that does not matter as long as d.sub.s does not leak. Note that since

(h.sup.d.sup.s mod N).sup.d.sup.p mod N(h.sup.d.sup.p mod N).sup.d.sup.s mod N,

[0139] the inner and outer modular exponentiations can be swapped.

[0140] The total workload for this method is +tmn, compared to mn for the protected method above: a considerable improvement when mn>1 since t is much smaller than . For example, in an embodiment, t is less than . For example, 10 t is less than . For example, t may be less than 256, while is larger than 2048.

[0141] Splitting the secret exponent into a secret part and a public part can be done at the same time key generation is done. These parts of the exponent can be stored in a storage, e.g., a memory of the computation device.

[0142] FIG. 4 schematically shows an example of an embodiment of a computation method 400. Computation method 400 is arranged for the obfuscated execution of a multiplication, Method 400 comprises [0143] storing 410 multiple variables used in the execution of an arithmetic operation, a variable (x; y; 2) of the multiple variables being represented as multiple multiplicative shares (X=(x.sub.0, x.sub.1, . . . , x.sub.m1); Y=(y.sub.0, y.sub.1, . . . , y.sub.m1); 20), said multiplicative shares being represented in the storage as multiple additive shares (X.sub.i=(x.sub.i,0, x.sub.i,1, . . . , x.sub.i,n1); Y.sub.i=(y.sub.i,0, y.sub.i,1, . . . , y.sub.i,n1); 210, 220), and [0144] multiplying (420) a first variable in the storage with a second variable in the storage to obtain a multiplication result (z=xy).

[0145] The multiplying comprises [0146] for each multiplicative share of the first variable, [0147] computing 430 a convolution (Z.sub.i=X.sub.i*Y.sub.i) of the additive shares representing said multiplicative share of the first variable (X.sub.i) and the additive shares representing the corresponding multiplicative shares of the second variable (Y.sub.i), [0148] storing 440 the resulting multiple additive shares (Z.sub.i) in the storage as a representation in additive shares of a multiplicative share of the multiplication result (z). Thus operations 430 and 440 are repeated, e.g., iterated as often as necessary, e.g., as often as in the representation of the numbers in the storage.

[0149] Many different ways of executing the method are possible, as will be apparent to a person skilled in the art. For example, the order of the steps can be varied or some steps may be executed in parallel. Moreover, in between steps other method steps may be inserted. The inserted steps may represent refinements of the method such as described herein, or may be unrelated to the method. For example, operations 430 and 440 may be executed, at least partially, in parallel. Moreover, a given step may not have finished completely before a next step is started.

[0150] A method according to the invention may be executed using software, which comprises instructions for causing a processor system to perform method 400. Software may only include those steps taken by a particular sub-entity of the system. The software may be stored in a suitable storage medium, such as a hard disk, a floppy, a memory, an optical disc, etc. The software may be sent as a signal along a wire, or wireless, or using a data network, e.g., the Internet. The software may be made available for download and/or for remote usage on a server. A method according to the invention may be executed using a bitstream arranged to configure programmable logic, e.g., a field-programmable gate array (FPGA), to perform the method.

[0151] It will be appreciated that the invention also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the invention into practice. The program may be in the form of source code, object code, a code intermediate source, and object code such as partially compiled form, or in any other form suitable for use in the implementation of the method according to the invention. An embodiment relating to a computer program product comprises computer executable instructions corresponding to each of the processing steps of at least one of the methods set forth. These instructions may be subdivided into subroutines and/or be stored in one or more files that may be linked statically or dynamically. Another embodiment relating to a computer program product comprises computer executable instructions corresponding to each of the means of at least one of the systems and/or products set forth.

[0152] FIG. 5a shows a computer readable medium 1000 having a writable part 1010 comprising a computer program 1020, the computer program 1020 comprising instructions for causing a processor system to perform a computation method, according to an embodiment. The computer program 1020 may be embodied on the computer readable medium 1000 as physical marks or by means of magnetization of the computer readable medium 1000. However, any other suitable embodiment is conceivable as well. Furthermore, it will be appreciated that, although the computer readable medium 1000 is shown here as an optical disc, the computer readable medium 1000 may be any suitable computer readable medium, such as a hard disk, solid state memory, flash memory, etc., and may be non-recordable or recordable. The computer program 1020 comprises instructions for causing a processor system to perform said computation method.

[0153] FIG. 5b shows in a schematic representation of a processor system 1140 according to an embodiment of a computation device. The processor system comprises one or more integrated circuits 1110. The architecture of the one or more integrated circuits 1110 is schematically shown in FIG. 5b. Circuit 1110 comprises a processing unit 1120, e.g., a CPU, for running computer program components to execute a method according to an embodiment and/or implement its modules or units. Circuit 1110 comprises a memory 1122 for storing programming code, data, etc. Part of memory 1122 may be read-only. Circuit 1110 may comprise a communication element 1126, e.g., an antenna, connectors or both, and the like. Circuit 1110 may comprise a dedicated integrated circuit 1124 for performing part or all of the processing defined in the method. Processor 1120, memory 1122, dedicated IC 1124 and communication element 1126 may be connected to each other via an interconnect 1130, say a bus. The processor system 1110 may be arranged for contact and/or contact-less communication, using an antenna and/or connectors, respectively.

[0154] For example, in an embodiment, the computation device may comprise a processor circuit and a memory circuit, the processor being arranged to execute software stored in the memory circuit. For example, the processor circuit may be an Intel Core i7 processor, ARM Cortex-R8, etc. In an embodiment, the processor circuit may be ARM Cortex M0. The memory circuit may be an ROM circuit, or a non-volatile memory, e.g., a flash memory. The memory circuit may be a volatile memory, e.g., an SRAM memory. In the latter case, the device may comprise a non-volatile software interface, e.g., a hard drive, a network interface, etc., arranged for providing the software.

[0155] It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments.

[0156] In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. Use of the verb comprise and its conjugations does not exclude the presence of elements or steps other than those stated in a claim. The article a or an preceding an element does not exclude the presence of a plurality of such elements. The invention may be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In the device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

[0157] In the claims references in parentheses refer to reference signs in drawings of exemplifying embodiments or to formulas of embodiments, thus increasing the intelligibility of the claim. These references shall not be construed as limiting the claim.