Brevet FR2837335A1 — publié le 20030919

L'invention se rapporte au domaine de la cryptographie et en particulier aux systèmes cryptographiques à clé publique. Lorsqu'il s'agit de communiquer des données que l'on souhaite conserver confidentielles ou bien que l'on souhaite authentifier par une signature, on utilise des systèmes cryptographiques à clé publique. On procède, selon le cas, à une opération publique ou une opération privée. Selon un exemple de chiffrement, quelqu'un souhaitant émettre un message, prend connaissance au préalable d'une clé publique attachée au destinataire à qui il va l'adresser. Il chiffre le message au moyen de cette clé publique et le transmet. Le destinataire, après réception, peut déchiffrer le message et retrouver le document initial en utilisant sa clé privée. Selon un autre exemple de signature, on signe un document en le codant au moyen de sa clé privée et on présente la signature avec le document initial. Le destinataire vérifie la signature en utilisant la clé publique associée à la clé privée de l'émetteur. Des systèmes permettant ces opérations sont maintenant bien connus. Par exemple, on connaît le crypto-système RSA développé par R. Rivest, A. Shamir et L. Adleman. On en trouve une présentation complète dans le brevet US 4 405 829 déposé à leurs noms. Pour procéder à ces opérations, on utilise notamment un dispositif électronique portable, tel qu'une carte à microprocesseur, constituant une carte cryptographique. Le code du programme cryptographique est enregistré dans la mémoire morte ROM, et les autres données, notamment la clé privée constituée du couple de l' exposant privé d et du "module" n, sont stockées dans une mémoire non volatile EEPROM. La carte peut comprendre également un crypto-processeur qui est une unité de calcul spécialisée, pouvant traiter des grands nombres, par exemple de 1024 bits. Incidemment, la clé publique est constituée du couple de l'exposant public e et du module n. La méthode RSA comprend comme étape préalable, avant que l'on puisse procéder aux opérations publiques et privées, la détermination de l'exposant privé d à partir d'un exposant public e donné. Dans ce but, on génère d'abord, au moyen d'un générateur de nombres aléatoires, deux nombres premiers p et q. Puis, à partir d'une fonction déterminée #(n) du produit n = p*q, on détermine l'exposant privé d associé à l'exposant e, avec e. d = 1 (modulo À(n)) ou d e-I (modulo ,(n . Dans le cas du procédé RSA, la fonction ,(n) est le PPCM (plus petit commun multiple) du couple (p-1, q-1). L'exposant privé d est calculé comme étant la valeur inverse e'1 de l'exposant public e, modulo ,(n), c'est-à-dire qu'il existe un nombre entier k tel que e. d = 1 + k #(n). Lorsque ces valeurs sont établies, on peut procéder au chiffrement et au déchiffrement de messages ou bien à la signature d'un message m par exponentiation modulaire comme cela est connu par la méthode RSA. Plus précisément, n et e étant les paramètre publics et p, q, d, les paramètres privés se trouvant dans la carte pour le chiffrement, un message constitué du nombre m, compris dans l'intervalle [1, n-1], devient, après chiffrement, c = me, modulo n. A la réception, on retrouve le message m, suivant c'est-à-dire le reste de la division de cd par n. Dans le cas de la signature, un message m, en entrée de la carte, devient, en sortie de la carte, la signature s = md modulo n. Le destinataire, disposant des paramètres publics n et e, peut vérifier que, étant donné s et m, la relation se = m modulo n est satisfaite. Afin de pouvoir calculer l'exposant privé d, de manière simple, notamment par la formule d' inversion d'Arazi, connue dans le domaine, on impose au nombre e, exposant public, d'être premier, étant entendu que e et ,(n) sont copremiers, c'est-à-dire que leur PGCD (plus grand commun diviseur) est égal à 1. Si on pose L = ,(n), la formule d'Arazi permet d'exprimer e-1 modulo L en fonction de L-' modulo e. De plus, si e est premier, alors L-1 modulo e = Le-2 modulo e. compte-tenu du théorème de Fermat, selon lequel, pour tout nombre premier p, la relation suivante est vérifiée ap-1 # 1 (modulo p). On connaît certes l'algorithme d'Euclide étendu qui permet la détermination de la valeur inverse de l'exposant e modulo #(n) indépendamment de la primalité de celui-ci, algorithme selon lequel, e et L étant copremiers (PGCD (e, L) = 1), il existe deux nombres entiers u et v tels que ue + vL = 1. Cependant, la mise en #uvre de cet algorithme par un programme d'ordinateur, nécessite la mobilisation de mémoires supplémentaires par rapport à celles nécessaires à la mise en place du cryptosystème. Son application aux cartes à microprocesseur notamment est donc exclue en raison de la faible capacité mémoire de ces dernières. Il serait donc souhaitable de disposer d'un moyen permettant la mise en #uvre du cryptosystème RSA dans une carte à microprocesseur, ou tout autre support équivalent, autorisant le choix comme exposant public d'un nombre quelconque. En particulier, on pourrait ainsi choisir des valeurs relativement faibles non nécessairement premières et améliorer la vitesse de traitement des opérations publiques. L'invention a donc pour objet un procédé de cryptographie à clé publique de type RSA qui est mis en #uvre dans un dispositif électronique portable tel qu'une carte à microprocesseur et qui n'impose pas de contrainte de primalité quant au choix préalable du nombre représentant l'exposant public e. Ce problème est résolu par l'invention par un procédé de cryptographie de type RSA, mis en #uvre dans un dispositif électronique portable avec un processeur et une mémoire, comprenant la saisie d'un nombre arbitraire, exposant public e, et le calcul par le processeur d'un exposant privé d, tel que le produit de e et d est congruent à 1 modulo #(n), avec #(n)=ppcm ((p-1), (q-1)), p et q étant des nombres premiers dont le produit est égal à n, et son stockage dans la mémoire, caractérisé par le fait que, si e n'est pas premier, on choisit un paramètre C tel que e+C*(n)=ê soit premier et on calcule l'exposant privé d à partir de ê. L'invention devant être relative aussi bien à la mise en #uvre RSA mode standard qu'à d'autres mises en #uvre comme par exemple la mise en oeuvre CRT dont il sera question dans la description qui suit, la demanderesse entend élargir la portée de ses droits à un procédé de cryptographie, mis en #uvre dans un dispositif électronique portable avec un processeur et une mémoire, comprenant la saisie de nombres arbitraires e et # et le calcul par le processeur d'un nombre d, tel que le produit de e et d est congruent à 1 modulo #, et son stockage dans la mémoire, caractérisé par le fait que, si e n'est pas premier, on choisit un paramètre C tel que e+C*#=ê soit premier, et on calcule le nombre d à partir de ê. Conformément à une autre caractéristique, on détermine la valeur C par un calcul itératif depuis une valeur initiale c comme un élément inversible modulo le produit de nombres premiers. L'invention a également pour objet un système cryptographique comprenant un processeur central et, reliés au processeur, des moyens de stockage d'un programme cryptographique de type RSA, des moyens de stockage de paramètres cryptographiques privés et des moyens mémoires de travail, le processeur comprenant des moyens de génération de nombres premiers privés (p et q) et des moyens de détermination d'un exposant privé (d) à partir d'un exposant public (e) selon la relation d #e-1 [modulo ppcm (p-1), (q-1)]. Conformément à une caractéristique de l'invention, il est prévu des moyens pour, si e n'est pas un nombre premier, calculer un nombre premier ê selon la relation ê = e + C[ppcm (p-1), (q-1)] et des moyens pour vérifier que le nombre ê est premier. On décrit ci-après l'invention plus en détail, en référence au dessin annexé, sur lequel - la figure 1 représente un schéma-blocs du système cryptographique de l'invention et - la figure 2 représente l'organigramme de détermination du nombre premier ê à partir du nombre e. La mise en #uvre du crypto-système RSA consiste donc à définir, dans un premier temps, les clés publique et privée, c'est à dire l'exposant public e, le module n et l'exposant privé d. Ces valeurs sont liées entre elles. Ainsi l'exposant privé d est l'inverse modulo #(n) du nombre représentant l'exposant public e. On choisit n comme le produit de deux nombres premiers p et q ; #(n) est la fonction de Carmichael de ces nombres. Dans le système RSA, il s'agit du PPCM du couple de nombres p-1 et q-1. Ces valeurs étant établies, et comme on l'a déjà vu plus haut, on peut procéder aux opérations de chiffrement-déchiffrement ou de signature de messages Considérant un message numérique m à coder, d'une valeur inférieure à n. On observe que, si la valeur est supérieure à n, on découpe le message en autant de sous messages qu'il est nécessaire pour remplir cette condition. On traite séparément les différents sous messages. Si on souhaite transmettre le message sous forme codée à un tiers, on se procure la clé publique de ce dernier et on introduit la valeur m dans le système cryptographique qui restitue une valeur codée c telle que c=me modulo n. Le destinataire du message codé peut retrouver le message initial en procédant à la même opération avec sa clé privée : m=cdmodulo n. Le système permet aussi de signer un document. L'émetteur du document m code celui-ci avec sa clé privée d ; obtient une signature s telle que s=mdmodulo n. Pour qu'un tiers authentifie cette signature, il lui suffit d'appliquer la clé publique correspondante à la signature et de comparer le message transformé avec le message d'origine. Il faut que les messages en résultant soient les mêmes. Lorsque le système cryptographique est chargé sur une carte à microprocesseur ou tout autre support équivalent, on est limité en espace mémoire disponible si bien qu'il ne paraît pas possible d'appliquer les moyens de l'art antérieur pour résoudre le problème de l'invention, à savoir le libre choix de l'exposant public quant à sa primalité. Pour mémoire, la formule connue sous le nom de formule d'inversion d'Arazi permet le calcul de l'inverse modulo L d'un nombre e, si ce nombre est premier. Elle est reproduite ci dessous, après avoir été exprimée un peu différemment ci-dessus : e-1mod L = (1 + L(-L-1 mod e))/e avec pgcd (e, L)=l. Dans la mesure où l'on souhaite ne pas être limité dans la sélection du nombre e, on applique une étape de transformation du nombre e en un nombre ê qui est premier. Ce nombre ê est défini à partir de la formule ê = e+C*#(n). Il permet le calcul de l'exposant privé d de la même façon que le nombre e, car si d e-lmod 1(n), alors d+C*À(n)r1mod ,(n). On choisit C pour que ê soit premier. Dans ce but, et en référence à la figure 2, on choisit un nombre # égal à un produit de nombres premiers ; de préférence, ils sont petits. On définit (20) un nombre c co-premier avec #. On en déduit (21) le nombre C par la formule suivante C = [(c-e)*7(n)n -'] mod II Le nombre C ayant été calculé, on en déduit (22) une valeur pour ê. ê est alors premier avec #. Si le nombre ê est premier avec tous les petits premiers à savoir : 2,3, 5,7, 11, 13,17, 19,23, etc., alors la probabilité est grande qu'il soit premier dans l'absolu. On vérifie (23) la primalité T de ê, c'est-à-dire si le nombre ê est premier, selon une méthode connue en soi. Par exemple, il peut s'agir du test de Fermat ou bien du test de Miller et Rabin tel que décrit dans le chapitre 4 du livre "Handbook of Applied Cryptography" (A.J. Menezes, P. C. van Oorschot et S.A. Vanstone, CRC Press, 1997). S'il apparaît que ê n'est pas premier, alors on définit (20) un nouveau nombre c à partir duquel on calcule un nouveau nombre ê et, ainsi de suite, de façon itérative. Le nouveau nombre c est, de préférence, le produit de l'ancienne valeur c avec un nombre a qui est inversible modulo n. Le nouveau nombre e ainsi obtenu est alors également inversible modulo n. On détermine un nouveau nombre ê à partir de la nouvelle valeur de c. S'il n'est pas premier, on recommence jusqu'à ce que le test de primalité soit positif. Enfin, le nombre ê étant premier, on lui applique (24) l'opération d'inversion modulaire selon Arazi, et on en déduit l'exposant privé d associé à l'exposant public e. d = [1 + 1(n)(- À(n)ê-2 mod ê)]/ê. Ce nombre ayant été déterminé, on le stocke dans une mémoire de la carte à microprocesseur. Il s'agit de préférence d'une mémoire non volatile EEPROM. On peut alors utiliser la carte à microprocesseur pour le chiffrement ou la signature de documents. On vient d'exposer la mise en #uvre RSA en mode standard. Conformément à une autre mise en #uvre, on applique l' invention à la détermination de l'exposant privé d dans le cas d'une mise en #uvre du crypto-système RSA selon le mode connu sous le nom de CRT (du théorème des restes chinois). Selon cette mise en #uvre, on profite de la propriété du module n d'être le produit de deux nombres premiers p et q et de #(n) d'être le ppcm de (p-1), (q-1). L'exposant privé d ayant été déterminé, on établit des exposants privés partiels-dp et dq , à partir de d de la façon suivante : dp = d mod (p-1) et dq = d mod (q-1). Dans le cas d'une opération privée telle que la détermination de la signature d'un message m par calcul de la valeur s = mdmod n, il apparaît que si on connaît à la fois Sp = mdmod p et donc, selon le théorème de Fermat, Sp = mdp mod p et Sq = md mod q et donc Sq = mdq mod q, alors on peut déterminer aisément mdmod n. Dans un dispositif portable où la capacité mémoire est limitée, il est préférable de procéder aux calculs sur les exposants privés partiels dp et dq ainsi définis, car ceux-ci sont deux fois plus courts que l'exposant d. Il en est de même pour p et q qui sont deux fois plus courts que n = p. q. Il s'ensuit que le calcul de s à partir des valeurs sp et sq est sensiblement quatre fois plus rapide que le calcul de la signature s, directement à partir de l'exposant privé d. Ainsi, pour calculer la signature d'un message s=mdmod n, on calcule séparément les signatures partielles. sp = mdp mod p et Sq = mdq mod q. On détermine ensuite la signature s par la méthode connue de calcul des restes chinois. s = CRT (sp, sa ) = sq +q*(iq*(sp~Sq) mod p) avec iq = 1/q mod p. On peut aussi calculer s à partir du nombre sp selon l'expression s =sp + p*( ip*(sq-sp) mod q) avec ip== 1/p mod q. Donc en mode CRT, on peut ne stocker en mémoire dans la carte que les valeurs nécessaires p, q, dp, dq, et iq. L'exposant partiel dp (respectivement dq) peut également s'obtenir directement à partir de e et de ,(p) = p-1 (respectivement #(q) = q-1). La méthodologie utilisée pour le calcul de d s'applique au calcul de dp en remplaçant n par p et #(n) par ,(p) = p-1. On pose êp = ep + Cp * ,(p) avec ep = emod(p-l) et Cp = (cp - e)(p-1)#(#) modII, où cp est un élément inversible modulo #. Si êp est premier, alors obtient dp = (1 + (p-l)(-(p-ir2 modêp /êp. La valeur de dq s'obtient de façon similaire en remplaçant les indices p par des indices q. L'avantage du calcul direct en mode CRT est, selon le dispositif portable, une vitesse de traitement accrue et/ou un gain en mémoire. Finalement, et en référence à la figure 1, l'invention concerne aussi, implanté sur une carte à microprocesseur 1, appelée couramment carte à puce, un système cryptographique 2, ou cryptosystème, comprenant un processeur central 3 et, reliées au processeur central 3, une mémoire (ROM) 8 de stockage d'un programme cryptographique RSA, une mémoire (EEPROM) 9 de stockage de paramètres cryptographiques privés et une mémoire (RAM) 10 de travail. Un cryptoprocesseur 11 est ici également relié au processeur central 3. Sous forme de logiciel, le processeur central 3 comprend un générateur 4 de nombres premiers privés (p et q), des moyens 5 de détermination d'un exposant privé (d) à partir d'un exposant public (e), selon la relation d e-1 [modulo ppcm (p-1, q-1)], des moyens 6 pour, si e n'est pas un nombre premier, calculer un nombre premier ê selon la relation ê = e + c* [ppcm (p-1), (q-1)] et des moyens 7 pour vérifier que le nombre ê est premier. L'invention concerne également le même programme cryptographique RSA utilisé en mode CRT. REVENDICATIONS 1.- Procédé de cryptographie, mis en #uvre dans un dispositif électronique portable avec un processeur et une mémoire, comprenant la saisie de nombres arbitraires e et # et le calcul par le processeur d'un nombre d, tel que le produit de e et d est congruent à 1 modulo #, et son stockage dans la mémoire, caractérisé par le fait que, si e n'est pas premier, on choisit un paramètre C tel que e+C*#=ê soit premier, et on calcule le nombre d à partir de ê. 2. - Procédé selon la revendication 1, de type RSA, dans lequel e est un exposant public, d est un exposant privé, le produit de e et d est congruent à 1 modulo #(n), avec ,(n) = ppcm((p-l)(q-l)), p et q étant des nombres premiers dont le produit est égal à n et C est tel que e + C*#(n) = ê. 3. - Procédé selon la revendication 1, de type RSA en mode CRT, dans lequel e est un exposant public, dp est un exposant privé, le produit de e et de dp est congruent à 1 mod #(p), avec #(p) = p - 1, p étant un nombre premier et C est tel que ep + C * #(p) = ê, avec ep = e mod (p - 1). 4. - Procédé selon l'une des revendications 1 à 3, dans lequel on stocke le nombre d dans une mémoire non volatile. 5. - Procédé selon l'une des revendications 1 à 4, dans lequel on détermine (21) le paramètre C par un calcul itératif depuis une valeur initiale c choisie (20) comme le produit # de nombres premiers. 6. - Procédé selon la revendication 5, dans lequel on prend des nombres premiers petits. 7. - Procédé selon l'une des revendications 5 et 6, dans lequel on détermine (21) la valeur C par application de la formule C = [( c-e )*À À(f1 )-1] mod II. 8. - Procédé selon la revendication 7 dans lequel tant que ê n'est pas premier (23), on calcule C à partir d'une nouvelle valeur de c. 9. - Procédé selon l'une des revendications 2 à 8, dans lequel on stocke en mémoire les valeurs de deux exposants privés partiels dp et dq calculés à partir des deux valeurs p et q, selon les formules 10. - Système cryptographique comprenant un processeur central et, reliés au processeur, des moyens de stockage d'un programme cryptographique de type RSA, des moyens de stockage de paramètres cryptographiques privés de cryptage et des moyens mémoires de travail, le processeur comprenant des moyens de génération de nombres premiers privés (p et q) et des moyens de détermination d'un exposant privé (d) à partir d'un exposant public (e) selon la relation caractérisé par le fait qu'il est prévu des moyens pour, si e n'est pas un nombre premier, calculer un nombre premier ê selon la relation et des moyens pour vérifier que le nombre ê est premier. 11.- Système selon la revendication 8, dans lequel les moyens de calcul de ê et de vérification de la primalité de ê sont agencés pour procéder de façon itérative.