Brevet FR2916064A1 — publié le 20081114

Procédé de génération de chaînes de bits pseudo-aléatoires notamment pour la protection de la confidentialité de données L'objet de l'invention concerne un procédé pour générer des caractères pseudo-aléatoires ou des chaînes de bits pseudo-aléatoires. Il est par exemple utilisé pour la protection de la confidentialité de données. L'invention s'applique, par exemple dans le domaine de la cryptographie. En particulier, elle se rapporte aux procédés cryptographiques de protection de la confidentialité des échanges de données entre deux applications. Elle est utilisée dans tous les systèmes de codage/décodage de données qui nécessite de protéger les échanges de données. Elle peut être utilisée dans le domaine de l'authentification d'utilisateurs ou 10 de données. A l'heure actuelle, la propriété de confidentialité peut être obtenue selon différents procédés, s'inspirant tous d'un même principe. En considérant un canal de communication supposé non sécurisé entre deux applications 15 notées A et B, et en supposant que A souhaite envoyer des données confidentielles à une application B via ce canal de communication, pour ce faire, l'application A doit masquer les données, puis les transmettre à l'application B. Afin que l'application soit en mesure de récupérer les données d'origine à partir des données masquées, il faut que l'application A 20 ait utilisé un procédé de masquage qui soit facilement inversible pour B et ceci uniquement pour B, et éventuellement A, afin que toute autre personne ne puisse prendre connaissance des données. Pour obtenir une telle technique de masquage, la cryptographie distingue deux approches différentes : la cryptographie à clé publique, appelée aussi cryptographie 25 asymétrique, et la cryptographie à clé secrète, appelée aussi cryptographie symétrique. Dans chacune de ces méthodes, les données sont représentées sous forme d'une chaîne de caractères, les caractères généralement utilisés étant des caractères 0, 1 alors appelés bits. La cryptographie à clé publique repose sur le fait que l'application B dispose d'une paire de clé notée (P, S) telle que : • P est une valeur connue de tout le monde et est appelée clé publique, • S est une valeur connue uniquement par l'application B et est appelée 5 clé privée, Les valeurs de P et S sont reliées par une relation mathématique telle qu'il est difficile de retrouver S à partir de la simple connaissance de P. Ainsi, seule l'application B est à même de connaître la valeur S. En cryptographie à clé publique, l'application A utilise la clé publique P de 10 l'application B pour coder les données. Dans ce contexte, il est nécessaire de disposer de la clé privée pour pouvoir décoder les données. Ainsi, seule l'application B est à même de connaître la valeur S. La cryptographie à clé secrète repose, quant à elle, sur le fait que l'application A et l'application B disposent d'une même valeur S connue 15 d'elles seules. La valeur S est appelée clé secrète. Ainsi, l'application A utilise la valeur S pour coder les données de sorte que la connaissance de S soit nécessaire pour décoder les données codées. L'application B est alors la seule, avec l'application A, à pouvoir déchiffrer, ce qui garantit bien la confidentialité des données. 20 La protection de la confidentialité dans le contexte de la cryptographie à clé secrète (cryptographie symétrique) est généralement appelée méthode de chiffrement symétrique. II existe deux catégories de méthodes de chiffrement. La première est appelée chiffrement à flot et la seconde est appelée chiffrement par bloc. En chiffrement à flot, les différents caractères 25 représentant la donnée sont codés successivement un à un. En chiffrement par bloc, la chaîne de caractères représentant la donnée est découpée sous forme de plusieurs blocs consécutifs de caractères et ces blocs, tous de même taille, sont ensuite codés successivement. A chaque codage d'un bloc, plusieurs caractères sont donc codés simultanément. 30 Il existe de nombreuses méthodes de chiffrement par bloc. Toutes ces solutions reposent sur l'utilisation d'une primitive cryptographique. Une primitive cryptographique f est une application prenant en entrée une chaîne notée m de n caractères et une chaîne notée K de k caractères. En sortie, la primitive f fournit une chaîne de N caractères notée C vérifiant C= f( m , K), avec N non nécessairement égal à n. Chaque choix d'une entrée K définit une application fK telle que fK( m) = f(m, K). L'entrée K est appelée clé secrète. La présente invention se rapporte, notamment, au cas où la primitive cryptographique f définit, pour chaque valeur K possible, une fonction bijective fK (en particulier n=N). L'application fK ainsi obtenue est également appelée permutation (terme préférentiellement utilisé dans la présente description). Ainsi, chaque clé secrète K définit une permutation fK. En pratique, la primitive f pourra être l'AES ou le DES. Pour coder un bloc m contenant n caractères, il suffit d'utiliser une fois la fonction fK. Par exernple, on pourra envisager que le codé, noté C, du bloc m soit calculé par C= f ). En pratique, la donnée confidentielle ne contiendra pas un unique bloc, mais au contraire s'écrira comme la suite de b blocs notés mi, ..., mb. II devient important de savoir comment coder ces b blocs. En s'inspirant du calcul C= fK(m), il est possible d'envisager que les différents blocs m;, 1 i b, soient codés en des blocs notés 1 i b, vérifiant C; = fK(m,). Spécifier comment coder plusieurs blocs d'un même message consiste à définir un mode opératoire. Celui défini ci-dessus et consistant à coder chaque bloc indépendamment les uns des autres en les passant comme entrée de la permutation fK est le mode ECB. La sécurité de ce mode n'est pas très élevée. Le problème de ce mode est qu'un bloc m;, quelle que soit sa position dans le message sera toujours codé par la même valeur C;. Cela pose un réel problème en pratique. II existe un grand nombre de modes opératoires, certains étant standardisés par le NIST [NIS01]1. Différents critères existent pour juger de la qualité de ces modes. Les deux principaux sont le niveau de sécurité de ce mode et le coût calculatoire engendré par ce mode. 4 La sécurité d'un mode opératoire représente le fait qu'il soit difficile de décider si une chaîne de caractères donnée est le résultat du codage d'une donnée via ce mode opératoire, ou si au contraire cette chaîne de caractères est une chaîne de caractères pris au hasard. Si une telle distinction est difficile, alors il est raisonnable de penser que ce mode opératoire est relativement sûr. Toutefois, cette sécurité ne peut être garantie que lorsque le nombre de blocs codés par le mode opératoire choisi reste inférieur à une constante (dépendante du mode). Cette constante s'exprime généralement sous la forme 2' avec n la taille du bloc et a une valeur comprise entre 1/2 et 1. La valeur a sera généralement appelée seuil de sécurité. Le coût calculatoire représente le nombre d'appels à la primitive cryptographique pour coder un message de b blocs. Le coût calculatoire idéal est b appels à la permutation fK (c'est le cas du mode ECB). La sécurité du mode est en partie associée à la valeur a. Bien évidemment, plus la valeur a est grande, plus la valeur 2' est grande et plus longtemps le mode reste sûr. Dans le tableau suivant, un rappel est donné pour la sécurité des modes standardisés par le NIST. II est également précisé si le modèle de sécurité associé est élevé (ce qui est préférable) ou au contraire faible (ce qui est plutôt pénalisant). Les arguments formels de sécurité peuvent être trouvés dans [BDJR97] et [SLLLY01]. Mode Constante associée à la sécurité Référence pour la sécurité opératoire ECB [NIST01] 1/2 (modèle de sécurité faible) [BDJR97] CFB [NIST01] Y2 (modèle de sécurité élevé) [SLLLY01] OFB [NIST01] 1/2 (modèle de sécurité élevé) [SLLLY01] CBC [NIST01] 1/2 (modèle de sécurité élevé) [BDJR97] CTR [NIST01] 1/2 (modèle de sécurité élevé) [BDJR97] Les solutions existantes (et standardisées) ont une sécurité ne dépassant pas le seuil Y2. L'art antérieur divulgue trois propositions permettant d'aller éventuellement au-delà du seuil de sécurité Y2. Les deux premières [KN000] et [ABAGO1] ont 5 été fournies avec une preuve de sécurité quasiment inexistante pour la première et dans un modèle faible pour la seconde de sorte qu'il n'est pas possible de savoir si ces modes ont effectivement une constante supérieure à %2. La troisième solution [IWA06] parvient quant à elle à atteindre le seuil de sécurité 2/3 avec une preuve de sécurité complète et dans un modèle de sécurité élevé. Cette dernière proposition dispose également d'un coût calculatoire proche du coût calculatoire idéal (quasiment similaire au coût du mode ECB). La présente invention concerne un procédé de génération de chaînes de caractères pseudo-aléatoires à partir d'une application, par exemple une permutation fK, d'une valeur initiale x et de coefficients a;. La présente invention peut en particulier être utilisée pour le chiffrement par bloc. L'objet de l'invention concerne un procédé pour générer des chaînes de bits dans un système dans lequel les échanges de données entre un premier utilisateur et un deuxième utilisateur sont protégés caractérisé en ce qu'il comporte au moins les étapes suivantes : • utiliser une application fK de taille de sortie n bits, • déterminer une valeur x et à partir de cette valeur x et en appliquant 25 l'application fK, générer t valeurs v;, • à partir des t valeurs v; et de u*t coefficients déterminer u blocs Si contenant des caractères pseudo-aléatoires. Selon un mode de réalisation, l'objet de l'invention concerne un procédé pour générer des chaînes de bits pseudo-aléatoires, au sein d'un système 30 comprenant un module de codage de données, telles qu'un message de b= f*u*n + q bits, où f et u sont supérieurs ou égaux à 0, et q est compris entre 0 et u*n, peut se mettre sous la forme de f groupes de u blocs de n bits et d'un (f+1)ième groupe de q bits caractérisé en ce que : le codage d'un groupe considéré de u blocs comporte au moins les étapes suivantes : • pour le groupe considéré choisir une valeur initiale x, • à partir des t valeurs v; générées et de u*t coefficients déterminer u blocs Si contenant des caractères pseudo-aléatoires afin de coder les u blocs du groupe considéré, • combiner les u blocs du groupe considéré avec les u blocs Si afin d'obtenir le groupe codé, • réitérer ces trois étapes pour les f groupes, pour le (f+1)ième groupe de q bits, • choisir une valeur initiale de x, • à partir des t valeurs v; générées et de u*t coefficients déterminer un nombre de blocs Si égal au moins à la partie entière supérieure de pin, • combiner q bits extraits des blocs Si déterminés avec les q bits du (f+1)ième groupe. L'invention est, par exemple, utilisée dans des applications d'authentification. Un des avantages de la présente invention est qu'elle permet de construire de nouvelles fonctions pseudo-aléatoires qui ont une sortie de taille supérieure à n. Généralement, les constructions existantes ont une sortie uniquement de n bits tout en utilisant plusieurs fois la permutation fK. Ces constructions ont donc un rendement très faible (au mieux, elles manipulent deux fois l'algorithme bloc pour sortir n bits, le rendement étant alors de '/2, ce qui en pratique n'est pas acceptable). La présente invention utilise plusieurs fois la permutation fK, mais pour générer u blocs de n bits. De plus, le rendement obtenu est quasiment égal à 1. D'autres caractéristiques et avantages apparaîtront à la lecture de la description détaillée donnée à titre d'exemple et non limitative qui suit faite en regard des figures qui représentent • La figure 1, un exemple d'échanges de données de manière sécurisée 5 entre un serveur bancaire et un utilisateur, • La figure 2, un exemple d'utilisation du procédé selon l'invention dans un système d'authentification. L'un des buts de l'invention est de créer de nouvelles fonctions pseudo-10 aléatoires, en utilisant, notamment, des permutations dont la sortie est un bloc de n bits; la sortie de la nouvelle fonction étant de taille égale à un multiple de n bits, notée u*n bits. Le principe de l'invention consiste, notamment, à considérer t appels à l'algorithme bloc afin d'obtenir t chaînes de n bits qui seront alors organisées 15 de manière adéquate selon des coefficients fournis en paramètre pour obtenir les u Comme il a été précédemment annoncé, de telles fonctions peuvent être également utilisées pour définir de nouveaux modes opératoires, tels que leur sécurité soit identique à la sécurité de la fonction sous- jacente utilisée. Ainsi, en utilisant les fonctions pseudo-aléatoires paramétrées par des matrices de codes linéaires obtenues par la présente invention, il est possible d'obtenir des modes opératoires avec un niveau de sécurité égal à d/d+1, où d est la distance du code linéaire utilisé. En particulier, en utilisant des codes linéaires de distance supérieure ou égale à 3, il est alors possible d'obtenir des modes opératoires ayant une sécurité très élevée, non décrite dans l'art antérieur. Selon un exemple de mise en oeuvre, le procédé selon l'invention concerne un procédé de génération de chaînes de caractères pseudo-aléatoires à partir d'une permutation fK, d'une valeur initiale x et de coefficients a;. La présente invention peut en particulier être utilisée pour coder un message découpé en bloc. Dans un tel contexte, deux considérations sont possibles. • Si l'on souhaite coder u blocs d'un message, il est alors suffisant de disposer (en plus de la valeur initiale et de la permutation) de u*t 20 coefficients a; pour une valeur t 1 quelconque. • Si l'on dispose de la donnée de u*t, t 1 coefficients a; (en plus de la valeur initiale et de la permutation), il est alors possible de coder u blocs. Les u*t coefficients sont répartis en u séquences de t valeurs. Pour plus de 25 clarté, cette répartition peut être représentée sous la forme d'une matrice contenant u lignes et t colonnes comme décrite ci-dessous. La représentation sous forme matricielle est utilisée à titre illustratif, afin d'améliorer la compréhension de l'exemple donné pour illustrer le procédé, mais n'est en aucun cas indispensable pour le bon fonctionnement de 3o l'invention. a1, 1 a1,2 a1,3 a1,t a2,1 a2,2 a2,3 a2,t au-1,1 au-1,2 au-1,3 au-1,t au,1 au,2 au,3 au,t Selon l'invention, la donnée initiale x peut être une valeur stockée dans 10 l'application, ou une valeur issue d'un processus aléatoire ou pseudoaléatoire ou déterministe. A partir de cette valeur x, il est possible de générer t valeurs, représentées à titre d'exemple dans la présente description sous la forme d'une suite v contenant t valeurs notées 1 i t. Un exemple pour v est : / 15 v = (v1= fK(x+1 ), v2= fK(x+2), v3= fK(x+3), ... , vt-1= fK(x+t-1 ), vt= f, 25 D'autres exemples sont choisis parmi la liste non exhaustive suivante : • g,(fK ,x) = fK(x + i ù 1), • gi(fK ,x) = fK( L'(x)) où L' correspond à la sème itération d'un LFSR ou d'un registre diviseur, • g,(fK ,x) = fK( a;x + b;) où a; et b; sont des coefficients d'une 30 transformation affine, • g,(fK ,x) = fK( a;x + b; mod 2n) où a; et b; sont des coefficients d'une transformation affine, • g,{fK ,x) = fK(x + i) +O d1, où O+ représente l'opération de xor bit à bit et d; est une chaîne de bits, • g,(fK ,x) = fK(x + i ù 1) d;, où e représente l'opération de xor bit à bit et d; est une chaîne de bits, • g,{fK ,x) = fK( L'(x)) +O di, où L' correspond à la sème itération d'un LFSR ou d'un registre diviseur, O+ représente l'opération de xor bit à bit et d; est une chaîne de bits. A partir des t valeurs notées v;, 1 Selon l'invention, pour coder feu blocs, il suffit d'itérer le processus décrit précédemment f fois. Chaque itération nécessite les paramètres suivants : • la donnée d'une valeur initiale x, • la donnée de u*t coefficients, • la donnée de la permutation fK ou d'une application choisie. Selon l'invention, si l'application y voit un intérêt, elle pourra coder b blocs d'un message, b quelconque, en considérant b=u1 + u2 + ... + us et coder les ul blocs selon le procédé décrit dans la présente description, puis les u2 blocs avec une nouvelle itération du procédé et ainsi de suite, les différentes valeurs ul, u2, ..., us pouvant être différentes les unes des autres, ou certaines égales, ou encore toutes égales. A chaque itération du procédé de génération de chaînes pseudo-aléatoires, l'application pourra choisir de conserver tout ou partie des paramètres de précédentes itérations ou au contraire d'utiliser des paramètres tous différents. Premier exemple de mise en oeuvre de l'invention Supposons la donnée d'une valeur initiale x, d'une permutation fK et de la suite de coefficients présentée sous la forme de la matrice u*u (t = u). 1 00 000 01 0 000 001 000 000 1 00 0 0 0 0 1 0 0 0 0 0 0 1 30 12 En considérant la donnée de t valeurs vi obtenues par v; = fK(x + i ù 1), pour tout i, 1 i t=u, l'opérande e sera à tout moment de l'itération le ou exclusif bit à bit et l'opérande O sera la multiplication par 0 ou 1 (les valeurs des coefficients) comme défini précédemment. Soit un message de b bits, b égal à f*u*n + q bits avec f et u supérieurs ou égaux à 0, et q supérieur ou égal à 0 et strictement inférieur à u*n, devant être codé. La suite de coefficients et la permutation fK seront, par exemple, constantes à chaque itération, et la valeur initiale sera x pour la première itération, puis x+t pour la seconde, puis x+2t pour la troisième et plus généralement x+(i-11)*t pour la 1ème itération. Les u premiers blocs de n bits, ceux du premier groupe, seront codés grâce à la première itération (avec x comme valeur initiale) de la présente invention. Pour tout i, 1 i u, le codage du bloc i noté m; s'obtient alors par l'application de la formule Si =(ai,1 O v1) O+ (ai,2 O v2) +0 (a1,3 O v3) O ... (ai,1 O vt) Ci ==m10+ Si Or, tous les coefficients de la ligne i de la matrice sont nuls, sauf le /eme (matrice indentité). Par conséquent, Si se réduit à Si = ai,i 0 vi = vi = fK(x+1-1) de sorte que C; =mi O+ Si = mi +O fK(x+ i - 1). Lors de la seconde itération de l'invention, pour le codage du second groupe de u blocs de n bits, les u blocs mä +; suivants, 1 i u, seront codés en calculant S;==a,,10 vi = vi = fK(x + u + i ù 1 ) 25 de sorte que Cä+;=mu+i 0+ Si=m;O+ fK(x +u+iù1). Les deux itérations peuvent s'exprimer sous la forme commune suivante. Pour tout i, 1 Les derniers q bits, notés sous la forme d'un unique bloc m ä•f+1 seront codés en générant suffisamment de blocs Si pour pouvoir en extraire q bits, afin de former le bloc S'u*f+1. Le (f+1)ième groupe est codé en un groupe C'ä*f+1 _ m u•f+1 O+ S u*f+1. Second exemple d'application En supposant la donnée d'une valeur initiale x, d'une permutation fK et de la suite de coefficients présentée sous la forme de la matrice u*(u+1) (t = u+1). 1 1 00.... 000 1 01 0.... 000 15 1 001 .... 000 1 000....1 00 1 000....01 0 1 0 0 0 .... 0 0 1 20 En considérant la donnée de valeurs v; obtenues par v; = fK(x + i ù 1), pour tout i, 1 i t = u + 1. L'opérande +O sera à tout moment de l'itération le ou exclusif bit à bit et l'opérande O sera la multiplication par 0 ou 1 (les valeurs des coefficients) comme définie précédemment. Soit un message b=f*u*n + q bits, avec f et u supérieurs ou égaux à 0, et q 25 supérieur ou égal à 0 et strictement inférieur à u*n, devant être codé. La suite de coefficients et la permutation fK seront constantes à chaque itération, et la valeur initiale sera x pour la première itération, puis x+u+1 pour la seconde, puis x+2(u+1) pour la troisième et plus généralement x + (i ù 1)*(u+1) pour la 1ème itération. Les u premiers blocs seront codés grâce à la première itération 30 (avec x comme valeur initiale) de la présente invention. Pour tout i, 1 i u, le codage du bloc i noté mi s'obtient alors par l'application de la formule S;=(a1,1Ov1)O+(a;,2O v2) O+(a1,3Ov3)+O...O+(aj,tvt) C; =m1 O+ Si Or, tous les coefficients de la ligne i sont nuls, sauf le 1 er et le (i+1)ème Par conséquent, cette formule se réduit à S,= (a;,1 O v1) O (a1,1+1 O vv+1) = v1 O v;+1 = fK(x) O+ fK(x+ iù 1) de sorte que C;=m;O+ fK(x) fK(x +iù1) Lors de la seconde itération de l'invention, les u blocs mä +; pour tout i, 1 Pour un code linéaire de distance 4, la sécurité pourra être garantie dans que le nombre de blocs codés est inférieur à 24'1/5, ce qui est supérieur à 23"i4. En résumé, et de façon générale, il est possible d'utiliser la présente invention pour générer des chaînes de bits pseudo-aléatoires, non nécessairement dédiées à la problématique du codage de message. Exemple de mise en oeuvre du procédé selon l'invention au sein d'un 30 système permettant à un utilisateur d'effectuer des transactions avec un serveur bancaire. 16 Considérons une connexion entre un serveur de banque 1 et un client 2. Ces deux entités ont pour objectif de dialoguer ensemble de façon confidentielle (demande de virement, par exemple...). Supposons que le serveur et le client disposent tous deux d'une même clé 5 secrète K de 128 bits. La présente invention permet de réaliser cette communication confidentielle. En effet, considérons que le client souhaite transmettre à la banque un ordre de virement et supposons que cet ordre soit représenté par un message électronique M de taille 8*128=1024 bits. Un tel messagepeut donc s'écrire 10 sous la forme M= m1m2m4m4m5m6m7m8 Où chaque m; représente un bloc de 128 bits. Pour transmettre son ordre de façon confidentielle, le client va utiliser le procédé selon l'invention décrit ci-dessus. Pour cela, le serveur et le client 15 conviennent alors publiquement (i.e. de façon non secrète) : • d'un algorithrne de codage par bloc utilisant des clés de 128 bits, disons l'AES. Nous noterons AES(K , t) le codage du mot de 128 bits t en utilisant la clé secrète K. • d'une suite de valeurs binaires pouvant être représentée sous la forme 20 d'une matrice G ayant 4 lignes et 5 colonnes définie par 1 0 0 0 1 G= 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 25 Dans la suite, l'opérande O représente l'opération de ou exclusif bit à bit. Cette opérande vérifie A A=0;A0+ B=BOA; (AO+B) B=AO+(B B)=AO+0=A Le client 2 choisit (étape El) ensuite une première valeur initiale x de taille 30 128 bits et applique une première fois la présente invention en utilisant G 17 pour calculer (étape E2) 4 (le nombre de lignes de G) blocs Si de 128 bits définis par S~ = AES(K, x) +C AES(K , x+4) S2 = AES(K , x+1) O+ AES(K , x+4) S3 = AES(K , x+2) C+ AES(K , x+4) S4 = AES(K , x+3) AES(K , x+4) A partir de ces quatre blocs Si,, le client peut coder (étape E3) les 4 premiers blocs du message M en 4 blocs codés c; définis par C~=mi )S,; C2=m29S2; C3=m3C) S3; C4=m4OS4 10 Ensuite, le client peut considérer une seconde valeur initiale x'. Le client peut une nouvelle fois appliquer la présente invention avec la valeur initiale x' et la matrice G représentant la suite de coefficients. Le client obtient alors 4 nouveaux blocs Si de 128 bits définis par 15 S5 = AES(K , x') C+ AES(K , x'+4) S6 = AES(K , x'+1) AES(K , x'+4) S7 = AES(K , x'+2) C+ AES(K , x'+4) S8 = AES(K , x'+3) C+ AES(K , x'+4) Le client peut alors coder les 4 derniers blocs du message M en utilisant ces 20 4 nouveaux blocs Si. En effet, le client calcule alors c5=m50S5; c6=m60S6; c7=m7Cl S7; c8 =m8 S8 Ainsi, en appliquant deux fois la présente invention, le client a été capable de coder le message M en un message codé C défini par 25 C= CI C2 C3 C4 C5 C6 C7 C8 A partir de C, il est impossible de retrouver la valeur de M sans la connaissance de la clé secrète K partagée uniquement par le serveur et le client. Le client envoie (étape E4) alors au serveur le message C ainsi que le couple (x,x') de données initiales. Lors de la réception du couple (x,x'), le serveur peut, en appliquant également deux fois la présente invention recalculer (étape E5) les valeurs S~ = AES(K , x) $ AES(K , x+4) S2 = AES(K , x+1) AES(K , x+4) S3 = AES(K, x+2) +O AES(K , x+4) S4 = AES(K, x+3) AES(K , x+4) 10 et S5 = AES(K , x') AES(K , x'+4) S6 = AES(K, x'+1) O+ AES(K , x'+4) S7 = AES(K , x'+2) AES(K , x'+4) S8 = AES(K , x'+3) O+ AES(K , x'+4) 15 et ensuite calculer ci+OS,=(m1O+SI) (SI=mi+O(SI 0 S1)=m1O+O=mi c2OS2=(m2O+S2) C+S2=m2O(S2 O+S2)=m2 O+0=m2 C3+0S3=(m3O+S3) C+S3=m3+O(S3 OS3)=m3 O+0=m3 C4OS4=(m4(D S4) O+ S4=m4+O(S4 (D S4)=m4 O+ 0=m4 20 C5+CS5=(m5(D S5) O+ S5=m5O(S5 (D S5)=m5 O+0=m5 c6OS6=(m6(D S6) O+ S6=m6+O(S6 O+S6)=m6 O+0=m6 C7 C) S7=(m7O+S7) eS7=m7C) (S7 O+ S7)=m7O0=m7 c8+OS8=(m8O+S8) C+ S8=m8O0(S8 +OS8)=m8+O0=m8 25 Le serveur a ainsi pu recalculer (étape E6) le message décodé M = m1 m 2 m 3 m4 m 5 m 6 m 7 m 8 grâce à sa connaissance de K. Le serveur connaît alors l'ordre de virement qu'il peut maintenant exécuter.5 19 Exemple d'utilisation du procédé utilisé dans un dispositif d'authentification Considérons un distributeur 3 de contenus numériques payants, disposant de différents clients. Pour qu'un client du distributeur puisse avoir accès à un contenu, il doit d'abord prouver au distributeur qu'il a le droit d'obtenir ce contenu. Pour ce faire, le distributeur fournit au client un terminal 4 et une carte à puce 5 dans laquelle se trouve : • Une zone mémoire en lecture seule, 51 contenant • Une clé secrète K connue uniquement par le distributeur (qui aura par exemple fabriqué la carte lui-même) et propre à la carte. Par exemple, nous considérons qu'il s'agit d'une clé de taille '128 bits utilisable pour I'AES. Nous noterons AES(K , t) le chiffrement du mot de 128 bits t en utilisant la clé secrète K. • u*t coefficients binaires (pouvant être identique pour chaque carte). Par exemple u=4 et t =5. On pourra supposer que ces coefficients sont représentés dans la ROM 51 sous la forme d'une matrice G de taille 4*5 définie par 1 0 0 0 1 G= 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 25 • une zone de logique câblée ou un processeur 52 capable de réaliser les calculs associés à l'invention, en particulier, capable de mettre en oeuvre des calculs AES pour cet exemple. • Une interface 53 de communication pour pouvoir échanger des données. 30 Pour authentifier le client, le distributeur peut envoyer au client une valeur initiale x (étape Eu )). La carte à puce, à la réception de x, va alors mettre en20 20 oeuvre les étapes du procédé selon l'invention, en prenant comme paramètre la clé K et la matrice G stockées en ROM et la valeur initiale x envoyée par le distributeur. La carte à puce calcule (étape E11) les 4 blocs de 128 bits définis par S1 = AES(K, x) AES(K, x+4) S2 = AES(K , x+1) AES(K , x+4) S3 = AES(K, x+2) O+ AES(K, x+4) S4 = AES(K, x+3) $ AES(K , x+4) 10 La carte à puce renvoie alors les 4 blocs Si, (pouvant être considérés comme un unique bloc de 512 bits) étape E12. A la réception de ces 4 blocs, le distributeur calcule également, selon l'invention et avec les paramètres K, G et x, 4 blocs de 128 bits (étape E13). Si ces 4 blocs sous identiques aux 15 quatre reçus, alors le client est authentifié auprès du distributeur et peut logiquement obtenir le contenu auquel il a légitimement accès (étape E14 et E15). Sans sortir du cadre de l'invention, le procédé peut aussi être utilisé pour authentifier des données échangées dans un système. 20 Bibliographie : [ABAG0I] 2D-Encryption Mode, A. A. Belal and M. A. Abdel-Gawad, SPIE, 25 volume 4793, 2003, 64-75. [BDJR97] A Concrete Security Treatment of Symmetric Encryption, M Bellare, A. Desai, E. Jokipii et P. Rogaway, FOCS 1997, 394-403. 30 [IWA06] New Blockcipher Modes of Operation with Beyond the Birthday Bound Security, T. Iwata, Fast Secure Encryption 2006, 331-348.5 [KNUO0] Block Chaining Modes of Operation, L. R. Knudsen, NIST call for new modes of operation, 2000. [NIST0I] Recommendation for Block Cipher Modes of Operation, Methodes and Techniques. M Dworkin, NIST Special Publication 800-38A, 2001. [SLLLY0I]Concrete Security Analysis of CTR-OFB and CTR-CFB Modes of Operation. J. Sung, S. Lee, J. Lim, W. Lee et O. Yi. 4th International Conference of Information Security and ryptology 2001, 103-113.15 REVENDICATIONS 1 û Procédé pour générer des chaînes de bits pseudo-aléatoires dans un 5 système dans lequel les échanges de données entre un premier utilisateur et un deuxième utilisateur sont protégés caractérisé en ce qu'il comporte au moins les étapes suivantes : • utiliser une application fK de taille de sortie n bits, • déterminer une valeur x et à partir de cette valeur x et en appliquant 10 l'application fK, générer t valeurs v;, • à partir des t valeurs v; et de u*t coefficients déterminer u blocs Si contenant des caractères pseudo-aléatoires. 2 - Procédé selon la revendication 1 pour générer des chaînes de bits 15 pseudo-aléatoires, au sein d'un système comprenant un module de codage de données, telles qu'un message de b= f*u*n + q bits, où f et u sont supérieurs ou égaux à 0, et q est compris entre 0 et u*n, peut se mettre sous la forme de f groupes de u blocs de n bits et d'un (f+1)ième groupe de q bits caractérisé en ce que : 20 le codage d'un groupe considéré de u blocs comporte au moins les étapes suivantes : • pour le groupe considéré choisir une valeur initiale x, • à partir des t valeurs v; générées et de u*t coefficients déterminer u blocs Si contenant des caractères pseudo-aléatoires afin de coder les 25 u blocs du groupe considéré, • combiner les u blocs du groupe considéré avec les u blocs Si afin d'obtenir le groupe codé, • réitérer ces trois étapes pour les f groupes, pour le (f+1)ième groupe de q bits, 30 • choisir une valeur initiale de x, 23 • à partir des t valeurs v; générées et de u*t coefficients déterminer un nombre de blocs Si égal au moins à la partie entière supérieure de q/n, • combiner q bits extraits des blocs Si déterminés avec les q bits du 5 (f+1)ième groupe. 3 ù Procédé selon la revendication 2 caractérisé en ce que l'on fait varier les u*t coefficients. 10 4 ù Procédé selon l'une des revendications 1 à 3 caractérisé en ce que les blocs Si sont obtenus de la manière suivante S;=(ail 0 vi)(a;,20 v2)0(a,,30v3) ... (D (a;,tOvt) Où O est la multplication avec o Dans le cas a;,;=1,a;,1OO vj=vj 15 o Dans le cas a,1=0,a;,jOvi =0 - Procédé selon l'une des revendications 1 à 3 caractérisé en ce que les blocs Si sont obtenus de la manière suivante S; = (a;,1 O VI) ' (a42 O v2) (a;,3 0 v3) O+ ... (au O Vt) 20 avec, pour les au tells que 0 1, auO vi représentant la sélection de au des n bits, selon un critère de sélection connu de l'application. 6 ù Procédé selon l'une des revendications 2 à 5 caractérisé en ce que l'on détermine la valeur du bloc m; d'indice i codé par Ci= m; +O Si 25 où +O correspond soit à l'opération xor égale au ou exclusif bit à bit ou à l'addition modulaire modulo 2" 7 ù Procédé selon I"une des revendications 1 à 6 caractérisé en ce que les valeurs t peuvent être obtenues en appliquant une fonction g choisie parmi la 30 liste suivante :• g,(fK,x)=f,