Method for making secure one or several computer installations using a common secret key algorithm, use of the method and a computer system utilizing the method

• US 7,050,581 B1
• Filed: 04/07/2000
• Issued: 05/23/2006
• Est. Priority Date: 04/09/1999
• Status: Expired due to Fees

• Current Assignee: CP8 Technologies (Thales SA)
• Original Assignee: CP8 Technologies (Thales SA)
• Inventors: Goubin, Louis, Patarin, Jacques
• Primary Examiner(s): Moise, Emmanuel L.
• Assistant Examiner(s): Khoshnoodi, Nadia
• Application Number:
  US09/719,193
• Time in Patent Office: 2,237 Days
• Field of Search: 713/151, 713/190, 713/193, 713/200, 380/281, 380/284
• US Class Current: 380/28
• CPC Class Codes: G06F 2207/7219 Countermeasures against side channel or fault attacks
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI

Abstract

The invention relates to a method for protecting one or more computer systems using the same secret key (Ks) cryptographic algorithm, characterized in that the way in which said calculation is performed depends, for each computer system and for each secret key, on secret data (Ds) stored in a secret area of the computer system or systems.

Claims

1. A method for protecting one or more computer systems using the same secret key (Ks) cryptographic algorithm, each computer system having storage means for storing the secret key (Ks) and processing means for executing the cryptographic algorithm, the method comprising:

storing a secret data (Ds) in a secret area of the storage means;

separating a standard cryptographic algorithm into a plurality of simultaneous calculation processes based on the secret data (Ds);

creating a plurality of partial intermediate variables corresponding to each intermediate variable of the standard cryptographic algorithm;

applying nonlinear transformations to each of the plurality of partial intermediate variables to create a plurality of partial results; and

reconstituting a final result, corresponding to a result of the standard cryptographic algorithm, from the plurality of partial results.

2. The method according to claim 1, wherein the secret data (Ds) includes:

a secret function f;

a plurality of partial conversion tables;

a secret random conversion table associated with a calculation based on conversion tables stored in a non-secret area of the storage means;

a polynomial function and one or more conversion tables;

a bijective secret function and a random secret transformation; and

a quadratic secret function.

3. The method according to claim 1, wherein, for each of the computer systems, the secret key (Ks) and the secret data (Ds) are entered into a programmable, non-volatile memory.

4. A method according to claim 1, wherein the nonlinear transformations include nonlinear transformations of km bits into kn bits described by k conversion tables in which n output bits of the transformation are read at an address that is a function of the km input bits, and for each of said nonlinear transformations, said k tables are part of the secret data (Ds).

5. A method according to claim 1, wherein the nonlinear transformations include nonlinear transformations of km bits into kn bits described by k conversion tables in which n output bits of the transformation are read at an address obtained by applying a secret bijective function (φ

) to an m-bit value, itself obtained by applying a public function of the km input bits of the nonlinear transformation, and for each of said nonlinear transformations, said k tables are part of the secret data (Ds).

6. The method according to claim 1, further comprising storing a conversion table calculation program in each computer system and activating the calculation program by a given event in order to calculate tables and store all or part of said tables in the secret data (Ds).

7. A method according to claim 5, wherein for each of the nonlinear transformations, the secret bijective function (φ

) is also part of the secret data.

8. A computer system, comprising:

storage means for storing a secret encryption key and secret data in a secret area of the storage means; and

at least one processor, coupled to the storage means, for modifying a standard secret key cryptographic algorithm into calculation processes based on the secret data, the processor operating to;

separate the standard secret key cryptographic algorithm into a plurality of simultaneous calculation processes based on the secret data,

replace each intermediate variable of the standard secret key cryptographic algorithm with a plurality of partial intermediate variables,

apply nonlinear transformations to each of the plurality of partial intermediate variables to create a plurality of partial results, and

reconstitute a final result, corresponding to a result of the standard secret key cryptographic algorithm, from the plurality of partial results.

9. A computer system according to claim 8, wherein the secret data stored in the secret area includes at least one first random variable v₁ constituting at least one secret partial variable, and the modified cryptographic algorithm determines at least one other partial variable v₂, by applying a first secret function to the intermediate variable v and the secret partial variable or variables v₁.

10. A computer system according to claim 9, wherein:

the modified cryptographic algorithm includes tables used for applying the nonlinear transformations to the partial variables v₁ and v₂, at least one of said tables, formed by random selection, and being stored in the secret data, the other tables required for the calculations being stored in a nonvolatile memory, and

the processor executes various computational rounds of the standard algorithm, each time using the tables on the partial variables, and calculates the final result in the last round of the algorithm by combining the partial results in accordance with a second secret function.

11. A computer system according to claim 8, wherein the modified cryptographic algorithm includes a function f, linking the partial intermediate variables and each intermediate variable (v), such that the knowledge of one value of said intermediate variable never makes it possible to deduce all of the particular partial values v_i such that there exists a (k−

1)-tuple (v₁, . . . , v<sub>i−

1</sub>, v_i+1, . . . v_k) that satisfies the equation f(v₁, . . . , V_i, . . . , v_k)=v.

12. A computer system according to claim 8, wherein the secret data includes k partial conversion tables, and among the k partial conversion tables, k−

1 partial conversion tables contain secret random variables.

13. A computer system according to claim 11, wherein the secret data includes k conversion tables, each of said conversion tables receiving an input a value obtained by applying a secret bijective function φ

₁ to said function f(v₁, . . . , v_k) of the partial intermediate variables in accordance with the relation φ

_j of(v₁, . . . , v_k), j ε

[1,k], this application φ

_j of(v₁, . . . , v_k) being performed by direct evaluation of a resulting value, this resulting value, applied to the input of the conversion table, making it possible to read n output bits of the transformation at an address that is a function of these m input bits.

14. A computer system according to claim 8, wherein the processor operates to:

replace each nonlinear transformation applied to an intermediate variable of the standard cryptographic calculation process, without a separation, with a partial nonlinear transformation of km bits into kn bits applied to all of the partial intermediate variables,

calculate (k−

)n of said output bits of this transformation as a polynomial function of the km input bits, and

read the remaining n bits of said output bits by reading a conversion table in which the n remaining bits are read at an address that is a function of the km input bits.

15. A computer system according to claim 8, wherein the processor sequentially executes operations performed by the modified algorithm in the various parts resulting from the separation of the cryptographic calculation process into several distinct calculation process parts.

16. A computer system according to claim 8, wherein the processor executes in interleaved fashion, operations performed in the various parts resulting from the separation of the cryptographic calculation process into several distinct calculation process parts.

17. A computer system according to claim 8, wherein the processor simultaneously executes operations performed in the various parts resulting from the separation of the cryptographic calculation process into several distinct calculation process parts, in the event of multiprogramming.

18. A computer system according to claim 8, wherein the at least one processor includes different processors working in parallel, simultaneously executing the operations performed in the various parts resulting from the separation of the cryptographic calculation process into several distinct calculation process parts.

19. A computer system according to claim 8, wherein the secret data includes a conversion table calculation program stored in each computer system and activated by a given event of the calculation of the tables and for the storage of all or part of these tables in the secret data.

20. A computer system according to claim 8, further including a counter having means for storing a value that is incremented with each cryptographic calculation so as to constitute a given event for the activation, by activating means, of the calculation of the tables when a given value is exceeded.

21. A system according to claim 8, wherein the secret data includes a plurality of nonlinear transformation tables, each transformation table designed to be applied by the processor to a partial intermediate variable.