Brevet FR2728981A1 — publié le 19960705

PROCEDE POUR L4 MISE EN OEUVRE D'UN PROTOCOLE DE COMMUNIA TION A CL E PRO VER ENTRE DEUX DISPOSITIFS DE TRAITEMENT La présente invention a pour objet un procédé pour la mise en oeuvre d'un protocole de communication entre deux dispositifs de traitement dont l'un au moins est un support de mémorisation portable tel qu' une carte à puce. La confidentialité des informations reste à 1' heure actuelle une préoccupation majeure. I1 apparaît clairement que l'information sous toutes ses formes possède une valeur intrinsèque bien que parfois difficile à évaluer. La richesse d'une entreprise, d'un état même, réside ainsi pour une bonne part dans cette masse croissante de documents papiers et électroniques contenant le condensé de son activité passée, présente et même future. Les documents papiers dont la teneur justifait une protection étaient cachés, dissimulés dans des endroits dont l'accès était rendu le plus difficile possible. L'extension du courrier et de l'archivage électronique renouvelle le problème et induit la recherche de solutions pouvant répondre au même besoin de se protéger. La réponse apportée dans ce domaine repose sur la notion de partage à un moment donné d'une information secrète par un groupe de personnes. Les procédés mis en oeuvre jusqu'à présent sont basés sur des opérations simples pouvant être implémentées sur n'impolte quel dispositif capable d'opérations élémentaires (addition binaire, décalage, permutations...). La nature même de ces procédés implique un travail de conception long et particulièrement minutieux afin de construire une machine dont la logique ne pourra que très difficilement être prise en défaut et en tous les cas jamais de façon fatale. Le secret sur lequel repose toute la sécurité du système serait en effet divulgué dans le cas contraire et cette divulgation entraînerait alors la faillite du dit système. La construction de protocoles efficaces représente donc un investissement en temps et en ressources particulièrement lourd. Enfin la recherche d'une adaptabilité maximale conduit à une limitation des performances d'autant plus grande que la quantité d'information à traiter est importante. La présente invention permet de résoudre ce problème et en particulier de supprimer les contraintes de fabrication entraînées par le fait que toute la fiabilité du système ne repose que sur le caractère secret des informations gardées par ce matériel. Selon l'invention, on propose de répartir cette contrainte d'une part sur le secret gardé et d'autre part sur les traitements effectués c'est à dire sur le protocole lui-meme. A cette fin, selon l'invention, le procédé permet de réaliser des protocoles cryptographiques à clef secrète durcis grâce à 1' utilisation de ressources (matérielles ou logicielles) initialement dévolues à la réalisation de calculs complexes ( par exemple des opérations mettant en oeuvre le calcul modulaire) dans le cadre de protocoles cryptographiques à clef publique (DH, El Gamal, Schnorr, Fiat-Shamir, etc...). Des dispositifs équipés de ressources de calcul permettant de réaliser des opérations complexes (comme le calcul modulaire par exemple) sont connus à ce jour, on peut citer à titre d'exemple les circuits tels que le circuit ST16CF54 de la Société Thomson, 83C852/5 de la société Philips ou le SLE 44CP200. Selon l'invention on utilise une telle ressource de façon judicieuse, c'est à dire en utilisant des opérations prenant peu de temps mais dont les effets sur les données sont efficaces en terme de déformation de l'information traitée. Le principe est de combiner des opérations faisant appel à la fois aux ressources dédiées à des opérations complexes et au coeur du dispositif luimême, quel que soit sa nature (simple micro-contrôleur de type 8051 ou 6805, processeurs de la famille 80x86 ou 680x0, processeurs évolués (PENTIUM, puces Alpha, SUN ou RISC) et processeurs parallèles (machine HYPERCUBE par exemple) en combinant les informations en clair avec une clef secrète afin d'obtenir un message chiffré que seule une personne capable de reconstituer le secret peut déchiffrer. Ainsi l'invention propose un système extrèmement sécurisé dans lequel le calcul modulaire pourra porter sur un grand nombre par exemple 80 bits, 160 bits ou 512 bits ou plus et ne nécessitant que la combinaison de deux opérations. La présente invention a plus particulièrement pour objet un procédé pour la mise en oeuvre d'un protocole à clef secrète entre deux dispositifs de traitement, I'un d'entre-eux aux moins étant un support de mémorisation portable, principalement caractérisé en ce qu'il comprend les étapes suivantes équiper les dispositifs d'un circuit de traitement numérique apte à réaliser des opérations de type calcul modulaire pour la mise en oeuvre d'opérations telles que la multiplication modulaire, . utiliser ce circuit de traitement pour mettre en oeuvre une fonction de chiffrement à clé secrète composée d' une succession d'opérations réversibles comportant au moins la combinaison de deux opérations, l'une de type calcul modulaire et l'autre relevant de la logique binaire, . appliquer cette fonction soit sur des messages destinés à êtres transmis pour les chiffrer ou les signer, soit sur des messages reçus pour les déchiffrer. Afin de traiter des messages de n'importe quelle longueur, on réalise préalablement à tout traitement un découpage en q blocs x de N bits. Selon un autre objet de la présente invention, la fonction de chiffrement à clé secrète comporte la combinaison de deux opérations, dont l'une est une permutation mettant en oeuvre une multiplication modulaire et l'autre une opération logique ou- exclusif, de sorte que f est telle que: f(x) = (x ffl K2) * K, mod n dans laquelle:: x représentant un bloc de N bits du message K1 et K2 représentent une première et une deuxième clef secrète sur N bits, n un nombre impair de N bits, # une opération ou exclusif, * une opération de multiplication modulo n, Selon un autre aspect de l'invention, l'utilisateur peut choisir K1* K2 ou K1 = K2 Selon un autre aspect de l'invention, lorsqu' un dispositif envoie des messages, il opère sur le message un premier traitement consistant à appliquer sur chaque bloc x la fonction choisie f de façon itérative. De préférence on utilisera un nombre p d'itération au moins égal à 4. Ainsi selon un premier mode de réalisation Aj et Ak communiquent entre eux selon le protocole suivant: . le dispositif Aj chiffre chaque bloc x du message M préalablement découpé en (q + 1) blocs de N bits de sorte chaque bloc chiffré y du message soit tel que E(x) = fP(x) # K mod n = y, p étant supérieur ou égal à 4, le dispositif envoie les (q+l) y blocs au dispositif Ak, le dispositif Ak effectue sur chaque y l'opération suivante D(y) = gP(y) # K mod n = x, pour réaliser le déchiffrement du bloc y, de manière à déchiffrer y et à obtenir x, la fonction g étant la fonction inverse de ftelle que: g(y) = (y * K-1 mod n) d3 K, y représentant un bloc de N bits du chiffré. La puissance p indique que l'on compose p fois les fonctions f et g de la manière suivante: fP(x) = f(f(f( f(x)) )). On applique donc de façon itérative la fonction f. Le nombre d'itérations proposé garantit la sécurité du protocole. Selon un autre mode de réalisation, lorsque les dispositifs Aj et Ak communiquent entre-eux le dispositif Aj découpe au préalable le message en q+l blocs de N bits et place les blocs dans deux registres . Un bloc xi d' un message est placé dans un premier registre, le bloc suivant Xi+1 est placé dans un deuxième registre Lorsque le dispositif Aj envoie un message, il opère un chiffrement sur ce message avec une fonction f de chiffrement de sorte que # E(xi, xi+1) = fp(xi,, xi+1) # avec f(xi, xi+1) = yi, yi+1 # où yi = xi+1 # yi+1 = xi# ((yi # K2) * K1 mod n) - le dispositif envoie les (q+l) y blocs au dispositif Ak. D(yi, yi+1) = gp(yi, yi+1) de manière à déchiffrer (yi, yi+1) et d'obtenir (xi, xi+1), la fonction g étant la fonction inverse de f, cette fonction étant définie par: g (Yi, yi+1) = xj, x,+1 où xi+1 = y et xi = yi+1# ((xi+1 # K2) * K1 mod n) = yi+1# ((yi # K2) * K1 mod n) - le dispositif Ak reconstituant ainsi le message. L' application inverse permettant le déchiffrement est exactement du même type que l'application directe. I1 est donc possible de construire un système de chiffrement symétrique en composant plusieurs fonctions f comme cidessus. Dans ce cas le nombre d'itérations sera choisi supérieur ou égal à huit afin de donner au schéma une sécurité équivalente à la première solution. Le protocole basé sur cette fonction permettant le chiffrement d'un bloc x et le déchiffrement d'un bloc y du chiffré sera le suivant: E(x) = f8(x) e K mod n = y, pour réaliser le chiffrement du bloc x, D(y) = g8(y) e K mod n = x, pour réaliser le déchiffrement du bloc y, avec g 1' inverse de f comme définie ci-dessus, y représentant un bloc de N bits du chiffré. Les fonctions de chiffrement décrites précédemment pourront être utilisées pour hacher des messages de longueur quelconque. Le hachage d'un message s'effectue en combinant les valeurs bloc à bloc chiffré pour ne conserver que la dernière valeur chiffrée qui représente la valeur hachée du message. La longueur N en bits du modulo, des clefs et des blocs à chiffrer ou à hacher sera de façon préférentielle, suivant les dispositifs mis en oeuvre, de 80 bits ou 160, 512, 640, 1024 ou plus. Le nombre utilisé comme modulo sera impair. De façon préférentielle également, on utilisera le nombre n = 2N -1. D'autres particularités et avantages de 1' invention apparaîtront plus clairement à partir de la description qui est faite à titre indicatif et nullement limitatif et en regard des dessinS sur lesquels La figure 1 représente un schéma de principe d' un dispositif mettant en oeuvre le procédé selon la présente invention. La figure 2 représente les données transmises entre un dispositif Aj et un autre dispositif Ak utilisant un circuit de traitement numérique selon 1' invention, pendant une phase de chiffrement/déchiffrement d'un message. Dans toute la suite de la description on prendra comme exemple de dispositif de traitement le cas de cartes à puce afin de simplifier P exposé. Selon l'invention proposée, chaque carte à puce se compose d'une unité de traitement CPU 11, d'une interface de communication 10, d' une mémoire vive (RAM) et/ou d'une mémoire non inscriptible (ROM) 14 et/ou d'une mémoire inscriptible (généralement ré inscriptible) (EPROM ou EEPROM) 15. Chaque carte peut effectuer le chiffrement et/ou le déchiffrement de messages suivant les procédures proposées. L'unité CPU 11 et/ou la mémoire ROM 14 de la carte à puce contiennent des programmes ou des ressources de calcul permettant d'effectuer rapidement des opérations arithmétiques sur les grands nombres et notamment des multiplications, calcul d'inverse et réductions modulaires. De façon connue, on peut prévoir de regrouper certaines de ces opérations (par exemple, la réduction modulaire peut-être directement intégrée dans la multiplication). De même que pour l'implémentation d' un algorithme tel que le DES, la mémoire RAM contient le bloc x sur N bits du message M que l'on doit chiffrer. La mémoire E(E)PROM 15 contient les clefs K, K1 et K2. L'unité CPU 11 commande de manière connue, via les bus d'adresse et de données 16, I'interface de communication 10, les opérations de lecture et d'écriture en mémoire 13, 14 et 15. Chaque carte à puce est protégée du monde extérieur par des protections physiques 17. Ces protections devraient être suffisantes pour empêcher toute entité non autorisée d'obtenir la clef secrète K. Les techniques les plus utilisées de nos jours en la matière sont l'intégration de la puce dans un module de sécurité et l'équipement des puces de dispositifs capables de détecter des variations de température, de lumière ainsi que des tensions et des fréquences d' horloge anormales. Des techniques de conception particulières telles que l'embrouillage de l'accès mémoire sont également utilisées. Un dispositif utilisant un module de sécurité possédant les mêmes fonctionnalités qu'une carte à puce pourra effectuer les opérations de chiffrement et de déchiffrement de la même manière. Dans le cadre général de l'invention proposée, la mise en oeuvre d'un algorithme de chiffrement symétrique utilisant des ressources normalement dévolues à des opérations de type cryptographie à clef publique est réalisée en opérant les traitements qui vont suivre et en échangeant entre la carte et le dispositif vérifieur qui selon 1' invention peut être une autre carte, au moins les signaux suivants: Au préalable le dispositif réalisant le chiffrement d'un message de longueur L découpe le message pour obtenir (q+l) blocs de N bits .Si L = (q * N + r) bits, avec r Il complète le (q+1) 1ème bloc avec des zéros de manière à avoir q+l blocs de N bits, puis il chiffre chaque bloc xi en effectuant le calcul suivant: E(xi) = f4(xi) # K mod n = yi avec: f(xj) = (x; # K) * K mod n K représentant la clef secrète sur N bits n un nombre impair de N bits d3 le ou exclusif et * la multiplication modulo n II envoie ensuite au dispositif réalisant le déchiffrement les (q+l) yi blocs du chiffré. Le dispositif réalisant le déchiffrement du message effectue le calcul suivant sur chaque bloc yi: D(yj) = g4(yj) d3 K mod n = xi, pour réaliser le déchiffrement du bloc yi, avec g(y) = (y * K-1 mod n) e K. Il reconstitue enfin le message M = x1 x2 ... x1+1 Une seconde variante de la présente invention a pour objet de proposer un deuxième mode de réalisation de chiffrement symétrique, utilisant des ressources normalement dévolues à la cryptographie à clef publique, travaillant sur deux registres de N bits contenant les blocs du message à chiffrer. Le dispositif réalisant le chiffrement d'un message de longueur L réalise un découpage comme cela a été décrit précédemment. Pour un message de longueur L = (q * N ; r) bits, avec r n complète le (q+l) ième bloc avec des zéros, puis il chiffre chaque bloc xl en effectuant le calcul suivant: E(xi, xi+1) = f8 (xi1, xi+1) avec : f(xi, xi+1) = yi, yi-1 où yi = xi+1 yi+1 = xi # ((yj (E3 K2) * K1 mod n) K1 et K2 représentant les clefs secrètes sur N bits n un nombre impair de N bits # le ou exclusif et * la multiplication modulo n H envoie ensuite au dispositif réalisant le déchiffrement les (q+l) yi blocs du chiffré. Le dispositif réalisant le déchiffrement du message effectue le calcul suivant sur chaque bloc yi: D(yi, yi+1) = g8(yi, yi+1) avec : g(yi, yi+1) = xi, Xi+1 où xi+1 = yi xi = yi+1# ((xi+1 # K2) * K1 mod n) = yi+1# ((yi # K2) * K1 mod n) Il reconstitue enfin le message M = x1 x2 ... xq+1 A titre d' exemple pour mieux comprendre le traitement, dans le cas ou l'on procéderait à deux interations de la fonctin f, on aurait:: f2(xi, xi+1) = f( xi+1, xi # (( xi-1 # K2) * K1 mod n) =yi, yi+1 =( xi # (( xi+1 # K2) * K1 mod n, (xi+1 # ((yi # K2) * K1 mod n) Le procédé selon l'invention permet en outre de réaliser du hachage de messages, en vue par exemple de l'appliquer au calcul de signatures électroniques, ou à la mise en oeuvre de protocoles à clef secrète tels que définis ci dessus. n s'agit par exemple d'utiliser les deux fonctions de chiffrement des algorithmes précédemment décrit pour effectuer le hachage de messages de la façon suivante Selon une première variante: E(xi) = f4(xi) e K mod n Ol On calcule le chiffré y, du premier bloc x, du message : y, = E(xi) On effectue pour le reste des blocs xi du message le calcul suivant: yi = E(xi # yi+1) # yi+1 et on prend le dernier bloc comme valeur haché du message. Selon une seconde variante : E(xi, xi+1) = f8(xi,, xi+1) # On calcule le chiffré (y1, Y2) des deux premiers blocs (x1, x2) du message : y1, Y2 = E(x1,x1) # On effectue pour le reste des paires de blocs (xi, xi+1) du message le calcul suivant: yi, yi+1 = E(xi # yi-2, xi+1 # yi-1) # (yi-2, yi-1) et on prend le dernier bloc comme valeur hachée du message. Ainsi l'invention permet d'offrir des protocoles de chiffrement à clef secrète durcis grâce à l'introduction dans les dispositifs échangeant des messages de cicuits de traitement normalement dévolus à la cryptographie à clef publique. REVENDICATIONS 1. Procédé pour la mise en oeuvre d'un protocole à clef secrète entre deux dispositifs de traitement, I'un d'entre-eux aux moins étant un support de mémorisation portable, caractérisé en ce qu'il comprend les étapes suivantes: équiper les dispositifs d'un circuit de traitement numérique apte à réaliser des opérations de type calcul modulaire pour la mise en oeuvre d' opérations telles que la multiplication modulaire, . utiliser ce circuit de traitement pour mettre en oeuvre une fonction de chiffrement à clef secrète composée d'une succession d'opérations réversibles comportant au moins la combinaison de deux opérations, I'une de type calcul modulaire et l'autre relevant de la logique binaire, . appliquer cette fonction soit sur des messages destinés à êtres transmis pour les chiffrer ou les signer, soit sur des messages reçus pour les déchiffrer. 2. Procédé selon la revendication 1, caractérisé en ce que le circuit de traitement numérique réalise préalablement à tout traitement un découpage en x; blocs de N bits. 3. Procédé selon la revendication I ou 2, caractérisé en ce que la succession d'opérations comporte au moins une combinaison des deux opérations dont l'une est une permutation mettant en oeuvre une multiplication modulaire et l'autre une opération logique OU-exclusif, cette combinaison était définie par une fonction f de chiffrement à clef secrète telle que f(x) = (x # K2) * K1 mod n dans laquelle: x représentant un bloc de N bits du message Klet K2 représentent une première et une deuxième clef secrète sur N bits, n un nombre impair de N bits, # une opération ou exclusif, * une opération de multiplication modulo n. 4. Procédé selon la revendication 3, caractérisé en ce que lorsqu' un dispositif envoie des messages, il opère sur le message un premier traitement consistant à appliquer sur chaque bloc x; la fonction f de façon itérative. 5. Procédé selon la revendication 4, caractérisé en ce que, le nombre d'itération p est au moins égal à 4. 6. Procédé selon l'une quelconque des revendications I à 5, caractérisé en ce que les dispositifs Aj et At communiquent entre-eux selon le protocole suivant: au préalable le dispositif Aj découpe le message en (q+l) blocs de Nbits # le dispositif Aj chiffre chaque bloc x du message M de sorte le bloc chiffré y du message est tel que: E(x) = fP(x) d3 K mod n = y, p étant supérieur ou égal à 4, le dispositif envoie les (q+l) y blocs au dispositif Ab # le dispositif Ak effectue sur chaque y l'opération suivante:: D(y) = gP(y) # K mod n = x, pour réaliser le déchiffrement du bloc y, de manière à déchiffrer y et à obtenir x, la fonction g étant la fonction inverse de f telle que g(y) = (y * K-1 mod n) # K, y représentant un bloc de N bits du chiffré 7.Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que le message est découpé en (q+l) blocs de Nbits, en ce qu'un bloc xi d'un message est placé dans un premier registre, le bloc suivant xj,l est placé dans un deuxième registre et en ce que le dispositif envoie des messages chiffrés après avoir opéré le traitement consistant à appliquer une fonction f telle que E(xi, xi+1) = fp(xi,, xi+1) avec f(xi, xi+l) = Y, yi+1 où yi = xi+1 yi+1 = xi# ((yi # K2) * K1 mod n) le dispositif envoie les (q+l) y blocs au dispositifAk. le dispositif Ak effectue sur chaque bloc yi l'opération suivante : D(yi, yi+1) = gp(yi, yi+1) de manière à déchiffrer (yj, yi+1) et d'obtenir (xj, xi+1), la fonction g étant la fonction inverse de f, cette fonction étant définie par: g(yi, yi+1) = xi, xi+1 ou xi+ =Yi xi = yi+1# ((xi+1, # K2) * K1 mod n) = yi+1 # ((yi # K2) * K1 mod n) le dispositif Ak reconstituant ainsi le message. 8. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le circuit de traitement est utilisé pour réaliser du hachage de message et en ce qu' alors lorsqu' un dispositif Aj hache un message M de longueur L, le circuit réalise les étapes suivante : E(xj) = f4(xi) # K mod n # On calcule le chiffre y1 du premier bloc xl du message : y1 = E(x1) # On effectue pour le reste des blocs x du message le calcul suivant: y = E(xi # yi+1) e yi-l et on prend le dernier bloc comme valeur haché du message. 9. Procédé selon I'une quelconque des revendications 1 à 8, caractérisé en ce que le circuit de traitement est utilisé pour réaliser du hachage de message et en ce qu' alors lorsque un dispositif Aj hache un message M de longueur L, le circuit réalise les étapes suivantes E(xi, xi+1) = f8(xi, xi+1) # On calcule le chiffré (y1, Y2) des deux premiers blocs (x1, x2) du message : y1, y2 = E(x1,x1). # On effectue pour le reste des paires de blocs (x;, xi+1) du message le calcul suivant: yi, yi+1 = E(xi # yi-2, xi+1 # yi+1) # (yi-2, yi-1) et on prend le dernier bloc comme valeur haché du message. 10. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le calcul modulaire porte sur un grand nombre. 11. Procédé selon l'une quelconque des revendications précédentes caractérisé en ce que les appareils {A,} sont des cartes à puce.