FR 2510280 A1 19830128 FR 8213070 A 19820727 1 DISPOSITIF CRYPTOGRAPHIQUE La présente invention concerne un dispositif cryp- tographique servant à chiffrer un message ou une information utilisée dans les communications ordinaires et dans les ordi- nateurs et à déchiffrer le cryptogramme et plus particulière- ment un dispositif cryptographique permettant de réaliser le chiffrage et/ou le décryptage d'un système cryptographique, dont la clé de chiffrage peut être révélée au public. Dans le système cryptographique à clé de chiffra- ge connue du public, on utilise différentes clés pour le chiffrage et le décryptage et toute personne peut chiffrer un message en utilisant une clé de chiffrage connue publiquement, mais seul le récepteur peut déchiffrer un message chiffré en utilisant une clé de décryptage tenue secrète, ce qui permet de garantir les communications privées Comme système crypto- graphique de ce type à clé de chiffrage connue publiquement, on connalt le système cryptographique RAS proposé par R L. Rivest et consorts dans l'article "Procédé d'obtention de si- gnatures numériques et de systèmes cryptographiques à clé de chiffrage connue du public", dans Communications of the ACM, Février 1978, Vol 21, N 2, pp 120-126. Une procédure de chiffrage et une procédure de décryptage sont représentées par les expressions suivantes de congruence: - Chiffrage: C Me modulo N ( 1) d Déchiffrage: M = C modulo N ( 2) dans lesquelles C, M, e, d et-n sont tous des nombres en- tiers, C est la représentation d'un cryptogramme sous la for- me d'un nombre entier, M est la représentation d'un texte en clair sous la forme d'un nombre entier, e et N représentent une clé de chiffrage et d et N une clé de décryptage, avec e # d Selon la présente invention,toutes les variables,hor- mis les signaux de commande, sont des nombres entiers et sont représentées par leur complément à 2 Afin d'accroître les ca- capacités de protection et de sécurité, on choisit les valeurs 2510280 2 100 200 50 100 de n, e et d comme suit: N = 10 à 10 , e = i 05 à 101 et d = 1050 à 101 La procédure de chiffrage, c'est-à-dire un calcul du reste C lorsque Me est divisé par n, est mise en oeuvre de la manière décrite ci-après Ici M 1, M 2, R et C sont des variables On suppose préalablement que e est repré- k senté par la relation e =i O ei 2, o eé = O ou 1 Pas 1 : Régler la variable C = 1. Pas 2 : Exécuter les pas 2 a et 2 b pour i k, k-1, , 1, 0. Pas 2 a: Z M 1 = C, M 2 = C R M 1 x M 2 modulo n C=R Pas 2 b: Lorsque ei = 1 M 1 = C, M 2 M R ' M x M modulo n i 2 C=R C = R Pas 3 : Arrêt Dans les pas ou phases opératoires indiquées ci- dessus, le symbole d'équation "=" signifie qu'il faut donner la valeur du membre de droite à la variable du membre de gauche. C'est ainsi qu'est réalisée la procédure de chif- frage du chiffre RAS, c'est-à-dire le calcul de C Me modulo n Cette procédure de calcul sera désignée ci-après sous le terme de "procédure d'exponentiation". Comme on le voit d'après la comparaison des équa- tions ( 1) et ( 2), la procédure de décryptage est réalisée de façon similaire en utilisant d à la place de e Dans le cas o ledispositif cryptographique RAS, qui effectue un chiffrage et un décryptage tels que décrits ci-dessus, doit être mis en oeuvre grâce à l'utilisation de la technologie à haute den- sité d'intégration telle que la technologie des circuits CMOS, n MOS et autres, la taille du circuit du dispositif cryptographique serait de l'ordre de 100 000 à 200 000 portes Etant donné que 2510280 3 la densité d'intégration des circuits intégrés à haute densité d'intégration de l'art antérieur se situe dans la gamme de 10 000 à 30 000 portes par puce ou microplaquette, réalisa- tion d-nr tel dispositifcryptographique est difficile. Afin d'éviter ce problème, un dispositif cryptographique à haute densité d'intégration d'un système de commande par microprogram- mes, possédant une taille de circuit d'environ 20 000 portes, a été proposé dans l'article R L Rivest "Description de la réalisation du dispositif cryptographique RSA à clé de chiffra- ge connuedu public, sur une seule microplaquette", National Telecommunication Conference, 1980, Enregistrement de la conféren- ce, vol N 3 des 4 volumes, pp 49 2 1-49 2 4 Ce dispositifcryp- tographique à haute densité d'intégration est peu pratique étant donné que sa vitesse de calcul pour la cryptographie est inférieure à 1,2 Kbits/s En outre étant donné que la clé de chif- frage du dispositif cryptographique RSA possède une longueur fixe de 512 dans ce dispositif cryptographique à haute densité d'intégration, aucune procédure de cryptographie ne peut être mise en oeuvre dans le cas o la longueur de la clé de chiffra- ge est égale par exemple à 256 ou 1024 bits. Comme cela est décrit ci-dessus, dans ce dispositif cryptographique, le calcul de R M 1 x M 2 modulo N est effectué un certain nombre de fois Par le passé, ce calcul était ef- fectué de la même manière qu'une multiplication et unedivision ordinaires; en effet le produit M 1 x M 2 est obtenu par des mul- tiplicationsséquentiellesdans un ordre croissant en commençant tout d'abord par le chiffre du poids le plus faible, puis en divisant le résultat de la multiplication par n, et ce séquen- tiellement dans un ordre décroissant en commençant par le chiffre de poids le plus élevé Par conséquent ce dispositif cryptographiqueprésente comme inconvénient le fait que la durée du calcul est notablement longue en raison de telles multipli- cations et divisions séquentielles. C'est pourquoi un but de la présente invention est de fournir un dispositif cryptographique pouvant être aisément fabriqué sous la forme d'un dispositif à haute densité d'inté- 2510280 4 gration. Un autre but de la présente invention est de créer un dispositif cryptographique permettant un chiffrage et un décryptage à grande vitesse. Un autre but de la présente invention est de créer un dispositif cryptographique impliquant un coût réduit et dans lequel la longueur d'ureclé de chiffrage et/ou de décryp- tage peut être choisie dansune gamme étendue, telle que -par exemple ú bits ( O t = | = 0 pour Xl' O ( 19) Q , X , v x 2 13 pour X" 2510280 24 ment 40, un signal de sortie présent dans la ligne 38 de transmission de signaux de sortie passe à l'état " O ", et lorsqu'un signal " 1 " est appliquée à partir de la ligne de transmission de signaux de prépositionnement, le signal de sortie de la li- gne 38 de transmission de signaux de sortie devient " 1 " Cette bascule bistable enregistre les données présentes dans la li- gne 36 lors de la montée d'un signal d'horloge dans la ligne 37 La figure 4 Q représente une bascule bistable de déclenche- ment qui possède une ligne 42 de transmission de signaux d'en- trée de déclenchement, une ligne 40 de transmission d'entrée de signaux d'entrée d'effacement et une ligne 38 de transmis- sionde signaux de sortie raccordée à sa borne Q, et le signe de la sortie Q est inversé lors de la montée de l'impulsion d'entrée de déclenchement appliquée la bascule bistable La figure 4 R illustre un autre symbole de la bascule bistable du type maître-esclave D de la figure 4 P On emploie ce symbole lorsque la bascule bistable est utilisée en tant que circuit de retard sur une impulsion d'horloge La figure 4 S représente un compteur qui comporte une ligne 43 de transmission de si- gnaux d'effacement, une ligne 44 de transmission de signaux d'entrée pour des impulsions devant être comptées et une li- gne 45,de transmission de sortie, dans laquelle un signal " 1 " est retenu après comptaged'un 513-ème impulsion d'entrée. La référence " 512 " du sigle CNT 512 signifie que ce compteur effectue le comptage d'impulsions 512 fois et que la 513-ème impulsion provoque le passage de la sortie à " 1 " La figure 4 T est une illustration servant à expliquer le fonctionnement du compteur représenté sur la figure 4 S Une fois qu'il est alimenté avec le signal d'effacement à un instant 46, le comp- teur CNT 512 compte 512 fois des impulsions et lors de la dé- tection de la 513-ème impulsion, son signal de sortie devient " 1 " à l'instant 47 Du point de vue du compteur, il existe des compteurs effectuant le comptage de 128 impulsions, de 6 impulsions et de 2 impulsions Ces compteurs sont désignés par les sigles CNT 128, CNT 6 et CNT 2 de la même manière que dans le cas de la figure 45. 2510280 25 La figure 4 U représente globalement a portes ET (a= 1,2, ) comme cela est représenté sur la figure 4 V La figure 4 W représente globalement a portes OU (a= 1,2, ) présenté sur la figure 4 I La figure 4 Y représente globale- ment a portes NON (a= 1,2, ) comme cela est représenté sur la figure 4 Z La figure 5 A est identique à la figure 5 B, sur laquelle les lignes d'entrée et de sortie sont raccordées directement La figure 5 L indique le fait qu'une entrée à b bits est accrue de a bits (avec b>a) comme cela est re- présenté sur la figure 5 D La figure 5 E indique qu'une entrée à b bits est réduite de a bits et que la sortie est délivrée sous la forme de (b-a)bits (avec b>a) comme cela est représenté sur la figure 5 F La figure G 5 montre qu'une entrée à a bits est délivrée avec l'adjonction d'un zéro sur son côté d'ordre supérieur, comme cela est représenté sur la figure 5 H La figure 5 I indique que 10 bits d'ordre supérieur d'une entrée à 38 bits sont sortis telsquelset que les 28 bits d'ordre inférieur sont subdivisés en deux selon des ensemblesde 14 bits, et que 4 bits entre 2 bits d'ordre supérieur et 8 bits d'ordre inférieur de chaque groupe sont délivrés en même temps que les 10 bits d'ordre supérieur mentionnés ci-dessus, comme cela est représenté sur la figu- re 5 J La figure 5 K montre que 4 bits d'ordre supérieur d' une entrée à 64 bits sont retirés de cette entrée et que 4 bits sont ajoutés sur le côté de rang inférieur en vue d' obtenir une sortie à 64 bits comme cela est représenté sur la figure 5 L. La figure 5 M indique que le nom d'un signal dans une ligne de transmission de signaux 55 est D-SIG La figure 5 N indique que 12 sortes de signaux de commande sont présents dans la ligne de transmission de signaux 55 et que leursnoms sont CT 1 à CT 12 La figure 5 P indique que cinq signaux sont délivrés dans la ligne de transmission 55 et que leurs noms sont respectivement CLOCK (horloge), e-in (entrée de e), n-in (entrée de n), START (démarrage) et C-out (sortie de C) La figure 5 Q indique le nombre des signaux dans une ligne de 2510280 26 transmission de sianaux 56 et 12 est ou'ils sont désignés scus les noms CT 1 à CT 12 et qu'ils sontrépartis selon deux signaux CT 2 et CT 1 dans une ligne de transmission de signaux 57, trois signaux CT 5, CT 11 et CT 12 dans une ligne de transmission de si- anaux 58, etc. La valeur du signal présent dans la ligne de transmission de signaux est indiquée par une valeur locique binaire " O " ou " 1 ", ou bien par un nombre entier binaire représenté sous la forme d'un complément à 2. Agencement cénéral de la forme de réalisation La figure 6 illustre l'agencement général d'une forme de réalisation de la présente invention, dans laquelle les parties correspondant à celles de la figure 3 sont repé- rées par les mêmes chiffres de référence et par les mêmes caractères Le calculateur de quotient 9 est subdivisé en une section 60 de prétraitement de calcul du quotient et en une section 61 de post-traitement du calcul de quotient,et ces sec- tions de traitement 60, 61 sont interconnectées par l'inter- médiaire d'une ligne de transmission de signaux 62 Les sec- tions partielles 251 à 258 sont équipées respectivement de lignes de transmission de signaux d'entrée 631 à 638, 651 à 658 et 671 à 678 et de lignes de transmission de signaux de sortie 641 à 64 Les lignes de transmission de signaux d' entrée 671 à 677 sont mises à la terre et introduisent un signal de valeur " O ", et la ligne de transmission de signaux d'entrée 678 introduit un signal de-valeur " 1 " Le signal de valeur "'1 " présent dans la ligne de transmission de signaux 678 signifie que la section partielle 258 est la plus éloi- gnée du calculateur de quotient 9 et se trouve sur le côté du chiffre de poids le plus faible parmi les sections par- tielles Alimentée par le signal de valeur " 1 ", une partie de la section partielle 258 effectue une opération particu- lière différente des opérations dessections partielles 251 à 257 Ceci sera décrit ultérieurement Les chiffres de ré- férence 8 à 8 désignent des unités de commande 8 disposées dans les sections partielles individuelles 251 à 258. 2510280 27 Conformément au principe de la présente invention le dispositif cryptographique de la figure 6 reçoit les varia- bles e, N et M de la part des lignes de transmission de signaux d'entrée 281, 282 et 283 et effectue l'opération C Me modulo n de manière à délivrer la variable C dans la ligne de trans- mission de signaux de sortie 29 De façon similaire les varia- bles d, N et C sont envoyées par les lignes de transmission de signaux d'entrée 281, 282 et 283 au dispositif cryptographi- que lors de la mise en oeuvre de l'opération M C modulo n, avec délivrance de la variable M dans la ligne de transmission des signaux de sortie 29. Le dispositif cryptographique reçoit un signal de commande de fonctionnement de la part de la ligne de transmis- sion de signaux d'entrée 631 et l'unité de commande 81 délivreun signal de commande pour l'ensemble du dispositif crypto- graphique Les unités de commandes 82 à 88 ne fonctionnent pas. En d'autres termes les sections partielles 251 à 258 sont réa- lisées avec une constitution identique et l'une des unités de commande est utilisée Par conséquent, au lieu de prévoir une unité de commande dans chaque section partielle, il est possi- ble de prévoir séparément une seule unité de commande pour les sections partielles, comme cela est le cas pour le calculateur de quotient 9. L'état de fonctionnement du dispositif cryptogra- phique est délivré à l'extérieur par l'intermédiaire de la ligne de transmission de signaux de sortie 64 l Différents si- gnaux de commande nécessaires pour effectuer le calcul servant à la cryptographie sont délivrés non seulement par l'unité de commande 81, mais également par la section 61 de post-traite- ment de calcul du quotient et par des éléments situés dans la section partielle 251 autreset que l'unité de commande 81 Les noms des signaux circulant dans la ligne 26 de transmission de signaux de commande d'exponentiation, dans la ligne 21 de trans- mission de signaux de commande de multiplication et dans la li- gne 22 detransmission de signaux de commande de division sont respectivement EXP-SEL, M-SIG et D-SIG La ligne de transmis- 2510280 28 sion de signaux 27 comprend 12 lignes et leur nom sont respec- tivement CT 1 à CT 12. Section de prétraitement de calcul du quotient La figure 7 illustre la section de prétraitement de calcul du quotient, qui est formée par une mémoire morte "ROM" 68 La mémoire ROM 68 est utilisée à la place de la mise en oeuvre de l'équation ( 15) Lorsqu'une valeur ln 2 504 l est délivrée en tant qu'adresse dans la ligne de transmission de signaux 19, la mémoire ROM 68 délivre dans la ligne de transmission de signaux 62 une valeur ( 213 ln 2504 ll, pré- calculée et mémorisée dans cette mémoire Avec un tel agence- cement, la valeur de v calculée au moyen de l'équation ( 15) peut être obtenue dans la ligne de transmission de signaux 62 par application de bits de poids élevà:de la variable n. Section de post-traitement de calcul du quotient La figure 8 illustre l'agencement général de la section 61 de post-traitement de calcul du quotient, qui ef- fectue les opérations des équations ( 18) et ( 19) Le signal M-SIG présent dans la ligne 21 de transmission de signaux de commande de multiplication est composé de quatre signaux, dont chacun possède une valeur 6 2 j_)+i 2 (I= 0,1,2,3). Incidement on a i O* 4 (j_ 1)+i-21 = M 2,j à partir de l'équa- .tion ( 14) La ligne 24 de transmission de signaux d'entrée applique une valeur de 11 bits de poids élevé de M 1, obtenue par suppression de 501 bits de poids inférieur de M 1, repré- sentés par 512 bits dans l'équation ( 18); la ligne 23 de transmission de signaux d'entrée applique une valeur consti- tuée par un signal binaire de 14 bits obtenu par suppression de 500 bits de poids inférieur de Rj+i i(i= 0,1) représentés par 514 bits dans l'équation ( 18) Un groupe 70 de portes ET .i.2504 effectue la combinaison logique ET de M 1 et de 64 (j 1)+i 22 504 (i= 0,1,2,3,4) dans l'équation ( 18); un circuit logique 71 pro- duit la constante 38 de l'équation ( 18), et un additionneur conservant la retenue (CSA-Q 1) effectue l'addition contenue dans l'équation ( 18) de manière à calculer la valeur de X" Un additionneur conservant la retenue (CSA-Q 2) 72 comporte Un additionneur conservant la retenue (CSA-Q 2) 72 comporte 2510280 29 sept entrées et deux sorties, corres-Dpndant toutes à des nombres tiers binaires d'une largeur de 14 bits Un groupe 731 de por- tes ET effectue l'opération ET nécessaire pour le calcul de X" x v dans l'équation ( 19) C'est-à-dire que le groupe 731 j de portes ET reçoit la valeur v d'une largeur de 6 bits de la part de la ligne de transmission de signaux 62 et la valeur X" de la part d'un additionneur 72,effectue la combinaison logique ET de chaque chiffre de v représenté sous la forme d'un nombre binaire et de chaque chiffre de X"j représenté sous la forme d'un nombre binaire. Les résultats de la combinaison logique ET sont additionnéspar un additionneur conservant la retenue à douze entrées et à deu sorties (CSA-Q 2) 732 en vue d'obtenir la va- leur X" x v Chaque signal de sortie de l'additionneur 732 3 est envoyé à un circuit 733 dans lequel 13 bits sont élimi- nés dudit signal, et une valeur r X" x v x 213 est obtenue sous la forme de la somme des signaux qui sont envoyés dans la ligne de transmission de signaux 734 et 735 Les signaux présents dans les lignes de transmission de signaux 734 et 735 sont additionnés respectivement dans les additionneurs à pro- pagation de retenue à une sortie 741 et 743, et les signaux présents dans les lignes de transmission de signaux 734 et 735 et -1 sont additionnés dans un additionneur conservant la retenue à trois entrées et à deux sorties (CSA-Q 3) 76. Les résultats de l'addition soht additionnés dans l'addi- tionneur à propagation de retenue 74 Une valeur lX"j x v x 2 + 1 est envoyée dans J une ligne de transmission de signaux de sortie 781 de l'ad- ditionneur 741, tandis qu'une valeur f'"j x v x 2-13 1 est j envoyée dans une ligne de transmission de signaux de sortie 782 de l'additionneur 742 Le signal présent dans la ligne de transmission de signaux 782 est inversé, ce qui envoie dans la ligne de transmission de signaux 783 la valeur bi- naire lX" x v x 2 132 J-1, dont les bits respectifs sont in- versés, c'est-à-dire la valeur absolue de EX" x v x 2 13 l, c'est-à-dire IlX'j x v x 2 131 Dans une ligne 784 de trans- 2510280 30 mission de signaux de sortie du bit de poids le plus élevé de l'additionneur 743, on obtient une valeur " O " ou " 1 " se- lon que le signe de lX"j x v x 2-1 t c'est-à-dire le signe de X" est X" 2 O ou X" O ou X" O ou Q" mes d'ondes des signaux CLOCK, e-in, CT 1, CT 2, n-in- , CT 3, n-end, START, CT 4, MDEND, CT 5, SFT 1, es-end, CT 6, CT 7, MDEND, e-out, CT 11, CT 12 et CRYPT-end, qui apparaissent dans des parties respectives de l'unité de commande de la figure 49 lorsque cette dernière est en fonctionnement. Ci après,on va donner en référence à la figure 50, 2510280 43 une description du fonctionnement de l'unité de commande 8 représentée sur la figure 49 L'unité de commande 8 reçoit et e délivre des signaux pour la commande de l'opération C-M modu- lo N de la manière suivante: le signal CLOCK du dispositif cryptographique est toujours appliqué à l'unité de commande 8 Lors de l'envoi du signal e-in à un instant t 1, la premiè- re unité de commande 230 délivre le signal CT 1 de commande d' entrée de la variable e, au moyen duquel la variable e est introduite bit par bit, et ce au moyen de 512 impulsions d' horloge Une fois achevée cette opération, la première unité de commande 230 délivre, à cet instant t 2 le signal CT 2 représentant l'achèvement de l'introduction de la variable e. Ensuite lors de l'application du signal n-in à un instant t 3, la première unité de commande 230 délivre le signal CT 3 de commande d'entrée de la variable n, avec in- troduction de cette variable N par pas de 4 bits, au moyen de 128 impulsions d'horloge A l'achèvement de cette opéra- tion, la première unité de dommande 230 délivre le signal n-end représentant l'achèvement de l'introduction de la va- riable e à cet instant t 4. Ensuite, lorsque le signal START est appliqué à un instant t 5, la première unité de commande 230 délivre un signal CT 4 de commande d'introduction de la variable M commandant l'introduction de cette variable M par ensemblesde 4 bits, au moyen de 128 impulsions d'horloge A l'achève- ment de l'introduction de la variable M, l'unité de commande 230 délivre le signal MDEND représentant la fin de l'intro- duction de la variable M à cet instant t 6 Simultanément 1 ' unité de commande 230 délivre le signal CT 5 servant à ini- tialiser les registres (figure 15) à l'intérieur du disposi- tif cryptographique, avant de réaliser le démarrage de l'opé- ration C Me modulo n. Ensuite, la seconde unité de commande 250 déli- vre le signal SFT 1 au moyen duquel le contenu du registre 102 pour e, dans lequel est mémorisée la variable e, est dé- calé circulairement vers la gauche bit par bit, et délivre 2510280 44 ce signal en tant que signal CT 1 par l'intermédiaire du circuit OU 800, à partir d'un instant t 7 A cet instant le signal CT 1 est envoyé sous la forme d'impulsions d'horloge en un nombre égal au nombre des O situés du côté d'ordre supérieur de la variable e représentéepar 512 bits Lorsque le bit de poids le plus important du registre pour equi possède une lon- gueur de 512 bits et dans lequel est mémorisé la variable e, passe à l'état " 1 " après répétition d'un tel décalage circu- laire à gauche bit par bit, la seconde unité de commande 250 envoiele signal es-end représentant la fin du signal SFT 1 à un instant t 8 Ensuite les différents signaux suivants sont délivrés en vue de l'exécution des pas 2 a et 2 b de la procédure d'exponentiation. Lors de la délivrance du signal es-end, la troi- sième unité de commande 260 délivre tout d'abordle signal CT 6 en vue de la préparation du démarrage de l'opération de multiplication-division R M 1 x M 2 modulo n, puis délivre le signal CT 7 indiquant l'opération De ce fait tous les ad- ditionneurs principaux 1101 à 110 des sections partielles 251à 258 exécutent respectivement la multiplication-division R M 1 x M 2 modulo n Lors de la réception du signal MDEND in- diquant l'achèvement de cette multiplication-division à un instant t 9, le signal CT 7 provenant de la troisième unité de commande 260 est placé à l'état 0 Le signal CARRYEND pré- sent dans la ligne de transmission de signaux 205 et le signal SIGN présent dans la ligne de transmission de signal 206 sont utilisés pendant l'exécution de la multiplication- division Ceci sera décrit ultérieurement de façon détaillée. A chaque achèvement de la multiplication-division, les signaux CT 6 et SF Pl sont délivrés de manière à effectuer de façon ré- pétée l'opération C M 1 x M 2 modulo n Mais lorsque ei de la variable e amenée par décalage au niveau du bit de poids le plus important du registre pour e est " 1 " immédiatement après l'achèvement du pas 2 a de la procédure d'exponentiation, le signal SF Pl est " O " Le signal CT 7 est délivré en tant que signal indiquant les périodes d'exécution des pas 2 a et 2 b 2510280 45 de la procédure d'exponentiation Pendant l'exécution de la multiplication-division, le signal EXP-SEL commandant la commutation des sélecteurs 1061 à 1068 est envoyé dans la ligne de transmission de signaux 221 Ici, lorsque la valeur du signal EXP-SEL est 0, le pas 2 a de la procédure d'exponen- tiation est exécuté et lorsque le signal EXP-SEL est 1, le pas 2 b est exécuté Lors de l'achèvement de l'exponentiation, le signal CRYPT-end est envoyé par la seconde unité de com- mande 250. Lors de l'introduction du signal C-out commandant la délivrance de la variable C hors du dispositif cryptographique à un instant t 10, la cinquième unité de commande 280 déli- vre le signal CT 12 indiquant que la variable C sera délivrée par pas de 4 bis, au moyen de 128 impulsions d'horloge, et le signal CT 11 représentant la période pendant laquelle le signal CT 12 est valide, reste à 1 pendant l'opération indiquée ci- dessus. De cette manière l'unité de commande 8 reçoit et délivre des signaux pour la commande d'une série de calculs pour l'introduction des variables e, N et M, en exécutant l' opération C Me modulo N et en délivrant la variable C. C Ci-après on va décrire de façon détaillée les transmissions des signaux CARRYEND et SIGN et les agencements spécifiques des unités de commande 230, 250, 260, 270 et 280. La figure 51 illustre un exemple spécifique de la première unité de commande (CTL 1) 230 et les figures 52 A à 52 J montrent les formes d'onde des signaux qui apparaissent dans les parties respectives de la première unité de comman- de 230, lorsqu'elle est en fonctionnement, les formes d'onde étant désignées par les noms correspondants des signaux sur le côté gauche. Lorsque le signal e-in provenant d'une ligne de transmission de signaux 231 est introduit par l'intermédiaire d'une ligne à retard 805 dans une bascule bistable 806, la sortie de la bascule bistable 806 passe au niveau 1 afind' ouvrir une porte 807 Ensuite le signal CLOCK présent dans 25 10280 46 -a li Qne de transmission de signaux 240 est appliqué par 1 ' Jntermédiaire de la porte 807 à un compteur 808 pour que ce dernier effectue le comptage et simultanémentest appliqué à une porte 809 de manière que cette dernière délivre un signal CT 1 ' dans une ligne de transmission de signaux de sortie 234. Le signal CT 1 ' est envoyé au circuit OU 800 de la figure 49, de manière à délivrer le signal CT 1 Lorsque le contenu du compteur 808 atteint 512, la porte 809 est fermée C'est-à- dire que 512 signaux CT 1 ' sont produits En outre le signal de sortie du compteur 808 est envoyé en tant que signal CT 2 dans une ligne de transmission de signaux 238 Lorsque le signal n-in est envoyé dans une ligne de transmission de si- gnaux 232, le signal CT 3 est délivré par une ligne de trans- mission de signaux 235, au moyen 128 impulsions d'horloge, après quoi le signal n-end est envoyé dans une ligne de transmission de signaux 239 Lorsque les signaux CT 2 et n-end sont produits tous les deux, une porte 814 est ouverte En- suite, lorsque le signal START est appliqué à la porte 814 à partir d'une ligne de transmission de signaux 233, le signal CT 4 est délivré de façon similaire 128 fois dans une ligne de transmission de signaux 236, en synchronisme avec les im- pulsions d'horloge au moyen d'une bascule bistable 815,de deux grilles 816 et 818 et d'un compteur 817, après quoi le signal MEND est envoyé dans une ligne de transmission de si- gnaux 237 De cette manière la première unité de commande 230 commande l'introduction des variables e, N et M. La figure 53 montre un exemple spécifique de la seconde unité de commande (CTL 2) 250 et les figures 54 A à 54 G montrent des formes d'onde des signaux, qui apparaissent dans les parties respectives de la seconde unité de commande 250 lorsqu'elle est en fonctionnement Lorsque le signal M'END est appliqué par l'intermédiaire de la ligne de transmission de signaux 237 à partir de la première unité de commande 230, le signal CT 5 est envoyé à une ligne de transmission de signaux 252 à partir d'une porte ( 280) et ce pendant le re- tard fourni par une ligne à retard 819 En outre, alors que 2510280 47 le signal MEND est appliqué et que le signal e provenant d' une ligne de transmission de signaux 256 reste au niveau 0, les portes 821 et 822 sont ouvertes de manière à permettre à travers elles le passage du signal CLOCK, qui est envoyé en tant que signal SFT 1 dans une ligne de transmission de signaux 251 par l'intermédiaire d'un circuit OU 823 Sous l'action du signal SFT 1, le registre 102 pour e sur la figure 15 subit un décalage vers la gauche Lorsque le bit le plus important du registre 102 pour e de la section partielle 25 passe au niveau 1, le signal ei provenant de la ligne de transmission de signaux 256 passe également au niveau 1, ce qui a pour effet que la sortie Q de la bas- cule bistable 824 passe au niveau 1, ce qui provoque l'ou- verture d'une porte 825 et l'envoi du signal es-end par l'intermédiaire d'une porte 826 dans une ligne de transmission de signaux 253 Ensuite, lors de chaque application du si- gnal STF 2 à partir d'une ligne de transmission de signaux 254, ledit signal est délivré en tant que signal SFT 1 par l' intermédiaire de la porte 825 et du circuit OU 823 Les si- gnaux de sortie provenant du circuit OU 823, c'est-à-dire les signaux SFT 1, sont comptés par un compteur 827, qui délivre le signal CRYPT-end dans une ligne de transmission de signaux 255, lorsqu'il a atteint l'état de comptage 512, après i'intro- duction du signal CT 5. De cette manière, lorsque la secondeunité de com- mande 250 est alimentée par le signal MEND représentant la fin de l'introduction de la valeur M, cette unité de commande effectue la commande du décalage circulaire du contenu du registre pour e vers la gauche jusqu'à ce que son bit de poids le plus élevé passe à 1, en délivrantle signal SFT 1 pour un décalage circulaire du registre pour é vers la gauche, et ce,d'une position lors de chaque application du signal SFP 2, etdélivrant le signal CRYPT-end après le décalage circulaire du contenu du registre pour e vers la gauche sur un total de 512 positions binaires, c'est-à-dire après un cycle de décala- ge circulaire du registre pour e. 2510280 48 La figure 55 montre un exemple spécifique de la troisième unité de commancb(CT 3) 260 représentée sur la fi- gure 49, et les figures 56 A à 56 H montrent, à titre d'exem- ple, les formes d'onde de signaux qui apparaissent dans les parties respectives de la troisième unité de commande 260 lors- que cette dernière est en fonctionnement. Lors de l'application d'un signal CT 5 par l'intermédiaire de la ligne de transmission de signaux 252 à partir de la secondeunité de commande 250, les bascules bistables 828, 829, 830 et 831 sont effacées Lors de l'application du signal es-end-par l'intermédiaire de la ligne de transmission de signaux 253 à partir de la seconde unité de commande 250, le signal CT 6 est envoyé par l'intermàédiaire d'un circuit OU 832 dans une ligne de transmission de signaux 261 et la bascu- le bistable 831 est déclenchée par l'intermédiaire d'un circuit OU 833, provoquant la délivrance d'un signal de sortie Q de la bascule bistable 831 en tant que signal CT 7 dans une ligne de transmission de signaux 263 L'opération R = M 1 x M 2 modu- lo N est déclenché et, lors de l'achèvement de ce calcul, le signal MDEND est introduit par l'intermédiaire d'une ligne de transmission de signal 264, par exemple à un instant ei, à partir de la quatrième unité de commande M 270 Le signal MDEND est appliqué par l'intermédiaire du circuit OU 833 à la bas- cule bistable 831 de manière à déclencher cette dernière en provoquant le passage du signal CT 7 de 1 à 0 Le signal ei présent dans la ligne de transmission de signaux 256 et le signal de sortie de la bascule bistable 828 sont envoyés à une porte NON OU-EXCLUSIF 834, et un signal de sortie et le signal MDEND sont envoyés à une porte ET 835, de sorte que si le signal e est 1 lorsque le signal MDEND est appliqué à l'ins- i tant t 1, le signal de sortie provenant de la porte NON OU EXCLUSIF 834 est O et le signal de sortie de la porte ET 835 reste au niveau 0, ce qui a pour effet que le signal SFT 2 n'est pas délivré dans la ligne de transmission de signaux 254, comme cela est représenté à l'instant t 2 En outre étant donné que le signal MDEND, le signal ei présents dans la li- 2510280 49 gne de transmission de signaux 256 et le signal de sortie Q de la bascule 828 sont envoyés à une porte ET 836, la sortie Q de la bascule bistable 828 passe à 1 dans le cas o le si- gnal ei est au niveau 1 au moment de l'application du signal :DEND En outre le signal MDEND à l'instant t 1 traverseles bascules bistables 829 et 830, en étant envoyé ensuite en tant que signal CT 6 par l'intermrédiaire d'une porte 837 et du circuit OU 832 dans la liane de transmission de signaux 261, à un instant t 3 Le signal de sortie de la bascule bistable 830 est envoyé par l'intermédiaire d'une porte 838 et du cir- cuit OU 833 à la bascule bistable 831 en vue de déclencher cette dernière, en produisant le signal CT 7 à un instant t 4 Par conséquent l'opération R M 1 x M 2 modulo N est re- prise, c'est-à-dire que le pas 2 b est exécuté Lorsque le signal MDEND est appliqué à nouveau à un instant t 5, les mê- mes opérations que décrites ci-dessus sont effectuées, mais, dans le cas o le signal ei est au niveau 1, le signal de sortie du circuit 834 passe au niveau 1, en provoquant l'en- voi du signal SFT 2 comme représenté à l'instant t 6 Mais, lorsque le signal eiest au niveau O lorsque le signal MDEND apparaît à l'instant t 1, le signal de sortie du circuit 834 passe au niveau 1 de manière à provoquer la délivrance du signal SFT 2 et, sous l'effet du signal CT 7 suivant, le pas 2 a est exécuté A ce moment là, le signal de sortie Q de la bascule bistable 828 est placé au niveau 0. Ainsi, dans la procédure d'exponentiation, si une condition ei = O apparaît immédiatement après le pas 2 a, alors le contenu du registre 102 pour e est décalé d'une position binaire et une opération i* i-1 est effectuée; si ei = 1 immédiatement après l'achèvement du pas 2 a, alors le pas 2 b est exécuté et le contenu du registre 102 pour e est décalé d'une position binaire, à la suite de quoi l'opération i -1 et I =l 2 X+l + 2 X t l>O 1 1 2 2 = 2 M+ 1-nt +I 2 m- ) Ä (F 32) v 2 k+w+ 1) lf 2-(F 33) 5 * ou i (F 34) 2 1 (jl Xll '. X+l(-Ij)n 2 -ml> O (F 35) X+l(-Ij-1)n 2 ml O et 12 2 si t > O Dans ce cas I dans le théorème devient I 1 1 et 12 devient 12 2. 2510280 64 Corollaire 5 Par suite de l'obtention de Rj à partir de l'équa- tion (F 18) en utilisant I' = I + I' (o I' = + 1, + 2, J 3 j O j O ,+ 2 pour I obtenu par l'équation (F 16), 1 'intervalle valeurs de R. J~~~~~~~~~~~~~~ est donnée par l'équation ( 37) Si cetintervallede R est inclus J dans l'intervallede Rj+ 1, alors le théorème est valable Lors- que le corollaire 5 est combiné au corollaire 3, l'intervalle de Rj est donné par l'équation (F 38) et lorqu'il est combiné avec le corollaire 4,l'intervalleest donné par l'équation (F 39) Lors- que ce corollaire est combiné à la fois auxcoroltaires-3 et 4, l'intervalle de Rj est donné par l'équation (F 38) Dans le cas o l'une seulement des valeurs limites inférieure et supérieure de Ij est utilisée pour le corollaire 4, I-1 et (I 2 + 2) 2 dans J~~~~~~~~~~~~~~~ l'équation (F 39) deviennent respectivement I 1 et (I 2-+ 1) corres- pondant aux valeurs limites inférieure et supérieure. -(S+A+ (I 2 + 1)) ) * 2 m+ 6 (-1) lM 1 * 2 -3 l 2 -Ij O n O 1- 2510280 67 Exemple 2 Il s'agit d'un exempledans lequel I 1 et 12 sont déterminés en utilisant le corollaire 4, et dans lequel ensui- te le corollaire 3 est utilisé. ( 1) Condition préalable Les constantes K, , a, t 1, t 2 et S, hormis m et A, sontdéterminées par les équations suivantes ; est une va- riable nouvellement définie. K 2 -k+l t 1 = 2 t 2 = 2 21 Ä= A + S S= 2 .(B) Calculs des constantes Grâce à l'obtention de I 1 et de 12 en utilisant le corollaire 4, on obtient I 1 = et 12 = 2, et -la relation 1 S I O On comprendra aisément que dans le cas de 63 j = 1, la valeur attendue 63 j= 1 devient 2-k -1 moyennant l'hypothè- se que R O est réparti de façon uniforme dans l'intervalle n k 0 (H 2) j+l je 1 i i- l( 2 R jl)-2-ml+l( 6 m 1)-2-'l+l(-Q )*n 42-m J+ 2 +a O 0- 2510280 70 La valeur moyenne est 2 i lorsaue = 1. Exemple 3 Il s'agit d'un exemple dans lequel les corollaires 1, 2 et 4 sont utilisés et dans lequel, lorsque j = 1, le corol- laire 5 est utilisé en supplément, et dans lequel les constan- tes K, A, X, w, S, t 1 et t 2, hormis m,sontréglées cc -e suit: K = 11, A = 1, À = 8, W = 1, S = 405, t 1 = A + 113 ett 2 = 1. En outre la valeur de W dans le corollaire 2 est régl&eà la va- leur W = 10. 1 -O pour X I 1 + 2 x~~~~~ S~~I + 2 ~ Qj~ 'I = I + ~* X"XX>U) W = X ',à = IJ = jj$à T l k)Ul X = O t/2 ?our W = 1 Zj,p M 4 i -1 X 12 pou m = O .22 '+ 2 + 1 ~j 1 % 2 + 1,2 u+l z j = l)X'2 '6 2 'M 1 '6 ( 2 A o Zj,p -M 1 (j-l)X-2 + 2 + À 22 ppu o 3 = + 2 M 16 (j + 2 2 Poli u =K + W + 1 (B) Calcul des constantes I 1 et 12 obtenus en utilisant le corollaire 4 ont les valeurs suivantes: I 2 + 1 =, 12 2 A partir de l'équation (F 1), on a L = m + K + 1 ..m = L X 3 L'intervalle des valeurs de S est obtenue à partir des équations (F 7) et (F 8) Maisl'interval-edes valeurs de S est rendu inférieur à celui obtenu par le calcul et W est éliminé. 2 X+ 1 + 2 _ S X + 1 . u> 2 t + 4 lX- v-U 2 l+ 1 pour X≥ O i lX Elv-2-ul pour Xj 2 X + 4 Dans ces relations, lorsque W = 1, À est un nombre pair. Sup {x} désigne un nombre entier minimum supérieur ou égal à x; par exemple Sup { 1,5 } = 2. (D) Exécution du calcul (a) Préparatif Tout d'abord on introduit N ou obtenir v. v = l 2 u ln-2-m 5 l Ensuite on introduit M 1 et M 2. (b) Calcul répété La méthode de calcul est illustrée ci-après sous la forme d'un organigramme de programme. Pas 0: j+ en R + 1,O R+ -, Pas 1: X 11 E l( 2 À Rj+i) 2-l + Z l(z ) 2 l l i= O i) P= O + Sa + j + j O -2 O Qj +, J lX" v 2 ul pour X M 1)2 -ml w= 6 (j 1)xlM 2-ml(F 70) D'après l'équation (F 15), -A-n 2-k+ -2 X t 1 n+w-6 j,2 M 1 f-2 Rj+ 1 1 ij1 j+ 1 O (F 82)' -ni -ni j -1- R +M m+S+j_-w_+l (-Ij-1)-ln 2 ll O, P étant un nombre entier. l(-I)'Ilxll = l(-I) xl + P (F 85) o O - O (A) Lorsque I O (F 89) j M-m S+j -m-1 +l(-Ij-)n 2 ml 0: J les équations suivantes sont obtenues de la même manière nue décrite ci-dessus. R -m+M -+S+aj m-1 +l(-Ij)n-2 ml + P > O (F 92) R-m +M-m+S+a i-m-1 +l(-Ij-1)n 2 l + P 2 2510280 81 : O l( 1 ~ 2 ~)-n2 ~l+n-2la Pl ~ (F 98) Avec C 1 = O ou 1 (F 99) A partir de l'équation (F 72), on a L 0, et à partie de l'équation (F 1) on a 2 K 1, la condition de l'équation (F 88) est satisfai- te par l'équation (F 7) et I'1 = I 1 , ce qui a pour effet que l'équation suivante est valable. 0 O 2 2 2 alors la conditions de l'équation (F 88) est satisfaite par l'équ~ tion (F 7) et, d'après l'équation (F 7), on a l'équation suivante avec I 2 = 12 V 2 + 2 t 2, l'équation (F 93) est va- lable, mais l'équation (F 92) ne l'est pas. (F 111) l Intervalle de R (vérification de l'équation (F 19)) L'équation (F 75) est appliquée aux équations (F 89) et (F 92) pour y remplacer l'équation (F 18). l(Rj)2-ml y 3 +S+aj-Wml +P > (F 112) o Y 3 = 0, 1 ou 2 (F 113) P Pl pour I O . l(Rj-n)2-ml k O -(F 1 i on prend RL = (valeur limite inférieure de R valeur limite inférieure de Rj+ 1). R =-(S-+A(I 12 + 1)W) 2 m + I 21 klM 1 * 2-ml' +A-n 2 +t *n-re jx M 1 . RL= (-S +t 2 m 1 n-w 2 -(I 2 + 1) -2 m) +A-2 m(nx 2-m-k-1)+ 2 {lw 6 j XM 1 2-M l ( jx'12 À-m)+} Par conséquent d'après l'équation (F 8) RL > O (F 122) A l'aide des équations (F 121) et (F 122) on a vérifié que l'intervalle de R est inclu' dans l'intervalle de Rj+ 1. Par conséquent les formules de récurrenoe fournies par les équations (F 14) à (F 19) se répètent dans l'ordre j ,=, 1, 2, 1, et on peut obtenir R , R 9 _,1 ,R 2,R 1 et I I_,I I 21, I 1. Calcul de R et Q (équations (F 120) à (F 122). L'équation suivante est obtenue en multipliant les I (j-1)X deux membres de l'équation (F 20) par j * 2 ~~~~~~~ 2 k R =R * 2 SA -IN x z M 2 j 2 ( J-l k-1 2 +u'60 ' M-n' E I -2 (j-1)k +w O a j 1 } 2 j=:l 2510280 86 Par conséquent, en introduisant R+ 1 =, = O , = = O et MO 2 à partir des équations (Fll) à (F 14) dans l'équation ci-dessus, on obtient R c :M xil -nx Q (F 122 } O RC j 1 = Ml -n Ri ~ nx Q 1 oaQ~ 1 X 1 = 2 j-) (F 124 J I D'autre part l'équation suivanteest levalable pour le ouctient Q et le re E R de (M 1 x M 2) , n: R = M 1 x M 2-nx Q (F 125) D'après les équations (F 123) et (F 125), il s'ensuit que l'on a R-R 1 = -n x (Q-Q) (F 126) Etant donné que Q et Q 1 sont des nombres entiers, on voit que la différence entre R et R 1 est un multiple entier de n. En outre R 1 satisfait à l'équation (F 19), mais I 1 et 12 y sont substituéS -(S+A+l 2 + 1 + 2 x t 2 + 1 l)2 m+w 60 lM 12 ml-2 m R O (F 82) X+(-Ij-1)-ln 2 ml (F 44 10 Yl-î ln.2 ln 2 l 2 (k-1 w+) 2 (k+w+ 1) En posant el = ,0 _ 1, de sorte que l'on obtient l'équation suivante, en tenant compte de l'équation (F 141). ô pour X k O 1 pour X O i J Ensuite on obtient l'équation suivante de la même manière que dans le cas de l'obtention de l'équation (F 119). Rj 2 + 2 t 2, les équations (F 89) et ( 92) ne sont pas valables. .I Ij> 2-t 1 1 ) qui s'avère être supérieur à la valeur ( 2 + 2 t > 1 I ~ 2 *t 1 1) 2510280 du premier I , et ce d'un montant égal à +n ou + 2 n, r ais la va- D leur limite supérieure de R à cet instant est définiepar 1 ' J équation (F 149). Par conséquent on voit que la valeur limite supérieu- re de Rj est inférieure à la valeur limite supérieure de Rj+ 1 étant donné cue, la condition t n'0 est valable en tant aue condition préalable pour le corollaire 4. Par conséquent on a montré à l'évidence que le cc- rollaire 4 est valable. Vérification du corollaire 5 D'après l'équation (F 18) il ressort à l'évidence que l'équation (F 19) est valable, ce qui a pour effet que le corrolaire 5 est valable. Comme cela a décrit ci-dessus, conformément à la présente invention, étant donné que l'opération (M 1 x M 2) n peut être exécutéeen effectuant la multiplication et la divi- sion parallèle moyennant la mise en oeuvre de la même impul- sion d'horloge, le quotient Q et/ou le reste R peut être obtenu à vitesse élevée. Calculateur de M 1 M 2 j En ce qui concerne la multiplication décrite dans le théorème, on va donner ci-après une explication supplémen- taire en rapport avec la condition X = 1. Dans l'équation (F 10),en posantw=l on obtient l'équation suivante On va donner une description dans le cas o = 6 M 2 ja ,M 2 jb et M 2 jc sont définis comme suit: ~~~~~~ 2 jc 6 5 4 M -6 (j 2 + 26 j 1)4 2 ja -6 (j-i)+ 66 (j-1)+ 5 (j-)+ 4 - 2 jb =-6 (j-1)+ 4 '2 6 (j-_)+ 3 '2 26 (j-i)+ 22 .22 + 21 2 (o -2 jc 6 (j-i)+ 266 (O-1)+ 12+ 2 '66 (j 1)+ O - 2510280 95 alors, M 2,i est donné par la relation suivante: M ~M + M 2,j D M 2 ja 2 jb + M 2 jc M 2 ja M 2 jb et M 2 cb peuvent être obtenus au moyen d'un circuit similaire à celui prévu pour Qj, Qjc décrits précédemment en liaison avec le calculateur de -Qj N en référence à la figure 62 Avec un tel agencement, la quantité des données représen- tant M 1-M'2 j est réduite, ce qui permet une réduction de la i 2,j taille du circuit de l'additionneur conservant la retenue 16. Description supplémentaire du théorème 3 n va donner une description de l'agencement géné- ral d'un circuit permettant le calcul de la valeur I au moyen j des équations (F 35) et (F 36) Etant donné que cet agencement de ce circuit est identique à celui du circuit servant à cal- culer la valeur de Qj par les équations (H 2) et (H 3) décrites précédemment dans l'exemple 2, on va décrire ce circuit ci- après en référence à la figure 66. La figure 66 montre un calculateur de quotient 9 " pour le calcul de la valeur de Q à partir des équations (H 2) et (H 3) Les lignes de transmission de signaux d'entrée 601, 602,603 et 604 introduisent des variables Rj+i j,M 1 et n. j+ 1 ' j'1 Dans un circuit ET 171 se trouve formé le produit -mni 2 Un additionneur 620 effectue une opération C 2 Rj+ 1-2-' + l 6 M 1 2-ml + 2 Le dernier terme + 2 de cet ensemble est pro- duit à l'intérieur de l'additionneur 620 Les circuits 621, 622 et 623 reçoivent N et délivrent à partir de là respective- ment N 2 '5 , -n-2-'J et C-2 n 2-' Le signal de sortie de 1 ' additionneur 620 et les signaux de sortie des circuits 621, 622 et 623 sont additionnés dansles additionneurs 625, 627 et 628, et au signal de sortie de l'additionneur 620 est ajouté un zéro dans un additionneur 626 Les additionneurs 625 à 628 délivrent chacun un O ou un 1, basé sur les calculs suivants, en fonction du fait que le signal d'une valeur Qj = 0,1,2,3 est positif, nul ou négatif. l 2 R j+ j 2l+ + l( 21 Qj) N 2-ml + 2 j+ 1 J J 2510280 96 Les signaux de sortie sont indiqués par les signaux QA 1, QA 2, QA 3 et QA 4 Ces signaux sont appliqués à un circuit 629, qui délivre un signal QB basé sur la table logique représentée sur la figure 67 Le signal QB est égal à la valeur Qj qui satis- fait aux équations (H 2) et (H 3) De cette manière la valeur Qj peut être sortie, sous la forme du signal QV qui satisfait aux équations (H 2) et (H 3). Autre méthode de multiplication-division Les indications données ci-après décrivent le fait que le calcul pour la cryptographie RSA peut être effectué même si le multiplicateur-diviseur, qui est un constituant principal du dispositif cryptographique de la présente inven- tion, est remplacé par un autre type de multiplicateur-divi- seur On va donner toutd'abord une description d'une autre mé- thode de multiplication-division, puis d'un multiplicateur-di- viseur bas sur cette méthode de calcul et enfin l'agencement du dispositif cryptographique. Autre méthode de multiplication-division Cette multiplication-division est effectuée suivant une méthode qui peut être aisément déduite d'une méthode de calculordinaire Tout d'abord la multiplication M 1 x M 2 est effectuée, puis la division (M 1 x M 2) : N est effectuée de manière à obtenir le reste. (A) Multiplication La multiplication M 1 x M 2 est effectuée de la ma- nière suivante On suppose que Z est une variable. Pas 1: Z = O Pas 2: les opérations suivantes sont effectuées dans un ordre j = 1, 2, ú Z 2 + M 1 x M 2,j Pas 3: Arrêt (B) Division La division Z : N est effectuée de la manière sui- vante Ici Rj Ici -R est une variable et z est représenté sous la forme d'un nombre binaire et est divisé de façon égale en deux ensembles de chacun X bits. 2510280 97 Z =Z2 (j 1)A j=l l Pas 4: 2 À R = L Z 2 R+ 1 J j=+ J Pas 5: les opérations suivantes sont exécutées dans un ordre j = Z,&-1, 1 Qj l n R = 2 X R + Z Qj n j+l j Zj Pas 6: R = R 1, arrêt A l'aide des pas 1 à 6, il est possible d'obtenir le reste R de (M 1 x M 2): n. Ici l'intervalle de Rl+ 1 dans le pas 4 satisfait à la condition suivante 0 + ú Z 2 pi+ 1 ijt 3 2 Z = M 1 x M 2 O EX x v x 2-l pour XJ L m+ X + 2 Dans ce cas, il en va de même que pour la méthode décrite précédemment d'obtention de Ij par approximation et 1 ' 2510280 99 on a par conséquent la relation valable suivante: ou Q = Q + j, j = 0, 1 2 Ici R est subdivisé en Rj 1 et Rj, et l'on pose Rj = jo Rj,i. (C) Division utilisant Q". 3 Dans le cas de l'utilisation de Q'j à la place de Qj, la division décrite ci-dessus varie comme suit: Pas 4: 1 ~~~ 2 î TR = T 2 j-2 ) i= i=O ~+ 1 ,1 j= 2 +l i Pas 5 ': L'opération suivante est exécut 6 edans l'ordre j = ,-1, . l -o lXj x v x 2 ul + 1 pour Xj ' O QJ X xv pour Xj autres calculateurs de quotient à l'état inopérant Grâce à un tel agencement, le dispositif cryptographique de la présente invention peut être constitué par huit microplaquettes à haute densité d'intégration possédant la même configuration et il n'y a pas besoin de prévoir une microplaquette séparée à haute densité d'intégration pour le calculateur de quotient. De même il est possible de réaliser les circuits à haute den- sité d'intégration incluant une partie du calculateur de quo- tient 9, par exemple la section de post-traitement 61 ou la section de prétraitement 60, dans les sections partielles res- pectives 251 à 258, bien que ceci ne soit pas représenté. Inversement, étant donné que seule une unité de commande 81 dans la section partielle 25 représentée sur la figure 6 est rendue opérante, il est possible de supprimer toutes les unités de commande 81 à 88 des sections partielles respectives 251 à-258 et de prévoir une seule unité de comman- de d'unemiéroplaquette à haute densité d'intégration pour réa- liser la commande des sections partielles 81 à 88 et du calcu- lateur de quotient 9. Comme cela a été décrit précédemment, conformément à la présente invention, le dispositif cryptographique servant à mettre en oeuvre l'opération cryptographique RSA C Me modu- lo N peut être-aisément réalisé grâce à l'utilisation de l'actuelle technologie à haute densité d'intégration, même si la valeur de N est extrêmement élevée Par exemple la cryptogra- phie RSA utilise la valeur N = 1010 à 10 et dans ce cas la taille du circuit du dispositif cryptographique va jusqu'à 100000 à 200000 portes Conformément à la présente invention, 2510280 104 le dispositif cryptographique peut être réalisé à l'aide d'une mémoire ROM de petite taille et avec des microplaquettes à hau- te densité d'intégration comportant 10000 à 30000 portes et possédant la même configuration. En outre, comme cela ressortira de ce qui précède, la valeur L-m est indépendante de la valeur L Par conséquent le calcul réalisé par la section de post-traitement de calcul du quotient est indépendant de la valeur L, c'est-à-dire du nombre de chiffres de la valeirn; par conséquent la multiplica- tion-division R M X M 1 x M 2 modulo N et l'opération C Me modulo peuvent être effectuéeen augmentant ou en réduisant le nom- bre des sections partielles En d'autres termes les longueurs des clés de chiffrage (n et e) peuvent être aisément modifiées au moyen d'un accroissement ou d'une réduction du nombre des sections partielles. Outre-cela, confo-rmément à la présente invention, la vitesse de fonctionnement peut être accrue grâce à la multiplication-division simultanée comme décrit précédemment. Dans ce cas l'additionneur principal n'a pas besoin d'être toujours subdivisé, c'est-à-dire que l'on peut Utiliser l'agen- cement représenté sur la figure 68. Il ressortira à l'évidence que de nombreuses mo- difications et variantes peuvent être mises en oeuvre sans sortir du cadre de la présente invention. 2510280 105 REVENDICATIONS -1 Dispositif cryptographique, caractérisé en ce que des nombres entiers M, e et N (O M 0- Qu = lX 3 x v x 2-Ul pour X O Q= lX" x v x 2-l pour X' * la valeur R 1 + 6-n qui satisfait à la relation O R 1 + ô-n O Q j Q"= lX x v x 2 U lorsque X O et pour calculer R = 2 R + R Q" -n dans l'ordre j Q, J ~~J J J ú-1, 1, qu'il est prévu des moyens de calcul de compensation pour calculer, lorsque R 1 k 0, R 1 = R 1 + N juqu'à ce que l'on obtienne R 1 2 O, et que ledit additionneur principal est subdivisé en plusieurs sections partielles de même fonction , que 2510280 115 les variables M et N sont divisées pour être amenées sous forme de nombres entiers binaires de largeur fixe et sont envoyés séqej tiellement aux sections partielles,que M" 2 et Qj sont envoyés en commun auxdites 2,j j sections partielles, que lesdites sections partielles effectuent chacune le calcul Z = Z + M 1 x Me 2 j et R = 2 Rj+ 1 +Z -Qlj, N pour j+ 1 Zj j les valerus M 1,n,Qj M" 2 j et Rj+ 1 qui leur sont appliquées, et que lesdites sections partielles sont chacune raccordées à une section partielle d'ordre supérieur par l'intermédiaire d'une ligne de transmission de signaux de connexion pour que leur soit appliquée une partie du résultat Z du calcul, et que cha- cune desdites sections partielles est raccordée à une section partielle d'ordre inférieur, par l'intermédiaire d'une seconde ligne de transmission de signaux de connexion en vue de lui envoyer le résultat R du calcul. j 22 Dispositif cryptographique selon la revendica- tion 1, caractérisé en ce que des premier et second registres additionneurs sont prévus pour constituer ledit registre addi- tionneur, que la variable Rj est subdivisée en Rj O et en R (c'est-à-dire Rj =i O ji), que Rj O et Rj 1 sont mémorisés dans lesdits premier et second registres additionneurs et que l'additionneur principal effectue l'opération suivante: 1 1 X R = 2 Rj+,i + Z Qn. i-O j'' i=O j'i j j