Brevet FR2862454A1 — publié le 20050520

METHODE DE REDUCTION MODULAIRE ALEATOIRE ET EQUIPEMENT ASSOCIE La présente invention concerne une méthode de traitement et de calcul arithmétique, destinée à être utilisés particulièrement dans les applications cryptographiques. La présente invention concerne en particulier le calcul des résidus impliquant une réduction modulaire, particulièrement les calculs dérivés de la méthode de réduction de Barrett. De nombreux algorithmes cryptographiques utilisent la multiplication (ou l'exponentiation) de grands entiers et la réduction du produit à une valeur résiduelle qui est congruente avec un module spécifié associé à la clé cryptographique. Ces calculs peuvent faire l'objet d'attaques d'horloge et d'analyses de puissance. Il est donc important que ces calculs soient sécurisés de sorte que les informations sur la clé ne puissent être obtenues. En même temps, il est important que ces calculs soient rapides et précis. La multiplication et la réduction de grands entiers est généralement la partie exigeant le plus de calculs d'un algorithme cryptographique. Plusieurs techniques distinctes de calcul ont été développées en vue d'une réduction modulaire efficace, y compris celles connues sous le nom de méthode de Quisqueter, de méthode de Barrett et de méthode de Montgomery, et de modifications impliquant des calculs préliminaires et une consultation de table. Ces techniques bien connues sont décrites et comparées dans l'art antérieur. Voir, par exemple: (1) A. Bosselaers et al., Comparison of three modular reduction functions , , Advances in Cryptology/Crypto '93, LNCS 773, Springer- Verlag, 1994, pp. 175-186. (2) Jean-François Dhem, Design of an efficient public key cryptographic library for RISC-based smart cards , thèse de doctorat, Université catholique de Louvain, Louvain-la-Neuve, Belgique, mai 1998. (3) C. H. Lim et al., Fast Modular Reduction with Precomputation , publication préliminaire, 1999 (disponible à la CiteSeer Scientific Literature Digital Library, citeseer.nj.nec. com/109504.html). (4) Hollmann et al., Method and Device for Executing a Decrypting Mechanism through Calculating a Standardized Modular Exponentiation for Thwarting Timing Attacks , brevet US n 6 366 673 B1, Apr. 2 2002 (basé sur la demande déposée le 15 septembre 1998). Un objectif de la présente invention est d'améliorer la méthode de réduction modulaire de Barrett et le dispositif de calcul à cet effet, afin de le sécuriser davantage contre les attaques de cryptoanalyse, tout en continuant à obtenir des résultats rapides et précis. Un autre objectif de la présente invention est de proposer la méthode améliorée susmentionnée et un dispositif qui accélère l'estimation de quotient. Ces objets sont atteints par une méthode de réduction modulaire exécutée par ordinateur dans laquelle un quotient utilisé pour le calcul est systématiquement sous- estimé avec une erreur aléatoire de quelques bits, par exemple de moins d'un demi-mot. Le reste résultant est toujours congruent par rapport au produit intermédiaire correspondant associé au module spécifié, mais est plus grand que la valeur résiduelle et diffère de façon aléatoire d'une exécution à l'autre. Du fait que le quotient a seulement besoin d'être approximé, son estimation est plus rapide. Du fait que l'erreur d'estimation est délibérément aléatoire, cette méthode est plus sûre pour la prévention contre la cryptoanalyse. Toutefois, les résultats intermédiaires sont mathématiquement équivalents (congruents par rapport aux résultats réels), et le résultat final (après un ensemble final de soustractions du module) est exactement le même, ce qui permet d'atteindre la précision nécessaire pour pouvoir inverser les opérations cryptographiques. L'équipement utilisé pour exécuter les étapes de la méthode selon la présente invention comprend un générateur de nombres aléatoires pour injecter une erreur aléatoire dans l'estimation du quotient. Une unité de calcul à accès mémoire et injection de report opère sous contrôle d'un micrologiciel exécutant un séquenceur d'opérations pour exécuter les étapes de multiplication-accumulation au niveau mot nécessaires à la multiplication et à la réduction modulaire de grands entiers. La figure 1 est une vue en plan schématique de l'équipement de calcul selon la présente invention (y compris un générateur de nombres aléatoires) utilisé pour exécuter la méthode de réduction modulaire selon la présente invention. La figure 2 est un organigramme illustrant les étapes générales de la présente méthode de réduction modulaire. Sur la figure 1, l'équipement de calcul comprend une unité de calcul 10 capable d'exécuter les étapes de multiplication au niveau mot et de multiplication-accumulation d'opérandes extraits à partir de la mémoire (RAM) 12 et de termes de report issus des registres 14. Le séquenceur d'opérations 16 comprend des circuits logiques pour contrôler l'unité de calcul 10 en accord avec les instructions de micrologiciel ou de logiciel pour exécuter l'ensemble des opérations de multiplication (ou d'exponentiation) et la réduction modulaire de grands entiers. Les paramètres des opérations, stockés dans les registres 18 accessibles par le séquenceur d'opérations 16, consistent en pointeurs qui permettent au séquenceur d'opérations de situer un opérateur dans la RAM 12, ainsi que des informations sur la longueur (nombre de mots) des opérandes, les informations de contrôle d'injection de reports, et l'adresse de destination des résultats intermédiaires. Jusqu'à présent, ce dispositif est pratiquement similaire aux autres équipements adaptés aux opérations arithmétiques sur les grands entiers. En dehors des détails des étapes de réduction, qui seront décrits plus bas, les instructions de micrologiciel ou de logiciel sont également similaires aux programmes antérieurs pour l'exécution de multiplications ou d'exponentiations efficaces sur des grands entiers dans des segments de niveau mot. A la différence des équipements antérieurs de ce type, l'équipement de la figure 1 comprend également un générateur de nombres aléatoires 20 qui, par exemple, peut être tout circuit générateur de nombres pseudoaléatoires connu. Ce générateur de nombres aléatoires exécute un calcul et produit un nombre aléatoire utilisé dans la présente méthode. Ici le générateur de nombres aléatoires 20 est accédé par l'unité de calcul 10, sous commande du séquenceur d'opérations 16 en accord avec les instructions de programmes exécutant la méthode selon la présente invention, de façon à injecter la quantité d'erreur aléatoire dans l'estimation du quotient, comme décrit ci-dessous. Sur la figure 2, la méthode selon la présente invention est une amélioration de la technique de réduction modulaire de Barrett, en exécutant une estimation de quotient plus rapide et en permettant de résister aux attaques de cryptoanalyse. Cette méthode est exécutée par l'équipement de la figure 1. La réduction modulaire résout généralement R = X mod M X - LX/NL M, où R est la valeur résiduelle à déterminer qui est congruente avec X pour le module M, et le symbole Lai représente la partie entière (le plus grand entier s a) de telle sorte que LX/M_ correspond à une division d'entier. Le nombre X à réduire est typiquement un produit de deux grands entiers (généralement premiers), X = A.B, autrement dit l'un ou les deux parmi les entiers A et B ont une taille de plusieurs mots (ex. A et B peuvent être chacun de 1024 bits, ou 32 mots de 32 bits de long). Dans tous les cas, le problème de base dans toute méthode de réduction modulaire réside dans l'évaluation du quotient q = LX/M- de manière efficace pour de grands nombres (multi-mots) X et M. Dans la présente invention, un problème supplémentaire réside dans l'exécution de la réduction d'une manière sécurisée contre les attaques d'analyse de puissance dans les applications cryptographiques. La méthode de Barrett implique le calcul préliminaire et le stockage d'une estimation mise à l'échelle de la réciproque du module, U, et le remplacement de la longue division par des multiplications et des décalages de mots (division par b) afin d'estimer le quotient. Avec le choix approprié de paramètres, l'erreur d'estimation du quotient est au plus de deux. La présente invention améliore la méthode de Barrett en effectuant seulement une approximation du quotient par une estimation moins précise mais plus rapide, et en injectant intentionnellement une erreur aléatoire dans le quotient avant de calculer le reste. Le reste résultant sera plus légèrement plus grand que, mais congruent avec, la valeur résiduelle. Supposons que w représente la taille de mot (ex. w = 32 pour les processeurs 32 bits), b = 2w représente la 10 racine, n est la longueur du module M en mots, où M = Ei=on mibi, 0 2862454 7 Pour exécuter une réduction de module de X, nous estimons un quotient q (étape 32) en utilisant la valeur stockée U, q = L (LX/1A i.0) /bn+2i = L (LX/2nwi.U) /2nw+2w] Ceci n'exige que des multiplications et des décalages de mots pour le calcul. Les parties entières tendent à garantir que le quotient q est toujours sous-estimé (jamais surestimé), bien qu'il soit possible que l'estimation du quotient se révèle être exacte. Une soustraction supplémentaire de un peut être incluse si une sous-estimation est nécessaire. Le quotient U et l'estimation du quotient diffèrent tous deux de celles de Barrett d'un décalage supplémentaire d'un mot chacun. (Barrett utilise U - _b2n/M- et q = L (LX/bn-1 J.0) / bn+1] 15.) Le quotient estimé q s 0 aura une longueur maximum de n+1 mots. A ce stade, il est préférable d'injecter (étape 36) une erreur aléatoire E dans le quotient calculé de façon à obtenir un quotient aléatoire, q' = q - E. Dans ce cas, nous devons avoir M. 2wi2 s X Nous calculons ensuite (étape 38) le reste R' qui sera congruent (module M) avec la valeur résiduelle R: R' = X - q' M Du fait que le quotient q est sous-estimé, et qu'une erreur aléatoire E est introduite, le reste R' z R, à savoir le reste calculé, sera supérieur ou égal au résidu d'un petit multiple aléatoire du module M. Le reste aléatoire R' peut être utilisé dans des calculs ultérieurs (étape 48), du type multiplication ou addition, avec un autre reste R" (aléatoire ou non) qui, si nécessaire, est encore réduit (en revenant à l'étape 32) pour la cohérence. (L'erreur reste limitée). En variante, si un résultat aléatoire n'est pas requis, nous pouvons choisir de conserver le quotient rapproché q (étape 44). Dans ce cas, nous pouvons avoir 0 s X s bzn+l. Le fait de conserver le quotient proche va permettre d'obtenir le vrai reste (étapes 46 et 40). Finalement, en fonction des besoins de l'application particulière, le résidu R peut être calculé à partir du reste R' en appliquant des soustractions du module M (étape 40) jusqu'à ce que cette valeur soit inférieur à M. La valeur résiduelle R qui est égale à R' après la soustraction finale peut alors être renvoyée afin d'être utilisée dans le reste du système cryptographique (étape 42). La randomisation de la réduction modulaire constitue une protection contre les diverses attaques de cryptoanalyse qui reposent sur la constance de l'utilisation des puissances pour déterminer le module. Ici, la réduction de X modulo M varie de façon aléatoire d'une exécution à l'autre, tout en continuant à produire un reste intermédiaire R' qui est congruent. Le nombre de soustractions à la fin pour générer une valeur résiduelle finale R varie également de façon aléatoire d'une exécution à l'autre. Le nombre X à réduire de cette façon peut être obtenu à partir de diverses opérations mathématiques, y compris la multiplication, la mise au carré, l'exponentiation, l'addition, etc. De même, le module M à utiliser peut être dérivé de plusieurs manières, le plus souvent en cryptographie à partir d'une clé. La méthode de réduction modulaire aléatoire selon la présente invention est utile dans de nombreux algorithmes cryptographiques qui reposent sur cette réduction, dont les système cryptographiques à clé publique basés sur des grands premiers (par exemple RSA) et basés sur une courbe elliptique. REVENDICATIONS 1. Méthode de réduction modulaire exécutée par ordinateur sécurisée à des fins cryptographiques, comprenant: le calcul préliminaire et le stockage en mémoire 5 d'une constante U représentant une réciproque approximative au niveau bits d'un module M; l'estimation d'un quotient approximatif q pour un nombre X à réduire modulo M, dans lequel ladite estimation est exécutée sur X dans une unité de calcul, par multiplication par ladite constante U et par décalages de bits de X et par décalage de ladite multiplication; la génération dans un générateur de nombres aléatoires d'une valeur d'erreur aléatoire E et l'application de ladite valeur d'erreur audit quotient approximatif pour obtenir un quotient aléatoire q' = q - E; et le calcul d'un reste R' = X - q'M dans ladite unité de calcul, ledit reste étant supérieur audit module M mais congruent avec X modulo M. 2. Méthode selon la revendication 1 dans laquelle le calcul préliminaire de ladite constante U est exécuté selon l'équation U = _ben+l/M_, où b = 2W, w étant la taille en mots de l'unité de calcul en bits. 3. Méthode selon la revendication 2 dans laquelle l'estimation du quotient approximatif q est exécutée par l'unité de calcul selon l'équation q = L (LX/bn l.0) /bn+2i 4. Méthode selon la revendication 3 dans laquelle une soustraction supplémentaire de un est comprise dans l'estimation du quotient. 5. Méthode selon la revendication 1 dans laquelle la réduction modulaire de X fait partie d'un programme de cryptographie exécuté par ordinateur. 6. Méthode selon la revendication 1 dans laquelle un trajet de circulation alterné est assuré entre la génération et l'application d'une valeur d'erreur au quotient approximatif peut être omise de façon sélective. 7. Méthode selon la revendication 1 dans laquelle le 15 générateur de nombres aléatoires a une limite d'erreur spécifiée d'un demi-mot, moyennant quoi 0 s E 8. Equipement de calcul pour l'exécution d'une méthode de réduction modulaire sécurisée à des fins 20 cryptographiques, cet équipement comprenant: une unité de calcul adaptée pour exécuter des étapes de multiplication et d'accumulation au niveau mots sur des opérandes extraits de la mémoire et des termes de report issus d'un ensemble de registres; un générateur de nombres aléatoires pour générer une valeur d'erreur aléatoire E; un séquenceur d'opérations comprenant des circuits logiques pour contrôler l'unité de calcul, et un générateur de nombres aléatoires en accord avec des instructions de programme afin d'exécuter la réduction modulaire d'un nombre X par rapport à un module M, ce qui implique au moins une estimation d'un quotient approximatif q à partir d'une constante stockée au préalable U représentant une réciproque approximative en bits du module, une randomisation dudit quotient approximatif avec ladite valeur d'erreur E pour obtenir un quotient aléatoire q' = q - E, et un calcul d'une valeur de reste R' - X - q'M. 9. Equipement de calcul selon la revendication 8 comprenant en outre des registres de paramètres d'opérations accessibles par ledit séquenceur d'opérations, lesdits registres contenant un ou plusieurs parmi (a) des pointeurs pour situer l'opérande dans ladite mémoire, (b) des informations sur les longueurs des opérandes, (c) des informations de contrôle d'injection de report pour les registres de termes de report, et (d) des informations d'adresses de destination pour les résultats intermédiaires des étapes d'opérations. 10. Equipement de calcul selon la revendication 8 dans lequel la constante préstockée U dans ladite mémoire est obtenue par un calcul préliminaire selon l'équation U = _12n+1/FL, où b = 2W, w étant la taille de mot de l'unité de calculs en bits. 11. Equipement de calcul selon la revendication 10 dans lequel l'estimation dudit quotient approximatif q exécutée par ladite unité de calcul sous contrôle dudit séquenceur d'opérations exécutant les exécutions de programme est effectuée selon l'équation q = L (LX/b l I.0) /bn+2] 12. Equipement de calcul selon la revendication 11 dans lequel l'estimation de quotient exécutée par l'unité de calcul comprend une soustraction supplémentaire de un. 13. Equipement de calcul selon la revendication 8 dans lequel le générateur de nombres aléatoires a une limite d'erreur spécifiée d'un demi-mot, moyennant quoi 0 s E