Brevet FR2956541A1 — publié le 20110819

Procédé cryptographique de communication d'une information confidentielle Domaine technique L'invention concerne le domaine de la communication cryptographique d'une information confidentielle entre une première entité A et une deuxième entité B. Plus particulièrement, l'invention concerne le domaine de la communication cryptographique d'une information confidentielle pouvant être réalisée sur un dispositifs cryptographiques à bas coût possédant des capacités de calcul limité, notamment des cartes à puce ou des étiquettes radio fréquence. Selon un premier aspect l'invention concerne un procédé cryptographique de communication d'une information confidentielle entre une première entité et une deuxième entité. Selon un autre aspect, l'invention concerne un programme d'ordinateur comprenant une pluralité d'instructions pour la mise en oeuvre, à l'exécution, du procédé selon l'invention, un dispositif cryptographique comprenant des moyens de calculs agencés pour mettre en oeuvre le procédé selon l'invention ainsi qu'un support de données comprenant un tel dispositif cryptographique. Présentation de l'état de la technique et du problème technique II existe deux types d'approches pour le codage cryptographique. Une première approche très répandue est basée sur l'algorithme RSA, de River, Shamir et Adleman, dont la sécurité réside dans la difficulté mathématique pour factoriser de grands nombres entiers. Toutefois, un tel procédé cryptographique présente plusieurs inconvénients. En particulier, dans 30 l'algorithme RSA, il est nécessaire de procéder à des calculs sur des clés publiques de grandes tailles, et notamment des calculs d'exponentielles discrètes. De tels calculs peuvent être lents, tout particulièrement lorsqu'ils sont implémentés sur des dispositifs cryptographiques à bas coût possédant des capacités de calcul limitées, tels que sur les cartes à puce ou les étiquettes radio fréquence. 35 Parmi les alternatives aux procédés cryptographiques d'authentification basés sur l'algorithme RSA, sont connus les procédés cryptographiques d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique. Ces procédés ont l'avantage d'être la source de problèmes mathématiques NP-complets donc très difficiles à résoudre. Dès lors, ces procédés sont 40 très sécurisés. 20 25 L'utilisation des codes correcteurs d'erreurs en cryptographie est connue depuis les années 1980. La demande EP-A-O 661 846 décrit un tel procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique. Cette demande, ainsi que la publication du demandeur de cette demande, "A new identification scheme based on syndrome decoding", J. Stern 1993, décrivent un protocole d'authentification dit protocole par syndrome de Stern, utilisant une matrice publique aléatoire de très grande taille, typiquement de l'ordre de cent à mille kilobits. De même, la publication "Improved Identification schemes based on error-correcting codes", Veron, Applicable Alegbra in Engineering , Communication and Computing, 1 997, décrit une variante du protocole par syndrome, toujours dans le cadre d'un procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique. Toutefois, les contraintes de stockage des dispositifs cryptographiques à bas coûts ne permettent pas d'implémenter un tel protocole. D'autres procédés de cryptographie connus de l'homme du métier sont basés sur le protocole Diffie-Hellman qui a servi de fondation à l'élaboration de nombreux développements concernant la cryptographie moderne. 20 Ce protocole a été décrit pour la première fois dans la publication « New Directions in Cryptography W. Diffie and M. E. Hellman, IEEE Transactions on Information Theory, vol. IT-22, Nov. 1976 » et consiste en ce que Alice et Bob partage une information confidentielle exp(ab) après avoir échangé une première information exp(a) et une seconde information exp(b), tels que a et b correspondent à des nombres entiers secrets et exp() à une fonction exponentielle dans le groupe G. La sécurité de ce 25 protocole découle de la difficulté qui existe à inverser la fonction exponentielle de façon efficace et plus particulièrement de la difficulté qui existe à résoudre le problème exp(ab) à partir de exp(a) et exp(b). Le protocole Diffie-hellman est utilisé dans de nombreuses applications mais présente un coût non 30 négligeable puisque la résolution de problèmes exponentiels est, d'un point de vue algorithmique, l'une des fonctions arithmétiques les plus complexe. Ceux qui ont essayé de limiter ce coût en remplaçant la fonction exponentielle par d'autres fonctions ont rencontré de nombreuses difficultés et n'ont d'ailleurs jamais pu identifier une solution qui soit à la fois peu coûteuse en calculs et suffisamment sécurisée. 35 II est également connu d'un domaine technique différent des solutions de cryptographie quantique ayant permis de résoudre des problèmes d'échange de clés confidentielles. Le protocole de communication quantique permet à Alice d'être en possession d'une variable aléatoire X et à Bob 40 d'être en possession d'une version bruitée Y de la variable aléatoire X.15 Ainsi, grâce à l'utilisation de protocoles de communication classiques Bob peut, lors d'une phase de réconciliation, écarter le bruit de la version bruitée Y de la variable aléatoire X et en déduire une information confidentielle. L'information confidentielle est ainsi partagée par Alice et Bob de façon inconditionnelle. Ce protocole de communication quantique est donc avantageux puisqu'il permet d'échanger une information confidentielle en ayant la certitude que celle-ci ne sera pas interceptée. Mais il présente l'inconvénient majeur de nécessiter l'utilisation d'un tunnel quantique entre Alice et Bob, ce qui est extrêmement contraignant d'un point de vue pratique. II existe donc un besoin non satisfait dans le domaine de la cryptographie pour la réalisation d'un protocole de communication qui permette d'échanger une information confidentielle sans être trop coûteux à la fois en terme de ressources et d'exécution, afin de pouvoir être intégré sur des dispositifs de cryptographie à bas coûts tels que des cartes à puce ou des puces d'identification radiofréquences (RFID) mais qui assure, néanmoins, un degré de sécurité qui soit suffisamment fiable et un temps de réponse suffisamment court. Exposé de l'invention L'invention vise donc à répondre à ces besoins non satisfaits. A cet effet, l'invention vise un procédé cryptographique de communication d'une information confidentielle m entre une première entité (A) électronique et une deuxième entité (B) électronique comportant une étape de distribution et une étape de réconciliation, l'étape de distribution comportant plusieurs étapes consistant en ce que : d'une part, la première entité (A) : o calcule un premier syndrome SA = XA + f(YA) à partir d'une première information secrète composée de deux éléments primaires XA et YA appartenant à un anneau R et présentant une norme sensiblement petite vis-à-vis d'un élément f(XA) ou f(YA), • l'anneau R possédant l'addition et la multiplication, et • f étant une loi de composition interne associant à tout élément X, de l'anneau R un autre élément f(XI) de l'anneau R, et possédant la propriété que pour toute paire d'éléments X, et Y, de R, tels que X, et Y, ont une petite norme vis-à-vis des éléments f(XI) et f(Y,), alors X,.f(Y,) - Y,.f(X,) est de petite norme, et o émet un premier message composé à partir de ce premier syndrome SA de sorte que ledit premier syndrome SA soit accessible par la deuxième entité (B), d'autre part, la deuxième entité (B) : o calcule un deuxième syndrome SB = XB + f(YB) à partir d'une deuxième information secrète composée de deux éléments secondaires XB et YB appartenant à l'anneau R et présentant une norme sensiblement petite vis-à-vis d'un élément f(XB) ou f(YB), o transmet à la première entité (A) un deuxième message composé à partir du deuxième syndrome SB de sorte que ledit deuxième syndrome SB soit accessible par la première entité (A), dans lequel lors de cette première étape de distribution, la première entité (A) et la deuxième 5 entité (B) calculent respectivement une première valeur intermédiaire PA et une deuxième valeur intermédiaire PB, telles que : o PA = YA.SB = YA.XB + YA.f(YB), et o PB = YB.SA = YB.XA + YB f(YA), o de sorte que, lors de l'étape de réconciliation, la première entité (A) soit capable de retrouver 10 l'information confidentielle par une opération de déchiffrement d'un message bruité composé par la deuxième entité (B) à partir, notamment, de la deuxième valeur intermédiaire PB. Selon une réalisation, le premier message émis par la première entité (A) est transmis directement à destination de la deuxième entité (B). Selon une réalisation, le message bruité composé par la deuxième entité (B) lors de la phase de réconciliation comprend une donnée C obtenue à partir notamment de la deuxième valeur intermédiaire PB et de l'information confidentielle m. 20 Selon une réalisation, la première entité (A) décode l'information confidentielle m à partir notamment du message bruité et de la première valeur intermédiaire PA. Selon une réalisation, l'information confidentielle m est encodée dans la donnée C du message bruité, par un code correcteur d'erreur. 25 Selon une réalisation, la donnée C du message bruité est telle que C = m.G + PB + e, avec : ^ m qui représente l'information confidentielle, ^ G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, et 30 e qui représente un vecteur d'erreurs aléatoires de longueur n et de norme petite, la première entité A et la deuxième entité B s'étant préalablement publiquement accordées sur la longueur n. Selon une réalisation, la donnée C du message bruité est telle que C = m.G + v[PB], avec : m qui représente l'information confidentielle, 35 G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, et v[] qui représente une opération consistant à extraire p coordonnées parmi les n coordonnées d'un vecteur, la première entité A et la deuxième entité B s'étant préalablement accordées sur la valeur du p. 40 Selon une réalisation, la donnée C du message bruité est telle que C = m.G + v[PB] + e, avec : 15 ^ m qui représente l'information confidentielle, ^ G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, v[] qui représente une opération consistant à extraire p coordonnées parmi les n coordonnées d'un vecteur, la première entité A et la deuxième entité B s'étant préalablement accordées sur la valeur du p, e qui représente un vecteur d'erreurs aléatoires de longueur n et de norme petite, la première entité A et la deuxième entité B s'étant préalablement publiquement accordées sur la longueur n. Selon une réalisation, la première entité (A) compose une clé de chiffrement soit à partir de l'information confidentielle m, soit à partir de la deuxième valeur intermédiaire PB, soit à partir d'une combinaison de l'information confidentielle et de la deuxième valeur intermédiaire PB. Selon une réalisation, après avoir émis le premier message composé à partir du premier syndrome SA, la première entité (A) met ce premier message à disposition de la deuxième entité (B) dans un espace publique accessible au moins à une autre entité électronique. Selon une réalisation, après avoir calculé le deusième syndrome SB, la deuxième entité (B) transmet, à la première entité (A) : ^ le deuxième message composé à partir du deuxième syndrome SB, et ^ le message bruité composé à partir d'une donnée C obtenue à partir de la deuxième valeur intermédiaire PB et de l'information confidentielle m. Selon une réalisation, la première entité A décode l'information confidentielle à partir de du deuxième message et du message bruité. Selon une réalisation, la première entité A décode l'information confidentielle m à partir de du deuxième syndrome SB composant le deuxième message, de la deuxième valeur intermédiaire PB composant le message bruité et de la première valeur intermédiaire PA. Selon une réalisation, l'information confidentielle m est encodée dans la donnée C du message bruité, par un code correcteur d'erreur. Selon une réalisation, la donnée C du message bruité est telle que C = m.G + PB + e, avec : 35 ^ m qui représente l'information confidentielle, ^ G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, et e qui représente un vecteur d'erreurs aléatoires de longueur n et de norme petite, la première entité A et la deuxième entité B s'étant préalablement publiquement accordées sur la longueur n. 40 Selon une réalisation, la donnée C du message bruité est telle que C = m.G + v[PB], avec :30 ^ m qui représente l'information confidentielle, ^ G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, et v[] qui représente une opération consistant à extraire p coordonnées parmi les n coordonnées d'un vecteur, la première entité A et la deuxième entité B s'étant préalablement accordées sur la valeur du p. Selon une réalisation, la donnée C du message bruité est telle que C = m.G + v[PB] + e, avec : m qui représente l'information confidentielle, G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, v[] qui représente une opération consistant à extraire p coordonnées parmi les n coordonnées d'un vecteur, la première entité A et la deuxième entité B s'étant préalablement accordées sur la valeur du p, e qui représente un vecteur d'erreurs aléatoires de longueur n et de norme petite, la première entité A et la deuxième entité B s'étant préalablement publiquement accordées sur la longueur n. Selon une réalisation, la première entité (A) compose message d'authentification soit à partir de l'information confidentielle m, soit à partir de la deuxième valeur intermédiaire PB, soit à partir d'une combinaison de l'information confidentielle m et de la deuxième valeur intermédiaire PB. Selon une réalisation, l'anneau R est l'anneau Fq[x] / (Xn - 1), c'est-à-dire l'ensemble des polynômes à coefficients dans le corps Fq à q éléments pour lesquels on considère le reste par la division du polynôme (Xn - 1). Selon une réalisation, l'anneau R est l'anneau Fq[x] / (Xn - 1), c'est-à-dire l'ensemble des polynômes à coefficients dans le corps Fq à q éléments pour lesquels on considère le reste par la division du polynôme (Xn - 1). 30 Selon une réalisation, la norme correspond à la distance de hamming. Selon une réalisation: ^ n est sensiblement égale à 6000, et ^ XA, XB, YA, YB présentent une norme égale à 35 35 de sorte que la norme de PA ù PB est sensiblement égale à 2400. Selon une réalisation, l'anneau R est l'anneau Z/pZ, c'est-à-dire l'ensemble des entiers modulo p moins le reste de la division par p. 40 Selon une réalisation, la norme est une norme euclidienne. Selon une réalisation: p est sensiblement égale à 2500, f(x)=h.x modulo p avec h un nombre aléatoire plus petit que p, et/ou XA, XB, YA, YB sont des éléments de R de norme plus petite que racine (p). Selon un autre aspect, l'invention concerne un programme d'ordinateur comprenant une pluralité d'instructions pour la mise en oeuvre, à l'exécution, du procédé selon l'une quelconque des réalisations 1 à 24. 10 Selon un autre aspect, l'invention concerne dispositif cryptographique comprenant des moyens de calculs agencés pour mettre en oeuvre le procédé selon l'une des réalisations 1 à 24. Selon un autre aspect, l'invention concerne support de données comprenant un dispositif cryptographique selon l'invention. Description des fiqures Des exemples détaillés de réalisation de l'invention sont décrits, ci-dessous, en références aux figures 20 annexées, dans lesquelles : - la figure 1 est une représentation schématique d'une première réalisation du procédé cryptographique selon l'invention par lequel une première entité et une deuxième entité s'échangent une clé de chiffrement ; - la figure 2 est une représentation schématique d'une deuxième réalisation du procédé cryptographique selon l'invention, par lequel une première entité communique un message chiffré à une deuxième entité ; et 30 - la figure 3 est une représentation schématique d'une troisième réalisation du procédé cryptographique selon l'invention, par lequel une première entité s'authentifie vis-à-vis d'une deuxième entité. II convient en premier lieu de souligner que dans le cadre de l'invention de terme de « message » 35 correspond à tout type de signal ou bloc d'information véhiculé au travers d'un support physique ou d'ondes radiofréquences. Ces messages sont, par exemple, formés par une trame de données constituée d'une succession de « 0 » et de « 1 » caractérisant au moins une information pouvant être déduite d'une opération appropriée. 40 D'autre part, un « anneau » R peut être entendu comme toute structure algébrique sur laquelle deux opérations satisfont certaines des propriétés de l'addition et la multiplication. A cet égard, l'invention 15 25 propose d'utiliser comme structure algébrique, un anneau (R, +, x) connu publiquement plutôt qu'un groupe tel que l'utilisait le protocole traditionnel de Diffie-Hellman. En outre, une « norme », ou distance, est une application sur l'anneau R à valeurs réelles positives et satisfaisant les hypothèses suivantes : séparation, homogénéité, sous additivité et sous multiplicative. Un premier mode de réalisation du procédé selon l'invention est décrit en référence à la figure 1. Selon cette première réalisation, le procédé cryptographique selon l'invention est utilisé pour réaliser un échange de clé de chiffrement permettant à une première entité A électronique, nommée Alice, et une deuxième entité B électronique, nommée Bob, d'échanger des informations confidentielles chiffrées. Pour lui permettre d'émettre, de recevoir et de stocker des données, Alice comporte une un processeur 2A, un espace mémoire 4A et une unité de communication 6A. De façon similaire, Bob comporte également un processeur 2B, un espace mémoire 4B et une unité de communication 6B. Une première étape du procédé correspond à une étape dite de distribution. Selon cette première étape, Alice et Bob s'échangent des données afin de se mettre d'accord sur un anneau R, un entier n et un élément h de l'anneau R. L'élément h est choisi de façon aléatoire et peut être considéré comme un équivalent du générateur utilisé dans le cadre de l'étape d'élévation de puissance du protocole de Diffie-Hellman. Selon un exemple de réalisation, l'anneau R sélectionné correspond à F2[x]/(Xn-1), c'est-à-dire l'ensemble des polynômes à coefficients dans le corps F2 à deux éléments pour lesquels on considère le reste par la division du polynôme (XI' -1). On utilise alors comme fonction norme la distance de hamming. II convient de souligner que, de façon alternative, il serait également possible de sélectionner d'autres couples d'anneau R et de norme, parmi lesquels : - l'anneau Z/pZ et la norme euclidienne ; - l'anneau (Z/pZ)[x]/(xn-1) et la norme euclidienne également ; et - l'anneau (Z/prZ)[X]/(xn-1) et pour norme le rang métrique. Dans ce mode de réalisation, il est possible d'utiliser un code binaire doublement circulant C [2n, n] comprenant une matrice de vérification de parité de la forme [InIH] où In est la matrice identité de taille n x n et h est telle que :35 Après avoir sélectionnés l'anneau R, le générateur h et l'entier n, Alice et Bob sélectionnent séparément et de façon secrète un couple d'éléments primaires XA, YA pour Alice et XB, YB pour Bob de sorte que ces éléments primaires XA, YA, XB et YB sont de petite norme, et présentent donc une petite distance de Hamming, par rapport à un nombre réel positif w. Par exemple, pour un anneau R : F2[x]/(xAn-1) une telle petite distance de Hamming peut être de l'ordre de racine_carré(n)/10. Alternativement, pour un mode de réalisation où l'anneau R sélectionné serait Z/pZ, un exemple de petite norme correspondant à la distance min(x,p-x) petit serait racine_carrée (p) / 100. Alice et bob calculent ensuite respectivement les syndromes SA et SB à partir d'une fonction f telle que : SA = f(XA,YA) = XA.h + YA et SB = f(XB,YB) = XB.h + YB, où f est une loi de composition interne associant à tout élément X, de l'anneau R un autre élément f(XI) de l'anneau R et possédant la propriété que pour toute paire d'éléments X, et Y, de R, tels que X, et Y, ont une petite norme vis-à-vis des éléments f(XI) et f(Y,), alors X,.f(Y,) - Y,.f(X,) est de petite norme. Alice transmet à Bob un premier message M1A(SA) composé notamment à partir du premier syndrome SA de sorte que ledit premier syndrome SA puisse être récupéré par Bob. Parallèlement, Bob transmet à Alice un deuxième message M1B(SB) composé notamment à partir du deuxième syndrome SB de sorte que ledit deuxième syndrome SB puisse être récupéré par Alice. Alice calcule alors une première valeur intermédiaire PA, telle que : - PA = YA.SB = YA.XB + YA.h.YB. Et Bob calcule de façon similaire une deuxième valeur intermédiaire PB, telle que : - PB = YB.SA = YB.XA + YB.h.YA. Dès lors, Alice et Bob sont respectivement en possession d'une première valeur intermédiaire PA et d'une deuxième valeur intermédiaire PB qui diffèrent l'une de l'autre par la valeur YA.XB û YB.XA. Or, puisque les éléments primaires XA, YA, XB et YB ont été sélectionnés de sorte qu'ils aient une petite norme vis-à-vis du paramètre w, et puisque la distance de hamming est sous multiplicative dans F2[x]/(Xn-1), alors la première valeur intermédiaire PA détenue par Alice diffère de la deuxième valeur intermédiaire PB détenue par Bob d'une valeur dont la norme est nécessairement inférieure à 2 w2. 9 À l'issue de l'étape de distribution, Alice et Bob sont donc en possession de deux messages M1A(SA) et M1B(SB) correspondant à deux trames de données dont la première comporte le premier syndrome SA et la deuxième comporte le deuxième syndrome SB. Intervient alors une seconde étape dite de réconciliation. Selon un premier mode de réalisation la phase de réconciliation consiste en ce qu'Alice et Bob choisissent de manière publique une opération v[] consistant à sélectionner de façon aléatoire p bits 10 parmi les n bits constituant les première et deuxième valeur intermédiaire PA et PB, tel qu'il existe une probabilité suffisante que ces p bits sélectionnés par Alice et Bob permettent d'en déduire une information commune. Pour ce faire, Bob transmet à Alice un message bruité M2B(C) composé à partir d'une donnée C 15 correspondant à un code correcteur d'erreur de longueur p permettant de corriger une erreur d'une valeur inférieure ou égale à 2w2 et tel que : C = m.G + v[PB] où 20 - m représente alors une information confidentielle - G représente la matrice génératrice d'un code correcteur d'erreur sur lesquels Alice et Bob se sont préalablement publiquement accordés - v[]représente une opération de troncature consistant à extraire p bits parmi les n bits d'un vecteur. 25 Du fait de la construction ci-dessus, m.G est très bruité par rapport à v[PB]. Alice peut donc calculer la valeur de C û v[PA] et en déduire m.G + v[PB-PA]. Mais comme v[PB-PA] est relativement petit, Alice est capable en utilisant le code correcteur d'erreur de corriger cette erreur 30 v[PB-PA] qui a été ajoutée à m.G et donc de retrouver l'information confidentielle m ainsi que v[PB]. Alice peut alors avantageusement composer une clé de chiffrement soit à partir de l'information confidentielle m. Mai s de façon alternative, il est également possible que cette clé de chiffrement soit composée à partir de la deuxième valeur intermédiaire PB ou à partir d'une combinaison de 35 l'information confidentielle m et de la deuxième valeur intermédiaire PB. Sont décrits dans le tableau ci-dessous, plusieurs exemples de paramètres pouvant être utilisés dans le protocole selon l'invention, dans lesquels : 40 - le paramètre n correspond au nombre de coordonnées des syndrome SA et SB ; - le paramètre sb correspond au nombre de bits échangés de façon sécurisée dans le procédé ;5 code est le petit code C utilisé où BCH(255,55) X 13 correspond à la concaténation du code binaire BCH d'une distance de 55 concaténée avec un code de répétition de taille 3 ; - E est une majoration de la probabilité que le décodage soit erroné, obtenu à partir du taux d'erreur induit par 2w21n et de la capacité de correction de C ; - security correspond à la sécurité du paramètre ; et - complexity correspond au nombre de binaire nécessaire pour faire tourner le procédé d'un coté. Ces paramètres sont choisis de sorte que n22' = 280 pl .. FE: ? r#. .. ~.." .:s t tt 0' I' 3 t i_ Ii 3l_ ÿ.,"£j 3 F II convient de noter que dans ce premier mode de réalisation, la longueur de l'information confidentielle à décoder a été choisie de manière qu'aucune information ne soit perdue, ce qui limite la longueur code correcteur d'erreur utilisé pour le décodage. Toutefois, selon un deuxième mode de réalisation, il est également envisageable d'utiliser toute la longueur des premier et deuxième syndromes SA et SB pour le décodage, en y ajoutant un vecteur 20 erreur e. Ainsi, une attaque implique nécessairement la résolution d'un problème classique de décodage de syndrome pour un code correcteur d'erreur doublement circulant, ce qui le rend insoluble du fait de l'addition de l'erreur e. Dans ce cas de figure, Alice et Bob se mettent publiquement d'accord sur une permutation P, un 25 nombre t d'erreurs aléatoires et un code correcteur d'erreur de matrice génératrice G corrigeant un nombre d'erreurs de longueur p et de dimension k, avec un algorithme de décodage capable de résoudre un canal symétrique binaire avec une probabilité de transition (2w2+t)/n. Ensuite, Bob sélectionne une information confidentielle m qui est encodée sur une donnée C 30 composant un message bruité M2B(C) tel que : C = m.G + P[PB] + e, où - G représente la matrice génératrice du code correcteur d'erreur, 35 - e représente le vecteur de t erreurs aléatoires de longueur m et de dimension k et - P[PB] correspond à la permutation P de la deuxième valeur intermédiaire PB. 15 A partir du message bruité, Alice peut donc calculer la valeur C + P[PB], lui appliquer l'algorithme de décodage du code correcteur d'erreur et en déduire l'information confidentielle m, ainsi que le deuxième valeur intermédiaire PB. Ainsi, Alice peut composer une clé de chiffrement soit à partir de l'information confidentielle m ou comme précédemment, à partir de la deuxième valeur intermédiaire PB ou d'une combinaison de l'information confidentielle m et de la deuxième valeur intermédiaire PB. De la même façon que précédemment, sont décrits dans le tableau ci-dessous, plusieurs exemples de paramètres pouvant être utilisés dans le protocole selon l'invention dans lesquels : le paramètre n correspond au nombre de coordonnées des syndrome SA et SB ; - le paramètre sb correspond au nombre de bits échangés de façon sécurisée dans le procédé ; - le paramètre t correspond au poids du vecteur d'erreur aléatoire ; - code est le petit code C utilisé où BCH(255,55) X 13 correspond à la concaténation du code binaire BCH d'une distance de 55 concaténée avec un code de répétition de taille 3 ; - E est une majoration de la probabilité que le décodage soit erroné, obtenu à partir du taux d'erreur induit par 2w21n et de la capacité de correction de C ; - security correspond à la sécurité du paramètre ; et - complexity correspond au nombre de binaire nécessaire pour faire tourner le procédé d'un coté. Ces paramètres sont choisis de sorte que n22' = 280 487.7 150. DCH ), 5.M:'7 0.. "` x ? ; 2 581M 3.4'. 15(1 131 .~~`S 5.. 1 ...,::i . , ..- .., .2 ~.., y ~`? 821c 4:15 .3 Y ~ ire :,,v 410- 11483 ~,i`.~~t~~ 13:1 Z.ÿ_ 3:Z~?'`>, Vit; ~....?i Il convient de souligner que, selon un troisième mode de réalisation, l'étape de réconciliation peut faire intervenir un message bruité M2B(C) tel que la donnée C comporte simultanément une opération de troncature sur la deuxième valeur intermédiaire PB et un vecteur d'erreurs aléatoire. Une telle donnée C pourrait alors présenter la forme suivante C = m.G + v[PB] + e. 30 La figure 2 représente un deuxième mode de réalisation de l'invention. Selon ce deuxième mode de réalisation, le procédé de communication est utilisé pour permettre à Bob d'envoyer un message chiffré à l'attention de Alice selon un protocole de type El Gamal. De même que précédemment, Alice comporte un processeur 2A, un espace mémoire 4A et une unité de communication 6A et Bob comporte un processeur 2B, un espace mémoire 4B et une unité de communication 6B. La première étape du procédé correspond à l'étape de distribution. Comme précédemment, Alice et Bob s'échangent préalablement des données afin de se mettre d'accord sur un anneau R, un entier n et un élément h de l'anneau R. L'anneau R sélectionné correspond selon cet exemple à F2[x]/(Xn-1), c'est-à-dire l'ensemble des polynômes à coefficients dans le corps F2 à deux éléments pour lesquels on considère le reste par la division du polynôme (Xn -1). On utilise alors comme fonction norme la distance de hamming. 20 De façon alternative, il serait également possible de sélectionner d'autres couples d'anneau R et de norme, parmi lesquels : - l'anneau Z/pZ et la norme euclidienne ; - l'anneau (Z/pZ)[x]/(xn-1) et la norme euclidienne également ; et - l'anneau (Z/prZ)[X]/(xn-1) et pour norme le rang métrique. Dans ce mode de réalisation, il est possible d'utiliser un code binaire doublement circulant C [2n, n] comprenant une matrice de vérification de parité de la forme [InIH] où In est la matrice identité de taille n x n et h est telle que : 10 15 25 I-' :::_ 30 Après avoir sélectionnés l'anneau R, le générateur h et l'entier n, Alice et Bob sélectionnent séparément et de façon secrète un couple d'éléments primaires XA, YA pour Alice et XB, YB pour Bob de sorte que ces éléments primaires XA, YA, XB et YB sont de petite norme, et présente donc une 35 petite distance de Hamming, par rapport à un nombre réel positif w. Comme précédemment, pour un anneau R : F2[x]/(xAn-1) une telle petite distance de Hamming peut être de l'ordre de racine_carré(n)/10. Alternativement, pour un mode de réalisation où l'anneau R sélectionné serait Z/pZ, un exemple de petite norme correspondant à la distance min(x,p-x) petit serait racine_carrée (p) / 100. Alice et bob calculent ensuite respectivement les syndromes SA et SB à partir d'une fonction f telle que : SA = f(XA,YA) = XA.h + YA et SB = f(XB,YB) = XB.h + YB, où f est une loi de composition interne associant à tout élément X, de l'anneau R un autre élément f(XI) de l'anneau R et possédant la propriété que pour toute paire d'éléments X, et Y, de R, tels que X, et Y, ont une petite norme vis-à-vis des éléments f(XI) et f(Y,), alors X,.f(Y,) - Y,.f(X,) est de petite norme. Cet exemple de réalisation se distingue de celui de la figure 1 en ce que Alice ne transmet pas directement à Bob le premier message M1A(SA) composé à partir du premier syndrome SA. Au contraire, dans ce deuxième mode de réalisation, Alice émet le premier message M1A(SA) et le met à disposition de Bob et d'autres entités électroniques dans un espace publique 10. Ainsi, Bob peut récupérer le premier message M1A(SA) et en déduire le premier syndrome SA en interrogeant, par requête 12a, l'espace publique 10. Bob calcule ensuite une deuxième valeur intermédiaire PB, telle que : - PB = YB.SA = YB.XA + YB.h.YA. Ainsi, Bob est en mesure de transmettre à Alice un message comprenant : - un deuxième message M1B(SB) de longueur k composé à partir du deuxième syndrome SB, et 25 - un message bruité M2B(C) de longueur k composé à partir d'une donnée C obtenue à partir de la deuxième valeur intermédiaire PB et de l'information confidentielle m. Selon un premier mode de réalisation, la donnée C est telle que 30 C = m.G + v[PB], où - m représente alors une information confidentielle de longueur k, - G représente la matrice génératrice d'un code correcteur d'erreur sur lesquels Alice et Bob se sont préalablement publiquement accordés ; et 35 - v[] représente une opération de troncature consistant à extraire p bits parmi les n bits d'un vecteur, Alice et Bob s'étant préalablement accordées sur la valeur de p. De même que précédemment, Alice peut alors décoder C à partir du deuxième message M1B(SB) et du message bruité M2B(C) après avoir calculé PA et C + v[PA]. Alice en déduit alors m.G et 40 l'information confidentielle m. Sont décrits dans le tableau ci-dessous, plusieurs exemples de paramètres pouvant être utilisés dans le protocole selon l'invention, dans lesquels : - le paramètre n correspond au nombre de coordonnées des syndrome SA et SB ; - le paramètre sb correspond au nombre de bits échangés de façon sécurisée dans le procédé ; - code est le petit code C utilisé où BCH(255,55) X 13 correspond à la concaténation du code binaire BCH d'une distance de 55 concaténée avec un code de répétition de taille 3 ; - E est une majoration de la probabilité que le décodage soit erroné, obtenu à partir du taux d'erreur induit par 2w21n et de la capacité de correction de C ; - security correspond à la sécurité du paramètre ; et - complexity correspond au nombre de binaire nécessaire pour faire tourner le procédé d'un coté. Ces paramètres sont choisis de sorte que n22' = 280 pl .. FE: ? r#. .. ~.." .:s t t2 0'0 13 t i_ Ii 3l_ ÿ.,"£j 3 F Selon un deuxième mode de réalisation, la donnée C est telle que 20 C = m.G + P[PB], où - m représente alors une information confidentielle de longueur k - G représente la matrice génératrice du code correcteur d'erreur ; et - P[PA] correspond à la permutation P de la deuxième valeur intermédiaire PA. De façon similaire, Alice peut alors décoder C à partir du deuxième message M1B(SB) et du message bruité M2B(C) après avoir calculé PA et de C + v[PA] pour déterminer m.G et en déduire l'information confidentielle m. 30 De la même façon que précédemment, sont décrits dans le tableau ci-dessous, plusieurs exemples de paramètres pouvant être utilisés dans le protocole selon l'invention dans lesquels : - le paramètre n correspond au nombre de coordonnées des syndrome SA et SB ; - le paramètre sb correspond au nombre de bits échangés de façon sécurisée dans le procédé ; 35 - le paramètre t correspond au poids du vecteur d'erreur aléatoire ; - code est le petit code C utilisé où BCH(255,55) X 13 correspond à la concaténation du code binaire BCH d'une distance de 55 concaténée avec un code de répétition de taille 3 ; - E est une majoration de la probabilité que le décodage soit erroné, obtenu à partir du taux d'erreur induit par 2w2/n et de la capacité de correction de C ; 25 security correspond à la sécurité du paramètre ; et complexity correspond au nombre de binaire nécessaire pour faire tourner le procédé d'un coté. Ces paramètres sont choisis de sorte que n22' = 280 `ä e~ ,. .. .i:.T• 1 \ ?' tif É. ;. 4151 J tt, `c. ~~;` 1 310ù .. ,Y3 , 22-: ~Z.~8, ' 3 r s Z~ ? 1 ..;ÿ?_ .: :3:i'a" .. :.xl ..:r: :4C.: x ~, r 1.r~1 :â @,3 ~É..d_.'.ef ... }_:t 2(.\.F ? 3, ? II convient de souligner que, selon un troisième mode de réalisation, l'étape de réconciliation peut faire 10 intervenir un message bruité M2B(C) tel que la donnée C comporte simultanément une opération de troncature sur la deuxième valeur intermédiaire PB et un vecteur d'erreurs aléatoire. La figure 3 illustre à un troisième exemple de réalisation dans lequel le procédé selon l'invention est 15 utilisé pour réaliser un protocole d'authentification. Ce troisième exemple de réalisation fonctionne de la même façon que le deuxième exemple de réalisation. A l'issue du procédé tel que décrit précédemment, Alice renvoie l'information confidentielle m à Bob afin de garantir que Alice possède bien la clé privée correspondant aux deux éléments 20 primaires XA, YA associés à la clé publique correspondant au syndrome SA. REVENDICATIONS1. Procédé cryptographique de communication d'une information confidentielle m entre une première entité (A) électronique et une deuxième entité (B) électronique comportant une étape de distribution et une étape de réconciliation, l'étape de distribution comportant plusieurs étapes consistant en ce que : d'une part, la première entité (A) : o calcule un premier syndrome SA = XA + f(YA) à partir d'une première information secrète composée de deux éléments primaires XA et YA appartenant à un anneau R et présentant une norme sensiblement petite vis-à-vis d'un élément f(XA) ou f(YA), • l'anneau R possédant l'addition et la multiplication, et • f étant une loi de composition interne associant à tout élément X, de l'anneau R un autre élément f(XI) de l'anneau R, et possédant la propriété que pour toute paire d'éléments X, et Y, de R, tels que X, et Y, ont une petite norme vis-à-vis des éléments f(XI) et f(Y,), alors X,.f(Y,) - Y,.f(X,) est de petite norme, et o émet un premier message composé à partir de ce premier syndrome SA de sorte que ledit premier syndrome SA soit accessible par la deuxième entité (B), d'autre part, la deuxième entité (B) : o calcule un deuxième syndrome SB = XB + f(YB) à partir d'une deuxième information secrète 20 composée de deux éléments secondaires XB et YB appartenant à l'anneau R et présentant une norme sensiblement petite vis-à-vis d'un élément f(XB) ou f(YB), o transmet à la première entité (A) un deuxième message composé à partir du deuxième syndrome SB de sorte que ledit deuxième syndrome SB soit accessible par la première entité (A), 25 caractérisé en ce que, lors de cette première étape de distribution, la première entité (A) et la deuxième entité (B) calculent respectivement une première valeur intermédiaire PA et une deuxième valeur intermédiaire PB, telles que : o PA = YA.SB = YA.XB + YA.f(YB), et o PB = YB.SA = YB.XA + YB f(YA), 30 o de sorte que, lors de l'étape de réconciliation, la première entité (A) soit capable de retrouver l'information confidentielle par une opération de déchiffrement d'un message bruité composé par la deuxième entité (B) à partir, notamment, de la deuxième valeur intermédiaire PB. 2. Procédé cryptographique selon la revendication 1, dans lequel le premier message émis par la 35 première entité (A) est transmis directement à destination de la deuxième entité (B). 3. Procédé selon la revendication 2, dans lequel le message bruité composé par la deuxième entité (B) lors de la phase de réconciliation comprend une donnée C obtenue à partir notamment de la deuxième valeur intermédiaire PB et de l'information confidentielle m. 15 40 4. Procédé selon la revendication 3, dans lequel la première entité (A) décode l'information confidentielle m à partir notamment du message bruité et de la première valeur intermédiaire PA. 5. Procédé cryptographique selon la revendication 4, dans lequel l'information confidentielle m est encodée dans la donnée C du message bruité, par un code correcteur d'erreur. 6. Procédé cryptographique selon la revendication 5, dans lequel la donnée C du message bruité est telle que C = m.G + PB + e, avec : m qui représente l'information confidentielle, G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, et e qui représente un vecteur d'erreurs aléatoires de longueur n et de norme petite, la première entité A et la deuxième entité B s'étant préalablement publiquement accordées sur la longueur n. 7. Procédé cryptographique selon la revendication 5, dans lequel la donnée C du message bruité est telle que C = m.G + v[PB], avec : m qui représente l'information confidentielle, G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, et v[] qui représente une opération consistant à extraire p coordonnées parmi les n coordonnées d'un vecteur, la première entité A et la deuxième entité B s'étant préalablement accordées sur la valeur du p. 8. Procédé cryptographique selon la revendication 5, dans lequel la donnée C du message bruité est telle que C = m.G + v[PB] + e, avec : m qui représente l'information confidentielle, G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, v[] qui représente une opération consistant à extraire p coordonnées parmi les n coordonnées d'un vecteur, la première entité A et la deuxième entité B s'étant préalablement accordées sur la valeur du p, e qui représente un vecteur d'erreurs aléatoires de longueur n et de norme petite, la première entité A et la deuxième entité B s'étant préalablement publiquement accordées sur la longueur n. 9. Procédé cryptographique selon l'une quelconque des revendications 1 à 8, dans lequel la première entité (A) compose une clé de chiffrement soit à partir de l'information confidentielle m, soit à partir de la deuxième valeur intermédiaire PB, soit à partir d'une combinaison de l'information confidentielle et de la deuxième valeur intermédiaire PB. 10. Procédé cryptographique selon la revendication 1, dans lequel, après avoir émis le premier message composé à partir du premier syndrome SA, la première entité (A) met ce premier message à disposition de la deuxième entité (B) dans un espace publique accessible au moins à une autre entité électronique. 11. Procédé cryptographique selon la revendication 10, dans lequel, après avoir calculé le deuxième syndrome SB, la deuxième entité (B) transmet, à la première entité (A) : ^ le deuxième message composé à partir du deuxième syndrome SB, et ^ le message bruité composé à partir d'une donnée C obtenue à partir de la deuxième valeur intermédiaire PB et de l'information confidentielle m. 12. Procédé cryptographique selon la revendication 11, dans lequel la première entité A décode l'information confidentielle à partir du deuxième message et du message bruité. 13. Procédé cryptographique selon la revendication 11, dans lequel la première entité A décode l'information confidentielle m à partir du deuxième syndrome SB composant le deuxième message, de la deuxième valeur intermédiaire PB composant le message bruité et de la première valeur intermédiaire PA. 14. Procédé cryptographique selon l'une quelconque des revendications 11 à 13, dans lequel l'information confidentielle m est encodée dans la donnée C du message bruité, par un code correcteur d'erreur. 15. Procédé cryptographique selon la revendication 14, dans lequel la donnée C du message bruité est telle que C = m.G + PB + e, avec : ^ m qui représente l'information confidentielle, G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, et e qui représente un vecteur d'erreurs aléatoires de longueur n et de norme petite, la première entité A et la deuxième entité B s'étant préalablement publiquement accordées sur la longueur n. 16. Procédé cryptographique selon la revendication 14, dans lequel la donnée C du message bruité est telle que C = m.G + v[PB], avec : ^ m qui représente l'information confidentielle, ^ G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, et v[] qui représente une opération consistant à extraire p coordonnées parmi les n coordonnées d'un vecteur, la première entité A et la deuxième entité B s'étant préalablement accordées sur la valeur du p. 17. Procédé cryptographique selon la revendication 14, dans lequel la donnée C du message bruité est telle que C = m.G + v[PB] + e, avec : ^ m qui représente l'information confidentielle,G qui représente la matrice génératrice d'un code correcteur d'erreur sur lesquels la première entité A et la deuxième entité B se sont préalablement publiquement accordées, v[] qui représente une opération consistant à extraire p coordonnées parmi les n coordonnées d'un vecteur, la première entité A et la deuxième entité B s'étant préalablement accordées sur la valeur du p, e qui représente un vecteur d'erreurs aléatoires de longueur n et de norme petite, la première entité A et la deuxième entité B s'étant préalablement publiquement accordées sur la longueur n. 18. Procédé cryptographique selon l'une quelconque des revendications 9 à 17, dans lequel la première entité (A) compose message d'authentification soit à partir de l'information confidentielle m, soit à partir de la deuxième valeur intermédiaire PB, soit à partir d'une combinaison de l'information confidentielle m et de la deuxième valeur intermédiaire PB. 19. Procédé cryptographique selon l'une quelconque des revendications 1 à 18, dans lequel l'anneau R est l'anneau Fq[x] / (Xn - 1), c'est-à-dire l'ensemble des polynômes à coefficients dans le corps Fq à q éléments pour lesquels on considère le reste par la division du polynôme (Xn - 1). 20. Procédé cryptographique selon la revendication 19 dans lequel la norme correspond à la distance de hamming. 21. Procédé cryptographique selon la revendication 19 ou 20, dans lequel : ^ n est sensiblement égale à 6000, et ^ XA, XB, YA, YB présentent une norme égale à 35 ^ de sorte que la norme de PA ù PB est sensiblement égale à 2400. 25. Procédé cryptographique selon l'une quelconque des revendications 1 à 18, dans lequel l'anneau R est l'anneau Z/pZ, c'est-à-dire l'ensemble des entiers modulo p moins le reste de la division par p. 26. Procédé cryptographique selon la revendication 22, dans lequel la norme est une norme 30 euclidienne. 27. Procédé selon la revendication 22 ou 23, dans lequel : ^ p est sensiblement égale à 2500, ^ f(x)=h.x modulo p avec h un nombre aléatoire plus petit que p, et/ou 35 XA, XB, YA, YB sont des éléments de R de norme plus petite que racine (p). 25. Programme d'ordinateur comprenant une pluralité d'instructions pour la mise en oeuvre, à l'exécution, du procédé selon l'une quelconque des revendications 1 à 24. 40 26. Dispositif cryptographique comprenant des moyens de calculs agencés pour mettre en oeuvre le procédé selon l'une des revendications 1 à 24. 2527. Support de données comprenant un dispositif cryptographique selon la revendication 26.