Brevet FR2650411A1 — publié le 19910201

~Procédé de décalage d'un mot constitué d'un nombre pair de bits non multiple de huit" La présente invention concerne un procédé de décalage d'un mot constitué d'un nombre pair n de bits non multiple de huit pour un traitement de données réalisé au moyen d'un microprocesseur disposant d'une instruction du type test de bit. Les instructions de décalage (également appelé rotation) sont aisément réalisables au moyen des microprocesseurs courants du commerce. Cependant lorsqu'il est nécessaire d'effectuer de tels décalages sur des mots constitués d'un nombre pair de bits non multiples de huit et donc sur un nombre non entier d'octets, les microprocesseurs courants sont mal adaptés à ce type de traitement. La solution à ce genre de probléme passe obligatoirement par l'élaboration d'algorithmes nécessitant des temps de traitement prohibitifs et si de plus les données à traiter sont codées, une telle solution requiert une taille de code excessive et donc une occupation mémoire exagérée.En outre, le traitement d'un décalage à droite n'est pas dans ce cas identique à celui du traitement d'un décalage à gauche, il en résulte alors une différence de vitesse d'exécution, ce qui peut être gênant lorsque de tels traitements sont appliqués à des données codées, les procédés utilisés devant être différents selon qu'il s'agit d'un codage ou d'un décodage. De tels procédés sont pratique courante pour l'homme du métier. Ainsi un procédé classique de traitement d'un tel décalage consiste à exécuter le décalage sur un nombre entier d'octets puis à reconstituer le dernier octet par une suite de décalages et de masquages pour obtenir le décalage d'un nombre quelconque de bits. 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 et permet de ce fait un traitement rapide et peu coûteux en taille de code. Pour cela le procédé de décalage du genre mentionné dans le préambule est remarquable en ce qu'il est effectué une duplication croisée et symétrique des bits non significatifs pour obtenir un mot constitué d'un nombre n' de bits multiple de huit, sur lequel est d'abord effectué un test pour positionner le report au moyen de l'instruction du type test de bit puis est effectué un nombre m de décalages avec report, à droite ou à gauche selon le choix désiré. Ainsi grâce à ce procédé réorganisant de manière simple la structure des mots, le décalage peut s'exécuter aisément en un nombre d'opérations réduit à la quantité m+l (test de bit + m décalages) ce qui permet de réduire très sensiblement le temps d'exécution ainsi que la taille du code nécessaire à une telle opération. En outre, le procédé autorise à une exécution des instructions de -manière totalement symétrique, ainsi les décalages peuvent être effectués aussi bien à gauche qu'à droite dans un temps identique. Enfin, lorsque le procédé est appliqué au traitement de données codées, le codage et le décodage sont alors opérés à une même vitesse facilitant ainsi considérablement le traitement des données. De manière avantageuse, lorsqu'il est désiré exécuter un décalage de l'intégralité d'un mot traité, le nombre m est égal au rapport entier n'/8x, avec x entier variant de 1 à i selon la capacité de traitement du microprocesseur. Le nombre x dépend bien entendu de la capacité de traitement du microprocesseur, il est par exemple égal à l'u nitré pour un microprocesseur 8 bits, à 2 pour un microprocesseur 16 bits et à 4 pour un microprocesseur 32 bits. L'exemple suivant, non limitatif, permettra de bien comprendre comment l'invention peut être réalisée. Soit un décalage à réaliser sur un mot ne comportant que 28 bits (bit 0 à bit 27), le nombre n=28 n'étant pas un multiple de 8 et le mot ne contenant donc pas un nombre entier d'octets. Le mot de 28 bits est alors stocké dans un mot de n'=32 bits, les quatre bits non significatifs sont utilisés pour la duplication croisée et symétrique des bits 0, 1 et-26, 27.Ainsi les bits 26 et 27 sont dupliqués et placés devant le bit 0 et les bits 0 et 1 sont également dupliqués et placés après le bit 27 pour former un mot de n'=32 bits comme le montre l'exemple E1 suivant (26, 27, 0, I, 2 3, ..., 24, 25, 26, 27, 0, 13 (E1) Supposons de plus qu'un microprocesseur 8 bits est utilisé, par exemple le 6805 de chez Motorola ou lé 8051 de chez Intel, microprocesseur disposant de l'instruction test de bit, le nombre x est alors égal à 1 et le nombre de décalages égal n'l8=32l8=4. Selon le procédé de l'invention et à partir de cette nouvelle structure de n'=32 bits, le décalage peut s'exécuter de manière totalement symétrique (décalage à droite ou décalage à gauche) et ceci en m+1= 5 opérations.La première opération consiste à utiliser une instruction spécifique aux microprocesseurs précités :l'instruction de test de bit. Le résultat du test positionne le report ("flag carry" dans les termes de l'homme du métier) en fonction de la valeur du bit testé. il suffit alors d'exécuter les opérations de décalages avec report (ici au nombre de 4) pour réaliser le décalage du mot complet de 28 bits. Ainsi en reprenant exemple Efi proposé précédemment, un décalage à gauche donnerait le résultat suivant (26, 27,'0, 1, 3, 4, ..., 25, 26, 27, 0, 1, 2 ] (E2) 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.Le système DES 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. Dans ce système, le chiffrement est opéré par une suite de transformations des données d'entrée utilisant une extraction d'une clé secrète évoluant à chaque itération. Dans une telle application, il peut s'agir de réaliser un décalage sur une demi-clé comportant 28 bits (la clé dans le système DES comporte 56 bits). Ainsi un décalage à gauche des deux demi-clés peut être réalisé de la façon suivante selon le procédé de l'invention et en utilisant les instructions d'un microprocesseur tel que le 6805 de chez Motorola. BRSET ~ test de bit, positionnement du report (1èredemi-clé) ROL # 1er décalage à gauche ROL # 2nd décalage à gauche ROL # 3ème décalage à gauche ROL ~ 4èmedécalage à gauche BRSET c test du bit, positionnement du report (2ndedeni#clé) ROL z lerdécalage à gauche ROL ffi 2èmedécalage à gauche ROL ~ 3èmedécalage à gauche ROL + 4èmedécalage à gauche De même et dans les mêmes conditions, un décalage à droite est exécuté de manière totalement symétrique. BRSET ~ test u bit, positionnement du report (1èredemi#clé) ROR + lerdécalage à droite ROR f 2nddécalage à droite ROR ~ 3èmedécalage à droite ROR + 4èmedécalage à droite BRSET d test de bit, positionnement du report (2nde demi-clé) ROR # 1erdécalage à droite ROR # 2 nddécalage à droite ROR # 3èmedécalage à droite ROR c 4èmedécalage à droite De manière générale, le procédé, selon l'invention, peut être appliqué dans tous les algorithmes où la vitesse d'exécution et la compacité du code sont des facteurs déterminants, la carte à microcircuit étant un parfait exemple d'application. Revendications 1. Procédé de décalage d'un mot constitué d'un nombre pair n de bits non multiple de huit pour un traitement de données réalisé au moyen d'un microprocesseur disposant d'une instruction du type test de bit, caractérisé en ce qu'il est effectué par une duplication croisée et symétrique des bits extrémes aux emplacements des bits non significatifs pour obtenir un mot constitué d'un nombre n' de bits multiple de huit, sur lequel est d'abord effectué un test pour positionner le report au moyen de l'instruction du type test de bit, puis est effectué un nombre m de décalages avec report, à droite ou à gauche selon le choix désiré. 2. procédé de décalage d'un mot constitué d'un nombre pair de bits non multiple de huit selon la revendication 1 caractérisé par le fait que pour l'exécution d'un décalage de l'intégralité d'un mot traité, le nombre m est égal au rapport entier n'/8x, x entier variant de 1 à i selon la capacité de traitement du microprocesseur. 3. Carte à microcircuit protégée par chiffrement utilisant le système DES comportant un microprocesseur muni d'une mémoire programme pour la mise en application du procédé conforme à la revendication 1 ou 2.