Brevet FR2897451A1 — publié le 20070817

Titre de l'invention Dispositif et procédé de cryptographie pour générer des nombres pseudo-aléatoires. Domaine technique de l'invention L'invention se rapporte au domaine de la cryptographie. Plus précisément, l'invention concerne l'utilisation d'un schéma de génération de nombres pseudo-aléatoires pouvant être mis en oeuvre dans des dispositifs ayant une faible puissance de calcul. La technique selon l'invention peut être appliquée à la mise en oeuvre d'un générateur de nombres pseudo-aléatoires (en anglais "pseudo-random nimber generatot" ou PRNG) de faible coût. Arrière-plan de l'invention D'une manière générale, il existe deux approches pour la conception des algorithmes cryptographiques symétriques. La première approche consiste à fournir " une preuve de sécurité " fondée sur la relation entre une méthode pour "casser" un code et la capacité à résoudre ce qui est communément considéré comme un problème difficile. La deuxième approche plus commune dépend d'une ingénierie minutieuse d'un circuit électronique comportant plusieurs composants de type portes logiques pour réaliser un chiffrement selon le niveau de sécurité souhaité, Dans ce cas, l'efficacité peut être quantifiée par la vitesse de calcul ou le nombre de portes logiques nécessaires pour réaliser le rira lli électronique. '3,ctuell meoi e E. jr [, )ri ',=''-- gÇlO 1thl,le'.-cryptographiques de type AL (Standard chiffrement avancé, ou Advanced Encryption Standard" en anglais : FIPS 197, NIST 2001 existe un grand intérêt à mettre en oeuvre ce genre d'algorithmes dans une large gamme d'applications. L'AES est remarquable pour son étroite observation des principes connus de Shannon et de deux notions importantes pour la mise en oeuvre des algorithmes cryptographique, à savoir la "confusion" et la "diffusion". De façon simplifiée, la "confusion" correspond à l'idée de "faire des opérations difficiles" tandis que la "diffusion" correspond à l'idée de "faire propager le changement ou la transformation" pendant un calcul cryptographique. Il est habituellement considéré qu'un des meilleurs moyens pour fournir un effet de confusion consiste à utiliser une boite de substitution "boîte-S" (S-box Substitution box), et qu'un des meilleurs moyens pour fournir un effet de diffusion consiste à réaliser un certain type de permutation. En effet, l'algorithme AES prend en entrée un bloc de 16 octets. Chaque octet est remplacé par un autre octet selon une boite de substitution (boite-S) de 8-bits vers 8-bits. Ces octets sont ensuite placés dans une matrice où chaque élément de la matrice est décalé cycliquement à gauche d'un certain nombre de colonnes. Ensuite, on effectue un produit matriciel avant d'additionner chaque octet avec un octet correspondant d'une clé d'itération ("round keY' en anglais) obtenue par diversification d'une clé de chiffrement. Ainsi, la sécurité d'un algorithme du type AES dépend d'une interaction entre la boîte-S et une opération de mélange (ou de diffusion) consistant à permuter des octets et à les combiner structurellement. Y111i i i -Si i \rt d rrk3iiiP case Jfin (iRralitli" Jin hi". riirle :,taiic,'-T ( ) tta q di-yptanalyse différentielle ou pia cryptand Actuellement, on essaie d'introduire des fonctionnalités cryptographiques dans des environnements de calcul très restreints comme par exemple dans des puces RFID. Cependant, des algorithmes pour ce genre d'environnement sont réalisés au coup par coup et utilisent des composants cryptographiques de faible capacité. En effet, il est très difficile de réaliser des composants cryptographiques ayant une qualité comparable à ceux utilisés pour la mise en ceuvre d'un algorithme de type AES dans un environnement très restreint. Objet et résumé de l'invention La présente invention concerne un procédé cryptographique pour générer des nombres pseudo-aléatoires comportant les étapes suivantes : - subdiviser des données initiales en une pluralité de mots à b -bits définis dans un corps fini GF(2 , - affecter lesdits mots à des cellules d'un tableau d'état pour former un bloc d'état initial, -regrouper les cellules dudit tableau d'état pour affecter un groupe de cellules à chaque ensemble de d/b mots, où d est un multiple de b strictement supérieur à b, et - générer de manière itérative à partir dudit bloc d'état initial, une succession de blocs d'états pour former un bloc d'état final, de sorte qu'à chaque itération chaque ensemble de d /b mots d'un bloc d'état courant est remplacé par un autre ensemble de mots, en utilisant, pour f-11C)rr7let IP r-)10(, étai au moins 1 r flîE: ornpor arlt lIe ç,IVJ éienienb 5unstitute, uit,,,. Le fait d utiliser une table de référence àyant des éléments de longueur d strictement supérieure à b introduit un effet de diffusion en plus de l'effet de confusion, réalisant ainsi une génération de nombres pseudo-aléatoires de qualité avec un coût de calcul très réduit. On notera qu'un algorithme de type AES utilise une boîte-S ayant des éléments de la même taille que les mots d'un bloc d'état interne faisant correspondre un mot d'entrée de b -bits à un autre mot de sortie de b -bits, et les mots sont utilisés un par un. Ainsi, le remplacement des mots par substitution selon la boîte-S réalisée par ce genre d'algorithme engendre un effet de confusion mais aucun effet de diffusion. En revanche, l'opération de substitution selon la table de référence de l'invention n'utilise pas les mots un par un, mais par regroupement. Par ailleurs, on notera que l'utilisation d'une table de référence ou boite-S ayant des éléments plus grands que les mots de l'état interne est tout à fait contraire aux habitudes de l'homme du métier. Ainsi, la configuration selon l'invention permet d'assurer à la fois la diffusion et la confusion tout en économisant du temps de calcul pour le même niveau de sécurité. Ceci permet d'améliorer le niveau de sécurité tout en diminuant le nombre de portes logiques ("gates equîvalent" ou GE en anglais) dans la réalisation d'un circuit électronique mettant en oeuvre ce procédé de chiffrement. Ainsi, la technique selon l'invention peut être facilement appliquée pour la mise en oeuvre d'un générateur de nombres pseudo-aléatoires de faible coût et dans un environnement très restreint comme une cellule ou puce RFID. En outre, cette technique peut être appliquée à une variété d'algorithmes cryptographiques du type codage par blocs, codage par flux, fonctions de hachage, ou codes d'authentification de messages. De plus, l'utilisation de ee genre de table de -éférence avec Tic:terne ri dupé rieure oer met de - allSe! i` jene!at,-" H 'OMI:1- e,jdo ste attaques par cryptanalyse type "square attacks auxquelles les algorithmes de type AES sont réputées être sensibles, Avantageusement, la génération itérative de ladite succession de blocs d'états comporte en outre une étape pour mélanger les mots dudit bloc d'état courant selon une transformation de mélange prédéterminée. Cette transformation de mélange garantit une meilleure diffusion ou propagation des bits d'un bloc d'état améliorant ainsi la sécurité du cryptage et la qualité des nombres pseudo-aléatoires générés sans trop alourdir les étapes de calcul. Cette transformation de mélange prédéterminée peut comporter une multiplication dans le corps fini GF(2h) d'une colonne dudit bloc d'état courant par une matrice prédéfinie dans ledit corps fini. Cette multiplication matricielle est une transformation linéaire assez simple à mettre en oeuvre. Avantageusement, la génération itérative de ladite succession de blocs d'états comporte en outre une permutation entre des mots sur au moins une partie dudit bloc d'état courant. Ceci permet d'augmenter encore davantage la propagation des bits, ce qui améliore la sécurité. Selon une particularité de la présente invention, la génération itérative de ladite succession de blocs d'états comporte en outre une modification d'au moins une partie d'un mot situé dans une cellule prédéterminée du tableau d'état. Ceci permet de réduire toute symétrie pouvant s'installer lors des itérations successives, ce qui complique toute tentative de prédiction et améliore par conséquent la sécurité du procédé. r-T5elon i 1( ipn! te .i3ui-J.-e Particule rité E. uonnblnalson eédltlo le e chaque mot dudit bloc d'état initiai avec un mot correspondant dans une clé de chiffrement améliorant ainsi le niveau de sécurité. Ainsi, une sécurité similaire à celle d'un algorithme de type AES peut être garantie avec un nombre optimal de calculs. Avantageusement, lesdites données initiales sont générées par un compteur. Ainsi, on peut facilement générer des nombres pseudoaléatoires avec un nombre minimal d'opérations. L'invention vise aussi un dispositif cryptographique pour générer des nombres pseudo-aléatoires, comportant - un moyen de subdivision pour subdiviser des données initiales en une pluralité de mots à b -bits définis dans un corps fini GF(2'l ), - un moyen d'affectation pour affecter lesdits mots à des cellules d'un tableau d'état pour former un bloc d'état initial, - un moyen de définition pour définir et mémoriser au moins une table de référence comportant des éléments de substitution à d -bits, où d -est un multiple de b strictement supérieur à b, - un moyen de regroupement pour regrouper les cellules dudit tableau d'état pour affecter un groupe de cellules à chaque ensemble de d/b mots, et - un moyen de génération pour générer de manière itérative à partir dudit bloc d'état initial, une succession de blocs d'états pour former un bloc d'état final, de sorte qu'à chaque itération chaque ensemble de crib mots d'un bloc d'état courant est remplacé par un autre ensemble de d/b mots en fonction de ladite table de référence pour former un bloc d'état suivant. L'invention vise également un générateur de nombres pseudoaléatoires comportant un compteur et une pluralité de portes logiques pour la mise en oeuvre du procédé décrit succinctement ci-dessus. L'Invention Lise i i--::: ir UISLOSItIt 1_ _' Or ni O tant un géneLateu Lei que dé -.Lit su c noLernent Dessus. Brève description des dessins D'autres particularités et avantages de l'invention ressortiront à la lecture de la description faite, ci-après, à titre indicatif mais non limitatif, en référence aux dessins annexés, sur lesquels : - la figure 1 est un organigramme illustrant les différentes étapes d'un procédé cryptographique selon l'invention ; - la figure 2 est un exemple illustrant l'action d'une table de référence selon le procédé de la figure 1 ; - la figure 3 illustre très schématiquement un dispositif mettant en oeuvre le procédé de la figure 1 ; - la figure 4 est un mode particulier de réalisation du procédé de la figure 1 ; et - la figure 5 illustre très schématiquement un générateur de nombres pseudo-aléatoires mettant en oeuvre le procédé de la figure 4. Description détaillée de modes de réalisation Conformément à l'invention, la figure 1 est un organigramme illustrant les différentes étapes d'un procédé cryptographique pour générer des nombres pseudo-aléatoires à partir de données initiales. L'étape El comporte le découpage ou la subdivision du message ou des données initiales 1 en une pluralité de mots 3 à b -bits définis dans un corps fini GF(2''), où b peut par exemple être égal à 2, 4, 8, 16, 32, 64 ou 128. A l'étape E2, ces mots 3 sont affectés à des cellules 5 d'un tableau d'état 7 pour former un bloc d'état initial. On notera qu'on peut ne placer qu'une partie de ces mots 3 dans le tableau d'état elepe F3, ecil ine ies rellliieL (1ri iebleeli de iernr_ scinble Je 1/b mots, où d est un multiple de b , avec d > b . Chaque ensemble de mots correspond alors à un élément de d -bits. Finalement, à l'étape E4, on génère de manière itérative à partir du bloc d'état initial 13a, une succession de blocs d'états 13b courants pour former un dernier bloc ou un bloc d'état final 13c. Pour ce faire, on utilise au moins une table de référence ou de substitution 9 prédéfinie comportant des éléments de substitution à d -bits. Ainsi, cette table de référence 9 permet de remplacer un élément d'entrée de d -bits par un élément de sortie de d -bits. A chaque itération, chaque ensemble de d/b mots d'un bloc d'état 13b courant est remplacé par un autre ensemble de d/b mots en fonction de la table de référence 9 pour former un bloc d'état suivant. Ainsi, le dernier bloc d'état 13c représente le nombre pseudo-aléatoire généré. Le fait d'utiliser une table de référence ayant des éléments de longueur d > b introduit un effet de diffusion en plus de l'effet de confusion et permet de réaliser un bon niveau de sécurité d'une manière plus rapide qu'une table de substitution (boîte-S) de l'état de l'art où d =b. La figure 2 est un exemple illustrant l'action d'une table de référence 9 sur un tableau d'état 7 comportant quatre colonnes et quatre lignes (4x4). Selon cet exemple le bloc d'état initial 13a comporte les mots A00,_,A33 à 4-bits (c'est-à-dire b = 4) et la table de référence 9 comporte des éléments à 8-bits (c'est-à-dire d -8). Dans ce cas, on peut utiliser une table de référence du type boite-S d'un algorithme AES. Ainsi, les cellules 5 du tableau d'état 7 sont regroupées par groupes de deux cellules. Selon cet exemple, les c~llufes 5 comportant les Ou"'IDOrt le= outs comportant les mots A11 et Al2 forment un troisième groupe llc, etc. Dans ce cas, la table de référence 9 substitue les mots deux par deux. Par exemple les mots Aoo et Aol sont remplacés par Boo et Bol et les mots A02 et A03 sont remplacés par forment xemier qroupe ., OP-neni. un ciel_ Xlefl-1 Upe B02 et B03. Alors un autre bloc d'état 13b est formé comportant les mots 800,...,B33 définis par une fonction " S " déterminée par la table de référence 9 de la manière suivante : BoolIBol = S[AooI1Ao1J, Bo2IIBo3 = S[Ao2IIAo3] B11 I I B12 = S[A11I IAl2], B1311 B10 = S[A131 IA1o]]~7 B2011821 = S[A2o I I A21 ], B2211 B23 = S[A221 I A23] 8311 1 B32 = S[A311 I A321, 8331 1 B30 = S[A331 I A30] , où le symbole "Il" entre deux mots représente leur concaténation. Ainsi, on peut générer de manière itérative une succession de blocs d'état 13b en fonction d'une ou de plusieurs tables de référence 9. On notera que dans un milieu restreint (par exemple RFID), il est préférable (quoique non obligatoire) d'utiliser une seule table de référence 9 pour toutes les opérations. Afin de garantir une meilleure propagation, les mots 3 d'un bloc d'état 13b courant peuvent être mélangés selon une transformation MIX " de mélange prédéterminée. Ainsi, à chaque itération, l'opération de substitution en fonction de la table de référence 9 peut être suivie par un mélange de mots à b - bits, en utilisant par exemple une technique similaire à celle utilisée par l'algorithme AES. Selon l'exemple de la figure 2, ce mélange MIX peut être réalisé de la manière suivante : Coo (I 0101 102011030 = MIX [Boo l 1 81011 82011 830] Co1l1C111IC2111C31 = MIX [Boil1 B1111 B2111 B31] Co21IC1211C2211C32 = MIX [60211 B1211 82211 832] 1Ir 1',11 `. 'iIX_ S. 11hX11 )peratlOÎÎ la MIX qui dépendent des matrices choisies, il peut être avantageux de permuter des mots 3 sur au moins une partie du bloc d'état 13b courant selon une opération de permutation " Echanger" ("swap" en anglais). Selon l'exemple de la figure 2, cette permutation " Echanger " peut être réalisée de la manière suivante : Echanger CO21ICl2 avec C221IC32 Echanger CO311C13 avec C2311C33 En outre, selon les caractéristiques des composants électroniques utilisés pour la fabrication d'un dispositif mettant en oeuvre le procédé selon l'invention, un simple compteur d'incrémentation ou un tout autre mécanisme similaire peut être utilisé pour réduire toute symétrie pouvant s'installer lors des itérations successives. A titre d'exemple, ceci peut comporter une simple modification d'au moins une partie d'un mot situé dans une cellule 5 prédéterminée du tableau d'état 7. Par exemple, il suffit de complémenter quelques bits situés dans une seule cellule 5 bien déterminée et à un moment bien déterminé du calcul. De plus, le procédé selon l'invention peut comporter une combinaison par addition (opération "ou-exclusif") dans le corps fini de chaque mot 3 du bloc d'état initial 13a avec un mot correspondant d'une clé de chiffrement prédéfinie ou avec des suites alternées de mots secrets. La figure 3 illustre très schématiquement un dispositif 21 mettant en oeuvre le procédé selon la figure 1. Ce dispositif 21 comporte un moyen de subdivision 23, un moyen d'affectation 25, un moyen de définition 27, un moyen de regroupement 29 et un moyen de génération 31. Le moyen de subdivision 23 est destiné à subdiviser le message ou les données initiales en une pluralité de mots 3 à b -bits. Le moyen d'affectation 25 est destiné à affecter ces mots 3 aux cellules 5 du tableau d'état 7 pour for irliter bloc RI IrIlIRF moyen Iéfinitk.)n OPfinii rnérrIr'H',e L ta b!es reférence 9 ou de substitution comportant les e ements de substitution à d -bits avecd >h. Le moyen de regroupement 29 est destiné à regrouper les cellules 5 du tableau d'état pour affecter un groupe 11 de cellules à chaque ensemble de d lb mots. Le moyen de génération 31 est destiné à générer de manière itérative à partir du bloc d'état initial 13a, une succession de blocs d'états 13b pour former un bloc d'état final 13c représentatif d'un nombre pseudo-aléatoire. Dans la mise en oeuvre d'un générateur de nombres pseudoaléatoires, les données initiales 1 utilisées pour former le bloc d'état initial 13a peuvent être générées par un simple compteur. En effet, la figure 4 est un organigramme illustrant un mode particulier de réalisation d'un générateur de nombres pseudo-aléatoires PRNG à 64-bits et comportant dix itérations. Ce générateur peut être utilisé dans une puce RFID comportant une clé secrète de 128-bits. La clé secrète peut par exemple être représentée par un couple de données (so, si) où so et si a ont tous deux une longueur de 64 bits. A chaque séquence d'itérations définie par un compteur cl de 16-bits, une valeur de sortie v, de 64-bits est générée par le PRNG en fonction de cl, so et si (c'est-à-dire v,=f (cl, so, si) pour 15_ i A une itération numéro r donnée, le bloc d'état 13b courant est alors défini en fonction du tableau de référence 9 de la manière suivante : Booj !Bol = S[A001 IA01], B0211 B03 = S[A0211A03] BI 11E312 = S[An IAl2], B1311 Blo = S[AI311A10] 620f 1B21 = S[Az01IA21], B22HB23 = S[A22IIA23] 63111632 = S[A3111A32 e ri, 6331 B30 = S[A33I IA30] On notera qu'à l'itération numéro r, la valeur prise par r est ajoutée à un mot (par exemple le mot A32) afin de réduire tout effet de symétrie pouvant se produire entre les itérations. L'opération de mélange MIX est un mélange à l'intérieur d'une colonne utilisant une matrice M prédéterminée de dimension 4x4 dans un corps fini GF(24). Cette opération consiste à multiplier chaque colonne du tableau d'état (7) par cette matrice M. L'opération de mélange MIX peut être suivie par une permutation des mots sur les deux dernières lignes du bloc d'état 13b courant de la manière suivante : CO2IIC12 échangé avec C2211C32, et CO311CI3 échangé avec C2311C33. A l'étape E14, on combine par une addition ou-exclusif, les 64-bits du bloc d'état 13b courant avec les seize demi-octets (16 fois 4-bits) dans si de la clé secrète. A l'étape E15, on réalise encore quatre itérations d'opérations du type "rnixtab/e ". A l'étape E16, on combine par une addition ou-exclusif, les 64-bits du bloc d'état 13b courant avec les seize demi-octets (16 fois 4-bits) e e c-,e( rete erao Or ef r( ui '(ro( Lératiotns o u erations du type "mAtab/e'" . A l'étape E18, on recombine par une addition ou-exclusif, les 64-bits du bloc d'état 13b courant avec les seize demi-octet (4-bits) dans si de la clé secrète. L'étape E19 donne la valeur de sortie vi à la ième séquence d'itérations de la manière suivante : = [VO011-11V0311V10II-11V1311-11V33]. L'étape E20 est un test pour vérifier si la valeur ci du compteur est égale à (216-1). Si oui, la puce est détruite à l'étape E21, sinon, on incrémente cl à l'étape E22 avant de recommencer les étapes ci-dessus. La figure 5 illustre très schématiquement un générateur 41 de nombres pseudo-aléatoires PRNG mettant en oeuvre le procédé selon la figure 4. Ce générateur 41 comporte un compteur 43 et une pluralité de portes logiques 45. Ce générateur PRNG peut être facilement utilisé dans une puce RFID. On notera qu'une implémentation d'un algorithme du type AES est déterminée par une boîte-S et une mémoire RAM nécessitant 395 et 2337 portes logiques (GE) respectivement. En revanche, en comparaison avec l'algorithme AES, un PRNG 41 selon l'exemple des figures 4 et 5 divise le nombre d'états par deux et ne comporte pas des clés d'itération obtenues par diversification. Par ailleurs, les opérations de mélange à l'intérieur des colonnes nécessitent très peu de portes logiques. Ainsi, on obtient, grâce à l'invention, un générateur PRNG 41 efficace avec un bon niveau de sécurité et un nombre de portes (GE) réduit par rapport à l'algorithme AES. REVENDICATIONS 1. Procédé cryptographique pour générer des nombres pseudo-aléatoires (1), caractérisé en ce qu'il comporte les étapes suivantes - subdiviser des données initiales (1) en une pluralité de mots (3) à b -bits définis dans un corps fini GF(2'' ) - affecter lesdits mots à des cellules (5) d'un tableau d'état (7) pour former un bloc d'état initial (13a), - regrouper les cellules (5) dudit tableau d'état (7) pour affecter un groupe (11) de cellules à chaque ensemble de d/b mots, où d est un multiple de b strictement supérieur à b , et - générer de manière itérative à partir dudit bloc d'état initial (13a), une succession de blocs d'états (13b) pour former un bloc d'état final (13c), de sorte qu'à chaque itération chaque ensemble de d/b mots d'un bloc d'état (13b) courant est remplacé par un autre ensemble de d /b mots, en utilisant, pour former un bloc d'état suivant, au moins une table de référence (9) comportant des éléments de substitution à d -bits. 2. Procédé selon la revendication 1, caractérisé en ce que la génération itérative de ladite succession de blocs d'états (13b) comporte en outre une étape pour mélanger les mots dudit bloc d'état courant selon une transformation de mélange prédéterminée. 3. Procédé selon la revendication 2, caractérisé ce que ladite transformation de mmange adéterminée corriaorte Uarls ie ripa ini GF(a ) dune colonne dudit broc ( La courait par une matrice prédéfinie dans ledit corps fini. 4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que la génération itérative de ladite succession de blocs d'états comporte en outre une permutation entre des mots sur au moins une partie dudit bloc d'état courant. 5, Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que la génération itérative de ladite succession de blocs d'états comporte en outre une modification d'au moins une partie d'un mot situé dans une cellule (5) prédéterminée du tableau d'état (7). 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce qu'il comporte une combinaison par addition dans le corps fini de chaque mot dudit bloc d'état initial (13a) avec un mot correspondant dans une clé de chiffrement. 7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que lesdites données initiales (1) sont générés par un compteur. 8. Dispositif cryptographique pour générer des nombres pseudo-aléatoires, caractérisé en ce qu'il comporte : -un moyen de subdivision (23) pour subdiviser des données initiales (1) en une pluralité de mots (3) à b -bits définis dans un corps fini GF(2 , - un moyen d'affectation (25) pour affecter lesdits mots à des cellules (5) d'un tableau d'état (7) pour former un bloc d'état initial (13a), - un moyen de définition (27) pour définir et mémoriser au moins une table Ife référence (9) (opiner reni les élémentc, le sunstitutjor bits nu nnultIple Cie strictement `SU heur - un moyen de regroupement (29) pour regrouper les cellules dudit tableau d'état pour affecter un groupe de cellules à chaque ensemble de d/b mots, et- un moyen de génération (31) pour générer de manière itérative à partir dudit bloc d'état initial (13a), une succession de blocs d'états pour former un bloc d'état final (13c) de sorte qu'à chaque itération chaque ensemble de d /b mots d'un bloc d'état courant est remplacé par un autre ensemble de d / b mots en fonction de ladite table de référence (9) pour former un bloc d'état suivant, 9. Générateur de nombres pseudo-aléatoires caractérisé en ce qu'il comporte un compteur (43) et une pluralité de portes logiques (45) pour la mise en oeuvre du procédé selon les revendications 1 à 8. 10. Dispositif RFID caractérisé en ce qu'il comporte un générateur (41) selon la revendication 9.