Brevet FR2701323A1 — publié le 19940812

DISPOSITIF POUR EFFECTUER UNE DIVISION. Description: La présente invention concerne un dispositif pour effectuer une division d'un nombre dividende A par un nombre diviseur D formé de "n" mots exprimant une base "b", afin d'obtenir un quotient Q et un reste R. Un tel dispositif trouve d'importantes applications dans les domaines o l'on a affaire à des divisions de grands nombres Il y a cependant un domaine de prédilection pour l'invention: c'est celui des cartes à microcircuit utilisant le procédé de cryptage RSA Ce procédé, décrit dans le brevet des Etats Unis d'Amérique No 4 405 829 de Rivest, Shamir et Adleman en 1978, est un système à clé publique "e" Il repose sur la difficulté de factoriser un grand nombre "N" qui est le produit de deux nombres premiers "p et "q". L'opération de base de ce cryptage est définie de la manière suivante. Le message à coder est mis sous forme d'une chaîne de nombres séparés en blocs M de longueur fixe, inférieurs à N Chaque bloc donne un cryptogramme C à l'aide d'un exposant "e" qui peut être connu du public et qui est un nombre ne divisant ni "p 1 ", ni "q 1 ", en effectuant l'opération suivante. C =Me (mod N) o (mod N) indique que l'opération est effectuée selon un module N. Pour rétablir le message, le destinataire doit connaître un exposant secret "d" et effectuer l'opération M = Cd (mod N) c'est à dire M = Mde (mod N) Une grandeur couramment utilisée pour le nombre d'éléments binaires constituant N est 512 ce qui correspond à environ 155 chiffres décimaux, alors on prend pour "p" et "q" une longueur de l'ordre de 256 éléments binaires Les dispositifs mettant en application ce procédé de cryptage utilisent le Théorème du Reste Chinois qui permet de transformer une exponentielle portant sur 512 éléments binaires en deux exponentielles de 256 éléments relatives à chacun de ces facteurs Les facteurs p", "q" sont à leur tour substitués à "N" et les opérations d'exponentiation sont if t, effectuées selon les modules "p" et "q Dans la demande de brevet Européen N'0 443 679, on décrit la manière dont sont effectuées ces exponentiations. Ces enseignements ont été appliqués au micro-contrôleur 83 C 852 fabriqué par Philips Les exponentiations sont effectuées avec des modules qui sont des nombres normalisés Cette normalisation consiste à réserver trois octets qui sont utilisés dans la suite des calculs Cette demande propose néanmoins des mesures lorsque les nombres ne sont pas normalisés Ceci implique pratiquement qu'il faut prévoir deux sortes de processus de calcul une première pour les nombres normalisés et une autre pour les nombres non normalisés D'une part, cet autre processus est beaucoup moins adapté à la structure dudit micro- contrôleur et amène à un temps de calcul pouvant être long et d'autre part, la présence de deux processus encombre la mémoire de programme. L'invention trouve là une application importante en rendant possible la normalisation de tous les nombres N proposés Ceux-ci sont multipliés par un coefficient de normalisation puis une division est effectuée par ce même coefficient à la fin des processus d'exponentiation. La présente invention propose un dispositif du genre mentionné dans le préambule particulièrement bien adapté au micro-contrôleur du type précité qui permet donc d'utiliser des grands nombres quelconques comme module tout en procurant une vitesse de traitement satisfaisante. Pour cela, le dispositif du genre mentionné dans le préambule est remarquable en ce qu'il comporte des moyens d'estimation de Q pour effectuer l'opération: A + Q'dbk = Q bn+k + S bk + R' o dbk = bn+k D avec k k 1 afin que la valeur S, faisant office de séparateur, devienne nulle pour une valeur de Q' de sorte que Q" prend la valeur de Q et R', celle de R. La description suivante, accompagnée des dessins annexés, le tout donné à titre d'exemple non limitatif, fera bien comprendre comment l'invention peut être réalisée. La figure 1 montre la structure d'un dispositif dans lequel l'invention est mise en application. La figure 2 montre très schématiquement le fonctionnement de l'invention. La figure 3 montre l'organigramme de fonctionnement du dispositif selon un mode de réalisation préféré de l'invention. Le dispositif de la figure 1 est constitué à partir d'un microprocesseur 1, d'une mémoire vive 2 munie d'une entrée pour code d'adresse AD et d'un accès pour l'entrée et la sortie des données DT, d'une mémoire morte 3 contenant notamment les instructions de fonctionnement pour la mise en application de l'invention et également d'une mémoire EEPROM 5 pour contenir différentes données, notamment dans le cadre de l'exemple décrit une valeur de normalisation du diviseur X et la valeur dbk Sur cette figure, ces différents éléments sont reliés par une ligne BUS qui fonctionne en mode multiplexé, c'est à dire qu'elle transporte en certains moments des données et en d'autres des codes d'adresses Le dispositif de la figure 1 comporte aussi une unité de calcul 8 pour effectuer des multiplications avec ou sans cumul Cette unité 8 comporte un ensemble de quatre entrées a O, ai, a 2 et a 3 pour recevoir un opérande de quatre octets contenus dans des registres 10, 11, 12 et 13, une entrée xi reliée à des registres 14 et 15 pour un multiplicande à plusieurs octets, une entrée Ai, reliée à des registres 17 et 18 pour plusieurs octets à additionner et une sortie RO pour fournir le résultat Différents opérandes proviennent de la mémoire vive 2 Selon l'entrée à laquelle ces opérandes sont appliqués, on fait appel à des registres pointeurs 21, 22 et 23 Aux registres 21 et 23 sont associés des organes de décrémentation 25 et 26 Le registre 21 est relatif à l'opérande à appliquer à l'entrée Ai, le registre 22, aux opérandes à appliquer aux entrées ai, a 2, a 3 et a 1 et le registre 23, à l'opérande à appliquer à l'entrée "xi" Un autre registre pointeur 24 avec son organe de décrémentation associé 28 est relatif à l'emplacement dans la mémoire 2 pour ranger le résultat fourni à la sortie RO Des registres 40, 41, 42 et 43 montés en registre de pipe- line RPL, sont prévus pour recevoir aussi des octets disponibles à la sortie RO. D'une manière similaire à la mémoire 2, des registres pointeurs 51 et 52 associés avec des organes de décrémentation et 56 sont rattachés à la mémoire 5 Un registre supplémentaire 58 est aussi utilisé pour l'adressage. L'unité de calcul 8 est commandée par l'intermédiaire de différents registres 60, 62, 64, 66 et 68. Les registres 71, 73, 75, 77 sont directement gérés par l'unité de calcul 8 Le registre 60 est un registre dans lequel sont emmagasinées des commandes pour l'unité 8 et des informations de statuts concernant les opérations effectuées par cette unité Le registre 62 est utilisé pour la commande de l'unité de calcul 8 Le registre 64 sert à compter le nombre d'octets du résultat fourni à la sortie RO Le registre 66 commande le début de l'inscription en mémoire 2 des informations disponibles à la sortie RO et offre la possibilité d'inhiber l'écriture dans la mémoire d'un certain nombre d'octets tandis que le registre 68 est prévu pour fixer les limites des opérandes appliqués aux entrées Ai et xi c'est-à-dire leur nombre d'octets Tout détail complémentaire peut être trouvé dans la notice du micro- contrôleur 83 C 852 précité. Au moyen de ce dispositif, on propose d'effectuer une division d'un dividende A formé d'un grand nombre "m" d'octets par un diviseur D avec de préférence N m Le résultat que l'on veut obtenir est le quotient Q et le reste R. Selon l'invention, on a prévu des moyens d'estimation de Q qui effectuent l'opération A + Q'dbk =Q" bn+k +S bk +R ( 1) o dbk = bn+k _ D avec k > 1 afin que la valeur S, faisant office de séparateur, devienne nulle pour une valeur de Q' de sorte que Q" prend la valeur de Q et R', celle de R Selon un autre aspect de l'invention, on a prévu des emplacements de mémoire déterminés, suffisants pour contenir le dividende A dans lesquels les différentes opérations impliquées par la relation ( 1) vont être effectuées sans trop nécessiter d'emplacements supplémentaires Ces opérations vont s'effectuer en multi précision c'est-à-dire en opérant successivement sur des groupes de mots du dividende formé de "m" mots ou, dans le cadre de l'exemple décrit de "m" octets avec des multiples b J de la quantité dbk On commence par les plus fort poids ce qui revient à multiplier dbk par b J avec J = m n, donc à le décaler vers les plus forts poids Le résultat de l'opération ( 1) sera une valeur Q" représentant les fort poids du quotient Cette dernière quantité devient la valeur q 6 lorsqu'on voit la valeur nulle d'un séparateur S portant sur "k" octets (voir ligne "a" de la figure 2) En pratique, le séparateur est formé d'un seul octet Puis on recommence ce même processus en décalant la valeur de dbk d'une valeur Il N dépendant de la capacité de l'organe de multiplication faisant partie de l'organe de calcul 8 Cette valeur peut prendre la valeur x + y si la multiplication se fait sur des opérandes comprenant "x" et "y" octets. Différentes composantes du quotient qy, q, et qa apparaissent successivement, ceci est représenté respectivement aux lignes "b", "c" et "d" de la figure 1. L'invention repose sur les considérations suivantes. Soit en reprenant la formule de la division: A = Q D + R; O o A est le dividende codé sur "m" mots d'une base "b", o D est le diviseur codé sur "n" mots de la base "b". Soit k entier 2 1: Le complément à D dans Z n+k est désigné par dbk. B On a alors: A + Q dbk = Q bn+k + r Si on considère le format global de l'accumulateur dans lequel se trouve le résultat A + Q dbk, on voit apparaitre un séparateur (S): 1 Q I 111 1 | r l quotient exact k mots nuls Reste (S) Si on commet une erreur d'estimation (par défaut) du quotient exact q: = Q ô: quotient estimé. Alors: A +Q dbk =Q bn+k 6 dbk +R Le séparateur n'est pas nul Pour déterminer ô, l'erreur d'estimation commise, il suffit d'annuler le séparateur par additions successives de dbk à l'accumulateur Ce processus peut toutefois être amélioré par l'observation suivante: Si v O est la valeur contenue dans le séparateur, on alors: A + 4 dbk =a Obn+k +v O bn + r O En observant que: dbk = (bk _ l)b + do, o do représente le complément de D dans un format à n mots; on a alors par addition de vo dbk A + (e +v O) dbk = (a O + vo)bnk vo do + ro En posant vo do + r O = vib n+ r on constate que: a) v 1 b) l'estimation du quotient est plus précise. En outre, selon le mode de réalisation préféré de l'invention, un test de signe a été prévu Il consiste à ajouter la valeur dbk au niveau du séparateur pour qu'il ne puisse pas avoir propagation de la retenue o autrement dit que l'on s'assure que la composante du quotient n'a pas été trop sous-estimée. L'organigramme de la figure 3 est représenté selon une norme telle que chaque action est représentée à l'intérieur d'un rectangle Les cases en forme de pentagone représentent un test, si le test est positif on passq au rectangle inférieur, sinon on passe à la case située à droite. Les différentes cases indiquent des actions explicitées ci- dessous. Il est supposé que le dividende formé de M octets est situé dans un emplacement de la mémoire 2 référencé dans la suite de l'exposé par Accu {M,1} Cette notation signifie que les octets placés dans les accolades et séparés par une virgule sont à considérer Ici, il faut donc considérer l'ensemble des octets depuis M, représentant les plus forts poids jusqu'à l'octet 1, de faible poids Les M octets Accu {M,1} sont indexés par les registres pointeurs 21 et 24. Il est supposé ensuite que le diviseur, ou mieux la valeur dbk, est contenu dans la mémoire EEPROM; cette valeur est formée de 4 + K octets (K étant le nombre d'octets du séparateur); elle est pointée par le registre 52 Il est supposé enfin que le coefficient de normalisation X du diviseur D est aussi contenu dans la mémoire EEPROM mais il est pointé, lui, par 51 Le coefficient X est défini par = MAX { x E N; x D bnk o N désigne l'ensemble des entiers positifs. K: désigne l'action qui consiste à mettre dans un emplacement de la mémoire 2 faisant office de compteur, une valeur I représentant le nombre de pas de l'algorithme Pour déterminer ce nombre I on découpe le diviseur en groupe de quatre ce qui correspond à la longueur des multiplicandes convenant à l'opération de multiplication que peut effectuer l'unité de calcul 8. K 2:c'est l'action qui met à zéro les octets du groupe de 4 restant du côté du plus fort poids Les registres 23, 21 et 24 pointent vers l'octet Accu { 4 I-7}. K 3: on y teste si tous les pas ont été effectués. K 10: désigne en fait les opérations de la division. Kil: on met, tout d'abord, les quatre octets du coefficient de normalisation y, dans les 4 registres RPL; ces octets transitent dans l'unité 10 au moyen d'une instruction qui commande une multiplication avec un opérande de cumul qui est k et qui fixe le multiplicateur à une valeur nulle à l'aide du registre 68. K 13 on multiplie huit des octets (de plus fort poids du dividende lorsqu'on commence au premier pas) contenus dans A{I,4 I-7} Le résultat formé en principe de 12 octets noté ici par: UC { 12,1} transitera via le registre RPL. K 15 de ces 12 octets, on n'en retient que 4 c'est-à-dire UC { 11,8} L'octet de plus fort poids UC { 12} est écarté pour avoir un cadrage correct UC { 11,8} est ensuite transféré dans le registre RPL On notera que les opérations indiquées dans ces cases Kll et K 13 ne nécessitent pas la présence de mémoire intermédiaire hors de l'unité de calcul Ces octets UC { 11,8} constituent une valeur du quotient approché e K 17 le quotient approché étant disponible dans le registre RPL, on l'utilise pour réduire l'accumulateur par addition de C dbk On notera que le quotient approché apparaîtra dans la mémoire RAM au-delà des K octets de séparation. K 19 on prélève le séparateur dans Accu pour l'appliquer aux entrées RPL On notera les 0,0,0 émis avant le séparateur. K 21 on teste par rapport à zéro la valeur de ce séparateur. Tant que ce séparateur n'est pas nul on effectue les opérations de la case K 23 comportant elle-même les cases K 25 et K 27. K 25: on multiplie le séparateur par dbk et on l'ajoute au contenu de Accu. K 27: on prélève à nouveau le séparateur pour l'appliquer à RPL. Cela est effectué tant que le séparateur n'est pas nul. K 29: on commence le test du signe en ajoutant dbk au contenu de Accu, le résultat est mis dans des emplacements fictifs de travail UC { 6,1}, seul en fait sera considéré l'emplacement UC { 6} pour la case suivante. K 31: l'octet de plus fort contenant la valeur de la retenue est remis dans le registre RPL à des fins de test. K 33: c'est là que l'on effectue ce test, tant que ce contenu est différent de 0, on effectue l'opération indiquée à la case K 35. K 35: on additionne au contenu de Accu la valeur de dbk K 37: on décrémente la valeur de I afin de procéder s'il y a lieu à une exécution supplémentaire de la case K 10. On donne en annexe un exemple de division effectuée dans le système décimal Soit 99145360 le dividende et 80 le diviseur La multiplication est supposée être faite sur 2 X 2 chiffres, de ce fait on admet implicitement que la capacité du registre RPL est aussi de deux chiffres et le séparateur sur un seul Le coefficient de normalisation du diviseur est tel X D = 960 donc X = 12 et dbk = 920. ANNEXE 1 EXEMPLE EN BASE 10 (DECIMAL) D = 80 dbk = 9 2 O X = 12 O = 0099 x 12 = 001 188 qo-dbk = 920 x 01 = 920 > Test de signe: 0 O 9 9:1 4 5 3 6 O 92O:::: :::: :::: :::: :::: 92::::: 1 O 1 9 l O 1 séparateur l 9 3 9 Dûa 1 9 ql = 1914 x 12 = 022 968 qldbk = 920 x 22 = 20240 1 x 9 2 O = 9 2 O lx 920 = 920 2 O 2 4 O t 2 2 l 5 4 - 1 22154:: 920:: Test de signe: séparateur 1 2 3 O 7 4 jj l 9 94 IÄ 3 O7 4 :::: ::.:: e.e. 1:::: 14::: 1 1 3 ANNEXE 1 (suite) D = 80 0 O 9 9:1 4 5 3 6 O :e: e e: e ee :e: ee: e ee dbk = 9 2 O X = 12 Page précédente q 2 = 7453 x 12 = 089 436 q 2 dbk = 920 x 89 = 81880 t397453 8 1 8 80 1 2 3 8 $ 31 x 9202760 3 x 9 2 0 = 2 7 6 0 Test de signe: 1 2 3 9 M O 13 Test de signe dbk -> : 013 1 2 3 9 O 9 33 9333:: 2760:: 2093:: 9 3 3 ' ' __:: 2 7 6 0 * 2 0 9 3 * ' 920:: 3013:: 3 W 13:: "J, q 3 = 1360 x 12 = 016 320 2 93- 1 360 d 3 dbk = 920 x 16 = 14720 1 2 3 9 3 1 6 O 8 O 1 4 7 2 O :. ANNEXE 1 (suite) D = 80 0 O 9 9:1 4 5 3 6 O :::: dbk = 9 2 O X = 12 page précédente Test de signe: 1 2 3 9 3 1 r O O O o dbk > Test de signe: 1 2 3 9 3 1 7 0 0 0 1239317000 quotient séparateur reste quotient sêparateur reste EU 9 20 6 O 8 O REVENDICATIONS. 1 Dispositif pour effectuer une division d'un nombre dividende A par un nombre diviseur D formé de "n" mots exprimant une base "b", afin d'obtenir un quotient Q, et un reste R, caractérisé en ce qu'il comporte des moyens d'estimation de Q pour effectuer l'opération: A + Q'dbk = QI 1 bn+k + S bk + R' o dbk = bn+k D avec k 2 1 afin que la valeur S, faisant office de séparateur, devienne nulle pour une valeur de Q' de sorte que Q" prend la valeur de -Q et R', celle de R. 2 Dispositif pour effectuer une division, selon la revendication 1, du nombre dividende A formé de "m" mots exprimant une base "b", par le diviseur D, comportant une mémoire vive, un organe de multiplication muni d'une première entrée pour "x" mots d'un multiplicande, d'une deuxième entrée pour "y" mots d'un multiplicateur, caractérisé en ce que ladite mémoire vive comporte des emplacements déterminés pour contenir au moins les "m" mots du dividende, en ce qu'il est prévu des moyens de cumul pour ajouter à ces emplacements un multiple d'une quantité dbk b J élaborée par ledit organe de multiplication, des moyens de test pour fournir une indication de la valeur nulle d'un séparateur S défini par "k" et par "J" dans ledit emplacement et pour activer des moyens de cumuls jusqu'à ce que les moyens de test fournissent ladite indication et des moyens de décrémentation pour décrémenter la valeur J de x + y à chaque indication et en ce qu'à la fin de la décrémentation le reste de la division est contenu dans les "n" derniers emplacements et le quotient avant le "n+k" ième emplacement à la fin de la décréméntation de "J". 3 Dispositif pour effectuer une division selon la revendication 2, caractérisé en ce que les moyens de test effectuent une phase de vérification consistant à rajouter une quantité dbk b J à la quantité contenue dans des parties dudit emplacement définies par J, à examiner si ce rajout fournit une retenue et à rajouter effectivement cette quantité dbk b 3 si une retenue a été fournie.