WO2010026318A1

WO2010026318A1 - Procede cryptographique de generation d'une clef publique

Info

Publication number: WO2010026318A1
Application number: PCT/FR2009/001072
Authority: WO
Inventors: Thierry Berger; Philippe Gaborit
Original assignee: Centre National De La Recherche Scientifique -Cnrs-
Priority date: 2008-09-08
Filing date: 2009-09-08
Publication date: 2010-03-11
Also published as: FR2935859A1; FR2935859B1

Abstract

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 : une étape de création d'une matrice génératrice M provenant de l'application d'une matrice de permutation par bloc P_n et d'une matrice diagonale D_Λ à une matrice quasi-cyclique M_kcorrespondant à un code initial, une étape de 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.

Description

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 œuvre 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 œuvre 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 P_n et d'une matrice diagonale D_Λ à une matrice quasi-cyclique M_k 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 ; - la matrice diagonale D_Λ = Λ x I_n, avec Λ un nombre scalaire et I_n une matrice identité, de sorte que les éléments de la diagonale de D_Λ correspondent aux coordonnées de Λ ;

- la matrice de permutation P_n est définie par P_n=P_r® l_s> avec P_r correspondant à une matrice de permutation classique sélectionnée aléatoirement et l_s à une matrice identité ;

- la permutation permet d'obtenir un code de Reed-Solomon généralisé ;

- l'application de la matrice de permutation P_n à 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 œuvre 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 œuvre 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 Télécommunications 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 œuvre 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 œuvre 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 œuvre par les moyens de traitement du serveur sont aptes à déterminer cette matrice M à partir de l'équation suivante :

M= M_kxP_nx D_Λ

avec M_k se rapportant à une matrice génératrice d'un code de Reed-Solomon ordonné de manière à être quasi-cyclique, P_n correspondant à une matrice de permutation par bloc et D_Λ à une matrice diagonale. [0033] La mise en œuvre 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 œuvre 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 α (une racine primitive) tel que GF (q)= {0, 1 , α, a , .., α^q~2} et tel que en plus des opérations de multiplications et d'addition, tout élément de ce corps 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)ⁿ 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 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 par: si i = as + b, 0 ≤ a<r, 0 ≤ b<s, alors σ_s(i)= as +(b + 1 mod s).

[0041] Les codes alternants quasi-cycliques se construisent à partir des codes de Reed-Solomon généralisés quasi-cyclique qui font l'objet de multiplication colonne par colonne par des constantes adéquates pour obtenir des codes alternants quasi-cycliques.

[0042] Ces codes de Reed-Solomon généralisés quasi-cyclique sont invariants par la permutation σ_s.

[0043] Les moyens de traitement du serveur réalisent la construction de la matrice génératrice d'un code Reed-Solomon M_k. Cette construction correspond à des calculs permettant d'ordonner le code de Reed-Solomon de sorte à ce qu'il soit quasi-cyclique.

[0044] À la figure 1 , un exemple de cette matrice génératrice M_k est représenté. Cette matrice M_k est construite à partir d'une unité K. Cette unité K=GF(2^m), et n=2^m-1.

Avec α une racine primitive n-ième de l'unité dans K. Pour i variant de 0 à n - 1 on pose a,= cT^+u où i=us+v est la division Euclidienne de i par s.

En d'autres termes, si β = α^r, alors (aθ,a1 ,...,an-1 ) = (1 , β, β ,...,β^{s "1}, α, αβ, . . . , _ s-1 r-1 r-1 _ r-1 _s-1 , αβ , α ,α β α β )

[0045] Une fois cette matrice M_k construite, les moyens de traitement de ce serveur vont effectuer des opérations sur cette matrice M_k de sorte à obtenir la matrice M génératrice de code Reed-Salomon généralisé quasi-cyclique.

[0046] Ces opérations vont consister à appliquer une matrice de permutation par bloc P_n et une matrice D_Λ à cette matrice M_k.

[0047] La matrice de permutation P_n est déterminée par une permutation π D Sym(r) agissant sur les r blocs de taille s.

P_r est une matrice r x r correspondant à cette permutation avec le chiffre 1 par ligne et par colonne.

A partir de P_r, est construit une matrice de permutation P_n par blocs de taille n x n définie par P_n = P_r D l_s, où Is est la matrice identité de taille sxs. Ceci signifie que l'on construit P_n à partir de P_r en remplaçant les entrées nulles par la matrice carrée nulle de taille s x s et les entrées à 1 par I₅.

[0048] La matrice diagonale D_Λ est déterminé en choisissant de manière aléatoire r - 1 éléments non nuls A₁, ..., X^₁ de K. Avec β = α . On construit le n- uplet Λ = (1

(βⁱ ,β²ⁱ ,...,β^si)l ... lλr-1 (β^t ,β^2j,...,β^sj)) D K^r . On associe à Λ la matrice diagonale D_Λ =Λl_n dont les éléments de la diagonale sont les coordonnées de Λ.

[0049] Cette matrice diagonale est composée de s blocs et de r scalaires non nuls avec un même scalaire non nul pour chaque bloc.

[0050] Ainsi en partant d'une version cyclique du code Reed-Solomon et en multipliant les colonnes de ce code par des scalaires particuliers, reliés entre eux de telle sorte que les codes obtenus ne soient plus tous les codes Reed-Solomon généralisés mais une sous-famille de codes quasi-cyclique dérivés des Reed- Solomon généralisés, contrairement à ce qui est fait en générale et qui consiste à multiplier les colonnes du code Reed-Solomon par des éléments non nuls quelconques et d'obtenir les codes Reed-Solomon Généralisés classiques

[0051] Dès lors, sur la base de cette famille de codes quasi-cycliques dérivés du code Reed-Solomon, on prend alors les sous-codes sur le sous-corps comme on fait avec les codes alternants, mais comme les codes dont on part sont quasi- cyclique, les codes obtenus sur le sous-corps sont aussi quasi-cycliques et sont décodables en tant que codes alternants.

[0052] En outre, une spécificité de l'invention consiste en l'utilisation des codes sur des sous-corps intermédiaires du corps lié au code Reed-Solomon, contrairement aux systèmes classiques consistant en ce que des codes alternants sont construits à partir du Reed-Solomon Généralisés en prenant pour sous-corps le corps de base. À partir de ces codes, l'invention met en œuvre des techniques classiques de poinçonnage et de raccourcissement de codes tout en respectant la quasi-cyclicité des codes.

[0053] La considération du sous-code sur le sous corps est bien connue dans le domaine des codes correcteurs d'erreurs et notamment dans les publications de J.F MAC WILLIAMS et N.J.A SLOANE dans l'ouvrage intitulé « The theory of error correcting codes », de J.F. MacWilliams et NJA Sloane, North-Holland eds.

[0054] On entend par poinçonnage en plusieurs colonnes de ladite matrice génératrice M une suppression d'au moins une colonne de cette matrice M.

[0055] Dans un exemple si la matrice M correspond à :

après un poinçonnage de la dernière colonne, on obtient la matrice M' poinçonnée suivante :

M ^M' = f ' ⁰1 ¹1 ⁰1 0¹ [0056] La sélection d'un sous-code sur le sous corps correspond à une opération s'effectuant de la manière suivante, en prenant par exemple un code C de dimension n-k sur une extension. Cette extension correspond à un corps GF(4).

[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,w²} on prend par exemple la base à deux éléments sur GF(4) de GF(2): 1 et w.dans cette base:

- 0= 0.1 + O.w soit coordonnées (0,0) ;

- 1= 1.1 + 1.w soit (1 ,0) ;

- w= 0.1 + 1.w soit (0,1) ;

- w²=1+w= 1.1+1.w soit (1 ,1).

[0060] Concrètement sur un exemple, soit un code sur GF(4) de matrice duale

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) :

[0061] Ainsi le premier élément 1 de H est transformé en 1 , puis w en 0, et w2 en 1 , ainsi de suite.

[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 quasi- cyclicité 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 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.

[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 œuvre à 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 l'invention sans pour autant sortir du cadre du brevet.

Claims

REVENDICATIONS

1. 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 P_n et d'une matrice diagonale D_Λ à une matrice quasi-cyclique M_k 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 D_Λ = Λ x I_n, avec Λ un nombre scalaire et I_n une matrice identité, de sorte que les éléments de la diagonale de D_Λ correspondent aux coordonnées de Λ.

4. Procédé selon l'une quelconque des revendications précédentes, dans lequel la matrice de permutation P_n est définie par P_n=P_r ® l_s, avec P_r correspondant à une matrice de permutation classique sélectionnée aléatoirement et l_s à 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é.

6. Procédé selon l'une quelconque des revendications précédentes, dans lequel l'application de la matrice de permutation P_n à 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 œuvre le procédé selon l'une quelconques des revendications 1 à 8.