Brevet FR2807246A1 — publié le 20011005

PROCEDE DE GENERATION DE CLES ELECTRONIQUES A PARTIR DE NOMBRES ENTIERS PREMIERS ENTRE EUX ET DISPOSITIF MISE EN #UVRE DU PROCEDE. L'invention concerne un procédé de génération de clés électroniques à partir de nombres entiers premiers entre eux et un dispositif de mise en oeuvre du procédé. L'invention s'applique tout particulièrement ' des protocoles de cryptographie à clé publique utilisés pour le cryptage d'informations et/ou l'authentification entre deux entités et/ou la signa ture électronique de messages. Elle s'applique en particulier à des protocoles de cryptographie à clé publique tels que le protocole (Rivest Shamir et Adelman), E1 Gamal, Schnorr, Fiat Shamir. Dans le cas de telles applications on fait, appel à la génération de grands nombres entiers (pouvant être par exemple être supérieurs ou égaux a 512 bits) pour former une ou plusieurs clés du proto cole. Une condition est imposée pour le choix de ces nombres afin qu'ils restent secrets c'est qu'ils doi vent être co-premiers ou premiers entre eux. De façon pratique, le dispositif électronique qui désire générer de tels nombres en vue par exemple de mettre en oeuvre un protocole de cryptographie, opère de manière connue de la façon suivante -Prendre un nombre entier a (choisi parmi un ensem- de nombres entiers prédéterminés, ou tiré aléatoi- rement), -Tirer de façon aléatoire un deuxième nombre entier -Effectuer une opération de vérification de la co- primalité entre les nombres a et b. Cette opération permet de vérifier que les deux nombres entiers a, b obtenus sont premiers entre eux. Elle est réalisée par l'unité centrale du dispositif. L'unité centrale cal cule pour cela le plus grand commun diviseur (pgcd) en tre ces deux nombres et vérifie que le résultat est égal à 1. En effet on rappelle que deux nombres sont co-premiers si et seulement si leur plus grand commun diviseur est égal à 1. I1 existe pour cela plusieurs techniques bien con nues d'implémentation du calcul du pgcd de deux nombres à l'aide d'un microprocesseur. On peut citer à titre d'exemple les techniques tel les que celle du Binary GCD , du Extended GCD ou la technique de Lehmer. Malgré une complexité asympto tique excellente (c'est-à-dire pour des nombres de taille extrêmement grande), ces techniques s'avèrent à la fois difficile à programmer sur des dispositifs por tables de type carte à microprocesseur car complexes) et de performances médiocres pour des nombres de gran des de tailles usuelles (512 bits) qui tendent à ce jour à devenir supérieures à savoir 1024 bits et plus. L'invention a pour but de remédier à cet inconvé nient. Elle a plus particulièrement pour objet un pro cédé de génération de clés électroniques à partir de deux nombres entiers a, b, le procédé comprenant une étape de vérification de la co-primal " desdits nom bres a, b, principalement caractérisé ce que cette etape de vérification comprend les opérations suivan- A) - calcul de l'exponentiation, modulaire X(b)modb, où @, est la fonction de Carmichael, - vérification que cette exponentiation modu laire égale à 1, et en ce que - on retient le couple a, b lorsque l'égalite est verifiée et on réitère avec un autre couple dans cas contraire. Selon une autre caractéristique - on choisit un nombre entier b d'une longueur donnée et on le mémorise, - on tire au hasard un nombre entier a, - on calcule a#,(t'modb - on vérifie que axe" = 1 modb (ou a'""'modb = 1) , - on mémorise le nombre a dans le cas où l'égalite est vérifiée, - on réitère les étapes précédentes avec un autre nombre a dans le cas contraire. Selon une autre caractéristique, dans le cas où nombre b est donné au préalable, on pré calcule la leur (b) et on la stocke en mémoire. invention s'applique aux procédés de génération de clés cryptographiques RSA ou E1 Gamal ou Schnorr. invention a également pour objet un dispositi électronique portable comprenant un processeur arithmé tique et une mémoire de programme associée, apte à ef fectuer des exponentiations modulaires, principalement caractérisé en ce qu'il comprend un programme de véri fication de co-primalité de nombres entiers de longueur donnée qui effectue les opérations suivantes - calcul de l'exponentiation modulaire a#.(b)modb, où @. la fonction de Carmichael, - vérification que cette exponentiation modu laire égale à 1, en ce que C) le processeur arithmétique stocke couple a, b lorsque l'égalité est vérifiée réitère avec un autre couple dans le cas contraire. Selon une autre caractéristique, dans le où le nombre est donné au préalable, on pré calcule la va leur X et on la stocke en mémoire. Avantageusement le dispositif électronique porta ble, est constitué par une carte à puce à microproces seur. D'autres particularités et avantages de l'invention apparaîtront clairement à la lecture de la description qui est faite ci-après et qui est donnée à titre d'exemple non limitatif et en regard des dessins annexés sur lesquels - la figure 1, représente le schéma de principe d'un dispositif électronique portable tel qu'une carte à puce mettant en oeuvre le procédé selon l'invention, - la figure 2, représente le schéma d'un exemple de réalisation de le mise en oeuvre procédé selon l'invention. Dans la description qui va suivre, on a pris comme exemple de dispositif électronique portable celui des cartes à puces à microprocesseur et on parlera pour simplifier de cartes à microprocesseur. Dans le cas de la mise en oeuvre de protocoles de cryptographie tels que le RSA par exemple, il comme on la dit nécessaire de déterminer un couple nombres entiers de longueur donnée, premiers entre servant à la génération de clés électroniques du protocole. Afin de s'assurer que les nombres générés sont premiers entre eux une étape de vérification de co- primalité est réalisée par la carte à microprocesseur qui met en ceuvre le procédé de génération de clés pour le protocole de cryptographie. En pratique dans le protocole RSA, les deux nom bres entiers a, b, restent secrets, ils doivent être premiers entre eux et ont une longueur fixée générale ment de 512 bits ou 1024 bits chacun. Selon ce même exemple, un des deux nombres b est un nombre entier choisi à l'avance et stocké parmi un ensemble de nom bres générés par la carte à microprocesseur tandis que l'autre nombre a est généré de manière aléatoire par la carte à microprocesseur à l'exécution du protocole. A cette fin, la carte à microprocesseur possède un géné rateur de nombres aléatoires, capable de fournir un nombre entier de la taille désirée. on a donc représenté sur la figure 1 le schema fonctionnel d'une carte à microprocesseur susceptible de mettre en oeuvre le procédé selon l'invention. La carte C comporte une unité principale de trai tement 1, des mémoires de programmes 3 et 4 et une moire de travail (non représentée), associées à l'unité 1. La carte comporte également un processeur arithméti que 2 capable d'effectuer des calculs d'exponentiation modulaire. Il pourra s'agir par exemple de circuits tels que le circuit ST16CF54 commercialisé par la so ciété STMicroelectronics ou 83C852/5 de la société Phi- lips. La carte possède également un générateur -de nom bres entiers aléatoires 5. Selon l'invention, l'opération de vérification la co-primalité des nombres entiers a et b est réalisée par les étapes A et B indiquées sur le schéma de la fi gure 2, avec l'étape de retenue du couple a, b pour gé nérer une clé électronique dans le cas où ces nombres sont premiers entre eux. En pratique cette étape con siste stocker le couple a, b dans la mémoire sécuri- sée (non accessible de l'extérieur) du processeur arithmétique 2. Avant de décrire l'exemple d'implémentation du procédé selon l'invention dans le cas du protocole RSA, on rappelle que la fonction a, est la fonction de Carmi- chael et que cette fonction est définie par la relation suivante (b) = PPCM (paj) , (X (pak)) . dans laquelle PPCM désigne le plus petit commun multiple, dans laquelle b= rIpi5i où chaque pi est un nombre premier et chaque 5i un entier positif nul et 1 tirage d'un nombre entier aléatoire _a (90) - calcul de aX(b)modb (50) comparaison de a@'(k')modb à 1 (60) s'il y a égalité, stockage du couple (a, b) pour générer une clé du protocole de cryptographie, (70) - s'il n'y a pas d'égalité (80) réitération des étapes précédentes à partir du ti rage d'un nouveau nombre entier a. REVENDICATIONS 1. Procédé de génération de clés électroniques à partir de deux nombres entiers a, b, le procédé compre nant une étape de vérification de la co-primalité desdits nombres a, b, caractérisé en ce que cette étape de vérification comprend les opérations suivantes A) - calcul de l'exponentiation, modulaire a?`(b)modb, où X. est la fonction de Carmichael, - vérification que cette exponentiation modu laire égale à 1, et en que - on retient le couple a, b lorsque l'égalité est verifiée et on réitère avec un autre couple dans le cas contraire. 2. Procédé de génération de clés électroniques se lon la revendication 1, caractérisé en ce que - on choisit un nombre entier b d'une longueur donnée et on le mémorise, - on tire au hasard un nombre entier a, - on calcule aX(b'modb - on vérifie que al(t') = 1 modb (ou a@"'")modb = 1) , - on mémorise le nombre a dans le cas ' l'.égalité est vérifiée, - on réitère les étapes précédentes avec un autre nombre a dans le cas contraire. 3. Procédé de génération de clés électroniques se lon la revendication 1, caractérisé en ce dans le cas où le nombre b est donné au préalable, pré cal cule la valeur X(b) et on la stocke en mémoire. . Procédé de génération de clés cryptographiques RSA E1 Gamal ou Schnorr, caractérisé en ce qu'il met en aeuvre le procédé selon l'une quelconque revendi cations précédentes. 5. Dispositif électronique portable comprenant un processeur arithmétique et une mémoire de programme as sociée, apte à effectuer des exponentiations modulai res, caractérisé en ce qu'il comprend un programme de vérification de co-primalité de nombres entiers de lon gueur donnée qui effectue les opérations suivantes - calcul de l' exponentiation modulaire aX(b)modb, où @, la fonction de Carmichael, - vérification que cette exponentiation modu laire égale à 1, et en ce que D) le processeur arithmétique stocke couple a, b lorsque l'égalité est vérifiée réitère avec un autre couple dans le cas contraire. 6. Dispositif électronique portable selon la reven dication 5, caractérisé en ce que dans le cas où le nombre b est donné au préalable, on pré calcule la va leur X(b) et on la stocke en mémoire. . Dispositif électronique portable selon la reven dication 5 ou 7, caractérisé en ce qu'il est constitué par carte à puce à microprocesseur.