Brevet FR2738365A1 — publié le 19970307

Procédé et circuits pour la multipllcetion modulo un nombre binaire N de deux nombres binaires et leurs utilisations aux calculs d 'exponentiation s La présente invention concerne un procédé et des circuits pour la multiplication modulo un nombre binaire N de deux nombres binaires et leurs utilisations aux calculs d'exponentiations. Il est connu, pour assurer la confidentialité de messages transmis entre deux correspondants, de chiffrer l'information pour la rendre inintelligible aux personnes à qui elle zest pas destinée. Dans les systèmes de chiffrement à clés publiques les opérations de chiffrement et de déchiffrement sont effectuées à l'aide de deux clés, une clé publique et une clé secrète cette dernière n'étant en principe connue que par le destinataire. Ces clés sont construites à partir d'algorithmes qui, tout en établissant un lien mathématique entre les deux clés, rendent pratiquement impossible à des fraudeurs avisés de retrouver dans des temps de calcul raisonnables la clé secréte à partir de la clé publique. Suivant l'algorithme RSA de Rivest-Shamir et Adleman, par exemple les clés sont liées par une relation de la forme E x D = 1 modulo un nombre n gardé secret dans le systéme. On conçoit dans ces conditions qu'en choisissant des nombres très grands, l'inviolabilité des messages est assurée. Cependant, ce choix conduit à des calculs très compliqués de fonctions d'exponentiations et de prise de modulo sur des grands nombres. La taille de ces nombres est telle (plusieurs centaines de bits) que les moyens de calcul logiciels sont insuffisants pour obtenir des performances satisfaisantes. D'autre part, la dimension des nombres à manipuler qui augmente régulièrement à chaque nouvelle génération de matériel, rend les moyens informatiques classiques de moins en moins opérationnels. Une solution peut cependant être trouvée en remplaçant les moyens logiciels par des circuits logiques câblés. Cependant, la structure figée de ceux-ci empêche généralement leur réutilisation pour d'autres systèmes que celui pour lequel ils ont été initialement prévus, par exemple, lorsque les nombres pris en considération sont plus grands. Le but de l'invention est de pallier les inconvénients précités. A cet effet, l'invention a pour objet un procédé pour la multiplication modulo un nombre N de deux nombres binaires A et B tels que A et B soient inférieurs au nombre N avec du type consistant pour chacune des valeurs de i comprises entre p- l et 0 à effectuer un calcul par récurrence du produit Si-1 = S.. 2 + A bi 1 où pour i = p-l le produit partiel Sp 1 est égal à A . bp 1 caractérisé en ce qu'il consiste après chaque obtention d'un produit intermédiaire S = SI. 2 à soustraire, selon une première étape, le nombre N du produit intermédiaire S pour conserver selon une deuxième étape, la valeur du produit intermédiaire S inchangée si le résultat de la soustraction est négatif ou à modifier la valeur du produit intermédiaire S par sa valeur modulo N si le résultat de la soustraction est positif, à ajouter, selon une troisième étape, le produit du nombre A par le coefficient b. correspondant du nombre B au produit intermédiaire obtenu à la deuxième étape, à soustraire du résultat de l'addition obtenu à la troisième étape, le nombre N pour conserver ce résultat s'il est négatif ou le modifier par sa valeur modulo N s'il est positif. L'invention a également pour objet un circuit multiplicateur pour la mise en oeuvre du procédé précité. Elle a également pour objet l'utilisation du procédé et des circuits multiplicateurs selon l'invention pour la réalisation de circuits de calcul de fonctions d'exponentiation modulo un nombre N. D'autres caractéristiques et avantages de l'invention apparaîtront ci-après à l'aide de la description qui va suivre faite en regard des dessins annexés qui représentent - la figure 1 un organigramme illustrant les différentes étapes de calcul de fonctions d'exponentiation par multiplications successives mises en oeuvre par l'invention; - la figure 2 un organigramme illustrant les différentes étapes de la multiplication modulaire par additions et soustractions successives mises en oeuvre dans le procédé selon l'invention; - la figure 3 un schéma illustrant le mode de réalisation d'un circuit de multiplication modulaire - la figure 4 un schéma illustrant le séquencement mis en oeuvre pour l'exécution des étapes du procédé de multiplication selon l'invention;; - la figure 5 une table de vérité pour la commande des registres à décalage du circuit de multiplication de la figure 3 - la figure 6 un schéma illustrant la mise en cascade de plusieurs circuits multiplicateurs modulaires - la figure 7 un schéma illustrant le mode de réalisation d'un circuit de multiplication modulaire capable d'enchaîner les opérations de façon à effectuer une exponentiation - la figure 8 un tableau pour illustrer sur un exemple le principe du calcul de fonctions d 'exponentiation mis en oeuvre par l'invention; - la figure 9 un schéma illustrant la mise en cascade d'opérateurs d'exponentiation modulaire. Le calcul de fonctions d'exponentiation d'un nombre par un autre peut être ramené à celui de multiplications successives. Une méthode classique permettant de mémoriser un seul résultat intermédiaire, consiste à effectuer les opérations dans l'ordre décrit par la formule suivante E=((..((XyP-1)2.Xyp -2)2. ... .xy1)2 .xy0 (1) dans laquelle X et Y sont deux nombres binaires, tels que E = avec Y = y0 + y1.2 + etc... + yp-1-2P-1 Selon l'invention une prise de modulo est effectuée à chaque multiplication de façon à ce que la taille des résultats intermédiaires soit toujours de l'ordre de grandeur du nombre N. La formule (i) devient Un organigramme correspondant illustrant cette méthode est représenté à la figure l. Le procédé pour effectuer la multiplication modulaire selon l'invention permet, d'une part, d'effectuer le calcul en mémorisant une seule valeur de résultat intermédiaire, et d'autre part, d'effectuer la prise modulo à chaque étape du calcul sur les résultats intermédiaires, ce qui limite la taille des nombres à manipuler. En considérant trois nombres binaires A, B, N tels que et en supposant que A est inférieur à N et que B est inférieur à N, le calcul du produit S = A. B modulo N, que l'on peut écrire pour plus de facilité S = A.B|N| peut s'effectuer dans un ordre décrit par l'équation suivante S=((...((A.b p-1.2)+A.bp-2).2+. . +A.b1).2+A.b0 (3) En effectuant une prise de modulo à chaque étape, les résultats intermédiaires sont dans ces conditions toujours inférieurs au produit 2.N. Dans ce cas l'équation (3) devient et sa résolution s'obtient aisément par un calcul par récurrence d'une suite de résultats intermédiaires Si tels que Si = (2xSi+1 + A.bi)|N| (5) pour p-l 4 i 4 0 de la façon représentée par l'organigramme de la figure 2, en prenant pour valeur initiale de départ la valeur Sp = 0. La prise de modulo I NI s'effectue par soustraction du nombre N. Comme les résultats intermédiaires sont toujours inférieurs A 2.N, une seule soustraction au plus est nécessaire à chaque étape, ce qui conduit à effectuer une première soustraction S - N pour savoir si S est inférieur à N ou si S est plus grand ou égal à N et à déduire la valeur de S | N | de par la valeur du signe ainsi obtenu. Si le signe est positif, S|N| = S-N Si le signe est négatif, S|N| = S. D'après l'organigramme de la figure 2 le procédé selon l'invention consiste à initialiser le contenu d'un registre de résultats intermédiaires S à zéro, pour effectuer dans une première étape le calcul du résultat intermédiaire Sp-1 = A.bp-1. La multiplication de chaque résultat intermédiaire Sp-1 par 2 est obtenu par un simple décalage d'une position de bit du résultat Si dans le registre S. La prise du modulo du résultat contenu dans le registre S à chaque opération S = 2. Si est obtenue en calculant la différence F = S-N. Si le signe de cette différence est négatif le nombre S est inchangé et si le signe est positif le nombre S est modifié par sa valeur modulo N.A l'étape suivante le nombre A est ajouté au nombre contenu dans le registre S à la condition que le coefficient binaire b. du nombre B correspondant soit égal à 1. Par contre, si le coefficient b. est égal à 0, le contenu du registre S est inchangé. Le contenu du registre S devient après cette dernière opération S = 2.S1+1. NI +A.b1 et la prise de modulo sur ce dernier résultat s'effectue comme précédemment en calculant un nombre F = S-N = de la différence entre le contenu du registre S chargé précédemment diminuée du nombre N. Si le signe de cette différence est négatif le contenu du registre S reste inchangé, par contre si le signe de la différence est positif, le contenu du registre S est changé par le modulo de son contenu.De la sorte, on obtient à la fin de ce processus un contenu du registre S qui est égal à Si = (2.Si+1+A bi) INI Les calculs se répètent ainsi par récurrence pour chaque nouvelle valeur de l'indice i et jusqu'a l'obtention du résultat final A.BINl=So. Un mode de réalisation physique d'un circuit multiplicateur fonctionnant suivant le principe décrit précédemment est représenté à la figure 3. Le circuit multiplicateur représenté comprend, un circuit additionneur soustracteur commandable 19 deux entrées d'opérandes E1 et E2 et comportant une sortie S. Il comprend également un registre 2 de stockage du nombre binaire A, un registre 3 de stockage du nombre binaire N, un registre 4 à décalage destiné à stocker le nombre B, un registre 5 à décalage et à chargement parallèle destiné à stocker la variable du résultat S, un circuit multiplexeur 6 pour transmettre sur l'entrée E2 du circuit additionneur soustracteur 1 le contenu du registre 2 ou celui du registre 3 et un circuit logique combinatoire 7. En début de multiplication, les registres 2, 4, 3 et 5 sont respectivement initialisés aux valeurs des nombres A, B, N, et à la valeur 0. Le contenu du registre 5 est appliqué sur l'en- trée E1 du circuit additionneur soustracteur 1. Les contenus des registres 2 et 3 sont appliqués au travers du circuit multiplexeur 6 sur l'entrée E2 du circuit additionneur soustracteur 1. La sortie F du circuit additionneur soustracteur 1 est reliée aiix entrées parallèles du registre à décalage 5. Le registre 4 initialement chargé par le nombre B, présente à chaque étape de calcul initialisée à chaque nouvelle valeur de l'indice i, la valeur du coefficient b. correspondant, pour les valeurs de i décroissantes successivement de l'indice de P- 1 à l'indice 0.Chaque coefficient b. est appliqué sur une entrée du circuit logique combinatoire 7. Un circuit séquenceur, non représenté, permet la synchronisation des étapes de calcul effectuées par le dispositif de la figure 3 suivant le diagramme des signaux représenté à la figure 4. Suivant ce diagramme, les circuits de la figure 3 sont synchronisés par des signaux d'horloge H1, H2 et H3, tous obte nus à partir d'une horloge de base Ho. Le niveau du signal H1 égale 1 commande le décalage vers la gauche des contenus des registres 4 et 5 pour effectuer la multiplication par deux des résultats intermédiaires S contenus dans le registre 5 et transférer chaque coefficient b1 à l'intérieur du registre 5. Le niveau du signal d'horloge H2 à 1 commande la soustraction des contenus des registres 5 et 3 pour effectuer l'opération F = S-N décrite précédemment.Durant cette opération le signe du résultat est obtenu sur la sortie CO de report du circuit additionneur soustracteur 1, et permet d'effectuer ou non le chargement du résultat F à l'intérieur du registre 5. Lorsque le signal d'horloge H3 prend la valeur 1 le contenu du registre 5 est ajouté au contenu du registre 2 contenant le nombre A et le résultat est à nouveau réintroduit dans le registre 5 sur le front montant de l'horloge Ho si le coefficient b est égal à 1. Dans le cas contraire si le coefficient b. est égal à O le contenu du registre 5 n'est pas modifié par le résultat de l'addition des contenus des registres 5 et 2. Le signal d'horloge H2 est appliqué sur entrée de sélection SEL du circuit additionneur soustracteur 1 pour placer ce circuit dans le mode soustraction lorsque l'état du signal H2 est égal à 1 et dans le mode d'addition lorsque l'état du signal H2 est égal à 0. La commande des registres 4 et 5 a lieu suivant la table de vérité qui est représentée à la figure 5. Ces registres sont des registres à décalage à chargement parallèle du type de ceux connus par exemple sous la dénomination SN 74 178. Ils possèdent deux entrées de commande M1 et M2 et une entrée d'horloge CK. Sur la figure 5 le symbole 2 représente un front montant du signal. Suivant la table de vérité de la figure 5, des décalages à gauche du contenu du registre 4 peuvent avoir lieu sur le front montant de l'horloge Ho lorsque le signal d'horloge H1 est égal à 1, en appliquant simultanément le signal H1 sur l'entrée M1 un niveau O sur l'entrée M2 et le signal Ho sur l'entrée CK.De façon similaire une commande de décalage à gauche du registre 5 est obtenue en appliquant simultanément le signal H1 directement sur l'entrée M i, la sortie du circuit logique combinatoire 7 sur l'entrée M2 et l'horloge élémentaire Ho sur l'entrée CK. Sur la figure 3, le circuit logique de niveau 1 combinatoire 7 possède quatre entrées sur lesquelles sont appliqués les signaux H2, H3, le coefficient b1 et le bit de report Ci provenant du circuit additionneur soustracteur 1.Le circuit 7 est câblé pour fournir sur sa sortie un signal logique de niveau 1 lorsque l'équation logique 113. b1+H2. cO est vérifiée (cg désignant le complément du signal cO). Dans ces conditions on obtient des décalages à gauche du contenu du registre 5 pour chaque état 1 du signal H i sur les fronts montants du signal élémentaire Ho, des chargements en parallèle du registre 5 sur le front montant du signal d'horloge Ho, si le bit de report c0 est égal à O chaque fois que le signal H2 présente l'état 1, et des chargements du registre 5 en parallèle sur le front montant de l'horloge élémentaire H,, si le coefficient b. est égal à 1 chaque fois que le signal d'horloge H3 présente l'état 1. Le circuit multiplexeur 6 qui aiguille les contenus A du registre 2 et N du registre 3 sur l'entrée E2 du circuit 1 sont directement commandés par le signal d'horloge H2. Lorsque le niveau du signal d'horloge H2 est égal à 1, c'est le nombre N qui est appliqué sur l'entrée E2 et lorsque le signal H2 est égal à O c'est le nombre A qui est appliqué sur l'entrée E2. Le circuit multipllcateur qui vient d'être décrit peut être avantageusement utilisé dans des systèmes de chiffrement à clef publlque pour effectuer des opérations de prise de modulo sur des résultats de multiplication effectués sur des grands nombres, car il présente l'avantage d'avoir une structure qui le rend aisément cascadable avec d'autres circuits multiplicateurs de même structure, ce qui permet aux systèmes qui les utilisent de s'adapter A tout moment à la taille toujours grandissante des nombres binaires à multiplier. Un exemple de mise en cascade de plusieurs circuits multiplicateurs présentant ces caractéristiques est décrit ci-après à l'aide de la figure 6. Bien que sur la figure 6 seulement trois circuits multiplicateurs soient représentés pour faire apparaître le principe de la mise en cascade de plusieurs multiplicateurs selon l'invention, il est évident que le principe décrit ci-après peut s'appliquer à la mise en cascade d'un nombre quelconque de circuits multiplicateurs sans limitation. Comme les circuits multiplicateurs comportent les mêmes éléments, les éléments homologues sont représentés avec les mêmes références affectées toutefois d'un indice pour désigner le circuit multipllcateur auquel ils appartiennent. Le registre 23 du circuit multiplicateur situé à gauche de la figure 6 contient les bits de poids forts du nombre A alors que celui référencé 21 du circuit multiplicateur situé A droite de la figure 6 contient les bits de poids faibles du nombre A. Le registre 33 du circuit multiplicateur situé à gauche de la figure 6 contient les bits de poids forts du nombre N alors que le registre 31 du circuit multiplicateur situé A droite contient les bits de poids faibles du nombre N. Le registre 53 du circuit multipllcateur situé à gauche contient les bits de poids forts des résultats partiels S alors que le registre 5 du circuit multiplicateur situé à droite de la figure 6 contient les bits de poids faibles des résultats partiels S. La mise en cascade des registres 51 à 53 a lieu en connectant l'entrée d'un registre à la sortie du registre du multiplicateur suivant, à la différence toutefois de l'entrée série du registre 51 situé à droite de la figure 6 sur laquelle est appliqué un bit constant égal à 0. Le registre 43 du circuit multiplicateur situé à gauche de la figure 6 contient les bits de poids forts du nombre B, alors que celui 41 situé à droite contient les bits de poids faibles du nombre B. Ainsi dans le cadre d'une architecture qui comporterait un nombre quelconque de N circuits multiplicateurs, la sortie d'un registre 4 avec 1 j 4 N, sauf pour le dernier situé A la droite, est connectée à l'entrée série du registre 4 + 1 du boîtier suivant. La sortie série du registre 43 située à j+i gauche de la figure 6 délivre le bit b1 pour tous les multiplicateurs mis en série sur la figure 6.C'est ce bit b qui est utilisé pour commander le chargement de tous les registres 5i 5 Les retenues CO sont propagées d'un circuit additionneur soustracteur 1 vers son voisin situé à gauche. Dans le cas où les circuits additionneurs soustracteurs 1 sont programmés en soustracteurs la retenue CO du circuit multiplicateur situé à gauche de la figure 6 est égale au signe du résultat de la soustraction. C'est cette retenue CO qui est utilisée pour commander le chargement de tous les registres 5 L'utilisation des circuits de multiplication qui viennent d'être décrits pour le calcul d'exponentiations est décrite ciaprès à l'aide des figures 7 à 9. Ce calcul qui permet d'effectuer des exponentiations du type E = XY sur des nombres X et Y est exécuté dans l'ordre décrit par l'organigramme de la figure 1.Dans ce calcul, comme la valeur du résultat intermédiaire est toujours réutilisée à chaque multiplication, il suffit pour utiliser les circuits de multiplication précédemment décrits de mémoriser la valeur du nombre X dans un registre intermédiaire 8 comme représenté à la figure 7. Entre chaque multiplication, la valeur des registres est remise à jour en fonction des multiplications à effectuer conditionnées par la valeur de chaque coefficient yi. Le tableau de la figure 8 permet de suivre les opérations et l'évolution du contenu des registres étape par étape pour le calcul d'une exponentiation E = XY sur deux nombres X et Y dans un cas précis où le nombre Y a la valeur particulière binaire 10i11. Dans ce tableau, à chaque étape est indiquée par un chiffre entre parenthèses, le registre qui a été chargé au cours de l'étape précédente. A chaque multiplication le contenu du registre 5 est chargé dans le registre 4. Une ou deux multiplications sont exécutées par étape suivant la valeur du bit Yi dans l'opération en cours. Les contenus du registre 8 ou celui du registre 5 sont chargés dans le registre 2. L'enchaînement des multiplications est obtenu dans chaque circuit multiplicateur en ajoutant à son architecture le registre de stockage 8 et en chargeant chacun des registres d'après le contenu des registres à l'étape précédente. Le registre 4 contenant le nombre B est rechargé entre deux multiplications par la valeur du registre 5. Un aiguilleur 10 sélectionne une des deux possibilités d'entrée du registre 4. Une entrée extérieure est sélectionnée pendant la multiplication pour soit, initialiser le contenu B du registre 4 soit, pour la mise en cascade ou en série des circuits multiplicateurs, et enfin une entrée venant du registre 5 peut être sélectionnée pour modifier le contenu B du registre 4 avec le contenu S du registre 5 entre deux multiplications. Le registre 2 est rechargé soit par le contenu S du registre 5 soit par le contenu X du registre 8. Un aiguilleur 9 sélectionne les contenus des registres 5 ou 8 à utiliser en fonction de la valeur du bit y. La mise en cascade des circuits multiplicateurs élémentaires modifiés pour effectuer les opérations d'exponentiation est représentée à la figure 9, cette mise en cascade étant effectuée de façon similaire à celle représentée à la figure 6. REVENDICATIONS 1. Procédé pour le calcul modulo un nombre N de la multi nlication de deux nombres binaires A et B tels que A soit tnfé- rieur å N et B inférieur à N avec du type consistant, pour chacune des valeurs i comprises entre P-l et O, A effectuer un calcul par récurrence du produit Si 1 = Si. 2+A. bol 1 où pour Si = -1' Sp 1 = A.b -1 caractérisé en ce qu'il consiste après chaque obtention d'un produit intermédiaire S = Si.2, à soustraire selon iine première étape (H2), le produit intermédiaire S du nombre N, pour conserver, selon une deuxième étape, la valeur du produit intermédiaire S inchangée si le résultat de la soustraction est négatif ou à modifier la valeur du produit intermédiaire par sa valeur modulo N si le résultat de la soustraction est positif, à ajouter (1) selon une troisième étape (Hs) le produit du nombre A par le coefficient b. correspondant du nombre B, au produit intermédiaire obtenu à la deuxième étape, à soustraire (HL) du résultat de l'addition obtenu à la troisième étape, le nombre N pour conserver ce résultat si le résultat est négatif ou le modifier par sa valeur modulo N si le résultat est positif. 2. Circuit multiplicateur pour la mise en oeuvre du procédé selon la revendication 1 caractérisé en ce qu'il comprend des premier (2) et deuxième registres (3) pour le stockage des nombres binaires A et N, un troisième registre (4) à décalage pour le stockage et le décalage du nombre B, un quatrième registre (5) à décalage série et à chargement en parallèle pour mémoriser les produits intermédiaires Si, un circuit additionneur soustracteur (1) comportant, une première entrée d'opérande E1 couplée aux sorties parallèles du quatrième registre (5) et une deuxième entrée d'opérande E2 couplée au premier registre (2) et au deuxième registre(3) au travers d'un circuit multiplexeur (6), ainsi qu'une sortie F couplée à des entrées parallèles du quatrième registre, une sortie de report CO, et un circuit logique combinatoire (7) possédant deux entrées couplées respective ment sur une sortie série du troisième registre (4) fournissant chaque coefficient b1 et sur la sortie de report CO du circuit additionneur soustracteur (1), pour commander un décalage du contenu du registre (5) chaque fois que la sortie de report CO fournit un signal binaire de valeur nulle ou que le coefficient de bi présente l'état binaire 1. 3. Circuit multiplicateur pour la multiplication modulo N de nombres quelconques A et B supérieurs à N caractérisé en ce qu'il comprend une pluralité de circuits multiplicateurs élémentaires selon la revendication 2 reliés en cascade. 4. Circuit multiplicateur selon la revendication 3 caractérisé en ce que chaque circuit additionneur soustracteur (1)) d'un circuit multiplicateur possède une entrée de report Ci reliée à 1A sortie de report CO du circuit additionneur soustracteur qui le précède dans la cascade. 5. Circuit multiplicateur selon les revendications 3 et 4 caractérisé en ce que les quatrièmes registres à décalage (5) de mémorisation des produits intermédiaires sont reliés en série. 6. Circuit multiplicateur selon l'une quelconque des revendications 3 à 5 caractérisé en ce que les troisièmes registres à décalage (4) de mémorisation du nombre B sont reliés en série, et en ce que les deux entrées de chaque circuit logique combinatoire (7) sont reliées respectivement à la sortie du registre d'extrémité (43) de la série des troisièmes registres à décalage fournissant le coefficient b et à la sortie de report CO du circuit additionneur soustracteur (13) du circuit multiplicateur élementaire. 7. Adaptation des circuits multiplicateurs selon l'une quelconque des revendications 2 à 6 au calcul de fonction d'exponentiations du type E = XY, caractérisée en ce qu'elle consiste à placer dans chaque circuit multiplicateur élémentaire, un registre (8) de mémorisation de l'exposant X, un premier circuit multiplexeur (9) pour charger le premier registre (2) avec le contenu soit, du registre (8) de mémorisation de l'exposant soit, du registre de mémorisation (5) des résultats intermédiaires et un deuxième circuit multiplexeur (10) pour charger le troisième registre (4) par le contenu du registre (5) de mémorisation des résultats intermédiaires soit, pour transférer le bit sortant du troisième registre (4) du multiplicateur précédent lorsque les circuits multiplicateurs sont mis en cascade ou pour initialiser le contenu du troisième registre en début de multiplication. 8. Utilisation du procédé et des circuits selon l'une quelconque des revendications 1 à 7 dans les systèmes de chiffrement de messages à clefs publiques.