Brevet FR2713365A1 — publié le 19950609

XA 2713365 Procédé de réduction modulo à l'aide d'une table précalculée La présente invention concerne un procédé de réduction modulo utilisant une table précalculée pour augmenter une vitesse de réduction en diminuant le nombre d'opérations d'addition pendant l'exécution de traitements fonctionnels ordinaires à l'aide d'ordinateurs. L'augmentation récente du besoin de protéger les informations a entraîné la nécessité de mettre en oeuvre un mécanisme pour protéger les informations, dont les caractéristiques exigent des calculs modulo sur de très grands nombres. En particulier, le besoin en algorithmes de réduction modulo à grande vitesse a augmenté proportionnellement aux besoins croissants en opérations d'élévation à une puissance. La plupart des mécanismes de protection des informations doivent être mis en oeuvre sur des cartes intelligentes dans différentes conditions de fonctionnement qui sont limitées en ce qui concerne la taille de la mémoire et la vitesse des processeurs, ou des composants similaires, utilisés sur les cartes intelligentes. C'est pourquoi, on peut envisager des techniques fonctionnelles qui utilisent une table précalculée mémorisée dans une mémoire de taille appropriée, pour convertir en additions toutes les multiplications requises pour des opérations de réduction. Les techniques de réduction conventionnelles présentent des inconvénients en ce sens qu'elles exigent davantage d'opérations et ne sont pas efficaces. Un calcul modulo est une opération qui permet d'obtenir le reste de la division par N d'un nombre X supérieur à N, pour un modulo N donné. Un calcul modulo utilisé dans un mécanisme de protection des informations, dans lequel N est un nombre ordinaire comportant plus de 512 bits qui ne peuvent pas être traités en une seule fois, nécessite une opération à précision multiple. La partie la plus importante d'un algorithme d'opération modulo est la partie qui exécute l'arithmétique modulo. Il existe, en gros, deux méthodes pour exécuter la réduction modulo. L'une est la méthode qui utilise la vraie division pour exécuter la réduction, l'autre est la méthode qui utilise uniquement l'addition, et pas la division. La méthode qui utilise la division n'a pas besoin d'une table précalculée, tandis que la méthode qui n'utilise pas la division a besoin d'une table précalculée. Les algorithmes de réduction conventionnels utilisant des tables précalculées peuvent être expliqués en référence aux figures 1, 2 et 3 de la manière suivante. La figure 1 représente une configuration de table utilisée dans des algorithmes de réduction modulo conventionnels, la figure 2 représente une structure destinée à introduire des données dans un algorithme de réduction modulo, et la figure 3 représente un organigramme d'un algorithme de réduction modulo utilisant une table. Dans cette application, X représente une entrée (2nsX également un modulo, respectivement. Le numéro de référence 1, sur la figure 1 représente le ième élément (1 capacité. Supposons que N soit un nombre à n bits, un algorithme utilisant la table conventionnelle va fonctionner comme illustré sur la figure 3. Tout d'abord, supposons qu'un nombre présentant la structure illustrée sur la figure 2 doive être introduit. Supposons que le nombre introduit soit X et que X puisse être divisé par X = X_0-22 + X_R, en référence au bit n, et soit X(mod N) = (X 0-2n (mod N) + XR) (mod N). Ici, les résultats mis en mémoire précédemment, comme illustré sur la figure 1, peuvent être recherchés à l'aide d'un index de XO.2n (mod N). Le X_0-2n (mod N) recherché de cette manière peut être ajouté à XR pour former un nouveau X'. Dans ce cas, un bit de dépassement de capacité peut apparaître dans le (n+l)ième bit, étant donné que X_0.2" (modN) et XR sont respectivement des nombres à n bits maximum. En cas de dépassement de capacité, le traitement ci- dessus sera répété avec l'introduction du X'. Sinon, le traitement de réduction sera terminé. Toutefois, une soustraction peut être nécessaire après comparaison du résultat final avec N, car le résultat final peut être supérieur à N, même s'il comporte n bits. Comme cela a été expliqué précédemment, l'art antérieur nécessite une répétition du traitement de réduction qui se réfère à la table, lors d'un dépassement de capacité. Comme le nombre maximum d'exécutions du traitement de réduction n'est pas fixé, il se pose un problème à savoir que l'opération de réduction doit être exécutée un grand nombre de fois. La présente invention a par conséquent pour but de proposer un procédé de réduction modulo qui permette d'augmenter la vitesse de réduction en diminuant le nombre d'opérations d'addition et, simultanément le nombre d'éxécutions d'une opération moyenne d'addition en fixant le nombre d'opérations d'addition à 2 pour chaque exécution de l'algorithme de réduction. Pour atteindre ce but, le procédé de réduction modulo selon la présente invention, destiné à être mis en oeuvre notamment en association avec des cartes à mémoire comportant des moyens de calcul matériels, comprend les étapes qui consistent à: (1) rechercher une valeur mémorisée dans une table à l'aide d'un index d'un nombre à bits de poids fort et ajouter la valeur mémorisée dans la table à un nombre à bits de poids faible; (2) si le résultat obtenu à partir de l'addition du nombre à bits de poids faible et du nombre recherché dans la table au cours de l'étape (1) produit un dépassement de capacité (1 bit), supprimer le dépassement de capacité et terminer l'exécution de l'opération; (3) si le dépassement de capacité n'a pas lieu au cours de l'étape (2), ajouter N sur un module N au résultat obtenu à partir de l'étape (1) et terminer l'exécution de l'opération. Ce qui précède, ainsi que d'autres buts, caractéristiques et avantages de la présente invention, sera mieux compris à la lecture de la description détaillée suivante de deux modes de réalisation préférés, donnée à titre d'exemple nullement limitatif en référence aux dessins annexés dans lesquels: la figure 1 représente une configuration de table utilisée dans des algorithmes de réduction modulo conventionnels; la figure 2 représente une structure pour introduire des données dans un algorithme de réduction modulo conventionnel; la figure 3 représente un organigramme d'un algorithme de réduction modulo conventionnel utilisant une table; la figure 4 représente le contenu mémorisé dans une table utilisée dans le procédé de réduction modulo de la présente invention; la figure 5 représente un traitement d'optimisation pour la table représentée sur la figure 4; et la figure 6 représente une configuration de l'algorithme de réduction proposé dans la présente invention. En référence à la figure 4 qui représente le contenu mémorisé dans une table utilisée dans la présente invention, des valeurs d'index se situent dans une plage allant de 1 à t-1 (RT2 [1] à RT2 [t-l]), chaque élément du contenu comprenant n (n 2 512) bits. Il faut noter que la valeur qui doit être mémorisée à l'index i est (i + 1).2n(mod N). Si n est égal à 512 bits et si t représente 16 à 32 bits, la taille de la table est d'environ 1 kilo-octet à 2 kilo-octet. Le numéro de référence 6 représente le ième (l n bits et a comme taille maximale n+log2t bits. La figure 5 représente un traitement d'optimisation pour la table représentée sur la figure 4. L'optimisation est ici un traitement qui consiste, si le contenu de la table est un nombre inférieur à 2n-N, à ajouter N à celui-ci. Il sagit d'un traitement destiné à accélérer l'apparition d'un dépassement de capacité en rendant le bit de poids le plus fort (MSB) égal à 1, si possible. L'addition de N n'a ici, conformément aux lois du modulo, aucune influence sur les résultats et ne fait qu'accélérer l'apparition du dépassement de capacité. Sur la figure 5, le numéro de référence 7 désigne un traitement pour mémoriser RT2[i] + N, à la place de RT2[i], lorsque RT2[i] + N En référence à la figure 6 qui représente une configuration de l'algorithme de réduction proposé dans la présente invention, le numéro de référence 8 désigne le premier traitement de réduction de l'algorithme de réduction de la présente invention, le numéro de référence 9 désigne une étape destinée à contrôler si un dépassement de capacité s'est produit ou non, et le numéro de référence 10 désigne le traitement de réduction qui fait suite au premier traitement de réduction. Tout dabord, la valeur mémorisée dans la table doit être recherchée à l'aide d'un index de X 0 qui est un nombre à bits log2 t de poids fort, et ajoutée à un nombre à bits n de poids faible. Toutefois, il faut soustraire 2n à la valeur mémorisée, car il s'agit d'une valeur correspondant à un nombre à bits log2 t + 1. Lorsque le résultat de l'addition du nombre à bits n de poids faible et du nombre recherché dans la table a produit un dépassement de capacité (1 bit), l'algorithme doit être terminé car le fait de négliger le dépassement de capacité revient à soustraire 2". Si un dépassement de capacité n'a pas eu lieu ici, l'algorithme doit être terminé, après l'addition de N. Le résultat n'est pas affecté par l'addition de N ici, car cela revient à ajouter zéro à (mod N). L'addition de N va produire un dépassement de capacité puisque la table est déjà optimisée. Par conséquent le nombre maximum d'opérations dans l'algorithme proposé ne dépassera pas 2. Premier mode de réalisation de la présente invention Le résultat de la comparaison de l'application d'un algorithme de réduction conventionnel et du présent algorithme de réduction est donné ci-après. Les principales opérations de l'opération de réduction utilisant la table précalculée sont des additions, et les nombres des additions sont comparées dans les résultats suivants. [1] les résultats concernent la production et les tests de 300 modulo N aléatoires, (1) probabilité de supériorité de l'algorithme proposé sur l'algorithme conventionnel: 76% (228 fois/300 fois) Note - 1: B E A (mod N) dans cette opération 2: A est le nombre aléatoire de 1024 bits, et N est le nombre aléatoire de 512 bits. 3: B = A (mod N) est exécuté 100 fois pour un N 4: le nombre d'éléments contenus dans la table est 32 (2) nombre d'opérations d'addition utilisées en une seule fois au cours de l'opération de réduction, lorsque l'algorithme de la présente invention est supérieur à l'algorithme conventionnel: 134,32 additions par réduction. (3) nombre d'opérations d'addition utilisées en une seule fois au cours de l'opération de réduction, lorsque l'algorithme conventionnel est supérieur à l'algorithme de l'invention: 137, 53 additions par réduction. Dans le tableau "*" indique les cas dans lesquels la méthode conventionnelle est meilleure. - - Etat =- o.....Algorithme proposé Algorithme conventionnel... 1 1 352 500 1 389 282 + 36 782 2 1 270 959- 1 297 347 + 20 388 3 1 392 805 1 411 866 + 19 081 4 1 328 527 1 350 030 + 21 503 1 240 833 1 291 009 + 50 176 6 i 341 579 1 386 072 + 4 493 7! 385 147 1 417 932 32 785 8 1 322 977 1 367 321 + 44 344 9 1 233 809 1 369 281 1 35 472 1 500 023 1 439 361 - 60 662 il 1 556 986 1 446 9i9 - 110 067* 12 1 031 995 1 494 389 +4 62 394 13 1 39I 801:! 385 068 + 6 733 14 1 869 304 1 124 769 - 744 535 1 328 821 1 386 180 + 57 359 16 1 384 342 1 492 727 108 385 17! 431 188 1 499 430 + 68 242 18 1 268 503 1 308 922 + 40 419 19 1 392 834 1 449 149 + 56 315 1 358 019 1 31 865 - 4! 154 * 21 1 685 774! 321 166.. - 364 658* 22 1 450 890 1 422 326 - 28 564.* 23 1 97 291 1 I3 l,6 - 63 097 24 1 299 832 1'362 249 + 62 417 1 242 391 1 35i 493 +'109 162 26 1 421 763 1 522!24 + 100 388 27 1 409 829 1 420 723 + 10 894 28 1 310 560! 350 715 + 40 155 29 1 699 823 1.304-909 - 394 914 1 223 574 1 302 423 78 849 8! 1.391 700 1 406 007 + 14 307 32 r 431 471-. !487 634 + 58 163. 33 1 470 137 r462 661 - 7476 34 1 323 150! 1355 076 + 31926 1 619 725 1 390006 - 229 719 6. 1 766 667 1 234 038 - 532 629 37 1-324 599 1 373 2.0 + -9 211 38 1 287 884 1 297 056 9172 -3 1 299 470 1 325 298 25 828 ! 420 875 1 504 611 + 83 736 41 1 405 389 1 442 + 36 9 83 42 1 385 644 1 4!3. 467 27 823 4 3 1 L96 608 1.319 600 22 992 44 1 296 700 1 348170 5Il 470 1 501 683 1 5!5 + 13 601 4- 4.4C36. 1 540250 - 100 714 47 1 29 2È9 1 3 061 79792 43 1 328 022 1 405 252 - 77.230 9 i 343 236 1 93S - 60 750 501 3 85 5j9 1 357 9c9 - 27 50 + 214 70f3 --+ d 294 / ifois Analyse des résultats Lorsque l'algorithme de réduction conventionnel et l'algorithme de réduction de la présente invention disposent tous deux de la table de 32 éléments et sont exécutés à leur vitesse la plus rapide, le nombre d'opérations d'addition est de 103 pour réduire un nombre à 1024 bits. 512]1 (log232 _ Comme cela ressort de ces résultats, il y a une probabilité de 76% pour que l'algorithme de la présente invention soit supérieur à l'algorithme conventionnel pour un N arbitraire. De même, dans le cas o l'algorithme conventionnel est meilleur, 137,53 additions en moyenne sont nécessaires. Second mode de réalisation de la présente invention Le second mode de réalisation de la présente invention est le résultat de l'exécution de 10 000 réductions pour un N déterminé. L'algorithme proposé a eu recours à 1 268 663 opérations d'addition pour l'exécution des 10 000 réductions, tandis que l'algorithme conventionnel a dû recourir à i 315 858 opérations d'addition pour l'exécution de ces 000 réductions. LlCD i..! I, I I. i. I C,)t icirir-i Il II! II i II I.IIi " iII Il I r iI r I tg) IHH.H.HI +'HHHHH HHHHHI 1HHHHHI I.,.HHH -HHHHHI I.HHHHH n 1000001 îooooacg.0 00 01 0 00 0 0 001 1 100 0 001, 10 0 0 Il II 11 I"1 I IIIi r J i.......IIn1 r..... n.0 i loiHOHH 1]u - .oo o 0 00 o::]oooooooooooooooooooooooo0 IIjI I't à 1/ U (at À I'J. e,CD-s i= IlIIc IIi_i lIç.nII lCiiit I m(r çy)çr (I'U' -,1. Co,CI I Ilt-,I.- - 0c]() C 1t cIli I t' Cr, I e.uI CI) or.) c tg) t I I À iliI...î1, cqic i Cq Cq cIl 11 >q1 iqiCM 1 1 s ii I l i ' tlj3; ac,, ilzo 14CNC)ilIriDC0()C1 Ie-(iaci -IcIC I)i i 1*1Il 'I I.Il -*.I Il iI--Ii ' O II LIIr Il' 1.0o,oI.,,,,,,,15 gç I I À g-4 [' 'q'n, 3 1 (,f '1'. (ó) 3,'q n %{') 1 ' t tf . C É (' '"l "' 'P ',ls ' ' ' | tsn,1,' '. I.' -r4 Ic, I3 i> I t-IOC "I CgI*.O o(1)- - t(3.I-IIIII II 1I.I oooI,o I;jIoo.ooo **,.,**,,, o,,o ***....!',,;ie!'oo,oo*....... o i_IIe 1.1efIii.*0. II1' 5ri IIeIIII II t I.O I I r4 'r Co { "1>1 IcluICIîrI y') Jl Cf c-'l Cl '.-e ''t, 101=" w-tI' (\1:-ll mO,"l,-0.-4tr"4> -1-. Z-jgI îI L>>.-.o,..'rcî P)ri I)ceCoCI'CCII r,lo v5- c"C, 'c") %tg) d CI) C c "r (") I -) !S3!! 331'&1-18!&!! 21&2!C 1 ' C CI IM tIIItIIIIt-j lI.III ïo!ootoioi I I Imw IfCI CD,,(tI I"CI '.':: I.3.l ' !i I.-, C \(O-!c r- r,'--I I-I It-I I,--Ii,<>i -- 1 i;ïlVl'I- i1IlU).1tB I I l' IIuItt 1 o j3 ce iUito'tr t 1 o,.>, c'jII À'.c Il(Ii4 I '. ' ( O cx) 1 C]' ó,.1'. (1,0 r. i-. t', ql- ' ' iRJ l9 à.([ I SI COtDOlO I | I *tO((D1 1 I Dm r I t I tm I Im ti i I t! Ii t,, t,! EI tO OI I.. I (, t-- I - - I. '." I .I I 0 00 -.F- '' 4Ì- 4 -I-FF-FF-F |F-11--F--F i8i::ji0I _|I Ii LUi t] u ' @ O. I ffi, I I--,l l ll l l l I F-2(J tt4h)I F-INA fJ.'-|t)tX t) F- I JASt)t^-tt >)i - - F' - 0 C I tÈ 0.. F- tF -> -t -| |F -F -F t F- tG | lto M) Q! l'!!t Analyse des résultats Dans le cas o l'algorithme de réduction conventionnel et l'algorithme de réduction de la présente invention sont tous deux exécutés à leur vitesse la plus rapide, le nombre d'opérations d'addition de bits n est de 1, lorsque l'algorithme de réduction est appelé une fois. Plus de 10 300 opérations d'addition de bits n vont donc être exécutées étant donné que l'algorithme de réduction est appelé 10 300 fois pour chacun des nombres du mode de réalisation ci-dessus de la présente invention. La mise en oeuvre de la présente invention démontre la supériorité de l'algorithme de la présente invention pour la plupart des N produits arbitrairement. Une fois que N a été déterminé, il est, d'une manière caractéristique, utilisé un nombre considérable de fois. N ne sera remplacé que lorsqu'il sera le produit de deux nombres premiers supérieurs à 256 bits et que les informations concernant la résolution du facteur premier de N seront connues. Toutefois, si N est supérieur à 512 bits, il est considéré comme sûr et n'a pas à être remplacé périodiquement. La probabilité de supériorité de l'algorithme proposé sur l'algorithme conventionnel pour un N arbitraire est de 76%. On peut donc dire sans risque que l'algorithme proposé est supérieur à l'algorithme conventionnel. Le second mode de réalisation ci-dessus est le résultat de l'exécution de 10 000 réductions pour n'importe quel N déterminé. Il a été prouvé que pour ce N déterminé, l'un des deux algorithmes est plus rapide que l'autre dans presque tous les cas. Comme cela a été mentionné précédemment, la présente invention offre l'avantage d'exécuter des opérations de réduction à une plus grande vitesse comparativement à un algorithme de réduction conventionnel utilisant une table précalculée de même taille, en réduisant le nombre d'opérations d'addition pendant une opération de réduction modulo. Bien que la description précédente ait porté sur des modes de réalisation préférés de la présente invention, celle-ci n'est bien entendu pas limitée aux exemples particuliers décrits et illustrés ici, et l'homme de l'art comprendra aisément qu'il est possible d'y apporter de nombreuses variantes et modifications sans pour autant sortir du cadre de l'invention. REVENDICATIONS 1. Procédé de réduction modulo destiné à être mis en oeuvre notamment en association avec des cartes à mémoire comportant des moyens de calcul matériels, caractérisé en ce qu'il comprend les étapes qui consistent à: (1) rechercher une valeur mémorisée dans une table à l'aide d'un index d'un nombre à bits de poids fort et ajouter la valeur mémorisée dans la table à un nombre à bits de poids faible; (2) si le résultat obtenu à partir de l'addition du nombre à bits de poids faible et du nombre recherché dans la table au cours de l'étape (1) produit un dépassement de capacité (1 bit), supprimer le dépassement de capacité et terminer l'exécution d'une opération; et (3) si un dépassement de capacité n'a pas lieu au cours de l'étape (2), ajouter N sur un modulo N au résultat obtenu à partir de l'étape (1) et terminer l'exécution de l'opération. 2. Procédé selon la revendication 1, caractérisé en ce qu'une valeur dont le bit de poids le plus fort (MSD) est 1 est sélectionnée lorsque la valeur de N est déterminée au cours de l'étape (3). 3. Procédé selon la revendication 2, caractérisé en ce que la valeur mémorisée dans la table est une valeur correspondant à un nombre à bits log2t + 1, et le nombre à bits de poids fort est log2t(t1l). 4. Procédé de réduction modulo destiné à être mis en oeuvre notamment en association avec des cartes à mémoire comportant des moyens de calcul matériels, comprenant les méthodes suivantes de construction d'une table précalculée RT[X_0] à l'aide d'un index d'un nombre à bits (k-n) de poids fort pour un nombre à bits k(k>n) X et un modulo à n bits N arbitraires: (1) x O = 1,..., 2k-n 1 (2) RT[X_0] E (X_0+1) x 2n(mod N) 5. Procédé selon la revendication 4, caractérisé en ce que dans le cas de RT[X_O] + N 2n(mod N)) + N est utilisé.