Brevet FR2613861A1 — publié le 19881014

-- 1 -- Procéde et contrôleur pour cryptographier un message selon un algorithme à cl1 publique La présente invention concerne de manière générale la confidentialité et l'authentification de messages pour des systèmes électroniques de messagerie privée, de paiement ou de transferts de fonds. Plus particulièrement, l'invention concerne de tels systèmes électroniques traitant des messages a l'aide d'algorithmes cryptographiques à clé publique de type RSA (RIVEST, SHAMIR et ADLEMAN). Dans l'article "on digital signatures and public key cryptosystens", Communication of the ACM, Vol. 21, Février 1978, No. 2, p. 120-!21, Rivest, Shamir et Adleman divulguent un algorithme pour calculer une fonction cryptographique clé publique F telle que F(X) = Xs modulo N, o X et F(X) sont des messages représentés sous forme de mots numériques ayant des valeurs entières élevées de l'ordre 512 51? de 2 et N et S sont des entiers également de l'ordre de 2. Le calcul de l'exponentiation modulo N se reduit à une suite de calculs de type A.B modulo N, selon un processus de calcul itgratif. Un procédé classique pour calculer la quantité A.B modulo N consiste _ calculer le produit A.B puis à le diviser par N afin d'obtenir un reste recherché. Un tel procédé implique la nécessité de disposer de dispositifs de calcul pouvant traiter en parallèle un nombre de bit très élevé, de l'ordre de 1 024 dans le cas o l'on traite des nombres voisins de 251. Un processeur de calcul réalisable en application de ce procédé a certes de bonnes performances mais présente un coût de revient éleve et un encombrement trop important pour certaines applications. Un processeur de calcul cryptographique réalisé selon ce procédé se présente généralement sous forme d'un bottier de circuit intégré à adjoindre dans une carte électronique à un microprocesseur à 8 bits ou 16 bits afin de conférer à ce dernier des capacités de calcul cryptographique. Il est par exemple impossible d'encarter même sous forme de puce, ce processeur de calcul dans une carte dite "à mémoire". La présente invention vise à fournir un procéda pour calculer la fonction A.B modulo N ainsi qu'un contrôleur de faible encombrement et de faible coût mettant en oeuvre le procédg selon l'invention pour le calcul de la fonction cryptographique F, un tel contrôleur etant -2- réalisable sous forme d'une unique puce intégrant un microprocesseur apte à gérer un système, et une cellule de calcul spécialisée. A cette fin, le procédé selon l'invention pour crypter ou décrypter un message représenté sous la forme d'un mot numérique ayant une valeur entière élevée par le calcul d'une exponentiation modulo N dudit message, N étant un entier de valeur élevée choisi dans un intervalle de valeur déterminée, l'exponentiation modulo N étant calculée en effectuant une suite d'opérations A.B modulo N, o A et B sont des variables de calcul ayant des valeurs entières dépendantes de la valeur numérique du message et représentées par des mots numériques de nb bits, nb étant un entier prédétermine, est caractérisé en ce que pour effectuer chacune des opérations A.B modulo N, la variable A est fractionnée en J + I mots de tb bits, aO,....ai,....ai, o tb est un entier prédéterminé et J + 1 un entier égal ou strictement supérieur nb/tb, en ce que successivement chacun des mots ai, o i est un entier compris entre O et J, est multiplié par la variable B et le produit de la multiplication est ajouté 2 un mot numérique de somme T de valeur égale à la somme cummulée des produits antérieurs réduite modulo N, et en ce que la réduction modulo N du mot de somme T est réalisée en lui soustrayant une quantité di.N, o diest un mot numérique constitué des tb + 1 bits de poids fort du mot de somme T, 2 chaque fois qu'il atteint une valeur supérieure ou égale à ladite quantité d i.N. Un contrôleur selon l'invention pour la mise en oeuvre du procédé selon l'invention est caractérisé en ce qu'il comprend des moyens pour mémoriser un programme de calcul de l'exponentiation modulo N d'un mot numérique de message, des moyens pour gérer l'exécution du calcul selon le programme mémorisé et commander un système électronique incluant ledit contrôleur, et des moyens pour calculer à la demande des moyens pour gérer et pour commander des opération du type T + y.N, o y est un mot numérique ai ou di. De préférence, les moyens pour calculer comprennent des moyens pour régir des échanges de données et d'adresses avec les moyens pour gérer et commander et pour séquencer des opérations internes réalisées dans les moyens pour calculer, chaque opération étant relative 8 une partie de l'un des mots N et T fractionné, des moyens pour multiplier le mot numérique y au mot N ou à une partie du mot N fractionné, des premiers moyens pour additionner un mot de retenue à un produit fourni par les - 3 - moyens pour multiplier, des seconds moyens pour additionner le mot T ou une partie du mot T fractionné à un résultat délivré par les moyens pour additionner, et des moyens interconnectés aux premiers et seconds moyens pour additionner pour réaliser une inversion en complément à deux du résultat délivré par les premiers moyens pour additionner dans le cas o l'opération à réaliser est du type T - y.N. Avec les technologies actuelles, telle que la technologie CMOS 1,5 micron autorisant une fréquence d'horloge de l'ordre de 10 MHz, un contrôleur selon l'invention peut se présenter sous la forme d'une puce de 20 mm2 de surface et présente un temps en signature de message voisin de 1 s. D'autres avantages et caractéristiques de l'invention apparaîtront plus clairement à la lecture de la description suivante du procède et de plusieurs réalisations préférées d'un contrôleur selon l'invention en référence aux dessins annexés correspondants dans lesquels: - la Fig. 1 montre un organigramme de calcul de la fonction A.B modulo N; - la Fig. 2 est un bloc-diagramme d'un contrôleur selon l'invention; et - la Fig. 3 est un bloc-diagramme d'une cellule de calcul incluse dans un contrôleur selon l'invention. Le procédé selon l'invention est basé sur un calcul par tranche d'un nombre de bits tb = 16 déterminé alternant des multiplications et des réductions modulo N. De plus, le nombre N est choisi de façon à simplifier la réduction- modulo N afin de ne pas avoir à effectuer de vraies divisions mais des multiplications, soustractions et additions. Pour un calcul de A.B modulo N avec des nombres A et B ayant chacun un nombre de bits nb = 512, le nombre A est, par exemple, divisé en J + 1 = nb/tb = 32 tranches de tb = 16 bits. Le produit A.B s'exprime alors par la somme suivante: O 1ltb i.tb Jt A.B = a B2 +a B.2 +...+aB.2 +...+ a. B2Jtb 0..1., * aOB2+ al.B.21'tb+...+ amB itb.t o i est un entier compris entre 0 et J, et o a à aj sont des tranches o successives de tb = 16 bits du nombre A, à partir des bits de poids faible, telles que: 351.tb i'tb J.tb A=a 2 = a. 2 +..+ a.2 +.. + ai.*2 L'expression A.B modulo N se décompose de la manière suivante: A.B modulo N = aoB.20'tb modulo N + a1.B.2 tb modulo N + .+ - 4- ai.B.2itb modulo N +...+ a B.2 Jtb modulo N. i..DTD: nb nb nb (tb + 1) - Le nombre N est choisi dans l'intervalle: 2nb, 2nb+ 2nb (tb 1,r512 512 495 soit pour nb = 512 et tb =!6, 2, 2 + 2 '. Le choix de N est imposé dans cet intervalle afin de ramener les réductions modulo N de simples soustractions. A la Fig. 1 est montré un organigramme de calcul de la fonction A.B modulo N selon le procédé de l'invention. Une variable de calcul T de nb + tb + I = 529 bits en complément deux est utilisée pour le calcul. A la variable T est attribuée une valeur initiale égale à 0. La variable T cumule les produits partiels ai.B au fur et i mesure du calcul. Une boucle de calcul est réalisée J + 1 fois avant que la valeur de la variable T soit égale à A.B modulo N. Lors des J + 1 boucles de calcul sont calculés respectivement les J + 1 produits aj.B " a.B. A chaque passage dans une boucle de calcul, une nouvelle valeur de T est calculée par addition du produit ai.B correspondant à la valeur précédente de la variable T multipliée par tb 16 2 = 2. A une autre variable de calcul di est attribuée la valeur des tb + 1 = 17 bits de poids fort, (tb + 1) MSB, de la valeur calculge de la variable T. Le nombre N est multiplié par la variable d afin de i calculer un produit d. N correspondant la valeur de la variable T. Tout au long du calcul, à chaque fois que la valeur de la variable T excède le produit di.N correspondant, la variable T est réduite modulo N par soustraction du produit di.N. Cette simplicité de la réduction Z5i modulo N de la variable T résulte du choix de N dans l'intervalle [ 2nb nb+ 2nb - (tb + 1). E 2,2 +2 En effet, de manière générale, pour qu'une différence T - di.N soit égale à T modulo N, il faut que les conditions T - di.N > 0 et i' = T - di.N n 2b, 2ib+ 2n b - (tb + 1)- E,2 + 2 (b+) Lorsque la différence T - di.N est de signe négatif, la valeur de T n'est pas réductible modulo N et le produit di.N est ajouté la différence T - di.N pour retrouver la valeur de la variable T. La mise er. oeuvre du procédé selon l'invention implique de savoir faire des opérations du type CAL(T, y, N) = T + y.N, o y est le mot d. ou ai, les multiplications de la variable T par 2tb pouvant être 2613 8 6 1 -5 réalisées simplement par des opérations de décalage effectuées dans une unité centrale d'un contrôleur selon l'invention gérant un algorithme de calcul global de la fonction F. Il est intéressant, essentiellement pour des raisons de rapidité, de faire exécuter les opérations CAL(T, y, N) par une cellule de calcul spécialisée adjointe à l'unité centrale du contrôleur. En référence à la Fig.2, le contrôleur 1 selon l'invention comprend une unité centrale 2, une mémoire de programme 3, une mémoire de travail 4 de type RAM, et une cellule de calcul 5. L'unité centrale 2 est un microprocesseur connu, par exemple è 8 bits ou 16 bits. L'unité I est relise par des bus 20, 21 et 22 aux mémoires 3 et 4 la cellule de calcul 5. Les bus 20, 21 et 22 sont respectivement des bus de donnée, d'adresse et de commande. Les bus 20, 21 et 22 sont par ailleurs, connectés directement ou à travers des ports de communication, i différents éléments d'un système que gère le contrôleur. La mémoire de programme 3 est composée de circuits de mémoire de type ROM et EPROM (ou E2PROM). La mémoire 2 mémorise de manière classique un programme ou une partie d'un programme afin de commander le fonctionnement du système dont fait partie le contrôleur 1. Dans la mémoire 2 est également mémorisé un sous-programme et des paramètres relatifs au calcul de la fonction cryptographique F par l'unité centrale 2 et la cellule de calcul 5. La cellule de calcul 5 est utilisée par l'unité centrale 2 pour calculer les opérations CAL(T, y, N). Une cellule de calcul 5 pour un calcul octet par octet des opérations CAL(T, y, N) est représentée à la Fig.3. La cellule 5 comprend un séquenceur 50, un circuit de lecture 51 et un circuit d'écriture 52 tous deux connectés au bus de donnée 20, des registres-mémoires 53y, 53n, 53t et 53r, un multiplieur 54, un premier additionneur 55, un circuit d'inversion logique 56, un second additionneur 57, et une mémoire de retenue 58. Le séquenceur 50 gère l'ensemble de la cellule 5; il délivre aux différents circuits composant la cellule 5 des signaux de commande de séquencement ainsi que des données nécessaires aux déroulement des opérations de calcul. Le séquenceur 50 est connecté au bus de donnée 20, 26138 6 1 -6- d'adresse 21, et de commande 22 respectivement à des entrées parallèles 501, 502 et 503. Préalablement au début d'une opération CAL(T, y, N) l'unité centrale 2 écrit dans la mémoire 4, sous forme d'octets, à des adresses consécutives, la variable T et le nombre N. La variable T et le nombre N sont constituas d'octets to à tp et no à nQ mémorisés dans la mémoire 4 respectivement è des adresses consécutives atO à atp et anO è anQ, o P est un entier positif variable inférieur à 66 et Q est un entier égal 4 63 pour T et N représentés par nb + tb + 1 = 529 bits maximum et nb = 512 bits, respectivement. Les octets tO et n sont les octets de poids faible de T et de N respectivement; les octets tp et nQ sont les octets de poids fort de T et N respectivement. Lorsqu'une opération CAL(T, y, N) est commandée par l'unité centrale 2, via le bus de commande 22, le séquenceur 50 reçoit de l'unité 2, aux entrées de donnée 501, la valeur de la variable y, un bit SIG indiquant le signe + ou - de l'opgration CAL à effectuer, le nombre P + 1 d'octets composant la variable T, ainsi que les deux adresses at0 et an0 respectivement du premier octet de poids faible tO0 de la variable T et du premier octet de poids faible nO du nombre N. La variable y, représentée sur tb + 1 = 17 bits, est chargée par le séquenceur 50 dans le registre-mémoire 53y. Le registre-mémoire 53y est un registre parallèle de tb + 1 = 17 bits. Les adresses at0 et an0 sont chargées dans des compteurs d'adressage du séquenceur 50. Le nombre d'octets P + 1 de la variable T est chargé dans un compteur de boucle. Le séquenceur 50 adresse successivement les octets t et nO en délivrant dans le bus d'adresse 21 les adresses at0 et anO. Les octets tO et no sont transmis par la mémoire 4 dans le bus de donnée 20 è la réception des adresses at0 et an0 respectivement, et de signaux de commande fournis via le bus 22. Le séquenceur 50 a accès à la mémoire 4 en lecture et en écriture selon le mode d'accès connu DMA (direct memory access). Les adresses atO et anO sont incrémentées dans les compteurs d'adressage du séquenceur 50 à chaque fois qu'il convient de charger dans la cellule 5 deux nouveaux octets t et n, o p est un entier p p positif au maximum égal O P, afin de poursuivre octet par octet le calcul de l'opération CAL(T, y, N) en cours. Les octets t, n sont recus dans la cellule 5 des entrées p p parallèles 511 du circuit de lecture 51. Un octet t est chargé par le P -7- circuit 51 dans le registre-mémoire 53t; un octet n est chargé par le P circuit 51 dans le registre-mémoire 53n. Les registres-mémoires 53t et 53n sont des registres parallèles de 8 bits; ils mémorisent les octets t et n pendant la durée nécessaire aux opérations de calcul. P P Le multiplieur 54 est un multiplieur de type connu 8 +(nb + 1) = 25 bits; il reçoit respectivement à des première et seconde entrées parallèles 540 et 541 la variable y à nb + 1 = 17 bits et l'octet n contenus dans les registres-mémoires 53y et 53n. Le P produit y.n est fourni par le multiplieur 54, via des sorties P parallèles 542, à des premières entrées parallèles 550 de l'additionneur 55. L'additionneur 55 est un additionneur de type connu à 25 bits. L'additionneur 55 a pour fonction d'ajouter au produit y.n un mot de p retenue r de 17 bits mémorisé lors d'opérations de calcul relatives aux P octets n 1 et t 1 traités au cours du cycle précédent. La retenue r est mémorisée dans le registre-mémoire 53r qui la fournit à des secondes entrées parallèles 551 de l'additionneur 55. A des sorties parallèles 552, l'additionneur 55 délivre la somme r + y.n représentée sur 25 bits. Les 17 bits de poids forts de la somme r + y.n sont charges dans P p le registre-mémoire 53r et constituent le mot de retenue r + 1 qui sera ajout au produit servaty. ajouté au produit suivant y.n + 1' Le mot de retenue r0 à ajouter à un premier produit y.n0 est initialisé à 0 par le séquenceur 5, lors d'une phase d'initialisation. Les 8 bits restants de poids faible de la somme r + y.n représentent un résultat RE de l'opération à ajouter ou p P P soustraire à l'octet t. p Lorsque la cellule 5 réalise une opération CAL(T,y,N) = T - y.N, le résultat RE de la somme r + y.n est à inverser en complément à deux avant d'être ajouté à l'octet t. Le séquenceur 50 active dans ce cas un P circuit d'inversion logique 56 en lui fournissant lors de la phase d'initialisation le bit indicateur de signe SIG à un état déterminé. Le résultat RE est fourni à travers le circuit d'inversion 56, actif ou P inactif selon le signe de l'opération CAL en cours, à des premières entrées parallèles 570 d'un additionneur 57. L'additionneur 57 reçoit des secondes entrées parallèles 571 l'octet t mémorisé dans le P registremémoire 53t. Un bit de retenue c de l'opération précédente tp1 + RE est dlivré par une mémoire 58 une entre de retenue t + - RE est délivré par une mémoire 58 à une entrée de retenue tp-1 p-i1 -8- 572 de l'additionneur 57. Lors de la phase d'initialisation, le bit de retenue cO dans la mémoire 58 est forcé par le bit SIG c l'état "1" ou "0" selon qu'une opération CAL(T, y, N) = T - y.N ou CAL(T, y, N) = T + y.N est à effectuer. L'additionneur 57 délivre à des sorties parallèles 573 le résultat de la somme t + RE + c et à une sortie de retenue 574 le bit de retenu c + 1 pour le calcul suivant. Le bit de retenue cp + 1 est mémorisé dans la mémoire 58. Le résultat délivré par l'additionneur 57 est fournit via le circuit d'écriture 52 dans le bus de donnée 20 lorsque le séquenceur 50 commande son écriture dans la mémoire 4 à l'adresse at + 1. Le séquenceur 50 incrémente ensuite les compteurs d'adressage pour obtenir les adresses atp + 1 et anp + 1 des p+l octets suivants è traiter et décremente le compteur de boucle contenant à l'origine le nombre P + 1 d'octets composant la variable T. Lorsque le contenu du compteur de boucle atteint séquenceur 50 en informe l'unité centrale 2 via le bus de commande 22. L'unité centrale prend alors le contrôle des bus et lit aux adresses at0 à at le résultat de l'opération CAL(T, y, N) qu'elle a sous-traité par la cellule de calcul 5. l a cellule de calcul 5. -9- REVENDICATIONS 1 - Procédé pour crypter ou décrypter un message représenté sous la forme d'un mot numérique (X) ayant une valeur entière élevée (25]2 par le calcul d'une exponentiation modulo N dudit message (F(X)), N étant un entier de valeur élevée choisi dans un intervalle de valeur déterminée, l'exponentiation modulo N étant calculée en effectuant une suite d'opérations A.B modulo N, o A et B sont des variables de calcul ayant des valeurs entières dépendantes de la valeur numérique du message et représentées par des mots numériques de nb bits, nb étant un entier prédéterminé, caractérise en ce que pour effectuer chacune des opérations A.B modulo N, la variable A est fractionnée en J + 1 mots de tb bits, aO0. .ai,....aj, o tb est un entier prédéterminé et J + 1 un entier égal ou immédiatement supérieur à nb/tb, en ce que successivement chacun des mots ai, o i est un entier compris entre O et J, est multiplie par la variable B et le produit de la multiplication est ajouté 2 - Procédé conforme à la revendication 1, caractérisé en ce que l'entier N a une valeur numérique comprise dans l'intervalle de valeur r 2nb 2nb+ 2nb-(tb + 1), 3 - Contrôleur pour la mise en oeuvre du procédé conforme la revendication i ou 2, caractérisé en ce qu'il comprend: des moyens (3) pour mémoriser un programme de calcul de l'exponentiation modulo N (F(X)) d'un mot numérique de message (X), des moyens (2,3,4) pour gérer l'exécution du calcul selon le programme mémorisé et commander un système électronique incluant ledit contrôleur (l),et des moyens (5) pour calculer à la demande des moyens pour gérer et pour commander (2,3,4) des opérations du type T + y.N, o y est un mot numérique ai ou d.. 2613 8 6 1 - 10 - 4 - Contrôleur conforme à la revendication 3, caractérisé en ce que les moyens pour gérer et pour commander comprennent un microprocesseur 8 bits ou 16 bits. - Contr8leur conforme à la revendication 3 ou 4, caractérise en ce que les moyens pour calculer (5) comprennent: des moyens (50, 51, 52) pour régir des échanges de données et d'adresses avec les moyens pour gérer et commander (2, 3, 4) et pour séquencer des opérations internes réalisées dans les moyens pour calculer (5), chaque opération étant relative à une partie de l'un des mots N et T fractionné, des moyens (54) pour multiplier le mot numérique y au mot N ou ? une partie (np) du mot N fractionné (n0 a nQ), des premiers moyens (55, 53r) pour additionner un mot de retenue (r) à un produit (y.n) fourni par les moyens pour multiplier (54), p p des seconds moyens (57) pour additionner le mot T ou une partie (t) du mot T fractionn- (t0 à tp) à un résultat (RE) délivré par les premiers moyens pour additionner (55, 53r),et des moyens (56) interconnectés aux premiers et seconds moyens pour additionner pour réaliser une inversion en complément à deux du résultat (RE) délivré par les premiers moyens pour additionner (55, 53r) dans le P cas o l'opération à réaliser est du type T - y.N. 6 - Contrôleur conforme à la revendication 5, caractérisé en ce que les mots T et/ou N sont fractionnés en des mots de 8 bits ou 16 bits.