Brevet FR3038474A1 — publié le 20170106

MISE EN OEUVRE OPTIMISEE DU HFE La demande concerne notamment une mise en oeuvre optimisée de l'algorithme HFE (acronyme de l'expression de langue anglaise Hidden Field Equations). Pour concevoir des cryptosystèmes, une alternative au recours aux problèmes de la théorie des nombres consiste à s'appuyer sur le problème de résolution d'un système polynomial (désigné par l'acronyme PoSSo), La branche de la cryptographie s'appuyant sur PoSSa est appelée cryptographie multivariée. Le problème PoSSo étant NP-difficile, un cryptosystème multivarié résiste aux attaques quantiques. A l'inverse, on connaît des algorithmes quantiques pour factoriser un entier ou résoudre le problème du logarithme discret en un temps polynomial. Ces algorithmes mettraient à mal la sécurité des algorithmes asymétriques RSA ou encore EIGamal dans un monde où l'informatique quantique serait accessible, tandis qu'un oryptosystème basé sur un problème NP-difficile (tel que PoSSo) resterait pérenne. L'avènement des ordinateurs quantiques n'est pas encore d'actualité, mais l'usage d'algorithmes tels que le RSA est extrêmement répandu (notamment au sein des cartes à puce). il est donc judicieux de rechercher des cryptosystèmes s'appuyant sur des problèmes mathématiques difficiles que les ordinateurs quantiques ne pourraient pas aisément résoudre. Les cryptosystèmes multivariés considérés comme parmi les meilleurs présentent, outre une sécurité que l'on considère accrue, une certaine efficacité en terme notamment de vitesse de chiffrement et de déchiffrement. Certains cryptosystèmes symétriques (tels que QUAD) ou des fonctions de hachage utilisent le principe de la cryptographie multivariée. De façon générale, en cryptographie symétrique (non nécessairement multivariée, par exemple en QUAD, DES, 3DES, AES, etc.), chaque utilisateur dispose d'une clé (secrète) qu'il doit partager avec ses correspondants. Toute personne ayant accès à une telle clé secrète peut déchiffrer tout ce qui a été 3038474 2 chiffré avec cette clé, et peut chiffrer ce que bon lui semble avec cette clé comme si elle en était titulaire. Toutefois, la cryptographie multivariée est principalement utilisée en cryptographie asymétrique. La cryptographie asymétrique s'appuie sur des 5 paires de clés. Ainsi, au lieu de disposer d'une seule clé (secrète), chaque utilisateur dispose d'une paire de clés, dont l'une est publique (elle peut être librement partagée sans mettre en péril la sécurité) et l'autre privée. On parle habituellement de clé privée en cryptographie asymétrique et de clé secrète en cryptographie symétrique, bien que les termes privée/secrète soient utilisés 10 indistinctement par certains auteurs. En cryptographie asymétrique, la distribution des clés se trouve grandement simplifiée. La clé publique peut être échangée aisément. Il suffit par exemple de la faire certifier par une autorité de certification, qui émet un certificat contenant cette clé publique. Le certificat peut ensuite être échangé librement sans sécurité particulière (abstraction 15 faite notamment de la vérification éventuelle de la validité temporelle du certificat et de listes de révocations). Quant à la clé privée, elle est propre à son utilisateur et n'a donc pas de raison d'être partagée. Par exception, les clés privées de chiffrement peuvent être archivées de façon sécurisée. Ceci évite que la perte de la clé privée n'entraîne l'impossibilité de déchiffrer les 20 informations chiffrées avec la clé publique correspondante. L'application consécutive, à un message donné, de la clé privée et de la clé publique, ou inversement de la clé publique puis de la clé privée, est l'identité (on retrouve le message d'origine à l'issue des deux applications). Une paire de clé peut donc offrir plusieurs types d'utilisations. Une personne peut ainsi utiliser la clé 25 publique d'un tiers pour chiffrer un message à son attention. Elle sait que seul ce tiers détient la clé privée correspondante et donc que seul ce tiers peut déchiffrer le message. En pratique, on utilise généralement un algorithme symétrique, plus rapide, pour opérer le chiffrement de données, et on utilise la clé publique pour ne chiffrer que la clé symétrique utilisée (après application 30 d'une opération dite de "padding" de cette clé symétrique visant à la compléter avec des données de façon à obtenir un bloc compatible avec l'opération à clé publique) Cette clé symétrique peut ainsi être générée pour un usage unique 3038474 et être facilement partagée avec le tiers. Le problème du partage des clés en cryptographie symétrique est ainsi résolu par la cryptographie asymétrique. A l'inverse, une personne peut utiliser sa clé privée pour signer un message et communiquer le message ainsi signé à des tiers. Habituellement, on applique 5 un algorithme de hachage ("hash") sur le message à signer, et c'est ce hash que l'on signe avec la clé privée (après padding" approprié). Les tiers peuvent aisément se procurer la clé publique du prétendu signataire, et vérifier que le message a été signé par la bonne personne (seul la personne indiquée dans le certificat contenant la clé publique détient la clé privée correspondante, et 10 personne d'autre qu'elle n'a donc pu signer). Des variantes sont possibles. Il est également possible d'utiliser la cryptographie asymétrique à des fins d'authentification. Par exemple, une personne souhaitant authentifier un tiers peut générer un nombre aléatoire et le lui transmettre. Le tiers est alors censé signer ce nombre aléatoire et renvoyer la signature. De nombreux autres 15 usages de la cryptographie asymétrique sont connus et conventionnels depuis plusieurs décennies. En cryptographie asymétrique multivariée, la clé publique est déterminée par un système de polynômes en plusieurs variables. Pour pouvoir être inversé, ce système dispose d'une trappe. Le premier cryptosystème utilisant 20 ce concept, appelé C*, a été proposé par T. Matsumoto et H. lmai en 1988. Il a été cassé par J. Patarin en 1995. J. Patarin a lui-même proposé une généralisation de C* appelée HFE en 1996. C'est cet algorithme HFE que l'invention se propose d'améliorer. L'algorithme HFE, bien connu de l'homme du métier, peut être résumé de 25 la manière suivante. On note par M(D) le nombre d'opérations nécessaires pour multiplier deux polynômes univariés de degrés strictement inférieurs à D sur un corps 1:1 donné. Il est possible de calculer !es racines d'un polynôme 1-7 de degré strictement inférieur à D sur ce corps E_ en 0(_11(1); (D)) opérations dans 30 le corps L. Ceci est expliqué notamment dans Joachim von zur Gathen, Jürgen Gerhard, Modern Computer Algebra (3. ed.), Cambridge University 3038474 4 Press 2013, ISBN 978-1-107-03903-2, pages I-XIII, 1-795 dont le contenu est incorporé par référence. Dans la suite, on note C _11 D log(W. Soit N avec q une puissance d'un nombre premier, 5 rri n et un morphisme entre le corps et l'espace vectoriel (F est une base de F qn sur , on a: (v, Soit F . On construit une application dans l'extension 10 de corps n F F q V H> 17(V) On choisit un polynôme F avec la structure suivante: x + c F= (1) 0 (fi (Vi ''"/ Vn )' -"' fn (Vi ''"' Vn )) avec -- fn)E (Fq [ - --, Xn 1)n où les fi sont construits de telle façon que: F - - - 5 Considérons par exemple une instance de HFE avec q2, n-iui1 et D6 On considère l'extension de corps 1F2/ 4 +a+1 vecteur (1 3 est une base de l'espace vectoriel .On choisit un polynôme univarié de degré au plus D 6 qui respecte la construction HFE selon l'équation (1), par exemple: 10 +(u3+ a + 1)XI + a X3(a+a +1)X2 On peut construire la représentation de L sur , en calculant: 2` X2X.42 ;` - 4 X4 2 + X X- + X, X + X- 3 X2X + X-, + X + 1 4 x`2x 4-x,x4 a7 + 1 1 - 1)a5 + (x 2)(14 + 4 -- 5 5 3 ) +(xi x2)a +(xi + x4 4 15 lI suffit alors de réduire les puissances de a par (14 + a + 1, puis de 3038474 remplacer X i par xi pour tou n. On obtient: + X + X ., X +X3 +X1 I 3 1 +x,x3 x2x4+1)a- +(x x +x,x3+ x1x4 +x, +x,x3+ x, +x3x4 x3+ x4+ 1)a +x,x3+x, +x,x3+x,x4+x3x4) Ce qui correspond aux polynômes: f1 (X1 1X2 ,X3 1X4) 5 f2(x1 ).x-3.x1) -2 1.)( X2X4 X3X4 f.3(X: .X-) .X .X1 X1X2 X1X X 1X4 X2X:; (x, xi) xi, xl 1 -X1X2 -+X-)X3+- Une paire de clé HFE peut alors être calculée de la façon suivante. On définit la clé privée d'une paire de clé HFE comme comprenant un 10 polynôme F de type HFE ainsi que deux transformations affines inversibies. notées S et T. On peut représenter chacune des transformations S et T sous forme d'une matrice n n et d'un vecteur de taille il. Ces trois éléments F, S et T sont évidemment conservés de manière confidentielle (ils ne sont pas partagés avec les tiers). Dans la suite, on considère pour simplifier que les 15 transformations S et T sont linéaires (!es vecteurs associés sont nuls, et les transformations S et T sont alors représentées simplement par des matrices). La clé publique correspondante de la paire de clé HFE considérée peut être déterminée de la façon suivante. On commence par calculer les polynômes 20 polynôme F de la façon indiquée dans l'exemple ci-dessus. On calcule alors: correspondant au 3038474 La clé publique HFE est alors (g1.. ..,g13' avec in n Un chiffrement et un déchiffrement HFE peuvent s'opérer de la manière suivante, avec 111-1L fl 5 Pour chiffrer un message clair , on calcule le message chiffré: - " g n Le possesseur de la clé secrète peut déchiffrer le message chiffré en calculant une solution Z u système: 10 - 0, avec cr 11 - - - Dans le cadre du HFE, ceci est équivalent à trouver les tels que: F(q) 1( )) (2) On détermine ainsi le message clair M S-1, pour un z solution de l'équation (2). 15 Une signature HFE peut s'opérer de la manière suivante (avec m S n Une signature HFE peut consister à appliquer le procédé de déchiffrement HFE décrit précédemment sur un message auquel on ajoute des valeurs tirées aléatoirement. Soit Flash une fonction de hachage cryptographique. Pour 20 signer un message M E r on calcule a (i M), où a c It1 est l'empreinte (également appelée hash ou condensat) d'un message M à signer. On tire aléatoirement valeurs r dans n ni . On détermine alors 4 E 11L. tel que: 3038474 8 F(ço Ço9 - - - (3) Le vecteur Sig Z S E Fqn est une signature du message M. Pour un n-uplet donné, il est possible que l'équation (3) n ait aucune solution. Si c'est le cas, il suffit de répéter l'opération 5 avec d'autres valeurs pour l'Il Pour vérifier que la signature sig est valide pour \I, il suffit de comparer Rash( M) avec le résultat de l'application de la clé publique à la signature sicr. Autrement dit, on teste s `-;10_ Si cette égalité n'est pas vérifiée, alors sig n'est pas une signature valide du message 10 Dans son article Hidden Fields Equations (HFE) and lsomorphisms of Polynomials (IP): two new families of asymmetric algorithms, Advances in Corptology EUROCRYPT96. volume 1070 des Lecture Notes ln Computer Science, pages 33-48, Springer, 1996, J. Patarin, propose par exemple 15 d'utiliser q=2, n=80 et D=96 pour avoir un chiffré (ou une signature) de 80 bits. On recense principalement deux attaques contre HFE. L attaque directe en recouvrement de message contre HFE (proposée dans: Algebraic cryptanalysis of HFE using GrObner bases, Jean-Charles Faugère, Reasearch report RR-4738, INRIA, 2003) a une complexité 20 ( - h I t avec dreg D).Par exemple, dreg est égal à 4 si D est compris entre 17 et 128, dreg est égal à 5 si D est compris entre 129 et 512, et dreg est égal à 6 si D est compris entre 513 et 1280. Les valeurs de dreg en fonction de D sont données dans article précité de Jean-Charles Faugère. 3038474 9 La complexité de l'attaque en recouvrement de clé proposée dans Luk Bettale, Jean-Charles Faugère, and Ludovic Perret. Cryptanalysis of multivariate and odd-characteristic HFE variants. Public Key Cryptography - PKC 2011, volume 6571 des Lecture Notes in Computer Science, pages 441- 5 458. Springer, 2011, est 0(ii Une clé privée utilisée dans l'algorithme HFE conventionnel comprend un polynôme de type HFE (univarié), qui fait la sécurité et l'efficacité du chiffrement. Le degré de ce polynôme est fixé selon un compromis entre la sécurité et l'efficacité, qui sont deux contraintes opposées. Une difficulté qui se 10 pose dans 'algorithme HFE conventionnel est trouver un degré assurant à la fois sécurité et efficacité à la mise en oeuvre concrète de l'algorithme. L'invention vise à améliorer la situation. 15 Un aspect de l'invention concerne un procédé de mise en oeuvre accélérée, par un circuit électronique, d'un algorithme cryptographique HFE exploitant une clé privée HFE basée sur un polynôme de type HFE, sur un morphisme, et sur une première et une deuxième transformations affines, le procédé comprenant: 20 /E1/ une utilisation, par le circuit électronique, d'au moins un polynôme supplémentaire compris dans la c é privée HFE, et 1E21 une utilisation, par le circuit électronique, d'une premIère et d'une deuxième fonctions de mappage comprises dans la clé privée HFE, et associant chacune, à un paramètre d'entrée donné, autant de paramètres de 25 sortie qu'il y a de polynômes supplémentaires dans la clé privée HFE, l'au moins un polynôme supplémentaire et !es fonctions de mappage étant tels que, pour un paramètre donné, et pour toute racine du polynôme de type HFE moins ledit paramètre donné, le résultat de la première fonction de mappage appliquée à ladite racine est une racine de chaque polynôme 30 supplémentaire moins un paramètre de sortie, correspondant audit chaque 3038474 10 polynôme supplémentaire, de la deuxième fonction de mappage appliquée audit paramètre donné. Le procédé est avantageux notamment en ce qu'il permet une mise en oeuvre plus rapide de l'algorithme HFE que la mise en couvre conventionnelle 5 de cet algorithme. Ceci est particuirèrement avantageux lorsqu'il est envisagé d'utiliser l'algorithme HFE sur des dispositifs mobiles tels que des smartphones (parfois appelés "téléphones intelligents" en français) dont la puissance de calcul est limitée par rapport à celle d'un ordinateur de bureau conventionnel. Le procédé est a fortiori avantageux lorsque l'algorithme est mis en oeuvre sur 10 un circuit électronique tel qu'une carte à puce, dont la puissance de calcul est très limitée. Le procédé permet une représentation transformée du polynôme de type HFE utilisé dans l'algorithme HFE conventionnel, grâce au(x) polynôme(s) supplémentaire(s) et à la fonction de mappage. Un attaquant éventuel n'a pas d'accès à la structure du polynôme de type HFE (qui 15 nécessite la connaissance de la clé privée), il peut savoir tout au plus qu'il est confronté à un polynôme de haut degré. Mais grâce aux polynômes supplémentaires, le polynôme de type HFE peut être représenté de façon à ce que les opérations à clé privée (déchiffrement ou signature notamment) soient néanmoins exécutées plus rapidement, sans abaisser la sécurité. 20 Un autre aspect de l'invention concerne un circuit électronique agencé pour mettre en oeuvre de façon accélérée un algorithme cryptographique HFE exploitant une clé privée HFE basée sur un polynôme de type HFE, sur un morphisme, et sur une première et une deuxième transformations affines, le 25 circuit électronique comprenant: un sous circuit électronique d'utilisation d'au moins un polynôme supplémentaire compris dans la oie privée HFE, et un sous circuit électronique d'utilisation d'une première et d'une deuxième fonctions de mappage comprises dans la clé privée HFE, et 30 associant chacune, à un paramètre d'entrée donné, autant de paramètres de sortie qu'il y a de polynômes supplémentaires dans la clé privée HFE, 3038474 11 l'au moins un polynôme supplémentaire et !es fonctions de mappage étant tels que, pour un paramètre donné, et pour toute racine du polynôme de type HFE moins ledit paramètre donné, le résultat de la première fonction de mappage appliquée à ladite racine est une racine de chaque polynôme 5 supplémentaire moins un paramètre de sortie, correspondant audit chaque polynôme supplémentaire, de la deuxième fonction de mappage appliquée audit paramètre donné. Un tel circurt électronique est avantageux notamment en ce qu'il permet une mise en oeuvre plus rapide de l'algorithme HFE que la mise en oeuvre 10 conventionnelle de cet algorithme. D'autres aspects, buts et avantages de l'invention apparaîtront de manière non limitative à la lecture de la description de quelques uns de ses modes de réalisation. 15 L'invention sera également mieux comprise à laide des dessins, sur lesquels - la figure 1 illustre un circuit électronique selon un mode de réalisation de l'invention ; 20 la figure 2 illustre l'architecture d'un circuit électronique selon un mode de réalisation de l'invention ; la figure 3 illustre la mémoire d'un circuit électronique selon un mode de réalisation de l'invention; la figure 4 illustre le fonctionnement d'une fonction de mappage 25 selon un mode de réalisation de l'invention. La figure 1 montre une circuit électronique selon un mode de réalisation de l'invention, prenant la forme d'une carte à puce SC. Cette carte à puce comprend une puce électronique ICC. La figure 2 montre l'architecture d'une puce électronique ICC de la carte 30 à puce SC selon la figure 1. La puce ICC comprend notamment un processeur MP, une mémoire MEM, et un dispositif d'entrées sorties IO. Ces différents 3038474 12 composants sont représentés schématiquement sous la forme de composants discrets fixés sur un ROB (non représenté), et reliés entre eux par un bus non représenté. Mais ces différents composants peuvent être (et sont en pratique, dans le cas des cartes à puce) intégrés sur une même puce découpée à partir 5 d'un même wafer et fixée dans un module de carte à puce. La figure 3 montre ie contenu d'une mémoire non volatile MEM d'un circuit électronique selon un mode de réalisation possible de l'invention. On trouve, dans une première partie de la mémoire, une zone de stockage d'un morphisme y. On trouve, dans une autre partie de la mémoire, une clé privée 10 KpR selon un mode de réalisation de invention, comprenant notamment un polynôme FsLc, des transformations affines S et T, des polynômes supplémentaires r - et deux fonctions de mappage MAP et MAP_I. La figure 4 montre une première fonction de mappage MAP, qui à un 15 paramètre d'entrée A associe un paramètre de sortie et une deuxième fonction de mappage MAP_I, qui à un paramètre d'entrée C' associe un paramètre de sortie C'1 Un premier mode de réalisation se rapporte à un procédé de mise en 20 oeuvre accélérée, par un circuit électronique SC, d'un algorithme cryptographique HFE. Le circuit électronique est par exemple une carte à puce SC, mais il peut également s'agir de tout autre circuit électronique approprié, par exemple un circuit électronique dédié, un FPGA, un ASIC, un microcontrôleur, un DSP, ou encore un circuit comprenant un processeur et 25 une mémoire, la mémoire stockant un programme d'ordinateur approprié. L'algorithme cryptographique HFE selon !e premier mode de réalisation est modifié de manière à exploiter une cié privée HFE basée non seulement sur un polynôme FL_.c de type HFE, sur un morphisme t7 , et sur une première et une deuxième transformations affines S et T, mais en plus sur d'autres 30 éléments. L'exploitation de la clé peut consister à l'utiliser afin d'effectuer des opérations de déchiffrement, de signature, ou encore d'authentification. 3038474 13 L'exploitation peut consister également à manipuler la dé privée par exemple en effectuant un enregistrement de sauvegarde de cette clé privée au sein d'un serveur sécurisé, au cas où elle serait perdue) cette exploitation pouvant comprendre la génération préalable de ladite clé privée. 5 Selon une mise en oeuvre possible, le polynôme FsEc de type HFE correspond à un polynôme de type HFE conventionnel, noté F dans la description supra. Par l'expression "clé privée basée sur" on entend que la clé privée peut être construite à partir des éléments énumérés mais qu'elle ne les comprend 10 pas nécessairement. Par exemple, il n'est pas nécessaire de stocker une représentation du morphisme au sein de chaque clé privée, le morphisme pouvant être propre à l'algorithme HFE considéré et étant alors commun à toutes les clés privées générées pour cet algorithme. De même, la clé privée ne contient pas nécessairement le polynôme FsLc de type HFE. En effet, est 15 possible que la clé privée contienne d'autres éléments permettant de recalculer facilement le polynôme FsLc. Selon une mise en oeuvre possible, la clé privée contient les deux transformations affines S et T. Selon une autre mise en oeuvre, elle contient de surcroît le polynôme Fsi_c. Le procédé selon le premier mode de réalisation comprend une 20 utilisation, par le circuit électronique, d'au moins un polynôme(s) 3uu''" fUU supplémentaire(s) compris dans la clé privée HFE. Selon une rnse en oeuvre possible, la clé privée HFE comprend un seui polynôme supplémentaire. Selon une autre mise en oeuvre, la clé privée HFE comprend plusieurs polynômes f1E3°°st, f23uu'', ftBc'`'s' supplémentaires. L'utilisation doit 25 être entendue au sens large. Selon une mise en oeuvre possible, l'utilisation d'au moins un polynôme supplémentaire comprend la mise en oeuvre d'une opération cryptographique (par exemple une signature électronique, une authentification ou un déchiffrement) avec la clé privée comprenant l'au moins un polynôme supplémentaire, ce qui implique un calcul à l'aide du au moins un 30 polynôme supplémentaire. Selon une autre mise en oeuvre possible, l'utilisation comprend le stockage, après génération d'une clé privée selon un 3038474 14 mode de réalisation de l'invention, du au moins un polynôme supplémentaire dans une mémoire d'enregistrement de clé privée. Selon une autre mise en oeuvre possible, l'utilisation comprend la transmission, après génération d'une clé privée selon un mode de réalisation de l'invention, du au moins un 5 polynôme supplémentaire à un autre circuit électronique. Le procédé selon le premier mode de réalisation comprend une utilisation, par le circuit électronique, d'une première et d'une deuxième fonctions de mappage (MAP et MAP_I respectivement) comprises dans la clé privée HFE, et associant chacune, à un paramètre d'entrée (noté 10 respectivement A et C') donné, autant de paramètres de sortie respectivement A1,A2,...,At et C'1. C'2, --- C't) qu'il y a de polynômes fisuust, f23008', --- ftE3°°s' supplémentaires dans la clé privée HFE. Comme au paragraphe précédent, l'utilisation doit être entendue au sens large. Selon une mise en oeuvre possible, l'utilisation des fonctions de mappage consiste à 15 effectuer une opération cryptographique (par exemple une signature électronique, une authentification ou un déchiffrement) avec la clé privée comprenant lesdites fonctions de mappage, ce qui implique un calcul à l'aide desdites fonctions de mappage. Selon une autre mise en oeuvre possible, l'utilisation comprend le stockage, après génération d'une clé privée selon un 20 mode de réalisation de l'invention, desdites fonctions de mappage dans une mémoire d'enregistrement de clé privée. Selon une autre mise en oeuvre possible, utilisation comprend la transmission, après génération d'une clé privée selon un mode de réalisation de l'invention, desdites fonctions de mappage à un autre circuit électronique. 25 La première fonction de mappage MAP est une fonction qui transporte les racines entre le polynôme de type HFE et le(s) polynôme(s) supplémentaire(s). La fonction dite fonction inverse de la première fonction de mappage (notée MAP-1) désigne la fonction qui à un élément de lensemble d'arrivée de la première fonction de mappage MAP associe la préimage de cet 30 élément dans l'ensemble de départ de la fonction de mappage MAP. Selon le premier mode de réalisation, l'au moins un polynôme(s) ftBoost supplémentaire(s) et la première fonction de mappage MAP sont tels que, 3038474 15 pour un paramètre C' donné, et pour toute racine A du polynôme Fst_c de type HFE moins ledit paramètre C' donné, le résultat (A1,A2, ,A.) de la première fonction de mappage MAP appliquée à ladite racine A est une racine de chaque polynôme 1`,"s' supplémentaire moins un paramètre de sortie C'1, 5 correspondant audit chaque polynôme f,duas' supplémentaire (au sens par exemple où le paramètre C', et ce polynôme f3rjus' ont ie même indice, noté i en l'espèce), de la deuxième fonction de mappage MAP_I appliquée audit paramètre C' donné. La deuxième fonction de mappage MAP_I peut être une fonction identité (si son ensemble de départ et son ensemble d'arrivée sont les 10 mêmes). De façon plus générale, la deuxième fonction de mappage MAP_I est adaptée pour que la première fonction MAP transporte les racines comme indiqué ci-dessus. Un résultat (X1, X2, ... X1)=MAP(X) (respectivement (X1, X2, X1)=MAP I(X)) d'une fonction de mappage se décompose en t paramètres de sortie X1, X2, ... X qui (réciproquement) forment ensemble ledit résultat (X1, 15 X2, Xi). Ainsi, si l'on note (C'i, C'2, C,) MAP_I(C') et (Al, A2, ... At)=MAP(A), et si FsLc(A)=C1, aiors fi3uust( pour tout i entre 1 et t, t désignant le nombre de polynômes supplémentaires C'st. Ce procédé de mise en oeuvre accélérée d'un algorithme 20 cryptographique HFE peut être Intégré de manière conventionnelle dans des architectures de PKI infrastructures à clés publiques Par exemple, il est possible de réaliser une authentification et un chiffrement TLS (Transport Layer Security, le remplaçant du SSL, acronyme de Secure Socket Layer) grâce à l'algorithme HFE sebn l'invention. Il convient 25 cependant de changer la spécification TLS afin d'y autoriser l'emploi de l'algorithme HFE selon l'invention, ou d'utiliser une version propriétaire de TLS permettant un tel support. De façon analogue, il est possible d'intégrer ce procédé de mise en oeuvre accélérée d'un algorithme cryptographique HFE dans la suite de 30 protocoles IPSEC spécifiée par IllETF. Il convient par exemple d'ajouter aux protocoles pertinents de l'IPSEC (notamment les protocoles 1SAKMP et IKE) le support d'un procédé HFE selon l'invention (en plus des algorithmes 3038474 16 traditionnels tels que RSA ou Diffie-Hellman). Selon un deuxième mode de réalisation, un procédé selon le premier mode de réalisation comprend une génération, par le circuit électronique, de 5 ladite clé privée HFE. Ladite génération comprend une génération, par le circuit électronique SC, dudit au moins un polynôme(s) S' f CJUS ftBoost supplémentaire(s). Ladite génération comprend une génération, par le circuit électronique SC, desdites fonctions de mappage MAP et MAP_I. 10 Selon une mise en oeuvre possible, les générations des deux paragraphes précédents sont des étapes préalables. Autrement dit, l'utilisation de l'au moins un polynôme(s) f1B00, f2suus,fcoussupplémentaire(s) et celle des fonctions de mappage sont postérieurs à leur génération par le circuit électronique, et peuvent comprendre le stockage de !au moins un polynôme(s) 15 f1:3', f23"s',fUU supplémentaire(s) et celui des fonctions de mappage dans une mémoire d'enregistrement de clés privées à l'intérieur du circuit électronique. Selon d'autres modes de réalisation, la génération des clés privées n'est pas réalisée par le circuit électronique mais par exemple par un serveur (qui génère alors le au moins un polynôme supplémentaire et les 20 fonctions de mappage pour chaque clé privée générée). Ce serveur transmet chaque clé privée qu'il a générée au circuit électronique pertinent, de manière sécurisée. Selon un mode de réalisation, les clés privées ayant vocation à être utilisées pour des opérations de signature ou d'authentification sont générées par le circuit électronique lui-même, qui peut interdire leur extraction par des 25 mécanismes de sécurité (il n'y a donc pas d'archivage possible, mais en contrepartie une garantie accrue qu'aucun tiers mal intentionné ne peut accéder à ces dés privées). Le défaut d'archivage ne pose pas de problème significatif. En effet, alors que la perte d'une clé privée est concevable (par exemple par perte, destruction ou vol du circuit électronique stockant une telle 30 clé privée), !a perte d'une cié publique est beaucoup moins courante, car la clé publique est souvent partagée largement sous forme de certificat) en plus 3038474 17 d'être enregistrée sur un serveur sécurisé (typiquement un serveur d'autorité de certification). La perte d'une telle clé privée empêche donc d'effectuer de nouvelles signatures ou authentifications avec la clé perdue (mais il est très simple de révoquer l'ancienne clé et d'en générer une nouvelle pour assurer à 5 l'avenir les mêmes fonctions de signature et/ou d'authentification). Mais une telle perte n'empêche pas de vérifier les signatures ou authentifications passées (ce qui reste possible grâce à la clé publique, qui est généralement conservée). Selon un mode de réalisation possible, les clés privées ayant vocation à être utilisées pour des opérations de déchiffrement sont générées 10 par un serveur sécurisé, qui en conserve une copie de sauvegarde de manière sécurisée, et les transmet aux circuits électroniques pertinents a savoir les circuits électroniques qui ont vocation à effectuer des opération de déchiffrement avec ces clés Ceci permet de pouvoir déchiffrer des messages chiffrés dans le passé alors que la clé privée permettant ce déchiffrement a 15 depuis été perdue (par exemple par perte, destruction ou vol, comme envisagé précédemment pour d'autres types de clés Selon un troisième mode de réalisation, un procédé selon le premier ou le second mode de réalisation comprend une opération de déchiffrement. 20 Cette opération de déchiffrement comprend une réception (à une étape D1), par le circuit électronique SC, d'un message sous forme chiffrée c (qui peut être tronqué) et d'un hash h calculé sur le message sous forme non chiffrée. Le hash h est susceptible de présenter plusieurs intérêts. En particulier, le polynôme HFE possède éventuellement plusieurs racines. La 25 fonction de déchiffrement peut donc conduire à plusieurs messages déchiffrés possibles parmi lesquels il convient alors de déterminer lequel est le bon. Le hash h fournit dans un tel contexte une redondance compensant l'ambiguïté du déchiffrement (qui peut conduire à plusieurs messages clairs possibles alors qu'un seul est pertinent). Le hash h permet également d'introduire une 30 redondance pouvant compenser le fait que le message sous forme chiffrée est tronqué. L'opération de déchiffrement comprend une application, par le circuit 3038474 18 électronique SC, de l'inverse de la deuxième transformation affine T au message sous forme chiffrée c afin d'obtenir un message chiffré intermédiaire c'. On a ainsi c'=c*T1, T1 désignant la transformation inverse de la transformation affine T. 5 L'opération de déchiffrement comprend une application, par le circuit électronique SC, de l'inverse du morphisme ço au message chiffré intermédiaire c'. L'opération de déchiffrement comprend une obtention d'au moins un (par exemple de t) paramètre(s) de sortie C'1, C'2, par application, par le 10 circuit électronique SC, de la deuxième fonction de mappage MAP_I au résultat de ladite application de l'inverse du morphisme ço. L'opération de déchiffrement comprend une résolution, par le circuit électronique SC, d'un système d'équatron(s) tel que chaque polynôme f,Buus' supplémentaire soit égal au paramètre de sortie C', respectif obtenu à l'étape 15 précédente. L'opération de déchiffrement comprend une application, par le circuit électronique SC, de l'inverse de la première fonction de mappage MAP à une solution du système d'équation(s). L'opération de déchiffrement comprend une application, par le circuit 20 électronique SC, du morphisme au(x) résultat(s) de l'inverse de la fonction de mappage MAP obtenu à l'étape précédente (la préimage peut contenir plusieurs résultats, qui peuvent alors être traités un par un, indépendamment les uns des autres, par application du morphisme à chacun d'eux). L'opération de déchiffrement comprend une obtention d'une estimation 25 du message sous forme non chiffrée, par application, par le circuit électronique SC, de l'inverse de la première transformation affine S au résultat (ou à chacun des résultats, s'il y en a plusieurs) du morphisme obtenu à l'étape précédente. L'opération de déchiffrement comprend un calcu!, par le circuit 30 électronique SC, d'un hash de l'estimation du message sous forme non 3038474 19 chiffrée. Le hash est issu d'une fonction de hachage cryptographique publique (par exemple SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256, SHA3-224, SHA3-256, SHA3-384; SHA3-512. SHAKE128, SHAKE256, etc.) qui a été utilisée lors de l'opération de chiffrement ayant 5 conduit au message chiffré que le circuit électronique tente de déchiffrer. L'opération de déchiffrement comprend, si le hash de l'estimation du message sous forme non chiffrée est différent du hash h reçu à l'étape D1, l'obtention d'une autre estimation du message sous forme non chiffrée selon les étapes précédentes, Jusqu'à ce que les deux hash soient égaux. 10 Selon un quatrième mode de réalisation, un procédé selon l'un des premier au troisième modes de réalisation comprend une opération de signature. Cette opération de signature comprend un calcul, par le circuit 15 électronique SC. d'un hash d'un message à signer. L'opération de signature comprend une génération, par le circuit électronique, d'un nombre aléatoire de taille égale à la taille d'un élément de l'ensemble d'arrivée du morphisme yo moins la taille du hash du message à signer. Par taille, on entend taille au sens informatique du terme. Par exemple, 20 si un élément de l'ensemble d'arrivée du morphisme (1,7 est codé sur 256 bits, et si le hash d'un message est codé sur 224 bits, alors le nombre aléatoire généré est un nombre aléatoire de 32 bits. L'opération de signature comprend une application, par le circuit électronique, de l'inverse de la deuxième transformation affine T à une 25 concaténation du nombre aléatoire et du hash du message à signer. L'opération de signature comprend une application, par le circuit électronique, de l'inverse du morphisme yo au résultat de l'application de l'inverse de la deuxième transformation affine T. L'opération de signature comprend une obtention d'au moins un 30 paramètre de sortie par exemple une obtention de t paramètres de sortie 3038474 20 C'2, C'1), par application, par le circuit électronique, de la deuxième fonction de mappage MAPI au résultat de ladite application de l'inverse du morphisme. L'opération de signature comprend une résolution, par le circuit 5 électronique, d'un système d'équation(s) tel que chaque polynôme f,3"s' supplémentaire soit égal au paramètre de sortie C'i respectif obtenu à l'étape précédente. L'opération de signature comprend, si le système d'équation(s) n'admet pas de solution, une répétition des étapes précédentes avec un autre nombre 10 aléatoire. Selon une mise en oeuvre possible, l'autre nombre aléatoire est un nombre aléatoire généré à nouveau par le circuit électronique. Selon une autre mise en oeuvre, l'autre nombre aléatoire résulte de l'incrémentation, par le circuit électronique, du précédent nombre aléatoire. L'opération de signature comprend une application, par le circuit 15 électronique, de l'inverse de la première fonction de mappage MAP à une solution du système d'équation(s). Si la préimage renvoyée par l'inverse de la première fonction de mappage comprend plusieurs résultats, le circuit électronique recherche parmi eux un résultat qui convient (le résultat doit aboutir à une racine de SEC q) )- 20 L'opération de signature comprend une application, par le circuit électronique du morphisme O au résultat de l'inverse de la première fonction de mappage MAP obtenu à l'étape précédente. L'opération de signature comprend une obtention d'une signature du message à signer, par application, par le circuit électronique, de l'inverse de la 25 première transformation affine S au résultat du morphisme (,0 obtenu à l'étape précédente. Selon un cinquième mode de réalisation, la clé privée HFE d'un procédé selon l'une des premier au quatrième modes de réalisation précédents 30 comprend un unique polynôme3`"''' supplémentaire, la première fonction de 3038474 21 mappage MAP est un monôme, e le polynôme de type HFE Fst_c est égal à la composition du polynôme fB0 supplémentaire avec la première fonction de mappage MAP. 5 Selon un sixième mode de réalisation, un programme d'ordinateur comprend une suite d'instructions mettant en oeuvre les étapes du procédé selon l'un des premier au cinquième modes de réalisation lorsqu'elles sont exécutées par un processeur. Ce programme est par exemple rédigé en langage assembleur, ou encore en langage C. De tels langages, de bas 10 niveau, sont avantageux dans la mesure où ils permettent des optimisations fines et autorisent la mise en place de contremesures de façon plus efficace. Des langages de plus haut niveau sont possibles mais dégradent généralement !es performances et ne permettent pas nécessairement de mettre en place des contremesures efficaces. 15 Selon un septième mode de réalisation» un support de stockage non transitoire lisible par ordinateur comprend un programme d'ordinateur selon le sixième mode de réalisation. Ce support de stockage est par exemple une mémoire permettant un stockage permanent. La mémoire peut être 20 réinscriptible (Flash, EEPROM, RAM protégée par batterie, voire support magnétique ou optique) ou non réinscriptible (ROM, etc.). Un tel support de stockage peut être intégré à une carte à puce ou à un ordinateur quelconque, en particulier un smartphone. 25 Selon un huitième mode de réalisation, un circuit électronique (par exemple une carte à puce SC) est agencé pour mettre en oeuvre de façon accélérée un algorithme cryptographique HFE exploitant une clé privée HFE basée sur un polynôme FsLc de type HFE, sur un morphisme, et sur une première S et une deuxième T transformations affines. 30 Le circuit électronique comprend un sous circuit électronique d'utilisation d'au moins un polynôme(s) fiBuusl, f2Boost, coost supplémentaire(s) compris 3038474 22 dans la c é privée HFE. Selon une mise en oeuvre possible, Le sous circuit électronique d'utilisation d'au moins un polynôme est par exemple un circuit électronique dédié, un FPGA, un ASIC, un microcontrôleur, un DSP, ou encore un circuit comprenant un processeur et une mémoire, la mémoire 5 stockant un programme d'ordinateur approprié. Selon une mise en oeuvre possible, le sous circuit électronique d'utilisation d au moins un polynôme partage un processeur avec le circuit électronique. Le circuit électronique comprend un sous circuit électronique d'utilisation des fonctions de mappage MAP et MAP_I comprises dans la clé privée HFE, 10 et associant, à un paramètre d'entrée donné, autant de paramètre(s) de sortie qu'il y a de polynôme(s) f1.300s'. f'Buost, ftBci's supplémentaire(s) dans la clé privée HFE. Selon une mise en oeuvre possible, Le sous circuit électronique d'utilisation des fonctions de mappage est par exemple un circuit électronique dédié; un FPGA, un ASIC, un microcontrôleur, un DSP, ou encore un circuit 15 comprenant un processeur et une mémoire, la mémoire stockant un programme d'ordinateur approprié. Selon une mise en oeuvre possible, le sous circuit électronique d'utilisation des fonctions de mappage partage un processeur avec le circuit électronique. Par exemple, le circuit électronique comprend un processeur, une 20 mémoire contenant un programme d'ordinateur agencé pour mettre en oeuvre l'utilisation de l'au moins un polynôme(s) .f100`' Bous: e.3u0st supplémentaire(s), et une mémoire contenant un programme d'ordinateur agencé pour mettre en oeuvre l'utilisation des fonctions de mappage. Le sous circuit électronique d'utilisation d'au moins un polynôme(s) 00 - 25 ft3't supplémentaire(s) peut comprendre le processeur et la mémoire contenant le programme d'ordinateur agencé pour mettre en oeuvre l'utilisation de l'au moins un polynôme(s) .f1300s: 2±,us-1,f.dUL)supplémentaire(s), et le sous circuit électronique d'utilisation des fonctions de mappage peut comprendre le même processeur (partagé) et la mémoire contenant le 30 programme d'ordinateur agencé pour mettre en oeuvre l'utilisation des fonctions de mappage. Selon une autre mise en oeuvre possible le sous circuit électronique d'utilisation d'au moins un polynôme(s) f1BL"' 80( 3038474 23 Buus- supplémentaire(s) et te sous circuit électronique d'utilisation des fonctions de mappage sont deux sous circuits entièrement distincts, pouvant néanmoins coopérer l'un avec l'autre. L'au moins un polynôme supplémentaire et les fonctions de mappage 5 sont tels que, pour un paramètre C' donné, et pour toute racine A du polynôme FsLc de type HFE moins ledit paramètre C' donné, le résultat (Aii....,At) de la première fonction de mappage MAP appliquée à ladite racine A est une racine de chaque polynôme f,300s' supplémentaire moins un paramètre de sortie Ci, correspondant audit chaque polynôme r3aiost supplémentaire, de la deuxième 10 fonction de mappage MAP appliquée audit paramètre C' donné. Selon un neuvième mode de réalisation, un circuit électronique selon le huitième mode de réalisation comprend, afin de mettre en oeuvre une opération de déchiffrement, un sous circuit électronique de réception d'un 15 message sous forme chiffrée c et d'un hash h calculé sur le message sous forme non chiffrée. Le circuit électronique comprend un sous circuit électronique d'application de l'inverse de la deuxième transformation affine T au message sous forme chiffrée c afin d'obtenir un message chiffré intermédiaire c'. 20 Le circuit électronique comprend un sous circuit électronique d'application de l'inverse du morphisme au message chiffré intermédiaire c'. Le circuit électronique comprend un sous circuit électronique d'obtention d'au moins un paramètre de sortie C'1, CL, C't, par application de la deuxième fonction de mappage MAP_I au résultat de ladite application de 25 l'inverse du morphisme. Le circuit électronique comprend un sous circuit électronique de résolution d'un système d'équation(s) tel que chaque polynôme fLL supplémentaire soit égal au paramètre de sortie C'; respectif. Le circuit électronique comprend un sous circuit électronique 30 d'application de l'inverse de la première fonction de mappage MAP à une 3038474 24 solution du système d'équation(s). Le circuit électronique comprend un sous circuit électronique d'application du morphisme au résultat de l'inverse de la première fonction de mappage MAP. 5 Le circuit électronique comprend un sous circuit électronique d'obtention d'une estimation du message sous forme non chiffrée, par application de l'inverse de la première transformation affine S au résultat de l'application du morphisme. Le circuit électronique comprend un sous circuit électronique de calcul 10 d'un hash de l'estimation du message sous forme non chiffrée. Le circuit électronique comprend un sous circuit électronique de vérification agencé pour vérifier si le hash de l'estimation du message sous forme non chiffrée est différent du hash h reçu, et dans l'affirmative pour déclencher l'obtention d'une autre estimation du message sous forme non 15 chiffrée, jusqu'à ce que les deux hash soient égaux. Selon un dixième mode de réalisation, la clé privée HFE d'un circuit électronique selon le huitième ou neuvième mode de réalisation comprend un unique polynôme f.300st supplémentaire, la première fonction de mappage MAP 20 est un monôme, et le polynôme FsLc, de type HFE est égal à la composition du polynôme fa's' supplémentaire avec la première fonction de mappage MAP. D'autres modes de réalisation sont décrits plus précisément ci-dessous. Une manière de générer une paire de clés publique et privée selon un 25 mode de réalisation possible est la suivante. Soit (q, n, m, t,D) f I avec une puissance d'un nombre premier et m n. Un circuit électronique définit Aff, (iFq GL X FL' comme l'ensemble des transformations affines inversibles de La clé secrète dans HFEBoost comprend: 3038474 1. un polynôme univarié SEC précitée) de degré Dsi e type HFE (équation (1) y ."/f e exemple des si l'on prend comme corps K le corps par , avec K un polynômes 2. des polynômes corps -Boosi quelconque 13CnItil 5 3. une première fonction de mappage a fonction MAP transporte toute racine du polynôme L(. en une solution t . Une deuxième dans L-\\ du système 11 10 fonction de mappag AP 4. deux transformations affines (T, ))) E Aff, ffn (11-1q ) . On adopte ici une notation plus précise (différente des notations utilisées précédemment) afin de faWe apparaître expressément dans la notation la partie affine (s et t, 15 respectivement) des transformations, les notations S et T désignant des transformations linéaires. En pratique, utiliser une transformation linéaire en lieu et place d'une transformation affine (en posant 0 et t 0) ne présente pas d'inconvénient (cela ne diminue pas la sécurité de manière notable, et cela simplifie légèrement les calculs). 20 Soit Ç 3038474 26 Les polynômes Y - - - 1,,---1 sont tels que: ost rBoosL - si A est une racine de ,;1.c 1 (C 1), alors MAP(A) est une solution de fil''''sl(MAP(A)) C'1 ,... 8""st(MAP(A)) C't , avec (Cil C ) MAP I çc-I 5 - il est possible de calculer les solutions de ,Boost (mAp (A)) r, ''""'"I\IAP(A)) = C' en un temps inférieur à 0 C Un circuit électronique n n tels que: construit les polynômes XI 10 S " ' n et eee Le circuit électronique construit également la clé publique en masquant les composantes ft ,--- n de 15 Plus précisément, pour construire une clé publique, le circuit électronique calcule, selon un mode de réalisation: (xi ^"°1 n ),"-) gri (XI 1-1 )) Xn )S S La clé publique est alors l'ensemble des polynômes quadratiques: 20 gl /*---- '---,in ) . Selon un mode de réalisation, le circuit électronique utilise les fonctions avec 1 ' " 3038474 27 de mappage 1\1 et \1A1 I et les polynômes f-BOOSt YI, , - - - , pour les opérations impliquant la clé 11, - - - , privée, telles que le déchiffrement ou la signature. Le circuit électronique peut mettre en oeuvre le chiffrement et le 5 déchiffrement de la façon suivante. Soient IL un corps e Ihtsh:10 --> IL une fonction de hachage cryptographique publique. Une fonction de hachage cryptographique est une fonction de hachage qui est notamment résistante aux collisions (il est en pratique impossible de trouver un message qui donne le même hash que celui d'un message aléatoire donné). De plus, il est en 10 pratique impossible de retrouver le contenu d'un message à partir de son hash (calculé par une fonction de hachage cryptographique). Pour chiffrer un message clair M M1,... Fn le circuit q électronique calcule, selon une mise en oeuvre possible, un hash =ilash M) un message chiffré tronqué c: 15 = (c'...,Cm) Le message chiffré correspondant au message clair comme étant le couple est défini Le déchiffrement peut alors &opérer de la manière suivante. Soit (r1 ) n m et C, ) t).T 1. Le possesseur 20 de la clé privée peut déchiffrer le message chiffré (c- h) en recherchant, pour chaque r fRoost (r1,." m 1,1 , les solutions Z e jK du système: U001+1 (Z C't , 3038474 28 avec ( ) = MAP Le circuit électronique calcule alors M E (POEMAP pour un Z. solution de l'équation (2), telle que Hash(q)((MAP-I - S » 1. S'il y a plusieurs M possibles 5 (MAI) I renvoyant une préimage comprenant plusieurs éléments), te circuit électronique recherche parmi eux un élément M qui a la bonne empreinte h. Si la première solution Z trouvée ne convient pas (le hash du ou de chacun des message(s) M estimé(s) n'est pas égal à h et ne correspond donc pas le circuit électronique teste une autre des solutions Z. jusqu'à tomber sur la 10 bonne. Plus précisément, si aucune des solutions pour un "k111-111 donné ne convient, le circuit sélectionne un autre et recherche toutes les solutions pour ce LI ( - ri ,.;1-11) ..,1 . Le calcul de hash permet ainsi de déterminer laquelle des solutions est la bonne dans l'hypothèse où il y aurait plusieurs 15 solutions. Selon une mise en oeuvre possible fe circuit électronique calcule une signature électronique de la manière suivante. Le circuit électronique applique le procédé de déchiffrement précédemment décrit sur un message M à signer, auquel il a préalablement 20 concaténé des valeurs tirées aléatoirement. Soit Hash LI q une fonction de hachage cryptographique, qui peut être la même que la fonction de hachage utilisée pour le déchiffrement (on a alors = I) ou être une fonction de hachage différente (il importe évidemment que la fonction de hachage utilisée pour le chiffrement soit la 25 même que celle utilisée pour le déchiffrement, et que la fonction de hachage utilisée pour la signature soit la même que celle utilisée pour la vérification de 3038474 29 signatu e Pour signer un message e e circuit électronique calcule, selon un mode de réalisation possible, l'empreinte ,..., = Flash (M) du message M à signer. Le circuit 5 électronique tire aléatoirement n -m) valeurs - .. 5rn-m n et calcule une solution Z du système: (z) C 't AP I ço-1(((a.r, ' sig c K(MAP-I (Z) vecteur 1(((a,r. J- - Boosi 7 \ l.-=1 avec: CI --- Le 10 si:r; message S-1) tel que est une signature du Pour un ( ,.",rn--, donné, il est possible que l'équation (3) n'ait aucune solution. Sic'est le cas, le circuit électronique répète le procédé avec d'autres valeurs pour ri - -- . Par exemple, le circuit 15 électronique génère de nouveaux nombres aléatoires ri ,--- , OU incrémente les nombres aléatoires précédemment générés. Pour vérifier que la signature slg est valide pour M, le circuit électronique compare = Hash ) avec l'évaluation de la signature Sig en la clé publique. Autrement dit, le circuit électronique teste si 20 Si l'égalité n'est pas vérifiée, alors Slg n'est pas une signature valide du message 3038474 30 Un exemple particulier de réalisation est illustré ci-dessous: Soit (ci n, in, t, D) En: avec ci une puissance d'un nombre premier et t - 1 . Par exemple, ci peut être une puissance de 2. Le circuit électronique utlIlse comme polynôme HFE un polynôme si;(- tel que: 5 SEC ° iF ri [X] avec d,1 Xe . Comme D 13'ost= Dsi_c qd , le circuit électronique 10 peut déterminer les racines d , en un temps inférieur à 0 DSEC Dans cet exemple de réalisation, le polynôme de type HFE est la composée de deux polynômes. Que ce soit une composée n'influence pas la sécurité (ne la réduit pas). Mais le fait que ce polynôme soit une composée permet, pour le titulaire de la clé privée qui connaît la décomposition, de 15 résoudre plus facilement et donc plus rapidement l'équation, et donc d'effectuer une opération à clé privée plus rapidement. Il suffit de rechercher en deux étapes les solutions de polynômes de plus bas degré. Ainsi, si l'on note Z une racine de F on constate que: (:\ 1 '11 (Z)) FBoost 20 \iÀ1 donc transforme bien les racines de L en les racines de L'inverse de MM) est AP 1:X F-3 . En effet, MAP-I (MAI)( X)) - MAP-1 X' )- X dans E^ Comme DI 1(/q, les racines de Fgoost peuvent être calculées en un temps inférieur à 0(C(D, . Dans cet exemple, et MARI sont 25 linéaires. FBoo,,t MAP I:X I > X et Boost ' qfl ' 3038474 31 Un autre exemple particulier de réalisation est illustré ci-après Soit (g, n, m, t, D) avec q = 2, t =1 n > X] , avec un polynôme type HFE [X] un polynôme de degré Les sont tous divisibles par X est de degré Soit 5 de degré Li termes de Bocist Nous avons ici K = F21, 1 MAP et MAP:XFXL. 10 Cet exemple se distingue de l'exemple précédent notamment en ce que 3 (dans X3) n'est pas une puissance (d'exposant strictement supérieur à 1) d'un nombre premier (et notamment, 3 n'est pas une puissance de 2). Soit Z une racine de On a: ,t(i11111)(Z Z). MU transforme donc bien 15 les racines de FsEc en les racines de L11 Comme Di racines de E1,1',,, sont calculables en un temps inférieur à 1 , les Un troisième exemple particulier de réalisation est illustré ci-après. Soit (q. n. t, D) e '5 avec q = 2, t= 2, n 3. 20 Soit si;( F(X2)+ , avec F un polynôme type HFE de degré D. On définit: (.1.1)(2) f MAP_LX I > (X, 0) , et MAP(X) .X). Soit Z une racine de - On a: " -'(111AP(Z)) F(Z2)+1 X.Z) 3038474 32 NIAP(Z)) \__I transforme donc bien une racine de L.,,LL en une racine commune de fil et de Dans cet exemple M \_1) 1 est donnée par ( Y2 ) H> Y2 5 De façon plus générale, il a été exposé qu'au lieu d'une simple composition il est possible de mettre en place une transformation (grâce à la fonction de mappage MAP) qur permet de transformer la représentation d'un polynôme de type HFE conventionnel grâce à ensemble de polynômes 10 supplémentaires permettant de simplifier (et donc accélérer) le calcul. L'invention ne se limite pas aux formes de réalisation décrites ci-avant à titre d'exemple. Elle s'étend à d'autres variantes. Les divers circuits électroniques et sous circuits électroniques envisagés 15 peuvent être chacun tout circuit électronique approprié, par exemple un circuit électronique dédié, un FPGA, un ASIC, un microcontrôleur, un DSP, ou encore un circuit comprenant un processeur et une mémoire, la mémoire stockant un programme d'ordinateur approprié. Les mémoires utilisables ne se limitent pas aux exemples donnés à titre 20 purement illustratif mais couvrent tout type de mémoire fonctionnellement équivalent. Les modes de réalisation décrits en relation avec les procédés selon l'invention se transposent aux circuits électroniques, ainsi qu'aux programmes d'ordinateur et aux supports de stockage selon l'invention, et réciproquement. 25 REVENDICATIONS1. Procédé de mise en oeuvre accélérée, par un circuit électronique (SC), d'un algorithme cryptographique HFE exploitant une clé privée HFE basée sur un polynôme (FsLc) de type HFE, sur un morphisme (y)), et sur une première (S) et une deuxième (T) transformations affines, le procédé comprenant: /El/ une utilisation, par le circuit électronique (SC), d'au moins un polynôme (f1 r`-' supplémentaire compris dans la clé privée HFE, et /E2/ une utilisation, par le circuit électronique (SC), d'une première (MAP) et d'une deuxième (MAP_I) fonctions de mappage comprises dans la clé privée HFE, et associant chacune, à un paramètre d'entrée (A, C') donné, autant de paramètres de sortie (A1,...,A1,C1,...,C'1) qu'il y a de polynômes u SI supplémentaires dans la clé privée HFE, l'au moins un polynôme (f1s'-0 ,...,f1B0) supplémentaire et les fonctions de mappage (MAP, MAP_I) étant tels que, pour un paramètre (C') donné, et pour toute racine (A) du polynôme (FsLc) de type HFE moins ledit paramètre C') donné, le résultat de la première fonction de mappage (MAP) appliquée à ladite racine (A) est une racine de chaque polynôme (f,') supplémentaire moins un paramètre de sortie (C'1), correspondant audit chaque polynôme f;300s' supplémentaire, de la deuxième fonction de mappage (MAP_I) appliquée audit paramètre (C') donné. 2. Procédé selon la revendication 1, comprenant une génération, par le circuit électronique (SC), de ladite clé privée HFE, ladite génération comprenant: /G1/ une génération, par le circuit électronique (SC), dudit au moins un polynôme supplémentaire et /G2/ une génération, par le circuit électronique (SC), desdites fonctions de mappage (MAP, MAP_I). 3038474 34 3. Procédé selon ta revendication 1 ou 2, comprenant une opération de déchiffrement mise en oeuvre par : /D1/ une réception, par le circuit électronique (SC), d'un message sous forme chiffrée et d'un hash calculé sur le message sous forme non chiffrée, 5 /D2/ une application par le circuit électronique (SC), de l'inverse de la deuxième transformation affine (T) au message sous forme chiffrée afin d'obtenir un message chiffré intermédiaire, /D3/ une application, par le circuit électronique (SC), de l'inverse du morphisme (q)) au message chiffré intermédiaire, 10 /D4/ une obtention d'au moins un paramètre de sortie par application, par le circuit électronique (50), de la deuxième fonction de mappage (MAP_I) au résultat de ladite application de l'inverse du morphisme /D5/ une résolution, par le circuit électronique (SC), d'un système 15 d'équation(s) tel que chaque polynôme (f') supplémentaire soit égal au paramètre de sortie (C',) respectif obtenu à l'étape précédente, /D6/ une application, par le circuit électronique (SC), de l'inverse de la première fonction de mappage (MAP) à une solution du système d'équation(s), 11D71 une application, par le circuit électronique (SC). du morphisme (g') 20 au résultat de l'inverse de la première fonction de mappage (MAP) obtenu à l'étape précédente, 11381 une obtention d'une estimation du message sous forme non chiffrée, par application, par le circuit électronique (SC), de l'inverse de la première transformation affine (S) au résultat du morphisme (9) obtenu à 25 l'étape précédente, /09/ un calcul, par le circuit électronique (SC) d'un hash de l'estimation du message sous forme non chiffrée, /D10/ si le hash de l'estimation du message sous forme non chiffrée est différent du hash reçu, l'obtention d'une autre estimation du message sous 30 forme non chiffrée selon les étapes précédentesjusqu'à ce que les deux hash soient égaux. 3038474 4. Procédé selon l'une des revendications précédentes, comprenant une opération de signature mise en oeuvre par : /S1/ un calcul, par le circuit électronique (SC), d'un hash d'un message à signer, 5 /S2/ une génération, par le circuit électronique (SC), d'un nombre aléatoire de taille égale à la taille d'un élément de l'ensemble d'arrivée du morphisme (i,-> ) moins la taille du hash du message à signer, /S3/ une application, par le circuit électronique (SC), de l'inverse de la deuxième transformation affine (T) à une concaténation du nombre aléatoire et 10 du hash du message à signer, /S4/ une application, par le circuit électronique (SC), de l'inverse du morphisme ço) au résultat de l'application de l'inverse de la deuxième transformation affine (T), /S5/ une obtention d'au moins un paramètre de sortie par 15 application, par le circuit électronique (SC), de la deuxième fonction de mappage (MAP_I) au résultat de ladite application de l'inverse du morphisme 47), /S6/ une résolution, par le circuit électronique (SC): d'un système d'équation(s) tel que chaque polynôme (f) supplémentaire soit égal au 20 paramètre de sortie (Cl,) respectif obtenu à l'étape précédente, /571 si le système d'équation(s) n'admet pas de solution, une répétition des étapes précédentes avec un autre nombre aléatoire. /581 une application, par le circuit électronique (SC), de l'inverse de la première fonction de mappage (MAP) à une solution du système d'équation(s), 25 1S91 une application, par le circuit électronique (SC), du morphisme (iço) au résultat de l'inverse de la première fonction de mappage (MAP) obtenu à l'étape précédente, /S10/ une obtention d'une signature du message à signer, par application, par le circuit électronique (SC), de l'inverse de la première 30 transformation affine (S) au résultat du morphisme (ço) obtenu à l'étape précédente. 3038474 36 5. Procédé selon l'une des revendications précédentes, dans lequel la clé privée HFE comprend un unique polynôme supplémentaire, dans lequel la première fonction de mappage (MAP) est un monôme, et dans lequel le polynôme de type HFE (FsEc) est égal à la composition du polynôme 5 supplémentaire avec la première fonction de mappage (MAP). 6. Programme d'ordinateur comprenant une suite d'instructions mettant en oeuvre les étapes du procédé selon l'une des revendications 1 à 5 lorsqu'elles sont exécutées par un processeur. 10 7. Support de stockage non transitoire lisible par ordinateur comprenant un programme d'ordinateur selon la revendication 6. 8. Circuit électronique (SC) agencé pour mettre en oeuvre de façon 15 accélérée un algorithme cryptographique HFE exploitant une clé privée HFE basée sur un polynôme (FsLc) de type HFE, sur un morphisme (q)), et sur une première (S) et une deuxième (T) transformations affines, le circuit électronique (SC) comprenant: un sous circuit électronique d'utilisation d'au moins un polynôme 20 (fiBoost,..., tai us: supplémentaire compris dans la clé privée HFE, et un sous circuit électronique d'utilisation d'une première (MAP) et d'une deuxième (MARI) fonctions de mappage comprises dans la clé privée HFE, et associant chacune, à un paramètre d'entrée (A, C') donné, autant de paramètres de sortie (A1,....A. C'i,...,C't) qu'il y a de polynômes (fi Boost ,fiBoost) 25 supplémentaires dans la clé privée HFE, l'au moins un polynôme (f1'30'supplémentaire et les fonctions de mappage (MAP, MAU) étant tels que, pour un paramètre (C') donné, et pour toute racine (A) du polynôme (FsLc) de type HFE moins ledrt paramètre (C') donné, le résultat Ai,...,At) de la première fonction de mappage (MAP) 30 appliquée à ladite racine (A) est une racine de chaque polynôme (fiBuost) supplémentaire moins un paramètre de sortie (C'1), correspondant audit chaque polynôme (fost) supplémentaire, de la deuxième fonction de mappage (MAR_ ) appliquée audit paramètre C') donné. 3038474 37 9. Circuit électronique (SC) selon la revendication 8, comprenant, afin de mettre en oeuvre une opération de déchiffrement un sous circuit électronique de réception d'un message sous forme 5 chiffrée et d'un hash calculé sur le message sous forme non chiffrée, un sous circuit électronique d'application de l'inverse de la deuxième transformation affine (T) au message sous forme chiffrée afin d'obtenir un message chiffré intermédiaire, un sous circuit électronique d'application de l'inverse du morphisme (q)) 10 au message chiffré intermédiaire, un sous circuit électronique d'obtention d'au moins un paramètre de sortie (C'1,...,C',), par application de la deuxième fonction de mappage (MAP_I) au résultat de ladite application de l'inverse du morphisme un sous circuit électronique de résolution d'un système d'équation(s) tel 15 que chaque polynôme (1'301 supplémentaire soit égal au paramètre de sortie (C',) respectif, un sous circuit électronique d'application de l'inverse de la première fonction de mappage (MAP) à une solution du système d'équation(s), un sous circuit électronique d'application du morphisme ( ) au résultat 20 de l'inverse de fa première fonction de mappage MAP), un sous circuit électronique d'obtention d'une estimation du message sous forme non chiffrée, par application de l'inverse de la première transformation affine (S) au résultat de l'application du morphisme (p), un sous circuit électronique de calcul d'un hash de l'estimation du 25 message sous forme non chiffrée, un sous circuit électronique de vérification agencé pour vérifier si le hash de l'estimation du message sous forme non chiffrée est différent du hash reçu, et dans l'affirmative pour déclencher l'obtention d'une autre estimation du message sous forme non chiffrée, jusqu'à ce que les deux hash soient égaux. 30 10. Circuit électronique (SC) selon la revendication 8 ou 9, dans lequel la clé privée HFE comprend un unique polynôme supplémentaire, dans lequel la 3038474 38 première fonction de mappage (MAP) est un monôme, et dans lequel le polynôme de type HFE (FsEO est égal à la composition du polynôme supplémentaire avec la première fonction de mappage (MAP).