Brevet FR2757969A1 — publié le 19980703

La présente invention concerne un procéde et un appareil de multiplication d'éléments d'un champ fini et, en particulier, de multiplication d'éléments d'un champ fini dans un processeur dont la capacité de calcul est limitée, par exemple une carte intelligente, et dans lequel ces calculs font partie d'un système de cryptographie. L'arithmétique en champs finis est largement utilisée dans des applications comme la théorie du codage et la cryptographie. Des systèmes cryptographiques utilisent en particulier largement une arithmétique modulaire. L'exécution de calculs selon une arithmétique modulo n est semblable à l'exécution d'une arithmétique normale en ce qu'elle est commutative, associative et distributive. Une arithmétique modulaire est également plus facile à mettre en oeuvre puisque les plages de valeurs intermédiaires et les résultats, pour l'addition, la multiplication et la soustraction, sont limités. Ceci est particulièrement important lorsque les calculs sont mis en oeuvre sur un processeur à longueur de registre et à vitesse limitées. En arithmétique modulaire, l'ensemble des entiers modulo m est désigné par Fm = (0, 1, 2,.., m -l}. Lorsque m est un nombre premier p, l'ensemble des entiers modulo p, Fp forme un champ fini dans lequel on peut exécuter des opérations d'addition, de multiplication et de soustraction. En outre, si Fp = (0, 1, 2,.., p -1)} et si Ci est un élément de Fp, l'ensemble de polynômes en x o les coefficients proviennent de Fp est Fp[X] = (Cnxn+ +...+ Col Ci e Fp,n > 0). Comme défini ci-dessus, lorsque l'arithmétique est effectuée modulo un entier premier p, des cryptographes peuvent également utiliser en arithmétique modulo un polynôme irréductible f(x) de degré n dont les coefficients sont des entiers modulo q, o q est premier. Ces champs sont désignés symboliquement par F(qn). Ainsi, toute l'arithmétique est effectuée modulo une certaine f(x), qui est un polynôme irréductible de degré n et dans laquelle les coefficients du polynôme sont des éléments d'un champ fini. Si q est égal à 2, le calcul dans F(2n) peut être rapidement mis en oeuvre dans un matériel à registres à décalage à rétroaction linéaire. Pour cette raison, un calcul d'un F(2n) est souvent plus rapide qu'un calcul par F(p). Les valeurs de n qui produisent un système cryptographique faisable tendent à être relativement grandes. Des champs finis utilisés en cryptographie sont typiquement choisis parmi les champs à caractéristique deux, puisqu'ils se prêtent à des équipements et des processeurs linéaires. Une autre spécialisation du champ de caractéristique deux concerne ceux qui possèdent une base normale optimale, soit du type I, soit du type II. Des bases du type I qui sont des bases normales optimales qui possèdent la caractéristique que les coefficients d'un polynôme exprimé en termes d'une base polynomiale sont les coefficients permutés du polynôme exprimé en termes d'une base normale. Un champ fini peut être construit à partir d'un élément générateur a et est composé d'un espace vectoriel des puissances de a modulo le polynôme irréductible f(x) de degré n. Par exemple F23 possède les éléments suivants: 0, 1, x, x + 1, x2, x2 + 1, x2 + x, x2 + x + 1. Les puissances composantes de a peuvent alors être réduites à un degré inférieur à n au moyen du polynôme irréductible. Ces composants sont appelés la base et, pour un champ sur le champ binaire de deux éléments, les coefficients de la base sont simplement des zéros et des uns. Si le n- tuple résultant de coefficients est ordonné en correspondance avec la séquence ao, a1,... an-1, le champ a été représenté en ordre polynomial. Si les coefficients sont, en revanche, ordonnés pour correspondre à la séquence a2, a2, ..., a2 lorsque ces puissances sont de base normale pour le champ fini, la représentation est en ordre de base normale. Cette représentation offre plusieurs avantages pour une mise en oeuvre sous forme de matériel et elle est décrite plus complètement dans la demande de brevet du Royaume Uni GB 2 176 325. Pour la mise en oeuvre sur un processeur binaire, les composants sont typiquement répartis parmi plusieurs mots de processeur (qui peuvent être considérés comme un registre à mots multiples), puisqu'un mot unique de processeur n'est pas suffisant pour contenir tous les composants si la longueur du champ fini est même modérément grande. La longueur de ces registres dépasse cent bits, même pour des crypto- systèmes efficaces à courbe elliptique. Des systèmes à cartes intelligentes sont typiquement très pauvres en mémoire, au moins en ce qui concerne la mémoire vive ou RAM, et la présente invention résulte, sans y être limitée, du travail des inventeurs pour mettre en oeuvre des systèmes à clé publique dans de tels environnements. De plus, les processeurs disponibles dans de tels systèmes ne sont pas typiquement de puissance élevée, de sorte qu'il est important de développer des procédés efficaces qui peuvent être utiles dans cet environnement. C'est le but de la présente invention que de fournir un procédé de multiplication d'éléments de champs finis sur un processeur à capacité limitée de traitement, par exemple une carte intelligente ou similaire. Selon la présente invention, il est fourni un procédé de détermination du produit de deux éléments B et C à champs finis modulo un polynôme irréductible fl(x) o les éléments B et C de champs finis sont représentés en termes d'une base normale optimale du type I pour une dimension de champ n sur le champ binaire et comportant un polynôme irréductible f1l(x) de degré n, le procédé comprenant les étapes consistant a: a) représenter l'élément B sous forme de vecteur de chiffres binaires bi, o bi est le coefficient de a2 dans une base normale optimale de représentation du type I de B et o les bi sont en ordre polynomial; b) représenter l'élément C sous forme de vecteur de chiffres binaires ci, o ci est le coefficient de a2l dans une base normale optimale de représentation du type I de C et o les ci sont en ordre polynomial; c) représenter sous forme de vecteur di de chiffres binaires le produit partiel A d'un i-ième composant bi de l'élément B par l'élément C d) réduire le produit partiel A par un multiple f2(x) du polynôme irréductible fl(x); e) ajouter au produit partiel réduit de l'étape d) le produit partiel, par l'élément C, d'un composant successif bi_ de B; f) répéter les étapes d) et e) pour des chiffres successifs parmi les chiffres binaires de B; g) tester le bit supérieur du produit partiel A; et h) réduire l'élément A par le polynôme irréductible fl(x) si le bit supérieur est placé, grâce à quoi A représente le produit des deux éléments B et C à champs finis, modulo fl(x). On va maintenant décrire des modes de réalisation de l'invention à titre d'exemple seulement en se référant aux dessins annexés dans lesquels: la Figure 1 est un schéma logique qui représente la multiplication de deux éléments de champs finis; la Figure 2 est un schéma fonctionnel d'un multiplicateur destiné à mettre en oeuvre une multiplication de deux éléments dans le champ F(2n); et Figure 3 est un exemple qui illustre une opération d'élévation au carre. La description suivante fournit une vue d'ensemble d'une multiplication polynomiale modulo un polynôme irréductible fl(x). Une multiplication de deux champs finis est effectuée communément en choisissant l'un des deux éléments comme multiplicateur et l'autre élément comme multiplicande. D'une manière analogue aux chiffres dans le cas d'une multiplication de nombres en utilisant un calcul manuel, les composants du multiplicateur sont utilisés pour mettre à l'échelle le multiplicande, qui est décalé selon la position du composant concerné de multiplicateur, et les résultats sont ajoutés entre eux en produits partiels. La multiplication de polynômes binaires est entièrement analogue, sauf qu'aucun report entre positions n'est impliqué, et que des additions par composants consistent en simples opérations exclusive-OU. Des composants du multiplicateur peuvent être utilisés dans un ordre quelconque pour composer des produits partiels; typiquement ils sont utilisés dans l'ordre ascendant (ou parfois descendant), comme illustré dans l'exemple qui suit o les polynômes B et C à multiplier peuvent être représentés de la façon suivante: B = x4 + x3 + x1 + x (1) C = x3 + x2 + xO (2) En prenant simplement les coefficients des polynômes et en y effectuant une multiplication 1101 1 1 on obtient le résultat A x7 + x5 + x3 + x2 + xl + x0 (3) Lorsque deux polynômes doivent être multipliés modulo un autre polynôme (le polynôme irréductible dans le cas de champs finis) une réduction au moyen de ce polynôme est effectuée pour atteindre le résultat final. Cette réduction peut être effectuée sur le résultat final, ou sur des composants des produits partiels. Si le polynôme irréductible est fl(X) = X4 + X3 + X2 + xl + X0 (4) la représentation binaire de ses coefficients est 11111. Pour réduire les résultats, ou des intermédiaires, des multiples de l'irréductible sont soustraits du résultat, ou d'intermédiaires, jusqu'à ce que le degré soit réduit au-dessous de n, le degré de l'irréductible. Dans le cas d'une caractéristique deux, cette opération est identique à une addition. Le résultat A de l'équation (3) peut être réduit en utilisant le polynôme (4) en produisant le résultat ilii! 1 o 1 O 1 1 1 1 111 A x3 + xi(5) Lorsque des réductions sont effectuées à chaque étape d'établissement des produits partiels, il est efficace de composer les produits partiels en utilisant les composants du multiplicateur en ordre descendant. En se référant au schéma logique de la Figure 1, on peut voir que le nombre de réductions est réduit avec cette configuration, puisque tous composants additionnels qui résultent de la réduction des composants supérieurs peuvent être ajoutés entre eux et réduits tandis que les composants plus bas du produit sont réduits. De plus, il n'est pas nécessaire de décaler le multiplicande au fur et à mesure que les produits partiels sont composés dans cette configuration, et il n'est pas nécessaire non plus que le registre contenant le produit partiel soit d'une longueur double de celle des registres du multiplicateur et du multiplicande. Au contraire, le registre qui accumule les produits partiels peut être décalé pour le préparer à accepter l'addition du produit partiel suivant au fur et à mesure que les composants du multiplicateur sont utilisés. Afin de réduire les étapes de calcul nécessaires pour réduire les produits partiels (ou à toute autre étape), l'utilisation de polynômes irréductibles à coefficients minimaux non nuls est souvent employée. Les polynômes irréductibles de poids minimal sont les polynômes à trois termes non nuls, que l'on appelle les trinômes. Pour un champ de Galois F(2n), les cryptographes aiment utiliser le trinôme xn + xk + 1. Ces polynômes ont été proposés pour la cryptographie en raison de leur rétroaction minimale dans les termes d'ordre inférieur du polynôme au fur et à mesure que la réduction progresse. En se référant maintenant à la Figure 2, et à l'exposé qui suit, on va maintenant décrire un mode de réalisation conforme à la présente invention. Le tableau 1 représente une liste de valeurs de n au moyen du polynôme f2(x). Lorsque ceci est approprié pour le calcul qui suit, la réduction peut être complétée en employant le polynôme irréductible lui-même, c'est-à-dire en utilisant fl(x) et non f2(x). Cette opération est simple et efficace également, et elle est mise en oeuvre en testant le composant, ou bit, supérieur de l'élément partiellement réduit, c'est- à-dire réduit au moyen du polynôme f2(x), et en prenant le complément de chaque composant, ou bit, du résultat si ce bit de composant supérieur est non nul. Le degré du résultat est ainsi réduit à n - 1. Selon un autre mode de réalisation de l'invention, le multiplicateur peut être traité au préalable avant que le processus de multiplication ne soit lancé. Puisque le polynôme fl(x) est équivalent à zéro dans le champ fini, il peut être ajouté au multiplicateur sans affecter le résultat du calcul. En ce qui concerne l'effort de calcul, il est avantageux que le nombre de composants, ou bits, non nuls du multiplicateur soit réduit. Par conséquent, si le nombre de uns dans le registre de multiplicateur est supérieur à la quantité n/2, ajouter le polynôme fl1(x) à la représentation réduit le nombre d'éléments non nuls à une quantité égale ou inférieure à cette même quantité, puisque cette opération d'addition exerce l'effet de prendre des compléments des composants de la représentation, jusqu'au composant de degré n. Cette prise de complément est également calculable avec un rendement intéressant sur une machine qui est capable d'opérations binaires sur les mots de la représentation. Comme on peut le voir de ce qui suit, par exemple si n = 10 et f1(x) = x10 + x9 +... + x2 + x + 1 et si le multiplicateur est b = x9 + x8 + x6 + x4 + x3 + x2 + x1 + 1 alors, modulo fl, un multiplicateur équivalent mais plus efficace est b' = b + fi = x10O + X7 + x5 Comme représenté à la Figure 2, un schéma d'un processeur est désigné généralement par la référence numérique 100, pour déterminer le produit de deux éléments B et C de champs finis modulo un polynôme irréductible fl(x) ou les éléments B et C de champs finis peuvent être représentés en termes d'une base normale optimale du type I pour une dimension de champ n sur le champ binaire et comportant un polynôme irréductible fl(x) de degré n. Le processeur 100 inclut un premier et un deuxième registres polyvalents 102 et 104 respectivement. Il est prévu un registre accumulateur 106 et celui-ci est couplé à une unité arithmétique et logique, ou ALU, 108 par l'intermédiaire d'un trajet de données 120 et 122 respectivement. Un trajet 124 de données de sortie est agencé, à partir de la sortie de l'unité arithmétique et logique, vers les registres et l'accumulateur 106. Chacun des registres est susceptible d'un fonctionnement à décalage de bit. L'élément B qui est appelé le multiplicateur, et qui est un vecteur de chiffres binaires bi, o bi est le coefficient de a2 dans une représentation à base optimale normale de type I de B et o les bi sont en ordre polynomial, est mémorisé dans un registre 102 d'une longueur d'au moins n + 1 bits. L'élément C qui est appelé le multiplicande, et qui est un vecteur de chiffres binaires ci, o ci est le coefficient de a2 dans une représentation à base optimale normale de type I de C et o les ci en ordre polynomial, est mémorisé dans un registre 104 d'une longueur d'au moins n + 1 bits. Un accumulateur A est également agencé pour mémoriser sous forme de vecteur de chiffres binaires di le produit partiel A d'un i-ième composant bi de l'élément B et de l'élément C. La longueur de l'accumulateur A 106 est d'au moins n + 1 bits, mais elle pourrait dans certains cas être plus longue si le processeur était capable d'opérations d'une longueur de mot. Des entrées à l'unité arithmétique et logique 108 sont fournies à partir du registre 104 de multiplicande et du registre 106 d'accumulateur. L'unité arithmétique et logique 108 ajoute ses entrées, c'est-à-dire qu'elle effectue sur celles-ci une opération EXOR, pour produire un résultat qui est renvoyé pour être mémorisé dans l'accumulateur 106. En cours de fonctionnement, les éléments B et C sont mémorisés dans leurs registres respectifs. Un signal sélecteur 110 de bit au registre 102 de multiplicateur est placé d'une façon telle que le bit situé le plus à gauche du multiplicateur est sélectionné. Ici, un bit significatif augmente de la droite vers la gauche. Le bit bm est sélectionné et multiplié par le contenu complet du multiplicande C. Ce résultat est ensuite additionné, c'est-à-dire traité par opération EXOR, avec le contenu de l'accumulateur A. En fait, si bi est 1, B est ajouté à l'accumulateur, ou sinon, si bi est 0, 0 peut être ajouté à l'accumulateur, ou cette opération peut être sautée. L'opération d'addition est commandée par un signal de commande 109 d'addition à l'accumulateur. Le processus de multiplication et d'addition à l'accumulateur forme les produits partiels de chaque étape de multiplication intermédiaire. Puis, le contenu de l'accumulateur est décalé vers la gauche en appliquant à l'accumulateur un signal 114 de décalage vers la gauche, qui est l'équivalent d'une multiplication par un facteur x. Le bit le plus élevé est reporté dans la position inférieure de l'accumulateur 106, comme représenté par la référence numérique 112 à la Figure 2. Le déplacement de bit supérieur vers la position de bit inférieure est équivalent à une réduction intermédiaire du résultat par f2(x), comme exposé précédemment. Ce processus est répété pour des bits successifs du multiplicateur. Le report du bit le plus élevé vers la position inférieure de l'accumulateur peut être retardé jusqu'à ce qu'un mot complet de bits composants au-delà de n bits soit accumulé, ce mot de débordement pouvant ensuite être enlevé et envoyé par opération EXOR vers le bas du registre A. Le sélecteur de bit sur le multiplicateur est décalé d'un bit, moins significatif ou de poids moindre, vers la droite et le processus est répété de la même manière et pour chaque bit de poids moindre de b jusqu'à ce que les bits de b soient épuisés. Lorsque ceci est achevé, le bit supérieur de l'accumulateur est testé et, s'il est placé, le contenu de l'accumulateur est inversé, ce qui est équivalent à une réduction finale par fl(x). Si le bit supérieur n'est pas placé, le résultat dans l'accumulateur est le produit final modulo l'irréductible. Comme mentionné précédemment, selon un autre mode de réalisation, un signal de complément 119 peut être envoyé au multiplicateur si le nombre de uns dans le multiplicateur est supérieur à n/2. D'une façon plus générale, cependant, si l'une ou l'autre des entrées du multiplicateur comprend plus de n/2 composants qui sont non nuls, c'est-à-dire qui sont des uns, il est possible de prendre le complément de cette entrée. Par conséquent, l'élément qui comprend le moindre nombre de uns peut être sélectionné comme multiplicateur et cette sélection peut aussi inclure les composants. Le carré d'un élément peut être calculé exactement de la même manière que la multiplication décrite ci-dessus. Lors de la multiplication d'un élément de champ fini par lui-même, il se produit des simplifications qui rendent le calcul beaucoup plus efficace, du point de vue des possibilités de calcul, que la multiplication décrite ci-dessus qui n'est pas une élévation au carré. La représentation de base normale d'un élément offre l'avantage qu'une élévation au carré peut être calculée simplement par un décalage cyclique de la représentation, qui est maintenue dans l'ordre de base normal. Lorsque l'on dispose de peu de mémoire, ceci non seulement offre l'avantage d'une extrême simplicité et d'une extrême vitesse, mais permet également d'élever des éléments au carre, ou d'en calculer la racine carrée par inversion du processus, en place, c'est-à-dire qu'aucun registre additionnel n'est requis pour contenir le résultat. Si un élément B à élever au carré est représenté sous forme polynomiale, par n B = E biXi (8) i = O Le carré de l'élément est n/2 n B = E biX2i + biX2(i-n/2)-l (9) i = 0 i = n/2+l On va maintenant décrire un mode de réalisation de l'invention pour effectuer, en place, une élévation au carré, et aussi une extraction de racine carrée par inversion du processus, d'un élément à champ fini à ONB de type I, représenté en ordre polynomial. Lors d'une élévation au carré d'un élément dans un champ à caractéristique deux, les termes de produits croisés deviennent tous zéro puisqu'ils apparaissent deux fois, en utilisant le fait que 2 devient 0 dans un champ à caractéristique deux. L'effet en est que la première étape de mise au carré peut être calculée en imbriquant des zéros et en réduisant. Comme dans le cas de la multiplication entre éléments non identiques, on réduit en premier lieu au moyen du polynôme f2(x). Ainsi, en continuant l'exemple pour n = 10, si les coefficients d'un élément B peuvent être représentés en ordre ascendant par 01011010110, élever au carré implique d'imbriquer des zéros à droite de chaque élément de la manière suivante 000100101000100010100. Ce résultat peut ensuite être réduit au moyen du polynôme f2(x), constitué par les coefficients qui sont 0010001010, les n composants au-dessus des n + 1 composants du composant imbriqué. Ceci exige malheureusement, pour effectuer l'opération, un registre de longueur double, ou un registre de source et un registre de destination. Si un tel registre de longueur double est disponible, la réduction partielle au moyen de f2(x) est rendue très efficace en réduisant mot par mot, en ordre décroissant, comme c'était le cas dans la multiplication précédente. La réduction partielle au moyen de f2(x) offre l'avantage que, par le processus de l'opération d'élévation au carré, en partant du composant le plus bas, ou de degré zéro, les composants de degré [0, 1, n/2] sont repositionnés dans l'ordre aux composants pairs [0, 2, 4,... n] car n est pair pour une ONB du type I, et que les composants restants [n/2 + 1, n/2 + 2,... n] sont repositionnés dans l'ordre aux composants impairs [1, 3, 5,... n - 1]. On peut également voir ceci de l'équation (9). On utilisera ce fait pour réaliser une deuxième opération d'élévation au carré qui offre l'avantage que le calcul peut être effectué en place. Pour élever au carré en place, on aligne en premier lieu la deuxième moitié de la représentation à des limites de mot d'une façon telle que la partie supérieure, c'est-à-dire la partie [0, 1,..., n/2] qui contribue aux emplacements impairs, commence sur une frontière de mot. A cet effet, toute partie inutilisée du mot le plus haut, et peut être d'un mot additionnel, peuvent être nécessaires tandis que la moitié supérieure des composants est décalée vers le haut vers une frontière de mot. Par exemple, si un mot est d'une longueur d'un octet, un composant B = 01011010110 peut être mémorisé comme 0000101100010110. Cette représentation peut être divisée en mots représentés de la façon suivante: O1 = 0000, o0 = 1011, el = 0001, e0 = 0110 Ces composants entrelacés avec des zéros peuvent être représentés de la manière suivante: ô1 = 00000000, 60 = 10001010,l = 00000001, êO = 00010100 A cet instant, les composants qui ont été positionnes aux emplacements impairs sont tous dans l'ordre dans la moitié inférieure du registre et, par défaut, alignés en mot, tandis que les composants qui contribuent aux emplacements impairs sont tous dans l'ordre dans la moitié supérieure du registre, et aussi de préférence alignés en mot. Les composants sont maintenant imbriqués en place. Considérons les mots du registre comme étant appairés entre eux, le mot inférieur de la moitié inférieure appairé avec le mot inférieur de la moitié supérieure, cet appariement progressant vers le haut pour toutes les paires. Considérons la première paire, le mot du registre inférieur contribue des composants aux emplacements pairs du zéro-ième mot du résultat, ainsi qu'aux emplacements pairs du mot suivant du résultat, le numérotage commençant ici à zéro. Le mot situé en haut du registre contribue de même des composants aux emplacements inférieurs du zéro-ième mot du résultat et aux composants impairs du mot suivant du résultat. En d'autres termes, le mot inférieur de la paire est constitué par la concaténation ele0 et le mot supérieur par la paire de OlO o e0 est la moitié inférieure du mot, en supposant que la dimension du mot est paire, qui ne contribue qu'aux emplacements pairs du zéro-ième mot et el ne contribue qu'aux emplacements pairs du mot suivant. Les moitiés OlO de mot contribuent de même aux emplacements impairs de mot zéro et un respectivement. Soit maintenant êO les composants de e0 imbriqués avec des zéros d'une façon telle que les composants de eo0 sont aux emplacements pairs du mot, soit êl exactement le même mot, sauf qu'il utilise les composants de el. Soit de même 60 constitué des composants de o0 positionnes aux emplacements impaires, et soit aussi ô1 composé de façon semblable. Selon un autre mode de réalisation, des paires de (OLO0, eleo) peuvent être traitées pour produire la paire de mots (ô10êl, ô00êO). Selon un mode de réalisation préféré, une table à consulter, appelée simplement table dans ce qui suit, d'une dimension égale à la moitié de la dimension du mot, peut être utilisée pour produire des composants imbriqués avec zéro. En variante, un matériel peut être introduit pour effectuer l'imbrication. Positionner à des emplacements impairs est effectué ensuite au moyen d'un déplacement du mot, ou bien des emplacements pairs peuvent être produits au moyen d'un décalage si la table est établie pour produire des emplacements impairs imbriqués. A cet instant, les composants de mots sont à l'emplacement correct poproduire le carré, mais les mots eux-mêmes ne sont pas dans l'ordre correct. On se réfère maintenant à la Figure 3 o w0 désigne la valeur assemblée ôoo00êo0, w1 désigne ôo10êl et de même pour w2 et w3. Pour achever l'opération d'élévation au carré, on permute les mots du registre, ce qui peut impliquer des opérations de lecture et d'écriture de mots sur le processeur. Alors que la présente invention a été décrite en connexion avec son mode de réalisation spécifique et selon une utilisation spécifique, diverses modifications ressortiront l'homme de l'art sans s'écarter de l'esprit de l'invention exposé dans les revendications annexées. Les termes et expressions qui ont été employés dans la présente description sont utilisés à titre de termes de description et non à titre limitatif, puisqu'il n'existe aucune intention d'exclure, par l'utilisation de tels termes et expressions, tout équivalent des particularités représentées et décrites ou toute partie de ceux-ci, mais il est au contraire reconnu que diverses modifications sont possibles à l'intérieur du cadre des revendications de l'invention. II ad^l uouis II 'I ad,(i + I ad,L. + tNO0 aun u (uZ)j duiWqD al lanbal nod oooZ 5 u alq L 9661.98LI 0 OúSI.90ú1.8011 OL8.099 OL.Z6Z.901 t,661 58.LI.rzçS.00úI 9011 998 6S9.99V 18Z S01 9861 6LLI 8tI 56ZI ú011.858.859 *09t 8LZ.001 ú861 8LLI IISI. 06ZI.0601.ZS8 ú59 úSt úELZ 66 8L61 úLLI 6051 68ZI OLOI 9t8.ZS9 úEt OLZ 86 L.61 69LI St 0,ZgZl 5901 Kg8 1S9.Ztt *89Z S6 05 ZL.61 99LI 6611 8LZI.0901 ú8 059 I"t' 19Z 06 5961 ú9LI *86I1 *9LZI 5501 Iú8 5t9 8EtV SZ 68 1961 85LI.Z6PI SULZI 6t01.8Z8 119 IEt 15Z 98 6561 SSLI.Z8l, U t1ZI ú LO1.9Z8 6E9 6Zt 5tZ ú8 8561 6,4/ 18"1 ILZI It01.0Z8 8E9 9Zt, tZ. Z8 S561.9, LI LP1I 69Z 1 tú01 818 6Z9.OZtV 6úZ 18 ú561 St1LI 69 1 59I 1 IúI 018 +819 61V úZ L c 8Àt61,LI ú9VI '.8SZI 9ZOI1 608 519.81v IEZ 69 8ú61 tLI tSI ISZI 6101 ú08,19 li OcZ.99 Iú61 úLI.ZtI 8úZ1 *8101.96L *ZI19 úIt *9ZZ 59 0ú61.ZúLI ISPI.9úZI, IOI 16L. 119 11V IZZ.09 9Z61 OúLI.05i úúZI ú101.98L 909 OlPt +OIZ.8S Z61 90L.I útrI 6Z:Z I 866 58L ú65 86ú 60Z úS 0 LZ61 ú0LI 6útI.SZZI ú66 8L *98S ú6ú *961.ZS 9061.Z691 OúPI úZZI 686 6LL S85.88ú V61 IS 106t 5891 *9ZtI 81II 986 tLL SLS 98ú 161 OS *0061 6L.91 SZtI.ZIZI SL6.ZLL *Z9S.8Lú 681 1t 8681,L91 IZt1 IIZI 1b.6 ILL 195 +8/L 981 6ú 6881 *8991 SItl 6611 596 91L 855 SLú ú81 *9ú ú881 *9991 60t 1 '611 ú56 19L * 9S5 ZLú *081 5ú *9L8I 1991 I0TI.9811 OS6 *9SL S5 ILú 6LI úú +9981 6S91 86úI 511.9f6 55L,9VS 65ú *8Lt 0ú ú981 ú591 t'61 8LII.0f6 6CL S tVSC PLI 6Z 0981 6t91. 08ú1 *oOLI 6ú6 9/. úV 0N5ú úLI.8Z 681.991.ULIú1 6911 8ú6 úPL 0.OVtS.8.UI 9Z Vg1 9Z91 OLú1I 9911 Sú6 ItL IúS *9K.Z91 EZ 0581 OZ9I 6ú! SSII úú6 9ZL OúS 8úú 8SI +81 M1.8191 SSúI 1SII 0ú6 SZL.ZZS OúEC 55I t1 8ú8i 1091 úCSú1 9P11 Z6 úZL 61S 6Zú.8t, *ZI Sú81 ú6SI 6KI 1KII 116 61L SIS; 9ú 9I Il 6Z2I ú85I 9,I úúIi.906 ú1L 60S úZú.8úI.01 1Z81.OL.I IKI.ZZI1 ú68.80L *80S *91ú 5ú1 6 8181 6SSI 8úúI ItZl 168.00L S61 0ú K I 9 1181. 8tSI IúúI 6111.Zgg88 069 16t 90ú 1úI S 9081 ItSI 6Zú1 8111 6L.8 989.06t ú0C O 0úI. 16LI 6úSI ZCú1 *9111.9.L8 ú89 E8 66Z 61J ú 06LI úúSI OI 01ú 101 1 úL.8.9/9 ELt ú6Z ú 11 +Z 69,6LSLZT 696LSLZ REVENDICATION Procédé de détermination du produit de deux éléments B et C à champs finis modulo un polynôme irréductible fl(x) o les éléments B et C de champs finis sont représentés en termes d'une base normale optimale du type I pour une dimension de champ n sur le champ binaire et comportant un polynôme irréductible fl(x) de degré n, caractérisé en ce qu'il comprend les étapes consistant a: a) représenter l'élément B sous forme de vecteur de chiffres binaires bi, o bi est le coefficient de a2 dans une base normale optimale de représentation du type I de B et o les bi sont en ordre polynomial; b) représenter l'élément C sous forme de vecteur de chiffres binaires ci, o ci est le coefficient de a2 dans une base normale optimale de représentation du type I de C et o les ci sont en ordre polynomial; c) représenter sous forme de vecteur di de chiffres binaires le produit partiel A d'un i-ième composant bi de l'élément B par l'élément C d) réduire le produit partiel A par un multiple f2(x) du polynôme irréductible fl(x); e) ajouter au produit partiel réduit de l'étape d) le produit partiel, par l'élément C, d'un composant successif bi_ de B; f) répéter les étapes d) et e) pour des chiffres successifs parmi les chiffres binaires de B; g) tester le bit supérieur du produit partiel A; et h) réduire l'élément A par le polynôme irréductible fl(x) si le bit supérieur est placé, grâce à quoi A représente le produit des deux éléments B et C à champs finis, modulo fl(x).