Brevet FR2650458A1 — publié le 19910201

Procédé de traitement d'une permutation irrégulière de don- nées protégées par chiffrement". La présente invention concerne un procédé de trai- tement d'une permutation irrégulière mise en oeuvre lors d'un traitement de données binaires protégées par chiffrement pour carte à microcircuit, le chiffrement étant opéré par une suite de transformations de données d'entrée utilisant une extrac- tion d'une'clé secrète évoluant à chaque itération, la permu- tation irrégulière étant effectuée sur la clé secrète à partir d'une table de correspondance. Un tel traitement de données binaires protégées par chiffrement appliqué aux cartes à microcircuit est décrit dans la publication: "Federal Information Processing Standards Publication" (FIPS PUB 46) du 15 janvier 1977, du Bureau National des Standards du Ministère du Commerce américain.- Cette publication propose un traitement standard des données d'entrée ainsi que la clé secrète et notamment des permuta- tions à réaliser sur celle-ci à partir de tables de correspon- dance. Lorsqu'un tel traitement est appliqué aux données uti- lisées dans une carte à microcircuit, celui-ci doit être le plus rapide et également le plus compact possible, la taille de code admissible dans une carte à microcircuit étant des plus limitées. Or l'opération de permutation sur la clé est une étape coûteuse en temps de traitement et en taille de code. Pour traiter une permutation irrégulière, il existe habituellement deux procédés. Le premier consiste à traiter chaque permutation d'élément binaire (bit) un à un, alors que. le second consiste à lire dans la table de correspondance, l'adresse de destination de chaque bit. Le premier procédé est relativement rapide mais coûte cher en taille de code, tandis que le second présente les caractéristiques inverses. La présente invention propose un procédé du genre précité mais qui ne présente pas les inconvénients des procé- dés connus. Elle permet d'optimiser cette opération en ac- croissant très sensiblement la vitesse de traitement tout en nécessitant une taille de code limitée. Pour cela le procédé de traitement d'une permuta- tion irrégulière du genre mentionné dans le préambule est re- marquable en ce que ladite permutation irrégulière à effectuer sur un nombre n d'éléments binaires est décomposée en un nom- bre n' de permutations élémentaires, le nombre n' étant infé- rieur au nombre n, les permutations élémentaires étant trai- tées de telle sorte que le plus grand nombre d'entre elles soit opéré sur au moins deux éléments binaires. Pour cela, pour chaque ligne de la table de correspondance est réalisé un repérage des éléments binaires appartenant au premier octet de la clé, puis au second et ainsi de suite jusqu'au dernier octet. Ce repérage permet d'établir un système de masquage afin d'extraire les éléments binaires concernés pour la permutation de ceux-ci aux emplacements prédéfinis par la table de correspondance. Ainsi, un tel procédé autorise à la réalisation de permutations irrégulières et donc totalement asymétriques sur un grand nombre d'éléments binaires en évitant le traitement bit à bit coûteux en temps et en taille de code. En effet le concept combinant la décomposition en permutations élémen- 2-5 taires, le repérage des bits adéquats et l'utilisation d'un système de masquage permet d'effectuer de manière optimale des regroupements et donc des permutations par 2 et même par 3 bits et ainsi de bénéficier d'une réduction très sensible du temps de traitement sur l'ensemble de la permutation. Ce type de procédé est particulièrement bien adapté pour être avantageusement appliqué au traitement de données protégées par chiffrement des cartes à microcircuit utilisant le système DES, tel que décrit dans la publication précitée (FIPS PUB 46). Ainsi, selon ce système, la clé après rotation d'un bloc de 56 bits est comprimée à 48 bits ainsi que permu- tée à partir d'une table de correspondance appelée, selon le standard: table PC2. Cette opération est considérée comme la plus coûteuse du système DES en ce qui concerne le temps de traitement ainsi que la taille du code. L'application du pro- cédé selon l'invention, si elle ne permet pas de réduire nota- blement la taille du code permet cependant de réduire très sensiblement le temps de traitement (de l'ordre de 50%). Ainsi, pour chaque-ligne de la table PC2, le procé- dé consiste à repérer les bits appartenant au premier octet de la clé, puis au second et ainsi de suite. Ce repérage permet alors d'établir les masques correspondants afin d'extraire les bits concernés, la suite du procédé consistant à permuter les bits obtenus de façon à ce qu'ils correspondent bien aux em- placements définis par la table PC2. Sur les lignes de la table PC2, seuls les 6 bits situés à droite de l'octet résultant sont significatifs. Par exemple, la première ligne de la table PC2 se décompose comme suit: numéro de bit: 14 17 11 24 1 5 numéro d'octet dans la clé: (1) (2) (1) (2) (O) (0) Pour construire cette ligne de la table PC2, chaque octet de la clé est pointé séquentie- llement alors que les bits intéressants doivent être récupérés grâce au système de mas- quage. On voit selon cet exemple que seuls les bits 1 et 5 intéressent l'octet O de la clé lorsque celui-ci est pointé, le masque correspondant est ainsi défini: Entrée de la table PC2: a1 0 0 0 a2 O 0 Sortie de la table PC2: X X O O O O a1 a2 A la sortie de la table PC2, seuls les 6 bits situés à droite sont significatifs.' Les deux premiers situés à gauche étant non significatifs. Cette opération est réitérée 8 fois de façon à traiter tous les bits et, selon le procédé appliqué, un cer- tain nombre de permutations sont obtenues pour le traitement - O de la clé. IL suffit alors d'effectuer un OU logique entre chaque octet résultant pour un même octet donné de la clé. Le résultat final est codé sur 8 mots de 6 bits, en fait sur 8 octets, pour lesquels seuls 6 bits cadrés à droite sont con- serves. La définition des permutations est ainsi faite. Les octets (0) de la clé sont numérotés de 0 à 7. Les bits à l'in- térieur de chaque octet sont numérotés de 1 à 8 et de gauche à droite. Ainsi sont obtenues 15 permutations pour le traitement de la partie basse de la clé (de O0 à 03) et 14 permuta- tions pour le traitement de la partie haute de la clé (de 04 à 07), soit au total 29 permutations pour l'ensemble de la clé. Le traitement de'ces 29 permutations de manière li- néaire est coûteux en taille de code, mais est assurément le procédé le plus rapide. Ce traitement est effectué à l'aide de microprocesseurs 8 bits tels que le 6805 de chez Motorola ou le 8048 de chez Intel. Le traitement le plus rapide a été'ob- tenu lors de l'utilisation du'microprocesseur 8048. De manière spécifique, le procédé de traitement d'une permutation irrégulière selon l'invention, appliqué au traitement de données protégées par chiffrement des cartes à microcircuit utilisant le système DES est remarquable en ce qu'il est effectué selon les étapes suivantes et ceci pour chaque octet de la clé: a) pointage sur l'octet de rang i de la clé. b) chargement de la valeur du masque dans l'accumulateur. c) masquage entre l'accumulateur et le contenu de l'octet. d) permutation de l'octet. e) exécution d'un OU logique avec le résultat précédent. f) rangement du résultat dans un registre de stockage temporaire. Un tel procédé-peut s'appliquer bien entendu à toute permutation non régulière, le principe étant qu'il est plus facile de réaliser plusieurs permutations sur un, deux ou trois bits plutôt que d'en réaliser une seule sur un grand nombre de bits. Le procédé ne permet pas d'obtenir un gain en taille de code très notable, mais de réduire très sensiblement le temps de traitement de la permutation. REVENDICATIONS: 1. Procédé de traitement d'une permutation irrégulière mise en oeuvre lors d'un traitement de données binaires pro- tégées par chiffrement pour carte à microcircuit, le chif- frement étant opéré par une suite de transformations des don- nées d'entrée utilisant une extraction d'une clé secrète évo- luant à chaque itération, la permutation irrégulière étant ef- fectuée sur la clé secrète à partir d'une table de correspon- dance, caractérisé en ce que ladite permutation irrégulière à effectuer sur un nombre n d'éléments binaires, est décomposée * en un nombre n' de permutations élémentaires, le nombre n' étant inférieur au nombre n, les permutations élémentaires étant traitées de telle sorte que le plus grand nombre d'entre elles soit opéré sur au moins deux éléments binaires, pour ce- la, pour chaque ligne de la table de correspondance est réa- lisé un repérage des éléments binaires appartenant au premier octet de la clé, puis au second et ainsi de suite jusqu'au dernier octet, ce repérage permettant d'établir un système de masquage afin d'extraire les éléments binaires concernés pour la permutation de ceux-ci aux emplacements prédéfinis par la table de correspondance. 2. Procédé de traitement d'une permutation irrégulière selon la revendication 1 caractérisé en ce qu'il est effectué selon les étapes suivantes et ceci pour chaque octet de la clé: a) pointage sur l'octet de rang i.de la clé. b) chargement de la valeur du masque dans l'accumulateur. c) masquage entre l'accumulateur et le contenu de l'octet pointé. d) permutation de l'octet. e) exécution d'un OU logique avec le résultat précédent. f)-rangement du résultat dans un registre de stockage tempo- raire. 3. Carte à microcircuit protégé par chiffrement utili- sant le système DES, à laquelle est appliqué le procédé con- forme aux revendications 1 ou 2.