Brevet FR2811442A1 — publié le 20020111

*4 PROCEDE DE GÉNERATION D'UNE CLÉ ELECTRONIQUE À PARTIR D'UN NOMBRE PREMIER COMPRIS DANS UN INTERVALLE DETERMINE ET DISPOSITIF DE MISE EN EUVRE DU PROCÉDE L'invention concerne un procédé de génération d'une clé électronique à partir d'un nombre premier q compris dans un intervalle de nombres entiers positifs déterminé [Wm, WM]. L'invention concerne également 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 signature électronique de messages. Elle s'applique en particulier à des protocoles de cryptographie à clé publique tels que le protocole RSA (Rivest Shamir et Adelman), El Gamal, Schnorr, ou Fiat Shamir. Dans le cas de telles applications, on fait appel à la génération de grands nombres premiers (pouvant être par exemple supérieurs ou égaux à 512 bits) pour former une ou plusieurs clés du protocole. Une première méthode dite "naïve" de génération de nombre premier consiste à: - choisir un candidat parmi les nombres impairs, - tester sa primalité, - si la primalité est vérifiée, on mémorise ce nombre, sinon, on met à jour le candidat en l'incrémentant de 2, on réitère le test avec ce nouveau candidat et ainsi de suite jusqu'à ce que la primalité d'un candidat soit vérifiée. 2 2811442 Cette méthode est très lente. Une autre méthode consiste à choisir les candidats au test de primalité parmi les nombres premiers avec un nombre premier I. On rappelle que deux nombres sont premiers entre eux ou copremiers si et seulement si leur plus grand commun diviseur (pgcd) est égal à 1. Cette autre méthode consiste à: - considérer le nombre Il = 2.3. 5.7.... qui est le produit des k premiers nombres premiers (souvent k = 4) et à choisir un nombre p tel que p soit premier avec I, - tester la primalité de p, - si la primalité de p est vérifiée, on mémorise ce nombre, sinon on met à jour p en l'incrémentant de IH. Ce nouveau candidat p est également premier avec FI; en effet, on rappelle que pgcd(p+I, FI) = pgcd(p, I) = 1 - on réitère le test avec ce nouveau candidat et ainsi de suite jusqu'à ce que l'on ait trouvé un candidat qui soit un nombre premier. Cette méthode est plus efficace. Mais on souhaite en général générer un nombre premier dans un intervalle déterminé. En effet, dans le cas par exemple du protocole de cryptographie à clé publique RSA, on considère le produit de 1024 bits de deux nombres premiers p et q. c'est-à-dire 2511./2 nombre premier de 1024 bits, c'est-à-dire 21023 Ces protocoles s'avèrent difficiles à programmer sur 3 2811442 des dispositifs portables de type carte à microprocesseur (car complexes) et de performances médiocres pour des nombres de grandes tailles usuelles, 512 bits, 1024 bits voire plus. L'invention a pour but, étant donné l'intervalle [Wm,WM], de déterminer I une fois pour toutes et de proposer une mise à jour du candidat garantissant que le nouveau candidat sera premier avec nI dans l'intervalle déterminé initialement tout en maintenant le temps de calcul de ces nouveaux candidats dans des limites raisonnables, c'est-à-dire en limitant le nombre de tests de primalité. Le choix de n est illustré par la figure 1 o sont représentés l'ensemble I des entiers compris dans un intervalle [Wm, wM], dans lequel est inclus l'ensemble IN des entiers de cet intervalle premiers avec I, dans lequel est inclus l'ensemble IP des nombres premiers de cet intervalle. Le but consiste à déterminer n de façon à ce que l'ensemble intermédiaire IN des entiers premiers avec I, c'est-à-dire l'ensemble des candidats, soit le plus proche possible du sous-ensemble IP des nombres premiers de l'intervalle. L'invention a plus particulièrement pour objet un procédé de génération d'une clé électronique à partir d'un nombre premier q compris dans un intervalle de nombres entiers positifs déterminé [wm,wM], principalement caractérisé en ce que le nombre premier q est obtenu en réalisant les opérations suivantes: a) choix d'un nombre entier positif A, ' étant le produit des k premiers nombres premiers, avec k maximum pour qu'il existe deux nombres entiers positifs sm et EM tels que 5m est l'arrondi supérieur de Wm/T, et SM est l'arrondi inférieur de (WM-Wm)/q, calcul de I = SM.T et p = $m.t génération de deux nombres entiers positifs a et c appartenant au groupe multiplicatif Z*nfl des nombres entiers modulo n, avec c premier avec FI calcul de q = c + p b) test de la primalité de q, c) dans le cas o la primalité est vérifiée, on mémorise q, d) dans le cas contraire: on met à jour c en calculant a.c mod FI, on réitère les opérations précédentes à partir de b) avec la nouvelle valeur q = c+p. Selon une caractéristique de l'invention, a = 2 et I = (EM-1).T. Selon une autre caractéristique, a = 216 + 1. L'invention s'applique aux procédés de génération de clés cryptographiques RSA, El Gamal, Schnorr, ou Fiat Shamir. L'invention a également pour objet un dispositif électronique portable comprenant un processeur arithmétique et une mémoire de programme associée, apte à effectuer des calculs modulaires, principalement caractérisé en ce qu'il comprend un programme de vérification de primalité d'un nombre entier positif q compris dans un intervalle de nombres entiers positifs déterminé [wm,wM] qui effectue les opérations suivantes: a) choix d'un nombre entier positif A, r étant le produit des k premiers nombres premiers, avec k maximum pour qu'il existe deux nombres entiers positifs Sm et sM tels que sm est l'arrondi supérieur de Wm/1, et $M est l'arrondi inférieur de (WM-wm)/il, calcul de FI = EM.A et p = ESm., génération de deux nombres entiers positifs a et c appartenant au groupe multiplicatif Z*n des nombres entiers modulo I, avec c premier avec i calcul de q = c + p b) test de la primalité de q, c) dans le cas o la primalité est vérifiée, le processeur arithmétique stocke q, d) dans le cas contraire: mise à jour de c par le calcul de a.c mod I, le processeur arithmétique réitère les opérations précédentes à partir de b) avec q = c+p. 6 2811442 Avantageusement, le dispositif électronique portable est constitué par une carte à puce à microprocesseur. D'autres particularités et avantages de l'invention apparaîtront clairement à la lecture de la description faite à titre d'exemple non limitatif et en regard des dessins annexés sur lesquels: la figure 1 représente l'ensemble I des entiers compris dans un intervalle [Wm, wM], l'ensemble IN des entiers de cet intervalle premiers entre eux et enfin l'ensemble IP des nombres premiers de cet intervalle, la figure 2 représente l'organigramme du procédé selon l'invention, la figure 3 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. Le but de l'invention consiste donc dans un premier temps à déterminer I de façon à ce que l'ensemble IU des entiers premiers avec I représenté figure 1 soit le plus proche possible du sous-ensemble IP des. nombres premiers de l'intervalle. Selon l'invention, le procédé représenté figure 2 est initialisé de la manière suivante (étape I): pour générer un nombre premier q tel que q e [Wm,WM], on choisit un nombre n de la même forme que I (a est le produit des k' premiers nombres premiers) o k' est maximum et tel qu'il existe deux nombres entiers positifs sm et cM tels que gm est l'arrondi supérieur de Wm/f, que l'on note [ wrn/q 1 et EM est l'arrondi inférieur de (wM-wm)/T que l'on note L[ (wM-wm) /n J. F est alors obtenu en posant I = EM.A; on pose également p = sm. On remarque que Il est proche de wM- wm mais inférieur et que p est proche de wm mais supérieur. Il faut à présent déterminer la mise à jour des candidats de façon à ce que les nouveaux candidats appartiennent toujours à IH. On considère l'anneau Zn des entiers modulo r et Z*n le groupe multiplicatif de Zn; on remarque que l'ensemble (p + Z'n) est inclus dans et quasiment identique à IN, c'est-à-dire à l'ensemble des candidats. On génère alors deux nombres entiers positifs a et c appartenant à ce groupe multiplicatif Z'n avec c premier avec I (c'est-à-dire pgcd(c, H)=1) et on considère le candidat q = c + p (étape I). Pour -générer c, on utilise un algorithme de génération de nombres co-premiers tel qu'il en existe dans la littérature. Comme p est proche de wm et que c automatiquement que wm Par ailleurs, pgcd(q,I)= pgcd(c+p,n)= pgcd(c, H)=l On vérifie ainsi que q appartient effectivement à IH. 8 2811442 Cette phase d'initialisation terminée, on teste la primalité du candidat q (étape II). Si elle est vérifiée, on mémorise q, sinon: on met à jour c en calculant a.c mod F et on calcule le nouveau candidat q = c + p (étape III). Le nouveau candidat appartient à l'ensemble IN: en effet, en raison des propriétés des groupes multiplicatifs, a et c appartenant à Z'n, le produit a.c appartient aussi à ce groupe Z*n ainsi que a.c mod H. Les protocoles de cryptographie à clé publique sont souvent mis en ouvre sur des cartes à puce à microprocesseur. Par exemple, dans le protocole RSA, les clés sont générées à partir de nombres choisis 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 3 le schéma fonctionnel d'une carte à microprocesseur susceptible de mettre en oeuvre le procédé selon l'invention.' La carte C comporte une unité principale de traitement 1, des mémoires de programmes 3 et 4 et une mémoire de travail (non représentée), associées à l'unité 1. La carte comporte également un processeur arithmétique 2 capable d'effectuer des calculs modulaires et une mémoire sécurisée 6 (non accessible de l'extérieur) dans laquelle sera stockée le candidat q dont la primalité aura été vérifiée. La carte possède également un générateur de nombres entiers aléatoires 5. En vue de la mise en ouvre du procédé en particulier sur une carte à microprocesseur telle que décrite, il est souhaitable d'augmenter la vitesse du traitement mis en oeuvre par le procédé (opérations effectuées par le processeur arithmétique 2) et de libérer de l'emplacement dans la mémoire de travail. Dans ce but, en choisissant a = 2 et en excluant 2 du nombre I (H = 3.5.7. ...), on évite les calculs modulaires. En effet, la mise à jour de c devient 2c mod FI. Or comme c est un élément de Z'n, 2c mod i = 2c ou 2c - i. Mais, les nouveaux candidats q peuvent alors être pairs. Si c'est le cas, on ajoute alors au nouveau candidat un nombre tel que le nouveau candidat devienne impair tout en appartenant toujours à l'ensemble I. On pose ainsi: FI= (M - 1) *. q = c + p si q est pair alors q devient q + T. Selon une autre alternative, on peut garder F tel que défini initialement et choisir une valeur particulière de a telle que a soit premier avec FI. On peut choisir par exemple a = 216 + 1. Le procédé selon l'invention a été mis en oeuvre sur une plate-forme de carte à puce SLE66CXl60S d'Infineon comprenant une unité centrale 8-bit et un crypto- processeur arithmétique 1100-bit. En choisissant pour A, H et p les valeurs suivantes: i=bl6bdleO84af628fe5089e6dabdl6b5b80f60681d6aO92fcb le86d82876ed71921000bcfdd063fb90f81dfd07a021af23c735d52 e63bdlcb59c93cbb398afd16, = 1729.i p = 4180., on obtient avec a = 2, un nombre premier de 512 bits en moins de 4 secondes. On obtient par conséquent un nombre premier de 1024 bits en moyenne en moins de 8 secondes. REVENDICATIONS 1. Procédé de génération d'une clé électronique à partir d'un nombre premier q compris dans un intervalle de nombres entiers positifs déterminé [Wm, WM], caractérisé en ce que le nombre premier q est obtenu en réalisant les opérations suivantes: a) choix d'un nombre entier positif A, n étant le produit des k premiers nombres premiers, avec k maximum pour qu'il existe deux nombres entiers positifs sm et SM tels que sm est l'arrondi supérieur de wm/i, et $M est l'arrondi inférieur de (WM- Wm) /X, calcul de i = sM.q et p = em.I, génération de deux nombres entiers positifs a et c appartenant au groupe multiplicatif Z*n des nombres entiers modulo I, avec c premier avec FI calcul de q = c + p b) test de la primalité de q, c) dans le cas o la primalité est vérifiée, on mémorise q, d) dans le cas contraire: on met à jour c en calculant a.c mod n, on réitère les opérations précédentes à partir de b) avec la nouvelle valeur q = c+p. 12 2811442 2. Procédé selon la revendication précédente, caractérisé en ce que a = 2 et H = (sM-1).Y. 3. Procédé selon la revendication 1, caractérisé en ce que a = 216 + 1. 4. Procédé de génération de clés cryptographiques RSA, El Gamal, Schnorr, ou Fiat Shamir, caractérisé en ce qu'il met en oeuvre le procédé selon l'une quelconque des revendications précédentes. 5. Dispositif électronique portable comprenant un processeur arithmétique et une mémoire de programme associée, apte à effectuer des calculs modulaires, caractérisé en ce qu'il comprend un programme de vérification de primalité d'un nombre entier positif q compris dans un intervalle de nombres entiers positifs déterminé [Wm,WM] et qui effectue les opérations suivantes: a) choix d'un nombre entier positif q, T étant le produit des k premiers nombres premiers, avec k maximum pour qu'il existe deux nombres entiers positifs.sm et sM tels que Em est l'arrondi supérieur de Wm/T, et EM est l'arrondi inférieur de (WM-w,,)/T, calcul de H = EM.l et p = Sm-. génération de deux nombres entiers positifs a et c appartenant au groupe multiplicatif Z*n des nombres entiers modulo i, avec c premier avec F calcul de q = c + p b) test de la primalité de q, c) dans le cas o la primalité est vérifiée, le processeur arithmétique stocke q, d) dans le cas contraire: mise à jour de c par le calcul de a.c mod I, le processeur arithmétique réitère les opérations précédentes à partir de b) avec q = c+p. 6. Dispositif électronique portable selon la revendication 5, caractérisé en ce qu'il est constitué par une carte à puce à microprocesseur.