Brevet FR2739469A1 — publié le 19970404

PROCÉDÉ DE CRYPTOGRAPHIE A CLÉ PUBLIQUE BASÉ SUR LE LOGARITHME DISCRET La présente invention a pour objet un procédé de cryptographie dite à clé publique basé sur le logarithme discret faisant intervenir le calcul d'une grandeur modulo p. Elle trouve une application dans la génération de signatures numériques de messages, ou dans une cession d'authentification entre deux entités Dans de telles procédures, la sécurité est fondée sur l'extrême difficulté qu'il y a à inverser certaines fonctions et plus particulièrement le logarithme discret. Ce problème consiste, étant donné la relation mathématique y = gx modulo p que l'on notera par la suite y = gX modp (qui signifie y est le reste de la division de gx par p), à retrouver x lorsque l'on connaît p, g et y. Ce problème est impossible à résoudre, en l'état actuel des connaissances, dès que la taille p atteint ou dépasse 512 bits et que celle de x atteint ou dépasse 128 bits. Dans de tels systèmes, il existe en général une autorité qui fournit le nombre p de grande taille, constituant le module. L'autorité choisit également un entier g, appelé base tel que l'ensemble engendré par g ctest-à-dire l'ensemble formé des nombres gx modp, pour x appartenant à l'intervalle [0, p-l] soit un sous-ensemble de taille maximale, au moins 2128. Les paramètres p et g sont dits "publics" c'est-adire qu'ils sont fournis par l'autorité à tous les utilisateurs rattachés à cette autorité. Selon certaines variantes, ces paramètres sont choisis individuellement par chaque utilisateur et font, dans ce cas, partie intégrante de sa clé publique. Un inconvénient majeur à la mise en oeuvre de systèmes cryptographiques réside dans la nécessité d'avoir des moyens de calcul et de mémorisation relativement importants du fait des calculs complexes qui sont réalisés. En effet, le calcul de la grandeur gkmodp consiste à réaliser des multiplications modulaires et cela est coûteux en temps de calcul et en place mémoire. Dans des dispositifs électroniques simples n'utilisant que des microprocesseurs standards, ce type d'opération n'est guère réalisable. Pour des dispositifs électroniques possédant un processeur spécialisé pour ce type de calcul, il est malgré tout souhaitable de limiter, le temps de calcul et la place mémoire nécessaire pour les résultats intermédiaires. En effet, le calcul de la grandeur gkmodp est en général relativement coûteux par la méthode classique du 11carré-multiplié'1 connue sous l'abréviation anglosaxonne SQM (Square-Multiply) puisqu'il équivaut en moyenne à 3/2 Log2(p) multiplications. Selon cette méthode on calcule toutes les puissances de g c'est à dire, lorsque k est de longueur n bits, tous les carrés g2 , g2 , .. g2 n Selon la méthode du "carré multiplié" simple gk requiert n/2 multiplications et n carrés. Une méthode proposée par E. BRICKELL et al. dénommée par l'abréviation BGCW permet de réduire le nombre de multiplications dans le cas de la méthode du carré-multiplié mais introduit un besoin de stockage de nombreuses constantes précalculées et donc la nécessité de disposer d'une quantité de mémoires de stockage très pénalisante. La présente invention a pour objet de remédier à tous ces inconvénients. Elle permet d'apporter une solution souple et peu onéreuse en temps de calcul et en place mémoire à la mise en oeuvre d'algorithmes cryptographiques pour tous systèmes de cryptographie et en particulier par des appareils portables du type carte à puce à microprocesseur. Selon l'invention deux solutions sont proposées. Les deux solutions sont basées sur un principe commun consistant à constituer une base de données de valeurs aléatoires et à combiner ces valeurs pour déterminer des exposants k servant aux échanges entre deux entités. Avec les deux solutions proposées, le calcul d'un exposant k requiert moins de 30 multiplications modulaires pour un espace mémoire tout à fait acceptable pour des supports tels que les cartes à puce. L'invention a plus particulièrement pour objet un procédé de cryptographie à clé publique basé sur le logarithme discret faisant intervenir le calcul de la grandeur r = gk modp ou p est un nombre premier appelé module, l'exposant k un nombre aléatoire habituellement de longueur N bits et g un entier appelé base, dans lequel une entité E réalise des opérations d'authentification et/ou de signature, comprenant des échanges de signaux avec une autre entité dans lesquels intervient cette grandeur, caractérisé en ce qu'il comporte les étapes suivantes pour une entité donnée - former une base de données contenant un nombre fixe d'exposants et les puissances correspondantes, puis pour chaque échange de signaux:: - générer un exposant en opérant une combinaison linéaire aléatoire des valeurs d'exposant de la base, - et calculer la puissance de g à partir des puissances de la base entrant dans la combinaison. Selon un premier mode de réalisation, les étapes consistent à: - former une base de données fixe contenant m valeurs xi aléatoires et les grandeurs correspondantes Zi telles que Zi = gxi modp, - générer un exposant k nécessaire à chaque signature en opérant une combinaison linéaire aléatoire des valeurs xi de la base, - calculer la grandeur gk modp à partir des grandeurs Zi relatives aux valeurs xi intervenant dans la combinaison, - utiliser cette grandeur dans les échanges de signaux avec une autre entité. Selon un deuxième mode de réalisation, les étapes consiste à : - former une base de données évolutive contenant n valeurs aléatoires d'exposants et leur puissance (ki, gki modp) - générer un nouvel exposant k nécessaire à une signature en opérant une combinaison linéaire aléatoire des n valeurs ki - calculer la grandeur gki+l modp en réalisant le produit des puissances de gk de la combinaison linéaire, - mettre à jour la base des exposants et des puissances, - utiliser cette grandeur dans les échanges de signaux avec une autre entité. D'autres particularités et avantages de l'invention apparaîtront à la lecture de la description qui est faite et qui est donnée à titre d'exemple illustratif et non limitatif en regard des dessins qui représentent - la figure 1, un schéma de principe d'un système apte à mettre en oeuvre l'invention, - la figure 2, un schéma fonctionnel représentant les étapes essentielles du procédé selon l'invention, - la figure 3, le schéma fonctionnel selon un premier mode de réalisation, - la figure 4, le schéma fonctionnel selon un deuxième mode de réalisation. On a représenté sur la figure 1, un schéma de principe d'un système de mise en oeuvre du procédé de cryptographie objet de l'invention. Ce système est formé d'une entité El désirant effectuer des échanges de signaux électroniques avec au moins une autre entité E2. les deux entités sont munies respectivement d'une unité de traitement (CPU) 11, 30, d'une interface de communication, d'une mémoire vive (RAM) 13, 32 et/ou d'une mémoire non inscriptible (ROM) 14, 34 et/ou d'une mémoire non volatile inscriptible ou réinscriptible (EPROM ou EEPROM) 15, 33 et un bus d'adresses, de données, de contrôle 16, 35. L'unité de commande de traitement et/ou la ROM contiennent des programmes ou des ressources de calcul correspondant à l'exécution des étapes de calcul intervenant dans le procédé objet de l'invention, c'est-à-dire lors d'une session d'authentification ou lors de la génération d'une signature électronique ou au cours des quelles les deux entités s'échangent des signaux électroniques. L'unité de traitement ou la ROM possèdent les ressources nécessaires à des multiplications, additions et réductions modulaires. De même que l'unité de traitement et/ou la ROM comportent les fonctions de cryptographie utilisées propres à chaque algorithme de cryptographie et les paramètres g et p, nécessaires au calcul et fixés un fois pour toute pour la suite. Les exposants xi selon le premier mode ou ki selon le deuxième mode pourront être chargés au préalable dans une mémoire réinscriptible, par l'autorité ou, générés à partir d'un générateur aléatoire et d'une valeur aléatoire source x0 (ou kg) secrète. Chaque entité El, E2 possède en outre une clé secrète x et la clé publique y. L'invention s'applique tout particulièrement aux systèmes à cryptographie mis en place dans le domaine bancaire où une grande sécurité est requise lors de transactions opérées sur les comptes. C'est aussi le cas où l'on désire authentifier l'envoi de messages transmis sous forme de signaux électroniques envoyés par une autre entité. C'est aussi le cas où l'on a besoin de signer des messages lors d'échanges de signaux avec une autre entité. En pratique, l'entité désireuse de réaliser une transaction pourra être, par exemple, une carte à circuit intégré telle qu'une carte à puce et l'entité destinataire sera alors un terminal bancaire. La suite de la description va être faite dans le cadre de l'application du procédé à la signature de messages numériques, étant bien entendu que l'invention s'applique à tout système de cryptographie basé sur le logarithme discret. La figure 1, illustre les étapes essentielles du procédé. Selon l'invention on forme une une base de données contenant un nombre fixe d'exposants et les puissances correspondantes, puis pour chaque échange de signaux: - on génère un exposant en opérant une combinaison linéaire aléatoire des valeurs d'exposant de la base, - et on calcule la puissance de g à partir des puissances de la base entrant dans la combinaison. Le procédé selon l'invention propose deux solutions reposant toutes deux sur la formation (ou constitution) de cette base de données. Selon le premier mode de réalisation la base est fixe et est formée d'un ensemble de m couples (xi, Zi). Les données xi sont des nombres aléatoires obtenus comme dit précédemment par un générateur de nombres aléatoires ou pseudo-aléatoires. La longueur de ces nombres est celle d'un exposant k et est la même pour tous ( soit N bits ). Les grandeurs z i sont le résultat d'un calcul préalable tel que Xi Zi = g modp. La longueur des grandeurs Zi est celle du modulo p. Lorsque l'entité El possède cette base de données B = [(x0 Zo) ... (Xm-lt Zm-1)], elle peut échanger des signaux avec une autre entité en faisant intervenir par exemple une signature DSA (r, s) telle que r = gk modp dans laquelle k a été généré à partir des données de la base B. Ainsi selon l'invention, l'entité génère un exposant k lorsque cela est nécessaire et elle le fait en réalisant une combinaison linéaire aléatoire des valeurs xi de la base. L'entité calcule ensuite la grandeur gkmodp correspondante. Pour la génération de l'exposant k, l'entité procède de la manière suivante - l'entité génère une séquence de valeurs ai: (aO, ..., am-1) qui sont des nombres entiers aléatoires tels que 0 ' ai ' h et parmi lesquels w valeurs seulement sont non nulles. - l'entité génère k de sorte que - l'entité calcule ensuite la grandeur gkmodp en opérant les multiplications des puissances de g données par les valeurs zi relatives aux xi qui entrent dans la combinaison linéaire. En pratique les xi entrant dans la combinaison linéaire sont ceux pour lesquels le coefficient ai est non nul. On utilise l'algorithme de BRICKELL et al. pour réaliser ce calcul, mais le nombre de multiplications est désormais (h/h+l) w + h-2 au lieu de (h/h+l) m + h-2. Le nombre w est fixé par rapport à la sécurité requise et conduit aux résultats suivants pour des valeurs de m et h m=32, w=24 et h=8 m=64, w=20 et h=6 Ces valeurs sont données à titre d'exemple et on peut envisager diverses combinaisons dès lors que l'on respecte les contraintes de sécurité. Dans le cas où m=64 et w=20, le nombre de multiplications nécessaires selon l'invention est de 34 alors qu'avec une méthode telle que BRICKELL on aurait 60 multiplications à réaliser. Pour m=32, on stocke par conséquent 32 nombres de taille du module p soit 512 à 1024 bits suivant le cas et 32 nombres de 160 bits (N=160). Les m couples (xi, Zi) seront stockés en mémoire EEPROM dans le cas où l'entité est une carte et cela de façon protégé par les méthodes habituelles de blindage et analogue. La deuxième solution proposée selon l'invention consiste à former une base de données évolutive à partir de n valeurs aléatoires d'exposants ki, i=l à n et de leur puissance gki modp. Une première nouvelle valeur d'exposant ki+1 est ensuite obtenue par combinaison linéaire aléatoire des exposants de la base. Le calcul de la grandeur gki+i correspondant à ce nouvel exposant est effectué. Ce nouveau couple est introduit dans la base de données en remplacement du premier. Un exposant k nécessaire à une signature est obtenu par combinaison linéaire de tous les autres exposants de la base et le contenu de la base est modifié à chaque nouvelle génération d'un exposant. En effet, on remet à jour la base en remplaçant le premier couple par le dernier obtenu. Ainsi à l'instant t, la base est de la forme: (( k0, gko modp ), ( k1, gki modp ) ),.... , ( kt, gkt modp )) on calcule alors kt+1 et on met à jour la base qui devient: (( k1, gki modp ), ( k2, gk2 modp ) ),.... kt, ( kt, gkt modp ), ( kt+1, gkt+l modp )) le processus se répète à chaque calcul d'un nouveau k dans la séquence pseudo aléatoire. Chaque exposant de la base est une combinaison linéaire exprimé pour la relation suivante avec h-l = n dans laquelle les coefficients ai sont des nombres entiers positifs, aléatoires. Les nombres aléatoires sont obtenus à partir d'une séquence fixe aO, ..., ah 1 sur laquelle on effectue une permutation aléatoire. Ainsi, la génération d'un exposant kt+l peut s'exprimer par la relation suivante kt+l = ljk(t+i(hl) ..., kti étant une fonctionnelle linéaire ( linear functional à à coefficients entiers, choisie au hasard parmi L fonctionnelles Les coefficients ai sont des petites puissances de 2. On choisit des valeurs prises entre 1 et 2f avec f ayant une taille qui permet une implémentation efficace. On choisira par exemple f=7 afin de rester cohérent avec les valeurs proposées par l'algorithme de Schnorr. On prendra donc la suite 0, ..., ah~l comme une permutation aléatoire de la séquence (1, 2, ...,27). Les coefficients des combinaisons linéaires doivent être inférieurs à une valeur seuil b pour éviter des attaques et conserver les kt uniformément distribués et (h-1) -indépendant. En considérant h et L=bh, on suggère les valeurs h=8 et b=4 et on fixe L=l, ..., b}h. La taille des nombres k est généralement de 160 bits. Dans ce cas le nombre de multiplications modulaires intervenant selon le procédé de l'invention est nettement inférieur au nombre de multiplications généralement constaté dans l'état de l'art actuel. En effet il est pour les valeurs retenues, inférieur à 30. REVENDICATIONS 1. Procédé de cryptographie à clé publique basé sur le logarithme discret faisant intervenir le calcul de la grandeur r = gk modp ou p est un nombre premier appelé module, k un nombre aléatoire habituellement de longueur N bits et g un entier appelé base, dans lequel une entité E réalise des opérations d'authentification et/ou de signature, comprenant des échanges de signaux avec une autre entité dans lesquels intervient cette grandeur, caractérisé en ce qu'il comporte les étapes suivantes pour une entité donnée - former une base de données contenant un nombre fixe d'exposants et les puissances correspondantes, puis pour chaque échange de signaux: - générer un exposant en opérant une combinaison linéaire aléatoire des valeurs d'exposant de la base, - et calculer la puissance de g à partir des puissances de la base entrant dans la combinaison. 2. Procédé de cryptographie à clé publique selon la revendication 1, caractériser en ce que les étapes consistent à - former une base de données fixe contenant m valeurs xi aléatoires et les grandeurs correspondantes zi telles que z1 = gxi modp, - générer un exposant k nécessaire à chaque signature en opérant une combinaison linéaire aléatoire des valeurs xi de la base, - calculer la grandeur gk modp à partir des grandeurs Zi relatives aux valeurs xi intervenant dans la combinaison, - utiliser cette grandeur dans les échanges de signaux avec une autre entité. 3. Procédé de cryptographie selon la revendication 2, caractérisé en ce que la génération des grandeurs k comporte les étapes suivantes - générer un exposant k tel que k = àixi et tel que l'on ait w des m valeurs ai non nulles, le choix des ai non nuls étant obtenu de façon aléatoire, - calculer la grandeur gkmodp en utilisant les valeurs zi correspondant aux valeurs xi qui entrent dans la combinaison linéaire de k. 4. Procédé de cryptographie selon la revendication 2, caractérisé en ce que pour former la base de données dans une entité, on effectue les étapes suivantes - générer m valeurs aléatoires xi de N bits à partir d'un générateur pseudo-aléatoire, et d'une valeur initiale secrète x0, - calculer la grandeur zi = gxi modp en réalisant le produit des puissances de g modulo p entrant dans la combinaison linéaire selon laquelle peut être décomposée une valeur xi, - stocker en mémoire non volatile de l'entité les m couples (xi, Zi) 5.Procédé de cryptographie à clé publique selon la revendication 1, caractérisé en ce que les étapes consistent à: - former une base de données évolutive contenant n valeurs aléatoires d'exposants et de leur puissance ( ki, gki modp) - générer un nouvel exposant k nécessaire à une signature en opérant une combinaison linéaire aléatoire des n valeurs ki de la base, - calculer la grandeur gki+i modp en réalisant le produit des puissances de g entrant dans la combinaison linéaire, - mettre à jour la base en remplaçant un couple par ce nouveau couple, - utiliser cette grandeur dans les échanges de signaux avec une autre entité. 6. Procédé de cryptographie selon la revendication 5, caractérisé en ce que pour un exposant kt de la base, cet exposant est une combinaison linéaire de la forme avec h-l = n et dans laquelle les coefficients ai sont des nombres entiers positifs aléatoires. 7. Procédé de cryptographie selon la revendication 5, caractérisé en ce que les coefficients ai, i = 0 à h-l sont obtenus par une permutation aléatoire d'une séquence fixe. 8. Procédé de cryptographie selon la revendication 6, caractérisé en ce qu'un nouvel exposant kt+1 est une combinaison linéaire des autres exposants s'exprimant par la relation kt+l = It(kt+i-(h-1)..., kt), et lt une fonctionnelle linéaire. 9. Procédé de cryptographie selon l'une quelconque des revendications précédentes caractérisé en ce qu'il peut être mis en oeuvre pour des cartes à microprocesseur.