Brevet FR2917920A1 — publié le 20081226

PROCÉDÉ D'AUTHENTIFICATION UTILISANT UN DÉCODAGE DE CODE CORRECTEUR D'ERREURS À PARTIR D'UNE MATRICE PUBLIQUE L'invention se rapporte à un procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique. L'invention se rapporte également à un dispositif cryptographique 10 comprenant des moyens de calcul agencés pour mettre en oeuvre, à l'exécution, un tel procédé d'authentification. On connaît des procédés cryptographiques d'authentification. 15 Le procédé cryptographique d'authentification le plus répandu est actuellement basé 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. 20 Toutefois, un tel procédé cryptographique d'authentification présente plusieurs inconvénients. En particulier, dans l'algorithme RSA, il est nécessaire de procéder à des calculs sur des entiers très grands, et notamment des calculs d'exponentielles discrètes. De tels calculs peuvent être lents, tout particulièrement lorsqu'ils sont implémentés 25 sur des dispositifs cryptographiques à bas coût possédant des capacités de calcul limité, notamment des cartes à puce ou des étiquettes radio fréquence. Dès lors, les procédés cryptographiques d'authentification ne sont pas actuellement disponibles sur de tels dispositifs cryptographiques. 30 Parmi les alternatives aux procédés cryptographiques d'authentification basés sur l'algorithme RSA, on connaît les procédés cryptographiques d'authentification utilisant un décodage de code correcteur d'erreurs utilisant une matrice publique. 35 L'invention se rapporte plus particulièrement à un tel procédé. 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. En outre, les calculs de décodage de codes correcteurs d'erreur sont plus rapides que les calculs basés sur l'algorithme RSA. L'utilisation des codes correcteurs d'erreurs en cryptographie est 10 bien connue et date des années 1980. La demande EP-A-0661846 décrit un tel procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique. 15 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 20 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, 25 Communication and Computing, 1997, 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. Ce protocole est appelé protocole de Veron. 30 Dans ces protocoles d'authentification, la matrice publique est le plus souvent aléatoire, et il est donc nécessaire de stocker l'ensemble des coefficients de la matrice dans une mémoire du dispositif cryptographique implémentant le protocole. 35 Toutefois, les contraintes de stockage des dispositifs cryptographiques à bas coûts ne permettent pas d'implémenter un tel protocole. C'est notamment le cas dans une carte à puce ou une étiquette radio fréquence. Dans le document A new identification scheme based on syndrome decoding , J. Stern 1993, il est également proposé de générer la matrice publique de façon pseudo-aléatoire à partir d'une valeur initiale, et d'un générateur pseudo-aléatoire. Toutefois, la spécification d'un générateur pseudo-aléatoire est un problème qui reste actuellement non résolu. En outre, l'implémentation d'un tel générateur pseudo-aléatoire pourrait être incompatible avec les capacités limitées d'un dispositif cryptographique à bas coût. Un but de l'invention est de fournir un procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique qui puisse être implémenté dans un dispositif cryptographique à bas coût, ayant notamment des capacités de calcul et/ou de stockage limitées. En particulier, un but de l'invention est de réduire la quantité de données publiques à stocker dans un procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique. En outre, les matrices aléatoires utilisées dans les documents susmentionnés sont mal adaptées à des calculs rapides dans un dispositif cryptographique. 30 Un autre but de l'invention est de fournir un procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique permettant des calculs rapides. Pour atteindre ces buts, dans le cadre de l'invention, un nouveau 35 type de matrice publique est proposé.25 En particulier, ces buts sont atteints selon l'invention grâce au fait que la matrice publique est une matrice quasi-cyclique. Il est connu qu'une matrice quasi-cyclique est une matrice comprenant une juxtaposition de blocs circulants, dans lesquels on passe d'une ligne à une autre par une permutation circulaire. Dès lors, pour stocker l'ensemble de l'information sur la matrice publique, il suffit de stocker une ligne de base de chaque bloc circulant, le reste du bloc circulant se déduisant de cette ligne de base par une permutation. La quantité de données à stocker dans le procédé d'authentification est donc considérablement réduite. En outre, les multiplications d'un vecteur par une matrice quasi-cyclique sont rapides, grâce aux propriétés des blocs circulants. Or, le procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs met en oeuvre de telles multiplications. Il en résulte que le procédé selon l'invention permet d'améliorer la rapidité des calculs cryptographiques. Le procédé d'authentification selon l'invention peut donc être facilement implémenté dans un dispositif cryptographique, et ce même si ce dispositif cryptographique comprend des capacités de stockage et de calcul limités. Le procédé d'authentification selon l'invention a également l'avantage de fournir une matrice publique susceptible d'être compatible avec les protocoles décrits dans les publications mentionnées ci-dessus, c'est-à-dire les protocoles de décodage par syndrome de Stern, et le protocole dual du décodage par syndrome de Stern, décrit par Veron. Selon un premier mode de réalisation de l'invention, la matrice quasi- cyclique comprend k ligne et 2k colonnes et est une juxtaposition d'un bloc identité de taille k*k, et d'un bloc circulant de taille k*k. Dans ce cas, la clé privée du procédé d'authentification est un mot X de taille 2k. Les données publiques comprennent un syndrome s de taille k, et la moitié de la première ligne de la matrice quasi-cyclique de taille k. Un protocole de décodage par syndrome peut alors être mis en oeuvre à partir de 4k bits. Dans ce mode de réalisation, le bloc circulant peut être défini par un 10 vecteur de taille k aléatoire. La matrice publique de ce premier mode de réalisation peut être utilisé en tant que matrice publique dans les protocoles de Stern ou de Veron. 15 Dans un deuxième mode de réalisation, la matrice publique est construite à partir d'une matrice intermédiaire quasi-cyclique comprenant k lignes et 2k colonnes, la matrice intermédiaire étant composée d'une juxtaposition d'une d'un premier bloc carrée 20 circulant de taille k, et d'une d'un deuxième bloc carrée circulant de taille k, la matrice intermédiaire étant de la forme G'=[A B], la matrice publique étant construite en multipliant à gauche la matrice intermédiaire par la matrice inverse du bloc A, de sorte que la matrice publique est de la forme G=[Il A-1.B], la matrice A-1 étant la 25 matrice inverse du bloc A. Dans ce deuxième mode de réalisation, le premier bloc circulant et le deuxième bloc circulant sont définis respectivement par un premier vecteur et un deuxième vecteur, le vecteur formé par le premier 30 vecteur et le deuxième vecteur étant de poids faible. Le premier vecteur et le deuxième vecteur peuvent être aléatoires avec cette contrainte de poids. 35 Dans ce deuxième mode de réalisation, la matrice publique peut tout particulièrement être utilisée en tant que matrice publique dans un protocole de Veron. Dans ce cas, le secret du protocole de Veron est constitué par le 5 vecteur colonne transposé du vecteur ligne formé par le premier vecteur et le deuxième vecteur. Ce vecteur correspond à une clé privée de taille 2k. Les données publiques peuvent alors être déterminées à partir des blocs circulants 10 induits par la clé privée pour une taille k. Un protocole de décodage peut alors être mis en oeuvre à partir de 3k bits. L'invention se rapporte également à un programme d'ordinateur comprenant des instructions agencées de sorte à mettre en oeuvre, à 15 l'exécution, le procédé d'authentification tel que précédemment décrit. L'invention se rapporte également à un dispositif cryptographique comprenant des moyens de calcul agencés pour mettre en oeuvre le 20 procédé d'authentification tel que précédemment décrit. L'invention se rapporte également à une carte à puce comprenant un tel dispositif cryptographique. 25 On décrit maintenant des modes de réalisation de l'invention en référence aux figures annexées dans lesquelles : FIG. 1 représente de façon générale une matrice quasi-cyclique ; FIG. 2 représente une matrice publique à utiliser dans un procédé d'authentification selon un premier mode de réalisation de 30 l'invention ; FIG. 3 représente un exemple de bloc matriciel composant la matrice illustrée à la FIG. 2 ; FIG. 4 représente une matrice intermédiaire des mots de petit poids utilisée pour construire la matrice publique à utiliser dans un procédé 35 d'authentification selon un deuxième mode de réalisation de l'invention ; FIG. 5 représente un exemple de bloc matriciel composant la matrice intermédiaire illustrée à la FIG. 4. Le procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique selon l'invention est susceptible d'être mis en oeuvre à l'aide du protocole de décodage par syndrome de Stern. Ce protocole est entièrement décrit dans la demande de brevet EP-A-0661846 et dans la publication susmentionnée A new identification scheme based on syndrome decoding , J. Stern 1993. Il est également bien connu de l'homme du métier dans le domaine de la cryptographie par code correcteur d'erreurs. Pour l'implémentation de ce protocole, on se rapportera à ces documents. On rappelle ci-dessous les principales étapes du protocole de Stern. Dans le décodage par syndrome de Stern, deux entités détiennent une matrice publique H constituée d'éléments binaires. La clé privée est alors un mot de poids faible, et la clé publique est le produit de la matrice publique par ce mot. Pour réaliser l'authentification, avec le protocole de Stern, on considère une entité P, le prouveur, qui veut s'authentifier auprès d'un vérifieur V. On effectue une répétition de tours, dont chaque exécution correcte augmente la probabilité de véracité de l'identité de P. Chaque tour est composé d'une première étape où le prouveur P envoie un engagement au vérificateur V, qui renvoie alors dans une deuxième étape un défi à P. Dans une troisième étape, le prouveur P renvoie une réponse au vérificateur V, qui vérifie que la réponse du prouveur P est en accord avec sa clé publique. Le lien entre la clé publique de P et sa clé secrète est basé sur le problème du décodage par syndrome. Le détail calculatoire des opérations du protocole de Stern précité est bien connu de l'homme du métier, qui pourra éventuellement se rapporter à l'article précité. De la même façon, l'homme du métier connaît le protocole de Veron et pourra éventuellement se référer au document Improved Identification schemes based on error-correcting codes , Veron, Applicable Alegbra in Engineering, Communication and Computing, 1997, pour l'implémentation du protocole de Veron. On rappelle ci-dessous les principales étapes du protocole de Veron Pour réaliser l'authentification avec le protocole de Veron, les grandes étapes sont les mêmes que pour le protocole de Stern, la différence se situant au niveau des calculs effectués à chaque étape qui sont un peu différents. En particulier le lien entre la clé publique et la clé privée est basé sur le fait de trouver un mot de faible poids associé à une certaine matrice ou code correcteur d'erreurs. Dans ces documents, une matrice publique est décrite. Selon l'invention, le protocole est mis en oeuvre comme dans les documents précités en remplaçant la matrice publique décrite dans ces documents par les matrices publiques décrites ci-dessous. Le type de matrice publique susceptible d'être utilisé dans chacun des protocoles mentionnés ci- dessus est décrit ci-dessous. En particulier, la matrice H décrite ci-dessous dans le premier mode de réalisation peut être utilisée indifféremment en tant que matrice publique dans le protocole de Stern ou de Veron, et la matrice G décrite dans le deuxième mode de réalisation peut être utilisé dans le protocole de Veron. Selon l'invention, la matrice publique est une matrice quasi-cyclique, c'est-à-dire composée d'une juxtaposition de blocs circulants. La 35 FIG. 1 représente de façon générale une telle matrice H quasi- cyclique, composée de blocs carrés circulants AI, A2, ..., An. Chacun des blocs est défini par un vecteur de base, et le reste du bloc circulant est déterminé à partir du vecteur de base par des permutations. Illustré FIG. 2, selon un premier mode de réalisation, la matrice publique H est du type de la matrice décrite ci-dessus en référence à la FIG. 1 et comprend k lignes et 2k colonnes. Elle est composée d'une matrice identité I carrée de taille k, et d'une matrice circulante C carrée de taille k composée de 0 et de 1. La matrice H est donc de la forme H=[I C]. La matrice circulante C est décrite plus en détail sur la FIG. 3. Elle comprend une première ligne consistant en un vecteur aléatoire [c,, c2, ..., Ck_l, ck], les c; valant 0 ou 1. Les lignes suivantes sont déterminées par permutations successives de la première ligne, de sorte que la matrice C est entièrement déterminée par sa première ligne. Cette matrice publique H peut être utilisée en tant que matrice publique dans les protocoles de Stern et de Veron mentionnés plus haut. Selon un deuxième mode de réalisation, on définit une matrice intermédiaire G' quasi-cyclique comprenant k lignes et 2k colonnes. Elle est composée d'une première matrice carrée circulante A de taille k, et d'une deuxième matrice carrée circulante B de taille k. Cette matrice intermédiaire G' est illustrée FIG. 4. La matrice G' est donc de la forme G'=[A B]. On construit alors la matrice publique G=[l A-1.B], composée d'un premier bloc identité et d'un deuxième bloc correspondant à la multiplication à gauche de la matrice B par la matrice inverse de A, notée A-1. Dans la suite, on note D la matrice égale au produit A-1.B. La matrice G telle que décrite ci-dessus est utilisée en tant que matrice publique dans le protocole de Veron. Les matrices A et B sont illustrées FIG. 5 et sont définies respectivement à partir de leur première ligne respective a=[a,, a2, ..., ak_,, ak] et b=[bi, b2, ..., bk_l, bk], les a; et b; valant 0 ou 1. Ces deux premières lignes sont des vecteurs aléatoires et sont choisies de sorte que le vecteur [a,b] satisfasse la condition de poids dans le protocole de Veron. Dans ce cas, la donnée privée dans le protocole de Veron est le vecteur t[a,b] de taille 2k, c'est-à-dire le vecteur colonne transposé du vecteur ligne [a,b], et la donnée publique est le vecteur décrivant la matrice D de taille k, c'est-à-dire la première ligne de la matrice D. L'avantage de ce deuxième mode de réalisation est que la donnée secrète t[a,b] de poids faible est directement décrite dans la matrice publique. Selon l'invention, l'utilisation des matrices décrites ci-dessus dans un protocole de Veron ou de Stern pour le premier mode de réalisation, et tout particulièrement dans le protocole de Veron dans le deuxième mode de réalisation, permet de maintenir les contraintes de sécurité imposées pour les protocoles cryptographiques. En particulier, il est connu qu'un code est sécurisé pour les attaques usuelles lorsque ses paramètres sous en dessous de la limite de Gilbert-Varshanov. Dans le premier mode de réalisation, pour un secret X de poids w, si le poids w est choisi juste en dessous de la limite de Gilbert-Varshanov, on choisit k de sorte que le coût pour trouver un mot X de poids w dans un code de paramètres [2k, k] est au moins 250. Un exemple de paramètres respectant ces conditions pour la matrice quasi-cyclique du premier mode de réalisation est k=317, w=69, ce qui fournit une donnée publique de taille 634 correspondant à un syndrome s, et une donnée privée de taille 951 correspondant au secret de taille 2k, et à la première ligne de la matrice C. Dans ce cas, la matrice H est telle que HX=s, s étant le syndrome, X étant la clé secrète, et H la matrice publique. Dans le deuxième mode de réalisation, on choisit le vecteur x = [a,b] de poids w inférieur à la limite de Gilbert-Varshanov, et par exemple k=347, w=76, fournissant une donnée privée tx = t[a,b] de taille 694 bits, et une donnée publique, définie par la première ligne de la matrice D, de taille 347 bits. Ainsi, l'utilisation des matrices quasi-cycliques selon l'invention permet de diminuer la taille des matrices par rapport aux tailles usuelles dans les protocoles de Stern ou de Veron, typiquement de plusieurs centaines de kilobits à environ 300 bits. Le procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice quasi-cyclique selon l'invention peut être facilement implémenté dans un dispositif cryptographique, pour le protocole de Veron ou de Stern. En particulier, la matrice H décrite dans le premier mode de réalisation peut être utilisée indifféremment dans le protocole de Stern ou de Veron, et la matrice G décrite dans le deuxième mode de réalisation peut être utilisé dans le protocole de Veron. Pour ce faire, on programme un processeur de sorte à implémenter les protocoles susmentionnés avec la ou les matrices quasi-cycliques décrites ci-dessus. Le dispositif cryptographique comprend également des mémoires pour stocker les données lors des calculs cryptographiques. Grâce au fait que e procédé selon l'invention permet de diminuer la 35 taille des matrices utilisées dans le décodage de codes correcteurs d'erreurs, tel dispositif cryptographique peut par exemple être la puce d'une carte à puce. REVENDICATIONS 1. Procédé cryptographique d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique, caractérisé en ce que la matrice publique est une matrice quasi-cyclique. 2. Procédé selon la revendication 1, dans lequel la matrice 10 - publique (H) comprend k ligne et 2k colonnes et est une juxtaposition d'un bloc identité de taille k*k, et d'un bloc circulant de taille k*k. 3. Procédé selon la revendication 2, dans lequel la matrice 15 publique (H) est une matrice du type H=[l I C], dans laquelle I est la matrice identité de taille k*k, et C est le bloc circulant de taille k*k. 4. Procédé selon la revendication 2 ou 3, dans lequel le bloc 20 circulant est défini par un vecteur de taille k aléatoire. 5. Procédé selon l'une des revendications 2 à 4, dans lequel le bloc circulant est composé de données binaires. 25 6. Procédé selon l'une des revendications 2 à 5, dans lequel le nombre k est égal à 317. 7. Procédé selon l'une des revendications 2 à 5, dans lequel la matrice quasi-cyclique est utilisée dans un protocole de Stern 30 ou un protocole de Veron. 8. Procédé selon la revendication 1, dans lequel la matrice publique est construite à partir d'une matrice intermédiaire (G') quasi-cyclique comprenant k lignes et 2k colonnes, la matrice 35 intermédiaire (G') étant composée d'une juxtaposition d'uned'un premier bloc carrée circulant A de taille k, et d'une d'un deuxième bloc carrée circulant B de taille k, la matrice intermédiaire étant de la forme G'=[A B], la matrice publique étant construite en multipliant à gauche la matrice intermédiaire par la matrice inverse du bloc A, de sorte que la matrice publique est de la forme G=K A-'.B], la matrice A-1 étant la matrice inverse du bloc A. 9. Procédé selon la revendication 8, dans lequel le premier bloc circulant et le deuxième bloc circulant sont définis respectivement par un premier vecteur et un deuxième vecteur, le vecteur formé par le premier vecteur et le deuxième vecteur étant de poids faible. 10. Procédé selon la revendication 9, dans lequel le premier vecteur et le deuxième vecteur sont aléatoires. 11. Procédé selon l'une des revendications 8 à 10, dans lequel la matrice publique est utilisée en tant que matrice publique dans 20 un protocole de Veron. 12. Procédé selon la revendication 11, dans lequel, dans le secret du protocole de Veron est constitué par le vecteur colonne transposé du vecteur ligne formé par le premier vecteur et le 25 deuxième vecteur. 13. Programme d'ordinateur comprenant une pluralité d'instructions pour la mise en oeuvre, à l'exécution, du procédé selon l'une des revendications 1 à 12. 14. Dispositif cryptographique comprenant des moyens de calcul agencés pour mettre en oeuvre le procédé selon l'une des revendications 1 à 12. 30 35 15. Carte à puce comprenant un dispositif cryptographique selon la 15revendication 14.