Brevet FR2855690A1 — publié le 20041203

1979, pages 121 à 123. Il consiste à générer une clé de chiffrement publique en choisissant au hasard deux nombres entiers premiers et distincts: p et q, et un nombre entier quelconque e. Le produit n = p.q et le nombre e sont inscrits dans un annuaire et constituent une clé publique. 5 Pour chiffrer des informations, un expéditeur les convertit en une suite de chiffres, qu'il scinde ensuite en blocs constituant des nombres Pl, P2, etc, appartenant à l'ensemble 0, ..., n-l. Pour chaque nombre P. l'expéditeur l calcule un nombre Ci, constituant un cryptogramme, par la formule C. = P. e modulo n, n et e étant lus dans l'annuaire à l'adresse du I I destinataire. Pour décoder les informations reçues sous la forme de Ci, C2, etc, le destinataire utilise la valeur n et une clé secrète d dont la valeur est calculée à partir des nombres premiers p et q, qui restent secrets. On montre qu'il existe toujours d tel que d.e = I modulo (p-1). (q-l) si e est premier avec (p-l) et (q-l) et on montre que 15 P. = modulo n. Pour décoder C. le destinataire calcule donc P. selon I I I 1 cette dernière formule. La clé secrète d est déterminée par la formule d. e = I modulo (p-l).(q-l). Un tiers ne peut déterminer d qu'après avoir calculé les facteurs premiers p et q tels que n = p.q, ce qui est pratiquement impossible dès lors que n comporte environ 100 chiffres. La présente invention a pour objet un procédé ayant une sécurité meilleure que le procédé R.S.A. Ce dernier ne faisant dépendre chaque nombre Ci que de la valeur d'un seul nombre Pi en clair, la sécurité du chiffrement n'est pas améliorée en modifiant l'ordre des cryptogrammes Ci: si un tiers malveillant arrivait à déchiffrer les cryptogrammes Ci il 25 lui serait aisé ensuite de remettre les nombres P. dans un ordre fournisI sant un message intelligible car la vérification de l'intelligibilité du message demande peu de temps. Par contre, le procédé selon l'invention fait dépendre chaque cryptogramme Ci d'une combinaison de plusieurs nombres P. en clair. Il permet ainsi d'augmenter la sécurité du chiffreI ment en le combinant avec une permutation des cryptogrammes Ci après leur chiffrement. Ainsi un tiers malveillant qui posséderait un algorithme de déchiffrement devrait d'abord remettre dans le bon ordre les cryptogrammes pour pouvoir les déchiffrer. Un essai de déchiffrement des cryptogrammes, en les permutant systématiquement, serait extrêmement 35 long à cause du grand nombre de permutations possibles, qui multiplierait 1979, pages 121 à 123. Il consiste à générer une clé de chiffrement publique en choisissant au hasard deux nombres entiers premiers et distincts: p et q, et un nombre entier quelconque e. Le produit n = p.q et le nombre e sont inscrits dans un annuaire et constituent une clé publique. 5 Pour chiffrer des informations, un expéditeur les convertit en une suite de chiffres, qu'il scinde ensuite en blocs constituant des nombres PI, P2, etc, appartenant à l'ensemble 0, ..., n-1. Pour chaque nombre P. l'expéditeur ! calcule un nombre Ci, constituant un cryptogramme, par la formule C. = Pe modulo n, n et e étant lus dans l'annuaire à l'adresse du I I destinataire. Pour décoder les informations reçues sous la forme de C1, C2, etc, le destinataire utilise la valeur n et une clé secrète d dont la valeur est calculée à partir des nombres premiers p et q, qui restent secrets. On montre qu'il existe toujours d tel que d.e = ! modulo (p-l). (q-l) si e est premier avec (p-l) et (q-l) et on montre que 15 P. =d modulo n. Pour décoder C. le destinataire calcule donc P. selon I I I 1 cette dernière formule. La clé secrète d est déterminée par la formule d. e = I modulo (p-l).(q-l). Un tiers ne peut déterminer d qu'après avoir calculé les facteurs premiers p et q tels que n = p.q, ce qui est pratiquement impossible dès lors que n comporte environ 100 chiffres. La présente invention a pour objet un procédé ayant une sécurité meilleure que le procédé R.S.A. Ce dernier ne faisant dépendre chaque nombre Ci que de la valeur d'un seul nombre P. en clair, la sécurité du chiffrement n'est pas améliorée en modifiant l'ordre des cryptogrammes Ci: si un tiers malveillant arrivait à déchiffrer les cryptogrammes Ci il 25 lui serait aisé ensuite de remettre les nombres P. dans un ordre fournissant un message intelligible car la vérification de l'intelligibilité du message demande peu de temps. Par contre, le procédé selon l'invention fait dépendre chaque cryptogramme Ci d'une combinaison de plusieurs nombres P. en clair. Il permet ainsi d'augmenter la sécurité du chiffreI ment en le combinant avec une permutation des cryptogrammes Ci après leur chiffrement. Ainsi un tiers malveillant qui posséderait un algorithme de déchiffrement devrait d'abord remettre dans le bon ordre les cryptogrammes pour pouvoir les déchiffrer. Un essai de déchiffrement des cryptogrammes, en les permutant systématiquement, serait extrêmement 35 long à cause du grand nombre de permutations possibles, qui multiplierait la durée des essais de déchiffrement à réaliser, au point de la rendre prohibitive. Selon l'invention un procédé de chiffrement et de déchiffrement, à clé publique de chiffrement, pour chiffrer puis déchiffrer un message représenté par une suite de chiffres, est caractérisé en ce qu'il consiste: - à choisir aléatoirement deux nombres entiers premiers: p et q, gardés secrets, et à calculer n = p x q; - à regrouper les chiffres du message par paquets de longueur fixée telle que la valeur des nombres ainsi constitués est inférieure à n; - à constituer des éléments M, fonctions de N paquets de chiffres, N étant un nombre entier fixé et supérieur à I; - à choisir un nombre entier positif r premier avec un nombre g qui est un multiple du p p c m (plus petit commun multiple) des ordres des éléments inversibles de l'ensemble des éléments M munis de la multiplica15 tion modulo n, la clé publique de chiffrement étant constituée de (n, r); - à calculer les nombres E(M) = Mr modulo n, constituant un cryptogramme du message; - à calculer un nombre entier s tel que r.s = I modulo g, s constituant une clé de déchiffrement secrète; - à calculer les nombres D(E(M)) = (E(M)) s modulo n, pour restituer les nombres constitués des paquets de chiffres du message; - à reconstituer la suite des chiffres du message. L'invention sera mieux comprise et d'autres détails apparaîtront à l'aide de la description ci-dessous, et des figures l'accompagnant: - La figure I représente le schéma synoptique d'un exemple de réalisation d'un dispositif de chiffrement ou de déchiffrement pour la mise en oeuvre du procédé selon l'invention; - Les figures 2 et 4 représentent des organigrammes illustrant un exemple de mise en oeuvre de ce procédé; - La figure 3 représente le schéma synoptique d'un exemple de réalisation d'une partie du dispositif représenté sur la figure 1. D'une façon générale le chiffrement et le déchiffrement arithmétiques d'un élément x d'un ensemble utilise deux fonctions E et D inverses l'une de l'autre dans cet ensemble 35 EoD(x) = DoE(x) = x Dans un ensemble G qui est un groupe et o g' est l'ordre du groupe, c'est-à-dire le p p c m des ordes des éléments inversibles pour la multiplication, les éléments inversibles x ont notamment les propriétés suivantes: Vx (G xg = 1G Y 1G étant l'élément neutre de l'ensemble G, et: Yx EG VA (Z xl+ g= x, o Z est l'ensemble des entiers relatifs, et les fonctions E(x) = xr et D(x) = xs sont inverses l'une de l'autre s'il existe r et s tels que: r.s = I modulo g, o g est égal à g' ou à un multiple de g'. On montre que s existe si et seulement si r et g sont premiers entre eux. Si la structure de G permet de calculer facilement l'ordre g' du groupe ou un multiple de cet ordre, alors il est aisé de déterminer s en fonction de r et donc de disposer de deux fonctions inverses E(x) = xr et D(x) = x permettant de réaliser un chiffrement et un déchiffrement. Mais 15 pour que le déchiffrement soit pratiquement impossible par un tiers ignorant la valeur de s, il faut que la connaissance de la fonction de chiffrement E(x) et de la loi du groupe ne permette pas de trouver la structure du groupe G, ou l'ordre g' . Le groupe G peut avoir une structure de groupe-produit telle que 20 G = H x K o H et K sont deux groupes d'ordre h et k respectivement. L'ordre g' des éléments inversibles de G est alors le plus petit commun multiple de h et k. On peut espérer que la connaissance de G et de la loi de ce groupe ne permette pas de déterminer h et k si on prend g suffisamment grand pour rendre impossible le calcul de k et h. Le procédé 25 de Rivest, Shamir et Aldleman utilise le groupe G = Zn des nombres n entiers relatifs modulo n inversibles. Si n = p.q, avec p et q premiers, alors G = Z x Z3. P q Le procédé selon l'invention consiste à utiliser d'autres groupes o chaque élément est fonction de plusieurs nombres entiers constitués avec 30 les chiffres de la suite représentant le message à chiffrer et à transmettre. Dans une première variante le groupe G est constitué par les éléments inversibles de l'anneau (Znx2,x) de l'ensemble des matrices 2x2 à n coefficients entiers relatifs modulo n, muni de la multiplication. Chaque matrice M = [mi m2] est constituée par 4 nombres ml, m2, m3, m4 qui 335 sont des nombres constitués, par exemple, chacun par deux chiffres 3 5 sont des nombres constitués, par exemple, chacun par deux chiffres hexadécimaux consécutifs d'une suite de chiffres representant en codes ASCII le message à transmettre. Ces nombres ont des valeurs comprises entre O et n - 1, inclus. Le nombre n est choisi supérieur à 1080 pour que sa décomposition en facteurs premiers soit pratiquement impossible avec 5 les moyens de calculs disponibles actuellement. Il est calculé en faisant le produit de deux nombres premiers p et q choisis aléatoirement et qui sont gardés secrets. On montre que le nombre d'éléments inversibles du groupe 2x2 2 2 G = Z2 est alors p.(p-l)2.(p+l).q(q-l)2.(q+l) et que la valeur de l'ordre n g', qui est le p p c m de ces valeurs, n'est calculable qu'à partir des valeurs p et q. La valeur de s est donc impossible à calculer pour qui ne connaît pas p et q. La clé publique de chiffrement est constituée par n et par un nombre entier r, premier avec un nombre entier g, choisi aléatoirement. Le chiffrement de la portion de message représentée par les nombres ml, m2, m3, m4, consiste à calculer E(M) = Mr = o n, n2 Lm3, m2 modulo n = n3, n#4 m3, m4Les nombres ni, , n n3, n4, obtenus constituent un cryptogramme de cette portion de message. Le déchiffrement consiste à calculer: D [E(M) = (Mr)s [n l3 modulo n = [m, m Ln2Y n| L2s m 4 o la valeur de la clé secrète est s, telle que r.s = I modulo g Les nombres ml, , m2 m3, m4 obtenus permettent de reconstituer la suite de chiffres hexadécimaux constituant le message dans cet 25 exemple. Chacun des cryptogrammes ni, n2, n3, n4 est fonction de m1, m2, m3, m4 et r simultanément, sans qu'il y ait d'expression simple de cette fonction contrairement au procédé R.S.A o les nombres obtenus sont: n = mr (mod n) n2 = n (mod n) r n3 m (mod n) n = mr (mod n). Si les cryptogrammes n1, n2, n3, n4 ne sont pas transmis dans l'ordre correspondant à la suite représentant le message, il est nécessaire de les remettre dans cet ordre avant de les déchiffrer sinon le déchiffrement donne des chiffres qui sont différents des chiffres du message, contraire5 ment au procédé R.S.A qui fournirait des chiffres exacts, mais en désordre. Le procédé selon l'invention, combiné avec une permution des cryptogrammes, procure une sécurité plus grande que le procédé R.S.A grâce à cette propriété. En effet, si un tiers malveillant possédait un algorithme de décryptage, il pourrait décrypter séparément chacun des 10 cryptogrammes obtenus par le procédé R.S.A. puis rechercher la permutation permettant d'obtenir un message intelligible. La vérification de l'intelligibilité étant simple, cette recherche serait rapide à réaliser. Par contre, pour décrypter un message chiffré par le procédé selon l'invention, puis ayant subi une permutation, ce tiers malveillant devrait appliquer son 15 algorithme de décryptage en permutant, d'abord les cryptogrammes de toutes les manières possibles. La durée du calcul de décryptage est alors multipliée par le nombre de permutations à essayer, ce qui rend l'opération pratiquement impossible à réaliser. Naturellement, la permutation peut porter sur un nombre de cryptogrammes supérieur à quatre. Cette amélioration de la sécurité a pour inconvénient une durée plus importante des calculs de chiffrement et de déchiffrement par rapport au procédé R.S.A., mais cette augmentation est faible. Considérons le cas d'une élévation au carré dans le cas du procédé R.S.A et dans le cas de cette première variante du procédé selon l'invention: le calcul 25 de (ml) 2, (m2)2,(m3)2, et (m)2 modulo n nécessite 4 multiplications alors que le calcul de [m M3]mdl 2 [m m]modulo n, nécessite le calcul de: (ml) 2 4 m2.m3 m4 m1 + mn4 m2.(m1 + m4) m3.(m1 + m4) (ml)2 + m2.m3 m 4 + m2.m3 c'est-à-dire 5 multiplications et 3 additions modulo n. La durée de calcul d'une multiplication étant prédominante par rapport à celle du calcul d'une addition, la différence se réduit pratiquement à la durée d'une multiplication. Dans le cas d'une multiplication de 2 matrices quelconques 5 le calcul nécessite 8 multiplications et 4 additions. Le calcul d'une élévation à une puissance quelconque est réalisé par des élévations au carré successives et par des multiplications. L'augmentation du temps de calcul par rapport au procédé R.S.A. est de l'ordre d'un facteur 2, ce qui est peu gênant en pratique. Le chiffrement et le déchiffrement selon la première variante du procédé selon l'invention supposent que la matrice M = mI m3 _2 m4 soit inversible, ce qui n'est pas certain, car les nombres m1, m2, m3, m4 ne dépendent que des chiffres du message et sont donc aléatoires. En pratique l'éventualité d'une matrice non inversible n'est pas gênante car on montre que sa probabilité d'apparition est de l'ordre de 2 ce qui est 60 r très faible dès lors que n est supérieur à 10. Une seconde variante du procédé selon l'invention consiste à utiliser les éléments d'un sous ensemble multiplicatif V constitué des n éléments inversibles de l'anneau des nombres de la forme m = a + b.'d o 20 a et b sont des entiers relatifs modulo n et o d est un entier positif qui n'est pas un carré parfait dans l'ensemble Zn des entiers relatifs modulo n. Soit g l'ordre de ce sous-ensemble. Le chiffrement consiste d'abord à constituer des élément m = m +m2. \rdà partir de nombres m et m2 constitués en regroupant 25 par paquets de longueur fixée les chiffres de la suite représentant le message. Par exemple mI et m2 sont constitués chacun de deux chiffres hexadécimaux de la suite obtenue en traduisant le message en code ASCII. Les valeurs de ces nombres sont comprises entre 0 et n-I inclus. Le nombre n est choisi de l'ordre de 1080, en choisissant aléatoirement deux 30 nombres entiers p et q et en calculant n F p x q. Un nombre entier r premier avec g est choisi aléatoirement. La clé de chiffrement publique est (n, r), alors que les valeurs p et q sont gardées secrètes. On montre que l'ordre du sous-groupe Vn est: g' = p p c m [(p), (q)], p p c m désignant le plus petit commun 35 multiple; qu'il ne peut être calculé qu'à partir de p et q; et que le fonction V est telle que, pour u premier: W(u) = (u - l)2 si d est carré de Z 8)(u) = u -_ 1 sid n'est pascarré de Z u Si d n'est pas carré de Z et n'est pas carré de Z: g = (p2- l).(q2 - 1) P q Si d est carré de Z et n'est pas carré de Zq: g = (p-l)2.(q2-1) P Si d n'est pas carré de Z et est carré de Z: g = (p2-1).(q-l)2 p q Si d est carré de Zp et Zq, il est carré de Zn' donc sans intérêt pour ce procédé de chiffrement. Le chiffrement consiste à calculer r m modulo n = (m1 + m2.ad)r modulo n = n1 + n2.d, n1 et n2 constituant des cryptogrammes de ml et m2, et les calculs étant réalisés suivant la règle (a+b 4)(a'+b' r) = (aa'+dbb')+(ab'+a'b)./ 15 On montre qu'il existe un nombre entier s tel que: (n+ n2) modulon = m + m2.d et tel que r.s = I modulo g. Le nombre s constitue la clé de déchiffrement secrète et est déduit de la formule r.s = i modulo g, o g est égal à g' ou à un multiple 20 de g'. Le calcul du p p c m de t(p) et Y (q) nécessite de décomposer leur valeur en facteurs premiers ce qui est une opération très difficile lorsque ces nombres ont une valeur élevée, c'est pourquoi, en pratique, la valeur choisie pour g est celle du produit (p) x (q) et non la valeur g' du p p c m de 1(p) et 4(q). 25 g = ' (p) x V (q). Le déchiffrement consiste donc à calculer (n1 + n2' /)s modulo n = m1 + m2.d, puis à reconstituer la suite des chiffres hexadécimaux du message à partir des nombres m1 et m2. Comme la première variante du procédé selon l'invention, cette seconde variante peut être combinée à une permutation des cryptogram- mes pour obtenir une sécurité améliorée par rapport au procédé R.S.A. au prix d'une augmentation de la durée des calculs, de l'ordre d'un facteur 2. En effet, le calcul de (ml + m2. d)2 modulo n nécessite trois multiplications et une addition modulo n; et un produit de deux éléments quelcon5 que nécessite quatre multiplications et deux additions modulo n. Cette augmentation de la durée de calcul est suffisamment faible pour ne pas être gênante en pratique. Tous les éléments m de l'ensemble Vn ne sont pas inversibles, il peut donc y avoir impossibilité de chiffrer et de déchiffrer certains 10 couples m1, m2. On montre que si d n'est ni carré de Zp et de Zq tous les messages sont correctement codés. Si d est carré soit de Zp, soit de Zq certains couples ml, m2 ne sont pas inversibles, mais on montre que ce cas a une probabilité égale à environ 2(- + -), c'est-à-dire 4.10-3 si p et q 30 p q sont de l'ordre 10. Le choix de d est libre, mais il doit cependant être limité aux entiers positifs non carrés dans Z. D'autre part, comme il a été n mentionné précédemment, les formules de calcul de g en fonction de p et q, changent selon que d est carré ou non carré dans Z et dans Zq. P q Déterminer si un nombre d est un carré dans Z ou dans Zq,pour p et q 20 ayant une valeur élevée, est un problème à la portée de l'homme de l'art, mais qui est relativement complexe car il n'y a pas de formules générales. Ce n'est pas très gênant pour utiliser le procédé car d a une valeur fixée et publique. Par exemple, on montre que 2 est carré de Zu si et seulement si 25 u =- + 3 modulo 8 donc pour d = 2 et u premier: (u) = u2 -1 si u + 3 modulo 8 (u) = (u-1)2 si u = + I modulo 8 On montre que 3 est carré de Zu si et seulement si u = + 1 modulo 12, donc pour d = 3 et u premier: 30 4i'(u) = u2-1 si u = + 5 modulo 12 f(u) = (u-I)2 si u = + I modulo 12. La figure I représente le schéma synoptique d'un exemple de réalisation d'un dispositif de chiffrement ou de déchiffrement pour la mise en oeuvre du procédé selon l'invention. Il comporte une borne d'entrée/sortie 1, un miprocesseur 2, une visu 3, une interface 4, et un circuit 5 de multiplication modulo. Le microprocesseur 2 possède une entrée/ sortie série reliée à la borne d'entrée/sortie I pour recevoir ou émettre des données chiffrées, la borne I étant reliée à un autre dispositif de chiffrement ou de déchiffrement identique. Le microprocesseur 2 possède en outre une entrée/sortie reliée à la visu 3 pour recevoir des données et des commandes d'un opérateur et pour afficher des données en clair; une entrée/sortie de 32 bits reliée à l'interface 4; et une entrée/sortie de 10 commandes reliée au circuit 5. Le circuit 5 possède une entrée de 128 bits reliée à une sortie de l'interface 4, une sortie de 128 bits reliee a une entrée de l'interface 4, et une entrée/sortie de commandes reliée à l'entrée/sortie de commandes du microprocesseur 2. Comme il apparaît dans la description du procédé, celui-ci nécessite principalement de 15 calculer les puissances d'un nombre donné, modulo un autre nombre fixé. Dans cet exemple de réalisation toutes les multiplications modulo sont realisées dans un circuit spécialisé et rapide, le circuit 5. Le microprocesseur 2 a principalement un rôle de séquenceur pour commander les échanges d'informations entre la borne d'entrée/sortie 1, la visu 3, et le 20 circuit 5. L'interface 4 a pour rôle de transformer les mots de 128 bits constituant le multiplicateur, le multiplicande, et le résultat des multiplications modulo, en des mots de 32 bits assimilables par le microprocesseur 2. Les paramètres n et r qui constituent la clé publique du destinataire du message chiffré, ainsi que les paramètres p, q, g et s qui constituent la clé 25 secrète du dispositif considéré, sont stockés dans une memoire interne au microprocesseur 2 après avoir été introduits par un clavier incorporé à la visu 3. La réalisation d'un générateur de clé pour mettre en oeuvre le procédé selon l'invention est à la portée de l'homme de l'art. Un tel générateur comprend un générateur de chiffres aléatoires, dont la réalisation est classique, fournissant 3 nombres i p, q, et r; et un dispositif de calcul permettant de vérifier si p et q sont premiers, en mettant en oeuvre un test de primalité de Miller-Rabin; permettant de calculer n = p.q et g, selon les formules vues précédemment dans le cas d = 2 par 35 exemple; et permettant de calculer s en fonction de r et de n selon les Il formules vues précédemment. Les valeurs n et r sont publiques alors que les valeurs p, q, g, et s sont gardées secrètes. Dans cet exemple de réalisation le dispositif de chiffrement ou de déchiffrement met en oeuvre la seconde variante de procédé selon 5 l'invention, avec d = 2. Lors du chiffrement d'un message la visu 3 fournit au microprocesseur 2 les caractères de ce message, sous la forme ASCII. Le microprocesseur 2 découpe la suite des bits en blocs de 127 bits auxquels est ajouté un 128 me bit de valeur nulle. Les calculs sont effectués sur 128 bits et le 128 me bit de ces blocs est utilisé comme bit 10 de dépassement. Le programme suivi par le microprocesseur 2 pour le chiffrement est très semblable à celui suivi pour le déchiffrement. Pour chiffrer deux blocs de données: m] et m2, le microprocesseur calcule (ml + m2. )r modulo n, en utilisant le circuit 5 pour réaliser les multiplications, puis il 15 transmet à la borne 1 les cryptogrammes nI et n2 obtenus. En attendant d'être chiffrées les données en clair sont stockées dans une mémoire tampon interne au microprocesseur 2, et les cryptogrammes sont stockés dans cette mémoire tampon avant d'être transmis afin de régulariser le débit des données transmises vers la borne 1. Pour le déchiffrement le microprocesseur 2 stocke dans cette mémoire tampon les cryptogrammes reçus par la borne 1. Il lit dans cette mémoire deux cryptogrammes nI et n2, qui sont deux crytogrammes qui ont été chiffrées ensemble, mais pas forcément transmis ensemble s'il est prévu des permutations des cryptogrammes dans le procédé mis en oeuvre. 25 Le microprocesseur 2 calcule (nI + n2 /)s modulo n en utilisant le circuit pour réaliser toutes les multiplications modulo n. La valeur s de la clé secrète est disponible dans une mémoire interne au microprocesseur 2. Ce calcul fournit deux valeurs en clair: m1 et m2, qui sont stockées dans la mémoire tampon du microprocesseur 2 puis sont transmises à la visu 3 30 sous une forme permettant d'afficher un message alphanumérique. Dans cet exemple les données sont remises sous la forme de paquets de 7 bits codés en code ASCII. Le microprocesseur 2 traite successivement chaque couple de paquets de données chiffrées jusqu'à ce que sa mémoire tampon n'en contienne plus. L'élévation d'un nombre x à la puissance ca modulo n est réalisée par une succession de multiplications, en minimisant leur nombre. n c est de la forme:c = Ea..21, avec a. = 0 ou 1 n Oa..2 i a 0a n 2i donc:x =x = r a..x i=O 0 a.IO a i eo exemple x19 = 16 x.x2tl6 = xX2(x22)2)2 x peut donc être calculé par 6 multiplications La figure 2 représente l'organigramme des opérations réalisées par le microprocesseur 2 pour calculer y = x Y représente le contenu d'un registre utilisé comme accumulateur, X représente le contenu d'un registre utilisé pour stocker successivement les puissances de x, et i est le contenu d'un registre servant de compteur. Au commencement du calcul, Y est initialisé à 1, X est initialisé avec la valeur x, et i est initialisé à 0. Lorsque la valeur d'un 15 coefficient ai est égale à 1 la valeur de Y est multipliée par la valeur de X, modulo n, en utilisant le circuit 5. Cette opération est recommencée pour chaque valeur de i telle que ai= 1, jusqu'à ce que i atteigne la valeur n. Pour chaque nouvelle valeur de i la valeur de X est remplacée par sa valeur au carré, modulo n, calculée en utilisant le circuit 5. 20 Soit, par exemple, à chiffrer le message suivant: "COMMENT ALLEZ VOUS"; par la seconde variante du procédé selon l'invention et en utilisant pour clé publique n = 143 = 11 x 13, r = 17. Ces valeurs sont trop petites pour assurer la sécurité du chiffrement, mais elles constituent un exemple simple à exposer. d est pris égal à 2. Ce 25 message est tapé sur le clavier de la visu 3 qui le transmet au microprocesseur 2, en code ASCII, c'est-à-dire avec 7 bits par caractère. La valeur n = 143 étant comprise entre 27 et 28 le message est chiffré par blocs de 7 bits, plus un bit de dépassement. Chaque bloc correspond exactement à un caractère du message puisque, dans le code ASCII, 30 chaque caractère est représenté par 7 bits. Considérons le chiffrement des deux premiers caractères C est codé 0101000 O est codé 0010100 Ces 2 paquets correspondent aux nombres 28 et 14 en hexadécimal. Le chiffrement est appliqué aux nombres m 1= 28 et m2 = 14. Il consiste à calculer: mr = (m + F.m2)r modulo 143 m = (28 + 14 /)17 modulo 143 or m17 = m.m16 modulo 143 17 2 22 2 donc m7 = m.(((m2)2)2)2 modulo 143 Le calcul est réalisé par cinq multiplications successives, réalisées par le circuit 5 sous la commande du microprocesseur 2 m = (28 + 14 2).(28 + 14 /2) = 32 + 69 r/ modulo 143 m = (32 + 69 'F2).(32 + 69 '/2) = 107 + 126 X/ m =(107 + 126 \) .(107 + 126 V) = 15 + 80 16 m16 = (15 + 80 V2).(15 + 80 r2) = 12 + 112 r[ m = (28 + 14 1[).(12 + 112 -2) = 40 + 15 f et 15 constituent les cryptogrammes nI et n2 à transmettre. A la clé publique r = 17 correspond la clé secrète s telle que r.s = I modulo g o g est un multiple de g' = p p c m (i(p), W(q)). En 20 pratique on prend g = ''(p). Y(p) mais pour simplifier l'exemple décrit on prend ici g = p p c m (W(p) ,Y(q)). Dans cet exemple n = 143 = 11x13. Les paramètres secrets p = 11 et q = 13 sont congrus à + 3 modulo 8 donc, d'après les formules mentionnées précédemment pour d = 2: (p) = p2 _ 1 = 121-1 = 120 tf(q) = q2-1 = 169-1 = 168 donc g = 840, et s = 593 Soit t=n1 +n. . Le déchiffrement est réalisé en calculant: t = (n + n2 2)S modulo 143 = (40 + 15 r. 3 modulo 143 or 593 = 512 + 64 + 16 + I Le microprocesseur 2 commande successivement sées par le circuit 5 t2= (40 + 15).(40 + 15 2) = 48 + 56 i t4 =(48 + 56 \2).(48 + 56) = 139 + 85 q t = (139 + 85 \).(139 + 85 V2) = 23 + 35 t16 = (23 + 35 r).(23 + 35 r. = 119 + 37 '1r t32 = (119 + 37 '\2).(119 + 37 ') = 25 + 83 t =(25 + 83 1). (25 + 83 r. = 103 + 3 r 128 =113 t128 = (103 + 3 2).(103 + 3 \r2) = 45 + 46\F 256 = (45 + 46).(5 + 46) = 103 + 136 t = (45 + 462)45 4 2)=13+36r 12 multiplications, réali1 modulo 143 À t512 = (108 + 13642).(108 + 1364) = 36 + 611i m=593 512 64 * 16t2 4r m = t3 = tt64.t6.t= 28 + 14 f/2 m= m1 +m2 = 28 + 14 r donc m = 28 m2= 14 Remis sous la forme binaire, puis sous la forme de caractères alphanumériques, les blocs m1 et m2 restituent les caractères C et O du message clair. La multiplication d'un nombre entier x par un nombre entier y, modulo un nombre entier n est réalisée en calculant successivement: I = -1 n a = x. y b = a.j q = [b]la partie entière de b n.q a-n.q Il y a donc 3 multiplications (ordinaires) à réaliser. soit x = a0o.2 +al.21+a2.22+...+ap,.2P y = bo.20+b.21+b2.22+...+bp,.2P' V' 2 p n = co.20+c1.21+c+...+cp,.2P avec cp, = 1. O l 2 p p alors j 1 = 1 n C.2 +cl.2 +...cp,.2p cp.2p ) = c.2P+1.2)+c2.2 (p' )+... + 1 -= P. 1l- 1 - 2P j = Cp,.2 P(l-k.2 +k2.2 +...kp.2)+a Une première multiplication donne: I 2p'1 a = x.y = a 0.bo+(al bo+bl.a0).2 +...+ap,.bp. 2 a possède 2p'+1 termes, de poids 2 à 22p. Une deuxième multiplication donne b = a.j. Les p' premiers termes de j étant nuls cette multiplication est réalisée avec les p'+l derniers 10 termes de j, de poids 2-2p' à 2-p'. Pour que le multiplicateur et le multiplicande de la multiplication soient dans la même gamme de poids, 22p à 2P', il suffit de multiplier au préalable a par 2-P' et de multiplier au préalable j par 2p', ce qui ne changera rien au résultat de la multiplication a.j. 1 5 soit a' = a.2-P et j' = j.2P alors b = a.j = a'.j' a', j' et b peuvent être écrits de la manière suivante a' = ao.bo.2 +(al.bo+bl1.ao)a + .+ap,.bp,.2P j = (l-k2-+k2-2 +...+k.2-P)+ l' 2' 2 b = a'.j' = (dp,.2P+ dp 1.2P-+...+dl.21+do+d 1.2- +...+d_2p,.2- P)+a'...DTD: La détermination de la partie entière de b consiste à ne conserver que les p'+l bits de poids fort: q = [b] dp,.2P+dp, 11.2P 1+...+d La troisième multiplication donne: q.n = c.d +(c l.d +c d).2±-.+c,.dp,.2p oo P.1)2 La soustraction a-a.n élimine les p'+l bits de poids fort de a, et donne un reste, codé sur p+1 bits, qui est éventuellement majoré de n car le coefficient E.al, mentionné précédemment et qui est négligé dans le calcul de b, peut causer une erreur de -1 sur b et q, puis une erreur de -n 5 unités sur q.n et de + n unités sur a-q.n. Dans le cas o le reste est supérieur à n, il est erroné de +n, et doit être diminué en soustrayant cette valeur. Les multiplications sont réalisées par un circuit spécialisé, le circuit 5, afin d'obtenir une vitesse de calcul relativement élevée compte tenu du nombre de bits du multiplicateur et du multiplicande. Dans cet 10 exemple, ces nombres de bits sont égaux à 128, autrement dit p' = 127. Pour améliorer la sécurité du chiffrement on peut augmenter ce nombre de bits et utiliser 256 bits par exemple, mais le coût du matériel augmente dans la même proportion. Sur la figure 3, l'exemple de réalisation du circuit 5 comporte 15 des registres 6, 7, 8, 9, 11, 14, et 17 pouvant stocker un mot de 128 bits en parallèle, des multiplicateurs 10, 13, et 15, pour multiplier deux mots de 128 bits et fournir un résultat sur 256 bits, un dispositif à retard 12 pour retarder un mot de 256 bits, et un soustracteur 16 pour mots de 128 bits. Les registres 6, 7, 8, 9 ont une entrée parallèle reliée à la borne d'entrée 20 19 du circuit 5 et stockent des mots de 128 bits qui sont respectivement: X, Y, 1, et J. Le multiplicateur 10 possède deux entrées reliées respectivement à une sortie parallèle du registre 6 et à une sortie parallèle du registre 7, et possède une sortie reliée à une entrée parallèle du registre Il pour lui fournir un mot binaire A de 256 bits. Le multiplicateur 13 25 possède deux entrées reliées respectivement à une sortie parallèle du registre 11 et à une sortie parallèle du registre 8, et possède une sortie reliée à une entrée parallèle du registre 14. Le multiplicateur 13 fournit un mot binaire B de 256 bits, mais seuls les 128 bits de poids fort sont appliqués à l'entrée du registre 14 et constituent un mot binaire Q. Le 30 multiplicateur 15 possède deux entrées reliées respectivement à une sortie parallèle du registre 14, pour recevoir le mot binaire Q de 128 bits, et à une sortie parallèle du registre 9, pour recevoir le mot binaire J de 128 bits; et possède une sortie reliée à une entrée - du soustracteur 16 pour lui fournir un mot binaire U de 256 bits. Le soustracteur 16 possède en outre une entrée + reliée à une sortie du dispositif à retard 12, pour recevoir le mot binaire A retardé, et une sortie reliée à une entrée parallèle du registre 17, pour lui fournir un mot binaire R de 128 bits. Le registre 17 possède une sortie reliée à la borne de sortie 18 du circuit 5. 5 Le dispositif à retard 12 est constitué, par exemple, de 256 registres à décalage en parallèle, retardant un mot binaire de 256 bits appliqués respectivement sur 256 entrées série, d'un temps égal au temps de calcul dans les multiplicateurs 13 et 15, et dans le registre 14. Tous les éléments du circuit 5 reçoivent des signaux de commande, non représentés sur la 10 figure 4 et qui sont générés par le microprocesseur 2. La figure 4 représente un organigramme du calcul de x.y modulo n tel qu'il est effectué dans l'exemple de réalisation du dipositif de chiffrement et de déchiffrement selon l'invention. La partie du traitement située au-dessus des pointillés est réalisée par le circuit 5 dont un 15 exemple de réalisation est représenté sur la figure 3. La partie du traitement située en dessous des pointillés est effectuée par le microprocesseur 2. Comme il est indiqué sur l'organigramme représenté par la figure 4, la multiplication x.y modulo n est réalisée: en chargeant successi20 vement les registres 6, 7, 8, 9 avec des mots binaires de 128 bits constitués respectivement des valeurs x, y, n, et n; puis en commandant le multiplicateur 10 pour multiplier les mots binaires X et Y fournis par les registres 6 et 7; en commandant le stockage dans le registre Il du mot binaire A fourni par le multiplicateur 10; puis en commandant le 25 multiplicateur 13 pour multiplier A par le mot binaire I fourni par le registre 8 et de valeur-; en commandant le stockage dans le registre 14 du mot binaire Q constitué par les 128 bits de poids le plus fort du mot B, c'est-à-dire la partie entière de B; en commandant le multiplicateur 15 pour multiplier Q par J et fournir un mot binaire U de 256 bits à l'entrée 30 du soustracteur 16; en commandant le dispositif à retard 12 pour stocker et retarder A, puis le transmettre à l'entrée + du soustracteur 16; puis en commandant le registre 17 pour stocker un mot binaire R constitué des 128 bits de poids faible du mot binaire fourni par le soustracteur 16, les 128 bits de poids fort étant nuls. Le mot binaire R est transmis au 35 microprocesseur 2 par l'intermédiaire de la borne de sortie 18 et de l'interface 4, puis le microprocesseur 2 termine le calcul selon l'organigramme représenté à la partie inférieure de la figure 4. La valeur du mot R est comparée par rapport à la valeur n; si elle est supérieure à n le résultat R' du calcul de x.y modulo n est constitué par la différence R-n, 5 sinon il est constitué par la valeur de R; puis ce résultat R' est stocké dans une mémoire du microprocesseur en attendant une utilisation ultérieure. Les multiplicateurs: 10, 13, 15 peuvent être constitués en cascadant des circuits intégrés multiplicateurs pour mots de 16 bits, tels que 10 ceux fabriqués par la Société TRW LSI PRODUCTS sous la référence MPY 16 AJ. Le microprocesseur peut être constitué, par exemple, par un microprocesseur 68 000 de la Société MOTOROLA. L'invention n'est pas limitée aux exemples de réalisation décrits cidessus. Il est à la portée de l'homme de l'art d'utiliser des valeurs de d 1 5 autres que 2 ou 3, ou bien d'utiliser d'autres dispositifs pour réaliser les multiplications. REVENDICATIONS 1. Procédé de chiffrement et de déchiffrement, à clé publique de chiffrement, pour chiffrer puis déchiffrer un message représenté par une suite de chiffres, caractérisé en ce qu'il consiste: - à choisir aléatoirement deux nombres entiers premiers: p et q, gardés secrets, et à calculer n = p x q; - à regrouper les chiffres du message par paquets de longueur fixée telle que la valeur des nombres ainsi constitués est inférieure à n; - à constituer des éléments M, fonctions de N paquets de chiffres, N étant un nombre entier fixé et supérieur à I; - à choisir un nombre entier positif r premier avec un nombre g qui est un multiple du p p c m des ordres des éléments inversibles de l'ensemble des éléments M munis de la multiplication modulo n, la clé publique de chiffrement étant constituée de (n, r); - à calculer les nombres E(M) = Mr modulo n, constituant un 15 cryptogramme du message; - à calculer un nombre entier s tel que r.s = I modulo g, s constituant une clé de déchiffrement secrète; - à calculer les nombres D(E(M)) = (E(M)) s modulo n, pour restituer les nombres constitués des paquets de chiffres du message; 20 - à reconstituer la suite des chiffres du message. 2. Procédé selon la revendication 1, caractérisé en ce que les éléments M sont des matrices 2 x 2 dont les coefficients sont quatre nombres constitués respectivement par quatre paquets de chiffres du message; et en ce que g = p.(p - l).(p + 1).q(q - 1).Oq + 1)2. 3. Procédé selon la revendication 1, caractérisé en ce que les éléments M sont de la forme M = a + b.N'o a et b sont des nombres constitués respectivement par deux paquets de chiffres du message, et ou d est un nombre entier positif qui n'est pas un carré parfait dans l'ensemble Zn des entiers relatifs modulo n, et qui est public; en ce que 30 g = Y (p) x 8 (q); et en ce que, pour u premier, la fonction Y est de la forme: (u) = (u - 1)2 si d carré de Zu et (u)= u2 u sid noncarrdeZu et Y (u)= u _-1 si dnon carré de Z 4. Procédé selon l'une quelconque des revendications I à 3, caractérisé en ce qu'il consiste, en outre, à effectuer des permutations entre les cryptogrammes du message avant de les transmettre, selon une fonction de permutation secrète; puis à effectuer après la transmission des permutations inverses avant de les déchiffrer. 5. Dispositif de chiffrement pour la mise en oeuvre du procédé selon la revendication 1, caractérisé en ce qu'il comporte - des moyens (2) pour stocker des nombres r et n; - des moyens (2, 3) pour entrer et stocker un message représenté 10 par une suite de chiffres; - des moyens (2) pour regrouper ces chiffres par paquets de longueur déterminée; - des moyens (2, 4, 5) pour déterminer des cryptogrammes en calculant E(M) = Mr modulo n, o M est une fonction d'un nombre fixé de 15 paquets, supérieur à 1; 6. Dispositif de déchiffrement pour la mise en oeuvre du procédé selon la revendication 1, caractérisé en ce qu'il comporte - des moyens (2) pour stocker des nombres s et n; - des moyens (2, 4, 5) pour déterminer des paquets de chiffres en 20 clair, en calculant (E(M))s modulo n, o E(M) est une fonction d'un nombre fixé de cryptogrammes, supérieur à I; - des moyens (2) pour reconstituer une suite de chiffres représentant un message en clair, à partir des paquets de chiffres en clair obtenus. 7. Dispositif de chiffrement selon la revendication 5 pour la mise 25 en oeuvre du procédé selon la revendication 4, caractérisé en ce qu'il comporte en outre des moyens (2) pour permuter l'ordre des cryptogrammes selon une loi temporelle secrète. 8. Dispositif de déchiffrement selon la revendication 6 pour la mise en oeuvre du procédé selon la revendication 4, caractérisé en ce qu'il 30 comporte en outre des moyens (2) pour remettre les cryptogrammes dans l'ordre o ils étaient avant d'être permutés.