Brevet FR2859030A1 — publié le 20050225

PROCEDE DE REALISATION D' UNE MULTIPLICATION MODULAIRE ET PROCEDE DE REALISATION D' UNE MULTIPLICATION EUCLIDIENNE SUR DES NOMBRES DE 2N BITS L'invention concerne un procédé de réalisation d'une multiplication modulaire de type AxB mod N sur des nombres A, B, N de 2xn bits avec un processeur adapté pour travailler sur des nombres de n bits. L'invention concerne également un procédé de réalisation d'une opération de type (XxY)/Z sur des nombres X, Y, Z de n bits, adapté pour la mise en #uvre du procédé de réalisation d'une multiplication modulaire selon l'invention. L'invention est notamment intéressante pour la mise en #uvre d'opérations sur des grands nombres (par exemple n de l'ordre de 2048 bits), que l'on utilise par exemple pour la réalisation de calculs cryptographiques. La réalisation d'opération d'arithmétique modulaire sur des nombres de taille supérieure à n pose d'importants problèmes de mise en #uvre et passe généralement par la mise en #uvre d'algorithmes complexes, comme par exemple les méthodes de Montgomery, Barrett, Quisquater ou Walter, au cours desquelles on découpe les grands nombres en mots de n bits puis on réalise des opérations élémentaires sur les mots de n bits. De tels algorithmes cependant ne peuvent être pas être mis en #uvre à l'aide de processeurs d'arithmétique modulaire limités, d'un point de vue matériel, pour traiter des nombres de au plus n bits. Par exemple, une simple multiplication de deux nombres de n bits ne peut pas être réalisée sur certains processeurs, pour la simple raison que le résultat de la multiplication est un nombre de 2xn qui ne peut pas être traité par les dits processeurs. Il est donc nécessaire d'émuler ces matériels, d'un point de vue logiciel, pour pouvoir réaliser des opérations sur des grands nombres. Pour cela, Fisher et Seifert ont proposé récemment dans Dl (Increasing the Bitlength of a Crypto-processor, Wieland FISHER and Jean Pierre SEIFERT, CHES 2002, LNCS 2523, pp 71-81, Springer-Verlang Berlin Heidelberg 2003) deux solutions, qui permettent de réaliser des multiplications modulaires de type AxB mod N sur des nombres A, B, N de taille 2xn (n étant la taille des mots traités par le processeur utilisé) à partir de deux fonctions élémentaires travaillant sur des nombres de n bits. Les deux fonctions élémentaires MultModDiv et MultModDivInit sont définies par : MultModDiv(X, Y, Z) = (Qa, Ra) = ( L (XxY) /zJ, (XxY) mod Z ) MultModDivInit (X, Y, T, Z) = (Qb, Rb) ( L (XxY+Tx2n) /zJ, (XxY + Tx2n) mod Z ) X, Y, T, Z sont des nombres entiers de au plus n bits, X, Y, T sont positifs ou négatifs, Z est positif, Qa, Qb, Ra, Rb sont des résultats de n bits. Chaque opération MultModDiv et MultModDivInit réalise entre autre deux multiplications sur des nombres de n bits. La notation "LAJ" signifie "partie entière de A" (en d'autres termes, A est arrondi au nombre entier inférieur le plus proche). La notation "mod" est l'abréviation habituelle pour "modulo". La notation "x" est utilisée pour parler de la multiplication euclidienne. Chaque fonction MultModDiv ou MultModDivInit réalise ainsi en pratique deux opérations élémentaires sur des nombres X, Y, Z de n bits : une multiplication euclidienne (Q = L (Xxy) /zJ ou L(XXY+Tx2n)/Z ) dont le résultat est arrondi à sa valeur entière par défaut, et une multiplication modulaire (R = (XxY) mod Z ) ou (XxY + Tx2n) mod Z ) . On déduit rapidement de la définition de la fonction (Q, R) = MultModDiv(X, Y, Z) que : XxY = QxZ + R De manière similaire, on déduit de la définition de la fonction (Q, R) = MultModDiv(X, Y, Z, T) que : XxY+Tx2n = QxZ + R Ces fonctions, et de manière plus générale, toutes les opérations d'arithmétique nécessaires à la mise en #uvre des procédés dont il sera question dans ce qui suit, sont mises en #uvre dans un processeur d'arithmétique modulaire, dimensionnés pour travailler sur des nombres de au plus n bits et produire des nombres de au plus n bits. Ici, et dans tout ce qui suit, par souci de clarté, on utilisera le même nom pour parler d'un registre du processeur et du mot ou nombre de n bits qu'il contient. Ainsi, écrire "C = AxB" signifie concrètement en terme de procédé "multiplier le contenu du registre A par le contenu du registre B dans un circuit de multiplication, et mémoriser le résultat de la multiplication dans le registre C" . Les solutions proposées par Fisher et Seifert utilisent, pour réaliser l'opération AxB mod N, avec A, B, N des nombres de 2n bits, une décomposition des nombres A, B, N en deux mots de n bits, un mot de poids fort A1, B1, Ni et un mot de poids faible Ao, B0, No. La première solution utilise 7 fonctions MultModDiv, et peut être résumée par l'algorithme FS1 suivant (algorithme de multiplication modulaire de Fisher et Seifert, 1ère version) : Entrée : A, B, N, entiers de 2n bits, décomposés sous la forme : A = Alx2n+Ao ; B = Blx2n+Bo ; N = N1#2n+N0 ; Sortie : AxB mod N Faire : (Ql, Ri) = MultModDiv ( Bl, 2n, Ni) (Q2, R2) = MultModDiv(Ql, No, 2n) (Q3, R3) = MultModDiv (Ai, R1-Q2+B0, Ni) (Q4, R4) = MultModDiv(Ao, B1, Ni) (Q5, R5) = MultModDiv (Q3+Q4, No, 2n) (Q6, R6) = MultModDiv (Al, R2, 2n) (Q7, R7) = MultModDiv(Ao, Bo, 2n) Retourner (R3+Rq-Q5-Q6+Q7)X2n + (R7-R6-R5) R1 à R7, Q1 à Q7 sont des variables intermédiaires de n bits, nécessaires à l'obtention du résultat final. La deuxième solution proposée par Fisher et Seifert utilise cinq fonctions de type MultModDiv et une fonction MultModDivInit. Cette deuxième solution peut être résumée par l'algorithme FS2 suivant (algorithme de multiplication modulaire de Fisher et Seifert, 2ème version) : Entrée : A, B, N, entiers de 2n bits, décomposés sous la forme A = Alx2n+Ao ; B = Blx2n+Bo ; N = Nlx2n+No ; Sortie : AxB mod N Faire : (Ql, R1) = MultModDiv (Al, B1, Ni) (Q2, R2) = MultModDivInit(No, -Q1, R1, Ni) (Q3, R3) = MultModDiv(A1, Bo, Ni) (Q4, R4) = MultModDiv(Ao, B1, Ni) (Q5, R5) = MultModDiv(Ao, Bo, 2n) (Q6, R6) = MultModDiv (Q2+Q3+Q4, No, 2n) Retourner ( R2+R3+Rq+Q5-Q6 ) x 2n + (R5-R6) Des détails et des compléments d'information sur les modes de réalisation des deux solutions proposées par Fisher et Seifert sont proposés dans Dl. Comme il a été dit précédemment, ces deux solutions permettent de réaliser des opérations modulaires sur des nombres de au plus 2xn bits avec un processeur intrinsèquement limité à des nombres de n bits. Toutefois, ces deux solutions sont consommatrices d'énergie dans la mesure où chaque fonction MultModDiv ou MultModDivInit requiert un certain nombre d'opérations élémentaires (additions, soustractions de contenus de registres, décalages de bits dans un registre, etc.). A noter que la mise en #uvre d'une fonction MultModDivInit requiert en général un nombre d'opérations élémentaires plus important que la mise en #uvre d'une fonction MultModDiv. (Voir notamment Dl pour des exemples de mises en #uvre des fonctions MultModDiv et MultModDivInit). Au mieux, avec certains processeurs, la mise en #uvre de l'opération MultModDivInit est aussi coûteuse que l'opération MultModDiv (voir par exemple l'algorithme de Sedlak). La mise en #uvre de fonctions de type MultModDiv ou MultModDivInit nécessite la réalisation d'opérations élémentaires de type Q = #(X#Y)/Z# et R = (XxY) mod Z, sur des nombres de n bits. Les processeurs dédiés aux calculs cryptographiques intègrent généralement des moyens matériels pour calculer des opérations modulaires de type R = (XxY) mod Z, mais pas toujours des moyens matériels pour réaliser des opérations euclidiennes de type Q = (XxY)/Z. Dans ce cas, on utilise généralement des moyens d'émulation (logicielle) pour réaliser les opérations euclidienne à partir d'un ensemble d'opérations élémentaires modulaires. Par exemple, dans Dl, est décrit un procédé permettant de calculer Q = L(xxy)/zl, à partir d'opérations de type R1 = (XxY) mod Z et R2 = (XxY) mod (Z+1). Plus précisément, dans Dl, on calcule Q par la relation suivante : Q = ((X*Y) mod Z)- ((X*Y) mod (Z+1) si cette valeur est positive, ou Q = ((X*Y) mod Z) - ((X*Y) mod (Z+1)) + (Z+1) L'opération R = (XxY) mod Z est mise en #uvre en utilisant l'algorithme bien connu de Montgomery. Toutefois, si cet algorithme est particulièrement efficace (en terme de précision et de temps de calcul) lorsque le modulo Z est un entier impair, ce n'est pas le cas lorsque Z est un entier pair. Il en résulte que le procédé proposé dans Dl n'est pas efficace puisque l'un ou l'autre des nombres Z et Z+l est nécessairement pair. Un objet de l'invention est de réaliser les mêmes opérations (AxB mod N, avec A, B, N de 2xn bits) que les algorithmes proposés par Fisher et Seifert, mais en utilisant un nombre plus petit de fonctions élémentaires de type MultModDiv ou MultModDivInit, de sorte à fournir un résultat plus rapidement tout en consommant moins d'énergie. Un autre objet de l'invention est un procédé de réalisation d'une opération de type S = #(X#Y)/Z# sur des nombres de n bits plus efficace que le procédé proposé dans Dl. Le procédé selon l'invention est susceptible d'être utilisé pour la réalisation d'une multiplication modulaire selon l'invention. Ainsi, l'invention concerne un procédé de réalisation d'une multiplication modulaire de type AxB mod N, A, B, N étant des nombres de 2xn bits. Quel que soit le mode de réalisation d'un procédé selon l'invention, les nombres A, B, N sont décomposés en mots de n bits. Puis on exécute, au cours du procédé, des opérations sur les nombres Al, Ao, B1, Bo, Ni, No de n bits. Selon un premier mode de réalisation de l'invention, les nombres A, B, N sont décomposés en base 2n sous la forme : A = Alx2n + Ao, B = Blx2n + Bo, et N = N1*2n + No. En d'autres termes, les n bits de poids forts de A, respectivement B, N forment le mot A1, respectivement B1, Ni et les n bits de poids faibles de A, respectivement B, N, forment le mot Ao, respectivement Bo, No. On réalise ensuite 6 fonctions élémentaires de type MultModDiv, la sixième fournissant le résultat de la multiplication modulaire. Concrètement, on réalise le procédé Al suivant : Entrée : A, B, N, entiers de 2xn bits, décomposés sous la forme A = AlX2n+Ap ; B = Blx2n+Bo ; N = Nlx2n+No ; Sortie : AxB mod N Faire (Ql, Ri) = MultModDiv(Ai, B1, Ni) (Q2, R2) = MultModDiv(Qi, No, 2n) (Q3, R3) = MultModDiv(Ai+AO, Bl+Bo, 2n -1) (Q4, R4) = MultModDiv(Ao, Bo, 2n) (Q5, R5) - MultModDiv(2n-1, Rl+Q3-Q2-Q4. Ni) (Q6, R6) = MultModDiv(Q5, No, 2n) Retourner (R3+R5-Q6-R2-R4)x2n + (R2+R4-R6) L'algorithme Al ci-dessus réalise bien la multiplication modulaire AxB mod N. En effet, selon le lemme de Karatsuba (voir notamment D2 "Multiplication Of Multidigit Numbers On Automata" Soviet Physics - Doklady, volume 7, pages 595-596,1963), on a : AxB = 2n(2n-l)A,xBl + 2n(Ai+A0) x (Bi+B0) - (2n-l)AoxBo Comme N = Nlx2n+No, on a Nlx2n #N -No, où =N est la relation d'équivalence modulo N. De la définition de Q1 à Q6, R1 à R6 dans l'algorithme Al et de la définition de la fonction MultModDiv, on déduit que : 2n(2n-1)XAlXBl-N 2n(2n-1)(Q1"N1+R1) =N - (2n-1) x (Q1XN0) +2n (2n-1) XRl =N -(2n-l) (Q2x2n+R2) + 2n(2n-1) R1 =N 2n(2n-1) (Rl-Q2) (2-1)xR 2n(Ai+A0) (Bi+Bo)=2n((2n-1)Q3+R3) = 2n (2n-1) Q3+2nxR3 (2n-1)xApXB=(2n~1) (2nXQ4+R4)=2n(2n-1)Q4+(2n~1)R4 On en déduit finalement : AxB =N 2n(2n-1)(R1+Q3-Q2-Q4)+2nxR3-(2n~1)(R2+R4) =N 2n(Q5xN1+R5)+2nXR3-(2n~1)(R2+R4) =N -Q5xNO+2n(R3+R5)-(2n-l)(R2+R4) =N -(Q6x2n+R6)+2n(R3+Rs)-(2n-1) (R2+R4) =N 2n(R3+R5-Q6-R2-R4)+(R2+R4-R6) et donc : AxB mod N = 2n (R3+R5-Q6-R2-R4) + (R2+R4-R6) ce qui est le résultat produit par l'algorithme Al. On notera que le procédé Al selon l'invention utilise une fonction MultModDiv de moins que le procédé FS1 connu de l'art antérieur. On a donc bien, pour un même résultat, une diminution du nombre global d'opérations à réaliser, et donc une diminution en conséquence du temps global et de l'énergie globale consommés pour exécuter le procédé. Concrètement, une opération MultModDiv réalisant 2 multiplications modulaires sur des nombres de n bits, l'algorithme Al utilise ici 12 multiplications modulaires sur des nombres de n bits au lieu de 14 dans l'algorithme FS1, d'où un gain en temps de calcul de (14-12)/14 = 14%. Selon un deuxième mode de réalisation de l'invention, les nombres A, B, N sont également décomposés en base 2n sous la forme : A = Alx2n + Ao, B = Blx2n + Bo, et N = Nl*2n + No. On réalise ensuite une fonction de type MultModDivInit et quatre fonctions élémentaires de type MultModDiv, la quatrième fournissant le résultat de la multiplication modulaire. Concrètement, on réalise le procédé A2 suivant : Entrée : A, B, N, entiers de 2xn bits, décomposés sous la forme A = Ai*2n+A0 ; B = B1x2n+Bo ; N = Ni> (Ql, R1) = MultModDiv(A1, B1, Ni) (Q2, R2) = MultModDiv (A1+Ap, Bl+Bo, 2n-l) (Q3, R3) = MultModDiv(Ao, Bo, 2n) (Q4, R4) = MultModDivInit (Q1, No, Q3-R1-Q2, Ni) (Q5, R5) = MultModDiv(Np+N1, Q4, 2n) Retourner (R2+Q5-R3-R4)x2n + (R3+R4+R5) L'algorithme A2 réalise bien la multiplication modulaire AxB mod N. En effet, on a, de par les définitions de Q1 à Q5, R1 à R5 . 2n(2n-l) xAixBi =N 2n(2n-I)QlxNl+Rl) (2n-l) (-QixN0+Ri*2n) 2n(A1+AO)(B1+BO)= 2n((2n-l)Q2+R2) = 2n(2n~1)Q2+2nxR2 (2n-l)AoxBo= (2n-l) (2nxQ3+R3)= 2n(2n~1)Q3+(2n~1) XR3 Du lemme de Karatsuba (D2), on a : AxB = 2n(2n-I)A,xBl + 2n(A!+A0) x (Bi+B0) - (2n-l)AoxBo On en déduit donc (car N1(2n-1) ---N -Np-N1): AxB =N -(2n-1) (QlxNO+(Q3-R1-Q2)X2n)+2nxR2-(2n~1)R3 (2n-l)(Q4xN,+R4)+2nxR2-(2n-l)R3 (N0+Ni)Q4+2nxR2-(2n-l) (R3+R4) (2nXQ5+R5)+2nXR2-(2n~1)(R3+R4) 2n ( R2+QS-R3-R4 ) + ( R3+R4+R5 ) Il vient finalement : AxB mod N = 2n (R2+Q5-R3-R4) + (R3+R4+R5) ce qui est le résultat produit par l'algorithme A2. On notera que le procédé A2 selon l'invention utilise une fonction MultModDiv de moins que le procédé FS2 connu de l'art antérieur. On a donc bien là encore, pour un même résultat, une diminution du nombre global d'opérations à réaliser, et donc une diminution en conséquence du temps global et de l'énergie globale consommés pour exécuter le procédé. Concrètement, une opération MultModDiv ou une opération MultModDivInit réalisant 2 multiplications modulaires sur des nombres de n bits, l'algorithme A2 utilise ici 10 multiplications modulaires sur des nombres de n bits au lieu de 12 dans l'algorithme FS2, d'où un gain en temps de calcul de (12-10)/12 = 16% par rapport au procédé équivalent FS2 de Dl. Selon un troisième mode de réalisation de l'invention, les nombres A, B, N sont décomposés dans une base U, U étant différent de 2n, telle que : A = AlxU + Ao, B = B1#U + Bo, et N = NlxU + No. Ai, Ao, Bl, Bo, Ni et No sont des mots de n bits. On réalise ensuite opérations élémentaires de type MultModDiv sur les mots Al, Ao, B1, B0, Ni et No. Dans un premier exemple, on réalise le procédé A3 suivant: Entrée : A, B, N, entiers de 2xn bits, décomposés sous la forme A = AlxU+Ap : B = BlxU+Bo ; N = NlxU+No Sortie : AxB mod N Faire : (Ql, Ri) = MultModDiv(Ao Bo U) (Q2, R2) = MultModDiv(A1+Ao, Bl+Bo, U) (Q3, R3) = MultModDiv(A1, B1, U) (Q4, R4) = MultModDiv(a, Q3, U) (Q5, R5) = MultModDiv(a, -Q1+Q2-Q3+Q4+R3, U) Retourner (R5+R1)+(Rq-R1+Q1+R2-R3+Q5)xU avec a = U2 mod N. Dans ce 1er exemple, l'algorithme A3 réalise bien la multiplication modulaire AxB mod N. En effet, comme a = U2 mod N, on a U2 #N a. De plus, on a, grâce aux définitions de Q1 à Q5, R1 à R5 . (U-1) xApxBp =N (U-1) (QlxU + Ri) =N Qlxa - R1 + (Ri-Qi)xU Ux(A1+Ao) ( B1+BO ) =N U(Q2xU+R2) =N Q2xa + R2xU U(U-l)xAixBi ---N U2xAlxB, - UxAixBi ---N Ux ( R3xU+ Q3xa) - Ux (Q3xU+R3) #N R3xa + Q3xaxU - Q3xa + R3xU #N (-Q3 + R3) xa + (- R3 + Q3xa)xU Du lemme de Karatsuba (D2), on obtient : AxB = U (U-1)A1XB1 + Ux(Al+Ao x (Bi+Bo) - (U-1)AoxBo , soit : AxB =N (-Q3 + R3)xa + (- R3 + Q3xa)xU + Q2#[alpha] + R2xU - Qlxa + Ri - (Ri-Qi)xU =N [alpha] (-Q1 + Q2 - Q3 + R3) + R1 + U(-Ri+ Q1 + R2 - R3 + Q3xa) =N a(-Ql + Q2 - Q3 + R3) + R1 + U (Q4xU + R4 - R1 + Q1 + R2 - R3) =N a(-Qi + Q2 - Q3 + Q4 + R3) + R1 + U(R4 - Rl + Q1 + R2 - R3) =N ( R5 + R1 ) + U(R4 - Ri + Ql + R2 - R3 + Q5 ) ce qui est le résultat produit par l'algorithme A3. On notera que, dans ce 1er exemple, le procédé A3 selon l'invention utilise un nombre encore réduit de fonctions MultModDiv que les procédés connus ou même que le premier mode de réalisation ou le deuxième mode de réalisation de l'invention. On a donc bien là encore, pour un même résultat, une diminution encore plus importante du nombre global d'opérations à réaliser, et donc une diminution en conséquence du temps global et de l'énergie globale consommés pour exécuter le procédé. Concrètement, une opération MultModDiv ou une opération MultModDivInit réalisant 2 multiplications modulaires sur des nombres de n bits, l'algorithme A3 utilise ici 10 multiplications modulaires sur des nombres de n bits au lieu de 14 dans l'algorithme FS1, d'où un gain en temps de calcul de (14- 10)/14 = 28% par rapport au procédé équivalent FS1 de Dl. Pour la mise en #uvre de ce premier exemple, on pourra par exemple choisir U = # N #, où N est la racine carrée de N et r #N est la partie entière par excès de N (en d'autres termes, U est l'arrondi à l'entier immédiatement supérieur de N). On pourra également choisir U = r (k.N) #, avec k un nombre entier. De préférence, k est choisi tel que a = U2 mod N soit le plus petit possible. Dans un 2ème exemple, U est défini par la relation : U2 =N a + ##U. a et # sont des nombres entiers de préférence constants et aussi petits que possibles (inférieurs à 256 bits). a et # sont choisis de préférence de sorte que [alpha]+#2 soit également un entier constant et petit. Idéalement, 8 = 1 et a =-1, 2 ou 3. De telles valeurs de a, # peuvent être obtenues en choisissant un nombre N approprié, c'est-à-dire en choisissant un procédé de génération de clé approprié (on rappelle que N est ici un élément d'une clé d'un algorithme cryptographique). Le procédé A3 se simplifie pour donner le procédé A4 suivant : Entrée : A, B, N, entiers de 2n bits, décomposés sous la forme A = AixU+Ao ; B = BlxU+Bo ; N = NlxU+No Sortie : AxB mod N Faire : (Ql, R1) = MultModDiv(Ao, Bo, U) (Q2, R2) = MultModDiv(Al+Ap, Bl+Bo, U) (Q3, R3) = MultModDiv(Al, Bl, U) Retourner ax (-Q1+Q2-Q3+R3+SXQ3) +RX +U x[(-R1-R3+Q1+R2+Q3(a+62) + (-Q3+R3-Ql+Q2)xÔ] L'algorithme A4 réalise bien la multiplication modulaire AxB mod N. En effet, en utilisant U2 =N a + ÔxU et le lemme de Karatsuba, on obtient : {U-1) xApxBp =N (U-1) (QlxU + Ri) =N -QlxU- Ri + RlxU+Ql(a+8xU) =N Qlxa - Rl + (Ri-Qi+Qix5)xU Ux(Ai+A0) (Bl+Bo) ---N U(Q2xU+R2) #N R2xU + Q2x(a + ÔU) =N axQ2 + (R2 + ##Q2)U UxAlxBl =N U (Q3xU+R3) =N aQ3+ (R3+ÔXQ3) U U2xAlxB, ---N U(axQ3+(R3+bxQ3)xU) =N axUxQ3+(R3+$xQ3)x(a+S xU) =N ax (R3+ôxQ3) + ((Sx(R3+8xQ3)+axQ3)xU U(U-l)xAixBi =N ax(R3-Q3+8xQ3) + ( ( R3+SxQ3 ) x ( -1 ) +axQ3 ) xU =N ax(R3-Q3+8xQ3) + [-R3+8x (-Q3+R3) +Q3x (82+a) ] xU Et donc : AxB =N ax(-Ql+ Q2-Q3+R3+ÔXQ3) + R1 + Ux(-Rl-R3+Ql+R2+Q3x X+52) + 8x(-Q3+R3-Ql+Q2) On notera que le procédé A4 selon l'invention utilise un nombre encore réduit de fonctions MultModDiv que les procédés connus ou même que le premier mode de réalisation ou le deuxième mode de réalisation de l'invention. On a donc bien là encore, pour un même résultat, une diminution encore plus importante du nombre global d'opérations à réaliser, et donc une diminution en conséquence du temps global et de l'énergie globale consommés pour exécuter le procédé. Dans un 3ème exemple, on réalise le procédé A5 suivant : Entrée : A, B, N, entiers de 2n bits, décomposés sous la forme A = AixU+Ao ; B = B1#U+B0 ; N = NlxU+No ; Sortie : AxB mod N Faire : (XI, Y1, Zl, RI) = Coefficients(A, B, U) (Q2, R2) = MultModDiv(a, X1, U) (Q3, R3) = MultModDiv(a, Y1+Q2, U) Retourner Ri+R3+(R2+Zi+Q3)xU La fonction Coefficient calcule dans une base U les coefficients du polynôme produit de deux nombres entiers A, B décomposés dans la base U (A= AlxX+Ao et B = BlxX+Bo) : Coefficients (A, B, U) = (C3, C2, Ci, Co) tels que C3 = f ; = d + 3f ; Cl = e + 2f ; = RO ; avec : Ro = (A mod U)(Bmod U) mod U Rl = (A mod(U+1))(Bmod(U+1))mod(U+1) R2 = (A mod(U+2))(Bmod(U+2))mod(U+2) R3 = (A mod(2U+3))(Bmod(2U+3))mod(2U+3) et a = (RO - R2 + ((RO-R2) mod 2)(U+2))/2 mod U + 2 b = RO - R1 mod (U+1) c = (2 (RO-R3) + (2 (RO-R3) mod 3)(2U+3))/3 mod (2U+3) d = ((b-a) mod (U+1)) e = a + 2d f =-6d + 4e-4c mod (2U + 3) C3, C2, Ci, Co vérifient AxB = C3xU3 + C2xU2 + ClxU+ Co A noter que, comme A = AlxU+Ao et B = BlxU+Bo, RO, R1, R2, R3 peuvent être calculés facilement à partir des relations suivantes : Ro = AoBo mod U Ri = (AO-Al)(BO-Bi) mod (U+1) R2 = (Ao - 2Al) (Bo-2Bl) mod (U+2) R3 = (Ao + (Al mod 2)U - 3 (Ai div 2)) x (B0+(B1 mod 2)U - 3 (Bl div 2)) mod (2U + 3) Comme précédemment, le coût, en terme de temps de calcul, des opérations auxiliaires telles que les additions, soustractions, etc., est négligeable. L'algorithme A5 réalise bien la multiplication modulaire AxB mod N. En effet, en utilisant la définition de la fonction Coefficients, on obtient : AxB = XixU3 + YlxU2 + ZlxU + Ri son R1 + aXYl + (axXi + Zi)xU =N Rl + axYl + (Q2xU + R2 + Zl) xU =N Pi + ax(Yi+Q2)+(R2+Zi)xU =N Rl+R3+(R2+Zl+Q3)xU Dans ce troisième exemple, on pourra choisir U = r #N #. On pourra également choisir U = # #(k.N) # avec k un nombre entier. k est choisi de préférence aussi petit que possible tel que U soit impair et premier avec trois (c'est-à-dire que trois ne divise pas U) . On testera pour cela par exemple plusieurs valeurs croissantes de k, jusqu'à obtenir une valeur satisfaisante de U. On pourra également choisir k aussi petit que possible, tel que U soit impair, premier avec trois et tel que a = U2 mod N soit le plus petit possible. L'invention concerne enfin un procédé de réalisation d'une opération de type S = (XxY) /Z, où X, Y, Z sont des nombres de n bits. Ce procédé est susceptible d'être utilisé pour la mise en #uvre d'une multiplication modulaire telle que décrite ci-dessus et plus généralement d'une fonction MultModDiv. Au cours du procédé, on réalise les étapes suivantes : El : on initialise à zéro une variable #ss et on calcule deux données : C = XxY mod Z et Cp = XxY mod (Z+p), ss étant un nombre entier positif prédéfini de n bits. E2 : on calcule le résultat S = [C - Cp - d(3 (Z+(3) ] /(3 E3 : si la donnée intermédiaire n'est pas un nombre entier, alors on incrémente de 1 la variable #ss et on répète l'étape E2 puis l'étape E3. Pour justifier le procédé tel que décrit ci-dessus, dans ce qui suit, on va montrer dans un 1er temps qu'il existe un nombre entier #ss tel que S = LxY/zJ = [C - Css - 0(3 (Z+(3) ] /(3. Puis on montrera que le procédé ci-dessus permet de trouver la valeur correcte de Ap et de S. Soit (3 un nombre entier positif de n bits. On définit . C = XxY mod Z Css = XxY mod (Z+P), à = LXY/zJ - LxY/(Z+p)j Ap vérifie : 0 XY/(Z+p) XY = LxY/zJxZ + C = LXY/ (Z+(3) x (Z+(3) + Ce (#ss + LxY/Z)J)x(Z+p) + Css Soit C = LxY/zJxp + Apx(Z+j3) + Cp et donc : LXy/zJ = [C-Cp - Apx(7,+P)i / P (calcul de l'étape E3 du procédé) De la dernière relation, on déduit que #XY / Z# est égal à (C-Cp)/p moins un terme correctif (3 (Z+(3) /(3. Par ailleurs, par définition, LxY/zJ est un nombre entier, de même que ? et Ap. Aussi, en calculant = [C-C - 0(3x (Z+(3) / j3 de manière systématique avec les différentes valeurs possibles de #ss, et en vérifiant si le résultat est entier, on calcule la valeur correcte de (3 et donc la valeur correcte de #XY / Z#. Comme on l'a montré précédemment, 0 L'expérience montre que les meilleurs résultats (en terme de rapidité de calcul notamment) sont obtenus pour des valeurs de b choisies égales à une puissance de 2, valeurs parmi lesquelles P 2 donnent les meilleurs résultats. En effet, avec P 2, on effectue des réductions modulaires (C = XxY mod Z et Css = XxY mod (Z+P)) uniquement avec des moduli (Z et Z+2) de même parité que Z et donc on supprime toute difficulté liée au calcul d'une multiplication modulaire avec un modulo pair). Par ailleurs, la division par ss=2 n'est pas coûteuse en terme de temps de calcul, puisqu'une telle opération revient en pratique à décaler le contenu d'un registre de un bit à droite. Enfin, au maximum deux valeurs de Ap sont à tester (0 et 1). REVENDICATIONS 1. Procédé cryptographique de réalisation d'une multiplication modulaire de type AXB mod N, procédé au cours duquel : - si ils ne sont pas donnés décomposés, on décompose les nombres A, B, N de 2xn bits dans une base U tels que A = AlxU + Ao, B = BlxU + Bo, et N = NlxU + No, Ai, Ao, Bi, Bo, Ni et No étant des mots de n bits, puis - on réalise des opérations de type MultModDiv sur les nombres Ai, Ao, Bi, Bo, Ni et No, l'opération élémentaire MultModDiv étant définie par MultModDiv(X, Y, Z) ( L(XXY)/zJ , (XXY) mod Z ) , X, Y, Z étant des nombres entiers de au plus n bits. 2. Procédé selon la revendication 1, dans lequel U est différent de 2n. 3. Procédé selon la revendication 2, au cours duquel : - on réalise les opérations suivantes : (Ql, R1) = MultModDiv(Ao, B0, U) (Q2, R2) = MultModDiv(Al+Ao, Bl+Bo, U) (Q3, R3) = MultModDiv(Al, Bi, U) (Q4, R4) = MultModDiv(a, Q3, U) (Q5, R5) = MultModDiv(a, -Ql+Q2-Q3+Q4+R3, U) R1 à R5, Q1 à Q5 étant des résultats intermédiaires de n bits, a étant défini par la relation : a = U2 mod N, puis - on retourne le résultat suivant : (R5+Rl)+(R4-Rl+Ql+R2-R3+Q5)XU 4. Procédé selon la revendication 3, au cours duquel le nombre U est choisi égal à # #N #. 5. Procédé selon la revendication 3, au cours duquel le nombre U est choisi égal à r (k.N) 1, k étant un nombre entier. 6. Procédé selon la revendication 5, au cours duquel le nombre k est choisi tel que a soit le plus petit possible. 7. Procédé selon la revendication 2, au cours duquel : - on calcule initialement le nombre U selon la relation U2 =N a + ##U, a et # étant des nombres entiers, puis - on réalise les opérations suivantes : (Ql, R1) = MultModDiv(Ao, Bo, U) (Q2, R2) = MultModDiv(Al+Ao, Bl+Bo, U) (Q3, R3) = MultModDiv(Al, B1, U) R1 à R5, Q1 à Q5 étant des résultats intermédiaires de n bits, puis - on retourne le résultat suivant : ax ( -S21+Q2-Q3+R3+bxQ3 ) +R1 +U x ( -R1-R3+Q1+R2+Q3 (a+2 ) + (-Q3+R3-Ql+Q2)XO] 8. Procédé selon la revendication 7, dans lequel les nombres a et 8 sont choisis constants, aussi petits que possibles et de sorte que [alpha]+#2 soit également un entier constant et petit. 9. Procédé selon la revendication 2, au cours duquel : - on réalise les opérations suivantes : (Xl, Yl, Zl, R1) = Coefficients(A, B, U) (Q2, R2) = MultModDiv(a, X1, U) (Q3, R3) = MultModDiv(a, Y1+Q2, U) a étant un nombre entier défini par a = U2 mod N, l'opération élémentaire Coefficient étant définie par Coefficients (A, B, U) = (C3, C2, Ci, Co) tels que C3 = f ; C2 = d + 3f ; Cl = e + 2 f ; CO = RO ; avec : Ro = (A mod U)(Bmod U) mod U Ri = (A mod(U+1))(Bmod(U+1))mod(U+1) R2 = (A mod(U+2))(Bmod(U+2))mod(U+2) R3 = (A mod(2U+3))(Bmod(2U+3))mod(2U+3) et a = (RO - R2 + ((RO-R2) mod 2)(U+2))/2 mod U + 2 b = RO - R1 mod (U+1 ) c = (2(RO-R3) + (2(RO-R3) mod 3)(2U+3))/3 mod (2U+3) d = ((b-a) mod (U+1)) e = a + 2d f = -6d + 4e-4c mod (2U + 3) - on retourne le résultat suivant : R1+R3+ (R2+Z1+Q3) xu 10. Procédé selon la revendication 2, au cours duquel : - on réalise les opérations suivantes : (Xl, Yl, Zl, Rl) = Coefficients(A, B, U) (Q2, R2) = MultModDiv(a, X1, U) (Q3, R3) = MultModDiv(a, Y1+Q2, U) a étant un nombre entier défini par a = U2 mod N, l'opération élémentaire Coefficient étant définie par Coefficients (A, B, U) = (C3, C2, Ci, Co) tels que C3 = f ; C2 = d + 3 f ; Cl = e + 2 f ; CO = RO ; avec : Ro = A0B0 mod U Ri = ( AO-A1 ) ( BO-B1 ) mod (U+l) R2 = (Ao - 2A1) (BO-2B1) mod (U+2) R3 = (Ao + (Al mod 2)U - 3 (Al div 2)) x (BO+(B1 mod 2)U - 3 (B1 div 2)) mod (2U + 3) et a = (RO - R2 + ((RO-R2) mod 2)(U+2))/2 mod U + 2 b = RO - R1 mod (U+l) c = (2(RO-R3) + (2(RO-R3) mod 3)(2U+3))/3 mod (2U+3) d = ((b-a) mod (U+l)) e = a + 2d f =-6d + 4e-4c mod (2U + 3) - on retourne le résultat suivant : R1+R3+(R2+Z1+Q3)xU 11. Procédé selon la revendication 9 ou 10, au cours duquel le nombre U est choisi égal à # N 1. 12. Procédé selon la revendication 9 ou 10, au cours duquel le nombre U est choisi égal à # (k.N) #, k étant un nombre entier. 13. Procédé selon la revendication 12, dans lequel k est choisi aussi petit que possible tel que U soit impair et premier avec trois. 14. Procédé selon la revendication 13, au cours duquel le nombre k est choisi tel que a soit le plus petit possible. 15. Procédé selon la revendication 1, dans lequel U est égal à 2n et au cours duquel : - on réalise les fonctions suivantes : (Ql, Rl) = MultModDiv(Al, Bel, Ni) (Q2, R2) = MultModDiv(Ql, No, 2n) (Q3, R3) = MultModDiv(Al+AO, Bl+Bo, 2n -1) (Q4, R4) = MultModDiv(Ao, B0, 2n) (Q5, R5) = MultModDiv(2n-l, Rl+Q3-Q2-Q4, Ni) (Q6, R6) = MultModDiv(Q5, No, 2n) R1 à R6, Q1 à Q6 étant des résultats intermédiaires de n bits, l'opération élémentaire MultModDiv étant définie par MultModDiv (X, Y, Z) = ( #(X#Y)/Z#, (XXY) mod Z ) , X, Y, Z étant des nombres entiers de au plus n bits, puis - on retourne le résultat suivant : (R3+R5-Q6-R2-R4)x2n + (R2+R4-R6) 16. Procédé selon la revendication 1, dans lequel U est égal à 2n et au cours duquel : - on réalise les fonctions suivantes : (Ql, R1) = MultModDiv(Al, B1, Ni) (Q2, R2) = MultMOdDiV(A1+A0, Bl+Bo, 2n-l) (Q3, R3) = MultModDiv(Ao, B0, 2n) (Q4, Rg) - MultModDivInit (Q1, No, Q3-Ri-Q2, Ni) (Q5, R5) = MultModDiv(No+Ni, Q4, 2n) Ri à R5, Qi à Q5 étant des résultats intermédiaires de n bits, l'opération élémentaire MultModDiv étant définie par MultModDiv(X, Y, Z) = ( #(X#Y)/Z#, (XXY) mod Z ), et l'opération élémentaire MultModDivInit étant définie par MultModDivInit(X, Y, T, Z) = ( (XxY+Tx2n)/Z , (XxY + Tx2n)mod Z ), X, Y, Z et T étant des nombres entiers de au plus n bits, puis - on retourne le résultat suivant : (R2+Q5-R3-R4)x2n + (R3+R4+R5)