Brevet FR2836311A1 — publié le 20030822

PROCEDE DE CRYPTOGRAPHIE UTILISANT UN ALGORITHME CRYPTOGRAPHIQUE SYMETRIQUE PAR FLOT ET APPLICATION A UNE CARTE A PUCE La présente invention concerne un procédé de cryptographie pour la génération d'un nombre pseudoaléatoire et/ou pour le chiffrement/déchiffrement par flot et/ou pour l'authentification de données, utilisant une clé de chiffrement K et un algorithme cryptographique symétrique. Une application particulièrement intéressante concerne les cartes à puce qui s'appuient sur une mémoire déportée à l'extérieur, typiquement dans un lecteur de cartes ou dans un ordinateur personnel. Dans ce cas les informations contenues dans la mémoire déportée sont chiffrées et/ou authentifiées. La carte à puce (ou plus généralement, le support électronique portable) contient principalement des moyens de traitement (microprocesseur) et des moyens de mémorisation minimum nécessaires. La mémoire déportée contient des informations qui peuvent être du code exécutable ou des données. Lorsque la carte a besoin de ces informations, elle doit les déchiffrer et authentifier au moins une partie de ces informations. On rappelle que l'authentification de données permet de vérifier que les données n'ont pas été manipulées et que l'émetteur de ces données (qui appose"l'authentifiant") est bien celui attendu. Dans l'état de la technique, les procédés de cryptographie mis en oeuvre dans la carte pour déchiffrer et authentifier au vol les données transmises par la mémoire déportée sont très différents. Il faut donc d'abord déchiffrer tout un message puis authentifier une portion au moins de ce message. Pour le chiffrement ou le déchiffrement au vol,"on the fly stream en-/decryption"dans la littérature anglo-saxonne, la solution la plus courante est l'utilisation de registres à décalage pour générer un masque pseudo-aléatoire à partir d'une clé de chiffrement, et à effectuer un ou exclusif bit à bit entre ce masque et le flot de données considéré. Pour l'authentification au vol, on utilise habituellement le CBC-MAC, acronyme anglosaxon pour"Cipher Block Chaining-Message Authentication Code", basé sur l'utilisation de l'algorithme DES pour chaque flot de données, la sortie d'un bloc d'authentification servant dans le bloc d'authentification du flot de données suivant, d'où la notion de"chaîne". Mais le mécanisme de traitement des données utilisé dans les deux opérations ne permet pas que l'on puisse réaliser en parallèle le déchiffrement et l'authentification sur un même flot de données. Ainsi, en pratique, on déchiffre un message en entier, puis on authentifie une portion au moins de ce message, ce qui n'est pas très performant. Dans l'invention, on a recherché un autre procédé de cryptographie au vol qui permette de faire du déchiffrement par flots et de l'authentification en parallèle. Dans l'invention, on a recherché un procédé de cryptographie utilisant un algorithme cryptographique symétrique par flot pour le chiffrement/déchiffrement et pour l'authentification. L'idée à la base de l'invention est qu'en mettant en oeuvre les mêmes mécanismes dans les deux opérations, on va permettre le traitement en parallèle des flots de données à déchiffrer et authentifier. Dans l'invention, on a cherché un moyen d'utiliser de façon performante un algorithme cryptographique faible, tel que le DES ("Data Encryption Standard"), dont la mise en oeuvre est peu coûteuse (en temps de calcul et en besoin mémoire notamment). L'idée à la base de l'invention, est d'augmenter la force cryptographique de cet algorithme en utilisant un mécanisme particulier. Dans l'invention, on a cherché une solution à ces différents problèmes techniques. Telle que caractérisée, l'invention concerne donc un procédé de cryptographie pour la génération d'un nombre pseudo-aléatoire et/ou pour le chiffrement/déchiffrement et/ou pour l'authentification de données, utilisant une clé de chiffrement K et un algorithme cryptographique symétrique par flot, caractérisé en ce qu'il comprend les étapes suivantes : - concaténation d'un index fourni par un compteur avec une première sous-clé, pour former une première donnée de longueur 1, - application de ladite première donnée en entrée d'un bloc de chiffrement correspondant à l'algorithme cryptographique symétrique, avec une deuxième sous-clé de longueur k, pour fournir en sortie une deuxième donnée, - réalisation d'un OU exclusif bit à bit de ladite deuxième donnée avec une troisième clé de longueur l, pour fournir en sortie une donnée pseudoaléatoire fonction de la clé de chiffrement K formée desdites première, deuxième et troisième sous-clés. Ce procédé permet de réaliser le déchiffrement et l'authentification du même flot de message en parallèle. On gagne ainsi du temps et on a une gestion beaucoup plus simple des données de la mémoire déportée, récupérées par la carte à puce. Ce procédé peut utiliser pour le déchiffrement une primitive d'algorithme cryptographique symétrique (code exécutable implémenté dans la carte à puce) déjà implémentée pour l'authentification, ce qui réduit l'espace mémoire nécessaire au code exécutable correspondant, et qui simplifie aussi la mise en oeuvre du procédé (un seul code à tester). En outre, de manière avantageuse, en appliquant en entrée du procédé de déchiffrement selon l'invention, des aléas physiques de la carte, on obtient un générateur d'aléas beaucoup plus fort sur le plan cryptographique, et ce à moindre coût. D'autres caractéristiques et avantages de l'invention sont détaillés dans la description suivante, à titre indicatif et non limitatif et en référence aux dessins annexés dans lesquels : - la figure 1 représente un organigramme de la génération d'un nombre pseudo-aléatoire et du déchiffrement par flot d'un message m selon le procédé de cryptographie au vol de l'invention ; et - la figure 2 représente un organigramme correspondant à une authentification par flot du message m, selon le procédé de cryptographie au vol selon l'invention. Sur la figure 1, on a représenté la séquence de déchiffrement des flots mi et mi+i d'un message m selon le procédé de cryptographie de l'invention, utilisant un bloc de chiffrement E, de taille l, et une clé de chiffrement K de taille supérieure à 1. Le bloc de chiffrement E correspond à un algorithme cryptographique symétrique par bloc. Il s'agit par exemple de l'algorithme DES. La taille du bloc (nombre de bits en entrée et en sortie du bloc) correspond à la longueur du bloc de message mi. Cette séquence comprend la génération d'un nombre pseudo-aléatoire à partir de l'index des blocs de message. Cet index vaut i pour le ième bloc mi du message m. C'est ce nombre pseudo-aléatoire qui sert de masque au flot de message à déchiffrer. La séquence de génération du nombre pseudoaléatoire pour le flot de message mi est la suivante : - concaténation de l'index i, fourni par un compteur non représenté, avec une première sous-clé K2 de la clé de chiffrement, pour former une première donnée Dl= (i//K2) de longueur 1 ; - application de cette première donnée Dl de longueur 1 en entrée d'un bloc de chiffrement E de l'algorithme cryptographique symétrique, avec une deuxième sous-clé Kl de longueur k, pour fournir une deuxième donnée D2=E (Kl, i//K2), - réalisation d'un OU exclusif bit à bit de cette deuxième donnée D2 avec une troisième sous-clé K3 de longueur l, pour fournir une donnée pseudo-aléatoire Daléa-i=F (K, i). Cette donnée pseudo-aléatoire obtenue à partir de la valeur i de l'index est fonction de l'algorithme cryptographique utilisé (bloc de chiffrement ou primitive E) et de la clé de chiffrement K formée des trois sous-clés Kl, K2, K3. Dans la suite, pour la simplicité de l'exposé, le terme" index" peut désigner aussi bien sa fonction que sa valeur. En pratique, l'index et la sous clé K2 ont chacun une longueur de 1/2 bits et la sous clé K3 a une longueur de 1 bits. La force de l'algorithme cryptographique symétrique par flot est donnée par la taille de la clé de chiffrement qu'il utilise. Dans l'exemple, cette force est donnée par la taille k de la sous clé Kl utilisée par le bloc de chiffrement E. On sait calculer que la force cryptographique due à la sous clé K2 est égale à 1/2 ; et que la force cryptographique due à la sous clé K3 est égale à 1/2. Ainsi, la force cryptographique du procédé de cryptographie selon l'invention utilisant une clé de chiffrement K= (K1, K2, K3) en combinaison avec le bloc de chiffrement E devient donc égale à k+l. Ainsi, bien qu'utilisant un algorithme dit faible, on obtient un procédé de cryptographie sûr, à moindre coût. Dans un exemple de réalisation pratique avec un algorithme DES de force cryptographique k égale à 56 bits, on aura 1 typiquement égal à 64 bits. La force cryptographique d'un procédé selon l'invention est alors de 120 bits, avec une clé de chiffrement K de 152 bits. On a vu que la contribution de la sous clé K3 à la force de l'algorithme DES est limitée à 1/2. Aussi, on formera de préférence la sous-clé-K3 à partir d'une clé k3 de taille 1/2, que l'on concatène avec elle-même : K3=k3//k3. On a ainsi un gain de place mémoire correspondant de 1/2 bits (on mémorise k3, mais on utilise K3). On a vu que le procédé de cryptographie au vol selon l'invention fournit une donnée pseudo-aléatoire Daléa-i à partir de l'index des flots de message. Cette donnée pseudo-aléatoire Daléa-i est utilisée pour masquer le flot de message correspondant mi. On réalise donc un OU Exclusif bit à bit, opération notée m, entre cette donnée pseudo-aléatoire et le flot de message à déchiffrer mi. On obtient en sortie, le flot de donnée déchiffré correspondant, dci. Pour le flot de message mi+i suivant, d'index i + 1, on a la même séquence de déchiffrement. Ainsi, de flot en flot, on déchiffre l'ensemble du message m. Le procédé cryptographique qui vient d'être décrit en relation avec la figure 1, comprend ainsi un procédé permettant la génération d'un nombre pseudo-aléatoire Aléa-il à partir d'un simple index, c'est à dire en d'autres termes le contenu d'un compteur incrémenté à chaque nouveau flot de message. Le procédé de déchiffrement comprend la séquence de fourniture de ce nombre pseudo-aléatoire, qui sert de masque au flot de message à déchiffrer, et qui est donc utilisé dans l'opération de OU exclusif bit à bit avec ce flot de message. Ce procédé peut aussi bien être utilisé comme procédé de chiffrement, pour chiffrer un message, par exemple si la carte veut enregistrer une information dans la mémoire déportée. Avantageusement, le nombre pseudo-aléatoire généré selon le procédé de l'invention, peut être utilisé de la même façon que dans le procédé de déchiffrement, mais pour générer un aléa fort, du point de vue cryptographique, à partir d'un aléa faible, typiquement un aléa physique. On entend par aléa physique, un aléa fourni à partir de caractéristiques physiques, telles qu'un champ électromagnétique ou autres. Ces aléas physiques sont liés à la structure physique du circuit qui les génère. Ils sont souvent utilisés dans les cartes à puce. Mais ce sont des aléas faibles sur le plan cryptographique. En appliquant un aléa physique Aléa-@ en entrée à la place d'un flot de message mi, on obtient en sortie un aléa fort Aléa- (pF. Ainsi, le procédé de cryptographie selon l'invention permet trois applications indépendantes : la génération d'un nombre pseudo-aléatoire Daléa-i 1 le chiffrement/déchiffrement par flot de message mi, et la génération d'un aléa fort à partir d'un aléa faible. La figure 2 représente un exemple typique d'un procédé d'authentification au vol du type CBC-MAC. Pour chaque flot d'un message à authentifier, on utilise habituellement le même bloc de chiffrement E avec la même clé d'authentification K4, sauf pour le dernier flot qui doit utiliser soit au moins une clé d'authentification différente et/ou un bloc de chiffrement différent. On peut aussi avoir pour le dernier bloc, l'utilisation d'une combinaison de blocs de chiffrement, dont l'un au moins est différent de celui utilisé pour les blocs précédents. Dans l'exemple, le message à authentifier comprend 1 p blocs de messages mi à mp. La description d'une séquence d'authentification (autre que la dernière) est la suivante : en entrée de la séquence d'authentification, on a le bloc de message mi. Un Ou exclusif bit à bit est réalisé entre ce bloc de message et la donnée d'authentification ai-i fournie par la séquence d'authentification précédente (pour le bloc mi-i. La donnée obtenue est appliquée en entrée du bloc E de chiffrement, utilisant la clé d'authentification K4. En sortie de ce bloc, on obtient une donnée d'authentification correspondante noté ai. Cette donnée d'authentification est fournie à la séquence d'authentification suivante, pour réaliser un Ou exclusif bit à bit avec le bloc de message suivant mi+l. La dernière séquence d'authentification appliquée au dernier bloc de message mp est différente en ce qu'elle utilise par exemple une clé d'authentification différente K5 ; ou qu'elle applique successivement le bloc E de chiffrement avec une première clé, par exemple K4, puis à la suite avec une autre clé, par exemple K5 ; ou encore que le bloc de chiffrement est différent ; ou qu'elle utilise une combinaison de ces différentes variantes. Sur la figure 2, la dernière séquence d'authentification utilise le bloc E de chiffrement avec une clé d'authentification K5, différente de K4, pour le dernier flot de donnée mp. De tels procédés d'authentification par chaîne font partie de l'état de l'art. Mais l'avantage que l'on tire d'un procédé de cryptographie selon l'invention, est qu'après la réception d'un nouveau bloc de message mi, on peut réaliser en parallèle le déchiffrement et l'authentification. En outre, on peut n'utiliser qu'un seul et même bloc E de chiffrement pour les deux procédés, ou un nombre limité de blocs de chiffrement. On gagne ainsi du temps de calcul et de l'espace mémoire de travail et espace mémoire de code exécutable. L'invention qui vient d'être décrite ne se limite pas à une utilisation du DES, comme algorithme cryptographique symétrique par flot. Par exemple, on peut aussi utiliser l'algorithme AES. L'intérêt du DES est qu'il nécessite peu de puissance de calcul et peu d'espace mémoire (code exécutable). Cette invention s'applique dans tous les cas où l'on veut utiliser un algorithme cryptographiquement faible, en général pour des raisons de moyens de traitement limités ou de temps de calcul disponible réduit, tout en ayant un procédé de cryptographie très sûr. Elle s'applique aussi de façon avantageuse dans tous les domaines où l'on cherche à réaliser différentes fonctions indépendantes à moindre coût. On a vu que le procédé de cryptographie permettait à la fois de renforcer un aléa physique, de chiffrer/déchiffrer et authentifier des messages et de générer des nombres pseudo-aléatoires. Cette invention s'applique tout particulièrement dans le domaine des cartes à puce ou plus généralement des dispositifs électroniques portables utilisant une mémoire déportée, qui nécessite le déchiffrement et l'authentification des données contenues dans cette mémoire. REVENDICATIONS 1. Procédé de cryptographie pour la génération d'un nombre pseudo-aléatoire et/ou pour le chiffrement/déchiffrement par flot et/ou pour l'authentification de données, utilisant une clé de chiffrement K et un algorithme cryptographique symétrique par bloc, caractérisé en ce qu'il comprend les étapes suivantes : - concaténation d'un index (i) fourni par un compteur avec une première sous-clé (K2), pour former une première donnée (Dl) de longueur l, - application de ladite première donnée en entrée d'un bloc de chiffrement (E) dudit algorithme cryptographique symétrique, avec une deuxième sous-clé (Kl) de longueur k, pour fournir en sortie une deuxième donnée (D2), - réalisation d'un OU exclusif bit à bit de ladite deuxième donnée avec une troisième clé (K3) de longueur l, pour fournir en sortie une donnée pseudo aléatoire (Daléai) fonction de la clé de chiffrement K formée desdites première, deuxième et troisième sous-clés. 2. Procédé de cryptographie selon la revendication 1, caractérisé en ce que ledit index (i) et ladite deuxième sous-clé (K2) ont une longueur 1/2. 3. Procédé de cryptographie selon la revendication 1 ou 2, caractérisé en ce que ladite troisième sous-clé (K3) est formée par la concaténation de deux fois la même clé (k3) de longueur 1/2. 4. Procédé de cryptographie selon l'une quelconque des revendications précédentes, caractérisé en ce que pour le déchiffrement d'un message m par blocs de longueur l, il comprend pour chaque bloc de message la réalisation d'un OU exclusif bit à bit entre le bloc de message considéré (mi) d'index i et la donnée pseudo-aléatoire (Daiéa-i) calculée à partir dudit index du bloc dans le flot de message. 5. Procédé de cryptographie selon la revendication précédente, caractérisé en ce qu'il comprend pour chaque bloc de message mi à déchiffrer, l'authentification en parallèle dudit bloc de message. 6. Procédé de cryptographie selon la revendication précédente, caractérisé en ce que ladite authentification comprend l'utilisation du même bloc de chiffrement (E) dudit algorithme de cryptographie. 7. Procédé de cryptographie selon la revendication précédente, caractérisé en ce que ladite authentification comprend l'utilisation pour le dernier bloc de message au moins, d'une clé d'authentification différente, et/ou d'un bloc de chiffrement différent dudit algorithme de cryptographie. 8. Procédé de cryptographie selon l'une quelconque des revendications 1 à 3, caractérisé en ce qu'il comprend la réalisation d'un OU exclusif bit à bit de ladite donnée pseudo-aléatoire (Daiea-i) avec un aléa physique (Aléa- (p) pour fournir en sortie un aléa cryptographiquement sûr (Aléa- (pF). 9. Procédé de cryptographie selon l'une quelconque des revendications précédentes, caractérisé en ce que ledit algorithme cryptographique symétrique est le DES. 10. Procédé de cryptographie selon l'une quelconque des revendications précédentes, caractérisé en ce que ledit algorithme cryptographique symétrique est l'AES. 11. Carte à puce ou dispositif électronique portable comprenant des moyens de traitement de données, des moyens de mémorisation et au moins un compteur, caractérisé en ce qu'il met en oeuvre un procédé de cryptographie selon l'une quelconque des revendications précédentes. 12. Carte à puce ou dispositif électronique portable selon la revendication précédente, lesdits moyens de mémorisation comprenant de la mémoire déportée sur un autre support physique, caractérisé en ce qu'elle met en oeuvre ledit procédé de cryptographie pour déchiffrer les informations contenues dans la dite mémoire déportée ou pour authentifier une portion au moins de ces informations.