EP2248009A2 - Procede et dispositifs de contre-mesure pour cryptographie asymetrique - Google Patents

Procede et dispositifs de contre-mesure pour cryptographie asymetrique

Info

Publication number
EP2248009A2
EP2248009A2 EP09719837A EP09719837A EP2248009A2 EP 2248009 A2 EP2248009 A2 EP 2248009A2 EP 09719837 A EP09719837 A EP 09719837A EP 09719837 A EP09719837 A EP 09719837A EP 2248009 A2 EP2248009 A2 EP 2248009A2
Authority
EP
European Patent Office
Prior art keywords
parameter
private key
binary
countermeasure
sequence
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP09719837A
Other languages
German (de)
English (en)
Inventor
Bruno Benteo
Benoît FEIX
Sébastien NEROT
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Inside Secure SA
Original Assignee
Inside Contactless SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Inside Contactless SA filed Critical Inside Contactless SA
Publication of EP2248009A2 publication Critical patent/EP2248009A2/fr
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/723—Modular exponentiation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/724—Finite field arithmetic
    • G06F7/725—Finite field arithmetic over elliptic curves
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/002—Countermeasures against attacks on cryptographic mechanisms
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3066—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
    • G06F2207/7219—Countermeasures against side channel or fault attacks

Definitions

  • the present invention relates to a countermeasure method in an electronic component implementing an asymmetric cryptography algorithm with a private key, resistant to attacks aimed at discovering the private key. It also relates to a microcircuit device and a portable device, in particular a smart card, implementing such a method.
  • an asymmetric cryptographic algorithm application 10 involving the use of a private key d is generally implemented by a microcircuit 12 to authenticate the transmission of a message M by a signature of this message. message or to protect the reception of an encrypted message M by a decryption of this message, using the private key.
  • the private key d is for example stored in the microcircuit 12 which includes a memory 14 including itself a secure memory space 16 provided for this purpose and a microprocessor 18 for executing the asymmetric cryptographic algorithm 10.
  • Microcircuit devices implementing cryptographic algorithms are sometimes attacked to determine the secret data they manipulate such as the key (s) used and possibly, in some cases, information on the messages. themselves.
  • asymmetric cryptography algorithms are under attack to discover the private key, when it is used.
  • Auxiliary channel attacks are an important family of cryptanalysis techniques that exploit certain properties of software or hardware implementations of cryptographic algorithms.
  • the attacks of the SPA (Simple Power Analysis) or DPA (Differential Power Analysis) type consist in measuring the incoming and outgoing currents and voltages in the microcircuit. during the execution of the asymmetric cryptographic algorithm in order to deduce the private key. The feasibility of this family of attacks has been demonstrated in the article by P. Kocher, J.
  • Fault injection (s) attacks are also known, among which are the DFA (Differential Fault Analysis) attacks, which consist in intentionally generating faults during the execution of the algorithm. cryptography, for example by disrupting the microcircuit on which it runs. Such a disturbance may include one or more short illumination (s) of the microcircuit or the generation of one or more peak (s) of voltage on one of its contacts. It thus makes it possible, under certain conditions, to exploit the calculation and behavior errors generated in order to obtain part or all of the private key sought.
  • DFA Different Fault Analysis attacks
  • RSA asymmetric cryptographic algorithm
  • An efficient implementation of this primitive uses a binary representation of the private key d by iterating on each bit of this binary representation. In each iteration, the calculation performed and in fact the energy consumption during the calculation depends on the value of the bit concerned. Therefore, the execution of such a primitive makes the private key particularly vulnerable to the aforementioned attacks.
  • a primitive consisting of a scalar multiplication is executed.
  • This primitive uses a binary representation of the private key d by iterating on each bit of this binary representation. Similarly, in each iteration, the energy consumption during the calculation depends on the value of the bit concerned. Therefore, the execution of such a primitive also makes the value of the scalar, which can be assimilated for security reasons to a private key, particularly vulnerable to attack. In order to combat these attacks which are varied by nature, many solutions very different from each other have been made.
  • the invention more particularly relates to those which implement a method of countermeasure in an electronic component implementing a private key asymmetric cryptography algorithm, comprising the steps of:
  • the protection parameter a is conventionally generated using a pseudo-random data generator 20, so that the execution of the primitive by the cryptographic algorithm 10 is itself made random and decorrelated of the private key used, for example by a technique commonly referred to as masking, which can also be renamed a method of transformation or deformation of the data since their manipulation is deformed as opposed to their raw use, carried out by a countermeasure section 22 of the microprocessor 18, using the protection parameter a.
  • the intermediate data of the cryptographic algorithm and, consequently, the measurable currents are modified by the random protection parameter and their observation does not make it possible to find the true value of the private key.
  • the masking does not disturb the algorithm itself, which therefore provides the same result with or without masking.
  • Another embodiment of an attack-resistant RSA algorithm comprises a first step in which the protection parameter d1 is chosen randomly such that 0 ⁇ d1 ⁇ d.
  • the private key d is decomposed into at least two exponents d1 and d2 of sizes comparable to that of d, so that the RSA algorithm is complicated by imposing on the at least two executions of the modular exponentiation instead of one.
  • One embodiment of the invention relates to a countermeasure method in an electronic component implementing a private key asymmetric cryptography algorithm, comprising the steps of:
  • the protection parameter is used to transform the binary blocks rather than the complete binary representation of the private key. Consequently, the size of the binary representation of the protection parameter can be much smaller than that of the binary representation of the private key, that is to say of the order of that of the binary blocks.
  • We simplify the calculation because, even if we increase the number of executions of the primitive, they operate on binary data of smaller sizes. At the end of the day, we can protect the execution of the algorithm asymmetric cryptography by significantly reducing its complexity compared to conventional countermeasure methods.
  • the countermeasure method comprises the step of dividing the binary representation of the private key such that the size of each binary block is greater than or equal to that of the binary representation of the protection parameter. .
  • the countermeasure method comprises the step of dividing the binary representation of the private key into a plurality of bit blocks such that the sum of the sizes of the binary blocks is equal to the size of the binary representation. of the private key.
  • the countermeasure method comprises the step of randomly determining iteratively the size of each bit block so that the value of each bit block is greater than the value of the protection parameter. According to one embodiment, the countermeasure method comprises the steps of:
  • the primitive is a modular exponentiation of the input data by the private key for the realization of an RSA or RSA CRT type cryptographic algorithm.
  • the countermeasure method comprises a preliminary step of masking the RSA module and the input data.
  • the primitive is a scalar multiplication of the input data by the private key, for the realization of a cryptography algorithm based on an elliptic curve in which the input data is a predetermined point of the elliptic curve.
  • the countermeasure method comprises a preliminary step of masking the predetermined point of the elliptical curve. According to one embodiment, the countermeasure method further comprises the steps of: initially generating, in a reproducible manner, at least one verification parameter before any execution of the primitive,
  • the regeneration and comparison step is performed at each iteration of the primitive when it is applied to a transformed binary block.
  • the countermeasure method comprises the step of triggering an alert and scrambling at least the private key, if the regeneration and comparison step indicates a difference between the verification parameter initially generated and the regenerated verification parameter.
  • the generation of the protection parameter and / or the verification parameter comprises the steps of:
  • the countermeasure method comprises the steps of: defining a plurality of functions, each function being generator, by successive applications to at least one predetermined secret parameter and stored in memory, of a sequence of corresponding values determinable only from the corresponding secret parameter and the corresponding function, - combining the plurality of sequences of values generated using a predefined relation to generate a new sequence of values,
  • the countermeasure method comprises the steps of: define a generating function, by successive applications to at least one predetermined secret parameter stored in memory, of a sequence of values that can be determined solely from the secret parameter and from the function; combining the sequence of generated values with public parameters the cryptographic algorithm to generate a new sequence of values,
  • Another embodiment of the invention consists in providing a microcircuit device, comprising a microprocessor for implementing a countermeasure method of a private key asymmetric cryptography algorithm, at least one secure memory for storage of the private key, and a data generator for generating a protection parameter, characterized in that it is configured to:
  • the microprocessor is configured to iteratively randomly determine the size of each bit block such that the value of each bit block is greater than the value of the protection parameter.
  • the primitive is a modular exponentiation of the input data by the private key for the realization of an RSA or RSA CRT type cryptographic algorithm.
  • the primitive is a scalar multiplication of the input data by the private key, for the realization of a cryptography algorithm based on an elliptic curve in which the input data is a predetermined point of the elliptic curve.
  • the microcircuit device is configured to further initially reproducibly generate at least one verification parameter before any execution of the primitive, to regenerate this verification parameter during execution or after execution of the primitive and compare the regenerated verification parameter with the verification parameter initially generated.
  • the data generator is configured to generate the protection parameter and / or the verification parameter in:
  • the data generator is configured to:
  • each function being generating, by successive applications to at least one predetermined secret parameter and stored in memory, a corresponding sequence of values that can be determined solely from the corresponding secret parameter and the corresponding function
  • the data generator is configured to: define a generating function, by successive applications to at least one predetermined secret parameter stored in memory, of a sequence of values that can be determined solely from the secret parameter and from the function; combining the sequence of generated values with public parameters the cryptographic algorithm to generate a new sequence of values,
  • Another embodiment of the invention consists in providing a portable device, in particular a smart card, comprising a microcircuit device as described above.
  • FIG. 1 previously described schematically represents the structure of a microcircuit device, of conventional type
  • FIG. 2 schematically represents the structure of a microcircuit device, according to a first embodiment of the invention.
  • FIG. 3 schematically represents a smart card comprising the device of FIG. 2,
  • FIG. 4 illustrates the successive steps of a first countermeasure method implemented by the device of FIG. 2,
  • FIG. 5 illustrates the successive steps of a second countermeasure method implemented by the device of FIG. 2,
  • FIG. 6 illustrates the successive steps of a third countermeasure method implemented by the device of FIG. 2
  • FIG. 7 illustrates the successive steps of a fourth countermeasure method implemented by the device of Figure 2
  • FIG. 8 illustrates the successive steps of a fifth countermeasure method implemented by the device of FIG. 2,
  • FIG. 9 schematically represents the structure of a microcircuit device, according to a second embodiment of the invention
  • FIG. 10 illustrates the successive steps of a countermeasure method implemented by the device of FIG. 9.
  • the microcircuit device 12 'represented in FIG. 2 comprises, like that represented in FIG. 1, an algorithmic application of asymmetric cryptography 10, a memory 14 including a secure memory space 16 for storing, in particular, a private key d for use by the application 10, a microprocessor 18 and a pseudo random data generator 20 for providing a protection parameter a. It also has a countermeasure section 22 ', but this provides an improvement to the existing countermeasures, in particular to the countermeasure section 22 previously described.
  • the device 12 ' is for example integrated in a portable device, in particular in the form of a secure smart card chip 30, as shown in FIG.
  • the countermeasure section 22' comprises:
  • d bin [D ⁇ 1 , ..., D 0 I 2 , and
  • the generator 20 may be designed to generate a protection parameter a whose size of the binary representation is at most equal to half the size of the binary representation of the private key d.
  • the section 22'a can be designed to divide the binary representation of the private key so that the size of each binary block is greater than or equal to that of the binary representation of the parameter of protection.
  • the algorithmic application of asymmetric cryptography 10 then executes the primitive using data whose size does not exceed half that of d b ⁇ n . The gain in calculation time is very sensitive.
  • FIG. 4 A first method of this type, performing an N-type RSA type cryptography on a message M, is illustrated in FIG. 4.
  • a verification parameter r1 is generated.
  • This verification parameter r1 is for example determined by the application of a predetermined COMB function, combining in particular a value v generated by the generator 20 and stored in memory, the protection parameter a and other parameters of the RSA algorithm. .
  • the message M and the module RSA N can also be transformed using functions g and h:
  • N N ⁇ - h (N)
  • M M ⁇ - g (M) mod N
  • V Exp (M, a, N, V), where V represents an intermediate data calculated using the Exp primitive from the input data M and the protection parameter a.
  • the output data S is initialized to 1 and a counter i to n-1. Then, during a test step 108, the value of the counter i is tested.
  • this value is strictly positive, it goes to a step 110, if not to an optional step 120 followed by a final step 122 or directly to the final step 122.
  • an integer j is determined, for example randomly, which verifies the following conditions:
  • This value D represents a binary block of the private key d transformed by a.
  • S Exp (M, D, N, S).
  • V the intermediate value V is combined with the value of S obtained in step 114, as follows: S ⁇ - SV mod N.
  • step 120 which is optional, follows step 108 when the value of the counter i is null and as long as the optional step 102 has been performed.
  • the parameter r1 is calculated again, using the COMB function and the public and / or stored values used by this function. If the value of r1 has changed between step 102 and step 120, it can be concluded that a fault injection attack (s) has occurred between these two steps.
  • An alert is then transmitted by the cryptographic application 10.
  • the output data S 1 is also unmasked as a function of the functions g and h that have been used to mask the input data M.
  • the reverse transformation (unmasking) performed with a fault makes it possible to counter an attack by fault injection (s).
  • the cryptographic application 10 returns the value S.
  • Steps 200, 202 (optional) and 204 of this second method remain identical to steps 100, 102 (optional) and 104 previously described.
  • the output data S is initialized to 1 and a counter i to u-1.
  • C [C ⁇ 1 C 0 ] 2 , recursively calculated as follows:
  • D ' represents the ith binary block of the private key d transformed by a.
  • step 214 the intermediate value V is combined with the value of S obtained in step 212, as follows:
  • Steps 218 and 220 are identical to steps 120 and 122 previously described.
  • RSA CRT type cryptography ie RSA algorithm using the Chinese Remainder Theorem
  • the RSA CRT algorithm is an alternative to the RSA algorithm for performing a signature or decryption: it is four times faster. It defines the following parameters:
  • steps 300 and 302 (optional) of this third method remain identical to the steps 100, 200 and 102, 202 (optional) previously described.
  • Vp Exp (M, a, p, Vp), where Vp represents an intermediate data computed using the Exp primitive from the input data M and the protection parameter a.
  • Vq Exp (M, a, q, Vq), where Vq is an intermediate data calculated using the Exp primitive from input data M and protection parameter a.
  • steps 304 to 310 are executed is not fixed. Indeed, it is important only that they be executed after step 302, that step 304 is executed before step 306 and that step 308 is executed before step 310.
  • an optional step 312 is followed by a final step 314 or directly at the final step 314.
  • the optional step 312 is identical to the step 120 and is performed only if the optional step 302 has been executed.
  • the cryptographic application 10 calculates the value of S from S p and S q as previously indicated and returns this value.
  • a fourth countermeasure method according to the invention that can be implemented by the device of FIG. 2, performing an Elliptic Curve type cryptography on a message M, will now be presented with reference to FIG.
  • an elliptic curve asymmetric cryptography algorithm otherwise known as the Elliptic Curve Cryptosystem (ECC) algorithm
  • ECC Elliptic Curve Cryptosystem
  • a verification parameter r is generated.
  • This verification parameter r is for example determined by the application of a predetermined COMB function, combining in particular a value v generated by the generator 20 and stored in memory, the protection parameter a and other parameters of the ECC algorithm. .
  • V ScalarMult (P, a, V), where V represents an intermediate data computed using the ScalarMult primitive from the input data P and the protection parameter a.
  • the output data Q is initialized to 0 and a counter i to n-1.
  • step 408 the value of the counter i is tested. If this value is strictly positive, proceed to a step 410, if not to an optional step 420 followed by a final step 422 or directly to the final step 422.
  • step 410 an integer j is determined by example randomly, which verifies the following conditions:
  • step 416 the intermediate value V is combined with the value of Q obtained in step 414, as follows: Q + - Q + V.
  • Step 420 which is optional, follows step 408 when the value of counter i is zero and provided that optional step 402 has been performed.
  • the parameter r is calculated again, using the function COMB and the public values and / or stored in memory used by this function. If the value of ra changed between step 402 and step 420, it can be concluded that a fault injection attack (s) occurred between these two steps.
  • An alert is then sent by the application of cryptography 10.
  • step 420 the output data Q is also unmasked, as a function of the function g which has been used to mask the input data P. According to the alert transmitted by the application cryptography 10, the inverse transformation (unmasking) performed with a fault makes it possible to counter an attack by fault injection (s).
  • the fourth method described above involves n + k scalar multiplication iterations: k iterations during step 404 and n iterations in the loop of steps 408 to 418.
  • the extra cost of the countermeasure on the ECC algorithm is very small. In any case, it is much weaker than that of prior art solutions involving at least 2 n scalar multiplication iterations.
  • V ScalarMult (-P, a, V).
  • D d
  • FIG. 8 A fifth countermeasure method according to the invention that can be implemented by the device of FIG. 2, and also performing Elliptic Curve cryptography, is illustrated in FIG. 8. It is a variant of FIG.
  • Steps 500, 502 (optional) and 504 of this fifth method remain identical to steps 400, 402 (optional) and 404 previously described.
  • the output data Q is initialized to 0 and a counter i to u-1.
  • step 508 the value of the counter i is tested. If this value is strictly positive, proceed to a step 510, if not to an optional step 518 followed by a final step 520 or directly to the final step 520.
  • D ⁇ D
  • D ⁇ D
  • step 514 the intermediate value V is combined with the value of Q obtained in step 512, as follows:
  • Steps 518 and 520 are identical to steps 420 and 422 previously described.
  • V ScalarMult (-P, a, V).
  • V ScalarMult (-P, a, V).
  • the microcircuit device 12 "represented in FIG. 9 comprises, like that represented in FIG. 2, an algorithmic application of cryptography 10, a memory 14 including a secure memory space 16, a microprocessor 18 and a countermeasure section 22 '. It is for example integrated in a portable device, in particular in the form of a chip of a secure smart card 30 as shown in FIG. 3. It will be noted, however, that although the algorithmic application of cryptography 10 and the section of against Measurements 22 'have been represented as distinct, these can in fact be intimately nested in the same implementation of a cryptography algorithm including a countermeasure.
  • the countermeasure section 22 'of the device 12 “comprises, like that of the device 12':
  • a section 22'b for transforming each binary block D 1 by means of a protection parameter a and, for each converted binary block D ',, to perform an intermediate calculation using the primitive.
  • the pseudo-random data generator 20 of the conventional type is replaced by a data generator 20" which comprises: a section 20 "a of application of a function F predefined to at minus a predetermined secret parameter S for the generation of a determinable sequence of values only from this secret parameter and this function F, and
  • a section 20 "b for providing at least one protection parameter reproducibly has a value of this sequence.
  • Section 20 is actually a software or hardware implementation of the F function.
  • the secret parameter S is stored in the secure memory 16 and supplied at the input of the section 20 "of the generator 20", while the protection parameter a is provided, at the output of the section 20 “b, at the counter section. -measure 22 '.
  • the parameter a is not therefore a hazard in the conventional sense mentioned in the documents of the state of the art.
  • This is a deterministic result derived from the calculation of the function F executed by the generator 20 "over at least one secret parameter S which may be specific to the smart card 30 on which the microcircuit 12 'is arranged.
  • This secret parameter is for example derived from a public datum of the device 30.
  • the element A n can be processed before providing the parameter a.
  • sequence (A n ) is cyclic and / or operates in a finite set of elements, the space of the values A n generated will have to be large enough to resist the attacks. In fact, the greater the space considered, the better the robustness of the countermeasure.
  • sequences of values (A n ) that can be provided by a generator 20 "according to the second embodiment of the invention .Then a second step, we will expose several possible uses of such sequences of values for the provision of protection parameters in particular to the five countermeasure applications in asymmetric cryptography previously described with reference to FIGS. 4 to 8.
  • this sequence takes the form of the group of inverse affine transformations on the finite field
  • GF (m) ⁇ 0, 1 m-1 ⁇ .
  • m is one of the secret parameters to be kept in the secure memory of the device.
  • the initial element A 0 is chosen as being the generating element a to which the law of internal composition of the group GC is applied k times,
  • the secret parameters S used by the generating function of the sequence (A n ) are then, for example, the generating element a and the values k, k 'and m.
  • the protection parameters generated are for example the elements of the sequence (A n ).
  • Frobenius groups An interesting property of Frobenius groups is that no non-trivial element fixes more than one point.
  • a secret parameter A 0 for example 16 bits
  • a corresponding CRC polynomial among those conventionally used in CRC calculations, for example the CRC-16 polynomial (X 16 + X 15 + X 2 + 1) or the CRC CCITT V41 polynomial (X 16 + X 12 + X 5 + 1).
  • the function T in question can be a secret matrix of values, the values A ' n and A " n respectively denoting respectively a row and a column of this matrix.
  • the sequence (A n ) can be generated from a first sequence (A ' n ), also according to public data, such as for example data used during the execution of the cryptography application with countermeasure and not secret. Among these data, depending on the applications, mention may be made of the message M (in clear or encrypted), a public key e, etc.
  • the values of the sequence used as protection parameters are then calculated using any COMB function combining all these data:
  • a n COMB (A ' n , M, e, ).
  • FIG. 10 illustrates an example of steps performed by a method according to the second embodiment of FIG. 9, applied to the execution of an asymmetric cryptographic algorithm with countermeasure, using T protection parameters a ,,. .. a ⁇ by execution, all the protection parameters can be extracted from the same sequence of values (A n ) generated by the section 20'a.
  • a counter i is initialized to 0. This counter i is intended to keep in memory the number of times that the asymmetric cryptographic algorithm has been executed since this step of initialization INIT, as long as another initialization is not performed.
  • the secret parameter S (or the parameters S when there are several), from which the sequence of values must be generated, is defined. It can be kept from a previous initialization, but can also be generated on the basis of a new value on the occasion of this initialization. It is for example generated from unique identification data, such as a public data device 30. It can also be generated from parameters or physical phenomena related to the microcircuit at a given instant, which can be random. In all cases, it is stored in memory in a secure manner, to allow the microcircuit to regenerate at any time the same sequence of values (A n ) using the function implemented by section 20 "a.
  • initialization INIT can be unique in the life cycle of the microcircuit, made during the design by the manufacturer, or reproduced several times, for example regularly or whenever the counter i reaches an imax value.
  • the generator 20 " is solicited one or more times to apply the secret parameter S to the predefined function F, to generate, in one or more times, a number T of elements of the sequence of values (A n ): A 1 , ... A ⁇ . From these first T elements, the protection parameters ⁇ , ... a ⁇ are generated.
  • a k A k .
  • T C 1 ,... SeC 7 additional secret values T C 1 ,... SeC 7 among the secret parameters S kept in secure memory
  • the generator 20 " is again requested one or more times to apply the secret parameter S to the predefined function F, so as to generate, in one or more times, a number T of additional elements of the sequence of values (A n ): A T (M) +1 , ... A 71 .
  • the knowledge of the method and the secret values used by the method allows to find at any time the protection parameters generated and used in the life of the device. It is clear that this feature allows simple and efficient debugging as well as improved resistance to fault injection attacks.
  • the choice of the method used to generate the sequence of values and the protection parameter (s) is dictated by the intended application.
  • 100, 200, 300 and the parameters v, r2, r3 during the steps 102, 202, 302 may be one of those recommended in the second embodiment.
  • the parameters v then r1, r2 and r3 can be found in steps 120, 218, 312 without necessarily being kept in memory during the execution of the exponentiation.
  • the protection parameter a can also be found to verify that its integrity has been preserved during the exponentiation.
  • the method used by the fourth and fifth methods of FIGS. 7 and 8 to generate the protection parameter a during steps 400, 500 and the parameter v during steps 402, 502 may be one of those recommended in FIG. second embodiment.
  • the parameter v then r can be found in steps 420, 518 without necessarily being stored in memory during the execution of the scalar multiplication.
  • the protection parameter a can also be found to verify that its integrity, and that of the parameters used to generate it, has been retained during the scalar multiplication.
  • Additional protection may be added when executing the computation loop of the primitive, in each of the five aforementioned methods.
  • the data M, N, d, etc. can be scrambled for not being discovered and an alert can be triggered.
  • Other data than M, N and d can be used, from the moment these data are used during the execution of the primitive.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computing Systems (AREA)
  • Computer Security & Cryptography (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • General Engineering & Computer Science (AREA)
  • Algebra (AREA)
  • Storage Device Security (AREA)
  • Complex Calculations (AREA)

Abstract

Ce procédé de contre-mesure dans un composant électronique mettant en oevre un algorithme de cryptographie asymétrique à clé privée, comprend la génération (100) d'un paramètre de protection et le calcul (104), à l'aide d'une primitive, d'une donnée intermédiaire à partir du paramètre de protection. Il comprend en outre les étapes consistant à diviser (110) la représentation binaire de la clé privée en plusieurs blocs binaires, à transformer (112) chaque bloc binaire à l'aide du paramètre de protection et, pour chaque bloc binaire transformé, à effectuer (114) un calcul intermédiaire à l'aide de la primitive, et à calculer (106-122) une donnée de sortie par combinaison (116) de la donnée intermédiaire avec les calculs intermédiaires (114).

Description

PROCEDE ET DISPOSITIFS DE CONTRE-MESURE POUR CRYPTOGRAPHIE ASYMETRIQUE
La présente invention concerne un procédé de contre-mesure dans un composant électronique mettant en œuvre un algorithme de cryptographie asymétrique à clé privée, résistant à des attaques visant à découvrir la clé privée. Elle concerne également un dispositif à microcircuit et un dispositif portable, notamment une carte à puce, mettant en œuvre un tel procédé.
Comme cela est illustré sur la figure 1 , une application algorithmique de cryptographie asymétrique 10 impliquant l'utilisation d'une clé privée d est généralement mise en oeuvre par un microcircuit 12 pour authentifier l'émission d'un message M par une signature de ce message ou pour protéger la réception d'un message M chiffré par un déchiffrement de ce message, à l'aide de la clé privée. La clé privée d est par exemple stockée dans le microcircuit 12 qui comporte une mémoire 14 incluant elle-même un espace de mémoire sécurisé 16 prévu à cet effet et un microprocesseur 18 pour exécuter l'algorithme de cryptographie asymétrique 10.
Les dispositifs à microcircuits mettant en œuvre des algorithmes de cryptographie font parfois l'objet d'attaques visant à déterminer les données secrètes qu'ils manipulent telles que la ou les clés utilisées et éventuellement, dans certains cas, de l'information sur les messages eux- mêmes. En particulier, les algorithmes de cryptographie asymétrique font l'objet d'attaques visant à découvrir la clé privée, lorsque celle-ci est utilisée. Les attaques par canaux auxiliaires constituent une famille importante des techniques de cryptanalyse qui exploitent certaines propriétés des implémentations logicielles ou matérielles des algorithmes de cryptographie. Parmi les attaques par canaux auxiliaires connues, les attaques de type SPA (de l'anglais « Simple Power Analysis ») ou DPA (de l'anglais « Différentiel Power Analysis ») consistent à mesurer les courants et tensions entrants et sortants dans le microcircuit au cours de l'exécution de l'algorithme de cryptographie asymétrique dans le but d'en déduire la clé privée. La faisabilité de cette famille d'attaques a été démontrée dans l'article de P. Kocher, J. Jaffe et B. Jun intitulé « Différentiel Power Analysis » notamment publié dans Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes In Computer Science Vol. 1666, M. Wiener, éd., Springer-Verlag, 1999. Les attaques temporelles analysent le temps mis pour effectuer certaines opérations. De telles attaques sur des algorithmes de cryptographie asymétrique sont décrites dans l'article de P. Kocher, N. Koblitz intitulé « Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other Systems » notamment publié dans Advances in Cryptology - Crypto 96, 16th annual international cryptology conférence, Aug. 18-22, 1996 Proceedings.
On connaît également les attaques par injection de faute(s), parmi lesquelles on peut citer les attaques DFA (de l'anglais « Differential Fault Analysis »), qui consistent à engendrer volontairement des fautes lors de l'exécution de l'algorithme de cryptographie, par exemple en perturbant le microcircuit sur lequel il s'exécute. Une telle perturbation peut inclure un (ou plusieurs) éclairage(s) bref(s) du microcircuit ou la génération d'un ou plusieurs pic(s) de tension sur l'un de ses contacts. Elle permet ainsi sous certaines conditions d'exploiter les erreurs de calcul et de comportement générées afin d'obtenir une partie voire la totalité de la clé privée recherchée.
En particulier, lors de l'exécution de l'algorithme de cryptographie asymétrique connu sous le nom de RSA (du nom de ses auteurs Rivest, Shamir et Adleman), une primitive consistant en une exponentiation modulaire est exécutée. Une implémentation efficace de cette primitive utilise une représentation binaire de la clé privée d en réalisant des itérations sur chaque bit de cette représentation binaire. Dans chaque itération, le calcul effectué et de fait la consommation d'énergie lors de la réalisation du calcul dépendent de la valeur du bit concerné. Par conséquent, l'exécution d'une telle primitive rend la clé privée particulièrement vulnérable aux attaques précitées. De même, lors de l'exécution d'une adaptation de cet algorithme de cryptographie asymétrique utilisant une courbe elliptique, une primitive consistant en une multiplication scalaire est exécutée. Une implémentation efficace de cette primitive utilise une représentation binaire de la clé privée d en réalisant des itérations sur chaque bit de cette représentation binaire. De même, dans chaque itération, la consommation d'énergie lors de la réalisation du calcul dépend de la valeur du bit concerné. Par conséquent, l'exécution d'une telle primitive rend aussi la valeur du scalaire, qui peut être assimilé pour des raisons de sécurité à une clé privée, particulièrement vulnérable aux attaques. Afin de lutter contre ces attaques qui sont variées par nature, de nombreuses solutions très différentes les unes des autres ont été apportées. L'invention concerne plus particulièrement celles qui mettent en œuvre un procédé de contre-mesure dans un composant électronique mettant en œuvre un algorithme de cryptographie asymétrique à clé privée, comprenant les étapes consistant à :
- générer un paramètre de protection,
- calculer, à l'aide d'une primitive de l'algorithme de cryptographie, une donnée intermédiaire à partir d'une donnée d'entrée et du paramètre de protection.
Ces algorithmes prévoient en général de transformer la clé privée à l'aide du paramètre de protection généré, d'appliquer la primitive à la clé privée transformée et de combiner le résultat obtenu avec la donnée intermédiaire. Généralement, le paramètre de protection a est généré de façon classique à l'aide d'un générateur de données pseudo aléatoires 20, de sorte que l'exécution de la primitive par l'algorithme de cryptographie 10 est elle-même rendue aléatoire et décorrélée de la clé privée utilisée, par exemple par une technique communément qualifiée de masquage, qui peut être également renommée méthode de transformation ou de déformation des données puisque leur manipulation est déformée par opposition à leur utilisation brute, réalisée, par une section de contre-mesure 22 du microprocesseur 18, à l'aide du paramètre de protection a. Ainsi, les données intermédiaires de l'algorithme de cryptographie et, par suite, les courants mesurables sont modifiés par le paramètre de protection aléatoire et leur observation ne permet pas de retrouver la véritable valeur de la clé privée. En revanche, le masquage ne perturbe pas l'algorithme lui-même qui fournit donc le même résultat avec ou sans masquage.
Un procédé de ce type est par exemple décrit dans le brevet Américain délivré sous le numéro US 6,381 ,699.
Dans ce document, un mode de réalisation dans le domaine de la cryptographie asymétrique de type RSA est décrit en référence à la figure 3. Dans l'algorithme RSA à clé publique e et à clé privée d, pour effectuer une signature ou un déchiffrement, exécuter la primitive consiste à calculer une donnée de sortie S à partir d'une donnée d'entrée M et de la clé privée d de la façon suivante : S = Md mod N, où N est le module RSA, produit de deux entiers premiers secrets, et où e et d vérifient la relation e.d = φ(N), la fonction <p(.) représentant la fonction indicatrice d'Euler.
En notant [dn..,, ..., do]2 la représentation binaire de la clé privée d, ce calcul peut être effectué comme suit : S = 1
Pour i variant de n-1 à 0 : S +- S2 mod N si d, = 1, S +- S x M mod N Le mode de réalisation d'un algorithme RSA résistant aux attaques décrit dans le document US 6,381 ,699, comporte une première étape 300 lors de laquelle un paramètre de protection d1 est généré de la façon suivante : on génère un nombre premier k aléatoirement choisi tel que 0<k<2128, puis z = k.φ(n), puis on choisit aléatoirement d1 tel que 0<d1<z et pgcd(d1 , z) = 1 (pgcd est la fonction « plus grand dénominateur commun »). La clé privée est alors transformée de la façon suivante : d2 = dχ(d.,~1 mod z) mod z.
Suite à la réception de la donnée d'entrée M, de nouvelles transformations sont réalisées sur d1 et d2 avant de procéder aux deux calculs suivants (étapes 345 et 350) :
- S0 = Md1 mod N (calcul à l'aide de la primitive d'une donnée intermédiaire S0 à partir de la donnée d'entrée M et du paramètre de protection d1 ),
- S = S0 d2 mod N (calcul de la donnée de sortie par combinaison de la donnée intermédiaire S0 avec l'application de la primitive à la clé privée transformée d2).
Un autre mode de réalisation d'un algorithme RSA résistant aux attaques, plus simple mais également décrit dans le document US 6,381 ,699, comporte une première étape lors de laquelle le paramètre de protection d1 est choisi aléatoirement tel que 0<d1<d.
La clé privée est alors transformée de la façon suivante : d2 = d - d1. Suite à la réception de la donnée d'entrée M, de nouvelles transformations sont réalisées sur d1 et d2 avant de procéder aux deux calculs suivants : - S1 = Md1 mod N (calcul à l'aide de la primitive d'une donnée intermédiaire S1 à partir de la donnée d'entrée M et du paramètre de protection d1 ), - S2 = Md2 mod N, S = S1-S2 mod N (calcul de la donnée de sortie S par combinaison de la donnée intermédiaire S1 avec l'application S2 de la primitive à la clé privée transformée d2).
Dans chacun des deux cas précités de l'état de la technique, on décompose la clé privée d en au moins deux exposants d1 et d2 de tailles comparables à celle de d, de sorte que l'on complique l'algorithme RSA en imposant au moins deux exécutions de l'exponentiation modulaire au lieu d'une. Bien que l'on ait ainsi conçu un algorithme de cryptographie asymétrique résistant à certaines attaques par canaux auxiliaires, c'est au prix d'une complexité sensiblement accrue de l'implémentation puisque que la complexité est en fait doublée.
Il peut ainsi être souhaité de prévoir un procédé de cryptographie asymétrique résistant aux attaques du type précité et qui soit simple à mettre en œuvre. Un mode de réalisation de l'invention concerne un procédé de contre- mesure dans un composant électronique mettant en œuvre un algorithme de cryptographie asymétrique à clé privée, comprenant les étapes consistant à :
- générer un paramètre de protection,
- calculer, à l'aide d'une primitive de l'algorithme de cryptographie, une donnée intermédiaire à partir d'une donnée d'entrée et du paramètre de protection, caractérisé en ce qu'il comporte en outre les étapes consistant à :
- diviser la représentation binaire de la clé privée en plusieurs blocs binaires, - transformer chaque bloc binaire à l'aide du paramètre de protection et, pour chaque bloc binaire transformé, effectuer un calcul intermédiaire à l'aide de la primitive, et
- calculer une donnée de sortie par combinaison de la donnée intermédiaire avec les calculs intermédiaires. Ainsi le paramètre de protection est utilisé pour transformer les blocs binaires plutôt que la représentation binaire complète de la clé privée. Par conséquent, la taille de la représentation binaire du paramètre de protection peut être nettement inférieure à celle de la représentation binaire de la clé privée, c'est-à-dire de l'ordre de celle des blocs binaires. On simplifie d'autant le calcul car, même si l'on augmente le nombre d'exécutions de la primitive, celles-ci opèrent sur des données binaires de plus petites tailles. Au bout du compte, on peut de la sorte protéger l'exécution de l'algorithme de cryptographie asymétrique en diminuant sa complexité de façon sensible par rapport aux procédés de contre-mesure classiques.
Selon un mode de réalisation, le procédé de contre-mesure comprend l'étape consistant à diviser la représentation binaire de la clé privée de telle sorte que la taille de chaque bloc binaire soit supérieure ou égale à celle de la représentation binaire du paramètre de protection.
Selon un mode de réalisation, le procédé de contre-mesure comprend l'étape consistant à diviser la représentation binaire de la clé privée en plusieurs blocs binaires de telle sorte que la somme des tailles des blocs binaires soit égale à la taille de la représentation binaire de la clé privée.
Selon un mode de réalisation, le procédé de contre-mesure comprend l'étape consistant à déterminer aléatoirement de manière itérative la taille de chaque bloc binaire de telle sorte que la valeur de chaque bloc binaire soit supérieure à la valeur du paramètre de protection. Selon un mode de réalisation, le procédé de contre-mesure comprend les étapes consistant à :
- choisir la taille k de la représentation binaire du paramètre de protection de telle sorte qu'il existe un entier u≥2 tel que n = k.u, n étant la taille de la représentation binaire de la clé privée, et - diviser la représentation binaire de la clé privée en u blocs binaires de k bits chacun.
Selon un mode de réalisation, la primitive est une exponentiation modulaire de la donnée d'entrée par la clé privée pour la réalisation d'un algorithme de cryptographie de type RSA ou RSA CRT. Selon un mode de réalisation, le procédé de contre-mesure comprend une étape préalable consistant à masquer le module RSA et la donnée d'entrée.
Selon un mode de réalisation, la primitive est une multiplication scalaire de la donnée d'entrée par la clé privée, pour la réalisation d'un algorithme de cryptographie basé sur une courbe elliptique dans lequel la donnée d'entrée est un point prédéterminé de la courbe elliptique.
Selon un mode de réalisation, le procédé de contre-mesure comprend une étape préalable consistant à masquer le point prédéterminé de la courbe elliptique. Selon un mode de réalisation, le procédé de contre-mesure comprend en outre les étapes consistant à : - générer initialement, de façon reproductible, au moins un paramètre de vérification avant toute exécution de la primitive,
- régénérer ce paramètre de vérification en cours d'exécution ou après exécution de la primitive et comparer le paramètre de vérification régénéré au paramètre de vérification généré initialement.
Selon un mode de réalisation, l'étape de régénération et de comparaison est exécutée à chaque itération de la primitive lorsqu'elle est appliquée à un bloc binaire transformé.
Selon un mode de réalisation, le procédé de contre-mesure comprend l'étape consistant à déclencher une alerte et brouiller au moins la clé privée, si l'étape de régénération et de comparaison indique une différence entre le paramètre de vérification généré initialement et le paramètre de vérification régénéré.
Selon un mode de réalisation, la génération du paramètre de protection et/ou du paramètre de vérification comporte les étapes consistant à :
- définir une fonction génératrice, par applications successives à au moins un paramètre secret prédéterminé et stocké en mémoire, d'une séquence de valeurs déterminable uniquement à partir de ce paramètre secret et de cette fonction,
- générer le paramètre de protection et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette séquence.
Selon un mode de réalisation, le procédé de contre-mesure comprend les étapes consistant à : - définir une pluralité de fonctions, chaque fonction étant génératrice, par applications successives à au moins un paramètre secret correspondant prédéterminé et stocké en mémoire, d'une séquence de valeurs correspondante déterminable uniquement à partir du paramètre secret correspondant et de la fonction correspondante, - combiner la pluralité de séquences de valeurs générées à l'aide d'une relation prédéfinie pour générer une nouvelle séquence de valeurs,
- générer le paramètre de protection et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette nouvelle séquence. Selon un mode de réalisation, le procédé de contre-mesure comprend les étapes consistant à : - définir une fonction génératrice, par applications successives à au moins un paramètre secret prédéterminé et stocké en mémoire, d'une séquence de valeurs déterminable uniquement à partir du paramètre secret et de la fonction, - combiner la séquence de valeurs générées avec des paramètres publics de l'algorithme de cryptographie pour générer une nouvelle séquence de valeurs,
- générer le paramètre de protection et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette nouvelle séquence.
Un autre mode de réalisation de l'invention consiste à fournir un dispositif à microcircuit, comprenant un microprocesseur pour la mise en œuvre d'un procédé de contre-mesure d'un algorithme de cryptographie asymétrique à clé privée, au moins une mémoire sécurisée pour le stockage de la clé privée, et un générateur de données pour la génération d'un paramètre de protection, caractérisé en ce qu'il est configuré pour :
- calculer, à l'aide d'une primitive de l'algorithme de cryptographie, une donnée intermédiaire à partir d'une donnée d'entrée et du paramètre de protection, - diviser la représentation binaire de la clé privée en plusieurs blocs binaires,
- transformer chaque bloc binaire à l'aide du paramètre de protection et, pour chaque bloc binaire transformé, effectuer un calcul intermédiaire à l'aide de la primitive, - calculer une donnée de sortie par combinaison de la donnée intermédiaire avec les calculs intermédiaires.
Selon un mode de réalisation, le microprocesseur est configuré pour déterminer aléatoirement de manière itérative la taille de chaque bloc binaire de telle sorte que la valeur de chaque bloc binaire soit supérieure à la valeur du paramètre de protection.
Selon un mode de réalisation, le générateur de données est configuré pour choisir la taille k de la représentation binaire du paramètre de protection de telle sorte qu'il existe un entier u≥2 tel que n = k.u, n étant la taille de la représentation binaire de la clé privée, et le microprocesseur est configuré pour diviser la représentation binaire de la clé privée en u blocs binaires de k bits chacun. Selon un mode de réalisation, la primitive est une exponentiation modulaire de la donnée d'entrée par la clé privée pour la réalisation d'un algorithme de cryptographie de type RSA ou RSA CRT.
Selon un mode de réalisation, la primitive est une multiplication scalaire de la donnée d'entrée par la clé privée, pour la réalisation d'un algorithme de cryptographie basé sur une courbe elliptique dans lequel la donnée d'entrée est un point prédéterminé de la courbe elliptique.
Selon un mode de réalisation, le dispositif à microcircuit est configuré pour en outre générer initialement, de façon reproductible, au moins un paramètre de vérification avant toute exécution de la primitive, régénérer ce paramètre de vérification en cours d'exécution ou après exécution de la primitive et comparer le paramètre de vérification régénéré au paramètre de vérification généré initialement.
Selon un mode de réalisation, le générateur de données est configuré pour générer le paramètre de protection et/ou le paramètre de vérification en :
- définissant une fonction génératrice, par applications successives à au moins un paramètre secret prédéterminé et stocké en mémoire, d'une séquence de valeurs déterminable uniquement à partir de ce paramètre secret et de cette fonction, et
- générant le paramètre de protection et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette séquence.
Selon un mode de réalisation, le générateur de données est configuré pour :
- définir une pluralité de fonctions, chaque fonction étant génératrice, par applications successives à au moins un paramètre secret correspondant prédéterminé et stocké en mémoire, d'une séquence de valeurs correspondante déterminable uniquement à partir du paramètre secret correspondant et de la fonction correspondante,
- combiner la pluralité de séquences de valeurs générées à l'aide d'une relation prédéfinie pour générer une nouvelle séquence de valeurs,
- générer le paramètre de protection et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette nouvelle séquence.
Selon un mode de réalisation, le générateur de données est configuré pour : - définir une fonction génératrice, par applications successives à au moins un paramètre secret prédéterminé et stocké en mémoire, d'une séquence de valeurs déterminable uniquement à partir du paramètre secret et de la fonction, - combiner la séquence de valeurs générées avec des paramètres publics de l'algorithme de cryptographie pour générer une nouvelle séquence de valeurs,
- générer le paramètre de protection et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette nouvelle séquence.
Un autre mode de réalisation de l'invention consiste à fournir un dispositif portable, notamment une carte à puce, comprenant un dispositif à microcircuit tel que décrit précédemment.
Ces objets, caractéristiques et avantages ainsi que d'autres de la présente invention seront exposés plus en détail dans la description suivante, faite à titre non limitatif en relation avec les figures jointes parmi lesquelles :
- la figure 1 précédemment décrite représente de façon schématique la structure d'un dispositif à microcircuit, de type classique, - la figure 2 représente de façon schématique la structure d'un dispositif à microcircuit, selon un premier mode de réalisation de l'invention,
- la figure 3 représente de façon schématique une carte à puce comprenant le dispositif de la figure 2,
- la figure 4 illustre les étapes successives d'un premier procédé de contre-mesure mis en œuvre par le dispositif de la figure 2,
- la figure 5 illustre les étapes successives d'un deuxième procédé de contre-mesure mis en œuvre par le dispositif de la figure 2,
- la figure 6 illustre les étapes successives d'un troisième procédé de contre-mesure mis en œuvre par le dispositif de la figure 2, - la figure 7 illustre les étapes successives d'un quatrième procédé de contre-mesure mis en œuvre par le dispositif de la figure 2,
- la figure 8 illustre les étapes successives d'un cinquième procédé de contre-mesure mis en œuvre par le dispositif de la figure 2,
- la figure 9 représente de façon schématique la structure d'un dispositif à microcircuit, selon un deuxième mode de réalisation de l'invention, et - la figure 10 illustre les étapes successives d'un procédé de contre- mesure mis en œuvre par le dispositif de la figure 9.
Premier mode de réalisation de l'invention.
Le dispositif à microcircuit 12' représenté sur la figure 2 comporte, comme celui représenté sur la figure 1 , une application algorithmique de cryptographie asymétrique 10, une mémoire 14 incluant un espace de mémoire sécurisé 16 pour le stockage, notamment, d'une clé privée d destinée à être utilisée par l'application 10, un microprocesseur 18 et un générateur de données pseudo aléatoires 20 pour la fourniture d'un paramètre de protection a. Il comporte également une section de contre- mesure 22', mais celle-ci apporte une amélioration aux contre-mesures existantes, en particulier à la section de contre-mesure 22 précédemment décrite.
Par ailleurs, le dispositif 12' est par exemple intégré dans un dispositif portable, notamment sous la forme d'une puce de carte à puce sécurisée 30, comme représenté sur la figure 3.
On notera que, bien que l'application algorithmique de cryptographie
10 et la section de contre-mesure 22' aient été représentées comme distinctes, celles-ci peuvent être en fait intimement imbriquées en une même implémentation, logicielle ou matérielle, d'un algorithme de cryptographie asymétrique incluant une contre-mesure.
Contrairement au dispositif 12, dans ce dispositif 12' la section de contre-mesure 22' comporte :
- une section 22'a pour diviser la représentation binaire de la clé privée d en plusieurs blocs binaires D11., D0, dont la somme des tailles est par exemple égale à la taille de la représentation binaire de la clé privée ; la représentation binaire de la clé privée d peut donc s'écrire dbin = [D^1, ..., D0I2, et
- une section 22'b pour transformer chaque bloc binaire D| à l'aide du paramètre de protection a et, pour chaque bloc binaire transformé D'i, effectuer un calcul intermédiaire à l'aide de la primitive.
Plus précisément, le générateur 20 peut être conçu pour générer un paramètre de protection a dont la taille de la représentation binaire est au plus égale à la moitié de la taille de la représentation binaire de la clé privée d. De même, la section 22'a peut être conçue pour diviser la représentation binaire de la clé privée de telle sorte que la taille de chaque bloc binaire soit supérieure ou égale à celle de la représentation binaire du paramètre de protection. L'application algorithmique de cryptographie asymétrique 10 exécute alors la primitive à l'aide de données dont la taille n'excède pas la moitié de celle de dbιn. Le gain en temps de calcul est très sensible.
Différents procédés de contre-mesure conformes à l'invention peuvent être mis en œuvre par le dispositif de la figure 2.
Un premier procédé de ce type, réalisant une cryptographie de type RSA de module N sur un message M, est illustré par la figure 4. De façon classique, l'algorithme RSA nécessite l'utilisation d'une clé privée d dont la taille n de la représentation binaire est par exemple égale à n = 1024 bits. Si l'on note d, les bits de cette représentation binaire, il vient dbin = [d^ do]2.
On note S = Exp (M, D, N, S), la primitive suivante : Pour i variant dej-1 à 0 : S *- S2 mod N Si D1 = 1, S <- S.M mod N Retourner la valeur S où M et S sont respectivement les données d'entrée et de sortie de la primitive, N est le module RSA et D est un exposant binaire de taille j tel que D = [Dj..,, ..., D0]2, OÙ les D1 sont les valeurs binaires de D.
Lors d'une première étape 100, le générateur 20 de données pseudo aléatoires génère un paramètre de protection a dont la taille k de la représentation binaire est largement inférieure à n, par exemple k = 32 bits.
Lors d'une deuxième étape 102 optionnelle, on génère un paramètre de vérification r1. Ce paramètre de vérification r1 est par exemple déterminé par l'application d'une fonction COMB prédéterminée, combinant notamment une valeur v générée par le générateur 20 et conservée en mémoire, le paramètre de protection a et d'autres paramètres de l'algorithme RSA.
Au cours de cette même étape optionnelle 102, on peut également transformer le message M et le module RSA N à l'aide de fonctions g et h :
N <- h(N), puis M <— g(M) mod N, où g et h sont par exemple des fonctions définies par g(x) = x + r2.N et h(x) = r3.x, ou g(x) = r2.x et h(x) = x, dans lesquelles r2 et r3 peuvent être des aléas générés par le générateur 20 et conservés en mémoire.
Ensuite, lors d'une étape d'exponentiation 104, on initialise une donnée V à 1 , puis on effectue le calcul suivant : V = Exp (M, a, N, V), où V représente une donnée intermédiaire calculée à l'aide de la primitive Exp à partir de la donnée d'entrée M et du paramètre de protection a.
Lors d'une étape d'initialisation 106, on initialise la donnée de sortie S à 1 et un compteur i à n-1. Ensuite, lors d'une étape de test 108, on teste la valeur du compteur i.
Si cette valeur est strictement positive, on passe à une étape 110, sinon à une étape optionnelle 120 suivie d'une étape finale 122 ou directement à l'étape finale 122.
Lors de l'étape 110, on détermine un entier j, par exemple de façon aléatoire, qui vérifie les conditions suivantes :
(a) k ≤ j < i, et
(b) di.2j + dM.2j-1 + ... + dH.2° > a.
En outre, si j est tel que i-j < k, alors on affecte à j la valeur du compteur i. Ensuite, lors d'une étape 112, on calcule la valeur D = dj.2J + dM.2H +
... + dμj.2° - a. Cette valeur D représente un bloc binaire de la clé privée d transformé par a. Puis lors d'une étape 114, on effectue le calcul intermédiaire suivant, en utilisant le bloc binaire D : S = Exp (M, D, N, S). Ensuite, lors d'une étape 116, on combine la valeur intermédiaire V avec la valeur de S obtenue à l'étape 114, de la façon suivante : S <- S.V mod N.
Puis on affecte au compteur i la valeur i-j lors d'une étape 118. On revient ensuite à l'étape de test 108. L'étape 120, qui est optionnelle, fait suite à l'étape 108 lorsque la valeur du compteur i est nulle et à condition que l'étape optionnelle 102 ait été réalisée. Lors de cette étape 120, on calcule de nouveau le paramètre r1 , à l'aide de la fonction COMB et des valeurs publiques et/ou conservées en mémoire utilisées par cette fonction. Si la valeur de r1 a changé entre l'étape 102 et l'étape 120, cela permet de conclure qu'une attaque par injection de faute(s) a eu lieu entre ces deux étapes. Une alerte est alors transmise par l'application de cryptographie 10. Lors de l'étape 120 on démasque également la donnée de sortie S1 en fonction des fonctions g et h qui ont été utilisées pour masquer la donnée d'entrée M. Suivant l'alerte transmise par l'application de cryptographie 10, la transformation inverse (démasquage) réalisée avec une faute permet de contrer une attaque par injection de faute(s). Enfin, lors d'une dernière étape 122, l'application de cryptographie 10 retourne la valeur S.
On remarque que le premier procédé décrit ci-dessus implique n+k itérations d'exponentiation : k itérations lors de l'étape 104 et n itérations dans la boucle des étapes 108 à 118. Lorsque k est très inférieur à n (par exemple lorsque k = 32 alors que n = 1024), le surcoût de la contre-mesure sur l'algorithme RSA est très faible. Il est en tout cas beaucoup plus faible que celui des solutions de l'état de la technique impliquant au moins 2n itérations d'exponentiation. Un deuxième procédé de contre-mesure conforme à l'invention pouvant être mis en œuvre par le dispositif de la figure 2, et réalisant également une cryptographie de type RSA de module N sur un message M, est illustré par la figure 5. Il s'agit d'une variante du premier procédé dans laquelle, la taille k du paramètre de protection a étant choisie de sorte qu'il existe un entier u tel que n = k.u, on fixe la valeur de j (étape 110) à k et on n'impose pas la condition (b). Le procédé de contre-mesure s'en trouve simplifié.
Les étapes 200, 202 (optionnelle) et 204 de ce deuxième procédé restent identiques aux étapes 100, 102 (optionnelle) et 104 précédemment décrites.
Ensuite, lors d'une étape d'initialisation 206, on initialise la donnée de sortie S à 1 et un compteur i à u-1. Lors de cette même étape, on divise la représentation binaire de la clé privée d en u blocs D1 successifs, chacun de taille k, tels que dbιn = [D^1, ..., D0]2. Il vient, pour tout i, 0<i<u : D, = [dk(l+1H, ..., DJ2. En outre, on calcule, puis on conserve en mémoire un vecteur C de retenues binaires C = [C^1 C0]2, calculé par récurrence de la façon suivante :
- C0 = O,
- C1 = (D, - a - C1)/^. Ensuite, lors d'une étape de test 208, on teste la valeur du compteur i.
Si cette valeur est strictement positive, on passe à une étape 210, sinon à une étape optionnelle 218 suivie d'une étape finale 220 ou directement à l'étape finale 220.
Lors de l'étape 210, on calcule la valeur D', = D, - a - C1. Pour le bon fonctionnement de l'algorithme, si i=u-1 et si C^1=I , alors cela signifie que D', est inférieur à a et dans ce cas on conserve D', = D1. Cette valeur D', représente le i-ème bloc binaire de la clé privée d transformé par a. On remarque que l'un des intérêts de ce deuxième procédé est de ne nécessiter que le stockage du vecteur de retenues binaires C, et pas celui des blocs transformés D',.
Ensuite, lors d'une étape 212, on effectue le calcul intermédiaire suivant, en utilisant le bloc binaire D', :
S = Exp (M, D',, N, S).
Ensuite, lors d'une étape 214, on combine la valeur intermédiaire V avec la valeur de S obtenue à l'étape 212, de la façon suivante :
S <- S.V mod N. Puis on affecte au compteur i la valeur i-1 lors d'une étape 216. On revient ensuite à l'étape de test 208.
Les étapes 218 et 220 sont identiques aux étapes 120 et 122 précédemment décrites.
On remarque également que le deuxième procédé décrit ci-dessus implique n+k itérations d'exponentiation.
Un troisième procédé de contre-mesure conforme à l'invention pouvant être mis en œuvre par le dispositif de la figure 2, réalisant une cryptographie de type RSA CRT (ie. Algorithme RSA utilisant le Théorème du Reste Chinois) de module N = p.q sur un message M, est illustré par la figure 6. De façon classique, l'algorithme RSA CRT constitue une alternative à l'algorithme RSA pour effectuer une signature ou un déchiffrement : il est quatre fois plus rapide. Il définit les paramètres suivants :
- dp = d mod (p-1 ),
- dq = d mod (q-1 ), - A = p"1 mod q.
Il consiste ensuite à remplacer le calcul d'exponentiation S = Md mod N par deux calculs d'exponentiation beaucoup plus simples à exécuter du fait de la taille de p et q par rapport à celle de N : Sp = Mdp mod p et Sq = Mdq mod q. Enfin on retrouve S par le calcul suivant : S = [((Sq - SP).A mod q).p + Sp] mod N.
Les étapes 300 et 302 (optionnelle) de ce troisième procédé restent identiques aux étapes 100, 200 et 102, 202 (optionnelles) précédemment décrites.
Ensuite, lors d'une étape d'exponentiation 304, on initialise une donnée Vp à 1 , puis on effectue le calcul suivant :
Vp = Exp (M, a, p, Vp), où Vp représente une donnée intermédiaire calculée à l'aide de la primitive Exp à partir de la donnée d'entrée M et du paramètre de protection a.
Suite à l'étape 304, lors d'une étape 306 incluant une série d'étapes en boucle et correspondant aux étapes déjà décrites 106 à 118 ou 206 à 216 moyennant le remplacement de l'exposant d par dp et du module N par p, on réalise le calcul Sp = Mdp mod p.
Lors d'une étape d'exponentiation 308, on initialise une donnée Vq à 1 , puis on effectue le calcul suivant :
Vq = Exp (M, a, q, Vq), où Vq représente une donnée intermédiaire calculée à l'aide de la primitive Exp à partir de la donnée d'entrée M et du paramètre de protection a.
Suite à l'étape 308, lors d'une étape 310 incluant une série d'étapes en boucle et correspondant aux étapes déjà décrites 106 à 118 ou 206 à 216 moyennant le remplacement de l'exposant d par dq et du module N par q, on réalise le calcul Sq = Mdq mod q.
L'ordre dans lequel les étapes 304 à 310 sont exécutées n'est pas figé. En effet, il importe juste qu'elles soient exécutées après l'étape 302, que l'étape 304 soit exécutée avant l'étape 306 et que l'étape 308 soit exécutée avant l'étape 310. En sortie de boucles, c'est-à-dire à l'issue des étapes 306 et 310, on passe à une étape optionnelle 312 suivie d'une étape finale 314 ou directement à l'étape finale 314.
L'étape optionnelle 312 est identique à l'étape 120 et est réalisée uniquement si l'étape optionnelle 302 a été exécutée.
Lors de l'étape finale 314, l'application de cryptographie 10 calcule la valeur de S à partir de Sp et Sq comme indiqué précédemment et retourne cette valeur.
Un quatrième procédé de contre-mesure conforme à l'invention pouvant être mis en œuvre par le dispositif de la figure 2, réalisant une cryptographie de type Courbe Elliptique sur un message M, va maintenant être présenté en référence à la figure 7. De façon classique, un algorithme de cryptographie asymétrique à Courbe Elliptique, autrement appelé algorithme ECC (de l'anglais « Elliptic Curve Cryptosystem »), nécessite l'utilisation d'une clé privée d dont la taille n est nettement inférieure à celle qui est nécessaire pour l'algorithme RSA à niveau de sécurité équivalent. En général, il faut que la représentation binaire de la clé privée d soit au moins égale à n = 160 bits. Dans un algorithme ECC à clé privée d, pour effectuer une signature ou un déchiffrement, « exécuter la primitive » consiste à calculer une donnée de sortie Q à partir d'une donnée d'entrée P et de la clé privée d de la façon suivante : Q = d.P, où P et Q sont des points d'une courbe elliptique prédéterminée sur un corps fini GF(p) dans lequel p est un nombre premier strictement supérieur à 3 (par exemple la courbe elliptique y2 = x3 + 1Ox + 5 dans le corps GF(13)), et l'opération « . » est une multiplication scalaire, ici du point P par le scalaire d. En notant [d^, ..., do]2 la représentation binaire de la clé privée d, ce calcul peut être effectué comme suit : Q = O Pour i variant de n-1 à 0 :
Q <- 2Q si dι = 1, Q +- Q + P où « 2Q » et « Q + P » sont respectivement des opérations de doublement de point et d'addition de points dont les formules sont déterminées de façon classique, et non détaillée ici, par la courbe elliptique choisie et l'ordre p du corps GF(p). Pour la suite de la description, on note S = ScalarMult (P, D, Q), la primitive suivante :
Pour i variant dej-1 à 0 : Q <- 2Q si D1 = I1 Q ^ Q + P Retourner la valeur Q où P et Q sont respectivement les données d'entrée et de sortie de la primitive et D est un exposant binaire de taille j tel que D = [DH, ..., D0]2, où les D; sont les valeurs binaires de D.
Lors d'une première étape 400, le générateur 20 de données pseudo aléatoires génère un paramètre de protection a dont la taille k de la représentation binaire est largement inférieure à n, par exemple k = 32 bits.
Lors d'une deuxième étape 402 optionnelle, on génère un paramètre de vérification r. Ce paramètre de vérification r est par exemple déterminé par l'application d'une fonction COMB prédéterminée, combinant notamment une valeur v générée par le générateur 20 et conservée en mémoire, le paramètre de protection a et d'autres paramètres de l'algorithme ECC. Au cours de cette même étape optionnelle 402, on peut également transformer les coordonnées Px et Py du point P à l'aide d'une fonction g qui s'applique sur ces coordonnées : P <— g(Px, Py) mod N.
Ensuite, lors d'une étape 404, on initialise une donnée V à 0, puis on effectue le calcul suivant :
V = ScalarMult (P, a, V), où V représente une donnée intermédiaire calculée à l'aide de la primitive ScalarMult à partir de la donnée d'entrée P et du paramètre de protection a.
Lors d'une étape d'initialisation 406, on initialise la donnée de sortie Q à 0 et un compteur i à n-1.
Ensuite, lors d'une étape de test 408, on teste la valeur du compteur i. Si cette valeur est strictement positive, on passe à une étape 410, sinon à une étape optionnelle 420 suivie d'une étape finale 422 ou directement à l'étape finale 422. Lors de l'étape 410, on détermine un entier j, par exemple de façon aléatoire, qui vérifie les conditions suivantes :
(a) k < j < i, et
(b) d,.2J + dl.1.2J-1 + ... + d,.J.2° > a.
En outre, si j est tel que i-j < k, alors on affecte à j la valeur du compteur i.
Ensuite, lors d'une étape 412, on calcule la valeur D = d,.2J + d,..,.2J~1 + ... + d,.r2° - a. Cette valeur D représente un bloc binaire de la clé privée d transformé par a. Puis lors d'une étape 414, on effectue le calcul intermédiaire suivant, en utilisant le bloc binaire D : Q= ScalarMult (P, D, Q).
Ensuite, lors d'une étape 416, on combine la valeur intermédiaire V avec la valeur de Q obtenue à l'étape 414, de la façon suivante : Q +- Q + V.
Puis on affecte au compteur i la valeur i-j lors d'une étape 418. On revient ensuite à l'étape de test 408.
L'étape 420, qui est optionnelle, fait suite à l'étape 408 lorsque la valeur du compteur i est nulle et à condition que l'étape optionnelle 402 ait été réalisée. Lors de cette étape 420, on calcule de nouveau le paramètre r, à l'aide de la fonction COMB et des valeurs publiques et/ou conservées en mémoire utilisées par cette fonction. Si la valeur de r a changé entre l'étape 402 et l'étape 420, cela permet de conclure qu'une attaque par injection de faute(s) a eu lieu entre ces deux étapes. Une alerte est alors transmise par l'application de cryptographie 10. Lors de l'étape 420 on démasque également la donnée de sortie Q, en fonction de la fonction g qui a été utilisée pour masquer la donnée d'entrée P. Suivant l'alerte transmise par l'application de cryptographie 10, la transformation inverse (démasquage) réalisée avec une faute permet de contrer une attaque par injection de faute(s).
Enfin, lors d'une dernière étape 422, l'application de cryptographie 10 retourne la valeur Q.
On remarque que le quatrième procédé décrit ci-dessus implique n+k itérations de multiplication scalaire : k itérations lors de l'étape 404 et n itérations dans la boucle des étapes 408 à 418. Lorsque k est très inférieur à n (par exemple lorsque k = 32 alors que n = 160 ou plus), le surcoût de la contre-mesure sur l'algorithme ECC est très faible. Il est en tout cas beaucoup plus faible que celui des solutions de l'état de la technique impliquant au moins 2n itérations de multiplication scalaire.
En variante, lors de l'étape 404, on initialise la donnée V à 0, puis on effectue le calcul suivant : V = ScalarMult (-P, a, V). Dans ce cas, lors de l'étape 412 on calcule la valeur D = d|.2j + dM.2H + ... + dH.2° + a. Ceci constitue une autre transformation possible de la clé privée d par a. Un cinquième procédé de contre-mesure conforme à l'invention pouvant être mis en œuvre par le dispositif de la figure 2, et réalisant également une cryptographie à Courbe Elliptique, est illustré par la figure 8. Il s'agit d'une variante du quatrième procédé dans laquelle, la taille k du paramètre de protection a étant choisie de sorte qu'il existe un entier u tel que n = k.u, on fixe la valeur de j (étape 410) à k et on n'impose pas la condition (b). Le procédé de contre-mesure s'en trouve simplifié.
Les étapes 500, 502 (optionnelle) et 504 de ce cinquième procédé restent identiques aux étapes 400, 402 (optionnelle) et 404 précédemment décrites. Ensuite, lors d'une étape d'initialisation 506, on initialise la donnée de sortie Q à 0 et un compteur i à u-1. Lors de cette même étape, on divise la représentation binaire de la clé privée d en u blocs D; successifs, chacun de taille k, tels que dbin = [D11., , ..., D0]2. Il vient, pour tout i, 0<i<u : D1 = [d^^, ..., D1J2- En outre, on calcule, puis on conserve en mémoire un vecteur C de retenues binaires C = [C0-1, ..., C0]2, calculé par récurrence de la façon suivante :
- C0 = O, - C1 = (D1 - a - C^".
Ensuite, lors d'une étape de test 508, on teste la valeur du compteur i. Si cette valeur est strictement positive, on passe à une étape 510, sinon à une étape optionnelle 518 suivie d'une étape finale 520 ou directement à l'étape finale 520.
Lors de l'étape 510, on calcule la valeur D'i = Dj - a - C,. Pour le bon fonctionnement de l'algorithme, si i=u-1 et si C^1=I , alors cela signifie que D'; est inférieur à a et dans ce cas on conserve D^ = D,. Cette valeur D^ représente le i-ème bloc binaire de la clé privée d transformé par a. On remarque que l'un des intérêts de ce deuxième procédé est de ne nécessiter que le stockage du vecteur de retenues binaires C, et pas celui des blocs transformés DV
Ensuite, lors d'une étape 512, on effectue le calcul intermédiaire suivant, en utilisant le bloc binaire D^ : Q = ScalarMult(P, D',, Q).
Ensuite, lors d'une étape 514, on combine la valeur intermédiaire V avec la valeur de Q obtenue à l'étape 512, de la façon suivante :
Q <- Q + V.
Puis on affecte au compteur i la valeur i-1 lors d'une étape 516. On revient ensuite à l'étape de test 508.
Les étapes 518 et 520 sont identiques aux étapes 420 et 422 précédemment décrites.
On remarque également que le deuxième procédé décrit ci-dessus implique n+k itérations de multiplication scalaire. De même que pour le quatrième procédé, en variante, lors de l'étape
504, on initialise la donnée V à 0, puis on effectue le calcul suivant : V = ScalarMult (-P, a, V). Dans ce cas, lors de l'étape 506, le calcul du vecteur de retenues binaires est modifié de la façon suivante :
- C0 = O, - C1 = (D1 + a + CM)/2k.
Dans ce cas également, lors de l'étape 510 on calcule la valeur D', = D| + a + C1. Ceci constitue une autre transformation possible de la clé privée d par a.
Second mode de réalisation de l'invention. Le dispositif à microcircuit 12" représenté sur la figure 9 comporte, comme celui représenté sur la figure 2, une application algorithmique de cryptographie 10, une mémoire 14 incluant un espace de mémoire sécurisé 16, un microprocesseur 18 et une section de contre-mesure 22'. Il est par exemple intégré dans un dispositif portable, notamment sous la forme de puce d'une carte à puce sécurisée 30 comme représenté sur la figure 3. On notera cependant que, bien que l'application algorithmique de cryptographie 10 et la section de contre-mesure 22' aient été représentées comme distinctes, celles-ci peuvent être en fait intimement imbriquées en une même implémentation d'un algorithme de cryptographie incluant une contre- mesure.
La section de contre-mesure 22' du dispositif 12" comporte, comme celle du dispositif 12' :
- une section 22'a pour diviser la représentation binaire de la clé privée d en plusieurs blocs binaires D11..,, ..., D0, dont la somme des tailles est par exemple égale à la taille de la représentation binaire de la clé privée, et
- une section 22'b pour transformer chaque bloc binaire D1 à l'aide d'un paramètre de protection a et, pour chaque bloc binaire transformé D',, effectuer un calcul intermédiaire à l'aide de la primitive.
Contrairement au dispositif 12', dans ce dispositif 12" le générateur de données pseudo aléatoires 20 de type classique est remplacé par un générateur de données 20" qui comporte : - une section 20"a d'application d'une fonction F prédéfinie à au moins un paramètre secret prédéterminé S pour la génération d'une séquence de valeurs déterminable uniquement à partir de ce paramètre secret et de cette fonction F, et
- une section 20"b de fourniture d'au moins un paramètre de protection a de façon reproductible à partir d'une valeur de cette séquence.
La section 20"a est en fait une implémentation logicielle ou matérielle de la fonction F.
Le paramètre secret S est stocké dans la mémoire sécurisée 16 et fourni en entrée de la section 20"a du générateur 20", tandis que le paramètre de protection a est fourni, en sortie de la section 20"b, à la section de contre-mesure 22'.
Dans ce second mode de réalisation, le paramètre a n'est donc pas un aléa au sens classique mentionné dans les documents de l'état de la technique. Il s'agit d'un résultat déterministe issu du calcul de la fonction F exécuté par le générateur 20" sur au moins un paramètre secret S qui peut être propre à la carte à puce 30 sur laquelle est disposé le microcircuit 12'. Ce paramètre secret est par exemple dérivé d'une donnée publique du dispositif 30.
L'application répétée de la fonction F à S génère une séquence (An) dont les éléments sont à l'origine du(des) paramètre(s) de protection fourni(s) par le générateur. D'une façon générale, le générateur peut fournir autant de paramètres a issus de valeurs de la séquence (An) que nécessaire en fonction de l'application de contre-mesure implémentée dans la carte 30. Cette séquence (An) ne peut être reproduite qu'avec la connaissance de la fonction génératrice F et des éléments déterministes initiaux qu'elle utilise (le paramètre S).
Chaque paramètre de protection a peut être directement issu d'un élément An de la séquence (An) : en d'autres termes, a = An. De façon alternative, l'élément An peut subir un traitement avant de fournir le paramètre a. Par exemple a peut être le résultat d'un calcul a = An XOR kn, où kn est une constante secrète de transformation.
Bien entendu, si la séquence (An) est cyclique et/ou opère dans un ensemble fini d'éléments, l'espace des valeurs An générées devra être suffisamment grand pour résister aux attaques. En effet plus l'espace considéré est grand, meilleure est la robustesse de la contre-mesure. Nous allons dans un premier temps présenter plusieurs exemples non limitatifs de séquences de valeurs (An) pouvant être fournies par un générateur 20" selon le deuxième mode de réalisation de l'invention. Dans un deuxième temps, nous exposerons plusieurs utilisations possibles de telles séquences de valeurs pour la fourniture de paramètres de protection notamment aux cinq applications de contre-mesure en cryptographie asymétrique précédemment décrites en références aux figures 4 à 8.
Exemples de fonctions génératrices de séquences de valeurs pour la fourniture de paramètres de protection
1 ) Fonctions à base de suites arithmético-géométriques Si l'on définit la séquence de valeurs (An) à l'aide de la fonction F entière à valeurs entières par la relation suivante :
An+1 = F(An) = q.An + r, où q et r sont des paramètres secrets constituant, avec l'élément initial A0 de la séquence, les paramètres secrets S précédemment cités, on est capable de fournir des paramètres de protection issus d'une suite arithmético- géométrique. Les paramètres de protection sont par exemple les éléments de la séquence (An). Si r = 0, il s'agit d'une séquence géométrique dont on peut retrouver un terme Aj, utilisé à une étape précise de la cryptographie, à l'aide des paramètres secrets q et A0 de la façon suivante : A; = q'.Ao.
Si q = 1 , il s'agit d'un séquence arithmétique dont on peut retrouver un terme A1 à l'aide des paramètres secrets r et A0 de la façon suivante : A; = r.i
+ A0-
Si r est non nul et q différent de 1 , il s'agit d'une séquence arithmético-géométrique dont on peut retrouver un terme A1 à l'aide des paramètres secrets q, r et A0 de la façon suivante : Λ = q'Λ + r.(q'-iy(q-1 ).
On peut aussi réduire l'espace des éléments de la séquence (An) par un nombre entier m à l'aide de la relation suivante : An+1 = F(An) modulo m = (q.An + r) modulo m.
On remarque que si m est un nombre premier, cette séquence prend la forme du groupe des transformations affines inversibles sur le corps fini
GF(m) = {0, 1 m-1}.
On peut aussi choisir m comme une puissance de 2, pour générer des séquences d'éléments à nombre de bits constant. Par exemple, si l'on veut générer des séquences de paramètres A; à k bits, on choisit m = 2k. De préférence, m fait partie des paramètres secrets à conserver dans la mémoire sécurisée du dispositif.
2) Fonctions définissant un groupe multiplicatif cyclique Soit un groupe cyclique GC à m éléments avec une valeur a comme élément générateur et la multiplication comme loi de composition interne : GC = {a, a2 am}. On peut définir la séquence de valeurs (An) de la façon suivante :
- l'élément initial A0 est choisi comme étant l'élément générateur a auquel on applique k fois la loi de composition interne du groupe GC,
- on passe de l'élément A1 à l'élément A1+1 en appliquant k' fois la loi de composition interne du groupe GC.
Les paramètres secrets S utilisés par la fonction génératrice de la séquence (An) sont alors par exemple l'élément générateur a et les valeurs k, k' et m. De plus, comme précédemment, Les paramètres de protection générés sont par exemple les éléments de la séquence (An). 3) Fonctions définissant un groupe de Frobenius
Soit un corps fini GF(q), où l'ordre q est un nombre premier de k bits. Le groupe des transformations affines inversibles sur ce corps fini est un groupe de Frobenius. Une propriété intéressante des groupes de Frobenius est qu'aucun élément non trivial ne fixe plus d'un point.
Dans ce contexte, les transformations affines utilisables prennent la forme de fonctions y = f(x) = b.x + c, où b ≠ 0 et où les opérations se font dans le corps GF(q). Il est donc possible de définir une fonction génératrice de la séquence (An) s'appliquant à des paramètres secrets q, b, c et A0 prédéterminés. En choisissant par exemple q = 216 + 1 et, en notation hexadécimale, b = 0x4cd3, c = 0x76bb, A0 = 0xef34, on obtient une séquence commençant par les termes A1 = Oxcθcf, A2 = Oxδbaf, A3 = 0x620d, A4 = 0x0605, A5 = 0xe70c, A6 = 0x3049, A7 = 0xe069, A8 = 0x55ee, etc.
4) Fonctions issues d'un registre à décalage avec rétroaction linéaire (registre de type LFSR)
II s'agit pour ce type de fonctions de choisir un paramètre secret A0, par exemple de 16 bits, et un registre à décalage LFSR, par exemple avec une sortie correspondante de 16 bits. Si la taille du registre LFSR est m, alors un terme At+m de la séquence (An) est déterminé par les m termes qui le précèdent à l'aide d'une équation linéaire du type :
At+m = αm.A, + + ... + Cx1.At+0Vi, où les α, prennent la valeur 0 ou 1 .
5) Fonctions définissant un calcul de Contrôle de Redondance Cyclique (CRC)
II s'agit pour ce type de fonctions de choisir un paramètre secret A0, par exemple de 16 bits, et un polynôme CRC correspondant parmi ceux utilisés de façon classique dans les calculs de CRC, par exemple le polynôme CRC-16 (X16 + X15 + X2 + 1 ) ou le polynôme CRC CCITT V41 (X16 + X12 + X5 + 1 ). Un terme An+1 de la séquence (An) est déterminé en fonction du terme précédent An par la relation An+1 = F(An), où F réalise un calcul de CRC sur la base du polynôme choisi. 6) Combinaisons de séquences de valeurs
II est en effet aussi possible de calculer plusieurs séquences de valeurs, chacune par exemple selon l'une des méthodes exposées ci- dessus, et de les combiner à l'aide d'une fonction prédéfinie pour générer une nouvelle séquence de valeurs à utiliser comme paramètres de protection. On génère ainsi la séquence (An), d'après deux autres séquences (A'n) et (A"n), en calculant pour chaque indice n, An = T(A'n, A"n). La fonction T en question peut être une matrice secrète de valeurs, les valeurs A'n et A"n désignant alors respectivement une ligne et une colonne de cette matrice.
7) Combinaisons impliquant une séquence de valeurs et des données publiques
La séquence (An) peut être générée à partir d'une première séquence (A'n), en fonction également de données publiques, telles que par exemple des données utilisées pendant l'exécution de l'application de cryptographie avec contre-mesure et non secrètes. Parmi ces données, selon les applications, on peut citer le message M (en clair ou crypté), une clé publique e, etc. Les valeurs de la séquence utilisées comme paramètres de protection sont alors calculées à l'aide d'une fonction COMB quelconque combinant toutes ces données :
An = COMB(A' n, M, e, ...). Un intérêt de cette combinaison est que la séquence de valeurs (An) peut servir, non seulement à alimenter en paramètres de protection l'application de contre-mesure de l'algorithme de cryptographie, mais aussi à détecter des attaques par injection de fautes (notamment sur les données publiques). En effet par régénération de la séquence (A'n) à l'aide du ou des paramètre(s) secret(s), en fin d'exécution de l'algorithme de cryptographie par exemple, mais avant de faire l'opération inverse de la transformation initiale en utilisant un paramètre de protection régénéré, puis par utilisation de cette séquence (A'n) régénérée et des données publiques telles qu'elles apparaissent en fin d'exécution, on peut vérifier si l'application de la fonction COMB produit la même séquence de valeurs (An) ou non et donc si des données publiques ont été affectées ou pas en cours d'exécution.
Exemples d'utilisation d'une séquence de valeurs générée selon l'une des méthodes précédentes dans un procédé de contre-mesure en cryptographie asymétrique, selon le deuxième mode de réalisation de l'invention
1 ) Principe général du second mode de réalisation D'une façon générale, chaque fois qu'une contre-mesure algorithmique est utilisée, la génération d'aléas introduits par la contre- mesure est préconisée, comme cela a été décrit dans le premier mode de réalisation utilisant un générateur de données pseudo aléatoires 20. Comme mentionné en référence à la figure 9, cette génération d'aléas peut être remplacée par la génération non aléatoire de paramètres issus d'une ou plusieurs séquence(s) de valeurs obtenue(s) à l'aide d'au moins un paramètre secret.
La figure 10 illustre un exemple d'étapes réalisées par un procédé selon le second mode de réalisation de la figure 9, appliqué à l'exécution d'un algorithme de cryptographie asymétrique avec contre-mesure, utilisant T paramètres de protection a,, ... aτ par exécution, tous les paramètres de protection pouvant être extraits d'une même séquence de valeurs (An) générée par la section 20'a.
Lors d'une première étape INIT réalisée par le générateur 20", un compteur i est initialisé à 0. Ce compteur i est destiné à conserver en mémoire le nombre de fois que l'algorithme de cryptographie asymétrique a été exécuté depuis cette étape d'initialisation INIT, tant qu'une autre initialisation n'est pas réalisée.
Au cours de cette étape, le paramètre secret S (ou les paramètres S lorsqu'il y en a plusieurs), à partir duquel la séquence de valeurs doit être générée, est défini. Il peut être conservé d'une précédente initialisation, mais peut aussi être généré sur la base d'une nouvelle valeur à l'occasion de cette initialisation. Il est par exemple généré à partir de données uniques d'identification, telle qu'une donnée publique du dispositif 30. Il peut aussi être généré à partir de paramètres ou phénomènes physiques liés au microcircuit à un instant donné, qui peuvent être aléatoires. Dans tous les cas, il est conservé en mémoire de façon sécurisée, pour permettre au microcircuit de régénérer à tout moment une même séquence de valeurs (An) à l'aide de la fonction implémentée par la section 20"a. L'étape d'initialisation INIT peut être unique dans le cycle de vie du microcircuit, réalisée lors de la conception par le constructeur, ou reproduite plusieurs fois, par exemple régulièrement ou chaque fois que le compteur i atteint une valeur imax.
Lors d'une première exécution EXE1 de l'algorithme de cryptographie asymétrique avec contre-mesure, le générateur 20", plus particulièrement la section 20"a, est sollicité une ou plusieurs fois pour appliquer le paramètre secret S à la fonction F prédéfinie, de manière à générer, en une ou plusieurs fois, un nombre T d'éléments de la séquence de valeurs (An) : A1, ... Aτ. A partir de ces T premiers éléments, les T paramètres de protection aλ , ... aτ sont générés.
Par exemple, pour tout k tel que 1<k≤T, ak = Ak. En variante, si l'on dispose de T valeurs secrètes supplémentaires SeC1, ... SeC7 parmi les paramètres secrets S conservés en mémoire sécurisée, on peut effectuer le calcul supplémentaire suivant : pour tout k tel que 1<k≤T, ak = Seck XOR Ak, ou ak = Seck ADD Ak, ou bien également ak = Seck SUB Ak, de manière à transformer (ou déformer ou masquer) les paramètres utilisés.
Par la suite, lors d'une i-ème exécution EXEi de l'algorithme de cryptographie avec contre-mesure, le générateur 20", plus particulièrement la section 20"a, est de nouveau sollicité une ou plusieurs fois pour appliquer le paramètre secret S à la fonction F prédéfinie, de manière à générer, en une ou plusieurs fois, un nombre T d'éléments supplémentaires de la séquence de valeurs (An) : AT(M)+1, ... A71. A partir de ces T éléments supplémentaires, les T paramètres de protection a.,, ... aτ sont générés, comme précédemment. Par exemple, pour tout k tel que 1 ≤k≤T, ak = AT(M)+k.
En variante, si l'on dispose des T valeurs secrètes supplémentaires SeC1, ... SeC7, on peut effectuer le calcul supplémentaire suivant : pour tout k tel que 1<k≤T, ak = Seck XOR AT(M)+k> ou ak = Seck ADD AT(i. 1)+k, ou bien également ak = Seck SUB AT(M)+k, de manière à transformer (ou déformer ou masquer) les paramètres utilisés.
Quelle que soit la méthode utilisée pour générer la ou les séquence(s) de valeurs à l'origine des paramètres de protection, la connaissance de la méthode et des valeurs secrètes utilisées par la méthode, y compris le paramètre initial A0 chargé préalablement en mémoire ou lors d'une étape du cycle de vie du dispositif à microcircuit en mémoire EEPROM, permet de retrouver à tout moment les paramètres de protection générés et utilisés dans la vie du dispositif. Il apparaît clairement que cette particularité permet alors des déboguages simples et efficaces ainsi qu'une résistance améliorée aux attaques par injection de fautes. Le choix de la méthode utilisée pour générer la séquence de valeurs et le ou les paramètre(s) de protection est dicté par l'application envisagée.
2) Application du principe général du second mode de réalisation aux cinq procédés décrits en référence aux figures 4 à 8
La méthode utilisée par les premier, second et troisième procédés des figures 4, 5 et 6 pour générer le paramètre de protection a lors des étapes
100, 200, 300 et les paramètres v, r2, r3 lors des étapes 102, 202, 302 peut être l'une de celles préconisées dans le second mode de réalisation. En outre, les paramètres a, v, r2, r3 peuvent avoir la même taille binaire et être issus d'une même séquence de valeurs (T=4). Par ailleurs, il n'est pas utile de conserver ces paramètres en mémoire puisqu'ils peuvent être retrouvés à chaque instant à partir de la séquence de valeurs qui est elle même déterminée par le(s) paramètre(s) secret(s) et la fonction F. C'est ainsi que les paramètres v puis r1 , r2 et r3 peuvent être retrouvés aux étapes 120, 218, 312 sans avoir nécessairement été conservés en mémoire pendant l'exécution de l'exponentiation. A ces étapes 120, 218, 312, le paramètre de protection a peut également être retrouvé pour vérifier que son intégrité a été conservée pendant l'exponentiation.
De même, la méthode utilisée par les quatrième et cinquième procédés des figures 7 et 8 pour générer le paramètre de protection a lors des étapes 400, 500 et le paramètre v lors des étapes 402, 502 peut être l'une de celles préconisées dans le second mode de réalisation. En outre, les paramètres a et v peuvent avoir la même taille binaire et être issus d'une même séquence de valeurs (T=2). Par ailleurs, il n'est pas utile de conserver ces paramètres en mémoire puisqu'ils peuvent être retrouvés à chaque instant à partir de la séquence de valeurs qui est elle même déterminée par le(s) paramètre(s) secret(s) et la fonction F. Ce processus consistant à régénérer ces paramètres est même une étape utile dans la protection de l'implémentation contre les attaques par injection de faute(s). C'est ainsi que le paramètre v puis r peut être retrouvé aux étapes 420, 518 sans avoir nécessairement été conservé en mémoire pendant l'exécution de la multiplication scalaire. A ces étapes 420, 518, le paramètre de protection a peut également être retrouvé pour vérifier que son intégrité, et celle des paramètres utilisés pour le générer, a été conservée pendant la multiplication scalaire.
Une protection supplémentaire peut être ajoutée lors de l'exécution de la boucle de calcul de la primitive, dans chacun des cinq procédés précités. On génère au préalable un paramètre de vérification s selon l'une des méthodes préconisées ci-dessus, ce paramètre venant s'ajouter aux paramètres a et v, M ou a, v, M , r2 et r3. A chaque itération dans cette boucle de calcul, par exemple à l'étape 118 du premier procédé, à l'étape 216 du deuxième procédé, aux étapes 306 et 310 du troisième procédé, à l'étape 418 du quatrième procédé et à l'étape 516 du cinquième procédé, on retrouve s et on extrait de façon déterministe à l'aide du paramètre s des portions d'au moins une partie des représentations binaires ou de représentations selon une autre base b du message M, du module N (dans le cas de RSA ou RSA CRT), de la clé privée d, etc. Ces portions sont alors notées Ms, Ns, ds, etc. et éventuellement combinées pour former une donnée de vérification. Le principe de cette protection est de vérifier qu'à chaque itération, la valeur de la donnée de vérification est inchangée. Si cette donnée de vérification change, les données M, N, d, etc. peuvent être brouillées pour ne pas être découvertes et une alerte peut être déclenchée. D'autres données que M, N et d peuvent être utilisées, à partir du moment où ces données sont utilisées lors de l'exécution de la primitive. II apparaît clairement que les procédés de contre-mesure décrits précédemment permettent de concevoir des applications de cryptographie asymétriques protégeant la clé privée utilisée contre des attaques par canaux auxiliaires, tout en limitant le surcoût en temps de calcul à un niveau très raisonnable. On notera en outre que l'invention n'est pas limitée aux modes de réalisation décrits et que, bien que de nombreuses variantes aient été présentées, d'autres sont également envisageables prévoyant notamment d'autres types de transformations de la clé privée que ceux qui ont été détaillés, ou d'autres applications de cryptographie asymétrique que celles abordées.

Claims

REVENDICATIONS
1. Procédé de contre-mesure dans un composant électronique mettant en œuvre un algorithme de cryptographie asymétrique à clé privée
(d), comprenant les étapes consistant à :
- générer (100 ; 200 ; 300 ; 400 ; 500) un paramètre de protection (a),
- calculer (104 ; 204 ; 304, 308 ; 404 ; 504), à l'aide d'une primitive de l'algorithme de cryptographie, une donnée intermédiaire à partir d'une donnée d'entrée et du paramètre de protection (a), caractérisé en ce qu'il comporte en outre les étapes consistant à :
- diviser (110 ; 206 ; 306, 310 ; 410 ; 506) la représentation binaire de la clé privée (d) en plusieurs blocs binaires,
- transformer (112 ; 210 ; 306, 310 ; 412 ; 510) chaque bloc binaire à l'aide du paramètre de protection (a) et, pour chaque bloc binaire transformé, effectuer (114 ; 212 ; 306, 310 ; 414 ; 512) un calcul intermédiaire à l'aide de la primitive, et
- calculer (106-122 ; 206-220 ; 306, 310, 312, 314 ; 406-422 ; 506- 520) une donnée de sortie par combinaison (116 ; 214 ; 306, 310 ; 416 ; 514) de la donnée intermédiaire avec les calculs intermédiaires (114 ; 212 ; 306, 310 ; 414 ; 512).
2. Procédé de contre-mesure dans un composant électronique selon la revendication 1 , comprenant l'étape consistant à diviser (110 ; 206 ; 306, 310 ; 410 ; 506) la représentation binaire de la clé privée de telle sorte que la taille de chaque bloc binaire (d) soit supérieure ou égale à celle de la représentation binaire du paramètre de protection (a).
3. Procédé de contre-mesure dans un composant électronique selon la revendication 1 ou 2, comprenant l'étape consistant à diviser (110 ; 206 ;
306, 310 ; 410 ; 506) la représentation binaire de la clé privée (d) en plusieurs blocs binaires de telle sorte que la somme des tailles des blocs binaires soit égale à la taille de la représentation binaire de la clé privée.
4. Procédé de contre-mesure dans un composant électronique selon l'une quelconque des revendications 1 à 3, comprenant l'étape consistant à déterminer aléatoirement (110 ; 410) de manière itérative la taille de chaque bloc binaire de telle sorte que la valeur de chaque bloc binaire soit supérieure à la valeur du paramètre de protection (d).
5. Procédé de contre-mesure dans un composant électronique selon l'une quelconque des revendications 1 à 3, comprenant les étapes consistant à :
- choisir la taille k de la représentation binaire du paramètre de protection (a) de telle sorte qu'il existe un entier u>2 tel que n = k.u, n étant la taille de la représentation binaire de la clé privée (d), et - diviser (206 ; 506) la représentation binaire de la clé privée en u blocs binaires de k bits chacun.
6. Procédé de contre-mesure dans un composant électronique selon l'une quelconque des revendications 1 à 5, dans lequel la primitive est une exponentiation modulaire de la donnée d'entrée par la clé privée (d) pour la réalisation d'un algorithme de cryptographie de type RSA ou RSA CRT.
7. Procédé de contre-mesure dans un composant électronique selon la revendication 6, comprenant une étape préalable (102 ; 202 ; 302) consistant à masquer le module RSA et la donnée d'entrée.
8. Procédé de contre-mesure dans un composant électronique selon l'une quelconque des revendications 1 à 5, dans lequel la primitive est une multiplication scalaire de la donnée d'entrée par la clé privée (d), pour la réalisation d'un algorithme de cryptographie basé sur une courbe elliptique dans lequel la donnée d'entrée est un point prédéterminé de la courbe elliptique.
9. Procédé de contre-mesure dans un composant électronique selon la revendication 8, comprenant une étape préalable (402 ; 502) consistant à masquer le point prédéterminé de la courbe elliptique.
10. Procédé de contre-mesure dans un composant électronique selon l'une quelconque des revendications 1 à 9, comportant en outre les étapes consistant à : - générer initialement (102 ; 202 ; 302 ; 402 ; 502), de façon reproductible, au moins un paramètre de vérification avant toute exécution de la primitive,
- régénérer (120, 118 ; 218, 216 ; 312, 306, 310 ; 420, 418 ; 518, 516) ce paramètre de vérification en cours d'exécution ou après exécution de la primitive et comparer le paramètre de vérification régénéré au paramètre de vérification généré initialement.
11. Procédé de contre-mesure dans un composant électronique selon la revendication 10, dans lequel l'étape (118 ; 216 ; 306, 310 ; 418 ; 516) de régénération et de comparaison est exécutée à chaque itération de la primitive lorsqu'elle est appliquée à un bloc binaire transformé.
12. Procédé de contre-mesure dans un composant électronique selon la revendication 10 ou 11 , comprenant l'étape consistant à déclencher une alerte et brouiller au moins la clé privée (d), si l'étape de régénération et de comparaison indique une différence entre le paramètre de vérification généré initialement et le paramètre de vérification régénéré.
13. Procédé de contre-mesure dans un composant électronique selon l'une quelconque des revendications 1 à 12, dans lequel la génération (100, 102 ; 200, 202 ; 300, 302 ; 400, 402 ; 500, 502) du paramètre de protection et/ou du paramètre de vérification comporte les étapes consistant à :
- définir une fonction (20"a) génératrice, par applications successives à au moins un paramètre secret (S) prédéterminé et stocké en mémoire (16), d'une séquence de valeurs ((An)) déterminable uniquement à partir de ce paramètre secret (S) et de cette fonction (20"a),
- générer le paramètre de protection (a) et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette séquence.
14. Procédé de contre-mesure dans un composant électronique selon la revendication 13, comportant les étapes consistant à :
- définir une pluralité de fonctions, chaque fonction étant génératrice, par applications successives à au moins un paramètre secret (S) correspondant prédéterminé et stocké en mémoire (16), d'une séquence de valeurs ((A'n), (A"n)) correspondante déterminable uniquement à partir du paramètre secret (S) correspondant et de la fonction correspondante,
- combiner la pluralité de séquences de valeurs ((A1J, (A"n)) générées à l'aide d'une relation prédéfinie pour générer une nouvelle séquence de valeurs ((An)),
- générer le paramètre de protection (a) et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette nouvelle séquence ((An)).
15. Procédé de contre-mesure dans un composant électronique selon la revendication 13, comportant les étapes consistant à :
- définir une fonction génératrice, par applications successives à au moins un paramètre secret (S) prédéterminé et stocké en mémoire (16), d'une séquence de valeurs ((A'n)) déterminable uniquement à partir du paramètre secret (S) et de la fonction,
- combiner la séquence de valeurs ((A1J) générées avec des paramètres publics de l'algorithme de cryptographie pour générer une nouvelle séquence de valeurs ((An)),
- générer le paramètre de protection (a) et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette nouvelle séquence ((An)).
16. Dispositif à microcircuit (12', 12"), comprenant un microprocesseur (18) pour la mise en œuvre d'un procédé de contre-mesure d'un algorithme de cryptographie asymétrique à clé privée (d), au moins une mémoire sécurisée (16) pour le stockage de la clé privée (d), et un générateur de données (20, 20") pour la génération d'un paramètre de protection (a), caractérisé en ce qu'il est configuré pour :
- calculer (104 ; 204 ; 304, 308 ; 404 ; 504), à l'aide d'une primitive de l'algorithme de cryptographie, une donnée intermédiaire à partir d'une donnée d'entrée et du paramètre de protection (a),
- diviser (110 ; 206 ; 306, 310 ; 410 ; 506) la représentation binaire de la clé privée (d) en plusieurs blocs binaires,
- transformer (112 ; 210 ; 306, 310 ; 412 ; 510) chaque bloc binaire à l'aide du paramètre de protection (a) et, pour chaque bloc binaire transformé, effectuer (114 ; 212 ; 306, 310 ; 414 ; 512) un calcul intermédiaire à l'aide de la primitive, - calculer (106-122 ; 206-220 ; 306, 310, 312, 314 ; 406-422 ; 506- 520 ) une donnée de sortie par combinaison (116 ; 214 ; 306, 310 ; 416 ; 514) de la donnée intermédiaire avec les calculs intermédiaires (114 ; 212 ; 306, 310 ; 414 ; 512).
17. Dispositif à microcircuit (12', 12") selon la revendication 16, dans lequel le microprocesseur (18) est configuré pour déterminer aléatoirement (110 ; 410) de manière itérative la taille de chaque bloc binaire de telle sorte que la valeur de chaque bloc binaire soit supérieure à la valeur du paramètre de protection (d).
18. Dispositif à microcircuit (12', 12") selon la revendications 16, dans lequel le générateur de données (20, 20") est configuré pour choisir la taille k de la représentation binaire du paramètre de protection (a) de telle sorte qu'il existe un entier u>2 tel que n = k.u, n étant la taille de la représentation binaire de la clé privée (d), et dans lequel le microprocesseur (18) est configuré pour diviser (206 ; 506) la représentation binaire de la clé privée en u blocs binaires de k bits chacun.
19. Dispositif à microcircuit (12', 12") selon l'une quelconque des revendications 16 à 18, dans lequel la primitive est une exponentiation modulaire de la donnée d'entrée par la clé privée (d) pour la réalisation d'un algorithme de cryptographie de type RSA ou RSA CRT.
20. Dispositif à microcircuit (12', 12") selon l'une quelconque des revendications 16 à 18, dans lequel la primitive est une multiplication scalaire de la donnée d'entrée par la clé privée (d), pour la réalisation d'un algorithme de cryptographie basé sur une courbe elliptique dans lequel la donnée d'entrée est un point prédéterminé de la courbe elliptique.
21. Dispositif à microcircuit (12', 12") selon l'une quelconque des revendications 16 à 20, configuré pour en outre générer initialement (102 ; 202 ; 302 ; 402 ; 502), de façon reproductible, au moins un paramètre de vérification avant toute exécution de la primitive, régénérer (120, 118 ; 218, 216 ; 312, 306, 310 ; 420, 418 ; 518, 516) ce paramètre de vérification en cours d'exécution ou après exécution de la primitive et comparer le paramètre de vérification régénéré au paramètre de vérification généré initialement.
22. Dispositif à microcircuit (12', 12") selon l'une quelconque des revendications 16 à 21 , dans lequel le générateur de données (20") est configuré pour générer (100, 102 ; 200, 202 ;,300, 302 ; 400, 402 ; 500, 502) le paramètre de protection et/ou le paramètre de vérification en :
- définissant une fonction (20"a) génératrice, par applications successives à au moins un paramètre secret (S) prédéterminé et stocké en mémoire (16), d'une séquence de valeurs ((An)) déterminable uniquement à partir de ce paramètre secret (S) et de cette fonction (20"a), et
- générant le paramètre de protection (a) et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette séquence.
23. Dispositif à microcircuit (12', 12") selon la revendication 22, dans lequel le générateur de données (20") est configuré pour :
- définir une pluralité de fonctions, chaque fonction étant génératrice, par applications successives à au moins un paramètre secret (S) correspondant prédéterminé et stocké en mémoire (16), d'une séquence de valeurs ((A'n), (A"J) correspondante déterminable uniquement à partir du paramètre secret (S) correspondant et de la fonction correspondante,
- combiner la pluralité de séquences de valeurs ((A'n), (A"n)) générées à l'aide d'une relation prédéfinie pour générer une nouvelle séquence de valeurs ((An)),
- générer le paramètre de protection (a) et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette nouvelle séquence ((An)).
24. Dispositif à microcircuit (12', 12") selon la revendication 22, dans lequel le générateur de données (20") est configuré pour :
- définir une fonction génératrice, par applications successives à au moins un paramètre secret (S) prédéterminé et stocké en mémoire (16), d'une séquence de valeurs ((A1J) déterminable uniquement à partir du paramètre secret (S) et de la fonction, - combiner la séquence de valeurs ((A'n)) générées avec des paramètres publics de l'algorithme de cryptographie pour générer une nouvelle séquence de valeurs ((An)),
- générer le paramètre de protection (a) et/ou le paramètre de vérification de façon reproductible à partir d'au moins une valeur de cette nouvelle séquence ((An)).
25. Dispositif portable, notamment carte à puce (30), comprenant un dispositif à microcircuit (12', 12") selon l'une quelconque des revendications 16 à 24.
EP09719837A 2008-01-23 2009-01-23 Procede et dispositifs de contre-mesure pour cryptographie asymetrique Withdrawn EP2248009A2 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0800344A FR2926651B1 (fr) 2008-01-23 2008-01-23 Procede et dispositifs de contre-mesure pour cryptographie asymetrique
PCT/FR2009/000071 WO2009112686A2 (fr) 2008-01-23 2009-01-23 Procede et dispositifs de contre-mesure pour cryptographie asymetrique

Publications (1)

Publication Number Publication Date
EP2248009A2 true EP2248009A2 (fr) 2010-11-10

Family

ID=39731064

Family Applications (1)

Application Number Title Priority Date Filing Date
EP09719837A Withdrawn EP2248009A2 (fr) 2008-01-23 2009-01-23 Procede et dispositifs de contre-mesure pour cryptographie asymetrique

Country Status (8)

Country Link
US (1) US20110274271A1 (fr)
EP (1) EP2248009A2 (fr)
JP (1) JP2011510578A (fr)
KR (1) KR20100113130A (fr)
CN (1) CN101925875A (fr)
CA (1) CA2712178A1 (fr)
FR (1) FR2926651B1 (fr)
WO (1) WO2009112686A2 (fr)

Families Citing this family (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2367316B1 (fr) * 2010-03-12 2017-07-05 STMicroelectronics (Rousset) SAS Procédé et circuit pour détecter une attaque par injection d'une faute
KR101344402B1 (ko) * 2010-08-12 2013-12-26 한국전자통신연구원 Ｒｓａ 서명 방법 및 장치
KR101297966B1 (ko) * 2011-12-14 2013-08-19 (주)엠씨씨 이.씨.씨. 알고리즘을 이용한 암호화 방법
CN104836808B (zh) * 2015-05-12 2017-12-15 中国科学院软件研究所 基于改进差分错误攻击的sm2签名算法安全性验证方法
US9965378B1 (en) * 2016-03-29 2018-05-08 Amazon Technologies, Inc. Mediated fault invocation service
DE112018002723B4 (de) * 2017-05-26 2023-12-14 Microchip Technology Incorporated System, verfahren und vorrichtung zur verschleierung von vorrichtungsoperationen
DE102017117899A1 (de) * 2017-08-07 2019-02-07 Infineon Technologies Ag Durchführen einer kryptografischen Operation
KR102006222B1 (ko) * 2018-01-05 2019-08-01 금오공과대학교 산학협력단 타원곡선 암호와 rsa 공개키 암호를 통합 구현하기 위한 연산장치 및 방법
CN109471610B (zh) * 2018-10-25 2021-03-19 北京链化未来科技有限公司 一种串行随机数生成方法、装置和存储介质
FR3095709B1 (fr) * 2019-05-03 2021-09-17 Commissariat Energie Atomique Procédé et système de masquage pour la cryptographie
WO2023155128A1 (fr) * 2022-02-18 2023-08-24 Oppo广东移动通信有限公司 Procédé de génération de clé, procédé de vérification d'informations et dispositifs
CN114692553B (zh) * 2022-03-30 2025-09-16 广州万协通信息技术有限公司 一种多轻量处理器使用单一指令存储器实现非对称算法多核并行架构的系统

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
ATE325478T1 (de) * 1998-01-02 2006-06-15 Cryptography Res Inc Leckresistentes kryptographisches verfahren und vorrichtung
IL139935A (en) * 1998-06-03 2005-06-19 Cryptography Res Inc Des and other cryptographic processes with leak minimization for smartcards and other cryptosystems
US6970562B2 (en) * 2000-12-19 2005-11-29 Tricipher, Inc. System and method for crypto-key generation and use in cryptosystem
WO2004051920A1 (fr) * 2002-12-03 2004-06-17 Matsushita Electric Industrial Co., Ltd. Systeme de partage de cle, dispositif de creation de cle partagee et dispositif de retablissement de cle partagee
GB2399904B (en) * 2003-03-28 2005-08-17 Sharp Kk Side channel attack prevention in data processing apparatus
US7594275B2 (en) * 2003-10-14 2009-09-22 Microsoft Corporation Digital rights management system
JP5179358B2 (ja) * 2005-06-29 2013-04-10 イルデト アイントホーフェン ベー フェー 攻撃又は解析に対してデータ処理装置を保護するための装置及び方法
US8015409B2 (en) * 2006-09-29 2011-09-06 Rockwell Automation Technologies, Inc. Authentication for licensing in an embedded system

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO2009112686A2 *

Also Published As

Publication number Publication date
WO2009112686A2 (fr) 2009-09-17
WO2009112686A3 (fr) 2010-01-14
US20110274271A1 (en) 2011-11-10
CN101925875A (zh) 2010-12-22
FR2926651B1 (fr) 2010-05-21
KR20100113130A (ko) 2010-10-20
JP2011510578A (ja) 2011-03-31
FR2926651A1 (fr) 2009-07-24
CA2712178A1 (fr) 2009-09-17

Similar Documents

Publication Publication Date Title
EP2248009A2 (fr) Procede et dispositifs de contre-mesure pour cryptographie asymetrique
EP2215768B1 (fr) Procede et dispositifs de protection d&#39;un microcircuit contre des attaques visant a decouvrir une donnee secrete
EP2248008A2 (fr) Procede et dispositifs de contre-mesure pour cryptographie asymetrique a schema de signature
EP2492804B1 (fr) Procédé de cryptographie comprenant une opération d&#39;exponentiation
EP2296086B1 (fr) Protection d&#39;une génération de nombres premiers contre des attaques par canaux cachés
EP1224765B1 (fr) Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie a cle publique de type rsa
EP0909495B1 (fr) Procede de cryptographie a cle publique
EP2983083B1 (fr) Procede de cryptographie sur courbe elliptique comprenant une detection d&#39;erreur
FR3145995A1 (fr) Procédé de séléction d’une valeur parmi deux valeurs enregistrées dans deux registres différents
WO2007006810A1 (fr) Procede cryptographique pour la mise en oeuvre securisee d&#39;une exponentiation et composant associe
FR2979725A1 (fr) Procede de calculs cryptographique resistant aux defaillances materielles
EP0980607A1 (fr) Generateur pseudo-aleatoire base sur une fonction de hachage pour systemes cryptographiques necessitant le tirage d&#39;aleas
EP1829279B1 (fr) Procédé et dispositif de génération de clé pour un algorithme cryptographique
WO2006103149A1 (fr) Procede et dispositif cryptographique permettant de proteger les logiques de cles publiques contre les attaques par faute
FR3018372A1 (fr) Generation de message pour test de generation de cles cryptographiques
WO2014096363A1 (fr) Generateur de sequences chaotiques
FR2818846A1 (fr) Procede de contre-mesure dans un composant electronique mettant en oeuvre un algorithme de cryptographie
FR3082333A1 (fr) Procede de determination d’inverse modulaire et dispositif de traitement cryptographique associe
WO2009068658A1 (fr) Procedes et dispositifs de cryptage et de decryptage d&#39;un message de donnees a cle secrete aleatoire
Zapalowicz Security of the pseudorandom number generators and implementations of public key signature schemes
FR2922067A1 (fr) Calcul de preuve d&#39;appartenance d&#39;un secret a un intervalle, mettant en oeuvre une decomposition binaire.
WO2003069841A1 (fr) Procede de detection des attaques par mise en defaut contre les algorithmes cryptographiques
EP2173056A1 (fr) Procédé de contre-mesure dans un composant électronique mettant en ouvre un algorithme de cryptographie à clef secrète
Zeitoun Algebraic methods for security analysis of cryptographic algorithms implementations
FR2984548A1 (fr) Procede de generation de nombres premiers prouves adapte aux cartes a puce

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20100813

AK Designated contracting states

Kind code of ref document: A2

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC MK MT NL NO PL PT RO SE SI SK TR

AX Request for extension of the european patent

Extension state: AL BA RS

RIN1 Information on inventor provided before grant (corrected)

Inventor name: NEROT, SEBASTIEN

Inventor name: FEIX, BENOIT

Inventor name: BENTEO, BRUNO

DAX Request for extension of the european patent (deleted)
RAP1 Party data changed (applicant data changed or rights of an application transferred)

Owner name: INSIDE SECURE

17Q First examination report despatched

Effective date: 20120312

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 20120925