FR3143243A1

FR3143243A1 - MESSAGE SIGNATURE AND DECRYPTION SECURED BY DOUBLE RSA-CRT

Info

Publication number: FR3143243A1
Application number: FR2213110A
Authority: FR
Inventors: Luk Bettale; Nicolas DEBANDE; Christophe Giraud; Nathan REBOUD
Original assignee: Idemia France SAS
Current assignee: Idemia France SAS
Priority date: 2022-12-09
Filing date: 2022-12-09
Publication date: 2024-06-14

Abstract

La présente invention concerne la sécurisation de traitements cryptographiques basés sur l’algorithme RSA-CRT utilisés pour signer ou déchiffrer un message m. Une double exécution de l’algorithme RSA-CRT est effectuée, suivie d’une vérification de la cohérence entre les résultats S et S’ obtenus, et de l’émission d’un des résultats en cas de vérification positive. Pour se prémunir d’une double injection de faute identique, l’invention prévoit que les exponentiations modulaires de même module des deux exécutions de l’algorithme RSA-CRT soient effectuées sur des messages différents basés sur m et/ou à l’aide d’exposants modulaires différents. Typiquement, S = md mod N en utilisant le RSA-CRT et S’ = md+1 mod N en utilisant les exposants dp+1 et dq+1. Si S’=m.S mod N, alors la donnée S est retournée en sortie. En variante, S’ = m2d mod N ou m2d+1 mod N ou m2(d+2) mod N ou encore (-m2)d mod N. [Fig. 3]The present invention relates to securing cryptographic processing based on the RSA-CRT algorithm used to sign or decrypt a message m. A double execution of the RSA-CRT algorithm is carried out, followed by a verification of the consistency between the results S and S' obtained, and the emission of one of the results in the event of a positive verification. To protect against a double injection of identical fault, the invention provides that the modular exponentiations of the same module of the two executions of the RSA-CRT algorithm are carried out on different messages based on m and/or using d different modular exhibitors. Typically, S = md mod N using RSA-CRT and S’ = md+1 mod N using the exponents dp+1 and dq+1. If S’=m.S mod N, then the data S is returned as output. Alternatively, S’ = m2d mod N or m2d+1 mod N or m2(d+2) mod N or even (-m2)d mod N. [Fig. 3]

Description

MESSAGE SIGNATURE AND DECRYPTION SECURED BY DOUBLE RSA-CRT

FIELD OF INVENTION

La présente invention concerne de façon générale le domaine de la cryptographie, et plus particulièrement la sécurisation de l’algorithme RSA – Rivest-Shamir-Adleman – utilisant le théorème des restes chinois – CRT (pour Chinese Remainder Theorem), utilisé pour la signature ou le déchiffrement d’un message.The present invention generally concerns the field of cryptography, and more particularly the securing of the RSA – Rivest-Shamir-Adleman – algorithm using the Chinese Remainder Theorem – CRT (for Chinese Remainder Theorem), used for signature or deciphering a message.

CONTEXTE DE L’INVENTIONBACKGROUND OF THE INVENTION

Les procédés cryptographiques à clé publique, tels le chiffrement RSA, sont utilisés pour chiffrer un message soit par la clé privée pour obtenir une signature numérique S du message vérifiable avec la clé publique, soit par la clé publique pour obtenir un message chiffré qui est déchiffrable avec la clé privée. Ils sont généralement mis en œuvre dans des systèmes cryptographiques sécurisés, tels des cartes à puce, des éléments sécurisés, des serveurs sécurisés.Public key cryptographic processes, such as RSA encryption, are used to encrypt a message either by the private key to obtain a digital signature S of the message verifiable with the public key, or by the public key to obtain an encrypted message which is decipherable with the private key. They are generally implemented in secure cryptographic systems, such as smart cards, secure elements, secure servers.

La clé publique est composée d’un module N et d’un exposant public ‘e’. La clé privée est composée du module N et d’un exposant privé ou secret ‘d’. Par construction, d est un inverse modulaire de e.The public key is composed of a module N and a public exponent ‘e’. The private key is composed of the module N and a private or secret exponent ‘d’. By construction, d is a modular inverse of e.

Le théorème des restes chinois ou CRT est utilisé avec l’algorithme RSA pour accélérer le temps de déchiffrement ou de signature. Le CRT est en effet un algorithme permettant de réduire le calcul arithmétique modulaire avec un grand module pour le même calcul pour chaque facteur du module. Le CRT peut ainsi réduire la taille des exposants utilisés dans les calculs, notamment dans l’algorithme RSA. Le chiffrement RSA dans sa version CRT est noté RSA-CRT.The Chinese Remainder Theorem or CRT is used with the RSA algorithm to speed up decryption or signing time. CRT is in fact an algorithm for reducing modular arithmetic calculation with a large module for the same calculation for each factor of the module. The CRT can thus reduce the size of the exponents used in calculations, particularly in the RSA algorithm. RSA encryption in its CRT version is denoted RSA-CRT.

Le chiffrement RSA-CRT pour signature d’un message ou déchiffrement d’un message chiffré s’appuie sur des exposants modulaires privés d_pet d_qconstruits à partir de l’exposant privé d, notamment d_p= d mod(p-1) et d_q= d mod(q-1) où p et q sont des nombres premiers formant le module N (N = p.q). Le chiffrement RSA-CRT réalise deux exponentiations modulaires du message respectivement par l’exposant modulaire d_pbasé sur p et par l’exposant modulaire d_qbasé sur q, puis une recombinaison des deux résultats. Par exemple dans le cas d’une signature d’un message ‘m’ ou du déchiffrement d’un message chiffré noté ‘m’ également :RSA-CRT encryption for signing a message or decrypting an encrypted message relies on private modular exponents d _p and d _q constructed from the private exponent d, in particular d _p = d mod(p- 1) and d _q = d mod(q-1) where p and q are prime numbers forming the module N (N = pq). The RSA-CRT encryption performs two modular exponentiations of the message respectively by the modular exponent d _p based on p and by the modular exponent d _q based on q, then a recombination of the two results. For example in the case of signing an 'm' message or decrypting an encrypted message also denoted 'm':

S_p<- m^dpmod pS _p <- m ^dp mod p

S_q<- m^dqmod qS _q <- m ^dq mod q

S <- CRTRecombine (S_p, S_q, p, q, i_q) où i_q= q^-1mod p.S <- CRTRecombine (S _p , S _q , p, q, i _q ) where i _q = q ^-1 mod p.

Le chiffrement RSA-CRT est très sensible aux attaques par injection de faute, typiquement l’attaque dite de Bellcore. L’attaque de Bellcore est documentée dans la publication "On the Importance of Checking Cryptographic Protocols for Faults” (D. Boneh et al., EUROCRYPT ’97, volume 1233 of LNCS, pages 37–51. Springer, 1997).RSA-CRT encryption is very susceptible to fault injection attacks, typically the so-called Bellcore attack. The Bellcore attack is documented in the publication “On the Importance of Checking Cryptographic Protocols for Faults” (D. Boneh et al., EUROCRYPT ’97, volume 1233 of LNCS, pages 37–51. Springer, 1997).

Notamment, la clé privée utilisée pour la signature RSA-CRT est complètement exposée à partir d'une seule signature erronée obtenue par l’injection d’une faute.In particular, the private key used for the RSA-CRT signature is completely exposed from a single erroneous signature obtained by the injection of a fault.

Un premier niveau de protection contre cette attaque est possible lorsque la clé publique est connue du système cryptographique de chiffrement, en vérifiant simplement que S^e=m c’est-à-dire (m^d)^e = m.A first level of protection against this attack is possible when the public key is known to the cryptographic encryption system, by simply checking that S^e=m, that is to say (m^d)^e = m.

Cependant, l’exposant public e n’est pas toujours connu du système cryptographique. S’il est possible de recalculer l’exposant public e en réalisant l’inversion modulaire de l’exposant privé d, ce calcul est trop coûteux. Néanmoins, la publication US 2009/175441 propose, en , de réaliser une inversion, moins coûteuse, d’exposants modulaires publics e_pet e_qrésultant de l’application du CRT à partir des exposants modulaires privés d_pet d_q. Il reste cependant que les inversions modulaires nécessaires sont généralement coûteuses et difficiles à sécuriser contre les attaques par canaux auxiliaires.However, the public exponent e is not always known to the cryptosystem. If it is possible to recalculate the public exponent e by performing the modular inversion of the private exponent d, this calculation is too costly. Nevertheless, publication US 2009/175441 proposes, in , to carry out a less costly inversion of public modular exponents e _p and e _q resulting from the application of the CRT from the private modular exponents d _p and d _q . However, the required modular inversions are generally expensive and difficult to secure against side-channel attacks.

Aussi, d’autres protections évitant ces inversions d’exposant ont été proposées. Typiquement, l’une d’entre elles effectue le double calcul de la signature et la comparaison de leurs résultats, avant d’émettre en sortie l’un des résultats en cas d’égalité. Néanmoins, comme deux calculs identiques sont réalisés, ce mécanisme de protection ne protège pas le chiffrement contre une double injection de la même faute dans les deux calculs.Also, other protections avoiding these exponent inversions have been proposed. Typically, one of them performs the double calculation of the signature and the comparison of their results, before outputting one of the results in the event of a tie. However, as two identical calculations are carried out, this protection mechanism does not protect the encryption against a double injection of the same fault in the two calculations.

Il existe donc un besoin de sécuriser un système cryptographique mettant en œuvre l’algorithme RSA-CRT de manière sécurisée à faible coût calculatoire.There is therefore a need to secure a cryptographic system implementing the RSA-CRT algorithm in a secure manner at low computational cost.

Dans ce dessein, l’invention propose un nouveau procédé de sécurisation de l’algorithme RSA-CRT pour protéger les exposants modulaires privés d_pet d_qsoit lors d’une signature de message, soit lors d’un déchiffrement de message chiffré. Elle concerne donc un procédé de signature ou déchiffrement, basé sur l’algorithme RSA-CRT, d’un message initial m dans un dispositif électronique, à l’aide d’une clé privée comprenant deux exposants modulaires d_pet d_qassociés à deux nombres premiers distincts p et q, l’algorithme RSA-CRT comprenant une première exponentiation modulaire de module p et une deuxième exponentiation modulaire de module q, le procédé comprenant les étapes suivantes :For this purpose, the invention proposes a new method for securing the RSA-CRT algorithm to protect the private modular exponents d _p and d _q either during message signing or during decryption of an encrypted message. It therefore relates to a signature or decryption method, based on the RSA-CRT algorithm, of an initial message m in an electronic device, using a private key comprising two modular exponents d _p and d _q associated with two distinct prime numbers p and q, the RSA-CRT algorithm comprising a first modular exponentiation of module p and a second modular exponentiation of module q, the method comprising the following steps:

générer une première donnée, S, par une première exécution de l’algorithme RSA-CRT sur m,generate a first piece of data, S, by a first execution of the RSA-CRT algorithm on m,

générer une deuxième donnée, S’, par une deuxième exécution de l’algorithme RSA-CRT sur m, etgenerate a second piece of data, S’, by a second execution of the RSA-CRT algorithm on m, and

émettre un message de sortie basé sur S ou S’, si S est cohérent avec S’.emit an output message based on S or S’, if S is consistent with S’.

L’invention s’appuie sur les propriétés mathématiques de l’algorithme RSA pour effectuer un deuxième calcul RSA-CRT différent et donc résistant à la double injection de la même faute. A cet effet, il est caractérisé en ce que les exponentiations modulaires de même module des première et deuxième exécutions de l’algorithme RSA-CRT sont effectuées sur des messages différents basés sur m et/ou à l’aide d’exposants modulaires différents.The invention relies on the mathematical properties of the RSA algorithm to perform a second RSA-CRT calculation that is different and therefore resistant to double injection of the same fault. For this purpose, it is characterized in that the modular exponentiations of the same module of the first and second executions of the RSA-CRT algorithm are carried out on different messages based on m and/or using different modular exponents.

En effet, le choix d’une modification, entre les deux exécutions, du message sur lequel sont réalisées les exponentiations modulaires ou des exposants modulaires utilisés garantit des exécutions différentes et donc résistantes à une double injection de la même faute. En même temps, il permet de vérifier, via la cohérence entre les deux données S et S’ obtenues, qu’aucune faute n’a été injectée sans besoin de calculs d’inverses modulaires (notamment pour obtenir l’exposant public e ou ses exposants modulaires e_pet e_q) coûteux en ressources.Indeed, the choice of a modification, between the two executions, of the message on which the modular exponentiations are carried out or of the modular exponents used guarantees different executions and therefore resistant to a double injection of the same fault. At the same time, it makes it possible to verify, via the consistency between the two data S and S' obtained, that no fault has been injected without the need for modular inverse calculations (in particular to obtain the public exponent e or its modular exponents e _p and e _q ) resource-intensive.

Corrélativement, l’invention concerne un dispositif électronique pour signature ou déchiffrement, basé sur l’algorithme RSA-CRT, d’un message initial m à l’aide d’une clé privée comprenant deux exposants modulaires d_pet d_qassociés à deux nombres premiers distincts p et q, l’algorithme RSA-CRT comprenant une première exponentiation modulaire de module p et une deuxième exponentiation modulaire de module q, le dispositif électronique comprenant un processeur configuré pour :Correlatively, the invention relates to an electronic device for signature or decryption, based on the RSA-CRT algorithm, of an initial message m using a private key comprising two modular exponents d _p and d _q associated with two distinct prime numbers p and q, the RSA-CRT algorithm comprising a first modular exponentiation of module p and a second modular exponentiation of module q, the electronic device comprising a processor configured to:

émettre un message de sortie basé sur S ou S’, si S est cohérent avec S’,emit an output message based on S or S’, if S is consistent with S’,

le dispositif électronique étant caractérisé en ce que les exponentiations modulaires de même module des première et deuxième exécutions de l’algorithme RSA-CRT sont effectuées sur des messages différents basés sur m et/ou à l’aide d’exposants modulaires différents.the electronic device being characterized in that the modular exponentiations of the same module of the first and second executions of the RSA-CRT algorithm are carried out on different messages based on m and/or using different modular exponents.

Le dispositif électronique est un système cryptographique qui peut préférablement être mis en œuvre par ordinateur. Aussi, l’invention concerne également un support non transitoire lisible par ordinateur stockant un programme qui, lorsqu’il est exécuté par un processeur d’un dispositif électronique de traitement cryptographique, amène le dispositif électronique de traitement cryptographique à effectuer le procédé ci-dessus.The electronic device is a cryptographic system which can preferably be implemented by computer. Also, the invention also relates to a non-transitory computer-readable medium storing a program which, when executed by a processor of an electronic cryptographic processing device, causes the electronic cryptographic processing device to perform the above method .

Des caractéristiques facultatives des modes de réalisation de l’invention sont définies dans les revendications annexées. Certaines de ces caractéristiques sont expliquées ci-dessous en référence à un procédé, tandis qu’elles peuvent être transposées en caractéristiques de dispositif.Optional features of embodiments of the invention are defined in the appended claims. Some of these characteristics are explained below with reference to a process, while they can be translated into device characteristics.

Dans un mode de réalisation, les première et deuxième exécutions de l’algorithme RSA-CRT appellent une même fonction informatique de chiffrement RSA-CRT prenant, en entrées, des messages différents basés sur m et/ou des exposants modulaires de même module qui sont différents. Cette disposition permet avantageusement de sécuriser l’algorithme RSA-CRT sans modifier une implémentation existante de cet algorithme, et par voie de conséquence sans besoin de requalifier ou re-tester une nouvelle fonction.In one embodiment, the first and second executions of the RSA-CRT algorithm call the same RSA-CRT encryption computer function taking, as inputs, different messages based on m and/or modular exponents of the same module which are different. This arrangement advantageously makes it possible to secure the RSA-CRT algorithm without modifying an existing implementation of this algorithm, and consequently without the need to requalify or re-test a new function.

Dans un mode de réalisation, les exponentiations modulaires d’une même exécution sont effectuées sur un message identique. In one embodiment, the modular exponentiations of the same execution are carried out on an identical message .

De même, dans un mode de réalisation, les exposants modulaires des deux exponentiations modulaires de chacune des exécutions sont obtenus par la même fonction (ou transformation) appliquée respectivement à d_pet d_q. Aussi, une fonction/transformation est utilisée pour la première exécution, par exemple la fonction Identité permettant d’appliquer d_pet d_q, et une fonction/transformation différente est utilisée pour la deuxième exécution comme exposé par la suite. Likewise, in one embodiment, the modular exponents of the two modular exponentiations of each of the executions are obtained by the same function (or transformation) applied respectively to d _p and d _q . Also, a function/transformation is used for the first execution, for example the Identity function making it possible to apply d _p and d _q , and a different function/transformation is used for the second execution as explained subsequently .

Dans un mode de réalisation, le message pour les exponentiations modulaires de la première exécution vaut m. Cela permet de construire le message de sortie à partir de la première donnée S issue de la première exécution de l’algorithme RSA-CRT.In one embodiment, the message for the modular exponentiations of the first execution is m. This makes it possible to construct the output message from the first data S resulting from the first execution of the RSA-CRT algorithm.

Dans un mode de réalisation particulier, les exposants modulaires des deux exponentiations modulaires de la première exécution valent respectivement d_pet d_q, et le message de sortie vaut S. Dans ce cas, la première exécution correspond à la signature ou au déchiffrement de m à l’aide de ladite clé privée.In a particular embodiment, the modular exponents of the two modular exponentiations of the first execution are respectively worth d _p and d _q , and the output message is worth S. In this case, the first execution corresponds to the signature or decryption of m using said private key.

Dans une variante, les exposants modulaires des deux exponentiations modulaires de la première exécution valent respectivement d_p-α et d_q-α, avec α un entier positif ou nul, et le message de sortie vaut S.m^α mod N. Le message de sortie n’est ainsi pas directement exposé dès la première exécution.In a variant, the modular exponents of the two modular exponentiations of the first execution are respectively worth d_p-α and d_q-α, with α a positive or zero integer, and the output message is S.m^α mod N. The output message is thus not directly exposed from the first execution.

Dans un mode de réalisation, le message pour les exponentiations modulaires de la deuxième exécution vaut (-1)^j.m^k, avec j et k des entiers positifs, k non nul. Dans ce cas, le message à chiffrer/déchiffrer est modifié lors de la deuxième exécution de l’algorithme RSA-CRT.In one embodiment, the message for the modular exponentiations of the second execution is (-1) ^j .m ^k , with j and k positive integers, k not zero. In this case, the message to be encrypted/decrypted is modified during the second execution of the RSA-CRT algorithm.

En particulier, le message pour les exponentiations modulaires de la deuxième exécution peut valoir m². En variante, le message pour les exponentiations modulaires de la deuxième exécution vaut -(m)². Ces configurations offrent avantageusement une complexité de calcul faible (grâce aux faibles valeurs choisies de j et k) pour un gain sécuritaire notable.In particular, the message for the modular exponentiations of the second execution can be worth m². Alternatively, the message for the modular exponentiations of the second execution is -(m)². These configurations advantageously offer low computational complexity (thanks to the low chosen values of j and k) for a notable security gain.

Dans un mode de réalisation, les exposants modulaires des deux exponentiations modulaires de la deuxième exécution valent respectivement β.d_p+γ et β.d_q+γ, où β est un entier positif non nul et γ un entier. Dans ce cas, les exposants modulaires pour p et q sont modifiés lors de la deuxième exécution de l’algorithme RSA-CRT.In one embodiment, the modular exponents of the two modular exponentiations of the second execution are respectively worth β.d _p +γ and β.d _q +γ, where β is a non-zero positive integer and γ an integer. In this case, the modular exponents for p and q are changed during the second execution of the RSA-CRT algorithm.

En particulier, il peut être choisi que β=1 et γ=1. Ces faibles valeurs offrent avantageusement une complexité de calcul faible pour un gain sécuritaire notable. Bien entendu, d’autres valeurs faibles peuvent être utilisées, par exemple β= 1 ou 2 et γ= 0, 1 ou 2.In particular, it can be chosen that β=1 and γ=1. These low values advantageously offer low computational complexity for a significant security gain. Of course, other low values can be used, for example β= 1 or 2 and γ= 0, 1 or 2.

Dans un mode de réalisation, le procédé comprend une étape de vérification de la cohérence de S’ avec S en comparant S et S’, la comparaison comparant :In one embodiment, the method includes a step of verifying the consistency of S' with S by comparing S and S', the comparison comparing:

S’ à (-1)^j( ^γ ⁺ ^β ⁾.(S.m^α)^k ^. ^β.m^k ^. ^γmod N, avec N=p.q, lorsque le message pour les exponentiations modulaires de la première exécution vaut m et celui pour les exponentiations modulaires de la deuxième exécution vaut (-1)^j.m^k, les exposants modulaires des deux exponentiations modulaires de la première exécution valent respectivement d_p-α et d_q-α et ceux des deux exponentiations modulaires de la deuxième exécution valent respectivement β.d_p+γ et β.d_q+γ, si γ positif, ouS' to (-1) ^j( ^γ ⁺ ^β ⁾ .(Sm ^α ) ^k ^. ^β .m ^k ^. ^γ mod N, with N=pq, when the message for the modular exponentiations of the first execution is worth m and that for the modular exponentiations of the second execution is worth (-1) ^j .m ^k , the modular exponents of the two modular exponentiations of the first execution are respectively worth d _p -α and d _q -α and those of the two modular exponentiations of the second execution are respectively worth β.d _p +γ and β.d _q +γ, if γ positive, or

S’.m^- ^k. ^γmod N à (-1)^j( ^γ ⁺β⁾.(S.m^α)^k ^. ^βmod N, si γ négatif.S'.m ^- ^k. ^γ mod N to (-1) ^j( ^γ ⁺ β ⁾ .(Sm ^α ) ^k ^. ^β mod N, if γ negative.

Il est à noter que l’expression (-1)^j ⁽ ^γ ⁺ ^β ⁾est équivalente à (-1)^j( ^γ ⁺ ^β. ^d)avec d l’exposant privé de la clé de chiffrement RSA-CRT (donc correspondant à d_pet d_q), dans la mesure où d est impair.It should be noted that the expression (-1) ^j ⁽ ^γ ⁺ ^β ⁾ is equivalent to (-1) ^{j (} ^γ ⁺ ^β. ^d) with d the private exponent of the RSA-CRT encryption key (therefore corresponding to d _p and d _q ), to the extent that d is odd.

Dans un mode de réalisation particulier, le procédé comprend une étape de calcul d’une valeur T=S.m^α, etIn a particular embodiment, the method comprises a step of calculating a value T=Sm ^α , and

dans lequel la comparaison compare S’ à (-1)^j( ^γ ^+β).T^k ^. ^β.m^k. ^γmod N, si γ positif, ou S’.m^- ^k. ^γmod N à (-1)^j(γ+β).T^k ^. ^βmod N, si γ négatif,
et l’étape d’émettre un message de sortie comprend l’étape d’émettre la valeur T.in which the comparison compares S' to (-1) ^j( ^γ ^+β) .T ^k ^. ^β .m ^k. ^γ mod N, if γ positive, or S'.m ^- ^k. ^γ mod N to (-1) ^j(γ+β) .T ^k ^. ^β mod N, if γ negative,
and the step of transmitting an output message includes the step of transmitting the T value.

Cette configuration permet de réduire les coûts calculatoires.This configuration makes it possible to reduce computational costs.

Dans un mode de réalisation particulier, la comparaison comprend :In a particular embodiment, the comparison comprises:

le tirage d’un entier aléatoire Rand,drawing a random integer Rand,

le calcul d’une valeur de vérification par l’addition d’un des deux termes à comparer à Rand suivi de la soustraction de l’autre terme à comparer, etcalculating a verification value by adding one of the two terms to be compared to Rand followed by subtraction of the other term to be compared, and

la comparaison de la valeur de vérification avec Rand, la comparaison étant positive en cas d’égalité.the comparison of the verification value with Rand, the comparison being positive in case of equality.

Cette configuration sécurise la comparaison en évitant une comparaison avec 0.This configuration secures the comparison by avoiding a comparison with 0.

Au moins une partie des procédés selon l’invention peut être mise en œuvre par ordinateur. En conséquence, la présente invention peut prendre la forme d’un mode de réalisation entièrement matériel, d’un mode de réalisation entièrement logiciel (comportant les microprogrammes, les logiciels résidents, les microcodes, etc.) ou d’un mode de réalisation combinant des aspects logiciels et matériels qui peuvent tous être globalement appelés ici "circuit", "module" ou "système". De plus, la présente invention peut prendre la forme d’un produit de programme informatique incorporé dans tout support d’expression tangible disposant d’un code de programme utilisable par ordinateur incorporé dans le support.At least part of the methods according to the invention can be implemented by computer. Consequently, the present invention can take the form of an entirely hardware embodiment, an entirely software embodiment (comprising firmware, resident software, microcodes, etc.) or an embodiment combining software and hardware aspects which can all be collectively called here "circuit", "module" or "system". Additionally, the present invention may take the form of a computer program product embodied in any tangible expression medium having computer-usable program code embodied in the medium.

D'autres particularités et avantages de l'invention apparaîtront encore dans la description ci-après, illustrée par les figures ci-jointes qui en illustrent des exemples de réalisation dépourvus de tout caractère limitatif.Other particularities and advantages of the invention will appear further in the description below, illustrated by the attached figures which illustrate examples of embodiment devoid of any limiting character.

La illustre schématiquement les éléments principaux d'une forme de réalisation possible pour une carte à microcircuit ou « carte à puce ».There schematically illustrates the main elements of a possible embodiment for a microcircuit card or “smart card”.

La illustre l'allure physique générale de la carte à microcircuit de la .There illustrates the general physical appearance of the microcircuit card of the .

La illustre, à partir d’un ordinogramme, des étapes générales pour chiffrer (signer) ou déchiffrer un message selon des modes de réalisation de l’invention.There illustrates, from a flowchart, general steps for encrypting (signing) or decrypting a message according to embodiments of the invention.

La illustre un mode de réalisation du procédé de la appelant une même fonction informatique de chiffrement RSA-CRT.There illustrates an embodiment of the method of calling the same RSA-CRT encryption computer function.

La illustre un premier exemple de réalisation calculant séparément S=m^dmod N et S’=m^d+1mod N.There illustrates a first exemplary embodiment separately calculating S=m ^d mod N and S'=m ^d+1 mod N.

La illustre un deuxième exemple de réalisation calculant séparément S=m^dmod N et S’=m^2dmod N.There illustrates a second embodiment separately calculating S=m ^d mod N and S'=m ^2d mod N.

La illustre un troisième exemple de réalisation calculant séparément S=m^dmod N et S’=(-m²)^dmod N.There illustrates a third embodiment separately calculating S=m ^d mod N and S'=(-m ² ) ^d mod N.

La illustre un quatrième exemple de réalisation calculant séparément S=m^dmod N et S’=m^2(d+1)mod N.There illustrates a fourth embodiment separately calculating S=m ^d mod N and S'=m ^2(d+1) mod N.

La illustre un cinquième exemple de réalisation calculant séparément S=m^dmod N et S’=m^2d+1mod N.There illustrates a fifth embodiment separately calculating S=m ^d mod N and S'=m ^2d+1 mod N.

La illustre un sixième de réalisation calculant séparément S=m^d-1mod N et S’=m^2(d+1)mod N.There illustrates a sixth embodiment separately calculating S=m ^d-1 mod N and S'=m ^2(d+1) mod N.

DETAILED DESCRIPTION

La présente invention concerne la sécurisation de traitements cryptographiques basés sur l’algorithme RSA-CRT, pour Rivest-Shamir-Adleman et Théorème des Restes Chinois (« Chinese Remainder Theorem » en langue anglosaxonne).The present invention relates to securing cryptographic processing based on the RSA-CRT algorithm, for Rivest-Shamir-Adleman and Chinese Remainder Theorem.

De façon connue, l’algorithme RSA-CRT est un algorithme de signature/chiffrement par clés asymétriques, basé sur une clé publique (e, N) et une clé privée (p, q, d_p, d_q, i_q) où :In known manner, the RSA-CRT algorithm is an asymmetric key signature/encryption algorithm, based on a public key (e, N) and a private key (p, q, d _p , d _q , i _q ) where :

le module N vaut le produit des grands nombres premiers p et q : N=p.q,the module N is worth the product of the large prime numbers p and q: N=p.q,

e est l’exposant public, choisi entre 1 et Φ=(p-1).(q-1),e is the public exponent, chosen between 1 and Φ=(p-1).(q-1),

d est l’exposant privé calculé par inversion modulaire de e avec le module Φ : d=e^-1mod Φ, c’est-à-dire e.d équivaut à 1 mod Φ,d is the private exponent calculated by modular inversion of e with the module Φ: d=e ^-1 mod Φ, that is to say ed is equivalent to 1 mod Φ,

d_pet d_qsont les exposants modulaires basés respectivement sur p et q : d_p= d mod(p-1) et d_q= d mod(q-1), etd _p and d _q are the modular exponents based on p and q respectively: d _p = d mod(p-1) and d _q = d mod(q-1), and

i_q= q^-1mod p.i _q = q ^-1 mod p.

Cet algorithme peut être utilisé pour chiffrer un message m ou le signer.This algorithm can be used to encrypt a message or sign it.

Lors du chiffrement, Alice chiffre le message m en utilisant l’algorithme RSA avec la clé publique (N, e) de Bob : S = m^emod N. Le message chiffré S est déchiffré par Bob en utilisant l’algorithme RSA avec sa propre clé privée (p, q, d_p, d_q, i_q) : m = S^dmod N. Le Théorème des Restes Chinois permet d’accélérer le temps de ce déchiffrage en utilisant d_pet d_q. Une implémentation possible de la fonction RSA-CRT est la suivante, notée RSA-CRT(S, (p, q, d_p, d_q, i_q)) :During encryption, Alice encrypts the message m using the RSA algorithm with Bob's public key (N, e): S = m ^e mod N. The encrypted message S is decrypted by Bob using the RSA algorithm with its own private key (p, q, d _p , d _q , i _q ): m = S ^d mod N. The Chinese Remainder Theorem makes it possible to accelerate the time of this decryption by using d _p and d _q . A possible implementation of the RSA-CRT function is the following, denoted RSA-CRT(S, (p, q, d _p , d _q , i _q )):

m_p= S^dpmod pm _p = S ^dp mod p

m_q= S^dqmod qm _q = S ^dq mod q

m = CRTRecombine (m_p, m_q, p, q, i_q). Typiquement, CRTRecombine (m_p, m_q, p, q, i_q) = m_q+ q.(i_q.(m_p-m_q) mod p).m = CRTRecombine ( _mp , m _q , p, q, i _q ). Typically, CRTRecombine ( _mp , m _q , p, q, i _q ) = m _q + q.(i _q .(m _p -m _q ) mod p).

De façon symétrique pour la signature du message m, Alice signe le message m en utilisant l’algorithme RSA avec sa propre clé privée (p, q, d_p, d_q, i_q) : S = m^dmod N. Le Théorème des Restes Chinois permet d’accélérer le temps de calcul de la signature en utilisant d_pet d_q, par appel par exemple de la fonction RSA-CRT(m, (p, q, d_p, d_q, i_q)) :Symmetrically for the signature of message m, Alice signs message m using the RSA algorithm with her own private key (p, q, d _p , d _q , i _q ): S = m ^d mod N. The Theorem of Chinese Remainders makes it possible to speed up the signature calculation time by using d _p and d _q , for example by calling the RSA-CRT function (m, (p, q, d _p , d _q , i _q )) :

S_p= m^dpmod pS _p = m ^dp mod p

S_q= m^dqmod qS _q = m ^dq mod q

S = CRTRecombine (S_p, S_q, p, q, i_q). Typiquement, CRTRecombine (S_p, S_q, p, q, i_q) = S_q+ q.(i_q.(S_p-S_q) mod p).S = CRTRecombine (S _p , S _q , p, q, i _q ). Typically, CRTRecombine (S _p , S _q , p, q, i _q ) = S _q + q.(i _q .(S _p -S _q ) mod p).

La signature S est vérifiée par Bob en utilisant l’algorithme RSA avec la clé publique (N, e) d’Alice pour calculer un message m’ : m’ = S^emod N, puis comparer m et m’.The signature S is verified by Bob using the RSA algorithm with Alice's public key (N, e) to calculate a message m': m' = S ^e mod N, then compare m and m'.

Par la suite, les explications et illustrations sont fournies à titre principal en lien avec l’opération de signature du message m. Compte tenu de la symétrie de traitement, celles-ci s’appliquent également au déchiffrement d’un message chiffré par RSA.Subsequently, the explanations and illustrations are provided primarily in connection with the operation of signing the message m. Given processing symmetry, these also apply to the decryption of an RSA-encrypted message.

L’invention vise à sécuriser l’algorithme RSA-CRT exécutée par un dispositif électronique compte des attaques par injection de faute, typiquement des attaques de Bellcore. Cette exécution est obtenue par une double exécution de l’algorithme RSA-CRT dans lesquelles les exponentiations modulaires de même module (p ou q) des deux exécutions de l’algorithme RSA-CRT sont effectuées sur des messages différents basés sur m et/ou à l’aide d’exposants modulaires différents.The invention aims to secure the RSA-CRT algorithm executed by an electronic device against fault injection attacks, typically Bellcore attacks. This execution is obtained by a double execution of the RSA-CRT algorithm in which the modular exponentiations of the same module (p or q) of the two executions of the RSA-CRT algorithm are carried out on different messages based on m and/or using different modular exponents.

Cela peut s’illustrer par deux appels à la fonction RSA-CRT définie ci-dessus où les paramètres sont différents.This can be illustrated by two calls to the RSA-CRT function defined above where the parameters are different.

La cohérence entre les deux résultats obtenus par les deux exécutions est vérifiée, et dans l’affirmative, l’un des résultats est utilisé pour générer un message de sortie représentant la signature souhaitée (ou le message déchiffré).The two results obtained by the two executions are checked for consistency, and if so, one of the results is used to generate an output message representing the desired signature (or decrypted message).

La cohérence entre les deux résultats doit être entendue comme signifiant que ces deux résultats sont liés par une formule. Cela permet de garantir qu’aucune attaque simple ou double attaque identique a eu lieu sur ces exécutions.The consistency between the two results must be understood to mean that these two results are linked by a formula. This ensures that no identical single attacks or double attacks took place on these executions.

La représente, schématiquement, un dispositif électronique de traitement de données 40 formant système cryptographique dans lequel la présente invention peut être mise en œuvre. Ce dispositif 40 comprend un microprocesseur 10, auquel est associée d’une part une mémoire vive 60, par exemple au moyen d'un bus 70, et d’autre part une mémoire non volatile 20 (par exemple du type EEPROM), par exemple à travers un bus 50.There represents, schematically, an electronic data processing device 40 forming a cryptographic system in which the present invention can be implemented. This device 40 comprises a microprocessor 10, with which is associated on the one hand a RAM 60, for example by means of a bus 70, and on the other hand a non-volatile memory 20 (for example of the EEPROM type), for example through a 50 bus.

Le dispositif de traitement de données 40, et précisément le microprocesseur 10 qu'il incorpore, peuvent échanger des données avec des dispositifs extérieurs au moyen d'une interface de communication 30.The data processing device 40, and precisely the microprocessor 10 which it incorporates, can exchange data with external devices by means of a communication interface 30.

On a schématiquement représenté sur la la transmission d’une donnée d'entrée m reçue d'un dispositif extérieur (non représenté) et transmise de l'interface de communication 30 au microprocesseur 10. De manière similaire, on a représenté la transmission d'une donnée de sortie S du microprocesseur 10 vers l'interface de communication 30 à destination d'un dispositif extérieur. Cette donnée de sortie S est issue du traitement de données par le microprocesseur 10, sur la donnée d'entrée m à l'aide d'une clé secrète 80 interne au système, notamment la clé privée (p, q, d), soit (p, q, d_p, d_q, i_q) dans sa forme CRT, et stockée en mémoire.We have schematically represented on the the transmission of an input data m received from an external device (not shown) and transmitted from the communication interface 30 to the microprocessor 10. In a similar manner, the transmission of an output data S from the microprocessor 10 to the communication interface 30 intended for an external device. This output data S comes from the data processing by the microprocessor 10, on the input data m using a secret key 80 internal to the system, in particular the private key (p, q, d), i.e. (p, q, d _p , d _q , i _q ) in its CRT form, and stored in memory.

Bien que, pour l'illustration, les données d'entrée et les données de sortie figurent sur deux flèches différentes, les moyens physiques qui permettent la communication entre le microprocesseur 10 et l'interface 30 pourront être réalisés par des moyens uniques, par exemple un port de communication série ou un bus.Although, for the illustration, the input data and the output data appear on two different arrows, the physical means which allow communication between the microprocessor 10 and the interface 30 could be produced by unique means, for example a serial communications port or bus.

Le microprocesseur 10 est apte à exécuter un logiciel (ou programme d’ordinateur) qui permet au dispositif de traitement de données 40 d'exécuter un procédé conforme à l'invention dont des exemples sont donnés ci-dessous. Le logiciel est composé d'une série d'instructions de commande du microprocesseur 10 qui sont par exemple stockées dans la mémoire 20.The microprocessor 10 is able to execute software (or computer program) which allows the data processing device 40 to execute a method according to the invention, examples of which are given below. The software is composed of a series of instructions for controlling the microprocessor 10 which are for example stored in the memory 20.

En variante, l'ensemble microprocesseur 10 - mémoire non-volatile 20 - mémoire vive 60 peut être remplacé par un circuit à application spécifique qui comprend alors des moyens de mise en œuvre des différentes étapes du procédé selon l’invention.Alternatively, the microprocessor assembly 10 - non-volatile memory 20 - random access memory 60 can be replaced by a specific application circuit which then comprises means for implementing the different stages of the method according to the invention.

La représente une carte à microcircuit qui constitue un exemple de système cryptographique conforme à l'invention tel que représenté à la . L'interface de communication 30 est dans ce cas réalisée au moyen des contacts de la carte à microcircuit. La carte à microcircuit incorpore un microprocesseur 10, une mémoire vive 60 et une mémoire non volatile 20 comme cela est représenté sur la .There represents a microcircuit card which constitutes an example of a cryptographic system according to the invention as represented in . The communication interface 30 is in this case produced by means of the contacts of the microcircuit card. The microcircuit card incorporates a microprocessor 10, a RAM 60 and a non-volatile memory 20 as shown in the figure. .

Cette carte à microcircuit est par exemple conforme à la norme ISO 7816 et munie d’un microcontrôleur sécurisé qui regroupe le microprocesseur (ou CPU) 20 et la mémoire vive 60.This microcircuit card complies, for example, with the ISO 7816 standard and is equipped with a secure microcontroller which brings together the microprocessor (or CPU) 20 and the RAM 60.

En variante, le système cryptographique peut être inclus dans un élément sécurisé SE (pour « Secure Element » en langue anglo-saxonne), une clé USB, un document ou un support d’informations papier comportant dans l’une de ses feuilles un microcircuit associé à des moyens de communication sans contact. Il s’agit de manière préférée d’une entité électronique portable ou de poche. Bien entendu, l’invention s’applique aussi à un système cryptographique équipant un ordinateur personnel, un dispositif mobile (téléphone intelligent, tablette, objet connecté type IOT, ou équivalent) ou un serveur.Alternatively, the cryptographic system can be included in a secure element SE (for “Secure Element” in English), a USB key, a document or a paper information carrier comprising in one of its sheets a microcircuit associated with contactless means of communication. It is preferably a portable or pocket electronic entity. Of course, the invention also applies to a cryptographic system equipping a personal computer, a mobile device (smart phone, tablet, IOT type connected object, or equivalent) or a server.

La illustre, à partir d’un ordinogramme, des étapes générales pour chiffrer (signer) ou déchiffrer un message selon des modes de réalisation de l’invention. Le procédé peut être mis en œuvre par un dispositif électronique ou système cryptographique tel que décrit ci-dessus pour émettre en sortie un message chiffré (signature) ou déchiffré, ou être mis en œuvre par un module logiciel à l’intérieur du dispositif électronique ou système cryptographique pour fournir le message chiffré (signature) ou déchiffré à un autre module logiciel à l’intérieur du dispositif électronique ou système cryptographique.There illustrates, from a flowchart, general steps for encrypting (signing) or decrypting a message according to embodiments of the invention. The method can be implemented by an electronic device or cryptographic system as described above to output an encrypted (signature) or decrypted message, or be implemented by a software module inside the electronic device or cryptographic system for providing the encrypted (signature) or decrypted message to another software module within the electronic device or cryptographic system.

Le procédé débute à l’étape 300 avec le message m à signer et la clé privée (p,q,d_p,d_q,i_q). Les explications ci-dessous sont valables pour un message m à déchiffrer.The process begins at step 300 with the message m to be signed and the private key (p,q,d _p ,d _q ,i _q ). The explanations below are valid for a message m to be decrypted.

L’étape 310 consiste en une première exécution de l’algorithme RSA-CRT par le dispositif électronique pour obtenir une première signature S. Le message utilisé pour les exponentiations modulaires de cette première exécution vaut m.Step 310 consists of a first execution of the RSA-CRT algorithm by the electronic device to obtain a first signature S. The message used for the modular exponentiations of this first execution is worth m.

La première exponentiation modulaire de modulo p 312 utilise l’exposant d_p-α où α est un entier positif (0 ou plus) : S_p= m^dp ^- ^αmod p.The first modular exponentiation of modulo p 312 uses the exponent d _p -α where α is a positive integer (0 or more): S _p = m ^dp ^- ^α mod p.

La deuxième exponentiation modulaire de modulo q 314 utilise l’exposant d_q-α : S_q= m^dq ^- ^αmod q.The second modular exponentiation of modulo q 314 uses the exponent d _q -α: S _q = m ^dq ^- ^α mod q.

Les deux exponentiations peuvent être réalisées en parallèle, ou dans l’ordre inverse de la figure. Les exponentiations modulaires d’une même exécution sont effectuées sur un message identique, ici m. De même, les exposants modulaires des deux exponentiations modulaires de chacune des exécutions sont obtenus par la même fonction ou transformation appliquée respectivement à d_pet d_q, ici par la soustraction de α.The two exponentiations can be carried out in parallel, or in the reverse order of the figure. The modular exponentiations of the same execution are carried out on an identical message, here m. Likewise, the modular exponents of the two modular exponentiations of each of the executions are obtained by the same function or transformation applied respectively to d _p and d _q , here by the subtraction of α.

Une première donnée S est alors obtenue à l’étape 316 par recombinaison CRT des deux résultats S_pet S_qdes exponentiations modulaires 312 et 314. Par exemple, S = S_q+ q.(i_q.(S_p-S_q) mod p).A first piece of data S is then obtained in step 316 by CRT recombination of the two results S _p and S _q of the modular exponentiations 312 and 314. For example, S = S _q + q.(i _q .(S _p -S _q ) mod p).

Cette première donnée S vaut S = m^d- ^αmod N.This first data S is worth S = m ^d- ^α mod N.

De façon similaire, l’étape 320 consiste en une deuxième exécution de l’algorithme RSA-CRT par le dispositif électronique pour obtenir une deuxième signature S’. Selon l’invention, les exponentiations modulaires de cette deuxième exécution utilisent des messages différents basés sur m et/ou des exposants modulaires différents comparativement à la première exécution 310.Similarly, step 320 consists of a second execution of the RSA-CRT algorithm by the electronic device to obtain a second signature S'. According to the invention, the modular exponentiations of this second execution use different messages based on m and/or different modular exponents compared to the first execution 310.

De façon générale, le message pour les exponentiations modulaires de cette deuxième exécution 320 vaut (-1)^j.m^k, avec j et k des entiers, k non nul. Typiquement j peut prendre soit la valeur 0 équivalente à toute valeur paire de j, soit la valeur 1 équivalente à toute valeur impaire de j. k est préférentiellement positif, mais non nécessairement.Generally speaking, the message for the modular exponentiations of this second execution 320 is worth (-1) ^j .m ^k , with j and k integers, k not zero. Typically j can take either the value 0 equivalent to any even value of j, or the value 1 equivalent to any odd value of j. k is preferentially positive, but not necessarily.

Pour s’assurer que les messages et/ou les exposants modulaires utilisés lors des deux exécutions 310 et 320 soient différents, le cas trivial suivant est évité : j=0 (ou pair), k=1, α=-γ, β=1.To ensure that the messages and/or modular exponents used during the two executions 310 and 320 are different, the following trivial case is avoided: j=0 (or even), k=1, α=-γ, β= 1.

La première exponentiation modulaire de modulo p 322 utilise l’exposant β.d_p+γ où β est un entier positif non nul et γ un entier (0 ou plus) : S’_p= ((-1)^j.m^k)^β. ^dp ⁺ ^γmod p.The first modular exponentiation of modulo p 322 uses the exponent β.d _p +γ where β is a non-zero positive integer and γ an integer (0 or more): S' _p = ((-1) ^j .m ^k ) ^β. ^dp ⁺ ^γ mod p.

La deuxième exponentiation modulaire de modulo q 324 utilise l’exposant β.d_q+γ : S’_q= ((-1)^j.m^k)^β. ^dq ⁺ ^γmod q.The second modular exponentiation of modulo q 324 uses the exponent β.d _q +γ: S' _q = ((-1) ^j .m ^k ) ^β. ^dq ⁺ ^γ mod q.

Les deux exponentiations peuvent être réalisées en parallèle, ou dans l’ordre inverse de la figure. Les exponentiations modulaires d’une même exécution sont effectuées sur un message identique, ici (-1)^j.m^k. De même, les exposants modulaires des deux exponentiations modulaires de chacune des exécutions sont obtenus par la même fonction appliquée respectivement à d_pet d_q, ici par la fonction g(d)= β.d+γ.The two exponentiations can be carried out in parallel, or in the reverse order of the figure. The modular exponentiations of the same execution are carried out on an identical message, here (-1) ^j .m ^k . Likewise, the modular exponents of the two modular exponentiations of each of the executions are obtained by the same function applied respectively to d _p and d _q , here by the function g(d)= β.d+γ.

Une deuxième donnée S’ est alors obtenue à l’étape 326 par recombinaison CRT des deux résultats S’_pet S’_qdes exponentiations modulaires 322 et 324. Par exemple, S’ = S’_q+ q.(i_q.(S’_p-S’_q) mod p).A second piece of data S' is then obtained in step 326 by CRT recombination of the two results S' _p and S' _q of the modular exponentiations 322 and 324. For example, S' = S' _q + q.(i _q .( S' _p -S' _q ) mod p).

Cette deuxième donnée S’ vaut S’ = ((-1)^j.m^k)^β.d+ ^γmod N.This second data S' is worth S' = ((-1) ^j .m ^k ) ^β.d+ ^γ mod N.

Les deux exécutions de l’algorithme RSA-CRT 310 et 320 peuvent être réalisées en parallèle, ou dans l’ordre inverse de la figure.The two executions of the RSA-CRT algorithm 310 and 320 can be carried out in parallel, or in the reverse order of the figure.

L’étape 330 consiste à vérifier la cohérence entre les deux données obtenues S et S’ pour s’assurer qu’aucune injection de faute n’a eu lieu pendant les deux exécutions 310 et 320 de l’algorithme RSA-CRT par le dispositif électronique. La cohérence peut être vérifiée en comparant S et S’ selon une fonction de cohérence liée aux paramètres j, k, α, β et γ utilisés. En effet, les modifications proposées de message et/ou d’exposants entre les deux exécutions s’appuient sur les propriétés mathématiques de l’algorithme RSA-CRT afin de permettre une vérification finale mathématique.Step 330 consists of checking the consistency between the two data obtained S and S' to ensure that no fault injection has taken place during the two executions 310 and 320 of the RSA-CRT algorithm by the device electronic. Coherence can be checked by comparing S and S’ according to a coherence function linked to the parameters j, k, α, β and γ used. Indeed, the proposed modifications of message and/or exponents between the two executions rely on the mathematical properties of the RSA-CRT algorithm in order to allow a final mathematical verification.

Dans un mode de réalisation, la vérification comprend la comparaison de :In one embodiment, the verification includes the comparison of:

S’ à (-1)^j( ^γ ⁺ ^β ⁾.(S.m^α)^k. ^β.m^k. ^γmod N, si γ positif, ouS' to (-1) ^j( ^γ ⁺ ^β ⁾ .(Sm ^α ) ^k. ^β .m ^k. ^γ mod N, if γ positive, or

S’.m^- ^k. ^γmod N à (-1)^j ⁽ ^γ ⁺ ^β ⁾.(S.m^α)^k. ^βmod N, si γ négatif.S'.m ^- ^k. ^γ mod N to (-1) ^j ⁽ ^γ ⁺ ^β ⁾ .(Sm ^α ) ^k. ^β mod N, if γ negative.

Dans un mode de réalisation, la valeur T=S.m^αest calculée préalablement à cette vérification et est utilisée dans la comparaison.In one embodiment, the value T=Sm ^α is calculated prior to this verification and is used in the comparison.

Pour des raisons de sécurité, une valeur aléatoire, notée Rand, est utilisée pour masquer cette comparaison. Typiquement, dans des modes de réalisation, la comparaison 330 comprend :For security reasons, a random value, denoted Rand, is used to hide this comparison. Typically, in embodiments, the comparison 330 includes:

le tirage d’un entier aléatoire Rand,drawing a random integer Rand,

le calcul d’une valeur de vérification par l’addition d’un des deux termes à comparer à Rand suivi de la soustraction de l’autre terme à comparer. Par exemple, on calculethe calculation of a verification value by the addition of one of the two terms to be compared to Rand followed by the subtraction of the other term to be compared. For example, we calculate

Verif = S’ + Rand - (-1)^j( ^γ ⁺ ^β ⁾.(S.m^α)^k. ^β.m^k. ^γmod N, si γ positif, ouVerif = S' + Rand - (-1) ^j( ^γ ⁺ ^β ⁾ .(Sm ^α ) ^k. ^β .m ^k. ^γ mod N, if γ positive, or

Verif =S’.m^- ^k. ^γmod N + Rand - (-1)^j ⁽ ^γ ⁺ ^β ⁾.(S.m^α)^k. ^βmod N, si γ négatif, etVerif =S'.m ^- ^k. ^γ mod N + Rand - (-1) ^j ⁽ ^γ ⁺ ^β ⁾ .(Sm ^α ) ^k. ^β mod N, if γ negative, and

la comparaison de la valeur de vérification Verif avec Rand, la comparaison étant positive en cas d’égalité.the comparison of the Verif verification value with Rand, the comparison being positive in case of equality.

En cas d’incohérence (comparaison négative), une faute d’exécution est donc détectée, possiblement en raison d’une injection de faute, auquel cas une erreur est levée à l’étape 350. Cette erreur peut consister en l’absence d’émission d’une donnée de sortie issue des calculs 310 et 320. Elle peut également comprendre l’envoi d’un simple code d’erreur.In the event of inconsistency (negative comparison), an execution fault is therefore detected, possibly due to fault injection, in which case an error is raised at step 350. This error may consist of the absence of emission of output data resulting from calculations 310 and 320. It can also include the sending of a simple error code.

En cas de cohérence (comparaison positive), le message chiffré (signature) ou déchiffré est émis en sortie à l’étape 340. De façon générale, le message de sortie est basé sur S ou S’.In case of consistency (positive comparison), the encrypted (signature) or decrypted message is output in step 340. Generally, the output message is based on S or S'.

Préférentiellement, le message de sortie vaut S.m^αmod N. Dans un mode de réalisation, le message de sortie est T préalablement calculé. Avantageusement, lorsque α = 0, la première donnée S vaut directement le message de sortie (signature ou message déchiffré).Preferably, the output message is worth Sm ^α mod N. In one embodiment, the output message is T previously calculated. Advantageously, when α = 0, the first data S is directly worth the output message (signature or decrypted message).

Ce procédé selon l’invention protège l’algorithme RSA-CRT contre les fautes simples du fait des deux exécutions 310 et 320, mais également des fautes doubles identiques (une dans chaque exécution) du fait des messages ou exposants modulaires différents utilisés lors des deux exécutions 310 et 320.This method according to the invention protects the RSA-CRT algorithm against single faults due to the two executions 310 and 320, but also identical double faults (one in each execution) due to the different messages or modular exponents used during the two executions 310 and 320.

Une protection contre la modification malveillante de quelques bits d'une valeur intermédiaire (typiquement un octet ou un mot machine) à une valeur aléatoire étant obtenue par un double calcul classique, elle est également obtenue par le procédé de l’invention.Protection against the malicious modification of a few bits of an intermediate value (typically a byte or a machine word) to a random value being obtained by a conventional double calculation, it is also obtained by the method of the invention.

Une protection contre la modification malveillante de tous les bits d'une valeur intermédiaire à 0 ou à 1 (par exemple 0x00 ou 0xFF) est désormais obtenue par le procédé de l’invention. En effet, comme les entrées de l’algorithme RSA-CRT sont différentes (le message ou les exposants modulaires utilisés), les valeurs intermédiaires sont différentes, et donc une même faute sur les deux exécutions RSA-CRT conduit nécessairement à une faute différente sur les deux données S et S’.Protection against malicious modification of all bits of an intermediate value at 0 or 1 (for example 0x00 or 0xFF) is now obtained by the method of the invention. Indeed, as the inputs to the RSA-CRT algorithm are different (the message or the modular exponents used), the intermediate values are different, and therefore the same fault on the two RSA-CRT executions necessarily leads to a different fault on the two data S and S'.

Egalement, une protection contre la modification malveillante d’un pointeur de façon à ce qu'il pointe vers une certaine adresse en RAM est désormais obtenue par le procédé de l’invention. En effet, même si la modification parvient à fausser le pointeur d’un paramètre d’entrée de la fonction informatique de chiffrement RSA-CRT appelée, par exemple celui du message à utiliser ou celui des exposants modulaires à utiliser, de telle sorte qu'il pointe vers la même valeur pour les deux exponentiations modulaires de même module (p ou q) lors des deux exécutions 310 et 320, les deux données S et S’ ne seront pas cohérentes car les deux exécutions seront effectuées sur le même message ou avec les mêmes exposants modulaires, et non plus avec des messages ou exposants modulaires différents entre les deux exécutions.Also, protection against malicious modification of a pointer so that it points to a certain address in RAM is now obtained by the method of the invention. Indeed, even if the modification manages to distort the pointer of an input parameter of the RSA-CRT encryption computer function called, for example that of the message to use or that of the modular exponents to use, such that it points to the same value for the two modular exponentiations of the same module (p or q) during the two executions 310 and 320, the two data S and S' will not be consistent because the two executions will be carried out on the same message or with the same modular exponents, and no longer with different messages or modular exponents between the two executions.

Il est à noter qu’une protection conventionnelle contre une exécution sur un message nul (m = 0) peut être fournie, par une détection préalable à l’algorithme RSA-CRT ou par une vérification additionnelle sur m en début d’algorithme.It should be noted that conventional protection against execution on a null message (m = 0) can be provided, by detection prior to the RSA-CRT algorithm or by additional verification on m at the start of the algorithm.

Les coûts calculatoires du procédé selon l’invention restent contenus. Celui-ci coûte le coût de la modification du message m et/ou des exposants modulaires, plus deux fois le coût d’une exécution RSA-CRT et le coût de la vérification de cohérence, par exemple le calcul de S’ et (-1)^j( ^γ ⁺ ^β ⁾.(S.m^α)^k. ^β.m^k. ^γmod N. Ces coûts peuvent être maintenus négligeables lorsque les paramètres k, α, β et γ sont petits.The computational costs of the process according to the invention remain contained. This costs the cost of modifying the message m and/or the modular exponents, plus twice the cost of an RSA-CRT execution and the cost of the consistency check, for example the calculation of S' and (- 1) ^j( ^γ ⁺ ^β ⁾ .(Sm ^α ) ^k. ^β .m ^k. ^γ mod N. These costs can be kept negligible when the parameters k, α, β and γ are small.

C’est le cas par exemple des modes de réalisation décrits ci-après, dans lesquels les première et deuxième exécutions de l’algorithme RSA-CRT appellent une même fonction informatique de chiffrement RSA-CRT prenant, en entrées, des messages différents basés sur m et/ou des exposants modulaires de même module différents. Cette fonction est notée RSA-CRT(m, (p, q, d_p, d_q, i_q)) dont une mise en œuvre est décrite plus haut.This is the case for example of the embodiments described below, in which the first and second executions of the RSA-CRT algorithm call the same RSA-CRT encryption computer function taking, as inputs, different messages based on m and/or different modular exponents of the same module. This function is denoted RSA-CRT(m, (p, q, d _p , d _q , i _q )), an implementation of which is described above.

Ces modes de réalisation ont l’avantage de pouvoir s’appuyer sur une fonction RSA-CRT déjà existante, réduisant ainsi le besoin en qualification ou test de fonctions.These embodiments have the advantage of being able to rely on an already existing RSA-CRT function, thus reducing the need for qualification or function testing.

Ces modes de réalisation sont illustrés de façon générique par la . La première exécution 410 appelle la fonction RSA-CRT avec les données d’entrée suivantes (m, (p,q,d_p-α,d_q-α,i_q). Par ce premier appel, la première exponentiation modulaire 312 est calculée, suivie de la deuxième exponentiation modulaire 314 et de la recombinaison CRT 316. La première donnée S obtenue est donc identique à celle obtenue en .These embodiments are illustrated generically by the . The first execution 410 calls the RSA-CRT function with the following input data (m, (p,q,d _p -α,d _q -α,i _q ). By this first call, the first modular exponentiation 312 is calculated, followed by the second modular exponentiation 314 and the CRT recombination 316. The first data S obtained is therefore identical to that obtained in .

Puis la deuxième exécution 420 appelle la fonction RSA-CRT avec les données d’entrée suivantes ((-1)^j.m^k, (p,q,β.d_p+γ,β.d_q+γ,i_q)). Par cet autre appel à la fonction, la première exponentiation modulaire 322 est calculée, suivie de la deuxième exponentiation modulaire 324 et de la recombinaison CRT 326. La deuxième donnée S’ obtenue est donc identique à celle obtenue en .Then the second execution 420 calls the RSA-CRT function with the following input data ((-1) ^j .m ^k , (p,q,β.d _p +γ,β.d _q +γ,i _q ) ). By this other call to the function, the first modular exponentiation 322 is calculated, followed by the second modular exponentiation 324 and the CRT recombination 326. The second data S' obtained is therefore identical to that obtained in .

La vérification 430 reste inchangée, ainsi que la donnée émise en sortie à l’étape 440 ou l’émission d’une erreur à l’étape 450.The verification 430 remains unchanged, as well as the data output in step 440 or the emission of an error in step 450.

Bien entendu, d’autres mises en œuvre que l’appel à une même fonction peuvent être envisagées. Cela signifie que d’autres modes de réalisation de l’invention peuvent prévoir des implémentations différentes de l’algorithme RSA-CRT pour les deux exécutions requises selon l’invention. Notamment, les implémentations différentes peuvent déjà inclure les paramètres j, k, α, β et γ de telles sortes que les deux fonctions appelées prennent les mêmes valeurs en entrées, à savoir (m, (p, q, d_p, d_q, i_q)). D’autres implémentations intermédiaires (e.g. certains paramètres sont déjà fixés dans les implémentations, d’autres sont indiqués dans les valeurs d’entrée) peuvent être envisagées.Of course, other implementations than calling the same function can be considered. This means that other embodiments of the invention may provide different implementations of the RSA-CRT algorithm for the two executions required according to the invention. In particular, different implementations can already include the parameters j, k, α, β and γ such that the two called functions take the same values as inputs, namely (m, (p, q, d _p , d _q , i _q )). Other intermediate implementations (eg some parameters are already fixed in the implementations, others are indicated in the input values) can be considered.

LesFigures 5à9illustrent des modes de réalisation où la première exécution 310 calcule directement le message chiffré (signature) ou déchiffré attendu : S = m^dmod N. Dans ces modes de réalisation, le message pour les exponentiations modulaires de la première exécution et les exposants modulaires des deux exponentiations modulaires de la première exécution valent respectivement m, d_pet d_q. Aussi, le message de sortie vaut S. Ces modes de réalisation diffèrent donc par les paramètres j, k, β et γ utilisés lors de la deuxième exécution 320. Figures 5 to 9 illustrate embodiments where the first execution 310 directly calculates the expected encrypted (signature) or decrypted message: S = m ^d mod N. In these embodiments, the message for the modular exponentiations of the first execution and the modular exponents of the two modular exponentiations of the first execution are respectively worth m, d _p and d _q . Also, the output message is worth S. These embodiments therefore differ by the parameters j, k, β and γ used during the second execution 320.

Dans l’exemple de la , la deuxième exécution 520 de l’algorithme RSA-CRT par le dispositif électronique calcule S’ = m^d+1mod N.In the example of the , the second execution 520 of the RSA-CRT algorithm by the electronic device calculates S' = m ^d+1 mod N.

Cela correspond au mode de réalisation j=0, k=1, α=0, β=1 et γ=1.This corresponds to the embodiment j=0, k=1, α=0, β=1 and γ=1.

Les données S et S’ sont donc liées par la formule m.S mod N = S’. Cette dernière est donc vérifiée à l’étape 530 par exemple sous forme de comparaison entre, d’un côté, m.S mod N + Rand – S’ et, de l’autre côté, Rand.The data S and S’ are therefore linked by the formula m.S mod N = S’. The latter is therefore verified in step 530 for example in the form of comparison between, on the one hand, m.S mod N + Rand – S’ and, on the other side, Rand.

Dans l’exemple de la , la deuxième exécution 620 de l’algorithme RSA-CRT par le dispositif électronique calcule S’ = m^2dmod N.In the example of the , the second execution 620 of the RSA-CRT algorithm by the electronic device calculates S' = m ^2d mod N.

Cela correspond au mode de réalisation j=0, k=2, α=0, β=1 et γ=0. A noter que les mêmes données S et S’ sont obtenues avec les paramètres suivants j=0, k=1, α=0, β=2 et γ=0. On voit ainsi que k et β sont redondants. Dans un mode de réalisation simplifié, k peut être omis. Néanmoins, des modes de réalisation préférés conservent k et β afin de permettre une modification du message pris par l’algorithme RSA-CRT entre les deux exécutions 310, 320.This corresponds to the embodiment j=0, k=2, α=0, β=1 and γ=0. Note that the same data S and S’ are obtained with the following parameters j=0, k=1, α=0, β=2 and γ=0. We thus see that k and β are redundant. In a simplified embodiment, k can be omitted. However, preferred embodiments retain k and β in order to allow a modification of the message taken by the RSA-CRT algorithm between the two executions 310, 320.

Les données S et S’ du mode de réalisation de la sont donc liées par la formule S² mod N = S’. Cette dernière est donc vérifiée à l’étape 630 par exemple sous forme de comparaison entre, d’un côté, S² mod N + Rand – S’ et, de l’autre côté, Rand.The data S and S' of the embodiment of the are therefore linked by the formula S² mod N = S'. The latter is therefore verified in step 630 for example in the form of comparison between, on the one hand, S² mod N + Rand – S' and, on the other hand, Rand.

Dans l’exemple de la , la deuxième exécution 720 de l’algorithme RSA-CRT par le dispositif électronique calcule S’ = (-m²)^dmod N. Il est à noter que dans des modes de réalisation utilisant uniquement des valeurs positives (pour faciliter la représentation binaire), -m peut être manipulé sous forme de N-m ou m.(N-1).In the example of the , the second execution 720 of the RSA-CRT algorithm by the electronic device calculates S' = (-m ² ) ^d mod N. It should be noted that in embodiments using only positive values (to facilitate binary representation ), -m can be manipulated as Nm or m.(N-1).

Cet exemple correspond au mode de réalisation j=1, k=2, α=0, β=1 et γ=0.This example corresponds to the embodiment j=1, k=2, α=0, β=1 and γ=0.

Les données S et S’ sont également liées par la formule S² mod N = S’. Cette dernière est donc vérifiée à l’étape 730 par exemple sous forme de comparaison entre, d’un côté, S² mod N + Rand + S’ et, de l’autre côté, Rand.The data S and S’ are also linked by the formula S² mod N = S’. The latter is therefore verified in step 730 for example in the form of a comparison between, on the one hand, S² mod N + Rand + S’ and, on the other hand, Rand.

Dans l’exemple de la , la deuxième exécution 820 de l’algorithme RSA-CRT par le dispositif électronique calcule S’ = m² ⁽ ^d ⁺¹⁾mod N.In the example of the , the second execution 820 of the RSA-CRT algorithm by the electronic device calculates S' = m ² ⁽ ^d ⁺¹⁾ mod N.

Cet exemple correspond au mode de réalisation j=0, k=2, α=0, β=1 et γ=1. A noter que les mêmes données S et S’ sont obtenues avec les paramètres suivants j=0, k=1, α=0, β=2 et γ=2.This example corresponds to the embodiment j=0, k=2, α=0, β=1 and γ=1. Note that the same data S and S’ are obtained with the following parameters j=0, k=1, α=0, β=2 and γ=2.

Les données S et S’ sont également liées par la formule (m.S)² mod N = S’. Cette dernière est donc vérifiée à l’étape 830 par exemple sous forme de comparaison entre, d’un côté, (m.S)² mod N + Rand – S’ et, de l’autre côté, Rand.The data S and S’ are also linked by the formula (m.S)² mod N = S’. The latter is therefore verified in step 830 for example in the form of comparison between, on the one hand, (m.S)² mod N + Rand – S’ and, on the other hand, Rand.

Dans l’exemple de la , la deuxième exécution 920 de l’algorithme RSA-CRT par le dispositif électronique calcule S’ = m^2d+1mod N.In the example of the , the second execution 920 of the RSA-CRT algorithm by the electronic device calculates S' = m ^2d+1 mod N.

Cet exemple correspond au mode de réalisation j=0, k=1, α=0, β=2 et γ=1.This example corresponds to the embodiment j=0, k=1, α=0, β=2 and γ=1.

Les données S et S’ sont également liées par la formule m.S² mod N = S’. Cette dernière est donc vérifiée à l’étape 930 par exemple sous forme de comparaison entre, d’un côté, m.S² mod N + Rand – S’ et, de l’autre côté, Rand.The data S and S’ are also linked by the formula m.S² mod N = S’. The latter is therefore verified in step 930 for example in the form of comparison between, on the one hand, m.S² mod N + Rand – S’ and, on the other side, Rand.

La illustre un mode de réalisation où la première exécution 310 ne calcule pas directement le message chiffré (signature) ou déchiffré attendu, mais une donnée intermédiaire liée au message attendu par la formule : S.m^αmod N.There illustrates an embodiment where the first execution 310 does not directly calculate the expected encrypted (signature) or decrypted message, but an intermediate data linked to the expected message by the formula: Sm ^α mod N.

Dans l’exemple de la , la première exécution 1010 de l’algorithme RSA-CRT par le dispositif électronique calcule S = m^d-1mod N, c’est-à-dire α=1, et la deuxième exécution 1020 de l’algorithme RSA-CRT calcule S’ = m^2(d ⁺¹ ⁾mod N.In the example of the , the first execution 1010 of the RSA-CRT algorithm by the electronic device calculates S = m ^d-1 mod N, that is to say α=1, and the second execution 1020 of the RSA-CRT algorithm calculates S' = m ^2(d ⁺¹ ⁾ mod N.

Cet exemple correspond au mode de réalisation j=0, k=2, α=1, β=1 et γ=1. A noter que les mêmes données S et S’ sont obtenues avec les paramètres suivants j=0, k=1, α=1, β=2 et γ=2 .This example corresponds to the embodiment j=0, k=2, α=1, β=1 and γ=1. Note that the same data S and S’ are obtained with the following parameters j=0, k=1, α=1, β=2 and γ=2.

Bien entendu, d’autres valeurs de α peuvent être utilisées. De même, tout autre combinaison de j, k, β et γ (par exemples celles desFigures 5à9) peut être utilisée pour la deuxième exécution.Of course, other values of α can be used. Likewise, any other combination of j, k, β and γ (for example those in Figures 5 to 9 ) can be used for the second execution.

Les données S et S’ de l’exemple de la sont donc liées par la formule m².(m.S)² mod N = S’. Cette dernière est donc vérifiée à l’étape 1030 par exemple sous forme de comparaison entre, d’un côté, m⁴.S² mod N + Rand – S’ et, de l’autre côté, Rand.The data S and S' of the example of the are therefore linked by the formula m².(mS)² mod N = S'. The latter is therefore verified in step 1030 for example in the form of comparison between, on the one hand, m ⁴ .S² mod N + Rand – S' and, on the other side, Rand.

Dans un mode de réalisation, la valeur T=m.S (plus généralement m^α.S) peut être calculée à l’étape 1025, avant la comparaison 1030. Cette dernière peut alors consister à vérifier m².T² mod N = S’, par exemple en comparant, d’un côté, m².T² mod N + Rand – S’ et, de l’autre côté, Rand.In one embodiment, the value T=mS (more generally m ^α .S) can be calculated in step 1025, before comparison 1030. The latter can then consist of checking m².T² mod N = S', by example by comparing, on one side, m².T² mod N + Rand – S' and, on the other side, Rand.

Bien entendu, la présente invention ne se limite pas aux formes de réalisation décrites ci-avant à titre d’exemples ; elle s’étend à d’autres variantes. D’autres réalisations sont possibles.Of course, the present invention is not limited to the embodiments described above by way of examples; it extends to other variants. Other achievements are possible.

Claims

Method for signing or decrypting, based on the RSA-CRT algorithm, an initial message m in an electronic device, using a private key comprising two modular exponents d _p and d _q associated with two distinct prime numbers p and q, the RSA-CRT algorithm comprising a first modular exponentiation (312, 322) of module p and a second modular exponentiation (314, 324) of module q, the method comprising the following steps:
generate a first piece of data, S, by a first execution (310, 410, 510, 610, 710, 810, 910, 1010) of the RSA-CRT algorithm on m,
generate a second piece of data, S', by a second execution (320, 420, 520, 620, 720, 820, 920, 1020) of the RSA-CRT algorithm on m, and
emit (340, 440, 540, 640, 740, 840, 940, 1040) an output message based on S or S', if S is consistent with S',
characterized in that the modular exponentiations (312, 322; 314, 324) of the same module of the first and second executions of the RSA-CRT algorithm are carried out on different messages based on m and/or using exponents different modular ones.

Method according to claim 1, in which the first and second executions of the RSA-CRT algorithm call the same RSA-CRT encryption computer function taking, as inputs, different messages based on m and/or modular exponents of the same module which are different.

Method according to claim 1 or 2, in which the modular exponentiations of the same execution are carried out on an identical message .

Method according to one of the preceding claims, in which the modular exponents of the two modular exponentiations of each of the executions are obtained by the same function applied respectively to d _p and d _q .

Method according to one of the preceding claims, in which the message for the modular exponentiations of the first execution is worth m, the modular exponents of the two modular exponentiations of the first execution are respectively worth d _p -α and d _q -α, with α a positive integer or zero, and the output message is Sm ^α mod N.

Method according to one of the preceding claims, in which the message for the modular exponentiations of the second execution is worth (-1) ^j .m ^k , with j and k positive integers, k not zero. In this case, the message to be encrypted/decrypted is modified during the second execution of the RSA-CRT algorithm.

Method according to one of the preceding claims, in which the modular exponents of the two modular exponentiations of the second execution are respectively worth β.d _p +γ and β.d _q +γ, where β is a non-zero positive integer and γ an integer .

Method according to one of the preceding claims, comprising a step of verifying (330, 430, 530, 630, 730, 830, 930, 1030) the consistency of S' with S by comparing S and S', the comparison comparing:
S' to (-1) ^j( ^γ ⁺ ^β ⁾ .(Sm ^α ) ^k. ^β .m ^k. ^γ mod N, with N=pq, when the message for the modular exponentiations of the first execution is worth m and that for the modular exponentiations of the second execution is worth (-1) ^j .m ^k , the modular exponents of the two modular exponentiations of the first execution are respectively worth d _p -α and d _q -α and those of the two modular exponentiations of the second execution are respectively worth β.d _p +γ and β.d _q +γ, if γ positive, or
S'.m ^- ^k. ^γ mod N to (-1) ^j(γ+ β ⁾ .(Sm ^α ) ^k. ^β mod N, if γ negative.

Method according to the preceding claim, comprising a step of calculating a value T=Sm ^α , and
in which the comparison compares S' to (-1) ^j( ^γ ^+β) .T ^k ^. ^β .m ^k. ^γ mod N, if γ positive, or S'.m ^- ^k. ^γ mod N to (-1) ^j(γ+β) .T ^k ^. ^β mod N, if γ negative,
and the step of transmitting an output message includes the step of transmitting the T value.

Method according to the preceding claim, in which the comparison comprises:
drawing a random integer Rand,
calculating a verification value by adding one of the two terms to be compared to Rand followed by subtracting the other term to be compared, and
comparing the check value with Rand, the comparison being positive in case of equality.

Electronic device (40) for signing or decrypting, based on the RSA-CRT algorithm, an initial message m using a private key comprising two modular exponents d _p and d _q associated with two distinct prime numbers p and q, the RSA-CRT algorithm comprising a first modular exponentiation (312, 322) of module p and a second modular exponentiation (314, 324) of module q, the electronic device comprising a processor (10) configured to:
generate a first piece of data, S, by a first execution of the RSA-CRT algorithm on m,
generate a second piece of data, S', by a second execution of the RSA-CRT algorithm on m, and
emit an output message based on S or S', if S is consistent with S',
the electronic device being characterized in that the modular exponentiations of the same module of the first and second executions of the RSA-CRT algorithm are carried out on different messages based on m and/or using different modular exponents.

A non-transitory computer-readable medium storing a program which, when executed by a processor of an electronic cryptographic processing device, causes the electronic cryptographic processing device to perform the method according to one of claims 1 to 10.