Brevet FR2880149A1 — publié le 20060630

L'invention concerne des procédés de traitement de données, par exemple pour la mise en oeuvre d'algorithmes cryptographiques, ainsi que des dispositifs aptes à réaliser de tels procédés. Les procédés de traitement de données couramment mis en oeuvre au sein d'entités électroniques, telles que les cartes à microcircuit et les micro- ordinateurs, ont recours à des opérations parfois complexes. Par exemple, dans le domaine de la cryptographie, de nombreux algorithmes utilisent l'arithmétique modulaire, notamment la multiplication modulaire (qui a deux nombres a et b associe le reste de leur produit modulo un nombre particulier appelé le module n) ou l'opération d'exponentiation modulaire (qui a deux nombres a et e associe le reste modulo n idu nombre ae). Le coût calculatoire de telles opérations peut s'avérer important si l'on effectue les calculs de manière conventionnelle, par exemple du fait de l'utilisation de grands nombres dans les algorithmes cryptographiques par souci d'obtenir un niveau de sécurité correct. II a de ce fait été proposé d'optimiser les calculs à effectuer par la définition de nouvelles opérations qui permettent un allègement des calculs réalisés au sein des algorithmes et qui sont en pratique effectués par des circuits électroniques dédiés. Dans ce cadre, on a introduit l'arithmétique de Montgomery dont les opérations de base sont les suivantes: - la multiplication au sens de Montgomery, représentée par le symbole "*", est définie comme suit: a*b mod n=a.b.r-1 mod n, où r est le radical de Montgomery (un entier premier avec n et supérieur à n) et où le symbole "." représente la multiplication classique (généralement dénommée dans ce cadre "multiplication euclidienne") ; - l'exponentiation au sens de Montgomery, représentée en faisant précéder l'exposant du symbole "*" et définie comme suit: a *e mod n=ae. r mod n. L'avantage procuré par l'utilisation de l'arithmétique de Montgomery est principalement que les algorithmes n'ont alors pas besoin d'effectuer de manière traditionnelle la réduction modulo n, qui implique une opération de division par un grand nombre, particulièrement complexe à réaliser. L'utilisation de cette arithmétique nécessite toutefois certains calculs complémentaires, qui peuvent dans certains cas diminuer son intérêt, parfois à tel point que la réalisation d'une opération de manière classique est préférable. Par exemple, en remarquant que: a. b mod n=(a *r2) *b mod n, l'utilisation de la multiplication de Montgomery pour effectuer la multiplication modulaire implique le pré-calcul de la constante (r2 mod n) comme cela est par exemple décrit dans la demande de brevet EP 0 704 794. Dans d'autres cas au contraire, ces calculs complémentaires sont largement compensés par les bénéfices liés à l'utilisation de l'arithmétique de Montgomery. Ainsi par exemple, puisque: ae mod n=(a*r2 mod n)*e * 1 mod n, on ramène le résultat de l'exponentiation de Montgomery au résultat de l'exponentiation modulaire en multipliant, au sens de Montgomery, par 1 le résultat de l'exponentiation au sens de Montgomery. On comprend que de telles opérations complémentaires sont de manière générale pénalisantes, que ce soit en terme de temps de calcul ou d'espace mémoire nécessaire par exemple pour le stockage de la constante (r2 mod n) nécessaire. De ce fait, il a récemment,été proposé d'utiliser des protocoles cryptographiques modifiés qui ne puissent utiliser que des opérations de Montgomery, comme par exemple dans la demande de brevet WO 2004/054168. Ainsi, toutes les données utilisent la représentation de Montgomery et aucune conversion n'est nécessaire. La demande de brevet EP 0 578 059 utilise également une solution de ce type, dans laquelle la modification de la relation entre clés publique et privée (c'est-à-dire par là même du protocole) vise à s'affranchir des constantes qui apparaissent dans les opérations de Montgomery et nécessitent la conversion des données traitées. Ces solutions ne sont toutefois pas utilisables de manière généralisée puisqu'elles impliquent que l'ensemble des acteurs du système utilisent l'arithmétique de Montgomery et ne sont donc pas compatibles avec les systèmes utilisés antérieurement et travaillant en arithmétique euclidienne. Dans ce contexte, et afin notamment de réduire les besoins en temps de calcul et en espace de mémoriisation, sans toutefois compromettre la compatibilité avec les systèmes existants, l'invention propose un procédé de stockage (autrement dit, de mémorisation) de donnée de clé cryptographique dans une unité de stockage non volatil d"une entité électronique, caractérisé en ce qu'il comprend les étapes suivantes: conversion d'une donnée, issue d'au moins une partie de clé et destinée à être utilisée avec un opérande au sein d'une opération d'un premier type, en une donnée de clé apte à être utilisée avec ledit opérande au sein d'une opération d'un second type; - stockage de la donnée de clé dans l'unité de stockage non volatil. Lors du fonctionnement ultérieur, on peut ainsi directement lire la donnée de clé dans l'unité de stockage non volatil afin de l'utiliser dans l'opération du second type concernée, sans nécessiter l'opération de conversion déjà effectuée. Selon une possibilité de mise en oeuvre, l'étape de conversion est réalisée par un dispositif extérieur à l'entité électronique et la donnée de clé est transmise du dispositif extérieur à l'entité électronique avant l'étape de stockage. L'étape de stockage est par exemple réalisée durant une étape de 30 personnalisation de l'entité électronique. Dans un mode de réalisation particulièrement pratique lors du fonctionnement ultérieur, l'étape de conversion comprend une multiplication au sens de Montgomery de la donnée issue de la partie de clé par le carré du radical de Montgomery. Dans le même ordre d'idée, l'invention propose également un procédé de traitement de données mis en oeuvre dans une entité électronique comportant une unité de stockage non volatil et nécessitant la détermination du résultat d'une opération d'un premier type impliquant un opérande, caractérisé en ce qu'il comprend les étapes de: - lecture dans l'unité de stockage non volatil d'une donnée de clé ; - réalisation d'une opération d'un second type avec la donnée de clé et ledit opérande. Ainsi, l'opération du second type peut être réalisée en lieu et place de l'opération du premier type, sans nécessiter de conversion des données mises en jeu dans ces opérations. Autrement dit, l'invention propose un système impliquant un procédé de traitement de données pour déterminer le résultat d'une opération d'un premier type impliquant un opérande dans une entité électronique comportant une unité de stockage non volatil, caractérisé en ce qu'il comprend les étapes de: - conversion d'une donnée, issue d'au moins une partie de clé et destinée à être utilisée avec l'opérande au sein de l'opération du premier type, en une donnée de clé apte à être utilisée avec ledit opérande au sein d'une opération d'un second type; - stockage de la donnée de clé dans l'unité de stockage non volatil; - lecture dans l'unité de stockage non volatil de la donnée de clé ; - réalisation de l'opération du second type avec la donnée de clé lue et ledit opérande. Dans certains modes de réalisation, le résultat de ladite opération du second type est égal au résultat de l'opération du premier type. On obtient ainsi directement le résultat recherché. Dans un mode de réalisation particulier, l'opération du second type est une multiplication au sens de Montgornery et l'opération du premier type est une multiplication euclidienne impliquant l'opérande et une clé, ladite donnée de clé étant égale au produit au sens de Montgomery de la clé et du carré du radical de Montgomery. On obtient ainsi une solution particulièrement facile à mettre en oeuvre pour connaître le résultat d'une multiplication euclidienne au moyen d'une multiplication de Montgomery, sans nécessiter une opération complémentaire de conversion des opérandes de la multiplication. Selon d'autres modes de réalisations, le procédé comprend une étape de déconversion du résultat de l'opération du second type afin d'obtenir le résultat de l'opération du premier type. On peut ainsi appliquer l'invention à une gamme plus large d'opérations. Pour certaines applications, le procédé comprend les étapes suivantes: tirage d'un nombre pseudo-aléatoire; - déconversion du nombre pseudo-aléatoire pour obtenir ledit 15 opérande. On obtient ainsi de manière simple un nombre pseudo-aléatoire sous forme convertie et non-convertie utilisables pour des calculs ultérieurs. Par exemple, le procédé comporte une étape de multiplication au sens de Montgomery du nombre pseudo-aléatoire et de l'opérande, ce qui permet de manière simple d'obtenir le carré euclidien d'un nombre pseudoaléatoire. Une au moins des étapes de déconversion précitées peut être réalisée en pratique par une multiplication par l'unité au sens de Montgomery. Une telle opération ne nécessite pas la connaissance du radical de Montgomery ni de son carré. Un tel procédé peut être mis en oeuvre au sein d'un procédé de génération de signature ou d'un procédé de vérification de signature. Dans un premier cas envisageable, l'opération du premier type est une multiplication euclidienne et l'opération du second type est une multiplication de Montgomery. Dans un second cas envisageable, l'opération du premier type est une exponentiation modulaire euclidienne et l'opération du second type est une exponentiation de Montgomery. Dans le cas d'une utilisation de l'invention dans le cadre d'un algorithme utilisant des courbes elliptiques, la donnée de clé peut comprendre les paramètres d'une courbe elliptique et/ou les coordonnées d'un point de base d'une courbe elliptique. Ainsi, ces données n'ont pas à être converties avant leur utilisation au sein d'une opération du second type, par exemple une opération Montgomery. Comme cela ressortira dans la suite, l'invention est bien adaptée au cas où l'entité électronique est une carte à microcircuit, bien que d'autres entités électroniques puissent bien sûr être envisagées. L'invention propose également un dispositif de stockage de donnée de clé cryptographique dans une unité de stockage non volatil d'une entité électronique, caractérisé en ce qu'il comprend: - des moyens de conversion d'une donnée, issue d'au moins une partie de clé et destinée à être utilisée avec un opérande au sein d'une opération d'un premier type, en une donnée de clé apte à être utilisée avec ledit opérande au sein d'une opération d'un second type; - des moyens pour stocker la donnée de clé dans l'unité de stockage non volatil. Selon un mode de réalisation possible, les moyens de conversion sont situés dans un dispositif extérieur à l'entité électronique et les moyens pour stocker la donnée de clé comprennent des moyens de transmission de la donnée de clé du dispositif extérieur à l'entité électronique pour stockage. Un tel dispositif fait par exemple partie d'un dispositif de personnalisation de cartes. L'invention propose en outre un dispositif de traitement de données d'une entité électronique comportant une unité de stockage non volatil et nécessitant la détermination du résultat d'une opération d'un premier type impliquant un opérande caractérisé en ce qu'il comprend des moyens de lecture dans l'unité de stockage non volatil d'une donnée de clé et des moyens de réalisation d'une opération d'un second type avec la donnée de clé et ledit opérande. Vue sous forme d'un système, l'invention propose un dispositif de traitement de données (par exemple sous forme d'un système composé d'un dispositif de personnalisation et d'une entité électronique) pour déterminer le résultat d'une opération d'un premier type impliquant un opérande dans une entité électronique comportant une unité de stockage non volatil, caractérisé en ce qu'il comprend des moyens de conversion d'une donnée, issue d'au moins une partie de clé et destinée à être utilisée avec l'opérande au sein de l'opération du premier type, en une donnée de clé apte à être utilisée avec ledit opérande au sein d'une opération d'un second type, des moyens de stockage de la donnée de clé dans l'unité de stockage non volatil, des moyens de lecture dans l'unité de stockage non volatil de la donnée de clé et des moyens de réalisation de l'opération du second type avec la donnée de clé lue et ledit opérande. Les dispositifs proposés par l'invention peuvent éventuellement présenter des caractéristiques correspondant aux caractéristiques optionnelles de procédé précédemment évoquées et bénéficier ainsi des avantages qui en découlent. D'autres caractéristiques et avantages de la présente invention apparaîtront en outre à la lecture de la description qui suit, faite en référence aux dessins annexés, dans lesquels: la figure 1 représente schématiquement les éléments principaux d'une forme de réalisation possible pour une carte à microcircuit; la figure 2 représente l'allure physique générale de la carte à microcircuit de la figure 1; la figure 3 représente un procédé de stockage de données utilisé dans un premier mode de réalisation de l'invention; la figure 4 représente un procédé de traitement selon le premier mode de réalisation de l'invention; la figure 5 représente un procédé de stockage de données utilisé dans un second mode de réalisation de l'invention; la figure 6 représente un procédé de traitement selon le second mode de réalisation de l'invention. Un exemple d'entité électronique est une carte à microcircuit 10 dont les principaux éléments électroniques sont représentés à la figure 1 et qui comporte un microprocesseur 2 relié d'une part à une mémoire vive (ou RAM de l'anglais Random Access Memory) 4 et d'autre part à une mémoire à semi-conducteur non-volatile réinscriptible 6, par exemple une mémoire morte effaçable et programmable électriquement (ou EEPROM de l'anglais Electrically Erasable Programable Read Only Memory). En variante, la mémoire non- volatile réinscriptible à semi-conducteur 6 pourrait être une mémoire flash. Les mémoires 4, 6 sont reliées au microprocesseur 2 par un bus chacune sur la figure 1; en variante, il pourrait s'agir d'un bus commun. La carte à microcircuit 10 comporte également une interface 8 de communication avec un terminal utilisateur réalisée ici sous forme de contacts dont un assure par exemple une liaison bidirectionnelle avec le microprocesseur 2. L'interface 8 permet ainsi l'établissement d'une communication bidirectionnelle entre le microprocesseur 2 et le terminal utilisateur dans lequel la carte à microcircuit 10 sera insérée. Ainsi, lors de l'insertion de la carte à microcircuit 10 dans un terminal utilisateur, le microprocesseur 2 va mettre en oeuvre un procédé de fonctionnement de la carte à microcircuit 10, selon un jeu d'instructions, stockées par exemple dans une mémoire morte (ou ROM de l'anglais Read-Only Memory) non representée ou dans la mémoire réinscriptible 6, qui définit un programme d'ordinateur. Ce procédé inclut en général l'échange de données avec le terminal utilisateur via l'interface 8 et le traitement de données au sein de la carte à microcircuit 10, et précisément au sein du microprocesseur 2 avec utilisation éventuelle de données stockées dans la mémoire réinscriptible 6 et de données stockées temporairement dans la mémoire vive 4. Des exemples de procédés qui mettent en oeuvre l'invention sont donnés dans la suite. La figure 2 représente l'allure physique générale de la carte à microcircuit 10 réalisée avec la forme générale d'un parallélépipède rectangle de très faible épaisseur. L'interface de communication 8 pourvue des contacts déjà mentionnés apparaît clairement sur la face de la carte à microcircuit 10 visible sur la figure 2, sous forme d'un rectangle inscrit dans la face supérieure de la carte à microcircuit 10. Sur les figures 3 et 4, on a représenté des procédés utilisés dans un premier exemple de mise en oeuvre de l'invention. Le procédé représenté à la figure 3 est un procédé de stockage d'une donnée c dans la mémoire non-volatile 6 qui est par exemple mise en oeuvre lors de l'étape de personnalisation de la carte à microcircuit, c'est-à-dire à l'étape à laquelle l'ensemble des données de base que doit contenir la mémoire non-volatile 6 sont stockées dans la carte à microcircuit. Cette étape est par exemple mise en oeuvre par un système de personnalisation de cartes, fonctionnant selon les mêmes principes qu'un micro-ordinateur, et communiquant à la carte à microcircuit 10, au moyen d'une procédure spéciale, des données à stocker dans la mémoire nonvolatile 6, en général à travers l'interface 8. Lors d'une étape E30, le système de personnalisation reçoit une clé secrète a, par exemple en provenance d'un module matériel sécurisé (ou SHM de l'anglais "Secure Harware Module") tel qu'une carte PCMCIA IBM4758. Dans l'exemple décrit ici, la clé secrète a sera qualifiée d'euclidienne du fait qu'elle est destinée à être utilisée dans un protocole cryptographique défini par des opérations euclidiennes. On réalise alors à l'étape E32 une opération de pré-conversion de la clé secrète euclidienne a en une clé c utilisable directement dans la représentation de Montgomery et obtenue au moyen de l'opération: c=a *r2 mod n, où r est le radical de Montgomery pour la représentation de Montgomery choisie. Comme décrit en détail dans la suite, quand la clé c ainsi déterminée est multipliée au sens de Montgomery par un opérande quelconque, le résultat de la multiplication de Montgomery est égal au produit euclidien de la clé secrète euclidienne a et de l'opérande quelconque lui-même. L'étape E32 est par exemple réalisée par le système de personnalisation de cartes. De tels dispositifs possèdent en général des moyens de calcul et de mémorisation importants de telle manière que la pré-conversion de la clé secrète euclidienne a est réalisable sans difficulté. La clé pré-convertie c peut alors être transmise à la carte à microcircuit 10 pour stockage dans la mémoire non-volatile 6 dans une étape E34. En variante, et notamment lorsque la carte à microcircuit 10 comprend des circuits électroniques de calcul en arithmétique de Montgomery, l'étape de pré-conversion E32 peut être réalisée au sein de la carte à microcircuit 10. Selon une première forme de cette variante, le système de personnalisation transmet via l'interface 8 la clé secrète euclidienne a et le radical de Montgomery r au microprocesseur 2 qui stocke ces valeurs dans la mémoire vive 4, puis effectue la pré-conversion afin d'obtenir la clé préconvertie c (étape E32) et de la stocker dans la mémoire non- volatile 6 (étape E34). Selon une seconde forme de la variante, le radical de Montgomery r est stocké dans la mémoire non-volatile 6 lors d'une étape de personnalisation de la carte comme décrit ci-dessus; lors d'une étape ultérieure à laquelle on souhaite mémoriser une clé secrète dans la carte, la clé secrète euclidienne a est transmise à la carte via l'interface 8 et stockée en mémoire vive 4, le radical de Montgomery r est lu en mémoire non-volatile 6 et stocké dans la mémoire vive 4, puis la carte procède au calcul de la clé pré-convertie c au moyen de la multiplication de Montgomery mentionnée précédemment (étape E32) et stocke la clé pré- convertie c dans la mémoire non-volatile 6 dans la zone qui recevait jusqu'alors le radical de Montgomery r (c'est-à-dire avec écrasement de cette valeur). Cette dernière solution n'est bien sûr utilisable que lorsqu'il est déterminé par avance (par exemple au vu des utilisations prévues de la carte) que les opérations futures n'auront plus recours au radical de Montgomery r. On va à présent décrire en référence à la figure 4 un exemple d'utilisation d'une carte à microcircuit préparé conformément au procédé de stockage qui vient d'être décrit. Selon cet exemple, un tiers cherche à vérifier que son interlocuteur détient bien la clé secrète de valeur a en représentation euclidienne (c'est-à-dire en pratique qu'il possède bien la carte à microcircuit mémorisant la clé secrète euclidienne a), sans toutefois communiquer cette clé secrète. Selon une procédure relativement simple et présentée ici à titre d'exemple de mise en oeuvre de l'invention, le tiers émet une donnée b inconnue du détenteur de la carte (par exemple générée de manière pseudoaléatoire) et attend en retour le produit modulaire (euclidien) de la donnée b émise et de la clé secrète a, produit que seule une personne détentrice de la clé secrète est a priori apte à déterminer. La carte à microcircuit 10 reçoit donc dans une étape E40 la donnée b émise par le tiers et la stocke en mémoire vive 4. A l'étape E42 qui suit, le microprocesseur 2 commande la lecture de la clé pré-convertie c en mémoire non-volatile 6. (On rappelle que cette clé c a été stockée dans la mémoire non volatile 6 à l'étape E34 décrite en référence à la figure 3.) On procède alors à l'étape 1E44 à la multiplication au sens de Montgomery de la clé pré-convertie c lue en mémoire non-volatile 6 et de la donnée b reçue du tiers, afin d'obtenir un résultat d. Ce calcul est par exemple réalisé par un circuit électronique de calcul en arithmétique de Montgomery (non représenté). Du fait que c=a*r2 mod n (par définition: voir l'étape E32 en référence à la figure 3), le résultat de la multiplicatiion au sens de Montgomery de la clé pré-convertie c et de la donnée reçue b est égal au résultat du produit modulaire euclidien de la clé secrète euclidienne a et de la donnée reçue b, selon les formules: c*b mod n=(a*r2 mod n) *b mod n==a.b mod n. On obtient ainsi, en utilisant l'arithmétique de Montgomery mais sans nécessiter le stockage de son radical r, le résultat de la multiplication modulaire par la clé secrète euclidienne a, ce qui permet d'éviter tout changement de protocole avec le tiers. On peut ainsi émettre directement la donnée d à destination du tiers dans une étape E46. On remarque d'ailleurs en ce sens que la représentation euclidienne a et la représentation pré-convertie c (ou représentation de Montgomery) sont bien deux formes de représentation pour une même clé secrète, puisque le détenteur de la carte à microcircuit peut prouver sa connaissance de la clé secrète connue sous sa forme euclidienne par le tiers a alors que seule la clé sous sa forme pré-convertie c est stockée dans la mémoire non volatile 6. On remarque toutefois que la solution proposée implique que l'arithmétique de Montgomery utilisée lors de la pré-conversion (étape E32) et celle utilisée pour la multiplication de Montgomery à l'étape E44 utilisent le même radical r. Un second exemple de réalisation de l'invention va à présent être présenté en référence aux figures 5 et 6. La figure 5 décrit les principales étapes d'un procédé de stockage d'une donnée issue d'une clé en vue de son utilisation ultérieure dans un algorithme de chiffrement de type RSA (pour Rivest-Shamir-Adelman). On rappelle que le système de chiffrement RSA est basé sur l'utilisation d'une clé publique formée de deux entiers (n, e) et d'une clé privée composée de trois entiers (d, p, q), tels que: n = p.q et d.e = 1 mod [(p-1) (q-1)], où p et q sont des nombres premiers. Dans ce système de chiffrement, l'application de la clé privée à un message m consiste à calculer le produit de l'exponentiation modulaire m1 mod n (avec n=p.q), que ce soit pour signer le message m ou le déchiffrer. Pour simplifier le calcul de cette exponentiation modulaire et lorsque le détenteur de la clé privée connaît la décomposition n=p.q, on utilise fréquemment le théorème dit des restes chinois (ou CRT de l'anglais "Chinese Reminder Theorem") selon la formule: m'=[(S2-SI).Apq mod qJ.p+SI, où SI et S2 sont les résultats des exponentiations modulaires partielles détaillées plus bas et où Apq est l'inverse modulaire de p modulo q (c'est-à-dire Apq p-' mod q). Apq est donc issu de la partie de la clé privée formée par les nombres p et q. Lors d'une étape préalable à la réalisation du calcul de l'exponentiation modulaire, par exemple lors de la personnalisation de la carte à microcircuit utilisée (c'est-à-dire lors du stockage des informations nécessaires au fonctionnement de base de cette carte), on met en oeuvre le procédé décrit à la figure 5. Ce procédé commence à l'étape E50 par le calcul du paramètre Apq qui vient d'être défini. On procède ensuite à l'étape E52 où l'on calcule l'inverse modulaire pré-converti A* selon la formule: A*=Apq*r2 mod q. Les calculs réalisés aux étapes E50 et E52 sont par exemple effectués par le système de personnalisation de la carte qui transmet alors le résultat, à savoir l'inverse modulaire pré-converti A*, à la carte à microcircuit au moyen de l'interface 8. La carte à microcircuit procède alors au stockage de l'inverse modulaire pré-converti A* dans sa mémoire non-volatile 6. On va à présent décrire une solution possible pour l'application de la clé privée selon l'algorithme RSA au sein de la carte à microcircuit préparée selon le procédé qui vient d'être décrit en référence à la figure 5. Le procédé proposé utilise le théorème des restes chinois et nécessite donc dans une étape E60 le calcul des résidus modulaires du message in auquel on applique la clé privée, selon les formules: m1=m mod p et me=m mod q. De même, on doit déterminer à une étape E61 les exposants utilisés dans le théorème des restes chinois: dp=d mod (p-1) et dq=d mod (q-1). On procède également à une étape E62 à la lecture dans la mémoire non-volatile 6 de la valeur du paramètre r-2, où r est le radical de Montgomery. Ce paramètre est alors stocké en mémoire vive (ou RAM) 4. On peut alors procéder à l'étape E63 aux exponentiations modulaires partielles en utilisant l'arithmétique de Montgomery selon les formules: Si=(mi*r2 mod p)*dP*1 mod p S2=(m2*r2 mod q)*dq*1 mod q Les valeurs obtenues sont naturellement stockées en mémoire vive 10 4. Après l'étape E63, la mémoire vive comporte donc les valeurs de p, q SI, S2 et r. Comme on le verra dans la suite, le procédé proposé n'utilise plus la valeur du paramètre r2 une fois que les résultats de l'étape E63 sont connus. On peut de ce fait procéder à l'étape E64 à la lecture de l'inverse modulaire pré-converti A* dans la mémoire non-volatile 6 et stocker cette valeur en lieu et place du paramètre r2 dans la mémoire vive, c'est-à-dire avec écrasement de la valeur de r-2. On peut ainsi limiter la taille mémoire nécessaire à l'exécution du procédé (ce qui est particulièrement avantageux dans une carte à microcircuit qui dispose typiquement d'une mémoire RAM de 4 Ko ou 8 Ko alors que la mémorisation du paramètre r2 nécessite à elle seule 1024 bits, i.e. 1/8 Ko). Sur ce point, on peut remarquer de manière générale que la taille en mémoire vive nécessaire à l'exécution d'un calcul est critique du fait qu'il est nécessaire de limiter au maximum les accèsrelativement lourds aux mémoires non-volatiles, comme les mémoires EEPROM. On procède alors à l'étape E65 au calcul suivant, qui utilise une multiplication de Montgomery: [(S2-SI) * A* mod q].p+Sl, qui du fait de la définition de l'inverse modulaire pré-convertie 30 donnée à l'étape E52 vaut précisément: mI=[(S2-SI).Apq mod q]p+SI. On obtient ainsi le résultat de l'exponentiation modulaire en utilisant l'arithmétique de Montgomery, mais sans avoir à stocker en permanence le paramètre r2 en mémoire vive, ni à lire ce paramètre en mémoire non-volatile à chaque réalisation d'une opération au sens de Montgomery. En outre, bien que la carte à microcircuit stocke un paramètre employé comme l'un des opérandes dans une multiplication de Montgomery (ici l'inverse modulaire pré-converti At), le message m, les résultats intermédiaires (notamment Si et S2), et le résultat m' sont liés par les relations classiques dans la représentation euclidienne et le procédé qui vient d'être décrit pourra donc très bien être utilisé dans un système où les autres utilisateurs (par exemple ceux qui souhaitent vérifier la signature réalisée par l'application de la clé privée ou chiffrer le message à destination du détenteur de la clé privée) n'ont pas accès à l'arithmétique de Montgomery. On décrit à présent un troisième exemple de mise en oeuvre de l'invention dans le cadre du schéma de signature Feige-Fiat-Shamir (FFS). Les principes généraux de ce schéma de signature sont par exemple expliqués dans l'ouvrage "Handbook of applied cryptography", de A. Menezes, P. Van Oorschot et S. Vanstone, CRC Press, 1996, paragraphe 11.4. 1. Selon ce schéma, la clé privée est composée de k éléments si, s2, 20..., sk liés aux k éléments v2, ..., Vk qui forment avec le module n la clé publique par la relation: v;=--si-2 mod n, pour tout j en 1 et k. Pour signer un message m dans le cadre de ce schéma de signature, on utilise une carte à microcircuit du type de celle décrite en référence à la figure 1, dans laquelle on a stocké les clés pré-converties S.; définies sur la base des clés s; du schéma de signature choisi selon la relation: *r2 mod n. Pour le stockage des clés pré-converties S*;, par exemple lors de la personnalisation de la carte à microcircuit, on peut utiliser un procédé similaire à celui présenté aux figures 3 et 5. Pour signer un message m selon l'algorithme FFS avec la clé privée composée des éléments s; au moyen d'une telle carte à microcircuit, on procède aux étapes qui suivent: - on choisit un nombre p,, par exemple par tirage de nombres pseudo-aléatoires (ce nombre sera considéré comme la représentation de Montgomery d'un nombre pseudo-aléatoire) ; - calcul de po=p*1 mod n (ce qui revient comme expliqué dans la suite à déconvertir le nombre p1 de telle sorte que le nombre po est considéré comme la représentation euclidienne du nombre représenté par pl dans la représentation de Montgomery) ; - calcul de u=p,*po mod n (ce qui implique que ri po 2 mod n conformément au schéma classique FFS) ; - calcul du k-uplet e=(ei, e2, ..., ek)=h(mIIu) où h est une fonction de hachage et où les composantes e, de e valent 0 ou 1; k k - calcul de s=po* (fJ* S**j" où le symbole n* représente le J=1 1=1 produit des k éléments par des multiplications au sens de Montgomery. De par la définition de S*;, le nombre s n'est autre que la signature du k message m dans le schéma FFS: s= po. _n. On peut remarquer qu'on a ainsi utilisé l'arithmétique de Montgomery pour effectuer les multiplications modulaires requises par le schéma FFS sans toutefois avoir à stocker dans la carte à microcircuit le paramètre de Montgomery r (ni son carré r2). Un quatrième exemple de mise en oeuvre de l'invention, qui va être décrit à présent, se place dans le cadre du schéma de signature GuillouQuisquater (GQ). Les principes d'un tel schéma de signature sont par exemple donnés dans l'ouvrage "Handbook of applied cryptography' déjà mentionné, au paragraphe 11.4.2. Le schéma GQ utilise une clé privée a et une clé publique composée du module n, d'un entier e et d'un identifiant JA du détenteur A de la clé privée a. Pour obtenir la signature d'un message m, le détenteur A de la clé privée a stockée sous forme pré-convertie am dans la mémoire non-volatile d'une carte à microcircuit (où a, =a*r2 mod n) met en oeuvre le procédé suivant au sein de la carte à microcircuit: - choix d'un nombre k inconnu du public et de préférence variable, par exemple par tirage de nombre pseudo-aléatoire; - calcul au moyen d'une exponentiation de Montgomery puis d'une déconversion, du nombre p: p=k*e*1 mod n; - calcul de l=h(mIIp) , où h est une fonction de hachage; - calcul au moyen d'une multiplication au sens de Montgomery utilisant la clé pré-convertie am de la signature s selon la formule: s=k*(am*1)*1 mod n. Les calculs sont donc effectués en utilisant l'arithmétique de Montgomery, mais sans nécessiter la mémorisation du radical de Montgomery r (ou de son carré), grâce à l'utilisation de la clé pré-convertie am et à l'organisation des calculs de manière à n'utiliser que des dé- conversions (c'est-à-dire ici des multiplications par l'unité au sens de Montgomery) qui n'ont pas besoin de la connaissance du radical de Montgomery. La signature obtenue (s, 1) est ainsi identique à celle qui aurait été obtenue par des calculs euclidiens à partir de la clé privé a et pourra donc être vérifiée au moyen de la clé publique (n, e, JA) précédemment évoquée est liée à la clé privée a selon les relations classiques d'arithmétique euclidienne rappelées par exemple dans l'ouvrage susmentionné à l'algorithme 11.47. L'algorithme de vérification de la signature (s, 1) pourra toutefois lui aussi mettre en oeuvre l'invention, par exemple selon le procédé suivant qui utilise des clés pré-converties au sein d'une entité électronique dans laquelle sont mémorisés le carré du radical de Montgomery r2 et l'identifiant pré-converti JAm, qui vaut JAm=JA* r2 mod n: - lecture en mémoire non-volatile 6 du carré du radical de Montgomery r2 et stockage en mémoire vive 4; - conversion de la signature s dans la représentation de Montgomery par le calcul de la signature convertie s,=s * r2 mod n; lecture de la clé pré-convertie JA,n en mémoire non- volatile et stockage de cette clé publique pré-convertie en mémoire vive avec écrasement de la valeur du carré du radical de Montgomery r2 qui y avait été précédemment stockée; - calcul de u=Sm*e * JA,,,*l * 1 mod n; - calcul de l'=h(mjIu) où h est la fonction de hachage déjà mentionnée; - vérification de la validité de la signature par la vérification de l'équation 1=1'. Selon ce dernier mode de réalisation, le carré r2 du radical de Montgomery est stocké dans la mémoire non-volatile de l'entité électronique. Toutefois, le fait de stocker la clé publique (identifiant) JA sous forme pré-convertie autorise l'écrasement en mérnoire vive du carré r2 du radical de Montgomery et ainsi la limitation de la taille mémoire requise pour effectuer l'opération. Un cinquième mode de réalisation de l'invention va à présent être décrit dans le cadre du schéma de signature DSA tel qu'il est décrit dans l'ouvrage "Handbook of applied crytography' déjà mentionné. L'élément de clé publique a et la clé privée a sont stockés sous leur forme pré-convertie respectivement am et am dans la mémoire non- volatile de l'entité électronique qui doit générer la signature, par exemple une carte à microcircuit. On a donc am=a * r,2 mod p où a est la clé publique utilisée dans le protocole considéré et am=a * r22 mod q où a est la clé privée correspondante. (On utilise un radical de Montgomery r, pour les opérations modulo p et un radical de Montgomery r2 pour les opérations modulo q.) La génération de signature peut alors être effectuée selon les étapes suivantes: sélection d'un nombre k, par exemple par tirage d'un nombre pseudo-aléatoire; - calcul de ko = k, * 1 mod q: ko sera considéré comme un nombre pseudo-aléatoire dont la représentation convertie dans la représentation de Montgomery vaut k, ; - calcul de p = (am*k0 * 1 mod p) mod q - calcul de l'inverse de k, modulo q au sens de Montgomery, k," mod q, en calculant (par analogie au cas euclidien) : k,*(g-2) mod q; -calcul des = (k1" * {h(m) + am *p} mod q, avec h une fonction de hachage. On remarque k1*( mod q = ko-1.r2 mod q, c'est-à-dire que k1" est aussi le résultat de la conversion dans la représentation de Montgomery de l'inverse de ko. La signature du message m selon le protocole DSA avec les clés privé a et publique a est donc bien la paire (p, s). Un sixième exemple de réalisation de l'invention va maintenant être décrit dans le cadre du protocole de signature GQ2, décrit par exemple dans l'article "GQ2 une preuve zero-knowledge de connaissance de la factorisation complément essentiel à RSA", de S. Boutiton, F. Daudé et L. Guillou in Actes du Symposium SSTIC04. L'entité électronique utilisée pair le prouveur, par exemple une carte à microcircuit, stocke dans sa mémoire non-volatile m nombres secrets Q1, Q2..., Qm sous leur forme pré-convertie pour les opérations au sens de Montgomery (que l'on pourra ainsi dénommer forme de Montgomery) Q1* , Q2*, ... Qin*, où Q- =Q,.r mod n=Q,*r2 mod n. L'entité électronique détenue par le prouveur met alors en oeuvre les étapes suivantes: - sélection d'un nombre p1, par exemple par tirage d'un nombre pseudo-aléatoire; - déconversion du nombre p1 considéré sous forme de Montgomery afin d'obtenir un nombre po, que l'on peut lui aussi considérer comme obtenu par tirage d'un nombre pseudo-aléatoire, selon la formule po=p1 *1 mod n; - calcul du témoin W=(p1*V mod n) * 1 mod n, où l'exposant de vérification v est une donnée du protocole, Wvalant ainsi po' mod n; - en réponse à chaque défi du vérifieur consistant en une série de m nombres aléatoire d1, d2, ..., dm, calcul de la réponse D=po*(Q7*)*d1 * (Q2*)*d2 * ... * (Qm*)*dm. Grâce à la définition des nombres secrets pré-convertis Q;*, le nombre D vaut po. Q1d1. Q2d2 Qmdm: il s'agit de la réponse à renvoyer au vérifieur sans nécessiter d'autres calculs complémentaires. Comme précédemment, le stockage des clés secrètes pré-converties et la déconversion du nombre pseudo-aléatoire pl ont permis d'effectuer des opérations au sens de Montgomery sur des données reçues d'un dispositif extérieur et destinées à ce dispositif extérieur, sans que celui n'ait nécessairement accès à l'arithmétique de Montgomery, ni que l'entité électronique qui utilise cette arithmétique n'ait recours à la connaissance du radical de Montgomery r (ni de son carré r2). Les modes de réalisation qui viennent d'être présentés ne sont que des exemples possibles de mise en ceuvre de l'invention. Celle-ci pourra s'appliquer à d'autres protocoles que ceux indiqués. Par exemple, en remarquant qu'il existe un isomorphisme entre une courbe elliptique EC: y2=x3+a.x+b mod p et la courbe de Montgomery associée EC* : y*2=x*3+(a*r2)*x+(b*r2) mod p, et par conséquent que si un point P de coordonnées (x, y) appartient à la courbe EC, son image par cet isomorphisme est le point de coordonnées (x*r2, y*r2) de la courbe EC*, on peut utiliser l'invention dans le cadre des algorithmes travaillant sur des courbes elliptiques en stockant dans l'entité électronique les paramètres pré-convertis (a*r2), (b*r2), ainsi que les coordonnées préconverties (x*r2, y*r2) du point de base et en remplaçant les multiplications euclidiennes par des multiplications de Montgomery. En effet, les opérations sur les points de la courbe elliptique utilisées dans les algorithmes cryptographiques reviennent à des multiplications, qui pourront ainsi être effectuées en utilisant l'arithmétique de Montgomery. En outre, lorsque ces opérations utilisent les coordonnées du point de base et que celles-ci sont mémorisées pré-converties dans l'entité électronique, on pourra directement utiliser l'arithmétique de Montgomery sans avoir à mémoriser la valeur du radical de Montgomery r ni son carré r2. Comme dans des exemples précités, il pourra toutefois être nécessaire de déconvertir le résultat obtenu en effectuant sur celui-ci une multiplication par l'unité au sens de Montgomery, qui n'implique pas la connaissance du radical de Montgomery. L'invention n'est pas limitée à une utilisation dans les cartes à microcircuit, mais est au contraire applicable à tout type d'entité électronique, par exemple et de manière non limitative aux ordinateurs, aux assistants personnels numériques (également connus sous l'acronyme anglais PDA), aux téléphones et aux passeports électroniques. REVENDICATIONS, 1. Procédé de stockage de donnée de clé cryptographique dans une unité de stockage non volatil d'une entité électronique, caractérisé en ce qu'il 5 comprend les étapes suivantes: - conversion d'une donnée, issue d'au moins une partie de clé et destinée à être utilisée avec un opérande au sein d'une opération d'un premier type, en une donnée de clé apte à être utilisée avec ledit opérande au sein d'une opération d'un second type; stockage de la donnée de clé dans l'unité de stockage non volatil. 2. Procédé de stockage selon la revendication 1, caractérisé en ce que l'étape de conversion est réalisée par un dispositif extérieur à l'entité électronique et en ce que la donnée de clé est transmise du dispositif extérieur à l'entité électronique avant l'étape de stockage. 3. Procédé de stockage selon la revendication 1 ou 2, caractérisé en ce que l'étape de stockage est réalisée durant une étape de personnalisation de l'entité électronique. 4. Procédé de stockage selon l'une des revendications 1 à 3, caractérisé en ce que l'étape de conversion comprend une multiplication au sens de Montgomery de la donnée issue de la partie de clé par le carré du radical de Montgomery. 5. Procédé de traitement de données mis en oeuvre dans une entité électronique comportant une unité de stockage non volatil et nécessitant la détermination du résultat d'une opération d'un premier type impliquant un opérande caractérisé en ce qu'il comprend les étapes de: - lecture dans l'unité de stockage non volatil d'une donnée de clé ; - réalisation d'une opération d'un second type avec la donnée de clé et ledit opérande. 6. Procédé de traitement de données pour déterminer le résultat d'une opération d'un premier type impliquant un opérande dans une entité électronique comportant une unité de stockage non volatil, caractérisé en ce qu'il comprend les étapes de: - conversion d'une donnée, issue d'au moins une partie de clé et destinée à être utilisée avec l'opérande au sein de l'opération du premier type, en une donnée de clé apte à être utilisée avec ledit opérande au sein d'une opération d'un second type; stockage de la donnée de clé dans l'unité de stockage non volatil; lecture dans l'unité de stockage non volatil de la donnée de clé ; réalisation de l'opération du second type avec la donnée de clé lue et ledit opérande. 7. Procédé de traitement de données selon la revendication 5 ou 6, caractérisé en ce que le résultat de ladite opération du second type est égal au résultat de l'opération du premier type. 8. Procédé de traitement de données selon l'une des revendications 5 à 7, caractérisé en ce que l'opération du second type est une multiplication au sens de Montgomery et en ce que l'opération du premier type est une multiplication euclidienne impliquant l'opérande et une clé, ladite donnée de clé étant égale au produit au sens de Montgomery de la clé et du carré du radical de Montgomery. 9. Procédé de traitement de données selon la revendication 5 ou 6, caractérisé en ce qu'il comprend une étape de déconversion du résultat de l'opération du second type afin d'obtenir le résultat de l'opération du premier type. 10. Procédé de traitement de données selon l'une des revendications 5 à 9, caractérisé en ce qu'il comprend les étapes suivantes: - tirage d'un nombre pseudo-aléatoire; - déconversion du nombre pseudo-aléatoire pour obtenir ledit 5 opérande. 11. Procédé de traitement de données selon la revendication 10, caractérisé en ce qu'il comprend en outre une étape de multiplication au sens de Montgomery du nombre pseudo-aléatoire et de l'opérande. 12. Procédé de traitement de données selon l'une des revendications 9 à 11, caractérisé en ce qu'au moins une étape de déconversion est réalisée par une multiplication par l'unité au sens de Montgomery. 13. Procédé de génération de signature, caractérisé en ce qu'il met en oeuvre un procédé de traitement de données selon l'une des revendications 5 à 12. 14. Procédé de vérification de signature, caractérisé en ce qu'il met 20 en oeuvre un procédé de traitement de données selon l'une des revendications 5 à 12. 15. Procédé selon l'une des revendications 1 à 14, caractérisé en ce que l'opération du premier type est une multiplication euclidienne et en ce que 25 l'opération du second type est une multiplication de Montgomery. 16. Procédé selon l'une des revendications 1, 5 et 6, caractérisé en ce que l'opération du premier type est une exponentiation modulaire euclidienne et en ce que l'opération du second type est une exponentiation de Montgomery. 17. Procédé selon l'une des revendications 1 à 16, caractérisé en ce que la donnée de clé comprend les paramètres d'une courbe elliptique. 18. Procédé selon l'une des revendications 1 à 17, caractérisé en ce 5 que la donnée de clé comprend les coordonnées d'un point de base d'une courbe elliptique. 19. Procédé selon l'une des revendications 1 à 18, caractérisé en ce que l'entité électronique est une carte à microcircuit. 10 20. Dispositif de stockage de donnée de clé cryptographique dans une unité de stockage non volatil d'une entité électronique, caractérisé en ce qu'il comprend: - des moyens de conversion d'une donnée, issue d'au moins une partie de clé et destinée à être utilisée avec un opérande au sein d'une opération d'un premier type, en une donnée de clé apte à être utilisée avec ledit opérande au sein d'une opération d'un second type; - des moyens pour stocker la donnée de clé dans l'unité de stockage non volatil. 23. Dispositif de stockage selon la revendication 20, caractérisé en ce que les moyens de conversion sont situés dans un dispositif extérieur à l'entité électronique et en ce que les moyens pour stocker la donnée de clé comprennent des moyens de transmission de la donnée de clé du dispositif extérieur à l'entité électronique pour stockage. 24. Dispositif de personnalisation de carte caractérisé en ce qu'il comprend un dispositif selon la revendication 20 ou 21. 23. Dispositif selon l'une des revendications 20 à 22, caractérisé en ce que les moyens de conversion sont aptes à mettre en oeuvre une multiplication au sens de Montgomery de la donnée issue de la partie de clé par le carré du radical de Montgomery. 24. Dispositif de traitement de données d'une entité électronique comportant une unité de stockage non volatil et nécessitant la détermination du résultat d'une opération d'un premier type impliquant un opérande caractérisé en ce qu'il comprend: - des moyens de lecture dans l'unité de stockage non volatil d'une donnée de clé ; - des moyens de réalisation d'une opération d'un second type avec la donnée de clé et ledit opérande. 25. Dispositif de traitement de données pour déterminer le résultat d'une opération d'un premier type impliquant un opérande dans une entité électronique comportant une unité de stockage non volatil, caractérisé en ce qu'il comprend: - des moyens de conversion d'une donnée, issue d'au moins une partie de clé et destinée à être utilisée avec l'opérande au sein de l'opération du premier type, en une donnée de clé apte à être utilisée avec ledit opérande au sein d'une opération d'un second type; des moyens de stockage de la donnée de clé dans l'unité de stockage non volatil; - des moyens de lecture dans l'unité de stockage non volatil de la donnée de clé ; - des moyens de réalisation de l'opération du second type avec la donnée de clé lue et ledit opérande. 26. Dispositif de traitement de données selon la revendication 24 ou 25, caractérisé en ce que le résultat de ladite opération du second type est égal au résultat de l'opération du premier type. 27. Dispositif de traitement de données selon l'une des revendications 24 à 26, caractérisé en ce que l'opération du second type est une multiplication au sens de Montgomery et en ce que l'opération du premier type est une multiplication euclidienne impliquant l'opérande et une clé, ladite donnée de clé étant égale au produit au sens de Montgomery de la clé et du carré du radical de Montgomery. 28. Dispositif de traitement de données selon la revendication 24 ou 25, caractérisé en ce qu'il comprend des moyens de déconversion du résultat 10 de l'opération du second type aptes à d'obtenir le résultat de l'opération du premier type. 29. Dispositif de traitement de données selon l'une des revendications 24 à 28, caractérisé en ce qu'il comprend: - des moyens de tirage d'un nombre pseudo-aléatoire; - des moyens de déconversion du nombre pseudo-aléatoire pour obtenir ledit opérande. 30. Dispositif de traitement de données selon la revendication 29, 20 caractérisé en ce qu'il comprend en outre des moyens de multiplication au sens de Montgomery du nombre pseudo-aléatoire et de l'opérande. 31. Dispositif de traitement de données selon l'une des revendications 28 à 30, caractérisé en ce que les moyens de déconversion 25 comprennent des moyens de multiplication par l'unité au sens de Montgomery. 32. Dispositif de génération de signature, caractérisé en ce qu'il comprend un dispositif de traitement de données selon l'une des revendications 24 à 31. 33. Dispositif de vérification de signature, caractérisé en ce qu'il comprend un dispositif de traitement de données selon l'une des revendications 24 à 31. 34. Dispositif selon l'une des revendications 20 à 33, caractérisé en ce que l'opération du premier type est une multiplication euclidienne et en ce que l'opération du second type est une multiplication de Montgomery. 35. Dispositif selon l'une des revendications 20, 24 et 25, caractérisé en ce que l'opération du premier type est une exponentiation modulaire euclidienne et en ce que l'opération du second type est une exponentiation de Montgomery. 36. Dispositif selon l'une des revendications 20 à 35, caractérisé en 15 ce que la donnée de clé comprend les paramètres d'une courbe elliptique. 37. Dispositif selon l'une des revendications 20 à 36, caractérisé en ce que la donnée de clé comprend les coordonnées d'un point de base d'une courbe elliptique. 38. Dispositif selon l'une des revendications 20 à 37, caractérisé en ce que l'entité électronique est une carte à microcircuit.