Brevet FR2657481A1 — publié le 19910726

Procédé de rotation d'un mot constitué de "p' éléments binaires et dispositif dans lequel ledit procédé est mis en oeuvre. Description La présente invention concerne un procédé de rotation d'un mot constitué de "p" éléments binaires (bo à bu~1) disposé depuis une position P(i) jusqu'à une position P(i+p-1) dans un format global prévu pour contenir (p+n) éléments binaires disposés selon les positions P(I) à P(p+n), format global constitué de k format(s) élémentaire(s) FE(j), (j = 1... k) formé(s) de x éléments binaires kx = p+n. Un tel procédé trouve d'importantes applications notamment pour effectuer des permutations circulaires d'éléments binaires d'une clef de codage à utiliser à l'intérieur d'une carte à microcircuit. L'ouvrage intitulé : "Les cartes à microcircuit" de F.GUEZ et al. édité en France aux Editions Manon, donne toutes explications pour ce genre de codage. On trouvera aussi dans l'ouvrage "Security for Computer Networksz de D.W. Davies et W.L. Price, édité par John WILLEY & SONS des renseignements plus précis concernant les algorithmes employés dans ces cartes à microcircuits. On est confronté, avec ce genre de carte, au problême du manque d'emplacement offert par le microcircuit. La place pour le stockage des informations de programmation reste réduite, aussi il importe que les divers sous-programmes ou routines faisant partie de ces informations soient de la plus petite taille possible et soient utilisés le plus souvent possible. Ce problème se pose avec plus d'acuité lorsqu'on doit traiter la clé de codage formée de deux demi-clés de 28 éléments binaires chacune alors que les messages à crypter ou à décrypter sont séparés en deux blocs de 32 éléments binaires chacun. Il existe donc une disparité entre le format de ces blocs 32 éléments binaires et des demi-clés 28 éléments binaires, qui peuvent s'étaler dans le format de 32 éléments binaires. Ce format de 32 éléments binaires est considéré comme un format global qui est constitué de formats élémentaires de 8 éléments binaires chacun, par exemple. On se rend compte alors qu'une opération de rotation sur ces demi-clés à l'intérieur du format global peut être gaspilleuse d'informations de programmation. Le but de la présente invention est de proposer un procédé du genre mentionné dans le préambule qui optimise la place pour le stockage des informations de programmation. Pour cela un tel procédé est remarquable en ce qu'il est effectué au moyen d'un microprocesseur disposant d'une instruction du type test d'un élément binaire dans le format élémentaire avec transfert de sa valeur dans un registre de report, en ce qu'il implique une phase de préparation qui consiste - à recopier dans les positions P(1) à P(i-l) les éléments bi naires disposés dans les positions P(p+1) à P(i+p-I) et dans les positions P(i+p) à P(p+n) les éléments binaires disposés dans les positions P(i) à P(n) si O naires disposés dans les positions P(p+l) à P(p+n) si i-l = n, à à recopier dans les positions P(p+l) à P(p+n) les éléments binaires disposés dans les positions P(1) à P(n) si i = 1, et en ce que la phase de rotation proprement dite consiste à à transférer dans le registre de report au moyen de ladite instruction de report l'élément binaire situé à la position P(n+1) pour une rotation dans un premier sens et à effectuer successivement une rotation dans ce premier sens de tous les formats éléments FE(k), FE(k-I),... FE(I) instruction de report l'élément binaire situé à la position P(p+n-i+l) pour une rotation dans un second sens et à effectuer successivement une rotation dans ce second sens de chaque format élément FE(1), FE(2),... FE(k). La présente invention concerne aussi un dispositif dans lequel ledit procédé est mis en oeuvre. La description suivante, accompagnée des dessins annexés, le tout donné à titre d'exemple non limitatif, fera bien comprendre comment l'invention peut être réalisée. La figure 1 montre un dispositif conforme à l'invention. La figure 2 explicite les instructions impliquées par le procédé de l'invention. La figure 3 explicite la constitution d'un format élémentaire. La figure 4 montre la disposition d'un mot à "p" éléments binaires placé dans un format global et le résultat de la phase préparatoire. La figure 5 explicite la rotation à gauche du mot à traiter. La figure 6 explicite la rotation à droite du mot à traiter. La figure 7 montre la permutation effectuée en combinaison avec la phase préparatoire dans le cadre de la carte à microcircuit. La référence 1 à la figure I montre le dispositif dans lequel le procédé est mis en oeuvre, dispositif qui peut être une carte à microcircuit. Le mot à traiter est une clef de codage formée de deux demi-clés de 28 éléments binaires chacune, la première demi-clé est contenue dans quatre registres à huit éléments binaires KO, K1, K2, K3 et la deuxième dans les registres K4... K7 faisant partie d'une mémoire vive 5. Une unité de traitement 8 opérant selon des instructions provenant d'une mémoire morte 10 effectue différents traitements notamment sur les données contenues dans les registres KO à K7 de 8 éléments binaires chacun. Sur la figure 1 on a aussi représenté les registres IPO à IP7, de 8 éléments binaires chacun aussi, à partir desquels les demi-clés sont traitées pour subir une étape de permutation qui sera explicitée par la suite. On a également noté par C le registre de report faisant partie de l'unité de trai tement 8 et par A, X, RI différents autres registres. Pour effectuer lesdites rotations sur ces clés, on utilise notamment les instructions de rotation opérant sur un format élémentaire FE de 8 éléments binaires. Les opérations de ces instructions sont schématisées à la figure 2. Sur cette figure on a représenté les deux rotations gauche et droite envisageables ROL et ROR. En ce qui concerne l'instruction ROL - en a on a représenté un mot d7 ... do contenu dans un format élémentaire de travail FE et un élément binaire "e" contenu dans un registre de report C avant l'exécution de l'instruc tion ROL, - en b l'instruction a été exécutée et le mot contenu dans le format FE est maintenant d6 d5 d4 d3 d2 d1 do e et le regis tre de report contient d7. En ce qui concerne l'instruction ROR les sens sont inversés ; de la position de départ d7 ...do on obtient e d7 d6 d5 d4 d3 d2 d1 avec contenu dans le registre C. Selon l'invention, on choisit comme unité de traitement 8 un microprocesseur qui comporte une instruction, du type BRSET ; par exemple le microprocesseur 6805 fabriqué par MOTOROLA comporte une telle instruction. Cette instruction permet de tester n'importe quel élément binaire nbo à nb7 contenu dans un registre de format élémentaire FE (figure 3) et cette valeur est transférée dans le registre C. il est alors possible de voir comment le procédé de l'invention peut être mis en oeuvre. Pour cela, on se reporte à la figure 4 qui montre comment est disposé le mot à traiter WI dans un format global FG formé de quatre formats élémentaires FE(1), FE(2), FE(3), FE(4) du type explicité à la figure 3, correspondant au format de travail du microprocesseur précité. Sur la figure 4, à la ligne a on a représenté par WI la clef initiale composée des éléments binaires bo-b27 (p =28) ; ce mot est codé dans les registres précités KO-K3 à huit éléments binaires, ce qui correspond au format élémentaire de travail du microprocesseur précité. Les quatre registres K0-K3 correspondent donc à un format global FG de 32 éléments binaires (p+n =32) répartis dans 32 positions de ce format repérées par P(1) à P(32) de gauche à droite. Le mot WI occupe, par exemple, les positions P(i) à P(i+p-1) avec i = 4, i+p#1 = 31. Le procédé de l'invention prévoit une phase de préparation qui consiste à renvoyer dans des positions du format global des éléments binaires du mot à traiter. Ainsi dans les positions P(1) à P(3) situées à gauche du format global on recopie les éléments binaires du mot WI situés dans les positions P(29) à P(31) c'est-à-dire que les éléments binaires b25, b26, b27 se retrouvent aux positions P(1), P(2) et P(3) conformément à ce qui est indiqué par la flèche Al. D'une manière similaire, l'élément binaire bo situé en P(4) occupe la position P(32) (comme montré par la flèche A2). La ligne b de la figure 4 montre la répartition des éléments binaires après cette phase préparatoire. La figure 5 illustre la manière dont est exécutée une rotation à gauche. Pour cela, on commence à tester l'élément binaire qui suit ceux qui ont été recopiés dans la partie droite c'est-à-dire que, dans cet exemple, on teste l'élément binaire b1 situé à la position P(5). Du fait de ce test, la valeur de cet élément binaire est enregistrée dans le registre C (voir flèche A3). il est facile maintenant de comprendre en partant de la ligne b, en effectuant quatre rotations ROL et en examinant les lignes c, d, e et f comment la rotation du mot est obtenue. Il faut remarquer que le mot WO de la ligne f résultant de l'opération1 peut subir des rotations à droite et à gauche sans nécessiter de phase préparatoire. La figure 6 indique une rotation à droite. On admet ici que la phase préparatoire a déjà été effectuée et que le mot à traiter occupe toujours les positions P(4) à P(31). Ici on teste l'élément binaire b24 placé à la position P(28), sa valeur est recopiée dans le registre C de sorte qu'on peut exécuter l'opération ROR aux différents registres KO ligne c,... K3 ligne d, le mot W0 est indiqué à la ligne e. Les différentes phases du procédé de l'invention sont maintenant expliquées selon les instructions du microprocesseur 6805 précédemment cité. 1) Phase préparatoire Commentaires AND K3 1 1 1 1 1 1 1 O } la position P(32) (registre K3) STA K3 est mise à zéro AND K0 0 0 0 1 1 1 1 1 } les positions P(1), P(2), P(3) STA KO (registre KO) sont mises à zéro AND KO O 0 0 1 0 0 0 l'élément binaire bo est isolé ROR A ROR A ROR A l'élément binaire se retrouve à droite dans l'accumulateur A EOX K3 STA K3 l'élément binaire bo occupe la po sition P(32) AND K3 0 0 0 1 1 1 O les éléments binaires b251 b261 b27 sont isolés ROL A ROL A ROL A les éléments binaires b25, b261 b27 sont placés à gauche EOX KO STA KO les éléments binaires b25, b26, b27 occupent les positionsP(1), P(2), P(3). 2) Rotation à rauche Commentaires BRSET 4, KO, "lblG" on teste l'élément binaire à la position P(5), quelle que soit sa valeur, on exécute l'instruction situé à l'étiquette "lblG" "lblG" ROL K3 ROL K2 ROL KI ROL KO 3) Rotation à droite BRSET 3, K3, "lblR" on teste l'élément binaire situé à WlblRW ROR KO la position P(28). ROR K1 ROR K2 ROR K3 il est bien évident que le mot à traiter peut occuper n'importe quelle place dans le format global - soit être centré c'est-à-dire occuper les positions P(3) à P(30), - soit être situé en butée à l'une des extrémités par exemple occuper les positions P(5) à P(32), ce qui permet d'avoir une phase préparatoire plus rapide. En outre l'invention concerne aussi le cas où le format global est confondu avec le format élémentaire, le mot à traiter est alors contenu dans un seul registre. La rotation des deux demi-clés peut s'écrire alors en utilisant la notation en usage pour le type de microprocesseur précité, de la manière suivante pour les rotations à gauche. Le nombre de rotations à effectuer est fixé par le contenu du registre A "encî" BRSET 4, K4 "enc2" "enc2" ROL K7 ROL K6 ROL K5 ROL K4 BRSET 4, KO "enc3" enc3" ROL K3 ROL K2 ROL K1 ROL KO DECA on diminue d'une unité le contenu du registre A BNE N enc1" RTS pour les rotations à droite dont le nombre est aussi fixé par le contenu du registre A "deux" BRSET 3 K3 "dec2" "dec2" ROR KO ROR ROR K2 ROR K3 BRSET 3 K7 "dec3" "des3" ROR K4 ROR K5 ROR K6 ROR K7 DECA BNE "deci" RTS Selon une caractéristique importante de l'inven- tion, la phase préparatoire peut être combinée avec la première permutation effectuée sur les clés ; on pourra se reporter à la page 59 et notamment au tableau 3 de l'ouvrage précédemment cité comme deuxième référence. Les deux demi-clés sont entrées dans des registres IPO à IP7 comme indiqué à la figure 7 en a. Les chiffres progressant de gauche à droite et de haut en bas donnent l'ordre initial des éléments binaires composant les deux demi-clés KKI et KK2. Les zones hachurées représentent les éléments binaires à supprimer. En b à la figure 7 on représente les deux demi-clés KK1P et KK2P qui ont subi la permutation et sont préparées comme précédemment, seule la permutation de la clé KK1 est montrée en détail. On donne ci-dessous les instructions concernant cette phase préparatoire préférée. 4) Phase préparatoire préférée combinée avec une permutation Commentaires "psi" LDX #7 STX R1 "pc11" LDX R1 LDA IP X la concaténation de IP avec le contenu de X donne la référence du registre IPO à IP7 LDX "pc12" LSRA ROL K X la concaténation de K avec (X) donne la référence de l'un des re gistres KO à K7 DECX BPL "pc12" on revient à l'étiquette "pc12" 7 fois DEC R1 BPL "pc11" et on revient aussi 7 fois à l'étiquette "pcîî". LDA K4 LDX K6 STX K4 STA K6 LDX K3 LSLX LSLX LSLX LSLX STX K7 tDA BSR "dec1" on exécute la rotation droite dé finie ci-dessus. LDA BSI "encî" on exécute la rotation gauche dé finie ci-dessus. RTS Ainsi on se rend compte que la rotation conforme à l'invention est pleinement utilisée dans les procédures de cryptage/décryptage mises en oeuvre à l'intérieur de la carte à microcircuit. Revendications 1. Procédé de rotation d'un mot constitué de "p" éléments binaires (bo à bu~1) disposé depuis une position P(i) jusqu'à une position P(i+p-î) dans un format global prévu pour contenir (p+n) éléments binaires disposés selon les positions P(1) à P(ptn), format global constitué de k format(s) élémentaire(s) FE(j), (j = 1... k) formé(s) de x éléments binaires kx = p+n, procédé caractérisé en ce qu'il est effectué au moyen d'un microprocesseur disposant d'une instruction du type test d'un élément binaire dans le format élémentaire avec transfert de sa valeur dans un registre de report, en ce qu'il implique une phase de préparation qui consiste - à recopier dans les positions P(1) à P(i-1) les éléments bi naires disposés dans les positions P(p+l) à P(i+p-1) et dans les positions P(i+p) à P(p+n) les éléments binaires disposés dans les positions P(i) à P(n) si O naires disposés dans les positions P(p+l) à P(p+n) si i-l = n, - à recopier dans les positions P(p+1) à P(p+n) les éléments binaires disposés dans les positions P(1) à P(n) si i = 1, et en ce que la phase de rotation proprement dite consiste - à transférer dans le registre de report au moyen de ladite instruction de report l'élément binaire situé à la position P(n+l) pour une rotation dans un premier sens et à effectuer successivement une rotation dans ce premier sens de tous les formats éléments FE(k), FE(k-I),... FE(1), - à transférer dans le registre de report au moyen de ladite instruction de report l'élément binaire situé à la position P(p+n-i+1) pour une rotation dans un second sens et à effectuer successivement une rotation dans ce second sens de chaque format élément FE(1), FE(2),... FE(k). 2. Procédé de rotation selon la revendication 1 destiné à être combiné avec un procédé de cryptage/décryptage comportant une étape de permutation, caractérisé en ce que la phase de préparation est combinée avec l'étape de permutation. 3. Dispositif pour la mise en oeuvre du procédé de la revendication I ou 2, caractérisé en ce qu'il comporte un ensemble de registres pour le format global formé d'au moins un registre au format élémentaire, un microprocesseur pour exécuter au moins des instructions de rotation droite, de rotation gauche et une instruction de transfert d'élément binaire dans un registre de report et une mémoire morte pour contenir des instructions nécessaires pour la mise en oeuvre dudit procédé