FR 2658932 A1 19910830 FR 9002274 A 19900223 "Procédé de codage selon la méthode dite RSA, par un microcon- trôleur et dispositif utilisant ce procédé". Description: La présente invention concerne un procédé pour la mise en oeuvre par un microcontrôleur de la méthode de codage RSA ou une méthode dérivée, qui consiste à effectuer une expo- nentiation par un nombre e, modulo N, d'un message M; N, e et M étant des nombres entiers de grande longueur compris dans un format à N bits, procédé selon lequel le calcul d'exponentia- tion modulo N est décomposé en une suite de deux opérations successives, la première de ces opérations étant de la forme Bi = ai X + T 2 m expression dans laquelle Bi et X sont des variables de cal- cul qui dépendent de M et de N, dans laquelle ai est un ex- trait, de format restreint à m bits, d'une variable de calcul A dont la valeur découle d'une étape d'opérations précédentes, extrait pris dans l'ordre décroissant de poids de A, au rang i, et T une variable de totalisation utilisée dans le calcul de la variable A, et la deuxième opération consistant à rédui- re la longueur de la variable Bi par soustraction d'un mul- tiple déterminé du module N, et procure une nouvelle valeur Ai à la variable A. La présente invention concerne également un dispo- sitif mettant en oeuvre un tel procédé. La méthode de codage dite RSA, du nom de ses inven- teurs, est connue notamment du document US 4 405 829 Les avantages de cette méthode, notamment le fait qu'elle soit du type: à clé publique, sont également bien connus Sa mise en oeuvre au moyen de calculateurs puissants, dotés de mémoires suffisantes pour stocker des nombres de grande longueur, ne pose pas de difficultés particulières Il en va autrement lorsqu'on cherche à exploiter la même méthode au moyen de sys- tèmes de très petite taille, et en particulier au moyen de circuits semiconducteurs intégrés du genre microcontrôleur, susceptibles d'être incorporés dans une carte portative dite carte intelligente ou encore carte à puce Etant donné que l'on prévoit de nombreuses applications possibles et utiles de ce genre de dispositif dans le domaine de la transmission pri- vée (authentification d'un interlocuteur, signature, échange de clés, transfert de fonds confidentiels, monnaie électro- nique etc) des recherches importantes sont entreprises ac- tuellement dans ce domaine Elles ont pour but d'obtenir un procédé et des moyens de mise en oeuvre de la méthode de coda- ge RSA qui réussiraient à accomplir le traitement des données dans un temps raisonnable (au plus de l'ordre de la seconde), malgré les limitations sérieuses entraînées par l'emploi d'un dispositif intégré réalisé selon les technologies actuelles. Au titre des limitations d'ordre technologique des dispositifs actuels on peut citer la faible capacité mémoire (quelques centaines d'octets), la vitesse d'horloge limitée (de l'ordre de 8 M Hz seulement) et le faible nombre de bits traités en parallèle ( 8 ou 16 bits seulement). Un procédé pour la mise en oeuvre par un microcon- trôleur de la méthode de codage RSA qui est conforme au para- graphe introductif, a été décrit dans le document FR-A 2 613 861. L'algorithme de traitement, tel qu'il y est dé- crit, évite d'avoir à effectuer des calculs sur des nombres de grande longueur et utilise à cette fin un fractionnement des variables de calcul et une réduction modulo N après chaque multiplication partielle, de manière à éviter un accroissement de la longueur de ces variables au fur et à mesure d'un trai- tement poursuivi séquentiellement. Un inconvénient important du procédé connu réside dans le fait qu'à chaque étape de réduction modulo N, un test de signe est nécessaire, qui détermine si la soustraction du multiple de N a été excessive, auquel cas une addition de N sera opérée pour redonner une valeur positive à la variable de calcul A Un tel inconvénient n'est d'ailleurs pas limité au cas de l'algorithme connu du document cité plus haut, mais se retrouve de manière générale, dans l'état actuel de la techni- que. Tandis que les opérations arithmétiques peuvent être exécutées à grande vitesse par une cellule de calcul spé- cialisée, associée en parallèle à une unité centrale de ges- tion du programme, des opérations de test de signe ne peuvent être exécutées que par l'unité centrale, et le fonctionnement de la cellule doit alors être interrompu en attendant le ré- sultat du test. Le ralentissement du traitement dû aux opérations de test en question est d'autant plus significatif qu'il doit intervenir un très grand nombre de fois pendant le calcul d'exponentiation modulo N, et que le temps de cycle opératoire de l'unité centrale est comparativement lent par rapport au temps de cycle opératoire de la cellule de calcul, typiquement dans un rapport de 8 à 1. Aussi, l'invention a-t-elle pour but de proposer un procédé permettant l'exécution d'un codage par la méthode RSA au moyen d'un microcontrôleur muni d'une cellule de calcul spécialisée, qui soit plus rapide que le procédé connu, notam- ment par le fait que des tests de signe ou de grandeur de va- riables de calcul, seraient rendus beaucoup moins fréquents. A cet effet, le procédé de mise en oeuvre de la mé- thode de codage RSA selon la présente invention est caractéri- sé en ce qu'on effectue la deuxième opération par une quasi- réduction modulo N obtenue par la relation Ai = q N'+R dans laquelle N' est la valeur complémentée à deux de N dans le format à N bits, o q est un quotient entier dans un format à p bits fixé, approché par défaut, de la division Bi/N, avec p>m, et o R est une variable fournie par les N bits de poids faibles de la variable Bi, opération dont le résultat Ai est susceptible de contenir un faible multiple du module N et donc de présenter un dépassement de d bits de poids forts par rapport au format à N bits, en ce qu'on se fixe un nombre donné d'opérations successives et une tolérance d'approxima- tion de q tels que le nombre de bits d du dépassement accumulé lors desdites opérations successives soit au plus égal à p-m, et en ce qu'on effectue une quasi-réduction modulo supplémen- taire à la suite dudit nombre donné d'opérations, qui produit une nouvelle valeur de la variable A strictement dans le for- mat à N bits. Comme le procédé selon l'invention prévoit l'utili- sation d'un quotient q approché par défaut, la réduction de longueur de la variable Bi ne peut en aucun cas fournir un résultat de signe négatif et il n'est donc plus nécessaire de tester ce signe Le traitement peut ainsi être exécuté de ma- nière systématique et sans interruption, au moins durant un certain nombre d'opérations successives au-delà desquelles on pourrait courir le risque que l'accumulation du dépassement ne puisse plus être pris en compte dans le format à p bits du quotient q. En effet, le fait d'utiliser une valeur de quotient approché q conduit à la possibilité d'une réduction modulo in- complète qui est susceptible de fournir un résultat Ai dont le nombre de bits dépasse le format à N bits fixé au départ. C'est pourquoi on a choisi un format pour le quotient approché q, de p bits, qui est plus élevé que le format à m bits utili- sé pour le multiplicateur ai dans l'opération ai X. Le nombre prédéterminé d'opérations exécutées suc- cessivement en laissant au dépassement de la variable Ai la possibilité de s'accroître est avantageusement choisi égal au nombre de multiplications ai X suivies de leurs quasi-réduc- tions modulo N, qui sont nécessaires pour épuiser la variable A à l'aide de ses extraits successifs ai Ce nombre corres- pond à l'entier supérieur du rapport n/m. La valeur du quotient approché q, possédant le de- gré de précision recherché, peut être déterminée, selon l'in- vention, de plusieurs manières. Un premier mode de mise en oeuvre de l'invention, dans lequel la valeur du module N est prise dans un intervalle particulier, est caractérisé en ce que ledit intervalle parti- culier est égal à: 2 N 2 (n-m); 2 N 1 et en ce que la valeur du quotient approché q est fournie par les bits des poids forts de la variable Bl qui dépassent du format à N bits. Selon ce mode de mise en oeuvre, la valeur du quo- tient approché q est trouvée immédiatement et peut être recy- clée dans l'organe de traitement spécialisé, en tant qu'opé- rande pour la réduction modulo N sans même transiter par une mémoire de données L'emplacement mémoire correspondant peut donc être économisé. Lorsque ce mode de mise en oeuvre est appliqué à des variables à N bits o N est inférieur à 2000, on choisit avantageusement un nombre de bits p du quotient approché q égal à 32 et un nombre de bits m dudit format réduit de la va- riable ai égal à 24. Ces nombres de bits sont des multiples de 8, et sont bien adaptés à un microcontrôleur travaillant par mots de 8 bits auquel est associé une cellule de calcul travaillant également sur des opérandes à 8 bits La valeur de p-m est égale à 8 bits (soit un octet) permettant de recevoir le cumul de dépassement consécutif à une réduction modulo N éventuelle- ment incomplète jusqu'à ce qu'une réduction supplémentaire ne soit exécutée. En restreignant l'intervalle dans lequel la valeur du module N est choisie, on pourrait également augmenter le nombre d'opérations enchaînées successivement avant qu'une quasi-réduction modulo supplémentaire ne devienne nécessaire. Inversement, on pourrait également élargir l'inter- valle dans lequel on choisit la valeur du module N à la condi- tion de réduire de façon corrélative le nombre d'opérations successives qui sont enchaînées sans réduction modulo supplé- mentaire. Le procédé selon l'invention s'applique également lorsque la valeur du module N est choisie de manière quelcon- que parmi les nombres à N bits. En effet, un deuxième mode de mise en oeuvre de l'invention, qui s'applique dans un tel cas, pour des varia- bles à N bits o N est inférieur à 2000, est caractérisé en ce que l'on choisit un nombre de bits p du quotient approché q égal à 32 et un nombre de bits m dudit format réduit de la va- riable ai, égal à 24, en ce qu'après avoir effectué la pre- mière opération: Bi = ai X + T 22 on détermine la valeur du quotient approché q par une opéra- tion supplémentaire Ii.N* dans laquelle Si représente les bits de poids forts de la variable Bi qui dépassent du format à N bits, et N* repré- sente un nombre binaire limité à ses 56 bits les plus signifi- catifs de l'inverse du module N, opération supplémentaire dont le résultat, limité à ses 32 bits les plus significatifs, fournit la valeur du quotient approché q, et en ce qu'on ef- fectue ensuite la quasi-réduction modulo N par l'opération Ai = q N' + R déjà citée. La valeur N* peut être précalculée à l'avance et fournie au microcontrôleur en tant que donnée au même titre que N ou N' La valeur du quotient approché q se trouve déter- minée à la suite d'une petite opération supplémentaire (multi- plication de deux nombres, l'un de 4 octets et l'autre de 7 octets), qui est du même type que l'opération de réduction mo- dulo N mais beaucoup plus courte puisque le multiplicande n'est que de 7 octets Avec la facilité de pouvoir choisir pour N un nombre quelconque et non pas dans un intervalle dé- terminé comme dans le premier mode de mise en oeuvre, on al- longe la durée du traitement, seulement d'environ 15 %. L'invention concerne également un dispositif muni d'une unité centrale de microcalculateur commandée par un pro- gramme caractérisé par le fait que ledit programme met en oeu- vre le procédé défini ci-dessus. D'autres caractéristiques, détails et avantages de l'invention seront mis en évidence à l'aide de la description qui va suivre en regard des dessins annexés dans lequels: la figure 1 représente un algorithme de calcul de l'exponen- tiation par e d'un mot M à N bits, o e est également un nombre à N bits, la figure 2 représente un algorithme déduit de celui de la figure 1 permettant d'aboutir à la valeur de Me modulo N, o N est un module à N bits, la figure 3 représente une partie de l'algorithme de la fi- gure 2 dans un développement plus détaillé qui met en jeu le procédé selon l'invention, la figure 4 donne un schéma-bloc montrant l'organisation d'un microcontrôleur mettant en oeuvre le procédé selon l'invention, et la figure 5 montre une vue schématique d'une cellule de cal- cul pouvant être incorporée dans le microcontrôleur de la figure 4. Les procédés dits d'exponentiation binaire consis- tant à calculer la valeur de Me sont bien connus L'un d'eux qui exploite l'exposant e dans un ordre régressif de poids se- ra rappelé ici très brièvement dans le but de fixer les nota- tions et de faire bien comprendre la hiérarchie des calculs. On fixe un indice j = n, o N est égal au nombre de bits de l'exposant e exprimé en binaire, et une variable de calcul A initialisée à la valeur 1 On effectue ensuite une boucle de calcul dans laquelle on réalise le carré de A placé sous la variable B, puis on donne une nouvelle valeur de A = B, après quoi si le bit de l'exposant e au rang j est égal à 1 on effectue une opération supplémentaire consistant à écrire B = A M dont la valeur de B est remise sous la variable de calcul A alors que si le bit de e au rang j est égal à O cette opération est omise Puis on passe au bit juste inférieur de e en faisant j = j-1 après quoi on reboucle les opérations, com- me indiqué à la figure 1 Les opérations sont poursuivies tant que j est supérieur à O Le bit de poids faible de e est exploité pour j = 1, ce qui revient à dire que lorsque j = O le calcul est terminé et la variable de calcul A fournit la valeur de Me. La méthode de codage RSA consite à effectuer l'ex- ponentiation par un nombre e modulo N d'un message M; N, e et M étant des nombres entiers de grande longueur compris dans un format à N bits, N pouvant être de l'ordre de 512 bits. Un premier effet de la fonction modulo N est que le résultat est ramené à un format qui ne dépasse pas N bits Une autre propriété de la fonction modulo N est que l'on peut choisir le moment o on applique la réduction modulo N sans nuire à l'exactitude du résultat final, ce qui offre l'avanta- ge de réduire la longueur de la variable de calcul avant qu'elle n'atteigne une longueur prohibitive pour un microcon- trôleur dont la capacité de calcul et la quantité de mémoires sont très limitées. La figure 2 indique comment l'algorithme de la fi- gure 1 peut être modifié pour obtenir l'exponentiation par un nombre e, modulo N, d'un message M On entre dans le processus de calcul comme précédemment en faisant j = N et A = 1, et on effectue le calcul de B = A A que l'on peut réduire alors en une nouvelle valeur de la variable de calcul A en faisant A = B modulo N Lorsque le bit de e pris au rang j est égal à 1, on effectue ensuite B = A M que l'on réduit encore en po- sant A = B modulo N Lorsque le bit de e au rang j est égal à O cette double opération est omise On obtient alors une cer- taine valeur de la variable A à l'issue de cette étape de cal- cul, après quoi on effectue j = j-1 et on répète ces opéra- tions en boucle telles qu'indiquées à la figure 2, jusqu'à ce que la variable d'indice j soit égale à 0 Lorsque l'on a épuisé les bits de la variable e, un par un, la variable de calcul A fournit alors la valeur recherchée de Me modulo N. On peut observer sur la figure 2 que les couples d'opérations indiqués aux repères 1 et 2 sont de nature identique Pour les opérations de chacun de ces couples d'opérations, la première est du type B = A X tandis que la seconde est du type A = B modulo N Comme dans la première opération du type B = A X, o A et X sont des nombres de grande longueur, il n'est pas possible en général de faire exécuter cette opéra- tion directement par un microcontrôleur à faible capacité de calcul En réalité les couples d'opérations sus-indiqués se- ront traités par fractions imbriquées entre elles, de manière à ce que la longueur des variables ne progresse pas de beau- coup par rapport au format à N bit. On va donc maintenant détailler le processus sé- quentiel permettant d'obtenir un résultat équivalent au couple d'opérations noté 1 ou 2 sur la figure 2. La figure 3 montre un algorithme plus détaillé équivalent aux couples d'opérations 1 et 2 sus-mentionnés On place sous la variable X une valeur qui est égale soit à A soit à M selon qu'il s'agit d'une opération du type 1 ou du type 2 Sachant que la variable de calcul A va être exploitée par tranches ou extraits à format restreint ai, à m bits, on détermine en conséquence un indice de boucle i dont la valeur est égale à l'entier immédiatement supérieur de la division n/m On utilise une variable de totalisation T que l'on ini- tialise à O En partant de la tranche de poids forts corres- pondant à l'extrait ai de la variable A, on effectue une boucle de calcul dans laquelle on calcule Bl = ai X + T 2 puis on effectue une réduction de longueur de la variable Bi selon la relation Ai = q N'+ R. Conformément au procédé selon l'invention la valeur actuelle de la variable Ai représente une nouvelle valeur de la variable Bi à laquelle on a soustrait un multiple déter- miné du module N, procurant ainsi une réduction de la longueur de la variable Bi Cette opération s'apparente à la fonction modulo N mais du fait que cette réduction peut être incomplète elle a été appelée précédemment opération de quasi-réduction modulo N, puisque la variable Ai est susceptible de contenir un faible multiple du module N On fixe une variable R dont la valeur est fournie par les N bits de poids faibles de la va- riable Bi, et q un quotient approché par défaut de la divi- sion Bi/M dans un format à p bits fixé, o p est plus grand que m La valeur de la variable N' est le complément à deux de N dans le format à N bits Le terme q N' est donc un équiva- lent du terme -q N Du fait que la valeur de Ai est suscep- tible de contenir encore un faible multiple du module N (con- trairement à l'opération stricte de réduction modulo N), ce résultat Ai est donc susceptible de présenter un dépassement de d bits de poids forts par rapport au format à N bits C'est pourquoi on a choisi un format pour la variable q à p bits, le nombre p étant supérieur au nombre m de manière à pouvoir con- tenir le dépassement d en question. On affecte à la variable T la valeur actuelle de la variable Ai après quoi on diminue d'une unité l'indice de boucle i et l'on répète l'opération dans la boucle indiquée à la figure 3 jusqu'à ce que le dernier extrait ai, de poids faible, ait été exploité On se fixe un nombre donné d'opéra- tions successives dans la boucle indiquée à la figure 3 ainsi qu'une tolérance d'approximation de q tels que le nombre de bits d du dépassement accumulé lors desdites opérations suc- cessives soit au plus égal à p-m Dans l'exemple représenté à la figure 3, ledit nombre d'opérations successives est égal à i, ce qui fixe du même coup la tolérance d'approximation de q A l'issue des i calculs en boucle le dernier résultat Ai devient le résultat A 1 que l'on place sous la variable Bj On effectue ensuite une quasi-réduction modulo N supplémentaire identique à celle qui est pratiquée à l'intérieur de la boucle de calcul, et qui produit une nouvelle valeur de la variable de calcul A, en effectuant l'opération A = q N'+ R expression dans laquelle les variables ont la même signification que pré- cédemment et produisent une réduction de longueur de la varia- ble Bl qui fait disparaître tout dépassement et ramène cette variable dans un format à N bits Dans l'algorithme représen- té à la figure 3 on a fait figurer une condition i = O En il réalité il ne s'agit pas ici d'un test à proprement parler (au sens informatique du terme), car en pratique on a lancé le dispositif de calcul dans l'exécution de l'algorithme de la figure 3 en lui précisant le nombre i de boucles d'opérations à effectuer En définitive, cet algorithme ne présente aucun test de signe ni de grandeur et est effectué de manière systé- matique par un organe de calcul spécialisé, comme on le verra plus loin, sans qu'il soit nécessaire d'effectuer une inter- ruption sous les ordres de l'unité centrale du microcalcula- teur. La valeur du quotient approché q doué du degré de précision requis, peut être déterminée de plusieurs manières. Un premier mode de mise en oeuvre de l'invention dans lequel la valeur du module N est prise dans un intervalle particulier se caractérise par le fait que cet intervalle par- ticulier est égal à: 2 N 2 (n-m); 2 N 1 et en ce que la valeur du quotient approché q est fournie par les bits de poids forts de la variable Bi qui dépassent du format à N bits. Selon un exemple avantageux dans lequel N est infé- rieur à 2000, on choisit un nombre de bits p du quotient ap- proché q qui est égal à 32 et un nombre de bits m du format réduit de la variable ai qui est égal à 24 On dispose donc de 8 bits ( 1 octet) pour recueillir le dépassement d suscepti- ble de se produire dans des cas très défavorables au cours du processus de calcul en boucle répété i fois Il y a lieu de remarquer que dans le calcul Bi = ai X + T 2 n, le terme ai.X reste toujours strictement dans un format à (n+m) bits alors que c'est la valeur T 2 m qui peut dépasser un tel for- mat et faire apparaître un dépassement d Du fait que ce dé- passement est créé à l'addition on dispose d'un octet pour re- cueillir le cumul de ce dépassement durant les i calculs en boucle et par conséquent on dispose du nombre de 255 pour cumuler un tel dépassement alors qu'un tel dépassement est généralement d'une valeur de 1 dans un cas défavorable, au pi- re de 2, et exceptionnellement (mais une seule fois), de 3. Ceci revient à dire que l'on dispose d'un nombre de tours de boucle > 100 avant que le dépassement ne puisse plus être contenu dans l'octet qui lui est réservé A titre indicatif pour des variables de départ pour lesquelles N est égal à 512 bits, le nombre i de calculs en boucle est égal à 22 seulement. Comme on le verra ci-après les nombres de bits in- diqués à titre d'exemple sont des multiples de 8 bits et sont avantageux pour la raison qu'ils sont bien adaptés à un micro- contrôleur qui travaille par mots de 8 bits auquel est asso- ciée une cellule de calcul travaillant également sur des opé- randes à 8 bits. On a indiqué dans ce qui précède un exemple pour lequel le nombre d'opérations successives effectuées sans avoir recours à une quasiréduction modulo N supplémentaire est égal à i, c'est-à-dire le nombre d'opérations successives nécessaires pour exploiter la variable A à l'aide de ses ex- traits successifs ai On pourrait toutefois opérer différem- ment par exemple en augmentant la précision du quotient appro- ché q par le choix d'un intervalle du module N plus restreint, ce qui autorise alors à réduire le nombre p-m de bits réservés à accueillir le dépassement de format de la variable de calcul A, ou au contraire en élargissant l'intervalle particulier dans lequel la valeur du module N a été choisie, ce qui con- duirait soit à augmenter le nombre de bits p à utiliser pour contenir la variable q soit encore, en conservant une valeur de p égale à 32 bits, à réduire le nombre d'opérations enchaî- nées successivement à N bits. Le procédé selon l'invention est d'une mise en oeu- vre immédiate lorsque la valeur du module N est prise dans un intervalle particulier Mais il s'applique également lorsque la valeur du module N est choisie de manière quelconque parmi les nombres à N bits En effet, selon un deuxième mode de mise * en oeuvre de l'invention, on est conduit par une petite opéra- tion supplémentaire à déterminer la valeur du quotient appro- ché q possédant la tolérance d'approximation convenable. Comme les grandeurs des variables de calcul sont généralement corrélées entre elles on va décrire ce mode de mise en oeuvre à l'aide d'un exemple pour lequel ces variables possèdent un format dont la valeur est numériquement fixée Le nombre de bits N des mots de grande longueur est inférieur à 2000, le nombre de bits p du quotient approché q est égal à 32, le nombre de bits m du format réduit de la variable ai est égal à 24 Le procédé de calcul schématisé à la figure 3 est encore utilisé de sorte que la première des opérations ef- fectuées en boucle est donnée par Bi = ai X + T 2 m. La valeur du quotient approché q ne peut plus être fournie directement par les bits de poids forts de la variable Bi qui dépassent du format à N bits Le mot li représenté par ces bits de poids forts dépassant du format à N bits est néanmoins utilisé indirectement après transformation par une petite opération pour fournir la valeur du quotient approché q Comme on se permet selon l'invention une tolérance d'appro- ximation sur le quotient approché q, la transformation dont il va être question ne requiert pas non plus une précision très grande et peut être effectuée avec un nombre restreint de bits. Selon ce mode de mise en oeuvre de l'invention on effectue le produit úi N* dans lequel N* est une varia- ble constituée par un nombre binaire limité à ses 56 bits ( 7 octets) les plus significatifs de l'inverse du module N. La valeur qui résulte de cette multiplication est encore limi- tée à ses 32 bits ( 4 octets) les plus significatifs, valeur qui fournit le quotient approché q recherché A la suite de cette opération on effectue comme précédemment l'opération de réduction de longueur de la variable Bi par une opération Ai = q N'+ R, opération dans laquelle les variables ont la même signification que dans le précédent mode de mise en oeu- vre. Il est à noter que la valeur de N* est un paramè- tre qui peut être fourni au microcontrôleur au même titre que le module N ou son complément à deux N' de sorte que ce para- mètre n'est pas nécessairement calculé par le microcontrôleur lui-même En définitive avec la facilité que l'on peut choisir maintenant une valeur du module N de valeur quelconque parmi les nombres à N bits, on applique le même procédé que précé- demment à l'exception d'une petite opération supplémentaire pour déterminer la valeur du quotient approché q, opération qui est comparativement très courte puisqu'elle fait interve- nir une multiplication de deux nombres dont l'un est à un for- mat de 4 octets et l'autre à un format de 7 octets, opération supplémentaire qui n'allonge que d'environ 15 % la durée du traitement par rapport au premier mode de mise en oeuvre dans lequel la valeur du module N était choisie dans un intervalle particulier. Par rapport à cet exemple dans lequel les formats des variables ont été fixés numériquement, exemple représen- tant un mode pratique de mise en oeuvre préféré, on comprendra que le spécialiste est à même de fixer d'autres règles concer- nant la précision de la détermination du quotient approché q telles que la quasi-réduction modulo N soit effectuée de la manière indiquée, de manière systématique, et sans test pen- dant un nombre prédéterminé d'opérations successives après quoi une opération de quasi-réduction modulo N supplémentaire est appliquée de manière à supprimer le dépassement accumulé au cours de ces opérations successives. A l'aide des figures 4 et 5, on va maintenant dé- crire brièvement un exemple de microcontrôleur permettant une mise en oeuvre avantageuse et très efficace du procédé selon l'invention et un exemple d'une cellule de calcul pouvant être incorporée dans un tel microcontrôleur Il est à noter que ces dispositifs font, en eux-mêmes, respectivement l'objet des de- mandes de brevet français N' 89 17 455 et 89 17 456 déposées le 29 décembre 1989, demandes de brevets dans lesquelles ces dispositifs sont décrits avec plus de détails. Le microcontrôleur représenté schématiquement à la figure 4 comporte une unité centrale (CPU) 15, une mémoire de programme (ROM) 16, une mémoire de travail (RAM) 17, une cel- lule de calcul symbolisée par le rectangle en trait interrompu 18, ainsi qu'une unité de registres état et commandes (E C) 19 et un séquenceur (SE) 20 L'unité centrale 15 échange des données avec la mémoire de programme 16, l'unité d'état et de commandes 19, le séquenceur 20 au moyen d'un bus de données 7 et émet des valeurs d'adresses à la mémoire de programme 16 au moyen d'un bus d'adresses 8 L'unité centrale 15 peut égale- ment échanger des données et des adresses via les bus respec- tifs 7 et 8 avec la mémoire de travail 17 mais les accès à la mémoire de travail 17 ne sont pas directs. Le bus de données 7 qui est lié à l'unité centrale accède au port de données de la mémoire de travail 17 via une première entrée d'un multiplexeur de commutation de don- nées 4, dont la deuxième entrée communique avec un bus dit mlocalu 10 dont le rôle sera expliqué ultérieurement Le port d'adresses de la mémoire de travail 17 est relié à la sortie d'un autre multiplexeur dit de commutation d'adresses 5 dont quatre entrées sont reliées au bus d'adresses 8, respective- ment: pour la première entrée, via un registre double 122-222 d'adresses pour un opérande t, registre double qui est arrangé en file d'attente série, pour la deuxième entrée, via un autre registre double 121-221 également arrangé en file d'attente série pour l'adresse d'un opérande x, pour la troisième en- trée, via un registre simple 211 pour l'adresse d'un opérande a ll et enfin, pour la quatrième entrée, via un autre registre double 123-223 pour l'adresse d'un résultat d'opération b Les registres pointeurs d'adresses 122, 121, 211, 123 peuvent être chargés par l'unité centrale 15 tandis que les registres pointeurs 222, 221 et 223 sont conçus pour recevoir les va- leurs d'adresses de leurs registres homologues dans chacune des files d'attente correspondantes et sont susceptibles en- suite d'être incrémentés ou décrémentés automatiquement par le séquenceur 20 Le registre pointeur simple 211 peut également, après chargement par l'unité centale 15, être incrémenté ou décrémenté automatiquement par le séquenceur 20. La cellule de calcul 18 possède quatre entrées 11, 12, 13 et 14 pour des opérandes alll, al 2 l, al 3 l et al 4 l ainsi que des entrées 21 et 22 pour des opérandes respectivement xi et ti Entre le bus local 10 et les entrées d'opérande 11, 12, 13, 14 sont interposés des registres respectivement 311, 312, 313 et 314 dans lesquels la valeur des opérandes mentionnés est stockée Entre l'entrée 21 de l'opérande xi et le bus local 10 est interposée une paire de registres 321-421 arrangés en file d'attente série, de même qu'entre l'entrée 22 de l'opérande ti et le bus local 10 est interpo- sée une paire de registres 322-422 arrangés en file d'atten- te La cellule de calcul 18 possède encore une sortie 23 pour un résultat bi qui transite vers le bus local 10 via un re- gistre de sortie 323 Pour la clarté de la figure, le détail des liaisons de commande n'a pas été représenté Toutefois un ensemble de liaisons de commande 47 représenté en traits mix- tes, figure de manière symbolique les liaisons de commande en- tre l'unité de registre état et commandes 19, le séquenceur 20 et la cellule de calcul 18 laquelle reçoit ces commandes sur un port 25. La particularité du microcontrôleur représenté à la figure 4 réside principalement dans le fait que, grâce au bus local 10, des données peuvent transiter, via le multi- plexeur de commutation de données 4, entre la mémoire de tra- vail 17 et les ports de données de la cellule de calcul 18, et ainsi cette cellule peut effectuer une série de calculs sous la commande du séquenceur 20 sans intervention de l'unité centrale 15 Pendant cette série d'opérations l'unité centrale est à même de recharger les pointeurs d'adresses dans les registres pointeurs 121, 122 et 123 en vue d'une série de calculs ultérieurs. Dans un exemple pratique de mise en oeuvre du procédé selon l'invention, toutes les données traitées se présentent sous un format uniforme à 8 bits Les variables de calcul T et X sont découpées par mots de 8 bits qui, à un rang de poids i constituent les opérandes xi et ti Pour un couple de valeurs xi, ti donné, ces valeurs sont d'abord chargées en deux cycles d'horloge dans les registres 321 et 322 via le bus local 10 Un troisième cycle d'horloge est utilisé pour inscrire dans la mémoire de travail 17 un résultat bi stocké dans le registre 323 La cellule de calcul 18 peut fonctionner par cycle à 4 pas utilisant les opérandes al 1 l à al 4 l ou encore par cycle à 3 pas, l'opérande al 4 l n'étant pas utilisé et l'entrée 14 non utilisée. Pour effectuer une opération du type Bi = ai X + T on utilise un fonctionnement de la cellule de calcul 18 à cycle à 3 pas, les opérandes al 1 l à al 3 l représentant trois octets successifs formant ensemble les trois octets de la variable ai Comme on le verra par la suite, la cellule de calcul 18 est susceptible de fournir un unique résultat bi à la suite du cycle de calcul à 3 pas revenant à effectuer l'opération ai xi + ti Durant le cycle d'horloge pendant lequel un résultat bi est transféré à partir du registre 323 dans la mémoire de travail 17, de nouvelles valeurs des opérandes xi et ti sont transférées simultanément des registres respectifs 321 et 322 vers des registres correspondants 421 et 422 Chacune des variables de calcul T, X, et Bi étant stockée dans la mémoire de travail 17 par octets d'adresses consécutives, ces adresses sont pointées par les registres pointeurs respectifs 221, 222 et 223 par incrémentation ou décrémentation sous la commande du séquenceur 20. Lorsqu'on effectue une opération de quasi-réduction modulo N correspondant à la relation Ai = q N'+ R, à l'en- trée 21 l'opérande xi est remplacé par un octet n'i du pa- ramètre N' pris au rang i, à l'entrée 22 l'opérande ti est remplacé par un octet ri tiré de la variable R, et aux qua- tre entrées 11, 12, 13, 14 sont appliqués les 4 octets succes- sifs formant ensemble le quotient approché q La cellule de calcul 18 fonctionne alors à 4 pas effectuant cycliquement le traitement de chacun des octets formant ensemble le quotient q pour un couple de valeurs n'i et ri Un calcul est effec- tué à chaque pas du cycle à 4 pas tandis que le bus local 10 est à nouveau occupé pour la durée de deux cycles d'horloge pour le rechargement des données d'opérande dans les registres 321 et 322 plus un cycle d'horloge pour le transfert du résul- tat à partir du registre 323 vers la mémoire de travail 17. Dans ce cas le bus local 10 reste inoccupé pendant un cycle d'horloge sur les 4 qui forme un cycle de calcul. Pour un format de variables de départ N, M, à 512 bits c'est-à-dire 64 octets, il faudra effectuer 67 cycles à 3 pas pour exploiter entièrement et par octets les variables X et T permettant d'obtenir un résultat Bi De manière sembla- ble il faudra 68 cycles à 4 pas pour exploiter entièrement et par octets les variables N' et R (y compris le 'vidage' des données intermédiaires stockées dans la cellule de calcul) dans l'opération de quasi-réduction modulo N fournissant la variable de calcul Ai Durant le temps correspondant à ces séries de cycles pendant lequel la cellule de calcul travaille de manière quasiment autonome, l'unité centrale 15 dispose de tout le temps nécessaire pour recharger les différents paramè- tres nécessaires aux calculs qui vont suivre et notamment les adresses dans les registres pointeurs 121, 122 et 123 D'une manière similaire entre deux séries de cycles de calcul de nouveaux opérandes al 1 l, al 2 l, al 3 l -et le cas échéant un opé- rande al 4 l sont rechargés dans les registres 311 à 313 ( 314) à partir d'une adresse initiale chargée par l'unité centrale dans le registre pointeur 211 qui est ensuite décrémenté ou incrémenté pour fournir les valeurs suivantes de ces opérandes à partir de la mémoire de travail 17 Une variante de réalisa- tion non représentée à la figure 4 consiste à ajouter au re- gistre de données 323 recevant la sortie de résultat bi, une pile de trois registres tampons court-cuircuitables au moyen d'un multiplexeur Les 4 octets de poids fort de la variable Bi produits en dernier lieu par la cellule de calcul 18 peu- vent alors, à partir des 3 registres tampons de ladite pile augmentés du registre 323, être transférés directement et suc- cessivement dans les registres 311, 312, 313 et 314 en tant qu'opérandes pour la mise en oeuvre d'une quasi-réduction mo- dulo N qui va suivre De cette manière l'emplacement mémoire représenté par ces 4 octets de données peut être économisé. La figure 5 indique le schéma interne d'une cellule de calcul 18 de la figure 4 Les entrées et sorties de la cel- lule de calcul sont affectées des mêmes signes de référence qu'à la figure 4 Les entrées de données 11 à 14 sont appli- quées à 4 entrées d'un multiplexeur à commutation cyclique 33 dont la sortie est appliquée à une des deux entrées d'un mul- tiplieur 30 de 8 x 8 bits A la deuxième entrée du même multi- plieur est appliqué l'opérande xi à partir de l'entrée 21. La sortie du multiplieur 30 au format de 16 bits est appliquée sur l'une des deux entrées d'un premier additionneur 31 tandis qu'une deuxième entrée au format de 8 bits provient de moyens de recyclage de données qui seront décrits ci-après La sortie au format de 16 bits du premier additionneur 31 est appliquée à l'une des deux entrées d'un deuxième additionneur 32, de 16 + 8 bits, dont la deuxième entrée 35 peut recevoir la valeur de l'opérande ti à partir de l'entrée 22 via un multiplexeur 42 Le deuxième additionneur 32 possède deux sorties: une sortie 37 des 8 bits de poids faibles du résultat susceptible de contenir une donnée de résultat à transmettre sur la sortie 23 et une sortie 38 des 8 bits de poids forts qui sont mémori- sés dans un registre tampon 41 La sortie du registre tampon 41 est appliquée d'une part à la deuxième entrée du multi- plexeur 42 et d'autre part à l'une des deux entrées d'un autre multiplexeur 43 l'autre entrée à 8 bits de cet autre multi- plexeur étant reliée à la sortie 37 des poids faibles de ré- sultat La sortie à 8 bits du multiplexeur 43 et reliée à la deuxième entrée 34 du premier additionneur 31 via une pile de registres tampons 44, 445, 45, l'un des registres de cette pi- le (ici le registre 445) pouvant être évité au moyen d'un mul- tiplexeur 450 dit de court-circuit Les données transitent pas à pas dans cette pile de registres. Au premier pas d'un cycle correspondant à la sélec- tion de l'opérande alll le multiplexeur 42 est positionné pour sélectionner l'entrée d'opérande ti et le multiplexeur 43, positionné pour sélectionner la sortie du registre tampon 41. Ces positionnements sont ceux qui ont été indiqué de manière symbolique sur la figure 5 L'opérande ti est présenté à l'addition dans le deuxième additionneur 32 et le résultat des 8 bits de poids faible en sortie 37 de cet additionneur est mémorisé via la borne de sortie 23 dans le registre 323 (figu- re 4) Pour les autres pas c'est-à-dire les pas différents d'un premier pas de cycle, le positionnement des multiplexeurs 42 et 43 est inversé de sorte que les valeurs de poids forts des résultats en sortie 38 du deuxième additionneur 32 sont recyclées à l'addition sur l'entrée 35 du deuxième addition- neur 32 après un retard correspondant au stationnement de ces valeurs dans le registre tampon 41 Les 8 bits de poids fai- bles à la sortie 37 de résultat du deuxième additionneur 32 sont transférés dans le registre 44 constituant la tête de la pile de registre de stockage o les valeurs sont successive- ment transférées dans le registre qui suit à chaque pas Un retard convenable de 3 pas est donc assuré pour le recyclage de ces valeurs à l'addition dans le premier additonneur 31 sur l'entrée 34 de cet additionneur Par exception, au dernier pas d'un cycle c'est la valeur contenue dans le registre tampon 41 qui est transférée lors du premier pas du cycle suivant dans le registre tampon 44 et procure ainsi pour cette valeur un recyclage après un retard de 4 pas comme il convient, vers l'entrée 34 du premier additionneur 31. Une telle cellule de calcul fournit ainsi un seul résultat à 8 bits en sortie 23 par cycle de 4 pas, exploitant les opérandes al 1 l à al 4 l combinés aux opérandes xi et ti Des résultats intermédiaires sont recyclés au sein même de cette cellule par les moyens de recyclage constitués essen- tiellement par les registres 41, 44, 445 et 45 munis de moyens de commutation de recyclage constitués par les multiplexeurs 42 et 43. Une telle cellule est également capable de fonc- tionner en cycle à 3 pas Dans ce cas une information, sous la forme d'1 bit particulier, chargée par l'unité centrale 15 dans le registre état et commandes 19, commande à la cellule de calcul de ne pas utiliser l'opérande al 4 l de sorte que la commutation cyclique du multiplexeur 33 se borne à exploiter les opérandes al 1 à al 3 l Pour assurer un recyclage convena- ble des données intermédiaires il est alors nécessaire de ré- duire d'1 registre la pile de registres tampons 44, 445, 45 ce qui est opéré en positionnant le multiplexeur 450 de court- circuit dans la position qui permet d'éviter le registre 445. On comprend aisément que le microcontrôleur décrit brièvement à la figure 4 doté d'une cellule de calcul telle que décrite à la figure 5 est capable de mettre en oeuvre le procédé selon l'invention pour un codage par la méthode RSA d'une manière très efficace En procédant de cette manière, on évite un nombre considérable de tests susceptibles de ra- lentir de manière très significative l'opération de trai- tement. L'invention s'étend également à tout dispositif mu- ni d'une unité centrale de microcalculateur commandée par un programme, dispositif dans lequel ce programme met en oeuvre le procédé décrit précédemment. REVENDICATIONS 1 Procédé pour la mise en oeuvre par un microcontrô- leur de la méthode de codage RSA ou une méthode dérivée, qui consiste à effectuer une exponentiation par un nombre e, modu- lo N, d'un message M; N, e et M étant des nombres entiers de grande longueur compris dans un format à N bits, procédé selon lequel le calcul d'exponentiation modulo N est décomposé en une suite de deux opérations successives, la première de ces opérations étant de la forme Bi = ai X + T 2 m expression dans laquelle Bi et X sont des variables de cal- cul qui dépendent de M et de N, dans laquelle ai est un ex- trait, de format restreint à m bits, d'une variable de calcul A dont la valeur découle d'une étape d'opérations précédentes, extrait pris dans l'ordre décroissant de poids de A, au rang i, et T une variable de totalisation utilisée dans le calcul de la variable A, et la deuxième opération consistant à rédui- re la longueur de la variable Bi par soustraction d'un mul- tiple déterminé du module N, et procure une nouvelle valeur Ai à la variable A, caractérisé en ce qu'on effectue la deu- xième opération par une quasi-réduction modulo N obtenue par la relation: Ai = q N'+ R dans laquelle N' est la valeur complémentée à deux de N dans le format à N bits, o q est un quotient entier dans un format à p bits fixé, approché par défaut, de la division Bi/N, avec p>m, et o R est une variable fournie par les N bits de poids faibles de la variable Bi, opération dont le résultat Ai est susceptible de contenir un faible multiple du module N et donc de présenter un dépassement de d bits de poids forts par rapport au format à N bits, en ce qu'on se fixe un nombre donné d'opérations successives et une tolérance d'approxima- tion de q tels que le nombre de bits d du dépassement accumulé lors desdites opérations successives soit au plus égal à p-m, et en ce qu'on effectue une quasi-réduction modulo supplémen- taire à la suite dudit nombre donné d'opérations, qui produit une nouvelle valeur de la variable A strictement dans le for- mat à N bits. 2 Procédé selon la revendication 1, caractérisé en ce que ledit nombre fixé d'opérations successives est atteint lorsque la variable A a été exploitée entièrement à l'aide de ses extraits ai. 3 Procédé selon la revendication 2, dans lequel la valeur du module N est prise dans un intervalle particulier, caractérisé en ce que ledit intervalle particulier est égal à: 2 N 2 (n-m) i 2 N 1 et en ce que la valeur du quotient approché q est fournie par les bits des poids forts de la variable Bi qui dépassent du format à N bits. 4 Procédé selon la revendication 3 appliqué à des va- riables N bits o N est inférieur à 2000, caractérisé en ce que le nombre de bits p du quotient approché q est égal à 32 et le nombre de bits m dudit format réduit de la variable ai est égal à 24. Procédé selon la revendication 2 applicable lorsque la valeur du module N est choisie de manière quelconque parmi les nombres à N bits et pour des variables à N bits o N est inférieur à 2000, caractérisé en ce que l'on choisit un nombre de bits p du quotient approché q égal à 32 et un nombre de bits m dudit format réduit de la variable ai, égal à 24, en ce qu'après avoir effectué la première opération Bi = ai X + T 2 m on détermine la valeur du quotient approché q par une opéra- tion supplémentaire Ei.N* dans laquelle úi représente les bits de poids forts de la variable Bi qui dépassent du format à N bits, et N* repré- sente un nombre binaire limité à ses 56 bits les plus signifi- catifs de l'inverse du module N, opération supplémentaire dont le résultat limité à ses 32 bits les plus significatifs fournit la valeur du quotient approché q, et en ce qu'on ef- fectue ensuite la quasi-réduction modulo N par l'opération Ai = q N' + R déjà citée. 6 Dispositif muni d'une unité centrale de microcalcu- lateur commandée par un programme, caractérisé en ce que ledit programme met en oeuvre le procédé conforme à l'une des reven- dications 1 à 5.