Brevet FR2950715A1 — publié le 20110401

DISPOSITIF DE CALCUL POUR LA GENERATION OPTIMISEE D'APPLICATIONS AFFINES La présente invention concerne un dispositif de calcul optimisé pour la génération et la tabulation d'applications affines. Elle propose une solution permettant, par le biais d'un dispositif électronique tel qu'un composant à logique programmable ou un circuit intégré reconfigurable ou non, de générer avec une complexité de calcul optimale, des applications affines de la forme m(x)=Rx+r ainsi que leurs inverses, où x et r sont des vecteurs ~o binaires et R est une matrice binaire inversible. Ce type de calcul est nécessaire dans des applications diverses, notamment dans le cas de composants cryptographiques qui implémentent des solutions de protection de données secrètes. Une application affine peut 15 être notamment utilisée comme solution de masquage de variables sensibles dans un algorithme de chiffrement de données. L'invention s'applique en particulier, mais pas exclusivement, pour des dispositifs qui embarquent un circuit intégré contenant des données confidentielles tels qu'une carte à puce. L'invention s'applique également pour tout type de dispositif de calcul 20 nécessitant l'utilisation d'applications affines. A cet effet, les solutions de l'art antérieur connues ne permettent pas d'implémenter un tel calcul de façon optimisée sur un processeur limité en capacité de traitement qui exécute déjà par ailleurs d'autres fonctionnalités. La présente invention propose ainsi une solution permettant de générer avec un coût optimal l'ensemble des fonctions affines de type m(x)=Rx+r où r et x sont des vecteurs binaires quelconques et R est une matrice binaire inversible également quelconque. 25 30 A cet effet, l'invention a pour objet un dispositif de calcul pour la génération d'applications affines définies par une relation de type m(x)=Rx + r, x et r étant des vecteurs binaires de taille n, R étant une matrice binaire inversible à n lignes et n colonnes, ledit dispositif étant caractérisé en ce qu'il exécute au moins les étapes de calcul suivantes : o générer ledit vecteur binaire aléatoire r de taille n, o générer ladite matrice binaire inversible aléatoire R, o générer une table de correspondance T[x] de l'application m(x) à l'aide des étapes de calcul suivantes 0 T[0]=r g=O pour i variant de 1 à 2"-1, g'=g+2Gi T[g']=T[g] $ RGi 15 g=g' où RG; est la colonne d'indice G; de la matrice R et G; est l'indice de la position du bit modifié entre les mots de code de Gray g; et g;_ 1, G; = log2(g;_i ED g;) pour i variant de 0 à 2"-1, où m est l'opération ou exclusif et loge désigne la fonction logarithme en base 2. 20 o pour une valeur x donnée, fournir le résultat de l'application affine définie par m(x)=Rx+r en délivrant la valeur tabulée T[x]. Dans une variante de réalisation de l'invention, ledit dispositif de calcul exécute en plus l'étape de calcul suivante permettant de générer la table de correspondance S[x] de l'inverse de l'application m(x) : 25 o Pour tout vecteur binaire x de taille n, S[T[x]]=x. Dans une variante de réalisation de l'invention, ledit dispositif de calcul exécute en plus les étapes de calcul suivantes permettant de générer ladite matrice aléatoire R : o générer aléatoirement une matrice A binaire triangulaire inférieure 30 et inversible dont les colonnes sont appelées Ai pour j variant de 1 à n, o générer aléatoirement une séquence u= (ul,u2:...,un(n_1)/2) de n(n-1)/2 coefficients binaires, o déterminer la matrice R à l'aide du calcul suivant, où Ri, sont les colonnes de ladite matrice R : k=1 pour j' variant de 1 à n RR'=Ay pour j variant de 1 à j'-1 Ri' = Ri' uk. Ai k=k+1 où ® est l'opération ou exclusif. Dans une variante de réalisation de l'invention, ledit dispositif de calcul exécute en plus l'étape suivante permettant de générer ladite matrice R parmi l'ensemble des matrices binaires inversibles : o générer une matrice de permutation P à n colonnes et n lignes, o remplacer ladite matrice R par le produit matriciel de R et de P. Dans une variante de réalisation, ledit dispositif est un composant à logique programmable. Dans une variante de réalisation de l'invention, ledit dispositif met en oeuvre un algorithme cryptographique réalisant des opérations sur au moins une variable secrète x et que l'application affine m(x) = Rx+r est utilisée pour masquer ladite variable x en se substituant à elle au cours desdites opérations. D'autres caractéristiques apparaîtront à la lecture de la description détaillée donnée à titre d'exemple et non limitative qui suit faite en regard de dessins annexés qui représentent : La figure 1, un diagramme schématisant une méthode selon l'invention de génération optimale de l'ensemble des applications affines 30 T[x]=Rx+r à partir de la matrice R et du vecteur r, La figure 2, un diagramme illustrant une méthode selon l'invention de génération optimale de toute matrice R binaire inversible aléatoire pouvant être utilisée pour une application affine. La figure 1 schématise les étapes mises en oeuvre pour générer une table de correspondance T associant à tout vecteur binaire x possible, le résultat de l'application affine définie par la relation T[x] = R.x 8 r où R est une matrice binaire inversible et r un vecteur binaire. x et r sont des vecteurs binaires de taille donnée égale à n, n étant un entier strictement positif. R est ~o une matrice à n colonnes et n lignes binaires et inversibles. Par binaire, on entend que les vecteurs x et r ainsi que la matrice R ne contiennent que des 0 et des 1. La méthode proposée consiste à générer la table T[x] de façon optimisée afin d'éviter pour chaque valeur de x, d'effectuer le calcul matriciel 15 complexe consistant à multiplier la matrice R par le vecteur x et à additionner au résultat l'aléa r. En effet, un des buts de l'invention est de proposer une solution qui soit peu complexe à implémenter sur un circuit intégré à ressources limitées. La table de correspondance T[x] possède un nombre de lignes égal à n et un 20 nombre de colonnes égal à 2n, n étant la taille du vecteur x d'entrée. Dans une première étape 111, la première colonne de la table de correspondance est initialisée avec le vecteur binaire 101 r, T[0]=r. L'ensemble des valeurs que peut théoriquement prendre la variable x est égal à l'ensemble des vecteurs binaires de taille n. Une possibilité 25 permettant de lister l'ensemble de ces valeurs est d'utiliser le principe connu de l'Homme du métier du codage de Gray. Ce codage permet de représenter l'ensemble des vecteurs binaires ou mots de code de taille n donnée en ne modifiant qu'un seul bit à la fois entre deux vecteurs consécutifs. On note gi le i-ème mot de code de Gray pour i variant entre 0 et 2n -1. La 30 nature même du codage de Gray implique qu'il n'y a qu'un seul bit dont la valeur change entre le mot de code g;_1 et le mot de code g. A partir de la valeur connue du mot de code g, une deuxième étape de calcul 112 met en oeuvre le calcul optimisé de la table de correspondance T pour toutes ses valeurs. On note G; la position du bit dont la valeur est modifiée entre le mot de code et le mot de code g. Cette position peut être calculée à l'aide de la relation suivante : Gi =1og2 (gi_1 g,) (1) en utilisant les valeurs numériques des mots de code binaires g;_, et g. Ainsi, g;_.1 et g; sont reliés par la relation g, = gd-1 m 2G' (2) La table de correspondance T est ensuite remplie pour i variant de 1 à 2n -1 à l'aide du procédé récursif suivant : T[gi ] = T[gf-i ] Q Rc; (3) où Ra est la colonne d'indice G; de la matrice R. 15 La table 104 T est ainsi calculée pour l'ensemble des valeurs de x possibles en offrant une complexité d'implémentation faible. La table de correspondance S[x] associant à tout vecteur binaire x le résultat de l'application inverse m"1(x) peut être générée conjointement en 20 exécutant la relation suivante pour tout x : S[T[x]] = x (4) La construction d'applications affines par le biais de la méthode présentée à l'appui de la figure 1 nécessite comme point d'entrée une 25 matrice R binaire inversible et aléatoire. A cet effet, l'invention propose une méthode permettant de déterminer l'ensemble des matrices R possibles avec une complexité de calcul optimale. Le procédé utilise la réciproque de la méthode de décomposition LU connue de l'Homme du métier qui consiste à décomposer toute matrice A en 10 un produit d'une matrice triangulaire inférieure L et d'une matrice triangulaire supérieure U. A=LU (5) Les matrices A=LU sont uniformément distribuées lorsque L et U sont générées aléatoirement, c'est-à-dire que pour toute matrice A, il existe un unique couple (L,U) tel que A=LU. Cette affirmation est démontrée à l'aide des trois lemmes suivants. Lemme 1 : Si L est une matrice binaire inversible triangulaire inférieure, alors son inverse L-' l'est également. En effet, si sont les coefficients de la matrice L 1, Li est la colonne d'indice j de la matrice L et comme le produit de L et L"" est égal à la matrice identité I alors on en déduit que 15 E = (1,0,..., 0) et donc que 11=0 pour tout j > 1. i=l n De la même façon on démontre que E l2iL = (0,1,..., 0) et donc que 12;=O i=1 pour tout j > 2 et de façon générale, pour tout i, I;i=O pour j > i, ce qui montre bien que la matrice L"' est également triangulaire inférieure. 20 Lemme 2 : Si LU = I avec L une matrice inversible triangulaire inférieure et U une matrice inversible triangulaire supérieure alors L = I et U = I . En effet, comme L =U-1 , à l'aide du lemme 1 on sait que U"' est une matrice inversible triangulaire supérieure, L et U"' ne peuvent donc qu'être égales à la matrice identité I . 25 Lemme 3 : Si L et L' sont deux matrices binaires triangulaires inférieures alors le produit L.L' est également une matrice binaire triangulaire inférieure. Supposons maintenant qu'il existe deux couples de matrices triangulaires inférieures et triangulaires supérieures (L,U) et (L',U') différentes et telles que LU = L'U' . Dans ce cas on aurait également L'L'U'U-' = I . A partir des lemmes 2 et 3 on en déduit alors que L-'L'= I et U'U-' = I ou encore L = L' et U = U' ce qui prouve donc bien que pour toute matrice A inversible, il existe un unique couple de matrices (L,U) tel que A=LU. La figure 2 schématise les étapes de mise en oeuvre de la génération ~o optimisée de l'ensemble des matrices inversibles binaires de la forme A'=AU. Dans une première étape le procédé consiste à générer aléatoirement 201 une matrice triangulaire inférieure inversible A ayant n lignes et n colonnes et dont les colonnes sont notées Aj pour j variant de 1 à n. Dans une seconde étape, on génère aléatoirement 202 une séquence 15 binaire uk de longueur n(n-1)12 et on note U la matrice suivante : 1 u, Lis un(nù3)+2 2 0 1 u3 0 0 1 . L'invention consiste alors à générer de façon optimisée le produit A' des 20 deux matrices A et U. Pour ce faire, une variable k est initialisée à 1 lors d'une étape d'initialisation 211 du calcul. Ensuite, pour tout indice j' variant de 1 à n, les colonnes A'i, de la matrice A' sont initialisées avec les colonnes Agi, de la matrice A lors d'une étape 212a. Ensuite l'algorithme suivant est mis en œuvre au cours d'une étape 212b pour tout indice j variant de 1 à j'-1 : (6) k=k+1 (7) L'algorithme exécuté lors des étapes 212a et 212b peut être résumé par le pseudo code suivant : k=1 Pour j'=1 à n A'i,=Ay Pour j=1 à j'-1 A'j,=A'j'O+ukAJ k=k+l Fin Io Fin La matrice A' 203 est ainsi générée avec une complexité amoindrie par rapport à un calcul matriciel classique et est utilisée pour construire la fonction affine m(x) = R.x r, où la matrice R est ici égale à la matrice A'. 15 En utilisant cette méthode une économie substantielle est ainsi réalisée, en effet il est nécessaire de générer initialement n(n-1) bits aléatoires alors que la génération directe de la matrice R nécessiterait en moyenne, environ 3n2 bits aléatoires. Le facteur 3 s'explique par le fait que la probabilité de tirer une matrice inversible binaire parmi l'ensemble des 20 matrices binaires est d'environ 1 /3 lorsque 5 Le dispositif de calcul selon l'invention peut notamment être utilisé dans le cadre d'applications de cryptographie comportant des données secrètes que l'on souhaite masquer en remplaçant, dans toutes les opérations où ces données interviennent, leur valeur par une fonction affine de cette même valeur. Il est possible de démontrer que la quantité d'aléa et la complexité binaire de cette méthode selon l'invention sont optimales pour définir l'image d'une application affine inversible aléatoire ainsi que celle de son inverse en utilisant : n(n-1) bits aléatoires, n(n+1 )/2+2" opérations « ou exclusif » sur des octets. Au contraire la méthode « classique » de l'art antérieur nécessite : 15 3n2 bits aléatoires en moyenne, 3n2+n2n opérations « ou exclusif » sur des octets. Par exemple, lorsque n=8, la méthode classique de l'art antérieur nécessite 192 bits aléatoires (en moyenne) et 2240 opérations « ou 20 exclusif », alors que l'invention permet d'utiliser seulement 28 bits aléatoires et 292 « ou exclusif ». De plus, les tests d'inversibilité sont très coûteux puisque d'autres opérations, notamment pour obtenir la valeur d'un bit dans un octet, et de nombreux tests sont nécessaires. 25 Le dispositif selon l'invention permet ainsi de générer avec un coût de calcul optimal l'ensemble des applications affines du type m(x)=Rx+r pour des variables x binaires vectorielles de taille donnée. Le gain de complexité obtenu est avantageux pourdes dispositifs dont les ressources sont soit limitées soit déjà allouées à une autre application principale, comme cela est 30 le cas pour un dispositif cryptographique. REVENDICATIONS1. Dispositif de génération d'applications affines pour le traitement cryptographique de données x, tel que le masquage par substitution, lesdites applications affines m(x) étant reliées aux dites données x par la relation m(x)=Rx + r, où lesdites données x sont représentées sous forme d'un vecteur binaire de taille n, r est un vecteur binaire de taille n et R est une matrice binaire inversible à n lignes et n colonnes, ledit dispositif étant caractérisé en ce qu'il comporte des moyens adaptés à exécuter les étapes suivantes : o générer ledit vecteur binaire aléatoire r de taille n, o générer ladite matrice binaire inversible aléatoire R, o générer une table de correspondance T[x] de l'application m(x) à l'aide des étapes de calcul suivantes : T[0]=r g=0 pour i variant de 1 à 2n-1, g'=g+ 2G' T[g']=T[g] O+ Ra g=g' où RG; est la colonne d'indice G; de la matrice R et G; est l'indice de la position du bit modifié entre les mots de code de Gray g; et g;_ , G; = log2(gi_1 g;) pour i variant de 0 à 2n-1, où e est l'opération ou exclusif et loge désigne la fonction logarithme en base 2. o pour une valeur x donnée, fournir le résultat de l'application affine définie par m(x)=Rx+r en délivrant la valeur tabulée T[x]. 2. Dispositif selon la revendication 1 caractérisé en ce qu'il comporte des moyens adaptés à exécuter en plus l'étape de calcul suivante permettant de générer la table de correspondance S[x] de l'inverse de l'application m(x) :o Pour tout vecteur binaire x de taille n, S[T[x]]=x. 3. Dispositif selon l'une des revendications 1 à 2 caractérisé en ce qu'il comporte des moyens adaptés à exécuter en plus les étapes de calcul suivantes permettant de générer ladite matrice aléatoire R : o générer aléatoirement une matrice A binaire triangulaire inférieure et inversible dont les colonnes sont appelées Ai pour j variant de 1 à n, o générer aléatoirement une séquence u= (u1,u2,...,un(n_1)/2) de n(n-1)/2 coefficients binaires, o déterminer la matrice R à l'aide du calcul suivant, où Ri, sont les colonnes de ladite matrice R : k=1 pour j' variant de 1 à n Ri,=Ai, pour j variant de 1 à j'-1 R~ =Ri,10Uk.Ai k=k+1 où O+ est l'opération ou exclusif. 4. Dispositif selon la revendication 3 caractérisé en ce qu'il comporte des moyens adaptés à exécuter en plus l'étape suivante permettant de générer ladite matrice R parmi l'ensemble des matrices binaires inversibles : o générer une matrice de permutation P à n colonnes et n lignes, o remplacer ladite matrice R par le produit matriciel de R et de P. 5. Dispositif selon l'une des revendications précédentes caractérisé en ce que ledit dispositif est un composant à logique programmable.