Brevet FR2771237A1 — publié le 19990521

Procédé de chiffrement. La présente invention concerne un procédé de chiffrement, c'est-à-dire un chiffreur, dont l'originalité première est d'utiliser des éléments générateurs pseudoaléatoires mwc. On fait appel, dans certains domaines statistiques, aux générateurs pseudoaléatoires de multiplication par retenue (multiplication with carry) à l'aide donc d'une suite de ces éléments mwc qu'on déduit les uns des autres de la manière qui va être présentée ci-après. Un élément mwc s'écrit mwc = (a, b, c) relation dans laquelle a est un multiplicateur constant, b est un reste, c est une retenue. D'un élément de rang r, on tire l'élément de rang (r + 1) comme suit Soit une base B = 2' a br + cr _ cr+1 2r + br+l mwc r+1 = (a br+ r+l) mwc =(a,b, ) En d'autres termes, dans un système à base 2", l'élément mwc de rang (r+ 1) a pour reste, le nombre de poids le plus faible et, pour retenue, le nombre de poids le plus fort du nombre représentant l'élément de rang r dans le système. Exemple en base 10 Soit, comme élément initial mwc , l'élément 2 2771237 (6, 4, 4), avec a = 6, b = 4, co = 4 mwc = 28 (6 x4 + 4) = 2x10+ 8 mwc1 s'écrit donc (6, 8, 2) avec a = 6, bl =8, c =2 1o mwc' =50(6 x 8 + 2) = 5 x 10 + O mwc2 s'écrit donc (6, 0, 5) avec a = 6, b = 0, c = 5 mwc = 5 (6x0+ 5) = 0 X 10 + 5 mwc3 s'écrit donc (6, 5, 0) avec a = 6, b3 =5, c3 = 0 et ainsi de suite. 16 r-4- r+l Dans un système à base 216, cr+l et br+l sont égaux respectivement aux 16 bits de poids fort et au 16 bits de poids faible de abr + cr. O OO Ayant présenté les générateurs mwc et leur avance, l'invention peut maintenant être introduite. L'invention concerne un procédé de chiffrement de données claires, dans lequel, - dans un système à base 2P, - on découpe les données en une suite de blocs de p bits, 3 2771237 - on considère une fonction de chiffrement d'une pluralité q de paramètres constitués de générateurs mwc et on en détermine une séquence pseudoaléatoire de valeurs itératives de p bits et - on soumet deux à deux les blocs de données de ladite suite et les valeurs de chiffrement de ladite séquence à l'une des opérations du groupe comprenant l'opération logique d et les opérations arithmétiques + et -. Avantageusement, dans la fonction de chiffrement, les générateurs mwc sont respectivement introduits alternativement par l'opération e et l'opération +. De préférence, les indices des générateurs mwc de la fonction de chiffrement constituent une suite pseudoaléatoire de g indices (g une suite déterminée de q indices. De préférence encore, lesdits générateurs mwc constituent une combinaison non linéaire. o 0 0 L'invention sera mieux comprise à l'aide de la description suivante d'une étape d'itération de la mise en oeuvre préférée du chiffreur. Le chiffrement qui va maintenant être décrit comporte un certain nombre d'étapes, ou d'itérations, comme celle qui est exposée ci-dessous et qui se déroule après avance, à l'instant (to + n A t) d'une pluralité de huit éléments mwcn 0.... mwcn7 ici de 16 bits chacun. Ce chiffrement s'effectue à l'aide de 8 registres 32 bits en tant que générateurs mwc et d'un microprocesseur 16 bits. 1.- Itération du chiffreur Soit à cet instant, c'est-à-dire à l'étape n (n = 0,1...), un leader de 16 bits, dont la détermination apparaîtra plus loin I lea15 leal4 leal3........... leal leaol 4 2771237 On considère comme terme newlea l'élément générateur mwc de l'instant considéré, c'est-à-dire de l'étape considérée, et d'un premier indice combinatoire égal à une combinaison de bits particuliers du leader, ou le complément bit à bit de cet élément, selon qu'un des bits du leader est égal à 0 ou 1. Soit le terme ind égal à une autre combinaison d'autres bits particuliers du leader et considérons l'élément mwc d'un deuxième indice combinatoire égal à une autre combinaison de bits particuliers du leader et une suite d'un nombre donné d'éléments mwc d'indices respectifs suivant l'indice combinatoire. Soit le terme cmb égal à une fonction d'éléments de la suite d'éléments selon les valeurs de quelques (deux) autres bits particuliers du leader. 2.- Sortie du chiffreur. Soit une mémoire fifo (premier entré, premier sorti) à deux éléments. A l'instant (to + n A t) considéré, et selon la valeur d'un autre bit encore du leader, la sortie de la fifo est égale - au mot du premier élément, le mot du second élément devenant celui du premier et le terme cmb devenant celui du second élément ou - au terme cmb 4 41 2 4 cmb I En d'autres termes, à l'étape n, la sortie S" du chiffreur est le mot du premier élément de la fifo ou la valeur itérative cmb déterminée. 3.- Chiffrement et déchiffrement 2771237 Les données à chiffrer sont représentées par une suite ai (i = 0,...) de blocs, ici de 16 bits. A chaque étape i, le bloc ai est "XORé" (soumis à l'opération XOR, à l'opération de "XORage") avec la sortie Si du chiffreur pour former un bloc chiffré ici de 16 bits bi. Pour déchiffrer un bloc bi, il faut aussi le XORer avec la sortie correspondante Si du chiffreur. XORer deux blocs de bits, selon le symbole e3, consiste à les entrer bit à bit dans une porte "OU exclusif", selon le tableau de vérité suivant Si 0 1 bi 0 0 1 1 1 O1 0 1 4.- Avance du chiffreur Après avoir chiffré le bloc an des données, on avance d'un rang sept des huit éléments mwc, l'élément d'un troisième indice combinatoire égal à une combinaison encore différente de bits particuliers du leader de l'étape (n) étant avancé de deux rangs. Quant à l'élément mwc d'un quatrième indice combinatoire égal à une combinaison ici toujours distincte de bits particuliers du leader, avant l'avance, on en modifie le reste b' et la retenue c' comme suit: c' = a 1 - c (+ éventuellement 216 si Pour l'étape (n+ 2), newlea devient le terme leader. 6 2771237 5.- Initialisation du chiffreur 5.1.- Initialisation par une clé de 128 bits. La clé est découpée en 8 blocs de 16 bits ko, k....k7. On considère, comme restes bo, b,... b7 des huit éléments initiaux mwc , mwc 1... mwc 7, les huit blocs ko, k1...k7, comme retenues initiales c0, cl... ci... c7, les valeurs 1, 2,... i + 1.. 8. Pour initialiser la fifo, on considère, comme premier mot, ici de 16 bits dans le système hexadécimal, le nombre DA37h, soit 1 10110100011011 1, comme deuxième mot, le nombre C07Fh, soit 11000000011 1 1 1 1 1. Comme leader initial, on considère ici le bloc ko de la clé. Avant de procéder au chiffrement proprement dit, comme défini plus haut, on procède à une série d'avances de divergence du chiffreur, en l'espèce au moins 21, comme défini au point 1 ci-dessus. En effet, dans l'exemple considéré, ce n'est qu'après 21 avances des générateurs mwc qu'on peut être sûr d'obtenir à la sortie de la fifo, avec les mêmes probabilités, soit un mot de la fifo soit le terme cmb défini ci-dessus. Sinon, et le contenu de la fifo étant accessible, l'un des bits de la clé pourrait être révélé. 5.2.- Initialisation par une clé de 248 bits La clé de 248 bits est découpée en une partie basse de 128 bits, elle-même découpée en 8 blocs de 16 bits ho, hi... h7, et une partie haute, elle-même découpée en 8 blocs de 15 bits h8, h9... h15. 7 2771237 On considère, comme restes bo, bl... b7 des huit éléments initiaux mwc o, mwc l... mwc 7, les huit blocs ho, h1... h7, comme retenues initiales c0, c1... c7, les valeurs 216 AND h8, 216 AND h9,... 216 AND hl. L'initialisation de la fifo et les avances de divergence s'effectuent comme avec la clé de 128 bits. O 0 0 Avant de présenter une généralisation du chiffreur, abordons le détail de la mise en oeuvre préférée d'une étape d'itération. 15. lea1 = 0 newlea est l'élément mwc d'indice 4 lea3 + 2 lea6 + leal3 20. lea = 1 newlea est le complément bit à bit de l'élément mwc d'indice ci-dessus. Soit l'indice d = 41ea7 + 21ea1l + lea5 lea9 = O leal2 = 1 cmb = t [c(mwcd) c(mwcd+lmod8)] + c(mwcd+2mod8) 3 c(mwcd+3mod8) relation dans laquelle - c(mwcd) est la retenue de l'élément mwcd, - (E est l'opérateur OU exclusif bit à bit, - mod8 signifie modulo 8, puisqu'il n'y a que huit éléments mwc initiaux, - + est l'opérateur arithmétique d'addition modulo 216, puisque les termes ont 16 bits. 8 2771237 leal2 = 0 cmb = t [c(mwcd) + c(mwcd+lmod8)] 0 c(mwcd+2mod8) +c(mwcd+ 3mod8) 5. lea9 = 1 lea12 = 1 cmb = cmb(lea9 = O, leal2 = 1) + c(mwcd+ 4mod8) leal2 = O cmb = cmb(leag = O, leal2 = O) À c(mwcd+4mod8) lea8 = 1 la sortie du chiffreur est le premier mot de la fifo. lea8 = O la sortie du chiffreur est cmb. C'est l'élément mwc d'indice 41ea,0 + 21ea4 + leaI4 qui est avancé de deux rangs et ce sont les reste et retenue de l'élément mwc d'indice 41ea2 + 21ea1 + leao qui sont modifiés, à la fin d'une itération. O OO Généralisation du chiffreur 1) On procède dans le système à base 2P Les données claires à chiffrer pouvant être considérées comme une suite de bits, on les découpe en une suite de blocs de p bits. 9 2771237 - On considère une fonction de chiffrement, d'une pluralité q (dans l'exemple considéré, 8) de paramètres constitués de générateurs mwc et une séquence pseudoaléatoire de valeurs itératives de cette fonction. On soumet deux à deux les blocs de la suite de blocs de p bits de données claires et les valeurs de la séquence de valeurs itératives de la fonction de chiffrement à l'opération logique ed mais les opérations artihmétiques + et - seraient également envisageables. On remarquera que, en référence à l'exemple présenté plus haut, même si cmb n'est calculé qu'avec quatre ou cinq générateurs mwc, compte-tenu du choix probabilistique de ces générateurs dans l'ensemble des huit générateurs considérés, cmb reste une fonction de ces huit générateurs. 2.- Si l'opérateur est E, le chiffreur est reversible puisque le déchiffrement s'effectue de la même manière, en soumettant les blocs de données chiffrées au même chiffeur et à la même opération logique e, pour obtenir les données claires. Si l'opérateur est + ou -, pour obtenir les données claires (respectivement chiffrées), à partir des données chiffrées (respectivement claires), on soumet celles-ci au même chiffreur mais à l'opération inverse - ou +. 3.- Dans la fonction de chiffrement, les générateurs mwc sont respectivement introduits alternativement par l'opération e et l'opération +. 4.- Dans l'exemple considéré, cmb est une fonction de quatre générateurs mwc pris parmi huit, d'indices constituant une suite pseudoaléatoire de g indices (g 0 - 7. Mais, la suite d'indices des générateurs mwc de la fonction de chiffrement pourrait aussi être une suite déterminée, si on considérait effectivement l'ensemble des huit générateurs mwc. 2771237 On remarquera que pour déterminer le premier élément d de la suite d'indices des générateurs mwc de chiffrement, on part de la valeur d'un des générateurs d'une itération précédente et on en extrait une série de bits quelconques qu'on pondère par une série de multiplicateurs dont la somme est égale à 7 (q - 1), pour que la probabilité de prendre l'un quelconque des générateurs mwc soit la même pour tous les huit (q). Dans l'exemple considéré, o q = 8, la série de multiplicateurs 4, 2, 1 est la meilleure pour i'équidistribution. 5.- On a vu qu'au moment de l'avance du chiffreur, à chaque itération, on fait avancer l'un des générateurs mwc différemment des autres, en l'espèce, en le faisant avancer de deux rangs. Il s'agit alors d'une combinaison non linéaire de générateurs mwc. 6.- Dans l'exemple considéré, on a déterminé la sortie du chiffreur (le premier mot de la fifo ou cmb) en fonction de la valeur de lea8, bit du leader. Il est clair qu'on aurait pu considérer un bit de la valeur d'un autre générateur mwc d'une itération précédente. 7.- La clé d'initialisation sert à l'initialisation des générateurs mwc. 8.- Dans l'exemple considéré, la détermination de cmb dépend des valeurs de lea9 et lea12. On aurait pu aussi proposer de la déterminer à partir des valeurs de certains bits de la valeur d'un autre générateur mwc d'une itération précédente. 9.- Dans le système à base 216 (p = 16) et en considérant 8 (q = 8) générateurs mwc, on a proposé d'utiliser une clé de 128 bits ou 248 bits. Une clé de 128 bits est donc une clé de qp bits, une clé de 248 bits, une clé de qp+q(p-1) bits. 10.- Chaque bit du leader n'intervient qu'une fois dans chaque itération. lh l 2771237 REVENDICATIONS 1.- Procédé de chiffrement de données claires, dans lequel, - dans un système à base 2p, - on découpe les données en une suite de blocs de p bits, - on considère une fonction de chiffrement d'une pluralité q de paramètres constitués de générateurs mwc et on en détermine une séquence pseudoaléatoire de valeurs itératives de p bits et - on soumet deux à deux les blocs de données de ladite suite et les valeurs de chiffrement de ladite séquence à l'une des opérations du groupe comprenant l'opération logique ( et les opérations arithmétiques + et -. 2.- Procédé selon la revendication 1, dans lequel, dans la fonction de chiffrement, les générateurs mwc sont respectivement introduits alternativement par l'opération D et l'opération +. 3.- Procédé selon l'une des revendications 1 et 2, dans lequel les indices des générateurs mwc de la fonction de chiffrement constituent une suite déterminée de q indices. 4.- Procédé selon l'une des revendications 1 et 2, dans lequel les indices des générateurs mwc de la fonction de chiffrement constituent une suite pseudoaléatoire de g indices (g 5.- Procédé selon la revendication 4, dans lequel le premier indice de la suite pseudoaléatoire des indices des générateurs mwc de chiffrement est déterminée à partir de la valeur d'un des générateurs mwc d'une itération précédente dont on extrait une série de bits qu'on pondère par une série de multiplicateurs. 6.- Procédé selon l'une des revendications 1 à 5, dans lequel lesdits générateurs mwc constituent une combinaison non linéaire. 7.- Procédé selon l'une des revendication 1 à 6, dans lequel, avant de chiffrer les données claires, on procède à une série d'avances de divergence des générateurs mwc. 12 2771237 8.- Procédé selon l'une des revendications 1 à 7, dans lequel, après avoir déterminé chacune desdites valeurs itératives, on l'écrit dans le deuxième élément d'une mémoire fifo à deux éléments, le mot de ce deuxième élément devenant celui du premier élément, et on soumet à ladite opération, comme sortie du chiffreur, soit le mot du premier élément de la mémoire fifo, soit la valeur itérative déterminée. 9.- Procédé selon la revendication 8, dans lequel on détermine la sortie du chiffreur en fonction de la valeur d'un des bits de la valeur d'un des générateurs mwc d'une itération précédente. 10.- Procédé selon l'une des revendication 1 à 9, dans lequel on initialise les générateurs mwc par une clé d'initialisation. 1.- Procédé selon la revendication 10, dans lequel la clé d'initialisation est une clé de qp bits. 12.- Procédé selon la revendication 10, dans lequel la clé d'initialisation est une clé de [qp + q(p-1)] bits. 13.- Procédé selon l'une des revendications 1 à 12, dans lequel, à la fin d'une itération, l'un des générateurs mwc, avant qu'il ne soit avancé, est modifié dans son reste et sa retenue. 14.- Procédé selon l'une des revendications 1 à 13, dans lequel chaque valeur itérative de ladite fonction de chiffrement dépend des valeurs de certains bits de la valeur d'un des générateurs mwc d'une itération précédente. 15.- Procédé selon l'une des revendications 1 à 14, dans lequel p = 16. 16.- Procédé selon l'une des revendications 1 à 15, dans lequel q = 8. 17.- Procédé selon les revendications 5 et 16, dans lequel on considère, pour ladite série de multiplicateurs, la série 4, 2, 1.