Brevet FR2935859A1 — publié le 20100312

PROCEDE CRYPTOGRAPHIQUE DE GENERATION D'UNE CLEF PUBLIQUE DOMAINE TECHNIQUE DE L'INVENTION [0001] L'invention se rapporte à un procédé cryptographique de génération d'une clef publique utilisant des codes correcteurs d'erreurs. [0002] L'invention se rapporte au domaine du chiffrement et du déchiffrement de données, ainsi qu'à celui de l'échange de clefs et des mécanismes d'authentification et de transfert de données et de génération de clef publique. ETAT DE LA TECHNIQUE ANTERIEURE [0003] Dans le cadre d'échanges de données entre deux entités, comme par exemple deux ordinateurs, il est nécessaire de pouvoir protéger le contenu des données échangées. [0004] Cette protection se traduit par une intégrité et une confidentialité des échanges mais aussi par une authentification des différentes parties prenant part à ces échanges afin qu'il ne soit pas possible d'un point de vue matériel ou algorithmique par des méthodes de cryptanalyse de pouvoir déterminer le contenu d'un échange de message entre des parties. [0005] Dans l'art antérieur, il est commun d'utiliser des procédés cryptographiques reposant sur des algorithmes asymétriques à clé publique tels que Rivest Shamir Adleman (RSA) ou encore des méthodes mathématiques basées sur des courbes elliptiques ou des logarithmes discrets. [0006] De tels procédés ont pour inconvénients de nécessiter des dispositifs comportant des ressources matérielles conséquentes en terme de capacité de traitement de données, par des moyens de mémoire et des processeurs pour la réalisation de calculs, et notamment pour des calculs portant sur des entiers très grands tels que des calculs d'exponentielles dans le cas de RSA. [0007] Ces procédés ne peuvent être implémentés dans des équipements électroniques ayant souvent de multiples fonctionnalités et comportant par exemple des cartes à puces ou des puces RFID, car leur capacité limité en terme de ressources matérielles offre des temps de calculs lents et donc des résultats ne pouvant pas être exploités dans des mécanismes sécurisés d'authentification et de transfert de données. [0008] Pourtant, l'augmentation croissante du taux de pénétration au sein des foyers de tels équipements électroniques fait naître un besoin grandissant d'implémentation dans de tels équipements, de procédé de cryptographie. [0009] Pour pallier ces inconvénients, il est connu dans le domaine de la cryptographie d'utiliser des procédés cryptographiques d'authentification ayant des temps de calculs plus rapides que RSA, en mettant en oeuvre des mécanismes de décodages utilisant des codes correcteur d'erreurs. [0010] On connaît dans l'art antérieur, le document FR0704518 qui décrit des procédés d'authentification utilisant un décodage de code d'erreurs à partir d'une matrice publique et de matrices aléatoires. [0011] De tels procédés cryptographiques sont connus depuis de nombreuses années, et ont été implémentés, en particulier, dans des systèmes dits de Mc Eliece et de Niederreiter. Ces procédés constituent une alternative intéressante par rapport aux autres procédés cryptographiques tels que RSA, El Gamal ou encore ceux qui se rapportent aux courbes elliptiques. Le temps de calcul de ces procédés cryptographiques est en moyenne cent fois plus rapide que celui des autres procédés. [0012] Toutefois, un inconvénient majeur de ces procédés est d'utiliser une clef publique de grande taille, plusieurs centaines de milliers de bits contre simplement quelques milliers de bits pour les autres procédés (comme par exemple RSA). Une telle taille ne permet pas le stockage de cette clef publique dans les moyens de mémoire limités d'équipements électroniques, dont les ressources matérielles se rapportent, par exemple, à une carte à puce ou une puce RFID. [0013] Ce problème lié à la taille de la clef publique a limité le développement industriel de ces procédés, car les supports usuellement utilisés ont des capacités de calcul et de mémoire limitées. EXPOSE DE L'INVENTION [0014] La présente invention vise à résoudre le problème lié aux difficultés techniques rencontrées pour la mise en oeuvre d'un procédé cryptographique dans un équipement électronique à bas coût comportant des ressources matérielles ayant des capacités limités tant en termes de calcul que de stockage. [0015] L'invention propose d'améliorer les procédés cryptographiques en utilisant des codes quasi-cycliques alternants, qui permettent de réduire la taille d'une clef publique, à quelques milliers de bits. [0016] Ces codes quasi-cycliques alternants constituent une classe particulière des codes de contrôle d'erreurs générés par une matrice obtenue par un mécanisme de permutation appliqué à une matrice quasi-cyclique. [0017] Pour ce faire, un premier aspect de l'invention se rapporte à un procédé cryptographique de génération d'une clef publique apte à chiffrer des données numérique, dans lequel la clef publique correspond à un code quasi-cyclique alternant, caractérisé en ce que ledit procédé comprend les étapes suivantes : -création d'une matrice génératrice M provenant de l'application d'une matrice de permutation par bloc Pn et d'une matrice diagonale DA à une matrice quasi-cyclique Mk correspondant à un code initial, et -génération d'une matrice relative audit code quasi-cyclique alternant à partir d'un poinçonnage en plusieurs colonnes de ladite matrice génératrice M et d'une sélection d'un sous-code sur le sous corps dans cette dite matrice génératrice. Selon des modes de réalisation particuliers: - le code initial est un code Reed-Solomon généralisé quasi-cyclique ; 25 - la matrice diagonale DA = A x In, avec A un nombre scalaire et ln une matrice identité, de sorte que les éléments de la diagonale de DA correspondent aux coordonnées de A ; - la matrice de permutation Pn est définie par Pn=Pr O Is, avec Pr correspondant à une matrice de permutation classique sélectionnée aléatoirement et Is à une matrice identité ; - la permutation permet d'obtenir un code de Reed-Solomon généralisé ; - l'application de la matrice de permutation Pn à la matrice quasi-cyclique de masquage du code initial ; - la matrice génératrice M est utilisée dans le protocole de Mc Eliece, et - la matrice génératrice M est utilisée dans le protocole de Niederreiter. [0018] L'invention se rapporte aussi à un dispositif cryptographique de génération d'une clef publique comprenant des moyens de traitement agencés de sorte à mettre en oeuvre le procédé tel que précédemment décrit. BREVE DESCRIPTION DES FIGURES [0019] D'autres caractéristiques et avantages de l'invention ressortiront à la lecture de la description qui suit, en référence aux figures annexées, qui illustrent : la figure 1, une matrice génératrice d'un code de Reed-Solomon à utiliser dans un procédé d'authentification selon un mode de réalisation de l'invention. DESCRIPTION DETAILLEE D'UN MODE DE REALISATION [0020] Dans un exemple de réalisation, le procédé selon l'invention est mis en oeuvre dans une architecture réseau de communication. [0021] Ce réseau se rapporte à des moyens de câblage et/ou des moyens de transmission électromagnétique. Sans prétendre faire une liste exhaustive, ces moyens de câblage correspondent par exemple à de la fibre optique ou des câbles cuivrés, et les moyens de transmission électromagnétique se rapportent par exemple à des liaisons radioélectrique reposant sur des normes de téléphonie mobile comme le GSM (acronyme de Global System for Mobile Communications), UMTS (acronyme de Universal Mobile Telecommunications System), EDGE (acronyme de Enhanced Data Rates for GSM Evolution) ou encore HSDPA (acronyme de High-Speed Downlink Packet Access). Ces moyens peuvent aussi se rapporter à des technologies telles que le WIFI défini par les normes IEEE 802,11, ou le Bluetooth défini par les normes IEEE 802.15, ou encore au WIMAX (acronyme pour Worldwide Interoperability for Microwave Access) défini par la norme IEEE 802.13. [0022] Dans cette architecture, différents équipements échangent des données et en particulier des messages dans un cadre sécurisé. [0023] La sécurité des transactions est un critère important dans un environnement d'échanges de données. Elle implique la mise en oeuvre d'une politique de sécurité permettant de disposer d'un service d'authentification de l'origine des données mais aussi d'intégrité des données échangées. Les échanges de données pourront alors s'effectuer en étant protégés d'actes de piratages ou de corruption volontaire lors de leur transmission. [0024] L'échange de données dans le cadre de l'invention est réalisé entre des terminaux mobiles ou fixes tels que par exemple des ordinateurs fixes ou portables, des téléphones mobiles, des PDAs ou encore des smartphones. [0025] Dans ce système, les données échangées telles que des messages font l'objet d'un chiffrement asymétrique. Ce chiffrement asymétrique nécessite que l'utilisateur envoyant le message soit en possession d'une clef publique afin de chiffrer le contenu de ce message. [0026] Cette clef publique peut être stockée dans les moyens de mémoire du terminal ou encore dans un support de données amovible tel que par exemple : - une carte à puce, une carte magnétique, ou - une carte comprenant une puce RFID (acronyme de radio frequency identification qui se traduit en français par radio-identification). [0027] De tels supports de données sont pourvus de ressources matérielles limitées qui ne permettent pas la réalisation de traitements lourds de données. [0028] Ainsi, un terminal A peut envoyer à un terminal B un message codé, à partir de cette clef publique stocké dans un des supports de données mentionnés précédemment, que seul le terminal B pourra décoder à partir d'une clef privée. [0029] Cette clef publique est générée par un serveur comprenant des moyens de transmission et un lecteur/enregistreur aptes à transférer dans un support de données la clef publique générée, à partir par de commandes système d'entrée/sortie envoyées au lecteur/enregistreur. [0030] Ce serveur comprend aussi des moyens de traitement tel qu'un processeur associé à des moyens de mémoire volatile et/ou nom volatile qui sont aptes à mettre en oeuvre des algorithmes et des programmes informatique pour la génération d'une clef publique. [0031] Cette clef publique est générée à partir d'un code de matrice génératrice M correspondant à un code Reed-Solomon généralisé quasi-cyclique. [0032] Le programme informatique mis en oeuvre par les moyens de traitement du serveur sont aptes à déterminer cette matrice M à partir de l'équation suivante : M. MkXPnX DA avec Mk se rapportant à une matrice génératrice d'un code de Reed-Solomon ordonné de manière à être quasi-cyclique, Pn correspondant à une matrice de permutation par bloc et DA à une matrice diagonale. [0033] La mise en oeuvre de la matrice génératrice M permet de construire des codes alternants quasi-cycliques correspondant à la clef publique. [0034] Généralement les codes utilisés pour la génération de clefs publiques se rapportent aux codes correcteur utilisés pour corriger des erreurs aléatoires comme par exemple les codes de Goppa, BCH (signifiant Bose, Ray-Chaudhuri, Hocquenghem) ou encore Reed-Muller. [0035] Ces codes alternants quasi-cycliques sont une sous-classe de la classe des codes alternants. [0036] Plus précisément, un code quasi-cyclique est défini comme étant un code qui est stable par permutation par bloc. [0037] En prenant, x un vecteur du code que l'on sépare en r blocs de s colonnes consécutives alors le décalage de s colonnes de x est toujours un mot du code. On entend par mot les éléments d'un code. [0038] Ces codes ont l'avantage technique d'avoir une description beaucoup plus compacte puisque pour décrire la matrice d'un code, la donnée d'une ligne permet implicitement d'en construire en tout r grâce à la permutation. Cette permutation est dite quasi-cyclique, d'où le nom de ces codes. Dans ce mode de réalisation, les moyens de traitement au travers du programme informatique réalisent notamment des calculs sur la base de mots de codes mis en oeuvre par les moyens de traitement du serveur ont une longueur n et sont indicés par I = {0,...,n û 1}, ainsi qu'à partir d'un corps GF(q) à q éléments. Ce corps GF (q) à q éléments est une structure mathématique telle qu'il existe un élément a (une racine primitive) tel que GF (q)= {0, 1, a, a2, .., a' 2} et tel que en plus des opérations de multiplications et d'addition, tout élément de ce corps 25 admet un inverse. Un code de longueur n, de dimension k et de distance minimale d noté [n, k, d] sur le corps à q éléments GF (q) est un sous-espace vectoriel de dimension k de GF (q)n avec d le nombre minimal de coordonnées non nulles pour un élément non nul du code. [0039] Rappelons qu'un code est dit cyclique si le code est stable sous l'action des permutations cycliques, c'est-à-dire si toute permutation cyclique d'un mot du 5 code est aussi un mot du code. [0040] Un code est dit quasi-cyclique d'indice r si toute permutation cyclique d'un mot du code de r positions est toujours un mot du code ou encore s'il est stable sous l'action d'une permutation quasi-cyclique définie par: n = rs, une permutation n quasi-cyclique d'indice r et d'ordre s sur I est définie 10 par: si i = as + b, 0 a [0057] Le corps GF(4) est une extension du corps binaire GF(2). On créé la matrice du dual D de dimension k du code C. [0058] Cette matrice du dual D est inscrite dans la base du sous-corps, pour obtenir un code de dimension d.k avec d le degré de l'extension dans le cas GF(4) sur GF(2) le degré de l'extension est 2 sur le sous-corps, on obtient ainsi alors en prenant le dual, le sous-code sur le sous-corps. [0059] Par exemple on considère le corps à quatre éléments GF(4): {0,1,w,w2} on prend par exemple la base à deux éléments sur GF(4) de GF(2): 1 et w,dans cette base: 0= 0.1 + 0.w soit coordonnées (0,0) ; 1= 1.1 + 1.w soit (1,0) ; w= 0.1 + 1.w soit (0,1) ; w2=1+w= 1.1+1.w soit (1,1). [0060] Concrètement sur un exemple, soit un code sur GF(4) de matrice duale H: r H= 1 w w2 w 0 J 0 w2 w 1 w on prend l'image de H sur le sous-corps en utilisant la décomposition précédente et on obtient une nouvelle matrice H' sur GF(2) :25 10100 01 1 1 0 0 1 0 1 0 01101 J [0061] Ainsi le premier élément 1 de H est transformé en 1, puis w en 0, et w2 en 1, ainsi de suite. 10 [0062] Le sous-code sur le sous corps de C est alors la matrice duale de H'. [0063] Ainsi, l'utilisation de tels codes et notamment de leur propriété de quasicyclicité permet de diminuer la taille des clés de plusieurs centaines de kilobits à quelques kilobits (typiquement 6000 bits) ouvrant ainsi la porte aux applications industrielles des cryptosystèmes basés sur les codes, en particulier pour les 15 applications dans le domaine des cartes à puces et des étiquettes RFID. [0064] De plus, l'invention permet d'intégrer de la haute sécurité dans des dispositifs à très faibles ressources, et fournit une alternative aux mécanismes de sécurité actuels notamment dans le cas où la solidité de ces derniers viendrait à être compromise. 20 [0065] Le procédé de génération d'une clef publique utilisant une matrice génératrice pour la création de code quasi-cyclique alternant est susceptible d'être mis en oeuvre à l'aide du protocole de chiffrement de Mc Eliece ou de Niederreiter. [0066] L'invention est décrite dans ce qui précède à titre d'exemple. Il est entendu que l'homme du métier est à même de réaliser différentes variantes de 25 l'invention sans pour autant sortir du cadre du brevet. H' =5 REVENDICATIONS1. Procédé cryptographique de génération d'une clef publique apte à chiffrée des données numérique, dans lequel la clef publique correspond à un code quasi-cyclique alternant, caractérisé en ce que ledit procédé comprend les étapes suivantes : -création d'une matrice génératrice M provenant de l'application d'une matrice de permutation par bloc Pn et d'une matrice diagonale DA à une matrice quasi-cyclique Mk correspondant à un code initial, -génération d'une matrice relative audit code quasi-cyclique alternant à partir d'un poinçonnage en plusieurs colonnes de ladite matrice génératrice M et d'une sélection d'un sous-code sur le sous corps dans cette dite matrice génératrice. 2. Procédé selon la revendication 1, dans lequel ledit code initial est un code Reed-Solomon généralisé quasi-cyclique. 3. Procédé selon l'une quelconque des revendications 1 et 2, dans lequel ladite matrice diagonale DA = A x In, avec A un nombre scalaire et ln une matrice identité, de sorte que les éléments de la diagonale de DA correspondent aux coordonnées de A. 4. Procédé selon l'une quelconque des revendications précédentes, dans lequel la matrice de permutation Pn est définie par Pn=Pr O Is, avec Pr correspondant à une matrice de permutation classique sélectionnée aléatoirement et Is à une matrice identité. 5. Procédé selon la revendication 2, dans lequel ladite permutation permet d'obtenir un code de Reed-Solomon généralisé. 10 6. Procédé selon l'une quelconque des revendications précédentes, dans lequel l'application de la matrice de permutation Pn à la matrice quasi-cyclique de masquage du code initial. 7. Procédé selon l'une quelconque des revendications précédentes, dans lequel la matrice génératrice M est utilisée dans le protocole de Mc Eliece. 8. Procédé selon l'une quelconque des revendications précédentes, dans lequel la matrice génératrice M est utilisée dans le protocole de Niederreiter. 9. Dispositif cryptographique de génération d'une clef publique comprenant des moyens de traitement agencés de sorte à mettre en oeuvre le procédé selon l'une quelconques des revendications 1 à 8.