Brevet FR2780835A1 — publié le 20000107

CRYPTOSYSTEME A TEST D'ARRET SIMPLE ALEATOIRE. La présente invention concerne le domaine des cryptosystèmes. Les cryptosystèmes sont utilisés pour différentes applications. Un cryptosystème est souvent utilisé pour le chiffrement d'un message. Le but est alors d'interdire à un tiers ne disposant pas de la clé de déchiffrement de comprendre le message. Un cryptosystème peut également remplir une tâche d'authentification. L'authentification peut porter sur une partie à une transaction, par exemple l'émetteur ou le destinataire d'une information, par exemple pour la certification de l'origine d'un message, ou pour l'authentification d'une personne souhaitant accéder à un lieu, un équipement ou une information à accès contrôlé. Un cryptosystème peut encore être utilisé pour la certification de l'intégrité d'un message. Le but est alors d'interdire à un intrus d'altérer un message, ou de faire passer un message ayant l'apparence d'un message légitime. Le but d'un cryptosystème est de rendre difficile la cryptanalyse, c'està-dire l'attaque du cryptosystème par une personne ne détenant pas la clé de déchiffrement, tout en préservant une grande ergonomie et notamment une rapidité d'exécution des fonctionnalités par le titulaire légitime d'une clé. Il est fréquent qu'un cryptosystème utilise un moyen de vérification standardisé, par exemple un algorithme de type DES personnalisé par une clé spécifique dont la probabilité de découverte est extrêmement faible. De tels cryptosystèmes permettent d'échanger des informations ou de réaliser des transactions ou des contrôles à l'intérieur 2 2780835 d'une vaste communauté d'utilisateurs autorisés, de gérer facilement la remise, la destruction ou l'invalidation de clés, tout en interdisant ces fonctions à une communauté potentiellement plus vaste encore de cryptanalystes indésirables. L'homme du métier, et même l'expert, considèrent dans l'état technique qu'il n'existe que deux paramètres déterminant la vitesse d'une attaque exhaustive: 1.le nombre de clés à tester 2. la vitesse de chaque test. Le nombre de clés à tester dépend directement de l'entropie de la clé. En première approximation, un cryptosystème à clés de 56 bits autorise 256 clés possibles, soit environ dix mille millions de millions de clés. Pour cette raison, certaines législations réglementent la longueur maximale des clés autorisées, afin de conserver à l'autorité judiciaire la capacité de procéder avec une vitesse acceptable à la cryptanalyse d'un message potentiellement condamnable. Le deuxième paramètre est celui de la vitesse d'exécution de chaque test. Cette vitesse dépend d'une part du principe mise en oeuvre par le cryptosystème, et d'autre part de la puissance de calcul des moyens de cryptanalyse. L'article " Exhaustive Cryptanalysis of the NBS Data Encryption Standard (DES) " paru dans la revue COMPUTER vol. , N 6, P.74-84 en juin 1997 expose par exemple que si l'on utilise une machine composée d'un million de processeurs susceptibles chacun de tester un million de clés par secondes, l'attaque exhaustive d'une clé de 56 bits pourrait être réalisée en 20 heures, et celle d'une clé de 64 bits en 213 jours. Dans le cas d'une attaque par des solutions logicielles, on admet généralement que le temps nécessaire 3 2780835 est 1000 fois supérieur à celui d'une machine dédiée similaire à celle mentionnée dans l'exemple précédent. Selon un principe connu sous le nom de " Loi de MOORE ", la puissance de calcul des ordinateurs double tous les 18 mois, et la seule solution pour empêcher l'attaque trop rapide d'un cryptosystème consiste, selon l'état de la technique, d'augmenter l'entropie des clés utilisées. La longueur de la clé est, pour les cryptosystèmes de l'état de la technique, directement fonction de la sécurité recherchée. Pour une information dont la durée de validité critique est de quelques jours seulement, une clé courte est suffisante. De même, pour contrôler l'accès à un équipement ou un fichier dont la clé est modifiée chaque jour ou chaque semaine, une clé courte peut être suffisante. Par contre, pour la certification d'un document pour laquelle la vérification de l'authenticité ou de la signature doit être possible pendant plusieurs années, ou pour préserver des secrets ayant une grande durée de validité, il est nécessaire d'utiliser des clés présentant une entropie suffisante non seulement par rapport à la puissance de calcul de cryptanalyse disponible au moment du chiffrement, mais aussi pour tenir compte de l'augmentation prévisible de la puissance de calcul. L'augmentation de l'entropie des clés présente un inconvénient. Elle rend l'utilisation du cryptosystème peu ergonomique pour l'utilisateur légitime et laborieux le déchiffrement par le détenteur légitime d'une clé. À titre d'exemple, le déchiffrement d'un message chiffré avec un algorithme RSA avec une clé à 128 bits peut prendre plusieurs dizaines de secondes, temps qui peut être difficilement supportable voire excessif pour certaines applications. 4 2780835 Le but de la présente la présente invention est de remédier à cet inconvénient en proposant un cryptosystème présentant une grande résistance à la cryptanalyse tout en autorisant une utilisation généralement rapide par le détenteur de la clé. À cet effet, l'invention concerne un cryptosystème comprenant un moyen de ralentissement de la vérification de la clé entrant en fonction de façon aléatoire, de préférence avec un état de sortie pendant la phase de vérification correspondant à une clé non conforme de telle sorte que le cryptanalyste n'aura aucune indication quant au déroulement de la phase de vérification. De manière préférentielle, le cryptanalyste ne saura pas exactement quand la vérification est achevée. La sortie pourra aussi être définie de manière aléatoire, si la clé n'est pas valide. Un tel cryptosystème peut être réalisé aussi bien sous forme logicielle que sous forme matérielle. Dans ce dernier cas, la réalisation peut prendre la forme d'un circuit électronique, d'un circuit intégré spécifique voire une forme mécanique. L'effet technique produit par l'invention est une amélioration importante de la sécurité du cryptosystème sans augmentation du temps de déchiffrement. Le cryptanalyste devra attendre pour le test de chaque clé un temps au moins égal à celui de la durée maximale de vérification intervenant lorsque le moyen de ralentissement est en fonction. La recherche systématique de clé est de ce fait considérablement plus lente qu'avec les cryptosystèmes de l'état de la technique. L'utilisateur autorisé, par contre, pourra procéder au déchiffrement à la vitesse maximale dans la quasi-totalité des cas, hormis lorsque, par exception, le moyen de ralentissement aléatoire 2780835 entre en fonction. Seulement dans ce cas exceptionnel, il subira l'inconvénient d'un temps d'attente pour le déchiffrement. Il est toutefois possible de paramétrer la fréquence d'entrée en fonction du moyen de ralentissement de façon à ce que la probabilité de ralentissement pour l'utilisateur autorisé soit très faible, mais que la probabilité par rapport au nombre de clés à tester soit très élevée. À titre d'exemple, pour un cryptosystème à clés de 56 bits, il existe 1016 clés possibles. Si ce cryptosystème est destiné à être utilisé une fois par heure, par exemple pour le contrôle d'un accès ou de l'authenticité d'un utilisateur, une probabilité de ralentissement d'une chance sur quatre millions produira le ralentissement du test systématique de clé environ deux mille millions de fois. Elle obligera le cryptanalyste à ralentir considérablement sa vitesse de soumission de clés à tester, alors que l'utilisateur légitime aura plus de chance de gagner le gros lot à la loterie américaine que de subir un ralentissement dans l'utilisation légitime de sa clé. Si le ralentissement aléatoire présent une durée maximale d'une seconde, l'inconvénient pour l'utilisateur légitime sera supportable, mais imposera, pour le cryptanalyste, un délai du même ordre de grandeur que la vie estimée de l'univers. L'invention présente par ailleurs la particularité de permettre un paramétrage facile pour arbitrer entre la résistance à la cryptanalyse d'une part, et le confort d'utilisation légitime d'autre part. Selon un mode de réalisation préféré mais non exclusif, les moyens de vérification de clé sont indissociablement liés au moyen pour effectuer la tâche soumise à autorisation. Cette variante peut notamment être mise en oeuvre sous la forme d'un circuit intégré dédié 6 2780835 comportant un circuit d'interface pour l'entrée d'une clé, et un circuit d'interface de sortie délivrant le résultat du traitement, par exemple les signaux pour la visualisation d'une information déchiffrée ou un signal d'autorisation. Selon une application particulière de l'invention, le cryptosystème est destiné au chiffrement d'une information et en ce que les moyens de chiffrement et les moyens de déchiffrement sont identiques. Selon un exemple de mise en oeuvre, le cryptosystème comporte une mémoire tampon temporisée par un générateur de temps aléatoire interposée dans la chaîne de vérification. Tous les dispositifs décrits ci-après visent à rendre aléatoire le temps nécessaire pour l'authentification d'une personne habilitée, de façon à ce qu'une personne ne disposant pas des clefs d'habilitation ne puisse éliminer aucune clef à coup sûr en un temps fini. On observera que les dispositifs décrits ci-après sont tels que la fraudeur ne gagne rien à adopter une stratégie " diagonale " de tests de plus en plus longs, car chaque nouveau test démarre nécessairement à zéro. Les temps d'authentification pour l'utilisateur habilité peuvent être ajustés, tant en termes de valeurs moyennes qu'en termes de variance; une variance plus élevée, à valeur moyenne donnée, compliquera singulièrement la tâche d'un fraudeur éventuel, car, pour éliminer une clef avec une probabilité significative, il devra généralement la tester pendant un temps égal à la valeur moyenne majorée de plusieurs fois l'écart type. Un premier dispositif consiste à ce que le processus de vérification soit une promenade aléatoire (approximation du mouvement brownien ou intégrale stochastique plus sophistiquée) dans un sous- espace à n 7 2780835 dimensions. Chaque clef définit, par exemple un sous-espace de dimension 2 et un point de départ. Sachant qu'un mouvement brownien en dimension 2 a une probabilité 1 d'atteindre n'importe quel voisinage, la définition d'un tel voisinage dans l'espace à n dimensions conduira l'utilisateur à une certitude d'authentification au bout d'un délai aléatoire, fonction en moyenne de la taille relative du voisinage. Dans ce dispositif, la zone cible peut elle-même être dépendante de l'utilisateur légitime considéré, définie par exemple par ses caractéristiques publiques (nom, numéro de carte...) Une variante de ce même dispositif consiste à simuler un processus stochastique sur une sous-variété de l'espace à dimension n (par exemple un plan), aux formes éventuellement très contournées, de sorte qu'une petite variation de la position initiale de diffusion puisse induire de fortes variations de trajectoires. Dans le même esprit, des caractéristiques propres aux processus aléatoires choisis (direction privilégiée de diffusion, rotations locales etc...) peuvent faire partie des clefs d'identification publique ou cachée. Une seconde variante du dispositif proposé consiste à ne plus rechercher la coïncidence aléatoire entre un point mobile aléatoire et un point cible, mais la coïncidence entre le polygone défini par plusieurs points évoluant aléatoirement sur la sous-variété considérée et un polygone ou une famille de polygones prédéterminés. Cette approche pourra être particulièrement intéressante si la sous-variété support peut être mise en rapport avec des caractéristiques physiques de la personne à identifier. Ainsi la reconstitution en trois dimensions d'un visage à partir de deux caméras placées devant un distributeur pourrait constituer en elle-même la sous-variété support du processus aléatoire; le passage par un polygone semblable à un 8 2780835 polygone prédéterminé et précodé dans la carte de crédit fournirait alors le test aléatoire requis. De la même façon, un système de codage quelconque à partir d'empreintes digitales (par exemple premières transformées de Fourier longitudinales et latérales pour obtenir une invariance par translation) pourra être utilisée pour générer une sous- variété sur laquelle se déplacera un processus aléatoire, sans qu'il soit nécessaire que cette sous-variété ait une quelconque ressemblance directe avec les formes définies par les empreintes. Une application homologue, en prenant pour support l'image de l'oeil serait tout aussi concevable. Dans le même esprit enfin, des sous-variétés réelles ou virtuelles pourraient être intégrées à des dispositifs physiques d'identification. Le cryptosystème selon l'invention sera installé de préférence dans un moyen scellé physiquement. Pour cela, il pourra être installé dans une mémoire électronique scellée physiquement, sous forme de carte à mémoire ou de composant intégré ou hybride encapsulé d'une façon irréversible interdisant l'accès au circuit sans destruction. 9 2780835 REVENDICATIONS 1 - Cryptosystème comprenant des moyens de vérification de clé préalablement à l'exécution d'une fonction caractérisé en ce qu'il comprend un moyen de ralentissement de la vérification de la clé entrant en fonction de façon aléatoire. 2 - Cryptosystème selon la revendication principale caractérisé en ce que la sortie est aléatoire dans le cas d'une clé non conforme. 3 - Cryptosystème selon la revendication 1 ou 2 caractérisé en ce que l'état de la sortie du cryptosystème corresponde est indéterminé pendant l'étape de vérification de façon à ce que le cryptanalyste ne soit pas en mesure de déterminer la fin de l'étape de vérification. 4 - Cryptosystème selon la revendication 1 ou 2 caractérisé en ce que l'état de la sortie du cryptosystème corresponde, pendant l'étape de vérification de durée aléatoire, à l'état de sortie correspondant à l'utilisation d'une clé non conforme. 5 - Cryptosystème selon l'une au moins des revendications précédentes caractérisé en ce que les moyens de vérification de clé sont indissociablement liés au moyen pour effectuer la tâche soumise à autorisation. 6 - Cryptosystème selon l'une au moins des revendications précédentes caractérisé en ce qu'il est destiné au chiffrement d'une information et en ce que les moyens de chiffrement et les moyens de déchiffrement sont identiques. 7 Cryptosystème selon l'une au moins des revendications précédentes caractérisé en ce qu'il comporte une mémoire tampon temporisée par un générateur de temps aléatoire interposée dans la chaîne de vérification. 2780835 8 - Cryptosystème selon l'une au moins des revendications précédentes caractérisé en ce qu'il est installé dans un circuit électronique scellé. 9 - Cryptosystème selon l'une au moins des revendications précédentes caractérisé en ce qu'il est installé dans un circuit électronique encapsulé physiquement par un moyen interdisant l'accès au circuit sans destruction.