Brevet FR2755266A1 — publié le 19980430

Procédé et circuits pour la conversion et la multiplication, modulo un nombre N, de nombres et leur utilisation dans les systèmes de chiffrement à clefs publiques. La présente invention concerne un procédé et des circuits pour la conversion modulo un nombre binaire N, de nombres binaires, et leur utilisation dans les systèmes de chiffrement à clefs publiques. I1 est connu, pour assurer la confidentialité de messages transmis entre deux correspondants de chiffrer l'information transmise pour la rendre inintelligible aux personnes à qui elle n'est pas destinée. Dans les systèmes de chiffrement à clefs publiques les opérations de chiffrement et de déchiffrement sont effectuées à l'aide de deux clefs, une clef publique (E) et une clef secrète (D) cette dernière n'étant en principe connue que par le destinataire. Ces clefs sont construites à partir d'algorithmes qui, tout en établissant un lien mathématique entre les deux clefs, rendent pratiquement impossible à des fraudeurs avisés de retrouver dans des temps de calcul raisonnable la clef secrète (D) à partir de la clef publique (E). Suivant l'algorithme RSA de Rivest-Shamir et Adleman, par exemple, les clefs E et D sont liées par une relation de la forme ExD = 1 modulo un grand nombre n gardé secret dans le système. On peut concevoir, dans ces conditions, qu'en choisissant des nombres fn très grands, Pinviolabilité des messages est assurée. Cependant, ce choix conduit à des calculs très compliqués de fonctions exponentielles et de prises de modulo sur des grands nombres. Comme la dimension de ceux-ci, qui peut être estimée pour les systèmes actuellement utilisés à plusieurs dizaines de chiffres, ou pour des systèmes de haute sécurité, à quelques centaines de chiffres, ne cesse de croître, les performances que l'on peut obtenir en utilisant des moyens logiciels ordinaires pour effectuer ces calculs sont de plus en plus faibles, de sorte que, ces moyens apparaissent de moins en moins opérationnels. La solution à ces difficultés peut certainement ê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éutilisa tion dans d'autres systèmes, lorsque ceux-ci prennent en considération des nombres plus grands que ceux pour lesquels ces circuits ont été conçus. Ces difficultés rendent par conséquent les réalisations à circuit logique câblée peu viables sur le plan industriel. 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 conversion modulo un nombre binaire N, d'un nombre binaire représenté par des signaux numériques, caractérisé en ce qu'il consiste à calculer à l'aide d'un premier circuit, pour chacune des valeurs de i comprise entre 0 et 2p-1, un nombre Ri tel que Ri = 2i.Mod N, à i i multiplier à l'aide d'un deuxième circuit chacun des nombres Ri par le nombre binaire Xi correspondant, à additionner avec ce même circuit le produit Xi.Ri obtenu à un résultat intermédiaire Moi 1 précédent pour obtenir une somme Si vérifiant la relation Si = Mi 1 + Ri.Xi, chacun des i I i résultats intermédiaires Mi 1 étant obtenu à l'aide d'un troisième circuit à partir de la somme Si 1 précédente par la relation Mi= Si 1 Mod N, et à prendre pour i = 2p-1 la valeur M2p 1 obtenue en fin de calcul comme résultat de l'opération X modulo N. L'invention a également pour objet des circuits permettant la mise en oeuvre du procédé ainsi qu'une utilisation de ceux-ci dans les systèmes de chiffrement à clefs publiques. D'autres caractéristiques et avantages de l'invention apparaîtront ci-après à Paide de la description qui suit faite en regard des dessins annexés qui représentent: La figure 1 un organigramme illustrant les différentes étapes du procédé de prise de modulo selon l'invention. La figure 2 un schéma illustrant un mode de réalisation d'un circuit pour la prise de modulo de nombres binaires selon l'invention. La figure 3 plusieurs circuits de prise de modulo selon l'invention mis en cascade. La figure 4, un schéma illustrant un mode de réalisation d'un circuit muliplieur de deux nombres X et Y adapté aux circuits de prise modulo N selon l'invention. La figure 5 un mode d'assemblage de plusieurs circuits multiplieurs selon la figure 4 reliés en cascade. En appliquant la définition mathématique de la congruence modulo N de deux nombres, la conversion modulo N d'un nombre binaire X consiste à rechercher un nombre binaire R tel que R soit le reste de la division de X par un nombre Q, ce qui s'exprime généralement par la relation R = X (modulo N). Deux démarches peuvent être également adoptées pour calculer R.Lapremièreconsisteàcalculerlapartieentièreduquotientpuisà la multiplier avec N, et enfin, à retrancher le résultat obtenu à X. La deuxième consiste à effectuer la soustraction R = X - NQ en déterminant Q tel que o En se reportant au diagramme représenté à la figure 1, le procédé selon l'invention consiste dans une première étape 1, à calculer pour chacun des poids binaires 21 sa représentation R.=2i Modulo N. (1) Ce résultat est obtenu d'après la relation R. = (2xi 1) modulo N i i-I A l'étape 2, le nombre R. obtenu à Pétape 1 est multiplié par le nombre binaire X. correspondant et le résultat R..X. est ajouté à un résultat intermédiaire Mi 1 pour former un nombre Si suivant la relation Si = Mi- + R i X.. (2) i i A Pétape 3 la représentation modulo le nombre N du nombre Si est calculée pour former un nombre M. tel que M. = Si Modulo N. (3) I I Les calculs des étapes 1, 2 et 3 sont répétés successivement pour chaque valeur de i comprise entre 0 et 2p-1 (étape 4) et chaque valeur de M. obtenue est utilisée comme résultat intermédiaire pour le calcul du nombre Si + 1 suivant. Lorsqu'à l'étape 5, i = 2p-1, le calcul s'arrête et la valeur M 1 obtenue représente la valeur du résultat de l'opération X modulo N. Un circuit pour la mise en oeuvre de ce procédé est décrit à la figure 2. I1 comprend, un registre 7 pour stocker les résultats intermédiaires Mi 1 , un registre 8 pour stocker les nombres Si, un registre 9 pour stocker le nombre N et un registre à décalage 10 pour stocker les nombres R.. Un circuit soustracteur Il est connecté entre le registre 9 et le registre 10 pour soustraire le contenu N du registre 9 au nombre R. contenu dans le registre 10 et reporter le résultat obtenu dans le registre 10. Un circuit soustracteur 12 est connecté entre le registre 8 et le registre 9 pour soustraire le contenu N du registre 9 au contenu Si du registre 8. La sortie du registre 12 est connectée au registre 7 pour permettre le transfert du résultat Si - N obtenu à la sortie du circuit soustracteur 12 dans le registre 7. Pour les valeurs successives de i comprises entre 0 et 2p - le registre 10 contient successivement les valeurs: R0 = 2 (modulo N) pour i = o R1 = 2R0(modulo N) = 21modulo N pour i = 1 R2p-1 = 2R 2p-2(modulo N) = 22p-1 modulo N pour i = 2p-1 soit R i+1 = 2Ri (modulo N) pour ox SO = Xo Ro pour i = o Sî = M0 +R1 X1 pour i = 1 S2p-1 M2p-2 + R2p-1 X2p-1 pour i = 2p-1 soit Si= Mi-1 + Ri Xi pour o#i#2p-1 - le registre 7 contient successivement les valeurs: Mo = So (modulo N) pour i = o M1 S1(modulo N) pour i = 1 M -S (moduloN) pouri=2p-l 2p-1 = 2p-l soit M.=S.(moduloN) pour oX i I i Dans ces calculs: les nombres Si obtenus correspondent à des sommes intermédu aires vérifiant la relation modulo N + Xi2 i modulo N (4) les nombres M i correspondent à des résultats intermédiaires vérifiant la relation Mi = 2 Xj2j(modulo N) (5) 1=0 le nombre final M obtenu vérifie de ce fait la relation 2p-1 2p-1 M M2p 1 = 2 Xj-2j (modulo N) (6) j=o qui correspond à l'expression X (modulo N). Comme le registre 10 est un registre à décalage la multiplication des nombres R. par 2 s'effectue en décalant le mot binaire R. d'un i I élément binaire à droite à l'intérieur du registre sachant que la place du poids binaire le plus faible est à gauche dans le registre 10. Au départ, pour i = o, la valeur 1 est chargée dans le registre 10 pour obtenir Ro = 2o = 1 puis pour i = 1 la valeur o est chargée en série pour obtenir 2Ro = R1, et ainsi de suite jusqu'à obtenir R2p-1 = 2R2p-2. A chaque nouvelle valeur de i la prise de modulo de 2Ri est effectuée en soustrayant le nombre N contenu dans le regisre 9 au nombre 2Ri contenu dans le registre 10. Si 2Ri - N > , o le contenu du registre 10 est remplacé par 2R. - N pour former Ri+l. Par contre si 2Ri - N En fonction des valeurs de chaque X. on obtient en sortie de l'additionneur 2 soit Si = Ri + Mi-l si X. = 1 soit Si Mi~l si X. = o. i i i-I i I Egalement, en sortie du soustracteur 6 on obtient soit M. = S. - N I i si Si - N > o soit M. = Si dans le cas contraire. I i A titre d'exemple, on pourra pour effectuer les opérations d'addition et de soustraction décrites précédemment utiliser les circuits commercialisés sous les références 74 181 et fabriqués par la Société: Texas Instrument. Outre le fait qu'avec le procédé et le dispositif de l'invention les nombres manipulés ne peuvent jamais dépasser une dimension de 2N et qu'ainsi les temps de calcul ne peuvent grandir démesurément en fonction de la taille des nombres, ceux-ci présentent également l'avantage qu'ils conduisent à une structure de circuit de prise de modulo, facilement cascadable. On peut en effet, comme cela est représenté à la figure 3, connecter sans difficulté et à volonté plusieurs circuits en série lorsque les nombres X dont il faut prendre le modulo, ont une taille qui dépasse la capacité des registres de chaque opérateur. Sur la figure 3, trois circuits élémentaires 13, 14 et 15 du type de celui qui vient d'être décrit à l'aide de la figure 2 sont représentés à Pintérieur de rectangles en pointillés. Suivant cette représentation, les éléments composant ces opérateurs sont repérés avec les mêmes références que les éléments homologues de la figure 2 accompagnées cependant d'un indice a, b ou c suivant que l'élément correspondant appartient respectivement à l'un des trois opérateurs 13, 14 ou 15. Tous les circuits additionneurs 8a, 8b et 8c sont commandés simultanément par la valeur binaire X. correspondant à chaque instant d'horloge i. Les deux séries de soustracteurs 1 la, 1 lb et lic, d'une part, et 12a, 12b et 12c d'autre part, sont commandés simultanément par le signe du résultat fourni par le dernier soustracteur 12c par des liaisons 16 et 17, les autres retenues 18a, 18b, d'une part, et 19a et l9b d'autre part, sont transmises respectivement à chaque entrée de retenue correspondante du soustracteur suivant. Enfin les registres 10a, 10b et 10c sont reliés en série. Les dispositifs qui viennent d'être décrits peuvent être avantageusement utilisés dans des systèmes de chiffrement à clef publique pour effectuer des opérations de prise de modulo sur des résultats de multiplication effectués sur des grands nombres. Cependant pour les mêmes raisons qu'exposées précédemment il sera souhaitable que les multiplieurs utilisés aient aussi des structures aisément cascadables les unes aux autres pour que les systèmes puissent sans difficulté et à tout moment s'adapter à la taille toujours grandissante des nombres binaires à multiplier. A titre d'exemple, un circuit multiplieur présentant ces caractéristiques est représenté à la figure 4. Ce circuit qui a la structure d'un circuit systolique comprend un registre multiplicande 20 et un registre multiplicateur 21 tous deux reliés par leurs sorties à un réseau de portes "ET" 22. I1 comprend également un premier réseau de circuits additionneur 23 et un deuxième circuit additionneur 24, ce dernier étant relié à des bascules 25. En désignant par et par les nombres multiplicande et multiplicateur à multiplier, le circuit de la figure 4 permet d'obtenir le résultat X de la multiplication de A par B sous une forme avec des sommes partielles S; S.=a..b. C. + Ci avec i 1 j-o ' i X. = Si mod N i I C. = Si/2 (division entière) Pour effectuer le calcul, le nombre A est stocké en entier dans le registre 20 et le nombre B est rentré en série poids faible en tête, dans le registre 21. Les produits élémentaires des bits aj.bi j sont effectués chacun par une porte "ET" du réseau de porte "ET" 22, puis sont additionnés à l'aide du circuit additionneur 23. Le résultat de l'addition fourni par l'additionneur 23 est ajouté dans l'additionneur 24 à la retenue Ci de étape precédente pour donner S.. On stocke dans les bascules 25 le résultat d'un décalage vers la gauche de Si, c'est-à-dire C. 1 la retenue pour l'étape suivante. Le bit de poids faible de Si est égal à Xiième bit du résultat de la multiplication. Comme pour le circuit de prise de modulo décrit précédemment la mise en cascade de plusieurs circuits multiplieurs du type de celui qui vient d'être décrit à l'aide de la figure 4 n'offre pas de difficulté particulière, cette mise en cascade pouvant être effectuée de la manière représentée à la figure 5, qui représente à titre d'exemple trois circuits multiplieurs 26, 27 et 28 dessinés à l'intérieur de rectangles en pointillés montés en cascade. Comme précédemment les éléments composant ces multiplieurs sont repérés avec les mêmes références que les éléments homologues de la figure 4, celles-ci étant accompagnés cependant d'un indice a, b ou c suivant le multiplieur 26, 27 ou 28 où l'élément considéré est situé. Les connexions qui sont établies entre les multiplieurs permettent d'obtenir un comportement global des multiplieurs identique à celui que l'on pourrait obtenir avec un seul multiplieur de taille plus grosse. Ce résultat est obtenu en reliant les registres 21a, 21b et 21C en série les uns aux autres et en propageant le résultat obtenu par le dernier additionneur 24b sur une entrée d'opérande de l'additionneur 24b par la liaison 29 et le résultat obtenu à la sortie du deuxième circuit addition neur 24b sur une entrée d'opérande de l'additionneur 24 par la liaison 30. a Le résultat fourni par l'additionneur 24a est le bit Xi REVENDICATIONS 1. Procédé pour la conversion modulo un nombre binaire N, d'un nombre binaire représenté par des signaux numériques, caractérisé en ce qu'il consiste à calculer (1), à l'aide d'un premier circuit (10, 11), pour chacune des valeurs de i comprise entre 0 et 2p, un nombre Ri tel que R. = 2i.Mod N, à multiplier (2) à l'aide d'un deuxième circuit (8) I I chacun des nombres Ri par le nombre binaire Xi correspondant, à additionner (2) à Paide du même circuit (8) le produit Xi.Ri obtenu à un résultat intermédiaire Mi-1 précédent pour obtenir un nombre Si vérifiant la relation Si = M. 1 + RiXp chacun des résultats intermédiaires M. étant obtenu (3), à l'aide d'un troisième circuit à partir de la somme Si 1 précédente, par la relation Mi i-I = Si M od N (7, 12), et à prendre (6) la valeur Mep-l, obtenue pour i = 2p-1 en fin de calcul, comme résultat de l'opération X modulo N. 2. Procédé selon la revendication 1, caractérisé en ce que pour obtenir chaque nombre R., on multiplie (10) par 2 chaque nombre R. 1 et on compare (11) le nombre 2Ri 1 obtenu au nombre N pour prendre comme valeur de R. soit la valeur 2Ri 1 ~ N si le résultat de la comparaison est positif ou nul, soit la valeur 2Ri 1 si le résultat de la comparaison est négatif, ces calculs étant effectués par le premier circuit. 3. Procédé selon les revendications 1 et 2, caractérisé en ce que pour obtenir chaque nombre Mi, on compare (12) chaque valeur de Si au nombre N pour prendre comme valeur de M. soit la valeur M. = Si - N si le résultat de la comparaison est positif, soit la valeur de M i = Si dans le cas contraire. 4. Circuit pour la mise en oeuvre du procédé selon l'une quelcon que des revendications 1 à 3, caractérisé en ce que le premier circuit comprend un registre à décalage (10) pour effectuer les multiplications par 2 des nombres R. et un circuit soustracteur commandable (11) couplé au registre à décalage (10) pour comparer chaque valeur 2Ri 1 au nombre N et transférer les résultats 2Ri 1 - N ou 2Ri 1 dans le registre à décalage (10) en fonction du résultat de la comparaison. 5. Circuit selon Pune quelconque des revendications 1 à 4, caractérisé en ce que les deuxième et troisième circuits sont formés par un circuit additionneur (8) comprenant une première entrée d'opérande sur laquelle sont appliqués les nombres Ri, une deuxième entrée d'opérande sur laquelle sont appliqués les nombres Mi 1' une troisième entrée de commande sur laquelle sont appliqués les nombres X. et une sortie fournissant soit, le nombre Si = Mi 1 + R. Xi si la valeur du bit X. est i i i i égale à 1 soit le nombre Si = M. 1 si la valeur du bit X. est nulle. i i-I i 6. Circuit selon l'une quelconque des revendications 1 à 5, caractérisé en ce que le quatrième circuit comprend un registre (7) pour stocker les résultats intermédiaires Mi 1 et un circuit soustracteur commandable (12) comportant une première entrée d'opérande couplée à la sortie du circuit additionneur (8) et une deuxième entrée d'opérande sur laquelle est appliqué le nombre N, le circuit soustracteur comparant chaque valeur Si fournie par le circuit additionneur 8 au nombre N, la sortie du circuit soustracteur étant couplée au registre (7) de stockage des résultats intermédiaires pour stocker dans ce registre les nombres M. = Si - N ou M. = S. en fonction du résultat de la comparaison. i i i i 7. Circuit pour la prise de modulo de nombres binaires, caractérisé en ce qu'il comprend une pluralité de circuits selon les revendications 1 à 6 reliés en cascade. 8. Utilisation du circuit selon l'une quelconque des revendications 4 à 7 pour la multiplication modulo des nombres N de nombres binaires A et B définis par des relations de la forme 9. Utilisation selon la revendication 8 dans laquelle la multiplication est effectuée à l'aide des circuits multiplieurs systolique série. 10. Utilisation selon la revendication 9, caractérisée en ce que chaque circuit multiplieur comprend un registre multiplicande (20) et un registre multiplicateur (21) à décalage pour faire circuler les bits du nombre multiplieur B devant ceux du nombre multiplicande A, un réseau de porte "ET"(22) pour effectuer des produits élémentaires a..b. . sur les J I-J nombres A et B, et un dispositif additionneurs (23,24) pour effectuer des sommes partielles et fournir sur une de leur sortie le ième bit X. du résultat de la multiplication 11. Utilisation de circuits selon l'une quelconque des revendica tions 4 à 10, caractérisée en ce qu'elle comprend plusieurs circuits multiplieurs (26, 27, 28) selon la revendication 10 reliés en cascade. 12. Utilisation de circuits selon l'une quelconque des revendications 4 à 11 dans les systèmes de chiffrement de messages à clefs publiques.