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 œuvre, à l'exécution, du procédé selon l'invention, un dispositif cryptographique comprenant des moyens de calculs agencés pour mettre en œuvre 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

Il 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 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.

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 très sécurisés. L'utilisation des codes correcteurs d'erreurs en cryptographie est connue depuis les années 1980. La demande EP-A-0 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. 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 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 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.

Il 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 d'être en possession d'une version bruitée Y de la variable aléatoire X. 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.

Il 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 S _A = X _A + Î(YA) à partir d'une première information secrète composée de deux éléments primaires X _A et Y _A appartenant à un anneau R et présentant une norme sensiblement petite vis-à-vis d'un élément f(X _A ) ou f(Y _A ),

• 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(X|) 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 Yi ont une petite norme vis-à-vis des éléments f(X|) et f(Y|), alors X,.f(Yi) - Y,.f(Xi) est de petite norme, et

o émet un premier message composé à partir de ce premier syndrome S _A de sorte que ledit premier syndrome S _A soit accessible par la deuxième entité (B),

^■ d'autre part, la deuxième entité (B) :

o calcule un deuxième syndrome S _B = X _B + f(Ye) à partir d'une deuxième information secrète composée de deux éléments secondaires X _B et Y _B appartenant à l'anneau R et présentant une norme sensiblement petite vis-à-vis d'un élément f(X _B ) ou f(Y _B ), o transmet à la première entité (A) un deuxième message composé à partir du deuxième syndrome S _B de sorte que ledit deuxième syndrome S _B 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 entité (B) calculent respectivement une première valeur intermédiaire P _A et une deuxième valeur intermédiaire P _B , telles que :

o P _A = Y _A .SB = YA.XB + Y _A .f(Y _B ), et

o P _B = YB.S _A = Y _B .XA + Y _B f(Y _A ),

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 P _B .

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 P _B et de l'information confidentielle m. 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 P _A .

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 :

^■ 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.

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,

■ 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 une clé de chiffrement soit à partir de l'information confidentielle m, soit à partir de la deuxième valeur intermédiaire P _B , soit à partir d'une combinaison de l'information confidentielle et de la deuxième valeur intermédiaire P _B .

Selon une réalisation, après avoir émis le premier message composé à partir du premier syndrome S _A , 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 S _B , et

^■ le message bruité composé à partir d'une donnée C obtenue à partir de la deuxième valeur intermédiaire P _B 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 :

■ 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.

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,

^■ 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 F _q [x] / (X ^N - 1 ), c'est-à-dire l'ensemble des polynômes à coefficients dans le corps F _q à q éléments pour lesquels on considère le reste par la division du polynôme (X ^N - 1 ).

Selon une réalisation, l'anneau R est l'anneau F _q [x] / (X ^N - 1 ), c'est-à-dire l'ensemble des polynômes à coefficients dans le corps F _q à q éléments pour lesquels on considère le reste par la division du polynôme (X ^N - 1 ). Selon une réalisation, la norme correspond à la distance de hamming.

Selon une réalisation:

^■ n est sensiblement égale à 6000, et

^■ X _A , XB, YA, YB présentent une norme égale à 35

■ de sorte que la norme de P _A - P _B 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. 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

^■ X _A , 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 œuvre, à l'exécution, du procédé selon l'une quelconque des réalisations 1 à 24. Selon un autre aspect, l'invention concerne dispositif cryptographique comprenant des moyens de calculs agencés pour mettre en œuvre 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 figures

Des exemples détaillés de réalisation de l'invention sont décrits, ci-dessous, en références aux figures 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 - 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é.

Il convient en premier lieu de souligner que dans le cadre de l'invention de terme de « message » 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. 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 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 à F ₂ [x]/(X ⁿ -1 ), c'est-à-dire l'ensemble des polynômes à coefficients dans le corps F ₂ à deux éléments pour lesquels on considère le reste par la division du polynôme (X ⁿ -1 ). On utilise alors comme fonction norme la distance de hamming.

Il 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]/(x ⁿ -1 ) et la norme euclidienne également ; et

l'anneau (Z/p ^r Z)[X]/(x ⁿ -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 [l _n |H] où l _n est la matrice identité de taille n x n et h est telle que :

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 X _A , Y _A pour Alice et X _B , YB pour Bob de sorte que ces éléments primaires X _A , Y _A , X _B et Y _B 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]/(x ^A n-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 S _A et S _B à partir d'une fonction f telle que : S _A = f(X _A ,Y _A ) = X _A .h + Y _A et S _B = f(X _B ,Y _B ) = X _B .h + Y _B , où f est une loi de composition interne associant à tout élément X| de l'anneau R un autre élément f(X|) 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(X|) et f(Y|), alors X|.f(Y|) - Y|.f(Xi) est de petite norme.

Alice transmet à Bob un premier message M _1A (S _A ) composé notamment à partir du premier syndrome S _A de sorte que ledit premier syndrome S _A puisse être récupéré par Bob. Parallèlement, Bob transmet à Alice un deuxième message M _{1 B} (S _B ) composé notamment à partir du deuxième syndrome S _B de sorte que ledit deuxième syndrome S _B puisse être récupéré par Alice.

Alice calcule alors une première valeur intermédiaire P _A , telle que :

PA - YA-S _B - Y _A .X _B + Y _A .h.Y _B .

Et Bob calcule de façon similaire une deuxième valeur intermédiaire P _B , telle que :

P _B = Y _B .S _A = Y _B .X _A + Y _B .h.Y _A . Dès lors, Alice et Bob sont respectivement en possession d'une première valeur intermédiaire P _A et d'une deuxième valeur intermédiaire P _B qui diffèrent l'une de l'autre par la valeur Y _A .X _B - Y _B .X _A . Or, puisque les éléments primaires X _A , Y _A , X _B et Y _B 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 F ₂ [x]/(X ⁿ -1 ), alors la première valeur intermédiaire P _A détenue par Alice diffère de la deuxième valeur intermédiaire P _B détenue par Bob d'une valeur dont la norme est nécessairement inférieure à 2 w ² . À l'issue de l'étape de distribution, Alice et Bob sont donc en possession de deux messages M _1A (S _A ) et M-IB(SB) correspondant à deux trames de données dont la première comporte le premier syndrome S _A et la deuxième comporte le deuxième syndrome S _B .

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 parmi les n bits constituant les première et deuxième valeur intermédiaire P _A et P _B , 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é M ₂ B(C) composé à partir d'une donnée C correspondant à un code correcteur d'erreur de longueur p permettant de corriger une erreur d'une valeur inférieure ou égale à 2W ² et tel que :

C = m.G + v[P _B ] où 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.

Du fait de la construction ci-dessus, m.G est très bruité par rapport à v[P _B ].

Alice peut donc calculer la valeur de C - v[P _A ] et en déduire m.G + V[P _B -PA]- Mais comme V[P _B -PA] est relativement petit, Alice est capable en utilisant le code correcteur d'erreur de corriger cette erreur v[P _B -P _A ] qui a été ajoutée à m.G et donc de retrouver l'information confidentielle m ainsi que v[P _B ].

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 P _B ou à partir d'une combinaison de l'information confidentielle m et de la deuxième valeur intermédiaire P _B .

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 S _A et S _B ;

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 1 ₃ 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 ;

ε est une majoration de la probabilité que le décodage soit erroné, obtenu à partir du taux d'erreur induit par 2w ² /n 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 n2 ^{2w r} = 2 ⁸⁰ .

Il 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 S _A et S _B pour le décodage, en y ajoutant un vecteur 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 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

Ensuite, Bob sélectionne une information confidentielle m qui est encodée sur une donnée C composant un message bruité M ₂ B(C) tel que :

C = m.G + P[P _B ] + e, où

G représente la matrice génératrice du code correcteur d'erreur,

- e représente le vecteur de t erreurs aléatoires de longueur m et de dimension k et

P[P _B ] correspond à la permutation P de la deuxième valeur intermédiaire P _B . A partir du message bruité, Alice peut donc calculer la valeur C + P[P _B ], 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 P _B . 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 P _B ou d'une combinaison de l'information confidentielle m et de la deuxième valeur intermédiaire P _B .

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 S _A et S _B ;

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 1 ₃ 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 ;

ε est une majoration de la probabilité que le décodage soit erroné, obtenu à partir du taux d'erreur induit par 2v /n 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 n2 ^{2w r} = 2 ⁸⁰ .

Il convient de souligner que, selon un troisième mode de réalisation, l'étape de réconciliation peut faire intervenir un message bruité M _2B (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[P _B ] + e. 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 à F ₂ [x]/(X ⁿ -1 ), c'est-à-dire l'ensemble des polynômes à coefficients dans le corps F ₂ à deux éléments pour lesquels on considère le reste par la division du polynôme (X ⁿ -1 ). On utilise alors comme fonction norme la distance de hamming.

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]/(x ⁿ -1 ) et la norme euclidienne également ; et

l'anneau (Z p ^r Z)[X]/(x ⁿ -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 [l _n |H] où l _n est la matrice identité de taille n x n et h est telle que :

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 X _A , Y _A pour Alice et X _B , YB pour Bob de sorte que ces éléments primaires X _A , Y _A , X _B et Y _B sont de petite norme, et présente donc une petite distance de Hamming, par rapport à un nombre réel positif w. Comme précédemment, pour un anneau R : F2[x]/(x ^A n-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 S _A et S _B à partir d'une fonction f telle que : S _A = Î(XA,YA) = ΧΑ-Π + YA et S _B = Î(XB,YB) = Xe-h + YB, OÙ f est une loi de composition interne associant à tout élément X| de l'anneau R un autre élément f(X|) 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(X|) et f(Y|), alors X|.f(Y|) - Y|.f(Xi) 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 M _1A (S _A ) composé à partir du premier syndrome S _A . Au contraire, dans ce deuxième mode de réalisation, Alice émet le premier message M _1A (S _A ) 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 M _1A (S _A ) et en déduire le premier syndrome S _A en interrogeant, par requête 12a, l'espace publique 10. Bob calcule ensuite une deuxième valeur intermédiaire P _B , telle que :

PB = YB-SA = YB-XA ⁺ ΥΒ-ΙΊ ΥΑ-

Ainsi, Bob est en mesure de transmettre à Alice un message comprenant :

un deuxième message M _{1 B} (S _B ) de longueur k composé à partir du deuxième syndrome S _B , et - un message bruité M ₂ B(C) de longueur k composé à partir d'une donnée C obtenue à partir de la deuxième valeur intermédiaire P _B et de l'information confidentielle m.

Selon un premier mode de réalisation, la donnée C est telle que

C = m.G + v[P _B ], 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

- 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 M _{1 B} (S _B ) et du message bruité M ₂ B(C) après avoir calculé P _A et C + v[P _A ]. Alice en déduit alors m.G et 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 S _A et S _B ;

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 1 ₃ 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 ;

ε est une majoration de la probabilité que le décodage soit erroné, obtenu à partir du taux d'erreur induit par 2v /n 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 n2 ^{2w r} = 2

Selon un deuxième mode de réalisation, la donnée C est telle que

C = m.G + P[P _B ], 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[P _A ] correspond à la permutation P de la deuxième valeur intermédiaire P _A .

De façon similaire, Alice peut alors décoder C à partir du deuxième message M _{1 B} (S _B ) et du message bruité M _2B (C) après avoir calculé P _A et de C + pour déterminer m.G et en déduire l'information confidentielle m. 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 S _A et S _B ;

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 1 ₃ 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 ;

ε est une majoration de la probabilité que le décodage soit erroné, obtenu à partir du taux d'erreur induit par 2v /n 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'u coté.

Ces paramètres sont choisis de sorte que n2 ^{2w r} = 2

Il convient de souligner que, selon un troisième mode de réalisation, l'étape de réconciliation peut faire intervenir un message bruité M ₂ B(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 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 primaires X _A , Y _A associés à la clé publique correspondant au syndrome S _A .