Brevet FR2820851A1 — publié le 20020816

Méthode pour multiplier deux nombres binaires La présente invention concerne une méthode pour multiplier deux nombres représentés sous forme binaire. La multiplication est une opération arithmétique réalisée par les processeurs numériques au moyen d'opérations élémentaires telles que le décalage ou l'addition. La complexité d'une multiplication peut s'évaluer en estimant la quantité d'opérations élémentaires à effectuer pour parvenir au résultat. Elle dépend directement de la taille des deux nombres à multiplier. Ainsi, lorsqu'il s'agit de grands nombres, cette complexité affecte tant la puissance de calcul requise que le temps nécessaire à l'obtention du résultat. La présente invention a ainsi pour objet une méthode de multiplication présentant une complexité réduite. Selon l'invention, une méthode est prévue pour calculer le produit d'un premier et d'un second nombre binaire, le premier nombre résultant de la concaténation d'une première constante A et d'une première variable X de u bits, tous les bits de la première constante A étant égaux à 1, le deuxième nombre comportant s bits, méthode suivant laquelle ce produit résulte d'une suite d'opérations dont la plus complexe est une multiplication de u bits par s bits. En diminuant la taille des nombres à multiplier, quitte à devoir réaliser des opérations additionnelles, on diminue sensiblement la quantité d'opérations élémentaires à réaliser pour obtenir le produit. Selon une première option, la première constante A comportant 1 bits, la méthode comprend les opérations suivantes : - une première opération de décalage gauche de u bits du second nombre pour obtenir un premier opérande, - une deuxième opération de décalage gauche de 1 bits de ce premier opérande pour obtenir un deuxième opérande, - une troisième opération de multiplication de la première variable X par le second nombre pour obtenir un troisième opérande, - le produit résultant de la somme des deuxième et troisième opérandes à laquelle est retranchée le premier opérande. Avantageusement, lorsque le second nombre résulte de la concaténation d'une deuxième constante B dont les m bits valent 1 et d'une deuxième variable Y de v bits, le troisième opérande est obtenu au moyen des opérations suivantes : - une quatrième opération de décalage gauche de (v+m) bits de la première variable X pour obtenir un quatrième opérande, - une cinquième opération de décalage gauche de v bits et d'inversion de signe de la première variable X pour obtenir un cinquième opérande, - une sixième opération de multiplication des première X et seconde Y variables pour obtenir un sixième opérande, - le troisième opérande résultant de la somme des quatrième, cinquième et sixième opérandes. Selon une deuxième option, la première constante A comportant 1 bits, le second nombre résultant de la concaténation de la première constante A et d'une deuxième variable Y de u bits, la méthode comprend les opérations suivantes : - une première opération d'addition de la première variable X et du second nombre pour obtenir un premier opérande, - une deuxième opération de décalage gauche de (u+l) bits du premier opérande pour obtenir un deuxième opérande, - une troisième opération de décalage gauche de u bits et d'inversion de signe du premier opérande pour obtenir un troisième opérande, - une quatrième opération de multiplication de la première variable X par la seconde variable Y pour obtenir un quatrième opérande, - le produit résultant de la somme des deuxième, troisième et quatrième opérandes. Selon une troisième option, la première constante A comportant 1 bits, le second nombre résultant de la concaténation d'une deuxième constante B dont les m bits valent 1 et d'une deuxième variable Y de v bits, la méthode comprend les opérations suivantes : - une première opération de définition d'une premier opérande dont la valeur est 2exp (u+v+l+m)-2exo (u+v+l)-2exp (u+v+m) + 2exo (u+v), - une deuxième opération pour calculer un deuxième opérande valant (A. Y + B. X), - une troisième opération de multiplication de la première variable X par la seconde variable Y pour obtenir un troisième opérande, - le produit résultant de la somme des premier, deuxième et troisième opérandes. De préférence, le deuxième opérande résulte des opérations suivantes : - une quatrième opération de décalage gauche de (u+l) bits de la deuxième variable Y pour obtenir un quatrième opérande, - une cinquième opération de décalage gauche de u bits et d'inversion de signe de la deuxième variable Y pour obtenir un cinquième opérande, - une sixième opération de décalage gauche de (v+m) bits de la première variable X pour obtenir un sixième opérande, - une septième opération de décalage gauche de v bits et d'inversion de signe de la première variable X pour obtenir un septième opérande, - le deuxième opérande résultant de la somme des quatrième, cinquième, sixième et septième opérandes. Ou bien alors, la deuxième constante B étant égale à la première constante A, le nombre v de bits de la deuxième variable Y étant égal au nombre u de bits de la première variable X, le deuxième opérande résulte des opérations suivantes : - une quatrième opération d'addition des première X et deuxième Y variables pour obtenir un quatrième opérande, - une cinquième opération de décalage gauche de (u+l) bits du quatrième opérande pour obtenir un cinquième opérande, - une sixième opération de décalage gauche de u bits et d'inversion de signe du quatrième opérande pour obtenir un sixième opérande, - le deuxième opérande résultant de la somme des cinquième et sixième opérandes. Selon une quatrième option, les premier et second nombres étant égaux, la méthode comprend les opérations suivantes : - une première opération de définition d'un premier opérande dont la valeur est 2exp (2 (u+l))-2exp (2u+1+1) + 2exp (2u), une deuxième opération de décalage gauche de (u+1+1) bits de la première variable X pour obtenir un deuxième opérande, - une troisième opération de décalage gauche de (u+1) bits et d'inversion de signe de la première variable X pour obtenir un troisième opérande, - une quatrième opération d'élévation au carré de la première variable X pour obtenir un quatrième opérande, - le produit résultant de la somme des premier, deuxième, troisième et quatrième opérandes. L'invention vise également un dispositif comprenant des moyens pour mettre en oeuvre la méthode ci-dessus. Elle s'applique avantageusement à la cryptographie, notamment au chiffrement d'une signature. La présente invention apparaîtra maintenant avec plus de détails dans le cadre de la description qui suit d'exemples de réalisation donnés à titre illustratif en se référant aux figures annexées qui représentent : - la figure 1, une représentation des deux nombres binaires, et - la figure 2, un organigramme d'un procédé de chiffrement. Il convient, en premier lieu, de préciser que toutes les opérations décrites sont réalisées modulo n où n a une valeur prédéterminée. Il ne s'agit pas là d'une réelle limitation car toute latitude est permise pour le choix de cette valeur. D'autre part, pratiquement, les registres des processeurs ont une taille limitée, si bien que la plupart des opérations sont pratiquées modulo cette taille. En référence à la figure 1, le premier nombre F peut s'analyser comme la concaténation d'une première constante A et d'une première variable X. La constante A comporte 1 bits tous égaux à 1 et la variable X a une longueur de u bits. L'invention présente un avantage lorsque la valeur de 1 est supérieure à 1, bien qu'elle s'applique également dans le cas contraire. En notant aexpb a élevé à la puissance b, la constante A vaut : Le premier nombre F s'exprime ainsi : Le produit P du premier nombre F et du second nombre S de s bits devient : Le produit P s'analyse donc comme une somme algébrique de trois opérandes : Le premier opérande OP1 qui vaut 2expu. S s'obtient en pratiquant un décalage gauche sur le second nombre S de u bits et, naturellement, en forçant à 0 les u bits de poids faible du nombre décalé. Le deuxième opérande OP2 qui vaut 2exp (u+l). S s'obtient en pratiquant un décalage gauche de 1 bits sur le premier opérande. Le troisième opérande OP3 s'obtient en faisant la multiplication de la première variable X par le second nombre S, ceci au moyen d'une quelconque méthode connue. L'invention permet ainsi de substituer à une multiplication de (u+l) bits par s bits un ensemble d'opérations comprenant deux décalages, une inversion de signe, deux additions et une multiplication de u bits par s bits. L'avantage procuré par l'invention est d'autant plus sensible que 1 est grand. Le deuxième nombre S peut également s'analyser comme la concaténation d'une constante B et d'une variable Y. La constante B comporte m bits égaux à 1 et la variable Y a une longueur de v bits, le second nombre s'écrivant donc : Le troisième opérande de l'équation [1] devient : Le troisième opérande X. S s'analyse aussi comme la somme de trois opérandes, le quatrième opérande qui vaut 2exp (v+m). X qui s'obtient en pratiquant un décalage gauche sur la première variable X de (v+m) bits, le cinquième opérande qui vaut-2exov. X qui s'obtient en pratiquant un décalage gauche de v bits et une inversion de signe et le sixième opérande qui s'obtient en multipliant les première X et seconde Y variables. Dans ce cas, l'opération la plus complexe est une multiplication de u bits par v bits. Selon une première variante, l'invention tire avantage du fait que la deuxième constante B est égale à la première constante A et que la taille v de la deuxième variable Y est identique à la taille u de première variable X. Le produit P s'écrit alors : Le produit P est ici obtenu au moyen des quatre opérations suivantes. Un premier opérande est obtenu en additionnant la première variable X et de deuxième nombre S. Un deuxième opérande est obtenu par décalage gauche de (u+l) bits du premier opérande. Un troisième opérande est obtenu par décalage gauche de u bits et inversion de signe du premier opérande. Un quatrième opérande est obtenu par multiplication des première X et seconde Y variables. Finalement, le produit F est obtenu par addition de ces quatre opérandes. Selon une autre variante, l'invention considère encore que le premier F, respectivement le second nombre S, résultent de la concaténation d'une première constante A et d'une première variable X, respectivement d'une seconde constante B et d'une seconde variable Y. En reprenant les mêmes notations, le produit P s'écrit alors : Le produit P se présente ici également comme la somme de trois opérandes. Le premier opérande qui vaut A. B. 2e (u+v) se définit facilement comme MX tout nombre binaire exprimé par une suite de coefficients correspondant chacun à une puissance de 2. Le deuxième opérande vaut (A. 2expu. Y + B. 2expv. X) et) e troisième opérande est obtenu en multipliant les première X et seconde Y variables. Selon une première option le deuxième opérande est calculé directement à partir de l'expression 2exp (u+l). Y-2expu. Y + 2exp (v+m). X- 2edv. X Il faut ainsi procéder à un décalage gauche de (u+l) bits de la seconde variable Y, à un décalage gauche de u bits et à une inversion de signe de cette variable Y, à un décalage gauche de (v+m) bits de la première variable X, à un décalage gauche de v bits et une inversion de signe de cette variable X et, finalement, additionner les résultats des quatre opérations ci-dessus. Selon une deuxième option, lorsque les deux constantes A et B sont égales et lorsque les tailles u et v des deux variables sont identiques, le deuxième opérande s'écrit alors : 2exp (u+l). (X + Y)-2expu. (X + Y). On commence ici par faire la somme des deux variables X et Y, on applique un décalage gauche de (u+l) bits à cette somme, on applique un décalage gauche de u bits et une inversion de signe à cette somme pour finalement additionner les résultats des deux opérations précédentes. Selon encore une autre variante de l'invention, les deux nombres F et S sont égaux, ce qui revient à dire que la multiplication devient une élévation au carré du premier nombre F. Le produit P apparaît ici aussi comme la somme de quatre opérandes. Le premier opérande qui figure entre crochets dans l'équation [3] cidessus est un simple nombre binaire. Le deuxième opérande est obtenu par un décalage gauche de (u+1+1) bits de la variable X. Le troisième opérande est obtenu par un décalage gauche de (u+1) bits de cette variable X. Le quatrième opérande est donc obtenu par élévation au carré de la variable X. L'invention présentée ci-dessus permet ainsi de réduire la taille des nombres qui doivent être multipliés lors du calcul d'un produit. Elle peut être utilisée sur des nombres quelconques, auquel cas il convient tout d'abord d'identifier la première constante A en recherchant une suite de bits à 1 en tête du premier nombre. Elle peut également être employée lorsque cette constante A est connue à priori. Elle sera préférentiellement exploitée dans les domaines traitant de grands nombres. Il en est ainsi de la cryptographie. A titre d'exemple, on se réfère à la norme PKCS#1 qui définit notamment la signature G d'un message m dans le cadre de l'algorithme de chiffrement connu sous le nom de RSA (du nom de ses auteurs Ron RIVEST, Adi SHAMIR et Leonard ADLEMAN). En notant 1 l'opérateur de concaténation et mod l'opérateur module : Il s'agit d'une opération connue sous le nom d'exponentiation modulaire. Le terme A est une constante dont tous les bits, souvent plusieurs centaines, valent 1. Le terme P est un paramètre d'une taille de 10 octets environ. Le terme h (m) représente une fonction de hachage du message m, d'une longueur fixe, typiquement 20 octets. Il apparaît que le nombre F est la concaténation d'une constante A et d'une variable X de valeur Plh (m) comportant k bits. Le terme d est un exposant. Le terme n est le module selon lequel la signature G est calculée, il est égal au produit de deux grands nombres premiers. Le terme d est connu sous le nom de clé secrète alors que le terme n est une donnée publique, ces deux termes étant utilisés pour produire la signature. En référence à la figure 2, un procédé de calcul de la signature G est maintenant décrit en considérant que le bit di est le ième bit de l'exposant d, i variant donc de 0 à (k-1). Ce procédé est connu sous la terminologie anglosaxonne"Square and Multiply". Au cours d'une première étape, la signature G et l'indice i sont respectivement initialisés à 1 et 0. A la suite d'un premier test, si le bit d, vaut 1, une étape de multiplication de la signature G par le nombre F est réalisée. La signature G prenant maintenant la valeur du résultat de cette opération. Ensuite, quelle que soit la valeur de ce bit d,, une étape d'élévation au carré du nombre F est réalisée, ce nombre F prenant maintenant la valeur du résultat de cette dernière opération. L'indice i est alors incrémenté d'une unité et un second test est pratiqué sur la valeur de cet indice. Si celui-ci est égal à k, le procédé est terminé, tandis que dans le cas contraire, le procédé est poursuivi en reprenant le premier test. Il apparaît ainsi que la méthode de multiplication décrite plus haut peut être avantageusement appliquée à l'étape de multiplication et à l'étape d'élévation au carré du procédé ci-dessus. L'invention concerne de plus un dispositif pour la mise en oeuvre de la méthode de multiplication. Ce dispositif, un processeur comportant des éléments connus tels que, accumulateur, registre à décalage, additionneur, multiplieur ne sera par conséquent pas plus détaillé. Les exemples de réalisation de l'invention présentés ci-dessus ont été choisis pour leur caractère concret. Il ne serait cependant pas possible de répertorier de manière exhaustive tous les modes de réalisation que recouvre cette invention. En particulier, toute étape ou tout moyen décrit peut-être remplacé par une étape ou un moyen équivalent sans sortir du cadre de la présente invention. REVENDICATIONS 1) Procédé cryptographique utilisant une méthode pour calculer le produit d'un premier (F) et d'un second (S) nombre binaire dans un composant électronique comprenant un processeur, ledit premier nombre (F) résultant de la concaténation d'une première constante A et d'une première variable X de u bits, tous les bits de ladite première constante A étant égaux à 1, ledit deuxième nombre comportant s bits, procédé caractérisé en ce que ledit produit résulte d'une suite d'opérations dont la plus complexe est une multiplication de u bits par s bits. 2) Procédé cryptographique selon la revendication 1 caractérisé en ce que, ladite première constante A comportant 1 bits, la méthode mathématique comprend les opérations suivantes - une première opération de décalage gauche de (u+l) bits dudit second nombre (S) pour obtenir un premier opérande, - une deuxième opération de décalage gauche du u bits et d'inversion de signe dudit second nombre (S) pour obtenir un deuxième opérande, - une troisième opération de multiplication de ladite première variable X par ledit second nombre (S) pour obtenir un troisième opérande, - ledit produit résultant de la somme desdits premier, deuxième et troisième opérandes. 3) Procédé cryptographique selon la revendication 2 caractérisé en ce que, ledit second nombre (S) résultant de la concaténation d'une deuxième constante B dont les m bits valent 1 et d'une deuxième variable Y de v bits, ledit troisième opérande est obtenu au moyen des opérations suivantes - une quatrième opération de décalage gauche de (v+m) bits de ladite première variable X pour obtenir un quatrième opérande, - une cinquième opération de décalage gauche de v bits et d'inversion de signe de ladite première variable X pour obtenir un cinquième opérande, - une sixième opération de multiplication desdites première X et seconde Y variables pour obtenir un sixième opérande, - ledit troisième opérande résultant de la somme desdits quatrième, cinquième et sixième opérandes. 4) Procédé cryptographique selon la revendication 1 caractérisé en ce que, ladite première constante A comportant 1 bits, ledit second nombre (S) résultant de la concaténation de ladite première constante A et d'une deuxième variable Y de u bits, elle comprend les opérations suivantes - une première opération d'addition de ladite première variable X et dudit second nombre (S) pour obtenir un premier opérande, - une deuxième opération de décalage gauche de (u+l) bits dudit premier opérande pour obtenir un deuxième opérande, - une troisième opération de décalage gauche de u bits et d'inversion de signe dudit premier opérande pour obtenir un troisième opérande, - une quatrième opération de multiplication de ladite première variable X par ladite seconde variable Y pour obtenir un quatrième opérande, - ledit produit résultant de la somme desdits deuxième, troisième et quatrième opérandes. 5) Procédé cryptographique selon la revendication 1 caractérisé en ce que, ladite première constante A comportant 1 bits, ledit second nombre (S) résultant de la concaténation d'une deuxième constante B dont les m bits valent 1 et d'une deuxième variable Y de v bits, elle comprend les opérations suivantes - une première opération de définition d'un premier opérande dont la valeur est 2exe (u+v+l+m)-2ex (u+v+l)-2exp (u+v+m) + 2exp (u+v), - une deuxième opération pour calculer un deuxième opérande valant (A. Y + B. X), - une troisième opération de multiplication de ladite première variable X par ladite seconde variable Y pour obtenir un troisième opérande, - ledit produit résultant de la somme desdits premier, deuxième et troisième opérandes. 6) Procédé cryptographique selon la revendication 5, caractérisé en ce que ledit deuxième opérande résulte des opérations suivantes - une quatrième opération de décalage gauche de (u+l) bits de ladite deuxième variable Y pour obtenir un quatrième opérande, - une cinquième opération de décalage gauche de u bits et d'inversion de signe de ladite deuxième variable Y pour obtenir un cinquième opérande, - une sixième opération de décalage gauche de (v+m) bits de ladite première variable X pour obtenir un sixième opérande, - une septième opération de décalage gauche de v bits et d'inversion de signe de ladite première variable X pour obtenir un septième opérande, - ledit deuxième opérande résultant de la somme desdits quatrième, cinquième, sixième et septième opérandes. 7) Procédé cryptographique selon la revendication 5 caractérisé en ce que, ladite deuxième constante B étant égale à ladite première constante A, le nombre v de bits de la deuxième variable Y étant égal au nombre u de bits de la première variable X, ledit deuxième opérande résulte des opérations suivantes - une quatrième opération d'addition desdites première X et deuxième Y variables pour obtenir un quatrième opérande, - une cinquième opération de décalage gauche de (u+l) bits dudit quatrième opérande pour obtenir un cinquième opérande, - une sixième opération de décalage gauche de u bits et d'inversion de signe dudit quatrième opérande pour obtenir un sixième opérande, - ledit deuxième opérande résultant de la somme desdits cinquième et sixième opérandes. 8) Procédé cryptographique selon la revendication 1 caractérisé en ce que, lesdits premier (F) et second (S) nombres étant égaux, la méthode mathématique comprend les opérations suivantes - une première opération de définition d'un premier opérande dont la valeur est tex - une deuxième opération de décalage gauche de (u+1+1) bits de ladite première variable X pour obtenir un deuxième opérande, - une troisième opération de décalage gauche de (u+1) bits et d'inversion de signe de ladite première variable X pour obtenir un troisième opérande, - une quatrième opération d'élévation au carré de ladite première variable X pour obtenir un quatrième opérande, - ledit produit résultant de la somme desdits premier, deuxième, troisième et quatrième opérandes. 9) Procédé cryptographique selon l'une quelconque des revendications 1 à 8 appliqué au chiffrement d'une signature.