Brevet FR2754659A1 — publié le 19980417

La présente invention concerne des systèmes de chiffrage à clés publiques. Les systèmes de chiffrage à clés publiques utilisent une clé privée et une clé publique pour établir un échange d'information sûr. Les clés sont reliées mathématiquement d'une manière telle que l'une peut être utilisée pour chiffrer un message et l'autre pour récupérer un message. Un système typique utilise une clé privée à long terme et une clé publique correspondante qui est typiquement authentifiée par une autorité de certification pour indiquer le possesseur de la clé, et une clé à court terme ou de session privée pour chiffrer avec la clé publique correspondante un message particulier. Les clés peuvent être utilisées pour cacher le contenu du message comme dans un protocole de chiffrage, ou peuvent être utilisées pour authentifier un message, comme dans un protocole de signature numérique. La clé privée est typiquement un entier d'une longueur prédéterminée et la clé publique est obtenue en opérant sur l'entier selon une fonction connue. L'une des techniques établies les plus robustes consiste à élever un générateur d'un groupe multiplicatif à une puissance égale à l'entier et à se fonder, pour maintenir le secret de l'entier, sur l'irrésolvabiliité du problème des logs discrets. Selon une mise en oeuvre particulièrement avantageuse d'un tel système, l'entier peut être utilisé comme multiplicateur d'un point sur une courbe elliptique dans un champ fini, le point résultant étant utilisé comme clé publique. Cette élévation à une puissance assure que la clé privée ne peut pas être dérivée de la clé publique, pourvu que le champ sous-jacent soit de dimensions suffisantes. Alors que la clé privée ne peut pas être dérivée d'un examen unique de la clé publique, d'autres attaques peuvent être montées sur la base d'un examen d'un grand nombre de messages. La sélection de la clé privée est donc importante dans la sécurité d'ensemble du système et elle est particulièrement importante dans les protocoles qui mettent à jour sur une base régulière la clé privée à court terme. Toute corrélation entre des clés publiques successives peut donner la clé secrète et rendre donc vulnérables les transmissions. Afin que la clé privée soit acceptable, elle doit donc être à la fois unique et impossible à prédire. On suppose normalement qu'un nombre engendré de façon aléatoire répond à ces critères, mais on peut montrer qu'il existe une probabilité relativement élevée que le même entier soit sélectionné de façon aléatoire, ce que l'on appelle la "surprise de l'anniversaire". Par conséquent, un contrôle des messages peut donner une clé commune à partir de laquelle la clé privée peut être dérivée. C'est donc un but de la présente invention que de fournir un procédé et un appareil de sélection d'un entier à utiliser comme clé privée. Pour atteindre ce but, l'invention fournit, selon un premier aspect, un procédé de génération d'un entier à utiliser comme clé privée dans une méthode de chiffrage à clé publique, caractérisé en ce qu'il comprend les étapes consistant à: utiliser comme premier composant une sortie d'un séquenceur afin de fournir un élément unique audit entier, utiliser comme deuxième composant un entier engendré de façon aléatoire, et combiner ledit premier composant et ledit deuxième composant pour réaliser un entier unique et impossible à prédire. Lesdits premier et deuxième composants peuvent être concatérés. Dans ce cas, ledit premier composant peut précéder ledit deuxième composant. Ledit deuxième composant peut être utilisé pour régler ledit séquenceur. Ladite sortie dudit séquenceur peut être permutée avant d'être utilisée pour former ledit premier composant. Dans ce cas, ladite permutation peut être effectuée par un algorithme de chiffrage. Ledit séquenceur peut être un compteur qui incrémente et, dans ce cas, ledit compteur peut incrémenter de façon uniforme ou de façon non uniforme. Selon un deuxième aspect, l'invention réalise un appareil de génération d'une clé privée à utiliser dans une méthode de chiffrage à clé publique comprenant un dispositif de comptage pour fournir un entier non répétitif variant progressivement, caractérisé en ce qu'il comporte une première sortie, un générateur de nombres pour engendrer des nombres d'une manière impossible à prédire, et une deuxième sortie, et une unité arithmétique pour recevoir lesdites sorties et combiner ledit entier et ledit nombre pour produire un entier spécial et impossible à prédire, et un dispositif de sortie pour récupérer de ladite unité arithmétique ledit entier à utiliser comme clé privée. Ladite unité arithmétique peut inclure un registre à décalage pour recevoir lesdites sorties. Dans ce cas, lesdites sorties peuvent être concatérées. Ladite unité arithmétique peut inclure un dispositif de permutation, ladite première sortie y étant connectée. Dans ce cas, ledit dispositif de permutation peut être connecté audit registre à décalage. Les buts, particularités et avantages de l'invention seront mieux compris à la lecture de la description qui suit de trois modes de réalisation de l'invention, donnés à titre d'exemple, et en se référant aux dessins annexés et dans lesquels: la Figure 1 est une représentation schématique d'un système de communication de données; la Figure 2 est une représentation de l'entier; la Figure 3 est une représentation schématique de l'appareil utilisé pour engendrer un entier à utiliser comme clé privée; la Figure 4 est une représentation schématique d'un deuxième mode de réalisation de l'appareil; et la Figure 5 est une représentation schématique d'un troisième mode de réalisation de l'appareil. En se référant donc à la Figure 1, un réseau de communication 10 de données inclut une paire de correspondants 12, 14 connectés entre eux par une liaison de communication 16. Chacun des correspondants 12, 14 possède une clé privée respective ka, kb, et une clé publique correspondante Pa, Pb, qui est liée mathématiquement à la clé privée. Typiquement, la clé privée k est un élément d'un groupe multiplicatif dans un champ fini et la clé publique est l'exposant ock. Pour chiffrer un message, le correspondant 12 peut utiliser la clé publique pb du correspondant 14 afin de chiffrer le message et le transférer par la liaison 16 en tant que texte chiffré. Le correspondant 14 peut ensuite déchiffrer le message au moyen de la clé privée kb pour récupérer le texte en clair. De même, un message peut être signé par le correspondant 12 en utilisant sa clé privée ka et peut être authentifié par le correspondant 14 en utilisant la clé publique pa. De tels protocoles sont bien connus et sont généralement appelés des échanges par clés publiques de Diffie- Hellman ou des méthodes de signature de El Gamal et n'exigent pas d'être décrits de façon plus détaillée ici. Pour assurer la sécurité du chiffrage et éviter que la clé privée ne soit révélée par une analyse de la clé publique, il faut donner à l'entier k une longueur donnée, c'est-à-dire une longueur de 2n bits et il faut le choisir de façon qu'il soit unique et impossible à prédire. Comme représenté aux Figures 2 et 3, l'entier k est formé d'une paire de composants G1 et G2, respectivement, qui sont chacun d'une longueur de n bits et qui sont combinés pour réaliser un entier k pourvu des attributs nécessaires. Le composant G1 est engendré à partir d'un séquenceur qui engendre une valeur distincte non répétitive dans une plage finie. Dans le mode de réalisation préféré, ce séquenceur prend la forme d'un compteur 20 de n bits qui est incrémenté par un signal de commande 22 après chaque sélection d'une nouvelle clé k. Le signal de commande 22 incrémente d'un intervalle fixe, typiquement un compte unique, le compteur 20 de façon qu'un entier non répétitif, variant progressivement, soit amené à la sortie 23. La sortie 23 est connectée à une unité arithmétique 25 qui inclut un registre à décalage 24. La sortie du compteur 20 est transférée aux n premières cellules du registre 24. Le composant G2 est engendré à partir d'un générateur 26 de nombres aléatoires qui engendre à sa sortie 28 une suite de bits aléatoire de n bits. La sortie 28 est connectée aux n deuxièmes cellules du registre à décalage 24 de façon à être enchaînée avec la sortie du compteur 20 et à produire un entier à 2n bits qui est utilisé comme la clé privée suivante k. Le contenu du registre à décalage 24 est ensuite récupéré et l'entier résultant est mémorisé comme clé privée ka dans le registre sûr 30. Le compteur 20 fournit un composant unique en raison de son itération progressive tandis que le générateur 26 de nombres aléatoires fournit un composant impossible à prédire. En combinant les deux composants, on obtient un entier qui possède les attributs nécessaires. Le compteur 20 peut être agencé pour incrémenter selon des intervalles plus grands que 1 et peut à volonté incrémenter irrégnlièrement pour éviter une configuration du composant G1. Pourvu que le compteur 20 continue à incrémenter, le composant G1 est spécial. Si le compteur 20 atteint un compte complet, c'est-à- dire qu'il épuise la plage finie, une poursuite de la sélection de clé est empêchée. Le composant G1 est représenté comme précédent le composant G2, mais l'ordre pourrait être inversé, ou les composants pourraient être entrelacés. En général, les composants peuvent être combinés d'une manière fixe prévisible. De même, la longueur des composants pourrait, à volonté, être différente. Une variante de mode de réalisation est représentée à la Figure 4, dans laquelle des références numériques sont utilisées pour désigner des composants semblables, en ajoutant un suffixe ', c'est-à-dire prime, pour des raisons de clarté. En se référant donc à la Figure 4, la sortie 28' du générateur 26' de nombres aléatoires est utilisée comme entrée initiale 22' au compteur 20'. Le compteur 20' incrémente le compte pour fournir un composant unique G1, mais la valeur initiale du compteur est impossible à prédire. Selon un troisième mode de réalisation, représenté à la Figure 5, dans lequel un suffixe ", c'est-à-dire seconde, est ajouté à des références numériques semblables, la sortie du compteur 20" est utilisée comme entrée à une unité de permutation 32, par exemple une microplaquette de chiffrage selon la norme DES (Data Encryption Standard). L'unité de permutation 32 applique au compte un algorithme de chiffrage de manière impossible à prédire mais, puisque l'entrée de l'unité 32 est unique, la sortie est de même unique. La sortie de l'unité 32 est ensuite utilisée comme composant G1 dans le registre 24. Dans les modes de réalisation exposés précédemment, le composant G1 a été engendré en utilisant un compteur 20. D'autres séquenceurs, par exemple un registre à décalage à contre-réaction linéaire ou un réseau déterministe peuvent être utilisés, pourvu qu'une valeur distincte non répétitive soit obtenue. Pour fournir le composant unique, le séquenceur peut, soit incrémenter à partir d'une valeur initiale, soit décrémenter à partir de cette valeur. REVENDICATIONS 1. Procédé de génération d'un entier (k) à utiliser comme clé privée dans une méthode de chiffrage à clé publique, caractérisé en ce qu'il comprend les étapes consistant à: utiliser comme premier composant (G1) une sortie (23, 23', 23") d'un séquenceur (20, 20', 20") afin de fournir un élément unique audit entier (k), utiliser comme deuxième composant (G2) un entier (28, 28', 28") engendré (26) de façon aléatoire, et combiner (25, 25', 25") ledit premier composant (G1) et ledit deuxième composant (G2) pour réaliser un entier (k) unique et impossible à prédire- 2. Procédé selon la revendication 1 caractérisé en ce que lesdits premier et deuxième composants (G1, G2) sont concatérés- 3. Procédé selon la revendication 2 caractérisé en ce que ledit premier composant (G1) précède ledit deuxième composant (G2). 4. Procédé selon la revendication 1 caractérisé en ce que ledit deuxième composant (G2) est utilisé pour régler ledit séquenceur- 5. Procédé selon la revendication 1 caractérisé en ce que ladite sortie (23") dudit séquenceur (20") est permutée (32) avant d'être utilisée pour former ledit premier composant (G1). 6. Procédé selon la revendication 5 caractérisé en ce que ladite permutation (32) est effectuée par un algorithme de chiffrage. 7. Procédé selon la revendication 1 caractérisé en ce que ledit séquenceur (20, 20', 20") est un compteur qui incrémente. 8. Procédé selon la revendication 7 caractérisé en ce que ledit compteur (20, 20', 20") incrémente de façon uniforme. 9. Procédé selon la revendication 7 caractérisé en ce que ledit compteur (20, 20', 20") incrémente de façon non uniforme. 10. Appareil de génération d'une clé privée à utiliser dans une méthode de chiffrage à clé publique comprenant un dispositif de comptage (20, 20', 20") pour fournir un entier non répétitif (G1) variant progressivement, caractérisé en ce qu'il comporte une première sortie (23, 23', 23"), un générateur (26, 26', 26") de nombres pour engendrer des nombres (G2) d'une manière impossible à prédire, et une deuxième sortie (28, 28', 28"), et une unité arithmétique (25, 25', 25") pour recevoir lesdites sorties (G1, G2) et combiner ledit entier (G1) et ledit nombre (G2) pour produire un entier unique et impossible à prédire (k), et un dispositif de sortie (30, 30', 30") pour récupérer de ladite unité arithmétique (25, 25', 25") ledit entier (k) à utiliser comme clé privée. 11. Appareil selon la revendication 10 caractérisé en ce que ladite unité arithmétique (25, 25', 25") inclut un registre à décalage (24, 24', 24") pour recevoir lesdites sorties (23, 23'; 28, 28', 28"). 12. Appareil selon la revendication 11 caractérisé en ce que lesdites sorties (23, 23'; 28, 28') sont concatérées. 13. Appareil selon la revendication 10 caractérisé en ce que ladite unité arithmétique (25") inclut un dispositif de permutation (32) et ladite première sortie (23") y est connectée. 14. Appareil selon la revendication 13 et caractérisé en ce que ledit dispositif de permutation (32) est connecté audit registre à décalage (24").