Brevet FR2769726A1 — publié le 19990416

Nouveau procédé de cryptographie numérique par boîte de mélange La présente invention concerne un procédé dc cryptographie de données enregistrées sous forme dc bits sur un support exploitablc par une unité de calcul apte à traiter des données d'entrée m, pour fournir des données de sortie m1, comportant au moins une étape de traitement de données dans laquclle l'unité de calcul utilise une fonction Ck (m) dépendante d'une clef k. On connaît de nombreux procédés de cryptographie. Ils permettent le codage ou chiffrement de données au moyen d'unc clef ecrète, de sortc que les données deviennent inintelligibles à quiconque ne possède pas la clef. Le procédé doit cependant être réversible pour que le destinataire légitime des donnécs puisse les comprendre ; c'est le déchiffrement. Chiffrement ct déchiffrement constituent la cryptographie. Les principes fondamentaux de cryptographie ont été définis par Shannon en 1949. De nos jours, ils reposent principalement sur l'utilisation d'une unité de calcul qui traitc des fonctions ct des données au moyen de circuits électroniques. La fonction Data Encryption Standard (DES) proposée par le gouvernement américain en 1977 est un exemple devenu un standard intcrnational. La fonction DES était parfaitement adaptée aux bcsoins de sécurité ct à la technologie de l'époque, mais cllc est désormais insuffisantc, comme l'a montré le dernier concours d'attaque Challenge RSA. En outrc, des attaqucs statistiqucs miscs au point par Biham ct Shamir d'une part ct par Gilbert ct Matsui d'autre part ont dévoilé les faiblesses structurelles de la fonction DES. DES devrait prochainement être remplacée par un nouvcau standard, la fonction Advanced Encryption Standard (AES). Le but de l'invention est un procédé de cryptographie de données qui assurc une grande sécurité, qui peut être réalisé avec des fonctions rclativcmcnt simples nécessitant des moyens de calcul limitcs ct qui assurc des performances optimalcs avec la technologic actucllc, en cmployant le moins possible de circuits électroniques, par souci d'économie. A cet effet, l'invention conccrnc un procédé de cryptographie tel que défini ci-dcssus, caractérisé en ce que la fonction Ck(m) dépendante d'unc clef k, comporte une boîte de mélange M apte à traiter des données d'entrée de boîte de mélange (x1, ..., xi, .., x@), r # 2, pour fournir des données de sortie de boîte de mélange, boîte de mélange qui, lorsquc toutes les données d'entrée de boîte de mélange, sauf unc, sont fixes, produit pour chaque donnée de sortic de boîte de mélange une valcur qui est obtenue par permutation de la valcur de la donnée d'entrée dc boîte dc mélange non fixe. Selon un mode de réalisation de l'invention, la boîte dc mélange M est une permutation, ct de préférence, la boîte de mélange M est une multipermutation. Selon une variantc, la boîte de mélange M comporte une permutation sur au moins l'une quclconque de ses données d'entrée ou de ses données de sortic. Selon un mode de réalisation préféré dc l'invention, la fonction Ck(m) est obtenue par la mise en ocuvre d'étapes successives de traitement de données, chaque étape vérifiant la propriété des données de sortie de boîte de mélange. Avantagcusemcnt, la boitc de mélange comporte une étape de traitement de données par une fonction linéaire invcrsiblc #(x). A titre d'exemple, la fonction cp(x) est définie, dans un mode de représentation de donnécs, par #(x1, ..., x5, x4, x2, x1, x0) = (x1, ..., x5, x4 # x3, x3, x2 # x1, x1, x0 # x1), où x0, ..., x1 sont des blocs dc bits ct où 0 représente la fonction OU exclusif bit-à-bit. Selon un autrc exemple, la fonction (p(x) est définie, dans un mode de représentation de données, par : #(x1, ..., x5...x0) = (x1 # xt-1, ..., x5 # x4, x4, x3 # x2, x2, x1 # x0, x0), où x0, ..., xt sont des blocs de bits et où # représente la fonction OU exclusif bit-à-bit. Selon unc variante, le procédé de cryptographic comporte une étape de traitement de données par une permutation P à X bits d'entrée ct 8 bits de sortie, telle quc DPmax (P) = max a@0 Prx uniforme [P (x # a) # P (x) = b] # ou LPmax (P) = max a,b@0 (2 Prx uniforme [x. a = P (x).b] - 1)2 # la permutation P étant réalisée au moyen d'un circuit logiquc de profondeur inférieure ou égale à 17. Selon un perfectionnement, la permutation P est une involution. Selon une autre variante, le procédé de cryptographie comporte une étape de traitement de données par une permutation g à 4 bits d'entrée ct 4 bits de sortie, telle que DPmax (g) = max a@0 Prx uniforme [g (x # a) # g (x) = b] # 2-2, ou LPmax (g) = max a,b@0 (2 Prx uniforme [x.a = g (x).b] - 1)2 # 2-2, la permutation g étant réalisée au moyen d'un circuit logiquc de profondeur inférieure ou égale à 4. Sclon une autre variante, le procédé de cryptographie comporte une étape de traitement de données par une fonction f à 4 bits d'entée et 4 bits de sortie, telle que : DPmax (f) = max a@0 Prx uniforme [f (x # a) # f (x) = b] # 2-2, ou LPmax (f) = max a,b@0 (2 Prx uniforme [x.a = f (x).b] -1)2 # 2-2, la fonction f étant réalisée au moyen d'un circuit logique de profondeur inféricure ou égale à 2. Selon un mode de réalisation particulicr, la fonction f est définie par f (x3, x2, x1, Xo) = [NON(NONx3 . x2), NON(NONx2 . x1), NON(NONx1 . x0), NON(NONx0 . x3)]. Selon un perfectionnement, la clef k est décomposée en au moins deux blocs k-l et k-2, et sclon un autre pcrfcctionncmcnt, les blocs k-l ct k-2 sont traités au moyen d'un schéma de Feistel pour produirc des sous-clcfs k0, ..., Un mode de réalisation de la présente invention sera décrit ci-après en référence aux figures annexécs dans lesquelles : - a figure 1 représente une vue d'ensemble du chiffrement, - la figure 2 représente chaque fonction F de la figure 1, - la figure 3 représente la fonction g dans laquelle la lettre "n" est une fonction électronique NAND, - la figure 4 représente chaque permutation P de la figure 2, - la figure 5 représente la transformation E dc la figure 1 précédéc d'une série de transformations utilisant la fonction OU exclusif, - la figure 6 représente les fonctions M ct M-1 dc la figure 5, - la figure 7 représente schématiquement les opérations de déchiffremcnt, c'cst-à-dirc les opérations inverses telles que celles décrites aux figures précédentes. Selon cct exemple, le procédé dc cryptographie traite les données enregistrées m par blocs de longucur fixc égale à huit octets. La fonction Ck est réalisée au moyen d'une unité de calcul qui utilise une boîte de mélange M(x, y) à deux entrées. On rappelle qu'une boîte de mélange (M(x1, ...,xr) a r entrées (r # 2) est une fonction qui transforme r entrées en n sorties, de telle sortc que chaque sortie ait une distribution uniforme par permutation si l'on fixe arbitrairement (r - 1) entrées et que l'entrée rcstantc est aléatoire. Ainsi qu'il apparaît figure 1, l'ensemble des huit octect de m subit au travers du réseau de calcul successivement huit étapes de transformation semblables, puis une opération finalc. Chaque étape consistc à cffcctucr un ou exclusif bit-à-bit avec une sous-clcf k'. calculée à partir dc k ct qui dépend du numéro de l'étape i, puis à effectuer une transformation E. L'étape finalc est un ou exclusif bit-à-bit avec une dernière sousclef k8. On a donc Ck(m) = k8 # E (k7 # ... E (k1 # E (k0 # m))). On notc mi # bloc de huit octets qui cntre à l'étape i. (Le bloc entrant à l'étape 0 est m0 = m). Le bloc sortant est On a donc mi+1 = E(k1 # mi) ct m' = k8 # m8 Les clefs d'étape, toutes de huit octets, sont obtenues à partir de k par un procédé de diversification de clefs fondé sur le schéma de Feistel. La clef k est à l'origine une suite d'octets de longueur variable (au plus seize) que l'on complète sur seize octets avec des octets nuls. Ces seize octets sont découpés en deux séquences de huit octets k-2 et k-1 qui initialisent la suite k-2, k-1 k0, k1,...,k8. Deux éléments consécutifs ki et ki+1 de cette suite déterminent un nouvel élément ki+2 par la formule de récurrence ki+2 = ki # Fc1+2(ki+1) au movell d'une fonction Fci+2 qui utilise une constante préétablie ci+2. La figure 1 illustre la vue d'ensemble du procédé de chiffrement. La fonction fci+2 effectue d'abord un ou exclusif bit-à-bit de l'entrée avec la constante É+2, puis applique une transformation P sur chacun des huit octets obtenus, et enfin une transformation T (voir figure 2). Si l'on considère les huit octets qui sortent des transformations P comme un tableau de huit lignes de huit bits, la transformation T ne fait qu'échanger les lignes et les colonnes. La transformation P est décrite par un schéma de Feistel. L'entrée est un octet découpé en deux nombres de quatre bits. Chaque nombre entre dans l'une des branches du schéma de Feistel décrit sur la figure 4. On utilise deux fonctions f et g. La fonction f est définie par la table hexadécimale x 0 1 2 3 4 5 6 7 8 9 a b c d e f f(r) f d b b 7 5 7 7 e d a b e d 7 f qui provient de la formule ~(x3, x2, x1, x0) = (x3.x2, x2.x1, x1.x0, x0.x3). I,a fonction f a une bonne non-linéarité. On a en effet DPmax(f) = 2-2 et LPmax(f) = 2-2. De plus, la fonction f peut être réalisée par un circuit logique de profondeur deux. Les quantités DPmax et LPmaX mesurent la non-linéarité suivant des critères mis en évidence par Nyberg, Chabaud et Vaudena,v, puis Matsui. Par définition, on a DPmax(f) = max Pr [f(x # a) # f(x) = b] a#0,b x uniforme et LPmax(f) = max (2 Pr ex a = f(x)- b] . ,h7j0 .T uniforme La fonction g est définie par la table x lo 1 2 3 4 5 6 7 8 9 a b c d e f g(x) a 6 0 2 b e 1 8 d 4 5 3 f c 7 9 qui provient du circuit logique de profondeur quatre représenté sur la figure 3. La fonction g est de plus une permutation et présente une bonne non-linéarité puisque l'on a DPmax(g) - 2-2 et LPmax(g) = 2-2. La transformation P vérifie DPmax(P) = 2-4 et LPmax(P) = 2-4. Cela permet au procédé de chiffrement de résister aux attaques de Biham et Shamir et de Gilbert et Matsui. Le schéma de Feistel de la transformation P utilise successivement les fonctions f, g et f. Une conséquence est que P présente une propriété d'involution : la transformation inverse de P est P elle-même, ce qui facilite l'opération de déchiffrement. La table de la permutation P est .0 .1 .2 .3 .4 .5 .6 .7 .8 .9 a b c .d e f 0. 29 Od 61 40 9c eb 9e 8f 1f 85 5f 58 5b 01 39 86 1. 97 2e d7 d6 35 ae 17 16 21 b6 69 4e a5 72 87 08 2. 3c 18 e6 e7 fa ad b8 89 b7 00 f7 6f 73 84 11 63 3. 3f 96 7f 6e bf 14 9d ac a4 0e 7e f6 20 4a 62 30 4. 03 c5 4b 5a 46 a3 44 65 7d 4d 3d 42 79 49 lb 5c 5. f5 6c b5 94 54 ff 56 57 Ob f4 43 Oc 4f 70 6d Oa 6. e4 02 3e 2f a2 47 eO ci d5 la 95 a7 51 5e 33 2b 7. 5d d4 id 2c ee 75 ec dd 7c 4c a6 b4 78 48 3a 32 8. 98 af cO el 2d 09 Of le b9 27 8a e9 bd e3 9f 07 9. bl ea 92 93 53 6a 31 10 80 f2 d8 9b 04 36 06 8e a. be a9 64 45 38 lc 7a 6b f3 ai fO cd 37 25 15 81 b. fb 90 e8 d9 7b 52 19 28 26 88 fc di e2 8c aO 34 c. 82 67 da cb c7 41 e5 c4 c8 ef db c3 cc ab ce ed d. dO bb d3 d2 71 68 13 12 9a b3 c2 ca de 77 dc df e. 66 83 bc 8d 60 c6 22 23 b2 8b 91 05 76 cf 74 c9 f. aa fl 99 a8 59 50 3b 2a fe f9 24 bO ba fd f8 55. On a par exemple P(26) = b8. En effet, on a f(6) = 7, 2 e 7 = 5, g(5) = e, 6 # e = 8, f(8) = e et enfin 5 # e = b. Cette table définit également les constantes ci utilisées dans le système de diversification des clefs d'étape: ce = 290d61409ceb9e8f c1 = 1f855f585b013986 c2 = 972ed7d635ae1716 c3 = 21b6694ea5728708 c4 = 3c18e6e7faadb889 c5 = b700f76f73841163 c6 = 3f967f6ebf149dac cl = a40e7ef6204a6230 = = 03c54b5a46a34465. La transformation E utilisée dans chaque étape du chiffrement est une superposition de trois étages illustrés sur la figure 5 (on a indu le ou exclusif avec la clef d'étape k2 sur cette figure). Chaque étage est constitué d'un ou exclusif, avec une clef d'étape, ou une constante c ou c', de quatre boîtes de mélange f, et d'échanges de position des octets. Les constante c et c' sont définies par le développement de la constante mathématique e = 2,b7e151628aed2a6abf7158809cf4f3c762e7160f38b4da56a7 soit c = b7el51628aed2a6a c' = bf7158809cf4f3c7. Chaque boîte M transforme deux octets xg et xd en deux octets yg et Yd par la formule yg = P(#(xg)#xd) yd = P(R)(xg) # xd) où R est la rotation circulaire définie par R(x7,x6,x5,. .,x0) = (x6,x5,,...,x0,x7) et où # est une fonction définie par #(x7,. .,x0) = (x7,x6#x5,x5,x4#x3,x3,x2#x1,x1,x0#x7). La fonction M est construite pour satisfaire la propriété de boîte de mélange. Un critère de construction a été de la rendre facile à réaliser avec la technologie actuelle. Elle est également telle que la fonction inverse M-1 est également facile à réaliser. En fait, les fonctions M et M-1 peuvent être réalisées par les circuits représentés sur la figure 6 (on a inclu le ou exclusif avec la constante (c9, cd) sur cette figure). La fonction #' est définie par #'(x7,...,x0) = (x7#x6,x6,x5#x4,x4,x3#x2,x2,x1#x0,x0). Elle réalise en outre la propriété de mulltipermutation définie par Schnorr et Vaudenay, De façon générale, une e multipermutation à r entrées et n sorties est une e fonction f = (f1,...,fn) telle que chaque paire de famille (x1,...,xr,f1(x1,...,xr),. .,fn(x1,...,xr)) diffère sur au moins n t 1 positions. L'échange de position des octets de chaque étage est fondé sur le graphe de la transformée de Fourrier rapide, utilisé dans la fonction Parallel FFT Hashing de Schnorr et Vaudenav, et dans la fonction SAFER de Massey. Il présente les meilleurs propriétés de diffusion et de confusion. Le déchiffrement se réalise de manière semblable, en remontant chaque étape illustrée par la figure t. Le procédé de chiffrement peut être réalisé par un circuit qui utilise la technologie pipeline" : en découpant le réseau de calcul en plusieurs couches successives, on réalise chaque couche par un circuit logique et l'on insère des registres entre chaque couche. Cela permet de traiter uii flôt de données à chiffrer avec un débit plus élevé. REVENDICATIONS 1. Procédé de cryptographie de données enregistrées sous forme dc bits sur un support exploitable par une unité de calcul aptc à traiter des données d'entrée m, pour fournir des données de sortie m', comportant au moins une étape de traitement de données dans laquelle l'unité de calcul utilise une fonction Ck (m) dé[emdamte d'une clef k, caractérisé en ce que la fonction comporte une boîte de mélange M aptc à traiter des données d'entrée de boîte de mélange (x1, ..., xi, ..., xf), avce r # 2, où x1, ...,xr sont des blocs de bits, pour fournir des données de sortie de boîte de mélage, boîte de mélange qui, lorsque toutes les données d'entrée de boîte de mélange, sauf une, sont fixes, produit pour chaque donnée dc sortie dc boîte de mélange une valeur qui est obtenuc par permutation de la valcur de la donnée d'entrée de boîte de méclange non fixe. 2. Procédé de cryptographie sclon la revendication 1, caractérisé cn ce que la boîte de mélange M est une permutation. 3. Procédé de cryptographic sclon la revendication 1 ou 2, caractérisé en ce que la boîte de mélange M est une multipcrmutation. 4. Procédé de cryptographic sclon l'une quelconque des revendications précédentes, caractérisé en ce que la toîte de mélange M comporte une permutation sur au moins l'une quelconque de ses données d'entrée ou de ses données de sortic. 5. Procédé de cryptographie selon I'unc quclconquc des revcndications précédentes, caractérisé en ce que la fonction Ck(m) est obtenue par la mise en oeuvre d'étapes successives dc traitcmcnt de données, chaque étape vérifiant la propriétc des données de sortie de boîte de mélange. 6. Procédé de cryptographie sclon I'unc quelconque des revendications précédentes, caractérisé en ce que la boîte de mélange comporte une étape de traitement de données par une fonction linéaire invcrsiblc #(x). 7. Procédé de cryptographic sclon la revendication 6, caractérisé en ce que la fonction #(x) est définie, dans un mode de représentation dc données, par #(xt, ..., x5, x4, x2, x1, x0) = (x1, ..., x5, x4 # x3, x3, x2 # x1, x1, x0 # x1), où x0 ..., x, sont des blocs de bits ct où # représente la fonction OU exclusif bit-à-bit. 8. Procédé de cryptographie sclon la rcvcndication 6, caractérisé en ce que la fonction #(X) est définie, dans un mode de représentation de données, par #(x1, ..., x5...xo) = (x1 # x@-1, ..., x5 # x4, x4, x3 # x2, x2, x1 # x0, x0), où X0, ..., x, sont des blocs de bits ct où # représente la fonction OU exclusif bit-à-bit. 9. Procédé de cryptographie sclon l'une quelconque des revcndications précédentes, caractérisé en ce qu'il comporte une étape de traitement de données par une permutation P à 8 bits d'entrée et 8 bits de sortie, telle que DPmax (P) = maxa=0 Prx uniforme [P (x # a) # P (x) = b] # 2-4, ou LPmax (P) = maxa,b=0 (2 Prx uniforme [x . a = P (x).b] - 1)2 # la permutation P ctant réslisée au moyen d'un circuit logiquc de profondeur inférieurc ou égale à 17. 10. Procédé de cryptographie sclon la revendication 9, caractérisé en ce que la permutation P est une involution. 11. Procédé de cryptographie sclon l'une quclconquc des revendications précéentes, caractérisé en ce qu'il comporte une étape de traitement de données par une permutation g à 4 bits d'entrée ct 4 bits de sortie, telle quc DPmax (g) = maxa-0 Prx uniforme [g (x G a) G g (x) = b] s 2-2, ou LPmax (g) = max a,b=0 (2 Prx uniforme [x.a = g (x).b] - 1)2 s 2-2, la permutation g étant réalisée au moyen d'un circuit logiquc de profondeur inférieure ou égale à 4. 12. Procédé de cryptographie selon l'une quelconque des revendications précédentes, caractérisé cn ce qu'il comporte une étape de traitement de données par une fonction f à 4 bits d'entée ct 4 bits de sortie, telle quc DPmax (f) = maxa=0 Prx uniforme [f (x # a) # f (x) = b] # 2-2, ou LPmax (f) = maxa,b=0 (2 Prx uniforme [x.a = f (x).b] - 1)2 # 2-2, la fonction f étant réalisée au moyen d'un circuit logiquc de profondeur inférieure ou égale à 2. 13. Procédé de cryptographie sclon la revendication 12, caractérisé en ce que la fonction f est définic par f (x3, x2, x1, x0) = [NON(NONx3 . x2), NON(NONx2 . x1), NON(NONx1 . x0), NON(NONx0 . x3)]. 14. Procédé de cryptographie selon l'une quelconque des revcndications précédentes, caractérisé en ce que la clef k est décomposée en au moins deux blocs k-1 et k-2. 15. Procédé dc cryptographie sclon la revendication précédente, caractérisé en ce que les blocs k-' et k-2 sont traits au moyen d1un schéma de Feistel pour produirc des sous-clefs k0, ..., kn