Brevet FR2700430A1 — publié le 19940713

PROCEDE D'AUTHENTIFICATION D'AU MOINS UN DISPOSITIF D'IDENTIFICATION PAR UN DISPOSITIF DE VERIFICATION ET DISPOSITIF POUR SA MISE EN OEUVRE La présente invention a pour objet un procédé d'authentification d'au moins un dispositif d'identification par un dispositif de vérification, cette authentification étant réalisée par un protocole à apport nul de connaissance basé sur le problème du décodage par syndrome. La présente invention a aussi pour objet des dispositifs d'identification et de vérification pour la mise en oeuvre dudit procédé. La présente invention s'applique, plus particulièrement, au cas des communications dites sécurisées o deux dispositifs échangent des données à travers un canal dont la sécurité est suspecte Dans ce cas, il est essentiel d'avoir un moyen de reconnaissance mutuelle, à savoir un moyen permettant à un dispositif de vérification d'authentifier un utilisateur et de lui permettre l'accès aux données ou aux services Il existe de nombreux exemples nécessitant la mise en oeuvre de ce type de communication sécurisée On peut citer, notamment, le cas des ordinateurs de type bancaire permettant d'effectuer des transferts d'ordres Dans ce cas, les deux ordinateurs doivent avoir la certitude qu'ils sont bien en communication l'un avec l'autre et non pas avec une entité pirate On peut citer aussi le cas des distributeurs automatiques de billets, des décodeurs de télévision à péage, des publiphones Dans ces exemples, le dispositif d'identification est constitué par un appareil portable tel qu'une carte à puce ou une clé électronique et le dispositif de vérification inclus soit dans le distributeur ou le décodeur doit contrôler la validité des différents moyens d'accès de la carte à puce ou de la clé électronique. Dans ce contexte, on utilise fréquemment des méthodes d'authentification qui sont basées sur des techniques cryptographiques à clés secrètes Ces méthodes sont, jusqu'à ce jour, les plus simples à mettre en oeuvre Dans le cadre de ces méthodes, le dispositif d'identification par exemple les cartes à puces et le dispositif de vérification tel qu'un terminal, un lecteur de cartes, un décodeur, un publiphone, partagent la même clé secrète et l'identification est accomplie par un algorithme symétrique ou une fonction à sens unique. L'inconvénient de ces méthodes réside dans le fait que les deux parties, à savoir le dispositif de vérification et le dispositif d'identification, doivent coopérer mutuellement et secrètement Cette condition n'est pas toujours vérifiée Effet, un élément pirate peut acheter le dispositif de vérification et l'analyser pour connaître sa structure interne Sur la base de cette analyse, l'élément pirate est techniquement capable de réaliser des dispositifs d'identification performants, car les mêmes clés secrètes sont présentes aux deux extrémités du réseau, à savoir dans le dispositif de vérification et dans le dispositif d'identification. Il est reconnu que, parmi les divers procédés pouvant être implémentés pour se prémunir contre les inconvénients des méthodes classiques connues, les protocoles à apport nul de connaissance assurent jusqu'à maintenant le degré de sécurité le plus élevé. En résumé, les protocoles d'identification à apport nul de connaissance sont fonctionnellement caractérisés par le fait qu'un nombre illimité d'interactions avec le dispositif d'identification et une analyse complète de la structure du dispositif de vérification ne sont pas suffisants pour pouvoir reconstruire les dispositifs d'identification. Toutefois, les protocoles à apport nul de connaissance qui constituent une solution idéale au problème de l'identification présentent un inconvénient majeur Leur réalisation est quelque peu difficile à faire électroniquement, car ellle demande un nombre d'opérations très important On pourra trouver une description des procédés d'identification à apport nul de connaissance existant notamment, dans le brevet américain A-4 748 668 au nom de FIAT et ai ou dans la demande de brevet européenne A-O 311 470 au nom de GUILLOU et AL. Des efforts ont été accomplis récemment afin de développer des méthodes d'identification dont la réalisation électronique soit plus facile Une telle méthode est décrite notament dans le brevet américain US-A-4 932 056 au nom de SHAMIR Cette méthode est connue sous le nom de méthode PKP Toutefois, cette méthode, qui est plus facile à réaliser électroniquement que les algorithmes manipulant les grands nombres, présente l'inconvénient d'être relativement lente lors des échanges entre les dispositifs de vérification et d'identification. La présente invention a donc pour but de remédier aux inconvénients mentionnés ci-dessus en proposant un nouveau procédé d'authentification qui soit facilement réalisable électroniquement et qui permette une authentification rapide du dispositif d'identification par le dispositif de vérification. En conséquence, la présente invention a pour objet un procédé d'authentification d'au moins un dispositif d'identification par un dispositif de vérification, cette authentification étant réalisée par un protocole à apport nul de connaissance basé sur le problème du décodage par syndrome ou le problème connu sous le nom de "Modular Knapsack", le procédé étant caractérisé par les étapes suivantes: pour permettre le dialogue entre le dispositif d'identification et le dispositif de vérification, établir une clé secrète constituée par au moins un vecteur si de dimension N et de poids de Hamming d (d sécurité est exponentiellement croissant avec le nombre de tours. Dans le procédé d'authentification ci-dessus, on utilise une matrice M de dimensions N x k, cette matrice étant commune à tous les utilisateurs et construite aléatoirement Chaque utilisateur reçoit une clé secrète S qui est un mot de N bits avec un nombre d prescrit de 1 Dans ce cas, le système calcule la clé publique K telle que K = MS. Alternativement, un utilisateur peut être doté de plusieurs clés secrètes sl 11,, slwl auxquelles sont associées des clés publiques Klil = Mslil Avantageusement, on peut exiger que ces vecteurs sl 11, slwl forment un code simplexe étendu. Le procédé d'identification est basé principalement sur la notion technique d'engagement Si U est une séquence d'éléments binaires, un engagement pour U est l'image de U à travers une certaine fonction de hachage cryptographique L'engagement sera utilisé comme une fonction à sens unique. Selon un premier mode de réalisation du procédé d'authentification, dans une première étape a) commune aux différents procédés, le dispositif d'identification révèle son identité et/ou sa ou ses clés signées au dispositif de vérification qui vérifie que l'identité en question correspond bien au vecteur Ki, puis après avoir choisi un vecteur aléatoire y et une permutation aléatoire p. b) le dispositif d'identification calcule h 1 = H(p,My), h 2 = H(yp), h 3 = H (y xor s)p) et expédie l'engagement {h 1, h 2, h 3} au dispositif de vérification, (xp représentant le vecteur x permuté par p et xor la fonction Ou exclusif), c) puis le dispositif de vérification tire de façon aléatoire un nombre O de vérification considère que le protocole s'est terminé par un succès. Selon un autre mode de réalisation de la présente invention, o le vecteur S est remplacé par une collection de W vecteurs sl 1 l, sl 2 l, slwl formant un code simplexe de poids d, après avoir choisi un vecteur aléatoire y et une permutation aléatoire p -b) le dispositif d'identification calcule h 1 = H(My, p), h 2 = H(yp, slllp, slwlp) et expédie l'engagement {h 1, h 2} au dispositif de vérification, c) le dispositif de vérification tire de façon aléatoire un vecteur binaire bl 1 l,, blwl et l'envoie au dispositif d'identification; d) le dispositif d'identification calcule et envoie au dispositif de vérification une réponse z définie par: z = yp xor sl 1 lpbl 1 l xor sl 2 lpbl 2 l xor sl 3 lpbl 3 l xor slwlpblwl; e) le dispositif de vérification tire de façon et l'envoie au dispositif d'identification, f) le dispositif d'identification envoie une aléatoire un bit q réponse r définie par: Si q = O alors r = {yp, sl 1 lp,, slWlp} Si q = 1 alors r = {p}; g) le dispositif de vérification reçoit une réponse r = {rlOl, rl 11,, rlwl} si q = O our = {rlOl} si q = 1; h) le dispositif de vérification teste que: Si q = O alors h 2 = H(r),z = rl O l xor rl 1 lbl 1 l xor rl 2 lbl 2 l xor rl 3 lbl 3 l xor rlwlblwl et {rl 1 l, rl 2 l,, rlwl} forme un code simplexe; Si q = 1 alors H(M(depermute(z, rlOl)) xor (Kl 1 lbl 1 l xor Kl 2 lbl 2 l xor Kl 3 lbl 3 l xor Klwlblwl), rlO) = h 1 o K Iil = Msli I i) si le test correspondant à q s'est avéré correct, le dispositif de vérification considère que le protocole s'est terminé par un succès. D'autres avantages de la présente invention apparaîtront à la lecture de la description de différents modes de réalisation du procédé, cette description étant faite avec référence aux dessins ci-annexés dans lesquels: la figure 1 est un schéma expliquant un premier mode de mise en oeuvre du procédé d'authentification conforme à la présente invention; la figure 2 est un schéma d'un second mode de réalisation du procédé conforme à la présente invention; la figure 3 est un schéma sous forme de blocs d'un dispositif d'identification conforme à la présente invention; la figure 4 est un schéma sous forme de blocs d'un dispositif de vérification conforme à la présente invention, et la figure 5 est un schéma électrique d'un exemple de réalisation d'un multiplicateur matrice/vecteur conforme à la présente invention. La présente invention concerne donc un nouveau procédé d'authentification réalisé par un protocole à apport nul de connaissance. La sécurité du procédé est basée sur le problème du décodage par syndrome (DS) qui peut être explicité de la manière suivante: soit une matrice binaire M et un vecteur binaire K, il s'agit de trouver un vecteur binaire S de poids relativement fort ou relativement faible, tel que Ms = K Par poids, on entend le nombre de bits à 1 dans le vecteur concerné Le problème posé ci-dessus est en fait très difficile à résoudre par les moyens de calcul connus à ce jour, si les dimensions de la matrice M et le poids d'Hamming d de S sont choisis judicieusement Les algorithmes connus pour résoudre le problème du décodage par syndrome tels que décrits, par exemple, dans l'article de J S Leon "A probabilistic algorithm for computing minimum weights of large error- correcting codes" dans IEEE TIT, 34 ( 5), pages 1354 à 1359 ou dans l'article J Stern "A method for finding codewords of small weight" Coding Theory & Applications, notes de lecture en Computer Science 388 ( 1989), pages 106-113 ont un temps de calcul qui croît exponentiellement avec la taille des matrices en question. Les moyens de calcul actuels ne permettent pas de calculer s si les dimensions de M sont aux environs de 500 par 250 et la valeur de d proche de 50 Toutefois, étant donné S (pris au hasard mais avec un certain poids>, il est possible de calculer K. Dans la présente invention, on utilise cette propriété à sens unique pour que l'appareil de vérification qui connaît K puisse tester que le dispositif d'identification possède S sans que sa valeur soit révélée au cours de l'interaction. Pour mettre en oeuvre le procédé d'authentification conforme à la présente invention, une autorité choisit et publie la matrice M constituée de coefficients aij qui ont été choisis aléatoirement En fait, pour éviter de mémoriser toute la matrice M, il est possible de générer chaque coefficient aij par f(ij) o f est une fonction pseudo- aléatoire publique quelconque. L'autorité choisit aussi une collection de vecteurs binaires si, à savoir S 1 ' S 2, sn, dont le poids de Hamming d est relativement faible et les distribue aux divers dispositifs d'identification Ainsi, le dispositif d'identification i reçoit si D'autre part, on publie l'ensemble des clés publiques Ki o Ki = Msi. Selon une variante de réalisation, l'autorité peut aussi apposer sa signature sur les Ki de façon à constituer un système cryptographique fermé o une interaction avec l'autorité est nécessaire afin de valider les clés publiques créant ainsi un système basé sur l'identité du porteur de la clé secrète si. On décrira maintenant deux modes de réalisation spécifiques du procédé de la présente invention. Le premier procédé sera décrit avec référence à la figure 1 qui représente schématiquement le protocole de communication mis en oeuvre entre un dispositif d'identification et le dispositif de vérification pour réaliser une authentification Les dispositifs d'identification qui peuvent être constitués, par exemple, par des cartes à puce ou des clés électroniques doivent être physiquement inviolables Ainsi, pour une carte à puce, il doit être impossible d'accéder à sa mémoire interne Rien par contre n'est supposé concernant l'environnement dans lequel évolue le dispositif de vérification De plus, comme représenté sur les figures 3 et 4 qui représentent schématiquement un dispositif d'identification et un dispositif de vérification, le dispositif d'identification comporte dans une mémoire non volatile sa clé secrète si et la matrice M, de même le dispositif de vérification comporte dans une mémoire non volatile l'ensemble des clés publiques Ki et la matrice M Quand un dispositif d'identification veut entrer en contact avec un dispositif de vérification, les deux dispositifs exécutent le protocole suivant: a) tout d'abord le dispositif d'identification révèle son identité et/ou sa clé signée Ki au dispositif de vérification qui vérifie que l'identité en question correspond bien à Ki. b) ensuite, le dispositif d'identification choisit un vecteur binaire aléatoire y et une permutation aléatoire p Puis, il calcule les éléments suivants: h 1 = H(p,My), h 2 = H(yp), h 3 = H ("y xor s)p) et expédie l'engagement {h 1, h 2, h 3} au dispositif de vérification, (xp représentant le vecteur x permuté par p et xor la fonction Ou exclusif), c) puis le dispositif de vérification tire de façon aléatoire un nombre O de vérification considère que le protocole s'est terminé par un succès. Si le test n'est pas correct, le dispositif d'identification est rejeté. Lorsque le dispositif est accepté, on envoie une impulsion de commande sur l'interface entrée/sortie du système protégé qui permet la mise en route de la transaction ultérieure L'ensemble des opérations ci- dessus est symbolisé sur la figure 1 dans laquelle la partie de gauche représente les différentes opérations réalisées au niveau du dispositif d'identification tandis que la partie de droite représente les différentes opérations réalisées au niveau du dispositif de vérification, les flèches symbolisant l'envoi d'informations d'un dispositif vers l'autre. Pour accroître la sécurité du procédé, les deux dispositifs d'identification et de vérification répètent les étapes ci-dessus plusieurs fois, à savoir t fois, le dispositif de vérification n'authentifiant le dispositif d'identification que si toutes les sessions du protocole se sont soldées par un succès De préférence, on choisit t tel que O Le procédé de base décrit ci-dessus peut être modifié de différentes manières, permettant notamment une simplification de la réalisation électronique ainsi qu'un raccourcissement des temps de calcul Ainsi, il est possible de transmettre le vecteur My en clair et de redéfinir H 1 = H(p) en modifiant les tests correspondants Selon une autre variante, le dispositif de vérification et/ou le dispositif d'identification peuvent faire un test partiel sur un sous-ensemble de coordonnées des vecteurs et effectuer ainsi les calculs de façon plus rapide Dans ce cas, certaines étapes du procédé sont modifiées telles que décrites ci-après. Ainsi, l'étape b peut être modifiée de la façon suivante après avoir choisi un vecteur aléatoire y et une permutation aléatoire p, b) le dispositif d'identification calcule h 1 = H(p), h 2 = H(Yp), h 3 = H ((y xor s)p) et expédie l'engagement {hl, h 2, h 3} au dispositif de vérification, c) le dispositif de vérification tire de façon aléatoire une liste de nombres mutuellement disjoints G = {gl, gf} telle que 1 de vérification le vecteur Z ainsi obtenu. Dans ce cas, l'étape e est modifiée elle aussi de la façon suivante: e) le dispositif de vérification reçoit r = {U,V} et contrôle que: Si q = 1 alors h 1 = H(V), h 2 = H(UV) et Extrait (MU,G) xor Z = O o Extrait (x, G) représente le vecteur projection obtenu en choisissant dans x seulement les bits indiqués par G; Si q = 2 alors hl = H(V), h 3 = H(UV) et Extrait (MU xor K,G) xor Z= O; Si q = 3 alors h 2 = H(U), h 3 = H(U xor V) et le poids de Hamming de V est d. Selon une autre variante du procédé, I'étape b peut être modifiée de la manière suivante: b) après avoir choisi un vecteur aléatoire y et une permutation aléatoire p, le dispositif d'identification calcule h 1 = H(p), h 2 = H(yp), h 3 = H ((y xor S)p) et expédie l'engagement {h 1, h 2, h 3) au dispositif de vérification; c) le dispositif d'identification calcule Q = My et expédie le vecteur Q ainsi obtenu au dispositif de vérification; d) le dispositif de vérification tire de façon aléatoire une liste de nombres mutuellement disjoints G = {gl,, gf} telle que 1 et calcule le vecteur Z = Extrait (Q,G). Alors l'étape e est modifiée de la manière suivante e) le dispositif de vérification reçoit r = {U,V} et contrôle que Si q = 1 alors h 1 = H(V), h 2 = H(Uv) et Extrait (MU,G) xor Z = O; 1 1 Si q = 2 alors h 1 = H(V), h 3 = H(UV) et Extrait (MU xor K,G) xor Z = O; Si q = 3 alors h 2 = H(U), h 3 = H(U xor V) et le poids de Hamming de V est d. Un autre mode de mise en oeuvre du procédé d'authentification est maintenant décrit avec référence à la figure 2 Ce second mode de réalisation demande plus de calculs que le mode de réalisation précédent, mais la probabilité de succès d'une entité illégale décroît plus vite Dans ce cas, le vecteur si est remplacé par un ensemble de vecteurs sl 1 l,, slwl formant un code simplexe étendu. De plus le vecteur Ki est remplacé par un ensemble de vecteurs Kl 1 l, Klwl tels que M(slil) = Klil. Ce mode de réalisation comporte donc les étapes suivantes, symbolisées sur la figure 2 de manière identique à la symbolisation utilisée sur la figure 1: a) le dispositif d'identification choisit un vecteur aléatoire y et une permutation aléatoire p puis calcule h 1 = H(My, p), h 2 = H(yp, sl 1 lp,, slwlp) et expédie l'engagement {h 1, h 2} au dispositif de vérification, b) le dispositif de vérification tire de façon aléatoire un vecteur binaire bl 1 l,, blwl et l'envoie au dispositif d'identification; c) le dispositif d'identification calcule et envoie au dispositif de vérification une réponse z définie par: z = yp xor slllpbl 1 l xor sl 2 lpbl 2 l xor sl 3 lpbl 3 l xor slwlpblwl; d) le dispositif de vérification tire de façon aléatoire un bit q et l'envoie au dispositif d'identification, e) le dispositif d'identification envoie une réponse r définie par Si q = O alors r = t{yp, sll 11 lp,, slWlp} Si q = 1 alors r = {p}; f) le dispositif de vérification reçoit une réponse r = {rlOl, rl 1 l, rlwl} si q = O our = {rl 01} si q = 1; g) le dispositif de vérification teste que Si q = O alors h 2 = H(r),z = rd Ol xor rlill Iblll xor rl 2 lbl 2 l xor rl 3 lbl 3 l xor rlwlblwl et {rl 1 l, rl 2 l,, rlwl} forme un code simplexe; Si q = 1 alors H(M(depermute(z, rlOl)) xor (Kl 1 lbl 1 l xor Kl 2 lbl 2 l xor Kl 3 lbl 3 l xor Klwlblwl), rlOl) = h 1; h) si le test correspondant à q s'est avéré correct, ce dispositif de vérification considère que le protocole s'est terminé par un succès. Ce procédé peut lui aussi être modifié et adapté de manière à éviter la dépermutation du vecteur z, et à effectuer une vérification simplifiée sur un sous-ensemble des coordonnées des vecteurs comme décrit ci-dessus Dans ce cas, le procédé peut comporter, par exemple, les étapes suivantes: a) le dispositif d'identification choisit un vecteur aléatoire y et une permutation aléatoire p, puis calcule: h 1 = H(p), h 2 = H(yp, sl 1 lp,, slWlp) et expédie l'engagement {h 1, h 2} et le vecteur h O = My au dispositif de vérification; b) le dispositif de vérification tire de façon aléatoire un vecteur binaire bll 1,, blwl et l'envoie au dispositif d'identification, c) le dispositif d'identification calcule et envoie au dispositif de vérification une réponse z définie par: z = yp xor sl 1 lpbl 1 ll xor sl 2 lpbl 2 l xor sl 3 lpbl 3 l xor slIwlpblwl; d) le dispositif de vérification tire de façon aléatoire un bit q et l'envoie au dispositif d'identification, e) le dispositif d'identification envoie une réponse r définie par Si q = O alors r = {yp, sl 1 lp,, slwlp} Si q = 1 alors r = {p}; f) le dispositif de vérification reçoit uneréponse r = {rlOl, rl 1 l, rlwl} si q = O our = {rlOl} si q = 1; g) le dispositif de vérification teste que Si q = O alors h 2 = H(r),z = rlOl xor rl 1 lbl 1 l xor rl 2 lbl 2 l xor rl 3 lbl 3 l xor rlwlblwl et {rlll, rl 21, rlwl} forme un code simplexe; Si q = 1 alors h 1 = H(rlOl) et (h O)rlOj xor (Kll Jb Ill xor Kl 2 lbl 21 xor Kl 3 lbl 31 xor Klwlblwl)rlol = z. Si le test correspondant s'est avéré correct, le dispositif de vérification considère que le protocole s'est terminé par un succès. Comme dans le cas du premier mode de réalisation, le protocole décrit cidessus peut être répété t fois, le dispositif de vérification n'authentifiant le dispositif d'identification que si toutes les sessions du protocole se sont soldées par un succès. D'autre part, la sécurité des deux méthodes décrites ci-dessus dépend de la taille des différents paramètres, notamment de d, n k, et t. Il est évident pour l'homme de l'art que le choix de t est facilement modulable en cours de fonctionnement, au niveau des deux dispositifs communiquant entre eux en fonction du contexte En ce qui concerne les paramètres d, N et k, il s'agit de paramètres système et leurs choix sont fixés à l'origine et plus difficilement modifiables. Ainsi, de préférence, les paramètres d, n, k sont choisis sensiblement sous la borne Warshamov-Gilbert donnant une valeur limite théorique pour le poids minimal d d'un code (n,k) aléatoire, à savoir: d = n H 2 (k/n) o H 2 (x) est la fonction d'entropie H 2 (x) = x 1 og 2 (x) - ( 1-x) 1 o 92 ( 1 x) Dans ce cas, d est choisi tel que: d = (k n) log 2 ( 1(k/n J)k 1 o 92 (k/n) ou d = (n (k N log 2 ( 1 (kn) + k 1 og 2 (k/n). De plus, à la restriction de la borne de Warshamov-Gilbert, il convient d'ajouter une relation telle que 2 k = N qui lie les valeurs de N et k. En utilisant les relations ci-dessus, de préférence d = 0,11 n ou d = 0, 89 N et les couples N et k peuvent prendre l'une des valeurs suivantes: {n = 384, k = 196} ou {n = 512, k = 256} ou {n = 1024, k = 512} ou {n = 768, k = 384). Selon une variante de réalisation qui peut être utilisée dans l'ensemble des méthodes décrites ci-dessus, la fonction de hachage est remplacée par une fonction de chiffrement o le message à hacher joue le rôle de la clé et/ou de messages à chiffrer et o le contrôle de la véracité du message haché consiste à dévoiler le message qui a été haché et/ou la clé de chiffrement On pourra se référer à ce sujet aux publications suivantes: Ivan Damgaard, Crypto'89, "Design principles for hash- functions"; Naor and al "one-way hash functions and their cryptographic applications", Proceedings of the 21st annual ACM symposium on theory of computing, Seattle, Washington, May 15-17, 1989, pp 33-43; Matyas, "Generating strong one-way functions with cryptographic algorithm", IBM Technical disclosure bulletin, vol 27, N 10 A, March 1985, pp 5658-5659. Dans le cas d'un procédé basé sur le "Modular Knapsack", le choix du vecteur y et tous les calculs sont effectués modulo m et l'opération xor est remplacée par une addition ou une soustraction modulo m, les tests sur le poids étant remplacés par la vérification que toutes les coordonnées du vecteur sont soit 0, soit 1 et que le poids de ce vecteur est constant, la relation reliant n, k et m étant: N k In(m)/ln 2 et N k > 64 Alors m est choisi parmi les nombres 2, 3, 5, 7 ou 2 c dans lequel c est un nombre entier petit et les ensembles {n, k, m} peuvent prendre l'une des valeurs suivantes: { 196,128,3} ou { 384,256,3} ou { 128, 64, 5} ou { 192, 96, 5}. Dans beaucoup de cas, il est important d'avoir un moyen de déduire S de l'identité ID du porteur du dispositif d'identification Ceci permet, par exemple, d'éviter la sauvegarde des clés publiques Ki auprès des dispositifs de vérification et la mise à jour d'un dictionnaire de clés publiques dès qu'un nouvel utilisateur rejoint le système. Pour ce faire, un code simplexe étendu sigma 1,, sigmau est choisi par l'autorité une fois pour toutes comme paramètre. Pour enregistrer un utilisateur dont l'identité est ID, on hache la valeurID par une fonction à sens unique publique (par exemple la fonction de hachage H) et on obtient un vecteur binaire e 1,, eu On calcule u SID = Z el sigmai i= 1 On publie K 1 = M(sigma 1),, Ku = M(sigma)u et on donne Si D à l'utilisateur ID. Les dispositifs de vérifications peuvent calculer u KID= Z el Ki i= 1 o le vecteur el,, eu est donnée par le hachage de ID et vérifier que le dispositif d'identification possède SID- Pour atteindre un degré de sécurité suffisant, il est indispensable d'avoir u > 40 ce qui implique, à priori, des codes simplexes de taille trop importante En réalité, il est facilement possible de se ramener à des tailles raisonnables en choissant une collection de L codes simplexes de petites dimensions (par exemple d = 64, dim = 7, n = 580, k = 290, L = 8) et en calculant pour chaque utilisateur une collection de L clés secrètes slll D, sl 2 ll D,, slLli D obtenues comme suit. Choisir, une fois pour toutes L codes simplexes de dimension dim sigma l 1 l 1, sigmal 1 ldim sigma l 211, sigmal 2 ldim sigma lLl 1, sigmalLldim donner, à chaque dispositif d'identification, la collection complète des clés publiques Klilj = M (sigma lilj) pour i = 1, L et j = 1, dim. Pour chaque utilisateur 1 Calculer: H(ID) = e 1, eu 2 Partager le vecteur e en L segments el 1 l, elLl de dim bits chacun; 3 Pour i = 1 à L calculer dim slilîD = Z eliljsigmalilj j = 1 j= 4 Donner S 1 lD, sl 2 D,, sll D à l'utilisateur. 4 Donner sli 1 lD sl 2 llîD,, sllll D à l'utilisateur. On utilisera les divers slill D soit de façon sérielle (en utilisant aux tours successifs les slill D à tour de rôle) ou parallèle, comme l'illustre le protocole suivant: a) le dispositif d'identification révèle son identité ID au dispositif de vérification; b) le dispositif de vérification calcule KlIIID, Kl 211 D,,KlLIID c) le dispositif d'identification choisit L vecteurs yl 1 l,,ylLl et L permutations pl 1 l,, plLI, calcule h 1 = H({plil}, {Mylil}), h 2 = H({ylilplil}), h 3 = H ({ylil xor slilplil}) et expédie l'engagement {h 1, h 2, h 3} au dispositif de vérification; d) le dispositif de vérification tire de façon aléatoire un nombre O poids des Vlil est d. g) Si le test correspondant à q s'est avéré correct, le dispositif de vérification considère que le protocole s'est terminé par un succès; h) les deux dispositifs répètent les étapes a) à f) t fois. En version parallèle, le protocole prend la forme suivante a) I'identificateur révèle son identité ID au vérifieur b) le vérifieur calcule Kl 1 lD,Kl 2 lID,, KlLlID c) l'identifieur choisit L vecteurs yl 1 l,, ylLl et L permutations pl 1},, plLl, calcule h 1 = {H(plil, Mylil)}, h 2 = {H(ylilplil)}, h 3 = {H((ylil xor slilplil)} et expédie l'engagement {h 1, h 2, h 3} au vérifieur. d) le vérifieur tire de façon aléatoire L nombres aléatoires ql 1 l,, qlLl o O d'une facon évidente pour l'homme de l'art. Une autre méthode pour relier ID à S est la suivante on introduit t secrets de poids at dont les bits à un sont répartis sur 2 at positions Soit sl 1 l, sl 2 l,, sltl et on publie Mslil pour i = 1,,t. Dans ce cas, la génération d'une clé se passe selon le processus suivant Il est aisé, notamment par tiangulation partielle, de trouver un mot S tel que t s = Z xlil slil et i= 1 t Ms = Z el Mslil et i= 1 le poids de S est approximativement ta-t/2. Le choix des dimensions dans ce système est régi typiquement par les relations suivantes: 0,11 N = ta t/2, 2 k = N et 2 at 8 > 56 o 2 a-2 a H 2 ( 8) 1. Typiquement, pour t = 56 on a: d = 95, N = 863, k = 432. Il est évident pour l'homme de l'art que d'autres combinaisons sont possibles. On décrira maintenant succintement, avec référence à la figure 3, un mode de réalisation schématique d'un dispositif d'identification qui peut être, par exemple, une carte à puce Ce dispositif d'identification comporte donc une unité de commande 1, une mémoire non volatile 2 qui peut être seulement lue et qui contient par exemple la matrice M ou une fonction permettant d'obtenir les coefficients de la matrice M tels que définis ci-dessus ainsi que la clé secrète si du dispositif d'identification lui-même Ii comporte aussi une mémoire à accès aléatoire 3, un multiplicateur vecteur-matrice dont le mode de réalisation sera décrit avec référence à la figure 5, un moyen pour réaliser des OU exclusifs binaires 5, un générateur 6 de nombres aléatoires, une fonction de hachage 7 et un générateur de permutation 8, tous ces éléments étant protégés physiquement Il comporte aussi un interface de communication permettant un échange de données entre le dispositif de vérification et l'unité de commande du dispositif d'identification Le générateur de nombres aléatoires peut être réalisé par une source de bruit blanc numérisé qui peut être produit, par exemple, par une diode zener polarisée en inverse dans la zone dite "du coude"ou peut être aussi constitué par un générateur de nombres pseudo- aléatoires comme décrit dans les brevets américains 4 817 147 au nom de GUNTER ou 4 649 419 au nom d'ARAGON D'autre part, le générateur de permutation 8 est capable de permuter des vecteurs binaires en utilisant, par exemple, la méthode décrite dans la demande de brevet européen N 091 403065 ou dans l'article intitulé "On the generation of permutation" de David Naccache dans le South African Computer Journal, N 02, 1990, pages 12 à 16. La fonction de hachage peut être réalisée par une fonction de hachage MD 4 présentée par RIVEST à crypto 90, FFT-Hash Il itérée convenablement, présentée par SCHNOR à Eurocrypt 92, ou par l'algorithme de chiffrement DES. Le dispositif de vérification tel que représenté à la figure 4 comporte lui aussi une unité de commande 10, cette unité de commande étant reliée à une mémoire non volatile 11 du type ROM qui comporte la matrice M et la clé publique K, un calculateur du poids de Hamming 12, un comparateur 13, un multiplicateur matrice-vecteur 14, une mémoire à accès aléatoire 15, des moyens 16 pour réaliser des OU exclusifs binaires identiques aux moyens 5 du dispositif d'identification, un générateur 17 de nombres aléatoires, tel que décrit ci-dessus, une fonction de hachage 18 identique à la fonction de hachage 7 et un générateur de permutations 19 Il comporte aussi une interface de communication 20 reliée à l'unité de commande 10 et permettant de gérer la communication entre le dispositif de vérification et les différents dispositifs d'identification. On décrira maintenant avec référence à la figure 5, un mode de réalisation de la fonction multiplication de la matrice par un vecteur Ce mode de réalisation simplifié peut être utilisé avec un vecteur y de huit bits Comme représenté sur la figure 5 concernant un multiplicateur matriciel M permettant de multiplier un vecteur y de huit bits par la matrice de dimensions correspondantes, ce multiplicateur est formé de huit portes-ET 11, 12, 13, 14, 15, 16, 17, 18 Chaque porte-ET reçoit sur chaque entrée, un bit du vecteur y et un bit de la ligne courante de la matrice M Les sorties des porte-ET alimentent un réseau triangulaire de porte OU exclusifs 21, 22, 23, 24, 31 32, 4 afin d'obtenir à la sortie du circuit le bit correspondant au produit scalaire de y par la ligne courante de la matrice M De manière plus spécifique, les sorties des portes 11, 12 sont envoyées en entrée de la porte OU exclusif 21, les sorties des portes 13, 14 sont envoyées en entrée de la porte OU exclusif 22 et les sorties de ces deux portes OU exclusif sont envoyées en entrée de la porte OU exclusif 31 De manière identique, les sorties des portes 15, 16 sont envoyées en entrée de la porte OU exclusif 23 et les sorties des portes 17, 18 sont envoyées en entrée de la porte OU exclusif 24, les sorties de ces deux portes OU exclusif étant envoyées en entrée de la porte OU exclusif 32 Les sorties des portes OU exclusif 31, 32 sont envoyées en entrée de la porte OU exclusif 4 dont la sortie S correspond au produit scalaire de y par la ligne courante de la matrice M. REVENDICATIONS 1 Procédé d'authentification d'au moins un dispositif d'identification par un dispositif de vérification, cette authentification étant réalisée par un protocole à apport nul de connaissance basé sur le problème du décodage par syndrome ou le problème connu sous le nom de "Modular Knapsack", le procédé étant caractérisé par les étapes suivantes pour permettre le dialogue entre le dispositif d'identification et le dispositif de vérification, établir une clé secrète constituée par au moins un vecteur si de dimension N et de poids de Hamming d (d de sécurité souhaité. 2 Procédé selon la revendication 1, caractérisé en ce que le vecteur si est un vecteur binaire. 3 Procédé selon les revendications 1 et 2, caractérisé en ce que après avoir choisi un vecteur aléatoire y et une permutation aléatoire p, le dispositif d'identification calcule: h 1 = Fi(p,My), h 2 = H(yp>, h 3 = H ((y xor s)p) et expédie l'engagement {h 1, h 2, h 3} au dispositif de vérification, (xp représentant le vecteur x permuté par p et xor la fonction Ou exclusif), puis le dispositif de vérification tire de façon aléatoire un nombre O Hamming de V est d. Si le test correspondant à q s'est avéré correct, le dispositif de vérification considère que le protocole s'est terminé par un succès. 4 Procédé selon les revendications 1 et 2, caractérisé en ce que, après avoir choisi un vecteur aléatoire y et une permutation aléatoire p le dispositif d'identification calcule h 1 = H(p), h 2 = H(yp), h 3 = H ((y xor s)p) et expédie l'engagement {hl, h 2, h 3} à ce dispositif de vérification, le dispositif de vérification tire de façon aléatoire une liste de nombres mutuellement disjoints G = {g 9, gf} telle que 1 vérification considère que le protocole s'est terminé par un succès. Procédé selon les revendications 1 et 2, caractérisé en ce que, après avoir choisi un vecteur aléatoire y et une permutation aléatoire p, le dispositif d'identification calcule h 1 = H(p), h 2 = H(yp), h 3 = H ((y xor S)p) et expédie l'engagement {h 1, h 2, h 3} au dispositif de vérification; le dispositif d'identification calcule Q = My et expédie le vecteur Q ainsi obtenu au dispositif de vérification le dispositif de vérification tire de façon aléatoire une liste de nombres mutuellement disjoints G = {gl,, gf} telle que 1 Z = O; Si q = 2 alors h 1 = H(V), h 3 = H(UV) et Extrait (MU xor K,G) xor Z=O; Si q = 3 alors h 2 = H(U), h 3 = H(U xor V) et le poids de Hamming de V est d; Si le test correspondant à q s'est avéré correct, le dispositif de vérification considère que le protocole s'est terminé par un succès. 6 Procédé selon la revendication 1, caractérisé en de que le vecteur si est remplacé par un ensemble de vecteurs sl 11,, slwl formant un code simplexe étendu. 7 Procédé selon la revendication 6, caractérisé en ce que le vecteur Ki est remplacé par un ensemble de vecteurs Kl 1 l, Klwl tels que M(slil) = Klil. 8 Procédé selon les revendications 6 et 7, caractérisé en ce que le dispositif d'identification choisit un vecteur aléatoire y et une permutation aléatoire p puis calcule h 1 = H(My, p), h 2 = H(yp, sl 1 11 p, slWvvlp) et expédie l'engagement {h 1, h 2} au dispositif de vérification, le dispositif de vérification tire de façon aléatoire un vecteur binaire bl 1 1,, bfwl et l'envoie au dispositif d'identification; le dispositif d'identification calcule et envoie au dispositif de vérification une réponse z définie par: z = yp xor sl 1 lpbl 1 l xor sl 2 lpbl 2 l xor sl 3 lpb 3 l xor slwlpblwl; le dispositif de vérification tire de façon aléatoire un bit q et I'envoie au dispositif d'identification, le dispositif d'identification envoie une réponse r définie par Si q = O alors r = {yp, slllp,, slWlp} Si q = 1 alors r = {p}; le dispositif de vérification reçoit une réponse r = {rlOl, rl 1 l, ,rlwl} si q = O our = {rlOl} si q = 1; le dispositif de vérification teste que Si q = O alors h 2 = H(r),z = rlOl xor rllbl 1 l xor rl 2 lbl 2 l xor rl 3 lbl 3 l xor rlwlblwl et {rl 1 l, rl 21,, rlwl} forme un code simplexe; Si q = 1 alors H(M(depermute(z, rlOl)) xor (Kl 1 lbl 1 l xor Kl 21 bl 2 l xor Kl 3 lbl 3 l 1 xor Klwlblwl), rlOl)= h 1; si le test correspondant à q s'est avéré correct, le dispositif de vérification considère que le protocole s'est terminé par un succès. 9 Procédé selon les revendications 6 et 7, caractérisé en ce que le dispositif d'identification choisit un vecteur aléatoire y et une permutation aléatoire p, puis calcule: h 1 = H(p), h 2 = H(yp, sl 1 lp,, slWlp) et expédie I'engagement {h 1, h 2} et le vecteur h O = My au dispositif de vérification; le dispositif de vérification tire de façon aléatoire un vecteur binaire bl 1,, blwl et l'envoie au dispositif d'identification, le dispositif d'identification calcule et envoie au dispositif de vérification une réponse z définie par: z = yp xor sl 1 lpbl 1 l xor sl 2 lpbl 2 l xor sl 3 lpbl 3 l xor slwlpblwl; le dispositif de vérification tire de façon aléatoire un bit q et l'envoie au dispositif d'identification, le dispositif d'identification envoie une réponse r définie par Si q = O alors r = {yp, slllp,, slWlp} Si q = 1 alors r = {p}; le dispositif de vérification reçoit une réponse r = {rlO Il, rl 1 l, , rlwl}siq = O our = {rlOl}siq = 1; le dispositif de vérification teste que Si q = O alors h 2 = H(r),z = rl O l xor rl 1 lbl 1 l xor rl 2 lbl 2 l xor rl 3 lbl 31 xor rlwlblwl et {rl 1 l, rl 2 l, rlwl} forme un code simplexe; Si q = 1 alors h 1 = H(rl O l) et (h O)rl O I xor (Klllblll xor Kl 2 lbl 2 l xor Kl 3 lbl 3 l xor Klwlblwl)rlOl = z. Si le test correspondant s'est avéré correct, le dispositif de vérification considére que le protocole s'est terminé par un succès. Procédé selon l'une quelconque des revendications 1 à 9, caractérisé en ce que le protocole est répété t fois et que le dispositif de vérification n'authentifie le dispositif d'identification que si toutes les sessions du protocole se sont soldées par un succès. 11 Procédé selon la revendication 10, caractérisé en ce que t est choisi tel que O 12 Procédé selon l'une quelconque des revendications 1 à 11, caractérisé en ce que le poids de Hamming d est choisi tel que: d = (k n) log 2 ( 1 (kn)) k 1 o 92 (kh), et de préférence sensiblement inférieur à cette valeur. 13 Procédé selon l'une quelconque des revendications 1 à 11, caractérisé en ce que le poids de Hamming d est choisi tel que: d (n (k n) log 12 (k In) + k 1 og 2 (k/n>, et de préférence sensiblement supérieur à cette valeur. 14 Procédé selon l'une quelconque des revendications 13, caractérisé en ce que N = 2 k. Procédé selon l'une quelconque des revendications 12 à 14, caractérisé en ce que d= 0,1 ln ou d = 0,89 n 16 Procédé selon l'une quelconque des revendications 1 à 15, caractérisé en ce que N et k prennent comme valeur l'un des couples suivants; {n = 384, k = 196} ou {n = 512, k = 256} ou {n = 1024, k = 512} ou {n = 768,1 k = 384} 17 Procédé selon l'une quelconque des revendications 1 à 16, caractérisé en ce que la fonction de hachage est remplacée par une fonction de chiffrement o le message à hâcher joue le rôle de la clé et/ou du message à chiffrer et o le contrôle de la véracité du message hâché consiste à dévoiler le message qui a été hâché et/ou la clé de chiffrement. 18 Procédé basé sur le "Modular Knapsack" selon l'une quelconque des revendications 1 à 17, caractérisé en ce que le choix du vecteur y et tous les calculs sont effectués modulo m et l'opération xor est remplacée par une addition ou une soustraction modulo m, les tests sur le poids étant remplacés par la vérification que toutes les coordonnées du vecteur sont soit 0, soit 1 et que le poids de ce vecteur est constant, la relation reliant n k et m étant: N k ln(m)/ln 2 et N - k > 64. 19 Procédé selon la revendication 18, caractérisé en ce que m est choisi parmi les nombres 2, 3, 5, 7 ou 2 c dans lequel c est un nombre entier petit. Procédé selon les revendications 18 ou 19, caractérisé en ce que {n,k,m} prennent comme valeurs l'une des valeurs suivantes { 196, 128, 3} ou { 384, 256, 3} ou { 128, 64, 5} ou { 192, 96, 5}. 21 Procédé selon l'une quelconque des revendications 1 à 20, caractérisé en ce que le calcul de H(p) est effectué en calculant H(ep) o e est un vecteur constant pseudo-aléatoire. 22 Procédé selon l'une quelconque des revendications 1 à 21, caractérisé en ce que pour pouvoir associer l'identité ID de chaque utilisateur à ses clés {si, Ki}, l'autorité génératrice choisit un ensemble de clés secrètes primaires {K Pi} et hache ID en un vecteur binaire I = H(ID) servant à calculer si comme fonction des K Pl, l'autorité publiant l'ensemble des clés publiques primaires {P Pi} ou {P Pi} = f (KPI). 23 Procédé selon la revendication 22, caractérisé en ce que l'autorité utilise les bits de I comme indicateurs de sélection permettant de décider pour chaque K Pl si celui-ci intervient dans le processus de calcul de S ou non. 24 Procédé selon la revendication 23, caractérisé en ce que l'ensemble (K Pi} forme un ou plusieurs codes simplexes étendus. Procédé selon la revendication 24, caractérisé en ce que I est un nombre de 56 bits. 26 Procédé selon les revendications 22 à 25, caractérisé en ce que S est calculé comme combinaison linéaire des K Pl soit s = I l 1 l K Pl + I l 2 l KP 2 + I ltaille de 1 l Kp taille de I et o P Pl = (K Pi). 27 Procédé pour relier ID à S selon les revendications 22, 23 et 25, caractérisé en ce que l'on réalise les calculs suivants l'autorité sélectionne t secrets K Pl de poids at dont les bits à un sont répartis sur 2 at positions, publie l'ensemble des P Pl = M(KPI) et génére une clé S par triangulation partielle de la façon suivante: t s _Z xlil K Pl 1 = t Ms = Z 1 (il P Pl et le poids de S = ta-t/2 le choix des dimensions étant régi par les relations suivantes 0,11 N ta-t/2, 2 k = N et 2 atÈ > 56 o 2 a-2 a H 2 ( 6) 1. 28 Procédé selon la revendication 27, caractérisé en ce que t = 56, d = 95, N = 864, k = 432. 29 Système pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 28, comprenant au moins un dispositif d'identification et un dispositif de vérification, caractérisé en ce que le dispositif d'identification comporte au moins des moyens pour multiplier une matrice M de dimensions N x k, par des vecteurs de N bits des moyens pour stocker un vecteur secret si d'un poids de Hamming d, des moyens pour produire un vecteur aléatoire y et une permutation aléatoire p des moyens pour réaliser un hachage cryptographique H et des moyens de communication avec le dispositif de vérification. Système selon la revendication 29, caractérisé en ce que le dispositif de vérification comporte au moins des moyens pour multiplier une matrice M de dimensions N x k, par des vecteurs de N bits des moyens pour stocker au moins un vecteur public Ki tels que Ki = Msi, des moyens pour produire aléatoirement un nombre entier, des moyens pour réaliser un hachage cryptographique H et des moyens de communication avec les dispositifs d'identification. 31 Système selon les revendications 29 et 30, caractérisé en' ce que la matrice M est générée par un générateur déterministe de nombres pseudo-aléatoires. 32 Système selon les revendications 29 à 31, caractérisé en ce que le multiplieur matriciel M est formé d'un alignement de portes "et" aux entrées de chacune desquelles on applique un bit du vecteur y et un bit de la ligne courante de la matrice M et o les sorties des portes "et" alimentent un réseau triangulaire de portes "xor" afin d'obtenir à la sortie du circuit le bit correspondant au produit scalaire de y par la ligne courante de la matrice M.5