FR2865086A1

FR2865086A1 - Dispositif et procede pour convertir un premier message en un deuxieme message

Info

Publication number: FR2865086A1
Application number: FR0500259A
Authority: FR
Inventors: Wieland Fischer; Jean Pierre Seifert
Original assignee: Infineon Technologies AG
Current assignee: Infineon Technologies AG
Priority date: 2004-01-12
Filing date: 2005-01-11
Publication date: 2005-07-15
Anticipated expiration: 2025-01-11
Also published as: DE102004001659A1; FR2865086B1; DE102004001659B4

Abstract

Pour convertir un premier message en un deuxième message, le premier message est d'abord converti en un deuxième message auxiliaire défini dans un deuxième groupe de nombres qui se différencie du premier groupe de nombres dans lequel le premier message originel est défini. On définit ensuite une clé auxiliaire publique qui forme dans un troisième groupe de nombres conjointement avec la clé privée originelle une paire de clés du système asymétrique de chiffrement. Le deuxième message auxiliaire est vérifié à l'aide de cette clé auxiliaire publique, à savoir en se référant au troisième groupe de nombres. Le message originel issu du premier groupe est en outre transformé dans le troisième groupe pour ensuite, à partir du message originel transformé et à partir du résultat de l'opération cryptographique de vérification, calculer à l'aide de la clé publique une différence qui est ensuite utilisée finalement pour calculer, à partir du deuxième message auxiliaire défini dans le deuxième groupe de nombres, le deuxième message défini dans le premier groupe de nombres. Comme on utilise différentes opérations pour calculer la différence afin de parer à une DFA et comme la différence est de nouveau intégrée au calcul final du deuxième message à partir du deuxième message auxiliaire, on obtient une défense DFA sûre sans branchement "si".

Description

Dispositif et procédé pour convertir un premier message en un deuxième

message La présente invention concerne des systèmes asymétriques de cryptographie, en particulier des systèmes asymétriques de cryptographie protégés des attaques liées aux erreurs.

On a constaté ces derniers temps que les attaques DFA (DFA: Differential Fault Analysis, analyse différentielle des erreurs) attaquent io très efficacement les systèmes de cryptographie. Dans les systèmes RSA qui utilisent le théorème du reste chinois (TRC; CRT: Chinese Remainder Theorem) pour l'élévation modulaire à une puissance, on a en particulier démontré qu'il suffit déjà d'une seule sortie " incorrecte " due à une attaque DFA pour " découvrir " la clé secrète, par exemple lors du calcul d'une signature. D'autre part, dans le cas de l'algorithme RSA, l'élévation modulaire à une puissance est de préférence calculée à l'aide du TRC puisqu'on peut obtenir une grande efficacité de calcul en particulier pour de grands modules. L'algorithme RSA qui sert à chiffrer des messages ou déchiffrer des messages ou à calculer une signature est décrit dans son application avec ou sans TRC dans le " Handbook of Applied Cryptography " d'A. Menezes et al., CRC Press, 1996. Tandis que pour calculer efficacement l'élévation modulaire à une puissance sans TRC on a besoin d'unités de calcul dont la largeur est au moins aussi grande que le module, dans le cas de l'algorithme RSA du TRC un calcul est possible à l'aide d'une unité de calcul dont le nombre de cellules élémentaires est prédéfini, dont la longueur est donc prédéfinie, et dans laquelle le module (et donc la clé) est presque deux fois plus long que l'unité de calcul. Ceci est particulièrement important pour des applications RSA puisqu'ici à mesure que la longueur de la clé augmente on est d'autant mieux protégé de ce qu'on appelle des " attaques de force brute " dans lesquelles les possibilités sont es- sayées les unes après les autres.

Une attaque DFA part de l'idée d'exposer la puce de cryptographie à une situation extrême pendant qu'elle exécute un calcul cryptographique, de sorte que le résultat de la puce de cryptographie est erroné. Une telle mesure consiste par exemple à exposer la puce pendant qu'elle cal- cule à une forte contrainte mécanique, à un fort rayonnement électromagnétique ou à une succession d'impulsions optiques, etc. de telle manière que par exemple des contenus du registre de la puce deviennent faux ou que des gril-les à l'intérieur de la puce ne remplissent plus leur fonction spécifique mais une autre; il en résulte que le résultat est faux.

On a montré qu'un tel résultat faux était certes faux mais qu'il y a encore tant d'informations sur le secret qui fait l'objet de l'algorithme, comme par exemple la clé de chiffrement dans le cas d'un système symétrique de cryptographie ou la clé privée dans le cas d'un système asymétrique de cryptographie qu'il est possible de mener une attaque DFA efficace.

Des mesures défensives contre de telles attaque DFA consistent dans le cas le plus simple à exécuter deux fois chaque calcul cryptographique: le résultat du premier calcul cryptographique est alors comparé au résultat (identique) du deuxième calcul cryptographique. On réalise une interrogation en fonction de cette comparaison: on fournit une sortie au cas (souhaité) où les deux résultats sont identiques tandis qu'on empêche une sortie au cas où les deux résultats sont différents ou du moins un message d'alarme apparaît. Le coeur de cette mesure défensive consiste donc à empêcher toute sortie au cas où on soupçonne une erreur, de sorte qu'un agresseur n'obtiendra aucune sortie de puce s'il a mené une attaque DFA et qu'il ne peut par conséquent pas tirer de conclusions sur le secret qui fait l'objet de l'algorithme.

La mesure défensive précédente contre des attaques DFA pose problème dans la mesure où elle suppose que la puce ne fait pas la même erreur en réalisant deux fois le calcul. Une telle attaque ne serait pas reconnue.

D'autres mesures consistent à équiper la puce de cryptographie de capteurs de tension, de capteurs de rayonnement, de capteurs de température, etc. pour qu'on puisse directement détecter d'éventuelles attaques extérieures sur la puce afin de pouvoir ensuite empêcher une sortie si une attaque est détectée.

Comme les scénarios d'attaque et le nombre de capteurs qui leur sont liés sont très différents, il n'est pas toujours possible de réaliser une telle mesure défensive ou alors seulement en partie.

Encore d'autres mesures défensives consistent à observer io ou à comparer les uns aux autres des résultats intermédiaires à l'intérieur d'un algorithme cryptographique (assez long). Il existe souvent à l'intérieur d'un algorithme des dépendances qui demandent déjà avant la sortie un certain nombre de résultats intermédiaires qui doivent avoir une certaine relation indépendamment des données à chiffrer ou de la clé. Si on établit que les résul- tats intermédiaires qui doivent avoir une certaine relation lorsque l'algorithme se déroule correctement n'ont pas cette relation, on peut en conclure qu'une attaque est en cours. Dans ce cas, on exécute de nouveau un branchement " si ", c'est-à-dire un saut conditionnel (conditional jump) : on réalise par conséquent une sortie si l'interrogation donne le résultat escompté tandis que, si le résultat diffère des prévisions, la sortie est bloquée ou des messages d'erreur, des interruptions, etc. avertissent par exemple un système d'exploitation qu'une attaque DFA est (sans doute) en cours.

On pare à des attaques DFA sur des systèmes de cryptographie, comme par exemple des systèmes RSA, sur des systèmes symétri- ques comme DES, AES, etc. et sur d'autres systèmes de cryptographie à courbes elliptiques en ce sens qu'on vérifie d'une façon ou d'une autre l'exactitude et que dans le cas d'une erreur on empêche l'émission d'un mes-sage mal chiffré ou d'une signature erronée, par exemple d'une carte à mémoire. Le problème de cette mesure défensive est cependant le branchement " si ". Si un agresseur était en mesure de perturber cette vérification décisive de l'erreur, donc le saut conditionnel, un message mal chiffré ou une " signature " erronée serait émis et l'agresseur mènerait ainsi à bien une attaque DFA.

Le but de la présente invention est de procurer une meilleure conception pour convertir un premier message en un deuxième mes- sage au sens d'une signature ou d'un déchiffrement, cette conception étant plus sûre contre des attaques DFA.

On atteint ce but par un dispositif pour convertir un premier message en un deuxième message en utilisant un système asymétrique de cryptographie qui comprend une clé publique, une clé privée, une première opération de crypto- io graphie réalisable à l'aide de la clé privée et une deuxième opération de cryptographie réalisable à l'aide de la clé publique, le premier message étant défi-ni dans un premier groupe de nombres, caractérisé par: - une installation pour convertir le premier message en un deuxième mes- sage auxiliaire en utilisant la première opération de cryptographie, la clé privée et un paramètre auxiliaire (t), de sorte que le deuxième message auxiliaire est défini dans un deuxième groupe de nombres, une installation pour établir une clé auxiliaire publique, l'installation d'établissement étant conçue pour établir la clé auxiliaire publique de telle manière qu'elle forme, conjointement avec la clé privée dans un troisième groupe de nombres qui est défini par le paramètre auxiliaire, une paire de clés du système de chiffrement asymétrique, une installation pour établir une différence à partir du premier message et d'un résultat d'une conversion du deuxième message auxiliaire en utilisant la deuxième opération de cryptographie et la clé auxiliaire publique en se référant au troisième groupe de nombres, et une installation pour calculer le deuxième message en utilisant la différence et le deuxième message auxiliaire et par un procédé pour convertir un premier message en un deuxième message en utilisant un système asymétrique de cryptographie qui comprend une clé publique, une clé privée, une première opération de cryptographie réalisable à l'aide de la clé privée et une deuxième opération de cryptographie réalisable à l'aide de la clé publique, le premier message étant défini dans un premier groupe de nombres, caractérisé en ce qu'il comporte les étapes suivantes: convertir le premier message en un deuxième message auxiliaire en utilisant la première opération de cryptographie, la clé privée et un paramètre auxiliaire (t), de sorte que le deuxième message auxiliaire est défini dans un deuxième groupe de nombres, établir une clé auxiliaire publique, l'installation d'établissement étant conçue pour établir la clé auxiliaire publique de telle manière que, conjointement avec la clé privée dans un troisième groupe de nombres qui sont io définis par le paramètre auxiliaire, elle forme une paire de clés du système asymétrique de chiffrement, établir une différence à partir du premier message et d'un résultat issu d'une conversion du deuxième message auxiliaire en utilisant la deuxième opération de cryptographie et la clé auxiliaire publique en se référant au troisième groupe de nombres, et calculer le deuxième message en utilisant la différence et le deuxième mes-sage auxiliaire ou par un programme informatique comportant un code de programme pour exécuter le procédé suivant l'invention lorsque le programme informatique tourne sur un ordinateur.

Pour effectuer une conversion, par exemple pour produire une signature ou un message déchiffré à partir d'un message chiffré, conformément à l'invention, donc lors d'une opération de cryptographie qui utilise la clé privée du système asymétrique de cryptographie, un premier message est converti en un deuxième message auxiliaire, le deuxième message auxiliaire étant par exemple une signature. D'après l'invention, le premier message n'est cependant pas directement converti en le deuxième message mais justement en le deuxième message auxiliaire, le deuxième message auxiliaire se distinguant du deuxième message réellement recherché, donc de la signature, en ce que le deuxième message auxiliaire est une signature qui est définie par rapport à un autre groupe de nombres que le premier message (originel). Le deuxième message auxiliaire est maintenant en quelque sorte reconverti, donc par exemple à l'aide d'un algorithme de vérification dans lequel on utilise la clé publique. La clé publique utilisée n'est cependant pas la clé publique originelle mais la clé publique qui correspond à la clé privée originelle dans un troisième espace de nombres, c'est-à-dire dans un troisième groupe de nom- bres, et qui doit d'abord être calculée ou recherchée dans une mémoire. Le résultat de ce calcul de vérification se trouve donc dans un troisième groupe de nombres. Le message originel est en outre également transformé dans le troisième groupe de nombres, à savoir par une règle de transformation qui reproduit le groupe de nombres originel, donc le premier, dans le troisième io groupe de nombres. On calcule maintenant une différence dans ce troisième groupe de nombres.

S'il y a eu une attaque DFA pendant l'opération de calcul, les valeurs des " partenaires de la différence " sont différentes. Si par contre il n'y a pas eu d'attaque DFA (ni d'autre erreur), les partenaires de la différence sont égaux et la différence elle-même est 0. On calcule ensuite en utilisant cette différence la signature effectivement recherchée, à savoir le deuxième message, à partir du deuxième message auxiliaire qui est déjà la signature recherchée mais qui se trouve encore dans un autre espace de nombres. On tient compte du résultat de la différence pour ce calcul final, à savoir de telle manière que s'il n'y a pas eu d'attaque ni d'erreur, la différence qui est alors 0 n'a pas d'effet sur le calcul final, abstraction faite de la transformation dans le groupe de nombres qu'on recommande d'exécuter. Si par contre il y a eu une attaque DFA ou toute autre erreur de calcul, le calcul final est réalisé de telle manière que la différence qui est alors autre que 0 influence fortement le résultat.

On utilise ici de préférence la même règle de calcul que celle qu'on utilise aussi pour une opération de cryptographie. Pour prendre l'exemple de l'algorithme RSA connu, c'est une élévation à une puissance; il est alors tout à fait évident que les nombres seront considérablement modifiés si la différence sert d'exposant dans le cas où la différence est autre que 0 puisque la fonction exponentielle présente ici un gradient particulièrement élevé.

Si par contre le système de cryptographie est un système asymétrique de cryptographie à courbes elliptiques, l'opération qui sert à cal- culer le deuxième message à partir du deuxième message auxiliaire est une multiplication, à savoir la multiplication d'un point situé sur la courbe elliptique par un paramètre.

L'invention permet le résultat exact pour ainsi dire " automatiquement " donc sans boucle " si " au cas où il n'y a pas d'attaque et io cependant d'obtenir en cas d'attaque un résultat fortement modifié qui est en même temps chiffré si l'opération pour calculer le deuxième message à partir du deuxième message auxiliaire est à son tour interprétée comme un chiffre-ment. La clé destinée à " chiffrer " en fin de compte l'erreur éventuellement provoquée par une attaque dépend cependant de l'attaque elle-même, donc de beaucoup d'impondérables et en outre elle n'est mémorisée nulle part, donc ni sur la carte à puce ni ailleurs. C'est pourquoi cette clé ne peut pas être découverte par un agresseur. Un agresseur va en effet produire une sortie lors d'une attaque DFA. Cette sortie est cependant chiffrée par une clé qui n'est plus disponible et est donc inutile à l'agresseur.

On réalise conformément à l'invention un calcul dans plu-sieurs groupes de nombres, donc pour l'exemple du système de cryptographie RSA, dans différentes classes résiduelles de différents modules ou, dans l'exemple de la cryptographie à courbes elliptiques, dans différentes courbes elliptiques. Le premier groupe de nombres est alors une courbe elliptique sur un premier paramètre. Le deuxième groupe de nombres est une courbe elliptique sur un deuxième paramètre différent du premier paramètre et le troisième groupe de nombres est une courbe elliptique sur un troisième paramètre qui est à son tour de préférence différent du premier et du deuxième paramètre.

La conception conforme à l'invention repose en outre sur la découverte qu'il existe des trajets fermés dans un système dont les groupes de nombres sont différents, donc les courbes elliptiques différentes ou les classes résiduelles différentes. Par exemple un calcul de signature depuis un groupe de nombres au groupe de nombres suivant et une opération de vérification ultérieure elle aussi à un groupe de nombres suivant est utile au sens qu'on obtient un message originel qui cependant existe maintenant dans le dernier, donc le troisième, groupe de nombres. En transformant le message originel depuis le premier groupe de nombres dans le troisième groupe de nombres, on obtient un message transformé qu'on peut alors comparer au message calculé par la signature / la vérification pour obtenir une différence.

io D'après l'invention, cette différence n'est cependant pas exploitée à l'aide d'une condition " si " mais on l'utilise pour retransformer dans le premier groupe la signature calculée originelle qui n'existe cependant que dans le deuxième groupe de nombres. Si aucune attaque n'a eu lieu, on obtient la signature. Si par contre il y a eu une attaque, cette dernière étape provoque un important " chiffrement " du deuxième message auxiliaire, ce qui lui ôterait toute signification pour un agresseur.

On doit donc exécuter conformément à l'invention différentes étapes, à savoir la signature, la vérification, la transformation du message à l'intérieur ou sur différents groupes de nombres, de sorte qu'un agresseur devrait agir différemment sur chacune de ces étapes par une attaque DFA, ce qui n'est pas possible. Si une puce est attaquée par exemple en l'irradiant par une lumière très intense, du fait que les opérations de calcul au cours des trois étapes qui permettent d'obtenir la différence nécessaire sont différentes, il est improbable que la puce irradiée en lumière réagisse toujours de la même façon, donc qu'elle fasse toujours la même erreur, de telle manière que des erreurs puissent s'annuler les unes les autres ou qu'on ne puisse pas les reconnaître. C'est ce qui se passe par exemple lorsque deux partenaires de différence sont influencés de la même façon par l'attaque et que donc la différence de ces deux partenaires de différence est nulle. La différence égale à zéro indique cependant qu'aucune erreur n'a eu lieu, de sorte que l'attaque sera réussie, donc qu'une sortie se sera pas empêchée.

Pour les différentes opérations, on a en outre besoin de différentes valeurs issues des mémoires, de sorte qu'ici aussi pour que l'attaque DFA soit couronnée de succès une seule et même attaque devrait avoir des effets différents en fonction de l'opération qui est exécutée.

s Comme on l'a déjà dit, dans la conception anti DFA conforme à l'invention il n'y a pas non plus de branchement " si ". On produit au lieu de cela toujours un résultat sans tenir compte si une attaque a eu lieu ou non. Le résultat n'est pertinent que si aucune attaque n'a eu lieu. Si par contre une attaque a eu lieu, le résultat ne donnera pas l'erreur souhaitée par io l'agresseur mais fournira typiquement cette erreur dans une version très chif- frée dont l'agresseur ne pourra rien faire.

Comme les différentes étapes sont exécutées dans différents espaces de nombres et qu'on évite une boucle " si ", la conception conforme à l'invention permet de rendre inopérantes des attaques DFA puis- qu'une seule et même attaque devrait fonctionner différemment à différentes étapes du calcul et qu'on évite complètement les branchements " si " sensibles à des attaques définies.

Dans ce qui suit, on explique en détail des exemples recommandés de réalisation de la présente invention en se référant aux dessins 20 annexés.

La figure 1 montre sous forme de schéma fonctionnel le dispositif conforme à l'invention pour convertir un premier message en un deuxième message, la figure 2 est un tableau synoptique pour comparer deux systèmes asymétriques de cryptographie, à savoir le système de cryptographie RSA et le système de cryptographie à courbes elliptiques qu'on peut tous deux utiliser à titre d'exemple dans le procédé conforme à l'invention, et la figure 3 est un diagramme des groupes de nombres pour illustrer comment on passe d'un groupe de nombres à l'autre lors-que le premier message est converti en le deuxième mes- 30 sage auxiliaire, comment on calcule la différence et com- ment on calcule en fin de compte le deuxième message en utilisant la différence et le deuxième message auxiliaire.

La figure 1 montre un dispositif pour convertir un premier message en un deuxième message. Le dispositif conforme à l'invention utilise un système asymétrique de cryptographie qui comprend une clé publique, une clé privée, une première opération de cryptographie réalisable à l'aide de la clé privée et une deuxième opération de cryptographie réalisable à l'aide de la clé publique. Selon le cas d'utilisation, la première opération de cryptographie io réalisable à l'aide de la clé privée est une opération de signature ou une opération de déchiffrement. Selon que la première opération de cryptographie réalisable à l'aide de la clé privée est une opération de signature ou une opération de déchiffrement, le premier message représente aussi différentes choses. Au cas où la première opération de cryptographie réalisable à l'aide de la clé privée est l'opération de signature, le premier message est un message non chiffré, donc un message en texte clair, qui doit être signé.

Si par contre la première opération de cryptographie réalisable à l'aide de la clé privée est une opération de décryptage ou de déchiffrement, le premier message est un message chiffré, donc un message en texte chiffré, et le deuxième message est un message déchiffré, donc un message en texte clair.

Dans le cas d'un système asymétrique de cryptographie, il faut alors distinguer deux cas, à savoir la production de la signature qui per-met d'obtenir une signature numérique pour un document et le déchiffrement du message. La clé privée qu'on appelle " e " dans le cadre du système de cryptographie RSA intervient à la production de la signature pour obtenir la signature numérique. Lors de la vérification, on n'a par contre besoin que de la clé publique, de sorte qu'il n'est pas nécessaire ici de prendre des mesures de sécurité. Lors du chiffrement à l'aide d'un système asymétrique de crypto- graphie, on utilise aussi la seule clé publique, de sorte qu'ici non plus il n'est pas nécessaire de prendre des mesures de sécurité puisque la clé publique, comme l'indique son nom, n'est de toute manière pas secrète. II en résulte qu'il n'est pas nécessaire de prendre des mesures de sécurité anti DFA, justement lors du chiffrement.

Mais il en va autrement si un message chiffré (crypté) dans un système asymétrique de cryptographie doit être déchiffré, donc être traité en utilisant la clé privée du destinataire auquel le message est destiné.

Dans ce cadre, le premier message est donc effectivement un message en texte clair comme par exemple lorsqu'on produit une signature numérique à l'aide d'un algorithme asymétrique.

to Le premier message peut cependant aussi être un mes-sage chiffré comme par exemple lorsque des messages sont déchiffrés dans un système asymétrique de cryptographie dans lequel on utilise la clé privée pour le déchiffrage.

La figure 1 montre une installation destinée à fournir un pa- ts ramètre auxiliaire t et désignée par 10 à la figure 1. L'installation 10 est couplée à une installation 12 pour convertir le premier message en un deuxième message auxiliaire. L'installation 12 est adaptée pour fonctionner en ayant recours à la première opération de cryptographie et à la clé privée ainsi qu'au paramètre auxiliaire t, de sorte que le deuxième message auxiliaire est obtenu dans un deuxième groupe de nombres, tandis que le premier message, donc un message non chiffré dans le cas d'une signature ou un message chiffré dans le cas d'un déchiffrement comme on le constate à la figure 1, est obtenu dans le premier groupe de nombres.

Le dispositif conforme à l'invention tel qu'il est représenté à la figure 1 comprend en outre une installation 14 pour établir une clé auxiliaire publique; l'installation 14 pour établir la clé auxiliaire publique est alors conçue pour établir la clé auxiliaire publique de telle manière que, conjointe-ment avec la clé privée dans un troisième groupe de nombres qui est défini par un paramètre auxiliaire, elle forme une paire de clés du système de chif- 3o freinent asymétrique. En d'autres termes, l'installation 14 est adaptée pour établir une clé publique qui, par rapport au nouveau (donc le troisième) sys- tème de nombres, donc le troisième groupe de nombres (nouveau ou qui vient d'être défini), représente conjointement avec la clé privée originelle une paire de clés pour le système asymétrique de cryptographie. La clé auxiliaire publique établie par l'installation 14 de même que le premier message et aussi le paramètre auxiliaire t et encore le deuxième message auxiliaire sont acheminés à une installation 16. L'installation 16 est conçue pour établir une différence à partir du premier message et d'un résultat issu de la conversion du deuxième message auxiliaire en utilisant la deuxième opération de cryptographie et la clé auxiliaire, cette différence étant établie en se référant à un troisième groupe de nombres, comme on le constate également à la figure 1.

La différence est égale à 0 s'il n'y a eu aucune attaque ou aucune erreur. Par contre la différence n'est pas 0 si par exemple des erreurs sont dues à des attaques DFA.

La différence de même que le deuxième message auxiliaire tel qu'il a été établi par l'installation 12 sont acheminés à une installation 18 qui établit le deuxième message, donc la valeur effectivement recherchée, en utilisant la différence et le deuxième message auxiliaire.

La conception conforme à l'invention peut être utilisée pour des systèmes asymétriques de cryptographie quelconques. On se borne dans ce qui suit à expliquer la conception conforme à l'invention à l'aide du système de cryptographie RSA (colonne de gauche à la figure 2) et à l'aide du système de cryptographie à courbes elliptiques (colonne de droite à la figure 2) à titre d'exemple pour des raisons de clarté.

L'algorithme RSA est un excellent exemple de système asymétrique de cryptographie ou de système de cryptographie à clé privée.

On peut utiliser l'algorithme RSA à des fins de signature ou de vérification d'une part et de chiffrement ou de déchiffrement d'autre part. L'algorithme RSA de signature en tant qu'exemple de système asymétrique de cryptogra- phie est par exemple décrit dans le " Handbook of Applied Cryptography " d'A.

Menezes et al., CRC Press, 1996 au chapitre 11.3. Le schéma de signature RSA comprend deux étapes. Chaque entité doit d'abord produire pour soi une clé publique et une clé privée correspondante. On choisit à cet effet d'abord deux nombres premiers p et q différents qui ont de préférence la même taille. Puis on calcule le produit n = pq ainsi que la fonction phi d'Euler c = (t-1) (q-1). Puis on choisit un nombre entier e aléatoire qui vérifie 1 <_ e <_ (D, de ma- nière que le plus grand commun diviseur de e et D soit égal à 1. Puis on utilise l'algorithme d'Euler étendu pour calculer le nombre entier d univoque, où d vérifie également d est supérieur à 1 et inférieur à 'D et où d vérifie en outre: ed = 1 (mod (D). La clé publique de l'entité est alors le nombre entier e (et le module n ou N). Par contre la clé privée de l'entité est d.

io Après qu'une entité a produit pour soi une paire de clés, elle peut signer un message. L'entité calcule à cet effet une élévation modulaire à une puissance sur le message ou sur un nombre entier qu'on dérive de façon univoque du message; lors de l'élévation modulaire à la puissance, le message est la base, la clé privée est l'exposant et le module est la valeur n en fonction de laquelle la paire de clés a été calculée. On en obtient alors la signature pour le message dans une classe résiduelle ou dans un groupe de nombres qui est défini par la valeur n ou N. Pour vérifier la signature A (et si possible aussi pour restituer le message m) , l'autre entité doit d'abord obtenir la clé publique fournie par exemple par l'entité qui signe. Puis on calcule une élévation modulaire à une puissance, à savoir de telle manière que la base soit la signature, l'exposant la clé publique et le module n le même que celui utilisé pour produire la signature. Puis on vérifie si le résultat obtenu par l'élévation modulaire à une puissance se trouve dans une quantité MR donnée. Si ce n'est pas le cas, la signature est rejetée. Mais si cette condition est remplie, le message m est de nouveau obtenu à partir du résultat de l'élévation à une puissance réalisée en vérification, à savoirpar la fonction inverse de la fonction qu'on a utilisée pour produire à partir du message la valeur d'entrée pour la signature.

Dans une autre solution, la signature peut accompagner le document lui-même, de sorte que pour effectuer la vérification il suffit de comparer le document annexé typiquement en texte clair et le résultat obtenu à partir de l'élévation à une puissance réalisée en vérification.

Dans le chiffrement RSA, avant qu'elle puisse fonctionner une entité doit également produire une paire de clés à partir d'une clé publi- que et d'une clé privée (en se référant à un module N, donc dans un groupe de nombres défini). La clé est produite exactement comme dans le cas de la signature RSA. Pour le chiffrement RSA, l'entité qui souhaite chiffrer ses mes-sages doit obtenir la clé publique de l'entité qui doit recevoir le message chiffré. Après qu'elle a obtenu la clé publique, on exécute une élévation modulaire io à une puissance: la base est alors le message à chiffrer, l'exposant est la clé publique de l'entité cible et le module de l'élévation modulaire à une puissance est le module N qui fait partie de la clé publique de l'entité cible.

Les messages chiffrés de cette manière sont ensuite transmis à l'entité cible. L'entité cible réalisera ensuite de nouveau une éléva- tion à une puissance en utilisant sa clé secrète. La base de l'élévation à une puissance pour le déchiffrement ou le décryptage est le message chiffré. L'exposant est la clé privée de l'entité qui déchiffre et le module est le nombre en référence duquel la clé publique e et la clé privée d ont été calculées.

Une attaque DFA est typiquement dirigée contre des mes- sages secrets ou des informations secrètes. Le message secret déterminant est la clé privée, de sorte que typiquement une attaque DFA vaut toujours ses efforts si une entité exécute une opération de cryptographie, donc dans le cas du RSA une élévation à une puissance à laquelle prend part la clé privée. C'est d'une part l'opération de signature et d'autre part l'opération de déchif- frement comme on l'a compris par l'explication ci-dessus.

Dans ce qui suit on explique la conception conforme à l'invention à l'aide de la signature RSA en se référant à la figure 2, colonne de gauche. Sur la figure 2, un bloc 20 variable présente d'abord un aperçu des variables qui forment la base du calcul ou qui sont le résultat du calcul.

Les paramètres d'entrée (In) sont m, d, e et N; m représente le message à signer, d représente la clé privée, e représente la clé pu- blique et N représente le module, donc le produit de deux nombres premiers p et q qu'on a calculés pour produire le chiffrement RSA.

Le paramètre de sortie (Out) est la valeur s de la signature.

Conformément à l'invention, comme on l'a déjà représenté à l'aide de la figure 1, installation 10, on choisit d'abord un nombre entier t de 32 bits, de préférence petit, pour ensuite calculer une signature. Contraire-ment au calcul habituel de la signature, la signature n'est cependant pas cal-culée dans le premier groupe de nombres, donc dans la classe résiduelle en se référant au module N, mais dans un deuxième groupe de nombres, donc io dans la classe résiduelle du module qu'on obtient à partir du produit Nt. On renvoie à ce sujet à un bloc 22 à la figure 2. Pour convertir le premier mes-sage en un deuxième message auxiliaire, on utilise donc la première opération de cryptographie à l'aide de la clé privée, l'élévation à une puissance a donc m pour base et d pour exposant; la conversion dans le deuxième groupe de nombres a alors lieu de telle manière que la réduction n'a pas lieu dans la classe résiduelle du module N comme dans l'équation du bloc 20 mais qu'une réduction est effectuée dans la classe résiduelle du nouveau module, donc du produit Nt: il en résulte que le deuxième message auxiliaire est défini dans le deuxième groupe de nombres.

Un bloc 24 représente la manière d'utiliser la clé auxiliaire publique et. On calcule la clé auxiliaire et exactement de la même façon qu'on calcule habituellement un chiffrement RSA, à la seule différence qu'on ne choisit pas la clé publique et qu'on calcule ensuite la clé privée, comme pour calculer habituellement la clé RSA, mais que la clé privée d est déjà prédéfi- nie. Cette clé privée d correspond à la clé privée originelle dans le premier groupe de nombres. Par contre en utilisant maintenant, au lieu de la clé privée d comme dans l'état de la technique, l'algorithme euclidien étendu, on calcule la clé publique et de manière à satisfaire à l'équation représentée dans le bloc 24 à la figure 2. On fait en outre remarquer que, à la différence de la clé publi- que e dans le bloc 20, la clé auxiliaire publique et ne s'applique pas en se ré- férant au premier groupe de nombres mais est maintenant définie en se réfé- rant à un troisième groupe de nombres puisque l'algorithme euclidien étendu est utilisé de telle manière qu'on satisfait à l'équation donnée dans le bloc 24 et d'après laquelle on a du côté droit, au lieu de la fonction euclidienne cl) du module N, la fonction cD d'Euler du nouveau module t, donc du module auquel on se réfère pour définir le troisième groupe de nombres.

Un bloc 26 à la figure 2 représente quelle équation doit réaliser l'installation 16 afin d'établir la différence pour calculer la différence en se référant au troisième groupe de nombres, donc au groupe qui est défini par le paramètre t. On utilise à cet effet d'abord le message originel m, donc le io message en texte clair qu'il s'agit de signer. Puis le deuxième message auxiliaire s, donc la signature qui a été calculée dans le bloc 22 dans l'exemple montré à la figure 2, est en outre soumise à la deuxième opération de cryptographie, donc à l'élévation à une puissance, mais non pas à l'élévation à une puissance à l'aide d'une clé privée mais à l'élévation à une puissance à l'aide de la clé auxiliaire publique et calculée dans le bloc 24.

Dans un premier exemple de réalisation de la présente invention, la différence de ces deux valeurs est d'abord calculée et ce n'est qu'ensuite qu'elle est réduite de façon modulaire, le paramètre t servant de module. On obtient ainsi la différence dans le troisième groupe de nombres, donc dans la classe résiduelle qui est définie par t en tant que module. Au lieu de cela, on peut aussi calculer la différence comme le représente la deuxième équation dans le bloc 26 à la figure 2. Le message m originel donné dans le premier groupe de nombres peut d'abord être transformé dans le troisième groupe de nombre en le transformant dans la classe résiduelle du module t qui définit le troisième groupe de nombres. L'opération de vérification est en outre intégralement réalisée à l'aide de la clé auxiliaire publique et, donc par la deuxième opération de cryptographie et par la réduction modulaire qui a alors lieu, le paramètre t étant le module.

On constate par le bloc 26 à la figure 2 que la différence doit être 0, donc que le premier terme et le deuxième terme doivent être iden- tiques, s'il n'y a eu aucune erreur ou aucune attaque qui a déclenché une erreur. Si par contre il y a eu une attaque la différence ne sera pas 0. Cela tient à ce que l'attaque a lieu par exemple à l'étape où le deuxième message auxiliaire est calculé, donc au bloc 22 à la figure 2, ou que l'attaque a eu lieu lors-que la clé auxiliaire publique était calculée dans le bloc 24 ou que l'attaque a eu lieu directement lors du calcul de la différence.

Pour calculer en fin de compte le deuxième message effectivement recherché, donc la signature s, on utilise la fonction telle qu'elle est représentée au bloc 28 à la figure 2 pour l'exemple de réalisation recommandé montré à la figure 2. La réduction modulaire qui se réfère au module N sert io à retransformer dans le premier groupe de nombres le deuxième message auxiliaire qui est défini en se référant au deuxième groupe de nombres (à l'aide du module Nt). On utilise en outre la différence f. Cette caractéristique a pour effet qu'on n'a plus besoin de branchement " si " qui représente au contraire un point d'attaque dans l'état de la technique. La raison en est que la fonction qui a recours à la différence ne modifiera pas le deuxième message auxiliaire si la différence f est égale à O. Si par contre la différence n'est pas égale à 0, le deuxième message auxiliaire sera très fortement modifié puisque la différence est dans l'exposant comme le montre le bloc 28 à la figure 2.

En utilisant la différence et le deuxième message auxiliaire, l'installation 18 pour calculer le deuxième message utilise de préférence la même opération de cryptographie, donc l'élévation à une puissance, puisque typiquement une unité de calcul est bien adaptée à cette opération et qu'un calcul exponentiel où une valeur sert d'exposant réagit très fortement aux ex-posants. L'exposant est influencé par la différence. Si par exemple la diffé- rence n'est que relativement faible, l'élévation à une puissance modifiera encore très fortement le deuxième message auxiliaire, ce qui a le même effet envers l'agresseur que si on chiffrait le deuxième message auxiliaire, mais à l'aide d'une clé (f+1) qui n'est nulle part mémorisée, transmise ni enregistrée de quelque autre manière que ce soit, mais qui est effectivement utilisée pour exécuter le calcul dans le bloc 28; celui- ci est cependant par ailleurs inintéressant et il n'est donc pas mémorisé ou " supprimé ".

Dans des exemples de réalisation recommandés de la pré-sente invention, comme on l'a déjà dit le paramètre t est un nombre entier petit qui a typiquement moins de 128 bits, à savoir par exemple 64 ou mieux 32 bits. Il en résulte que le deuxième groupe de nombres, donc le groupe de nombres qui est défini par le module constitué par le produit de N par t, ne devient pas trop grand. Le choix d'un t petit sert en outre à ce que le troisième groupe de nombres, donc la classe résiduelle en se référant au paramètre t en tant que module, soit relativement petit, de sorte que la clé auxiliaire publique ou la différence qui sont déjà des calculs supplémentaires peuvent être io calculés en contrôlant leur complexité.

Pour augmenter l'efficacité, le paramètre t peut aussi être prédéfini, bien que cela réduise la sécurité contre les attaques. En prédéfinissant le paramètre t, il est cependant aussi possible de prédéfinir fermement la clé auxiliaire publique et ainsi que la fonction phi d'Euler cD (t) pour une clé pri- vée d également prédéfinie.

Une autre solution consiste à autoriser que t soit choisi parmi un nombre limité de candidats à la sélection et que la fonction phi d'Euler pour le nombre limité de candidats à la sélection soit mémorisée dans le processeur, par exemple dans la carte à puce elle-même (de préférence chiffrée) afin d'améliorer l'efficacité de la conception DFA conforme à l'invention. Si t est par exemple choisi aléatoirement parmi le groupe restreint de candidats à la sélection, donc en se fondant sur un nombre physique ou pseudoaléatoire, on peut encore obtenir une protection DFA suffisamment sûre tout en réduisant en même temps considérablement la complexité des mesures défensives par rapport au cas où tous les nombres t sont possibles et où on ne peut pas calculer d'avance la fonction phi d'Euler; en outre on ne peut pas non plus calculer d'avance la clé auxiliaire publique et même si différentes clés privées sont autorisées.

Si par contre un processeur de cryptographie est unique-30 ment conçu d'après la présente invention pour une seule clé privée et qu'il n'y a qu'un nombre limité de candidats à la sélection pour le paramètre t, on peut mémoriser la clé auxiliaire publique correspondante en l'associant à chaque candidat à la sélection t sans calculer explicitement la fonction phi d'Euler. Dans ce cas, l'installation 14 pour établir la clé auxiliaire publique est conçue pour avoir accès à une mémoire en utilisant le paramètre ou une information qui dépend du paramètre afin d'appeler dans la mémoire la clé auxiliaire publique correspondante sans que l'installation 14 de la figure 1 doive exécuter elle même quelque calcul logique et/ou arithmétique que ce soit.

On fait en outre remarquer que l'installation 18 pour calculer le deuxième message peut utiliser des fonctions quelconques pour prendre io en compte la différence. On pourrait aussi multiplier la signature auxiliaire par (f+1). On tient alors aussi compte de la différence en ce sens que le message auxiliaire n'est pas modifié si la différence a une valeur prédéfinie, à savoir 0, tandis que le deuxième message auxiliaire est modifié si la différence s'écarte de cette valeur prédéfinie.

En se référant dans ce qui suit à la figure 2, colonne de droite, on représente un autre exemple de la présente invention, à savoir la conception d'après l'invention pour un système de cryptographie à courbes elliptiques. Un bloc 30 représente de nouveau les paramètres d'entrée et de sortie qu'on recherche. On suppose à cet effet une courbe elliptique E, à sa- voir une courbe elliptique sur le paramètre p. On suppose en outre un point P sur la courbe elliptique, le point P étant d'ordre r. On suppose en outre une clé privée m. La courbe elliptique E sur p (E(Z/p)) représente le premier groupe de nombres. Le premier message représente le point P situé sur la courbe elliptique sur p d'ordre r. La signature est le produit de la clé privée m par le point P sur la courbe elliptique E(Z/p). En comparant le bloc 20 et le bloc 30, on voit que l'élévation à une puissance dans le cas du RSA devient une multiplication dans le cas des courbes elliptiques. La réduction modulaire qui a lieu pour le RSA en se référant à un module (mod N) est en outre prise en compte pour des courbes elliptiques en ce que la multiplication de m par p est réalisée sur la courbe elliptique spéciale prédéfinie.

Un bloc 32 à la figure 2 représente les fonctionnalités que l'installation 12 exécute pour transformer le premier message (P) en un deuxième message auxiliaire (Q). On utilise à cet effet la première opération de cryptographie, donc la multiplication, à savoir celle de la clé privée m et du message (du point P sur la courbe elliptique). Le deuxième message auxiliaire existe cependant en se référant au deuxième groupe de nombres, donc comme le représente la figure 2 bloc 32 en se référant à la courbe elliptique sur pt. On recommande pour la présente invention que le paramètre t soit un nombre premier qui soit en outre un nombre relativement petit tout comme io dans le cas du RSA; il a par exemple moins de 128 chiffres et comporte de préférence 32 bits.

Un bloc 34 à la figure 2 représente quelles sont les opérations que l'installation exécute pour établir la clé auxiliaire publique. La clé auxiliaire publique est désignée par m;nv à la figure 2, bloc 34, et on la calcule comme on le montre, à savoir par m-' mod rt; rt y représente l'ordre du point P, donc le message, sur la nouvelle courbe elliptique E(Z/t), la nouvelle courbe elliptique étant définie sur le paramètre t et, dans la terminologie de la présente demande, elle représente le troisième groupe de nombres. Au sens de la présente demande, mn, désigne la clé auxiliaire publique qu'on établit de telle manière que, conjointement avec la clé privée donc avec m dans le troisième groupe de nombres qui est défini par le paramètre auxiliaire, elle forme une paire de clés du système asymétrique de chiffrement.

Un bloc 36 à la figure 2 représente quelles sont les fonctionnalités que l'installation exécute maintenant pour établir la différence R. Dans le bloc 36, le premier terme de la première équation représente la vérification tandis que le point P dans l'équation du bloc 36 est le message originel qui maintenant ne se trouve pas sur les courbes elliptiques E(Z/p) mais sur la courbe elliptique E(Z/t), t étant le paramètre. La différence existe ainsi en se référant au troisième groupe de nombres, à savoir comme point situé sur la courbe elliptique sur t.

Dans la présente invention d'après l'exemple de réalisation recommandé représenté à la figure 2, le point R qui représente la différence se trouve sur la courbe elliptique sur t en coordonnées projetées, c'est-àdire que R = (x: y: z). Tout comme dans le cas du RSA au bloc 26, la différence est R = 0, donc au moins les coordonnées x et y sont égales à 0 si pendant tout le calcul il n'y a pas eu de problèmes qui ont provoqué une erreur, comme par exemple une attaque DFA. Comme on le constate par le bloc 38, l'installation 18 pour calculer le deuxième message en utilisant la différence et le deuxième message auxiliaire calcule par exemple uniquement une somme io à partir des deux premières coordonnées x, y du point R pour obtenir un nouveau paramètre k. Ce paramètre k est additionné à la valeur 1 et ensuite la somme k+1 est encore additionnée au point Q, à savoir sur la courbe elliptique E(Z/p). On constate que si la différence est égale à 0, donc que les coordonnées du point R sont égales à 0, le paramètre k est aussi égal à 0, de sorte que l'opération dans le bloc 38 est une opération triviale, à savoir la multiplication par la valeur " 1 ", ce qui évidemment ne modifie en rien le deuxième message auxiliaire.

Comme dans le bloc 28 pour l'exemple RSA, on obtient donc simplement dans le bloc 38 que le deuxième message auxiliaire, effecti- vement donné sur la courbe elliptique E(Z (pt)), est maintenant donné sur la courbe elliptique E(Z/p), donc dans le premier groupe de nombres pour lequel on a originellement recherché la signature.

En se référant à la figure 3, on représente dans ce qui suit la conception principale sur laquelle repose la présente invention. On repré- sente à cet effet schématiquement les trois groupes de nombres. Le premier groupe de nombres 40 est le groupe qui de l'extérieur est transparent à l'utilisateur. Dans ce premier groupe de nombres, le système de cryptographie a une clé privée donnée. Le module ou la courbe elliptique qui définissent le premier groupe de nombres est donc transparent vu de l'extérieur. Il n'en va pas de même pour le deuxième et le troisième groupes de nombres. Le deuxième groupe de nombres se différencie du premier groupe en ce que dans l'exemple de RSA le module est plus grand, donc égal au produit Nt, tandis que, dans l'exemple des courbes elliptiques, la courbe elliptique E n'est pas définie sur p mais sur le produit pt. Le troisième groupe de nombres se différencie du premier groupe et du deuxième groupe en ce qu'il est défini en se référant au module t ou que la courbe elliptique est définie sur t. Le premier groupe de nombres est par conséquent certes plus grand que le troisième groupe de nombres mais il est plus petit que le deuxième groupe de nombres. En d'autres termes, il n'y a pas de conversion directe du premier groupe en deuxième groupe ou du troisième groupe en premier groupe, comme le repréio sentent les flèches 46 et 47. Comme le montre une flèche 48, une opération de signature à l'aide du paramètre permet cependant de convertir le premier groupe en deuxième groupe, on ne se réfère cependant pas au premier mes-sage mais on se réfère à la signature du deuxième message. Comme on le voit à la figure 3, la signature n'est cependant pas définie dans le premier groupe de nombres mais dans le deuxième groupe de nombres, c'est pour-quoi on l'appelle aussi deuxième message auxiliaire dans la présente de-mande.

Les résultats d'une deuxième étape de vérification désignée par 50 à la figure 3 et d'une troisième étape de simple transformation désignée par 52 à la figure 3 sont soumis à une formation de la différence 54 par l'installation 16 pour établir la différence; la formation de la différence n'a maintenant plus lieu dans le premier ou dans le deuxième groupe de nombres mais dans le troisième groupe de nombres, donc dans le groupe défini par le (plus petit) paramètre t. Comme on le voit également à la figure 3, le résultat de cette formation de la différence 54 sera ensuite pris en compte lorsque le deuxième message est calculé à partir du deuxième message auxiliaire au cours d'une étape 56, comme le représente le bloc 54 à droite de l'étape 56.

La figure 3 représente un diagramme qui présente un trajet composé des étapes 48, 50, 52 qu'on désigne aussi par 1, 2, 3. En d'autres termes, le résultat de l'étape 52, donc la transformation du premier message issu du premier groupe de nombres dans le troisième groupe de nombres doit être égal au résultat des étapes 1 et 2 (49, 50) s'il n'y a pas eu d'attaque. D'autres trajets sont aussi possibles dans le diagramme de la figure 3: à par-tir du deuxième message auxiliaire, le deuxième message auxiliaire est transformé par réduction modulaire à l'aide du module t dans le troisième groupe de nombres comme l'indique une flèche 60 pour arriver à une signature dans le troisième groupe de nombres. La signature dans le troisième groupe de nombres pourrait aussi conduire au troisième groupe de nombres, d'abord par réduction modulaire à l'aide de N (flèche 62) puis par réduction modulaire à l'aide du module t (flèche 64). Le deuxième message auxiliaire qui était originellement défini dans le deuxième groupe de nombres serait alors transformé par la fonctionnalité de l'installation pour former la différence d'abord dans le troisième groupe de nombres pour ensuite être soumise à un déchiffrement (dans le cas d'un chiffrement) directement dans le troisième groupe de nombres afin d'obtenir le message originel, mais dans le troisième groupe de nombres. Une flèche discontinue 66 à la figure 3 représente l'utilisation de la clé publique directement dans le troisième groupe de nombres.

La conception conforme à l'invention est particulièrement adaptée pour parer à des attaques DFA, en ce sens qu'on souhaite certes obtenir finalement le deuxième message, donc par exemple la signature, dans le premier groupe de nombres mais que le premier message est converti dans un autre groupe de nombres en utilisant une opération de signature, à savoir dans le deuxième groupe, et que le deuxième message auxiliaire est converti dans un troisième groupe de nombres pour y produire une différence entre le message originel qui a cependant également été convertie dans le troisième groupe de nombres. Cette différence sert ensuite à convertir le deuxième message auxiliaire en deuxième message recherché.

On fait remarquer que de cette manière, comme le montre en l'illustrant la figure 3, la fonctionnalité est exactement calculée par des dé- tours comme le représente la flèche pleine 70, mais on ne suit pas ici cette flèche pleine 70. La présente invention permet donc d'une part de se passer d'un branchement " si " pour obtenir une défense DFA et d'autre part de calcu- ler le deuxième message " par des détours " pour faire des calculs dans différents groupes de nombres et pour obtenir finalement la différence 54. Les cal-culs qui mènent à la différence 54 sont cependant différents; il en résulte qu'il est très probable qu'une seule et même attaque produira des erreurs de calcul différentes, de sorte qu'en cas d'attaque on obtient une différence qui n'est pas égale à 0. Si par contre il y a une attaque telle que le premier message, par exemple sur le trajet de la flèche 70, est soumis à une signature et qu'il est ensuite vérifié dans le sens contraire à la flèche 70 pour ensuite former une différence à partir du premier message originel et du message obtenu par io la vérification, on utilise la même opération pour le calcul à l'aller et pour le calcul au retour; il en résulte qu'il pourrait ici y avoir une probabilité qu'une seule et même attaque provoque aussi la même erreur dans le calcul à l'aller et dans le calcul au retour, de sorte qu'on obtient une différence égale à 0, ce qui signifierait que l'attaque DFA ne serait pas reconnue. On remédie à cela conformément à l'invention puisqu'on utilise différentes étapes de calcul pour réaliser les étapes 48, 50 et 52; il en résulte qu'une seule et même attaque DFA provoquera aussi des erreurs différentes, de sorte que lors d'une attaque on obtient toujours une différence qui n'est pas égale à 0.

En fonction de la situation, le procédé conforme à l'invention et destiné à convertir un message peut être installé sous forme matérielle ou sous forme logicielle. L'installation peut être réalisée sur un support d'enregistrement numérique, en particulier sur une disquette ou un cédérom, à l'aide de signaux de commande, lisibles par des moyens électroniques, qui pourraient interagir avec un système informatique programmable de manière à exécuter le procédé. De façon générale l'invention consiste donc aussi en un produit de programmation informatique muni d'un code de programme mémorisé sur un support lisible par une machine et destiné à exécuter le pro-cédé conforme à l'invention pour convertir un premier message en un deuxième message lorsque le produit de programmation informatique tourne sur un ordinateur. En d'autres termes, l'invention peut aussi prendre la forme d'un programme informatique muni d'un code de programme destiné à exécu- 12.04.2005 05 00259 ter le procédé pour convertir le premier message en le deuxième message lorsque le produit de programmation informatique tourne sur un ordinateur. Suivant un mode de réalisation préféré de l'invention, le premier groupe de nombres, le deuxième groupe de nombres et le troisième groupe de nombres sont définis de telle manière qu'un message du premier groupe n'est pas reproduit dans le deuxième groupe sans opération de cryptographie, il existe une reproduction d'un message du deuxième groupe dans le premier groupe, il existe une reproduction d'un message du premier groupe dans le troisième groupe sans opération de cryptographie, et il n'existe pas de reproduction d'un message du troisième groupe dans le deuxième groupe sans opération de cryptographie.

Claims

26 Revendications

1. Dispositif pour convertir un premier message en un deuxième message en utilisant un système asymétrique de cryptographie, qui comprend une clé publique, une clé privée, une première opération de cryptographie réalisable à l'aide de la clé privée et une deuxième opération de cryptographie réalisable à l'aide de la clé publique, le premier message étant défini dans un premier groupe de nombres (40), caractérisé par: une installation (12) pour convertir le premier message en un deuxième io message auxiliaire en utilisant la première opération de cryptographie, la clé privée et un paramètre auxiliaire (t), de sorte que le deuxième message auxiliaire est défini dans un deuxième groupe de nombres (42), une installation (14) pour établir une clé auxiliaire publique, l'installation (14) d'établissement étant conçue pour établir la clé auxiliaire publique de telle manière qu'elle forme, conjointement avec la clé privée dans un troisième groupe de nombres (44) qui est défini par le paramètre auxiliaire, une paire de clés du système de chiffrement asymétrique, - une installation (16) pour établir une différence à partir du premier mes-sage et d'un résultat d'une conversion du deuxième message auxiliaire en utilisant la deuxième opération de cryptographie et la clé auxiliaire publi- que en se référant au troisième groupe de nombres, et une installation (44) pour calculer le deuxième message en utilisant la différence et le deuxième message auxiliaire.

2. Dispositif selon la revendication 1, caractérisé en ce que le premier message est un message non chiffré, le deuxième message est une signature du message non chiffré, la première opération de cryptographie est une opé- ration de signature et la deuxième opération de cryptographie est une opération de vérification.

3. Dispositif selon la revendication 1, caractérisé en ce que le premier message est un message chiffré et le deuxième message est une version déchiffrée du premier message, et dans lequel la première opération de cryptographie est une opération de déchiffrement et la deuxième opération de cryptographie est une opération de chiffrement.

io 4. Dispositif selon l'une des revendications précédentes, caractérisé en ce que le système asymétrique de cryptographie est un système de cryptographie RSA, le premier groupe de nombres (40) est une classe résiduelle en se référant à 15 un module (N), le deuxième groupe de nombres (42) est une classe résiduelle en se référant au module multiplié par le paramètre auxiliaire, et le troisième groupe de nombres (44) est une classe résiduelle en se référant au paramètre auxiliaire en tant que module.

5. Dispositif selon la revendication 4, caractérisé en ce qu'il présente en outre une installation (10) pour fournir le paramètre auxiliaire, l'installation (10) étant conçue pour que le paramètre auxiliaire fourni soit un nombre entier inférieur au module.

6. Dispositif selon la revendication 5, caractérisé en ce que le nombre entier a 128 chiffres ou moins de 128 chiffres.

7. Dispositif selon l'une des revendications 4 à 6, caractérisé en ce que 30 la première opération de cryptographie est une élévation à une puissance du premier message à l'aide de la clé privée, et la deuxième opération de cryptographie est une élévation à une puissance du deuxième message à l'aide de la clé publique.

8. Dispositif selon l'une des revendications 4 à 7, caractérisé en ce que l'installation (12) de conversion est conçue pour exécuter l'opération suivante: s = md mod Nt, où s représente le deuxième message, m représente le premier message, d représente la clé privée et N représente le module, t représente le paramètre auxiliaire et mod représente une réduction modulaire. i0

9. Dispositif selon l'une des revendications 4 à 8, caractérisé en ce que l'installation (14) destinée à établir la clé auxiliaire publique est conçue pour calculer la clé auxiliaire publique de manière à satisfaire à la relation sui-vante: etd = 1 mod cD(t), où et est la clé auxiliaire publique, d est la clé privée, mod représente la réduction modulaire, D(t) est la fonction phi d'Euler du paramètre auxiliaire t et t est le paramètre auxiliaire.

10. Dispositif selon l'une des revendications 4 à 9, caractérisé en ce que l'installation (16) destinée à établir la différence est conçue pour établir la différence d'après l'équation suivante: f = (m-set) mod t, où f représente la différence, m représente le premier message, s représente le deuxième message auxiliaire, et représente la clé auxiliaire publique, mod représente la réduction modulaire et t est le paramètre auxiliaire.

11. Dispositif selon l'une des revendications 4 à 10, caractérisé en ce que l'installation (18) destinée à calculer le deuxième message est conçue pour réaliser l'opération suivante: so = st' mod N, où so est le deuxième message, s est le deuxième message auxiliaire, f est la différence, mod représente la réduction modulaire et N est le module qui défi-nit le premier groupe de nombres (40).

12. Dispositif selon l'une des revendications précédentes, caractérisé en ce que l'installation (18) de calcul est conçue pour calculer le deuxième message de telle manière qu'il soit défini dans le premier groupe de nombres (42).

13. Dispositif selon l'une des revendications précédentes, caractérisé en ce io que le premier groupe de nombres comprend des nombres supérieurs au troisième groupe de nombres et des nombres inférieurs au deuxième groupe de nombres.

14. Dispositif selon l'une des revendications précédentes, caractérisé en ce que l'installation (18) destinée à calculer le deuxième message est conçue pour soumettre le deuxième message auxiliaire à une fonction et à un para-mètre, un élément neutre étant défini pour la fonction, et le paramètre combiné à la différence donne l'élément neutre, lorsque l'installation (12) de conversion, l'installation (14) d'établissement, l'installation (16) d'établissement ou l'installation (18) de calcul n'ont commis aucune erreur, et le paramètre combiné à la différence ne donne pas l'élément neutre lorsqu'il y a eu une erreur.

15. Dispositif selon la revendication 14, caractérisé en ce que la fonction est identique à la première et/ou à la deuxième opération de cryptographie.

16. Dispositif selon l'une des revendications 1 à 3, caractérisé en ce que le système asymétrique de cryptographie est. un système de cryptographie à courbes elliptiques, le premier groupe (40) est une courbe elliptique sur un nombre (p), le deuxième groupe (42) est une courbe elliptique sur un nombre (p) multiplié par le paramètre auxiliaire (t), le troisième groupe (44) est une courbe elliptique sur le paramètre auxiliaire (t).

17. Dispositif selon la revendication 16, caractérisé en ce qu'il y a en outre une installation (10), destinée à fournir le paramètre auxiliaire, qui fournit le paramètre auxiliaire de telle manière qu'il soit un nombre premier.

io 18. Dispositif selon la revendication 17, caractérisé en ce que le nombre premier a 64 chiffres ou moins.

19. Dispositif selon l'une des revendications 16 à 18, caractérisé en ce que la première opération de cryptographie représente une multiplication d'un point sur une courbe elliptique à l'aide de la clé privée, la deuxième opération de cryptographie représente une multiplication d'un point sur une courbe elliptique à l'aide de la clé publique, et le point sur la courbe elliptique représente le premier message.

20. Dispositif selon l'une des revendications 16 à 19, caractérisé en ce que le premier message est un point sur la courbe elliptique sur le nombre et le deuxième message est un autre point sur la courbe elliptique sur le nombre.

21. Dispositif selon l'une des revendications 16 à 20, caractérisé en ce que l'installation (12) de conversion est conçue pour exécuter l'opération suivante: Q = mP sur E(Z/pt), où Q est le deuxième message auxiliaire, m est la clé privée, P est le mes-sage, p est un nombre et t est le paramètre auxiliaire.

22. Dispositif selon l'une des revendications 16 à 22, caractérisé en ce que l'installation (14) destinée à établir la clé auxiliaire publique est conçue pour calculer l'équation suivante: 2865086 34 min, = m-' mod rt, où rt est un ordre d'un point P situé sur la courbe elliptique sur le paramètre t, mod représente une réduction modulaire, m-' est une clé privée inversée et min est la clé auxiliaire publique.

23. Dispositif selon l'une des revendications 4 à 9, caractérisé en ce que l'installation (16) destinée à établir la différence est conçue pour calculer l'équation suivante: R = m;nvQ P sur E(Z/t), io où R représente la différence et en même temps un point sur la courbe elliptique E(Z/t), m;nv est la clé auxiliaire publique, Q est le deuxième message auxiliaire, P est le premier message et t est le paramètre auxiliaire.

24. Dispositif selon l'une des revendications 16 à 23, caractérisé en ce que l'installation (18) destinée à calculer le deuxième message est conçue pour calculer un paramètre auxiliaire qui est égal à une somme d'une première et d'une deuxième coordonnées projectives de la différence et l'installation (18) de calcul est conçue pour exécuter l'équation suivante: S:=(k+1) Q, où S est le deuxième message, k est le paramètre auxiliaire et Q est le deuxième message auxiliaire.

25. Dispositif selon la revendication 24, caractérisé en ce que l'installation (18) de calcul est conçue pour calculer le deuxième message sous forme de 25 point situé sur la courbe elliptique sur le nombre p. 26. Dispositif selon l'une des revendications précédentes, caractérisé en ce que le premier groupe de nombres, le deuxième groupe de nombres et le troisième groupe de nombres sont définis de telle manière qu'un message du premier groupe n'est pas reproduit dans le deuxième groupe sans opération de cryptographie, en ce qu'il existe une reproduction d'un message du deuxième groupe dans le premier groupe, en ce qu'il existe une reproduction d'un message du premier groupe dans le troisième groupe sans opération de cryptographie, et en ce qu'il n'existe pas de reproduction d'un message du troisième groupe dans le deuxième groupe sans opération de cryptographie.
27 Procédé pour convertir un premier message en un deuxième message en utilisant un système asymétrique de cryptographie qui comprend une clé publique, une clé privée, une première opération de cryptographie réalisable à l'aide de la clé privée et une deuxième opération de cryptographie réalisable à l'aide de la clé publique, le premier message étant défini dans un premier io groupe de nombres (40), caractérisé en ce qu'il comporte les étapes suivantes: convertir (12) le premier message en un deuxième message auxiliaire en utilisant la première opération de cryptographie, la clé privée et un para-mètre auxiliaire (t), de sorte que le deuxième message auxiliaire est défini dans un deuxième groupe de nombres (42), établir (14) une clé auxiliaire publique, l'installation (14) d'établissement étant conçue pour établir la clé auxiliaire publique de telle manière que, conjointement avec la clé privée dans un troisième groupe de nombres (44) qui sont définis par le paramètre auxiliaire, elle forme une paire de clés du système asymétrique de chiffrement, établir (16) une différence à partir du premier message et d'un résultat issu d'une conversion du deuxième message auxiliaire en utilisant la deuxième opération de cryptographie et la clé auxiliaire publique en se référant au troisième groupe de nombres, et calculer (44) le deuxième message en utilisant la différence et le deuxième message auxiliaire.

28. Programme informatique comportant un code de programme pour exécuter le procédé selon la revendication 27 lorsque- le programme informatique tourne sur un ordinateur.