Brevet FR2734679A1 — publié le 19961129

PROCEDE DE CRYPTOGRAPHIE A CLE PUBLIQUE BASE SUR LE LOGARITHME DISCRET La présente invention a pour objet un procédé de cryptographie dite à clé publique basé sur le logarithme discret faisant intervenir le calcul d'une grandeur modulo p. Elle trouve une application dans la génération de signatures numériques de messages, dans une cession d'authentification entre deux entités ou dans le chiffrement de données. Dans de telles procédures, la sécurité est fondée sur l'e'trême difficulté qu'il y a à inverser certaines fonctions et plus particulièrement le logarithme discret. Ce problème consiste, étant donné la relation mathématique y = gXmodulop que l'on notera par la suite y = gXmodp (qui signifie y est le reste de la division de gX par p), à retrouver x lorsque l'on sonnait p, g et y. Ce problème est impossible à résoudre, en l'état actuel des connaissances, dès que la taille p atteint ou dépasse 512 bits et que celle de x atteint ou dépasse 128 bits. Dans de tels systèmes, il existe en général une autorité qui fournit le nombre p de grande taille, constituant le module. L'autorité choisit également un entier g, appelé base tel que l'ensemble engendré par g c'est-à-dire l'ensemble formé des nombres gXmodp, pour x appartenant à l'intervalle [0, p-i] soit un sousensemble de taille maximale, au moins 2128. Les paramètres p et g sont dits "publics" c'est-àdire qu'ils sont fournis par l'autorité à tous les utilisateurs rattachés à cette autorité. Selon certaines variantes, ces paramètres sont choisis individuellement par chaque utilisateur et font, dans ce cas, partie intégrante de sa clé publique. Un inconvénient majeur à la mise en oeuvre de systèmes cryptographiques réside dans la nécessité d'avoir des moyens de calcul et de mémorisation relativement importants du fait des calculs complexes qui sont réalisés. En effet, le calcul de la grandeur gkmodp consiste à réaliser des multiplications modulaires et cela est coûteux en temps de calcul et en place mémoire. Dans des dispositifs électroniques simples n'utilisant que des microprocesseurs standards, ce type d'opération n'est guère réalisable. Pour des dispositifs électroniques possédant un processeur spécialisé pour ce type de calcul, il est malgré tout souhaitable de limiter, le temps de calcul et la place mémoire nécessaire pour les résultats intermédiaires. En effet, le calcul de la grandeur gkmodp est en général relativement coûteux par la méthode classique du "carré-multiplié" connue sous l'abréviation anglosaxonne SQM (Square-Multiply) puisqu'il équivaut en moyenne à 3/2 Log2(p) multiplications. Selon cette méthode on calcule toutes les puissances de g c'est à dire tous les carrés : go, gl, g2.. .gn, lorsque k est de longueur n bits, puis on réalise les multiplications requises entre ces puissances ( par exemple g17= g1.g16 ). Selon la méthode du "carré multiplié" simple gk requiert n/2 multiplications et n carrés. Dans le cas ou N signatures sont à fournir en une seule fois, on produit Ngk, on réalise alors un calcul en parallele. La méthode du "carré-multipli parallèle requiert N x n/2 multiplications et n carres. Une méthode proposée par E. BRICKELL et al. dénommée par l'abréviation BGKW permet de réduire le nombre de multiplications dans le cas de la méthode du carré-multiplié mais introduit un besoin de stockage de nombreuses constantes précalculées et donc la nécessité de disposer d'une quantité de mémoires de stockage très pénalisante. L'introduction d'un calcul en parallèle de N valeurs dans cette méthode implique l'utilisation de nombreux registres pour conserver les résultats intermédiaires. Cette méthode devient donc plus contraignante dans le cas où l'on se trouve dans une situation où il s'agit de générer un grand nombre de signatures en un temps très bref puisque dans ce cas le calcul en parallèle est introduit. La présente invention a pour objet de remédier à tous ces inconvénients. Elle permet d'apporter une solution souple et peu onéreuse en temps de calcul et en place mémoire à la mise en oeuvre d'algorithmes cryptographiques pour tous systèmes de cryptographie et en particulier par des appareils portables du type carte à puce à microprocesseur. Selon un premier objet de l'invention, le procédé de cryptographie proposé permet de réduire le nombre de multiplications modulaires de façon telle que l'on obtienne des gains en temps de calcul de 15 à 40% et plus selon les schémas de cryptographie utilisés (Schnorr ou El Gamal). Selon l'invention, deux solutions sont proposées afin de réduire le nombre de multiplications, l'une consistant à générer des exposants k "creux" avec peu de bits à 1, mais de longueur suffisante pour garder toute la sécurité au système, et l'autre consistant à réaliser les calculs des puissances de g en parallèle tout en combinant les exposants entre eux de manière à ne pas refaire deux fois le même calcul de puissance pour un exposant donne. L'invention a plus particulièrement pour objet un procédé de cryptographie à clé publique basé sur le logarithme discret faisant intervenir le calcul de la grandeur qkmodp où p est un nombre premier appelé module, k un nombre aléatoire habituellement de longueur n bits et g un entier appelé base, dans lequel une entité E réalise des opérations d'authentification et/ou de signature et/ou de chiffrement, comprenant des échanges de signaux avec une autre entité dans lesquels intervient cette grandeur, caractérisé en ce qu'il comporte les étapes suivantes pour l'entité - générer un exposant k aléatoire de longueur N bits, N étant égal à n+b bits, - calculer le poids de Hamming C de cet exposant et le comparer à une valeur h fixée au préalable, - vérifier si la valeur aléatoire k remplit la condition C 2 h - rejeter la valeur aléatoire k dans le cas ou le poids de Hamming est inférieur à h et recommencer la génération de nouveaux exposants jusqu'à l'obtention d'un exposant satisfaisant cette condition, - ou conserver cette valeur dans le cas contraire, - calculer l'expression gkmodp à partir de la valeur conservée, - utiliser cette expression dans un échange de signaux électroniques avec l'autre entité. L'invention a également pour objet un procédé de cryptographie à clé publique basé sur le logarithme discret faisant intervenir le calcul de la grandeur gkmodp où p est un nombre premier appelé module, k un nombre aléatoire habituellement de longueur n bits et g un entier appelé base, dans lequel une entité E réalise des opérations d'authentification et/ou de signature et/ou de chiffrement, comprenant des échanges de signaux avec une autre entité dans lesquels interviennent plusieurs grandeurs de ce type, caractérisé en ce qu'il comporte les étapes suivantes pour l'entité - générer un ensemble d'exposants aléatoires kj de n bits de poids ai s'exprimant par l'expression k. Cai2 - calculer en parallèle les puissances de g2i tout en combinant les exposants de sorte que les puissances de g déjà calculées pour un exposant servent à d'autres exposants dans lesquels elles interviennent, - pour chaque kj donné, calculer les puissances de g non encore calculées et regrouper toutes ces puissances pour obtenir l'expression gkj modp désirée, - utiliser ces expressions dans un échange de signaux avec l'autre entité. Selon un premier mode de réalisation les étapes de calcul en parallèle et de regroupement comportent les opérations suivantes - combiner les exposants deux par deux pour obtenir des exposants k c reflet de leur parties communes et réitérer les combinaisons sur le résultat de combinaison obtenu, - calculer des grandeurs Gkc pour chaque valeur de k c telle que Gkc = gkcmodp - combiner un exposant kj à l'exposant k c obtenu pour la combinaison à laquelle cet exposant appartient de manière à éliminer les parties communes et ne conserver que les parties différentes, - définir des exposants k'. reflet des parties différentes entre un exposant kj donné et un exposant k c donné, - calculer des grandeurs Gk,jtelles que Gk,j = gkjmodp - déterminer les expressions Gkjmodp en opérant des multiplications entre les grandeurs GkC obtenues à chaque itération. Dans un deuxième mode de réalisation, les étapes de calcul en parallèle et de regroupement comportent les opérations suivantes - combiner les exposants entre-eux de manière à former tous les sous-ensembles de combinaisons possibles d'exposants possédant des parties communes, - définir des exposants k c reflet des parties communes, pour chaque sous-ensemble de combinaison tels que les bits non-nuls de poids donné correspondent aux bits non-nuls de même poids de la combinaison considérée, - calculée des grandeurs GkC pour chaque valeur de k c telles que :: GkC= gkcmodp - combiner chaque exposant kj avec tous les exposants k c obtenus pour chaque sous-ensemble de combinaison auquel cet exposant k. appartient de manière à éliminer les parties communes et ne conserver que les parties différentes, - définir des exposants k'j reflet des parties différentes entre un exposant kj donné et un exposant k c donné, - calculer des grandeurs Gk,j telles que Gk'j=gk'jmodp - déterminer les expressions gkjmodp en opérant une multiplication entre les grandeurs GSkj et Gkc pour chaque kj. Selon un autre objet de l'invention, les combinaisons permettant d'obtenir les parties communes entre les exposants sont réalisés par des jonctions logiques "ET". Selon un autre objet de l'invention, les combinaisons permettant d'obtenir les parties différentes sont réalisées par des fonctions logiques "OU-exclusif". D'autres particularités et avantages de l'invention apparaîtront à la lecture de la description qui est faite et qui est donnée à titre d'exemple illustratif et non limitatif et en regard des dessins qui représentent - la figure 1, un schéma de principe d'un système apte à mettre en oeuvre l'invention, - la figure 2, un schéma fonctionnel représentant les étapes essentielles du procédé dans une première application, - la figure 3, un schéma fonctionnel représentant les étapes essentielles du procédé dans une deuxième application selon un premier mode de réalisation, - la figure 4, un schéma fonctionnel, représentant les étapes essentielles du procédé dans la deuxième application, selon un deuxième mode de réalisation, On a représenté sur la figure 1, un schéma de principe d'un système de mise en oeuvre du procédé de cryptographie objet de l'invention. Ce système est formée d'une entité El désirant effectuer des échanges de signaux électroniques avec au moins une autre entité E2. les deux entités sont munies respectivement d'une unité de traitement (CPU) 11, 30, d'une interface de communication, d'une mémoire vive (RAM) 13, 32 et/ou d'une mémoire non inscriptible (ROM) 14, 34 et/ou d'une mémoire non volatile inscriptible ou réinscriptible (EPROM ou EEPROM) 15, 33 et un bus d'adresses, de données, de contrôle 16, 35. L'unité de commande de traitement et/ou la ROM contiennent des programmes ou des ressources de calcul correspondant à l'exécution des étapes de calcul intervenant dans le procédé objet de l'invention, c'est-à-dire lors d'une session d'authentification ou lors de la génération d'une signature électronique ou lors du cryptage de signaux électroniques à transmettre à l'autre entité. L'unité de traitement ou la ROM possèdent les ressources nécessaires à des multiplications, additions et réductions modulaires. De même que l'unité de traitement et/ou la ROM comportent les fonctions de cryptographies utilisées propres à chaque algorithme de cryptographie et les paramètres g et p. Les exposants kj pourront être chargés au préalable dans une mémoire réinscriptible par l'autorité ou, générés au fur et à mesure à partir d'un générateur aléatoire et d'une valeur aléatoire source ko secrète. L'entité El possède en outre la clé secrète x. L'invention s'applique tout particulièrement aux système à cryptographie mis en place dans le domaine bancaire où une grande sécurité est requise lors de transactions opérées sur les comptes. C'est aussi le cas où l'on désire authentifier l'envoi de messages transmis sous forme de signaux électroniques d'une autre entité. C'est aussi le cas où l'on a besoin de signer des messages lors d'échanges de signaux avec une autre entité. En pratique, l'entité désireuse de réaliser une transaction pourra être, par exemple, une carte à circuit intégré telle qu'une carte à puce et l'entité destinatrice sera alors un terminal bancaire. La suite de la description va être faite dans le cadre de l'application du procédé à la signature de messages numériques, étant bien entendu que l'invention s'applique à tout système de cryptographie basé sur un algorithme discret. Le procédé selon l'invention propose une première solution pour diminuer considérablement le nombre de multiplications particulièrement adapté au cas où l'on a un environnement où la place mémoire est faible. Dans ce cas, le principe est de produire des exposants kj "creux" en ce sens que le poids de Hamming sera choisi le plus faible possible, tout en conservant bien entendu le caractère aléatoire à ces exposants. Pour cela, le procédé consiste à générer des exposants kj soit au fur et à mesure du besoin soit au préalable à tout échange. Bien sûr dans ce cas, ils seront mémorisés. Les exposants générés n'ont pas une longueur de n bits mais une longueur supérieure n+b bits et remplissent une condition définie dans la suite. Lorsqu'un exposant k de n+b bits est généré le procédé consiste ensuite à calculer le poids de Hamming C de cet exposant puis à le comparer à une valeur h fixée au préalable. Si à l'issue de la comparaison Ch alors l'exposant est retenu et va être utilisé par l'entité qui va alors calculer l'expression gkmodp et utiliser cette expression dans l'envoi de signaux numériques dans lesquels cette expression sera utilisée comme signature par exemple. Dans le cas où le paramètre C ne remplit pas la condition requise, l'exposant k correspondant est rejeté, un nouvel exposant est généré, l'étape de vérification de la condition est recommencée jusqu'à obtention d'un exposant k remplissant cette condition. Ainsi cette solution permet d'avoir à réaliser moins de multiplication tout en conservant le même niveau de sécurité que si l'on avait des exposants de taille plus réduite. Selon un exemple particulier, permettant de réduire au maximum le nombre de multiplications on choisira C = h. En pratique, pour un exposant de taille n + b bits (avec n = log2 P) dont le poids de Hamming est h, pour avoir le même nombre de combinaisons que lorsque 1' exposant est de n bits, alors les relations suivantes doivent êtres vérifiées 2n n+b et( N + b)/2 + h S n (condition qui permet de réduire le nombre de calcul à effectuer). c'est à dire 2n et b+2h Les nombres b et h que l'on se fixe sont obtenus en résolvant cette double inéquation pour un n donné (n=160 par exemple). A titre illustratif les résultats du procédé selon l'invention ont été comparés aux méthodes connues. Dans le cas de l'algorithme de Shnorr où n = 160 bits, et dans le cas de l'algorithme de El Gamal où n = 512 bits. Ces résultats sont indiqués dans le tableau ci-dessous. variant o Schnorr El Gamal El Gamal Temps de Espace de effort ss calcul mémoire multiplications 62 (h) 187 (h) 199 (h) CARRE 87(b=15) 279(b=52) 273(b=35) EFFORT 149 469 472 GAIN 6,8% 9,4% 7,8% La contrainte mise sur l'espace des signatures couvert par des exposants de n bits peut être réduite par un facteur a dépendant du niveau de sécurité que l'on désire obtenir. Les paramètres n, h et b doivent alors remplir la condition (1) (1) 2 n-a tout en conservant la possibilité de générer les mêmes signatures à partir de différents aléas de taille (n + b) bits. En pratique 280 est assez pour contrer les différentes attaques possibles et donc n-a = 100 est une valeur tout à fait acceptable. variant # Exposant Expossant carré creuse creux multiplié temps place simple effort ss de calcu mémoire multiplications 37 (h) 49 (h) n/2 carrés n/2+7 n/2+2 n/2 (b=14) (b=4) Total n/2+44 n/2+51 n Cette variante d'exécution est d'autant plus interressante que le coût (en temps de calcul) d'un carré est souvent moindre que celui d'une multiplication modulaire. En général on obtient s/2 S m On a représenté des résultats comparatifs pour ces deux cas extrèmes dans le tableau suivant variant exposant exposant carré GAIN creux creux multiplié effort ss temps de place simple calcul mémoire Schnorr 124 131 160 22.5% (m=2s) El Gamal 300 307 512 41% (m=2s) Schnorr 204 211 240 15% (m=s) El Gamal 556 563 728 24% (m=s) On constate que le gain obtenu lorsque l'on applique le procédé aux schémas de Shnorr et El Gamal est très important par rapport à la méthode du carrémultiplié simple et même dans le cas où l'on considère que le coût d'un carré est le même que celui d'une multiplication. Selon un autre mode de réalisation, le procédé s'applique tout particulièrement à des systèmes n'ayant pas de contrainte particulière concernant la place mémoire. Dans ce mode de réalisation, on procède au calcul des différentes puissances de g en parallèle afin de ne calculer les carrés qu'une seule fois, tout en combinant les exposants afin de ne pas effectuer plusieurs fois le même calcul. Pour bien comprendre l'invention, on va décrire le cas où l'on a effectué le calcul de deux puissances. soit k. = ài2i, kj étant tiré aléatoirement (c'est-à-dire généré à partir d'un générateur aléatoire) soit kk = Kj = bi2i Selon le procédé on combine les exposants k. et kk de manière à définir un exposant k c tel que k c = àibi2i reflète des parties communes entre k et kk. Les coefficients ai sont, soit 1 soit 0. L'exposant kc correspond à la partie commune des exposants kj et kk c'est-à-dire si kj = 1 x 210 + ... + 0 + 1 x 20 et kk = 1 x 210 + 0 + 0 ... + 1 x 20 k c = i x 210 + 0 + ... + 1 x 20. Selon le procédé on détermine donc ainsi l'exposant k noté kc au moyen d'une fonction logique ET. On procéde ensuite à une deuxième combinaison consistant à déterminer les parties distinctes entre l'exposant kj et l'exposant kc On recherche également les parties distinctes entre l'exposant kk et l'exposant kc. On va noter kj $ k c et kk kc ces combinaisons 3 kk kc qui sont réalisées pour des OU-exclusifs. On calcule en parallèle les grandeurs suivantes Gkj = gkj d3 kcmodp Gkk = gkk z kcmodp Gkc = gkcmodp Pour obtenir gkjmodp et Gkkmodp il suffit de réaliser les opérations 1) Gkj X Gkcmodp 2) Gkk x Gkcmodp Lorsque l'on a, comme l'exemple qui vient d'être donné deux puissances, on effectue en moyenne environ 3n/4 multiplications au lieu de n multiplications. La gain est de 25%; Le procédé selon l'invention peut être généralisé à un plus grand nombre de combinaisons d'exposants. Cette généralisation peut en outre être implantée selon deux modes de réalisation illustrés par les schémas fonctionnels donnés sur les figures 3 et 4. Dans ce cas, l'invention s'applique tout particulièrement aux cas où l'on a besoin de générer un grand nombre de signatures. Selon le premier mode de réalisation, on réalise des combinaisons d'exposants deux par deux suivant une arborescence telle que représentée par le tableau cidessous k. al a2 a3 a4 kc bl = al.a2 b2 = a3.a4 cl = bl.b2 Ces combinaisons permettent tout comme l'exemple décrit précédemment, de fournir des exposants k c reflet des parties commune entre les exposants kj . Pour simplifier l'écriture, les exposants kj sont nommés a1, a2, a3, a4. Les exposants k c sont nommés au niveau -1 de l'arbre, b1 et b2 et au niveau -2 de l'arbre par c1. Les combinaisons a1. a2, a3. a4 sont réalisées par une fonction logique ET. On réitère les combinaisons à chaque niveau de l'arbre ainsi constitué. le nombre de multiplications diminue au fur et à mesure que l'on s'enfonce dans l'arbre du fait de la simple répartition statistique des bits. L'effort de calcul à réaliser est minoré par n/3 multiplications. Comme cela a été décrit précédemment, on détermine des grandeurs Gkc à chaque niveau. Ainsi on obtiendra G al = gal # blmodp Ga2 = ga2 $ blmodp Gbl = gbîmodp Gbl = gbl # clmodp soit Gbl = Gbl Cl modp Gb2 = gb2 &commat; cimodp soit Gb2 #Gb1 modp Gc1 = gcl modp Gal modp= Ga1 x Gb1 modp = Ga1xGb1 x G c1 modp En pratique, galmodp sera obtenu par le produit Ga1 x Gb1 modp et ga2 modp sera obtenu par le produit Ga2 x Gblx Gc1 modp. Selon un deuxième mode de réalisation on combine les exposants de manière à former tous les sousensembles de combinaison possibles soit par exemple si l'on a comme exposant kj : a, b, c, on formera les combinaisons ab, ac, bc, abc. On réalise donc des combinaisons permettant de définir les parties communes relatives à ces sousensembles en opérant une fonction logique ET entre a et b, a et c, b et c et a, b, c. On définit ainsi un exposant kc pour chaque sous-ensemble obtenu. On peut calculer en parallèle toutes les grandeurs Gkc = g kcmodp pour lesquelles kc ont peu de bits à 1 par rapport aux k initiaux et donc pour lesquelles le calcul modulaire est rapide. Puis on effectue un autre type de combinaison consistant à éliminer les parties communes entre un exposant et les combinaisons précédentes. Ces combinaisons sont réalisées au moyen de fonctions logiques OU-exclusif. Ainsi, on obtient suivant l'exemple donné ka = a xor abc xor ac xor ab kb = b xor abc xor ab xor bc kc = c xor abc xor ac xor bc On peut ensuite calculer des grandeurs G krj = gkj modp pour lesquelles les k'j ont encore moins de bits à 1 que les k c initiaux et pour lesquelles les modifications modulaires sont encore plus rapides. Pour finir les expressions gkjmodp sont obtenues par kj. Dans le cas de la génération de N signatures obtenues par ce deuxième mode de réalisation, l'effort de calcul tendra vers n/N carrés + n(2N-1)/N2N + (2N-1-l) multiplications. Le tableau qui suit permet de donner des résultats de comparaisons avec les méthodes connues telles que le carré-multiplié, le carré mutliplié en parallèle et l'invention. Méthodes Carré Carré Combinaison Temps de muliplié d'exposant effort multiplié parallèle arbre binaire Carrés N(n-l) n-l n-l Multiplication N(n/2-1) N(n/2-1) Nn/3 TOTAL N(3n/2-2) N(n/2-l)+n-1 Nn/3+n-l Effort pour N > > n 100% 33t 22% Le premier mode de réalisation donné (regroupement arborescent) dans le cas de l'application à la génération de N signatures est peu coûteuse en place mémoire. Pour un arbre binaire à 4 exposant on aura besoin de 8 registres de log2(p) bits pour les calculs. Le deuxième mode de réalisation donné (N regroupements) est très peu coûteux en temps de calcul car elle est optimale en nombre de multiplication. Pour 3 exposants on aura besoin de 8 registres de log2(p) bits pour les calculs. REVENDICATIONS 1. Procédé de cryptographie à clé publique basé sur le logarithme discret faisant intervenir le calcul de la grandeur gkmodp ou p est un nombre premier appelé module, k un nombre aléatoire habituellement de longueur n bits et g un entier appelé base, dans lequel une entité E réalise des opérations d'authentification et/ou de signature et/ou de chiffrement, comprenant des échanges de signaux avec une autre entité dans lesquels intervient cette grandeur, caractérisé en ce qu'il comporte les étapes suivantes pour l'entité: - générer un exposant k aléatoire de longueur N bits, N étant égal à n+b bits, - calculer le poids de Hamming C de cet exposant et le comparer à une valeur h fixée au préalable, - vérifier si la valeur aléatoire k remplit la condition:C 2 h - rejeter la valeur aléatoire k dans le cas ou le poids de Hamming est inférieur de h et recommander la génération de nouveaux exposants jusqu'à obtention d'un exposant satisfaisant cette condition, - ou conserver cette valeur dans le cas contraire, - calculer l'expression gkmodp à partir de la valeur conservée, - utiliser cette expression dans les échanges de signaux avec l'autre entité. 2. Procédé selon la revendication 1, caractérisé en ce que la condition à remplir est c = h. 3. Procédé de cryptographie à clé publique basé sur le logarithme discret faisant intervenir le calcul de la grandeur gkmodp ou p est un nombre premier appelé module, k un nombre aléatoire habituellement de longueur n bits et g un entier appelé base, dans lequel une entité E réalise des opérations d'authentification et/ou de signature et/ou de chiffrement, comprenant des échanges de signaux avec une autre entité dans lesquels intervient cette grandeur, caractérisé en ce qu'il comporte les étapes suivantes - générer un ensemble d'exposants aléatoires kj de n bits de poids ai s'exprimant par l'expression kj =ai2i - calculer en parallèle les puissance de g21tout en combinant les exposants de sorte que les puissances de g calculées pour un exposant servent à d'autres exposants dans lesquels elles interviennent, - pour chaque k. donné, calculer les puissances de g non encore calculées et regrouper toutes ces puissances pour obtenir l'expression gkjmodp désirée, - utiliser ces expressions dans un échange de signaux avec l'autre entité. 4. Procédé selon la revendication 3, caractérisé en ce que - les étapes de calcul en parallèle et de regroupement comportent les opérations suivantes - combiner les exposants deux par deux pour obtenir des exposants k c reflet de leur parties communes et réitérer les combinaisons sur le résultat de combinaison obtenu, - calculer les grandeurs Gkc pour chaque valeur de k c telle que Gkc = gkcmodp - combiner un exposant k. à l'exposant k c obtenu pour la combinaison à laquelle cet exposant appartient de manière à éliminer les parties communes et ne conserver que les parties différentes, - définir des exposants k,j reflet des parties différentes entre un exposant kj donné et un exposant k c donné, - calculer des grandeurs Gk,j telles que Gk,j = gmodp - déterminer les expressions Gkjmodp en opérant des multiplications entre les grandeurs GkC obtenues à chaque itération. 5. Procédé selon la revendication 3, caractérisé en ce que les étapes de calcul en parallèle et de regroupement comportent les opérations suivantes - combiner les exposants entre-eux de manière à former tous les sous-ensembles de combinaisons possibles d'exposants possédant des parties communes, - définir des exposants k c reflet des parties communes, pour chaque sous-ensemble de combinaison tels que les bits non-nuls de poids donné correspondent aux bits non-nuls de même poids de la combinaison considérée, - calculée des grandeurs Gkc pour chaque valeur de k c telles que : : GkC= gkcmodp - combiner chaque exposant kj avec tous les exposants k c obtenus pour chaque sous-ensemble de combinaison auquel cet exposant k. appartient de manière à éliminer les parties communes et ne conserver que les parties différentes, - définir des exposants k'. reflet des parties différentes entre un exposant k. donné et un exposant k c donné, - calculer des grandeurs Gk,j telles que Gk,j=gk imodp - déterminer les expressions gkjmodp en opérant une multiplication entre les grandeurs G'kj et GkC pour chaque kj.