Embed Size (px)
Citation preview
ENS Cachan - Antenne de BretagneUniversite Bordeaux I - Master cryptographie et Securite Informatique
Rapport de stage de fin d’etudes
Effectue chez Thales
Developpement et qualification d’unebibliotheque de calculs algebriques appliques a
la cryptographie sur GF (2d)
Thomas [email protected]
4eme annee de Magistere de MathematiquesMaster Cryptographie et Securite Informatique
06.43.28.68.25
2 Avril 2012 - 28 Septembre 2012
Thales Communications & Security Responsables de stage4, Avenue des Louvresses Sylvain Lachartre92622 Gennevilliers [email protected]
Olivier [email protected]
Tuteur de l’ecoleGuilhem [email protected]
2
Remerciements
Je tiens a remercier mes tuteurs de stage, Olivier Orciere et Sylvain Lachartre, qui m’ont fourniun suivi regulier et sans faille pendant toute la duree de mon stage. Leurs nombreuses remarques,de forme comme de fond, ont grandement aiguille et ameliore mon travail.
Je remercie mon tuteur ecole, Guilhem Castagnos, pour son suivi et notamment pour etre venua Colombes en Juillet verifier le bon deroulement de mon stage.
Je tiens egalement a remercier Eric Garrido pour m’avoir accueilli au sein de son laboratoire, etpour l’enthousiasme et le soutien qu’il a portes a mon projet de these.
Un grand merci a tous les membres du laboratoire Chiffre : Renaud, David, Alexandre, Emeline,Matthieu, Philippe et Sandra pour leur aide et la tres bonne ambiance qui regne au sein de l’equipe.
Et bien evidemment merci a Romain, Aurore et Christopher pour leur bonne humeur et pouravoir supporte mes nombreuses questions et remarques pas toujours pertinentes.
3
Table des matieres
Presentation de l’entreprise 7
Introduction 9
1 Reduction de polynomes modulo p 121.1 Implementation logicielle de GF (2d) . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.3 Mes contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.1 Reduction mot-a-mot forte . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.3.2 Le probleme du rebouclage . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.3.3 Comment eviter le rebouclage . . . . . . . . . . . . . . . . . . . . . . . . . . 171.3.4 Reduction mot-a-mot Generique . . . . . . . . . . . . . . . . . . . . . . . . 181.3.5 Generateur de code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3.6 Reduction tabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4 Reduction de Barrett . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241.4.1 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241.4.2 Implementation et contributions personnelles . . . . . . . . . . . . . . . . . 25
1.5 Comparatif et conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2 Multiplication 292.1 Multiplication suivie d’une reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 292.2 Multiplication avec precalculs (Mastrovito) . . . . . . . . . . . . . . . . . . . . . . 31
2.2.1 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.2.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3 Changement de representation (Montgomery) . . . . . . . . . . . . . . . . . . . . . 32
2.3.1 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.3.2 Contributions personnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.3.3 Comparaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 Exponentiation 413.1 Exponentiation de Montgomery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.1 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.1.2 Implementation et contributions . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 Methodes 2k-aires d’exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.2.1 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.2.2 Mes contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4 Inversion 474.1 Inversion exponentielle rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.1.2 Analyse de complexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.1.3 Comparaison avec la methode ”square-and-multiply” . . . . . . . . . . . . . 49
4.2 Inversion exponentielle par blocs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.2.2 Analyse de complexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4
4.2.3 Tests, comparaison avec la methode ”square-and-multiply” . . . . . . . . . . 514.3 Inversion par l’algorithme d’Euclide etendu . . . . . . . . . . . . . . . . . . . . . . 52
4.3.1 Etat de l’art et implementation . . . . . . . . . . . . . . . . . . . . . . . . . 524.3.2 Tests, comparaison avec les autres methodes . . . . . . . . . . . . . . . . . 53
5 Implementation 555.1 Comparaison avec Magma, NTL et PARI/GP . . . . . . . . . . . . . . . . . . . . . 555.2 Outils de qualification de code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.2.1 Valgrind : analyse dynamique de l’execution d’un programme . . . . . . . . 565.2.2 Codecov : couverture de code . . . . . . . . . . . . . . . . . . . . . . . . . . 565.2.3 Pmccabe : complexite cyclotomique d’un programme . . . . . . . . . . . . . 565.2.4 Cross-compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.2.5 Autres outils de qualification de code . . . . . . . . . . . . . . . . . . . . . . 56
5.3 Denombrement des polynomes admissibles pour la reduction forte . . . . . . . . . . 56
Conclusion 58
Bibliographie 59
A Reductions generees par le generateur de code pour w=32 60
5
Table des figures
1 Presence de Thales dans le monde . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Domaines d’activite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1 Reduction bit-a-bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.2 Reduction mot a mot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3 Rebouclage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.4 Cas particuliers de reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.5 Temps d’execution ajoute a la multiplication pour d = 1...256 . . . . . . . . . . . . 221.6 Temps d’execution ajoute au carre pour d = 1...256 . . . . . . . . . . . . . . . . . . 221.7 Comparatif des reductions avec la reduction bit-a-bit et le produit polynomial . . . 261.8 Comparatif des reductions entre elles . . . . . . . . . . . . . . . . . . . . . . . . . . 271.9 Forces et faiblesses des fonctions de reduction . . . . . . . . . . . . . . . . . . . . . 28
2.1 Temps d’execution de la multiplication pour differentes reductions et d = 1...2048 . 302.2 Temps d’execution du carre pour differentes reductions ,d = 1...2048 . . . . . . . . 302.3 Temps d’execution du produit de Mastrovito d = 1...256 . . . . . . . . . . . . . . . 322.4 Reductions de Montgomery comparees a celles deja existantes . . . . . . . . . . . . 382.5 Reductions generique, table et de Montgomery pour |p| = bd/3c . . . . . . . . . . . 392.6 Reductions generique, table et de Montgomery pour |p| = bd/3c . . . . . . . . . . . 39
3.1 Comparatif des exponentiations 2k-aires pour d = 10...512 . . . . . . . . . . . . . . 443.2 Comparatif des exponentiations 2k-aires pour d = 10...1024 . . . . . . . . . . . . . 443.3 Comparatif des exponentiations 2k-aires pour d = 10...2048 . . . . . . . . . . . . . 453.4 Ratio M
S (d) pour d = 10...2048 et p un pentanome . . . . . . . . . . . . . . . . . . 46
4.1 Inversion exponentielle par blocs de taille k pour d = 10...512 . . . . . . . . . . . . 514.2 Inversion exponentielle par blocs de taille k pour d = 10...4096 . . . . . . . . . . . 514.3 Comparatif des differentes methodes d’inversion pour d = 10...512 et p un pentanome 534.4 Comparatif des differentes methodes d’inversion pour d = 10...2048 et p un pentanome 54
5.1 Comparatif entre LibCryptoLCH, NTL et PARI/GP . . . . . . . . . . . . . . . . . 555.2 Nombre estime de trinomes et pentanomes irreductibles de la forme p(x) = xd+r(x),
ou d◦r < w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
A.1 Reduction polynomiale pour (d, p) = (163, x163 + x7 + x6 + x3 + 1) et w = 32 . . . 61
6
Presentation de l’entreprise
Le groupe Thales
Aujourd’hui le groupe Thales est le leader mondial des systemes d’informations critiques. En2011, la societe Thales a realise un chiffre d’affaire de 13,03 milliards d’euros, base principalementsur les marches de l’aeronautique/espace, de la defense et de la securite. Le groupe compte 68 000salaries, dont la moitie hors de France repartis dans 50 pays differents. Son siege social se situe aNeuilly-sur-Seine. Depuis aout 2009, la societe est dirigee par Luc Vigneron.
Figure 1 – Presence de Thales dans le monde
Thales concoit, developpe et realise des solutions de tres haute technologie qui repondent auxbesoins de securite, de communication et d’information dans le domaine militaire mais aussi ledomaine civil. Le groupe se decompose ainsi en deux poles d’activite : l’Aeronautique et Espace(Dual) et la Defense et la Securite (Civil).
7
Figure 2 – Domaines d’activite
Thales Communications & Security
Thales Communications & Security est detenue a 100% par le groupe Thales. Dans l’or-ganisation actuelle, cette societe fait partie de la division Systemes C4I de Defense & Securite(Computerized Command, Control, Communications and Intelligence).
Thales Communications & Security developpe des produits modulaires, securises et interope-rables. Il s’agit d’equipements de radiocommunications, de reseaux et de systemes d’infrastructure,de systemes de protection ou encore de solutions de securite de l’information, de controle ferro-viaire, de billettique ou de securite urbaine.Ses clients sont principalement des forces armees (terre, air, mer), des structures interarmees etdes forces speciales ainsi que des services de securite civile.
Thales Communications & Security emploie pres de 7 000 collaborateurs repartis sur huitprincipaux sites en France : Brive, Cholet, Gennevilliers, Lambersat, Laval, Bretigny-sur-Orge,Toulouse et Velizy.
Son siege social est localise au 4, Avenue des Louvresses, a Gennevilliers (92).
Le Laboratoire Chiffre
Le laboratoire Chiffre est rattache au service SCC (Service Cryptologie et Composants) lui-meme dependant du service SSI (Securite des Systemes d’Information) et ce au sein de la divisionLand & Joint Systems (Systemes Terre et Interarmees). Cette division est un acteur majeur de latransformation du combat aeroterrestre et contribue a la superiorite operationnelle des Forces parla maıtrise de l’information.
Elle offre une gamme complete de solutions terrestres, des systemes de renseignement, com-mandement et communication bout-en-bout interoperables pour les operations interarmees et info-centrees, et des equipements de communication et d’optronique pour les milieux aerien, terrestreet marin. Ses clients sont les trois forces armees, structures interarmees, gouvernements, agencesd’armements, plateformistes.
Le laboratoire Chiffre est compose de specialistes en mathematiques et algorithmie appliqueesa la cryptographie. Ses principales missions sont la realisation d’etudes amonts en cryptographiefondamentale, l’integration d’algorithmes et de mecanismes cryptographiques definis par la DGA-MI dans les composants gouvernementaux, la realisation de dossiers cryptographiques sur desequipements ou des systemes et la participation a des projets de recherche collaboratifs.
8
Introduction
L’utilisation des corps de la forme GF (2d), ou corps finis binaires, est largement repandue encryptographie, par exemple dans les protocoles AES ou ECDSA. Il est donc necessaire de disposerde bibliotheques permettant d’effectuer rapidement et de maniere fiable tous les calculs usuels surles corps binaires : addition, multiplication, exponentiation, inversion...Le corps GF (2d) est egal a F2[x]/(p(x)), ou p(x) = xd + r(x) est un polynome irreductible dansF2[x].
La maniere la plus evidente, mais egalement la plus simple et bien souvent la plus rapide d’ef-fectuer des calculs dans GF (2d) est de representer un element a de GF (2d) de maniere unique par
un polynomes binaire A(x) =∑d−1
i=0 aixi de degre 6 d−1. Ce meme polynome peut etre represente
par un element N ∈ J0; 2d − 1K unique par la bijection A(x) =∑d−1
i=0 aixi 7→ N(A) =
∑d−1i=0 ai2
i.Enfin, si on considere que les mots machine ont une taille w, ce nombre N(A) peut etre simule
par une liste de mots machine [N0, N1, ..., Ndd/we−1], ou∑dd/we−1
i=0 Ni2iw est la representation de
N(A) en base 2wi.Le resume de ces transformations figure sur le diagramme suivant :
GF (2d) ↪→ F2[x] → J0; 2d − 1K → [0; 2w − 1]dd/we
a 7→ A(x) =∑d−1
i=0 aixi 7→ N =
∑d−1i=0 ai2
i 7→ [N0, N1, ..., Ndd/we−1]
Cette representation est parfaitement adaptee pour l’addition qui consiste simplement a XOR-erles mots machine. Cependant, les autres operations ne se font pas de maniere aussi simple. Leproduit est le plus souvent un produit sans retenue suivi d’une reduction modulo un polynome,deux operations ne pouvant pas etre realisees de maniere immediate via une instruction processeur.Il en est de meme pour l’exponentiation et l’inversion.
Une autre possibilite aurait ete d’utiliser les representations en bases normales, que j’ai volon-tairement laissees de cote car 6 mois n’auraient pas suffi pour correctement les etudier en plus desautres taches que j’ai realisees.
Le theme premier de mon stage etait d’implementer une methode de reduction modulaire quiexploite l’architecture de mot machine, dans la librairie proprietaire de Thales, la librairie Lib-CryptoLCH. Si cela a effectivement constitue un des fils conducteurs de mon stage, celui-ci s’estetoffe pour porter egalement sur d’autres methodes de multiplications ainsi que les autres opera-tions dans GF (2d) : l’exponentiation et l’inversion.Un autre aspect de mon stage a ete d’assurer la robustesse et la portabilite du code que j’avaisecrit, et de maniere plus generale de toute la librairie.
Un chapitre sera consacre a chacune de ces operations :– la reduction modulo un polynome– le produit dans GF (2d)– l’exponentiation dans GF (2d)– l’inversion dans GF (2d)
Dans chaque chapitre, les complexites des differentes methodes seront donnees et des graphiquescomparatifs viendront etayer ces resultats.Enfin, un chapitre sera dedie a l’implementation de ces methodes dans la librairie.
9
Notations
Symbole SignificationComplexites M : produit dans GF (2d)
S : carre dans GF (2d)RB , RG, RT , RF , RP , RM : reductions de Barrett, Generique, Table, Forte, Precalculee, de Montgomery.SB , SG, ST , SF , SP , SM : carres avec les differentes reductions.MB ,MG,MT ,MF ,MP ,MM : produits avec les differentes reductions.INV EXB : inversion exponentiative par blocsINV EXR : inversion exponentiative rapide
d Le degre d’extension du corps binaire dans lequel on travaille.GF (2d) Le corps fini a 2d elements, aussi note F2d
p(x) Le polynome d’extension de GF (2d), par hypothese de degre d et irreductible sur F2[x].On a GF (2d) = F2[x]/(p(x)).
nb Dans le corps GF (2d) = F2[x]/(p(x)), nb designe le poids de Hamming de p : nb = |p|.nb est donc egal au nombre de coefficients non-nuls de f .En pratique, on choisit p de sorte que nb = 3 ou 5.
w La taille des mots machine. Celle-ci depend du processeur et vaut generalement 8, 16, 32 ou 64.nw(d,w) Le nombre de mots machine necessaires pour representer un polynome de degre d− 1.
nw(d,w) = d dw e. En l’absence d’ambiguıte, on notera simplement nw.nw2(d,w) Le nombre de mots machine necessaires pour representer un polynome de degre 2(d− 1).
nw2(d,w) = d 2d−1w e. En l’absence d’ambiguıte, on notera simplement nw2.
nwp(d,w) Le nombre de mots machine necessaires pour representer un polynome de degre d.nwp(d) = dd+1
w e. En l’absence d’ambiguıte, on notera simplement nwp.
r(x) Lorsqu’on etudie l’exponentiation de Montgomery-Koc-Acar, r = xdd/wew mod p.Dans tout autre contexte, r = xdd/wew mod p, de sorte que p(x) = xd + r(x).
Red Designe la reduction modulaire : Red(a) = a mod pRedB,RedG,RedM,RedP,RedT,RedF designent respectivement les reductions :de Barrett, Generique, de Montgomery, Precalculee, Table etForte.
d◦f Le degre de fval(f) La valuation de f : val(f) = max{d, xd divise f}H, I,B Pour un polynome represente sous forme dense, H designe le mot d’indice nw2− 1,
I les mots d’indice nw − 1 < i < nw2− 1, et B le mot d’indice nw − 1
Par souci de confidentialite et de concision, ce rapport ne contiendra aucun programme en C.
Les programmes seront presentes sous deux formes : soit sous la forme d’un algorithme haut-niveau, soit en pseudo-C, qui est une version simplifiee du C, et reprend la plupart des operateursutilises en C, dont on rappelle la signification ci-dessous :
Symbole Signification en pseudo-C>>,<< SHIFT de mots machine (ie division et multiplication par des puissances de 2)^ XOR de mots machinea%b Reste de la division euclidienne entiere de a par b:= Affectation== Test d’egalite!= Test de differencea^=b XOR en place : a := XOR(a, b)a+b Cet operateur est utilise indifferemment pour sommer des entiers ou des elements de GF (2d)
pow(a,b) ab
gf L’instance du corps binaire sur lequel on travaille. C’est un objet de type Gf2eData_t quiencapsule plusieurs donnees : le degre du corps, son polynome d’extension...
Ja; bK [a; b] ∩ NJa; bJ [a; b[∩N
10
Calcul des complexites des programmes en pseudo-C
Les programmes presentes en pseudo-C subiront une analyse de complexite. Etant donne l’im-portance que l’on portera pendant ce rapport a la rapidite d’un programme, il est necessaired’evaluer tres precisement cette complexite.
Par consequent, les analyses de complexite de programmes en pseudo-C evalueront le plus pre-cisement possible le nombre :
– d’operations logiques : les SHIFT, XOR, masques... (operations peu couteuses)– d’operation arithmetiques : les additions, soustractions, divisions... (operations moyennement
couteuses)– d’acces memoire : lecture et ecriture (operations au cout variable)– de branchements : les operateurs if, while, switch... (operations tres couteuses)
Methodologie des benchs
Les tests ont tous ete realises sur la meme machine, une station de travail dotee d’un processeurIntel Celeron E3400 cadence a 2.6 GHz, de 2Go de RAM et tournant sous Ubuntu 10.10.Pour mesurer le temps d’execution d’une fonction, celle-ci est executee 1 000 000 fois de fois (dansla mesure du possible) et le temps ecoule est mesure avec la fonction Gettimeofday, qui permetune precision a la microseconde pres.Par consequent, tous les graphiques de ce rapport affichent le nombre de microsecondes necessairespour executer 1 000 000 fois une fonction.
11
Chapitre 1
Reduction de polynomes modulo p
La multiplication dans GF (2d) est, avec l’addition, une brique de base des calculs dans GF (2d).Mais si l’addition peut s’effectuer tres rapidement (il suffit de XOR-er tous les mots), il n’existepas d’instruction processeur realisant la multiplication dans GF (2d).Une solution souvent utilisee consiste alors a realiser un produit polynomial suivi d’une reductionmodulo p, ou p(x) = xd + r(x) est le polynome de F2[x] qui definit l’extension GF (2d). La librairiesur laquelle je travaille, LibCryptoLCH, dispose deja d’algorithmes efficaces pour realiser le produitpolynomial et la premiere tache de mon stage a ete de completer ce produit en implementant lareduction modulo p.
1.1 Implementation logicielle de GF (2d)
Dans la librairie, le corps est represente par une structure contenant, entre autres, tous lesparametres dont j’aurai besoin pour realiser la reduction modulaire.
typedef struct {
unsigned int d; /**< degre de l’extension */
sGF2X_t p; /**< polynome d’extension sous forme creuse */
/**< On stocke la liste des coefficients non nuls de p */
unsigned int nb; /**< poids de Hamming du polynome d’extension */
Word_t denseModulus[NW]; /**< l’element de GF(2^d) representant r(x) = x^d mod p*/
unsigned int nw; /**< nombre de mots machine d’un element du corps */
Word_t mask; /**< masque pour la reduction du dernier mot */
/**< 1 sur les d%w bits de poids faible, 0 ailleurs */
WordList_t tmp; /**< variable intermediaire pour les calculs */
} Gf2eData_t;
Les elements de GF (2d) sont quant a eux representes par une liste de mots machine :
typedef Word_t GF2E_t[NW]; /**< Type des element d’un corps de la forme GF(2^n)*/
1.2 Etat de l’art
Presentons le contexte :- le corps est F2d , le polynome associe est p(x) = xd + r(x) = xd +
∑nb−2j=0 xaj , ou nb = |p| est le
nombre de cœfficients non-nuls de p- chaque mot machine peut contenir w bits, et par consequent il faut nw := dd/we mots machinepour contenir un element de F2d .- la reduction, dans notre cas, est toujours employee apres une multiplication ou un carre poly-nomial : on reduit des polynomes de degre au plus 2(d − 1), donc on stocke 2d − 1 bits, ce quinecessite nw2 := d(2d− 1)/we mots machine.
12
Il s’agit de l’application lineaire
Red : F2[X] → GF (2d)a(x) 7→ a(x) mod p(x)
Reduction bit-a-bitSous sa forme naıve, la reduction est effectuee bit-a-bit :
Reduction_Bit(a(x)):
| for (i=d-2...0)
| | if(a[d+i]==1)
| | | a[d+i]:=0;
| | | for(j=0...d-1)
| | | | a[i+j] ^= r[j];
| | | endfor
| | endif
| endfor
end
Complexite :
– d2
2 operations logiques
– d2
2 operations arithmetiques
– (d−1)2
2 acces memoire– d− 1 branchements
Nous avons tout interet a choisir un polynome d’extension p creux. En effet, si |p| est faible (|p|est le nombre de cœfficients non-nuls de p), alors nous aurons beaucoup moins de XOR a effectuerlors de la reduction.En pratique, p sera souvent un trinome ou un pentanome (a part pour d = 1, il n’existe pas debinome ou tetranome irreductible dans F2[X], car 1 serait alors une racine de ce polynome...).
Une amelioration consecutive a cette observation consiste a stocker le polynome p non seulementsous forme de tableau de mots, mais egalement sous la forme de la liste de ses cœfficients non-nuls,en encapsulant ces donnees dans les parametres du corps GF (2d)Une fois cette amelioration implementee, gf->nb renvoie nb = |p|, et gf->pExt.pos (qu’on abregep) donne un tableau contenant dans l’ordre croissant les nb cœfficients non-nuls de p.
Reduction_Bit_2(a):
| for (i=d-2...0)
| | if(a[d+i]==1)
| | | a[d+i]:=0;
| | | for(j=0...nb-2)
| | | | a[i+p[nb]]^=1;
| | | endfor
| | endif
| endfor
end
Figure 1.1 – Reduction bit-a-bit
13
Complexite :
– (nb−1)(d−1)2 operations logiques
– nb(d−1)2 acces memoire
– (nb+1/2)(d−1)2 operations arithmetiques
– d− 1 branchementsOn n’utilise pas la structure de mot machine. Par exemple, une machine avec une architecture 64bits mettra sensiblement moins de temps a XOR-er deux mots de 64 bits qu’a XOR-er un a un les64 bits de ces deux mots.Mes premieres contributions, qui figurent dans la partie suivante, ont ete d’exploiter le gain potentielapporte par la structure de mot machine.
1.3 Mes contributions
La bibliotheque disposait deja d’un algorithme efficace pour le produit de deux polynomesa(x), b(x) ∈ F2[x], construit sur un modele proche de celui presente dans [?] pour les valeurs faibleset moyennes de d.Seule la reduction modulaire posait probleme car ayant a mon arrivee un temps d’execution plusde deux fois plus eleve que le produit polynomial.
Ma contribution a ete de concevoir et d’implementer un algorithme similaire a Reduction_Bit_2,mais effectuant la reduction sur des mots entiers au lieu de la faire bit-a-bit.L’idee de la reduction mot-a-mot est de travailler sur des mots entiers.Soit T (x) un polynome tenant sur un seul mot machine. En remarquant que T (x) · xwi+d =T (x) · xwi · r(x) mod p(x), on obtient un moyen efficace de reduire un polynome par rapport aumot T d’indice i le composant : on recupere T , et on le ”redistribue” dans les mots d’indices plusfaibles comme indique sur la figure ci-dessous :
H I I B
H I I B
H I I B
H I I B
H I I B
H I I B
Figure 1.2 – Reduction mot a mot
14
1.3.1 Reduction mot-a-mot forte
Le premier algorithme mettant en œuvre ce principe admet comme hypothese supplementaired◦r < w (ou d◦r designe le degre de r), pour eviter des phenomenes de rebouclage que je detailleraipeu apres. Cette forte contrainte d’utilisation, et la plus grande rapidite qui en decoule, lui valentd’etre nommee Reduction Forte.
Reduction_Forte(a)
| k0 = arrondisup(d/w) ;
| quo = k0+d/w;
| rem = d%w;
| //Reduction de tous les mots a reduire sauf un
| for (k = k0...1)
| | quo--;
| | atmp = Selection_Mot(a, quo, rem);
| | MiseAZero_Mot(a, quo, rem);
| | for (i = 0...nb-1)
| | | a[k-1] ^= (atmp<<p[i]);
| | | a[k] ^= (atmp>>(w-p[i]));
| | endfor
| endfor
| //Reduction du dernier mot
| atmp = Selection_Mot(a, quo, rem);
| while (atmp != 0)
| | MiseAZero_Mot(a, quo, rem);
| | for (i = 0...nb-1)
| | | a[0] ^= (atmp<<p[i]);
| | | a[1] ^= (atmp>>(w-p[i]));
| | endfor
| | atmp = Selection_Mot(a, quo, rem);
| endwhile
end
La fonction Selection_Mot recupere le mot constitue des bits w ·quo+rem a w ·quo+rem−(w−1).Elle effectue 1 comparaison, 2 operations logiques, 2 acces memoire et 1 soustraction.La fonction MiseAZero_Mot met a zero les bits w ·quo+rem a w ·quo+rem− (w−1). Elle effectue4 SHIFT et 2 affectations.
Complexite :– 4nw(nb− 1) + 11 operations logiques– 4 + 2nw(nb+ 2) operations arithmetiques– 2nw + 2 acces memoire– 2nw + 4 branchements
Le gain theorique par rapport a l’algorithme precedent se situe entre w/4 et w/8. En pratique, cetalgorithme est environ 100 plus rapide que Reduction_Bit_2 !
15
1.3.2 Le probleme du rebouclage
On observe que lorsqu’on reduit a selon le dernier mot, on est parfois parfois oblige d’itererplusieurs fois la reduction. Ce phenomene est appele rebouclage. Il est du au fait qu’une operationde reduction peut impacter le mot qu’on vient de reduire.Si on leve la condition d◦r < w, le rebouclage peut se produire encore plus frequemment, commel’illustre la figure 1.3 :
H I I B
H I I B
H I I B
H I I B
H I II B
H I II B
...
...
Figure 1.3 – Rebouclage
Sur cet exemple, il faut effectuer trois iterations pour reduire un mot de poids intermediaire etdeux pour reduire le mot de poids fort (car le mot de poids fort est partiellement vide des le depart).
16
Un exemple plus concret illustre ce phenomene de rebouclage :
ExempleSoit GF (2w) = F2[x]/(xw + x3 + 1), avec w ≥ 8.Un mot que l’on souhaite reduire sera typiquement de la formea = A1(x) · xw +A0(x).Effectuons la reduction de a etape par etape :
– TMP(x)← A1(x);– A1(x)← 0;– a← a + TMP(x) + TMP(x) · x3
Apres cette premiere reduction, a = A1(x) · x3 +A1(x) +A0(x) = B1(x) · xw +B0(x)On a d◦B1 6 d◦A1 − (d− d◦r) 6 (w − 1)− (w − 3) = 2.d◦a 6 w + 2 et a necessite donc une autre reduction :
– TMP(x)← B1(x);– B1(x)← 0;– a← a + TMP(x) + TMP(x) · x3;
a est a present de degre au plus w − 1 et ne necessite plus de reduction.
1.3.3 Comment eviter le rebouclage
Formalisons le probleme du rebouclage :Reduire le mot T d’incide j revient a transformer T (x)·xwj en T (x)·(xwj−dr(x)), ce qui corresponda diminuer le degre d’une valeur d − d◦r. Le phenomene de rebouclage se produit donc quandd− d◦r < d◦T , car alors le polynome T (x) · (xwj−dr(x)) s’ecrit egalement sur le mot d’indice j.Observons comment eviter le rebouclage (N&S indique ”necessaire et suffisant”) :
1. Si w > 32w (ce qui est le cas ”general”) :
il est N&S que d− d◦r > (2d− 1) mod w pour eviter le rebouclage sur Hil est N&S que d− d◦r > w pour eviter le rebouclage sur les Iil est N&S que d− d◦r > (−d mod w) pour eviter le rebouclage sur B
2. Si w < d 6 32w :
il est N&S que d− d◦r > 2d− 1− 2w pour eviter le rebouclage sur Hil est N&S que d− d◦r > 2w − d pour eviter le rebouclage sur B
3. Si w2 < d 6 w :
il est N&S que d− d◦r > 2d− 1− w pour eviter le rebouclage sur Hil est N&S que d− d◦r > w − d pour eviter le rebouclage sur B
4. Si d 6 w2 :
il est N&S que d − d◦r > d − 1 pour eviter le rebouclage sur B, ce qui est par ailleursimpossible, sauf bien sur pour d > 1
Vous l’aurez compris, tout cela est bien complique et peut se resumer par ”il faut que d◦r soit leplus petit possible”. Par ailleurs, une CNS pour eviter le rebouclage est d− d◦r > w.
Bd 6 w2
H Bw2 < d 6 w
HH Bw < d 6 32w
Figure 1.4 – Cas particuliers de reductions
17
1.3.4 Reduction mot-a-mot Generique
L’algorithme precedent peut facilement se generaliser a un algorithme effectuant la reductionmot a mot dans un corps binaire generique GF (2d) = F2[X]/(p(x)), sans la moindre condition surp.La seule difference avec Reduction_Forte reside dans le fait que le rebouclage peut a present seproduire lors de la reduction de n’importe quel mot. A part cela, les deux algorithmes sont iden-tiques.
Reduction_Generique(a)
| k0 = arrondisup(d/w)
| quo = k0+d/w
| rem = d%w
| //Reduction de tous les mots a reduire sauf un
| for (k = k0...1)
| | quo--;
| | atmp = Selection_Mot(a, quo, rem)
| | while (atmp != 0)
| | | MiseAZero_Mot(a, quo, rem)
| | | for (i = 0...nb-1)
| | | | a[k-1] ^= (atmp<<p[i])
| | | | a[k] ^= (atmp>>(w-p[i]))
| | | endfor
| | endwhile
| endfor
| //Reduction du dernier mot
| atmp = Selection_Mot(a, quo, rem)
| while (atmp != 0)
| | MiseAZero_Mot(a, quo, rem)
| | for (i = 0...nb-1)
| | | a[0] ^= (atmp<<p[i]);
| | | a[1] ^= (atmp>>(w-p[i]));
| | endfor
| | atmp = Selection_Mot(a, quo, rem)
| endwhile
end
Complexite :La complexite est quasiment la meme que pour Reduction_Forte, si ce n’est l’ajout d’une bouclewhile (atmp != 0) qui rajoute nw branchements et nw acces memoire.
– 4nw(nb− 1) + 11 operations logiques– 4 + 2nw(nb+ 2) operations arithmetiques– 3nw + 2 acces memoire– 3nw + 4 branchements
Ce changement rend en pratique Reduction_Generique deux fois plus lent que Reduction_Forte,et montre bien a quel point les acces memoire et surtout les branchements peuvent etre couteux...On remarque que si p est dense, alors la complexite de Reduction_Generique est quadratique en d.S’il est creux comme c’est le cas dans la librairie (nous n’utilisons que des trinomes et pentanomes),la complexite devient lineaire en d.
1.3.5 Generateur de code
Bien que Reduction_Generique soit «tout-terrain», il souffre d’un defaut : sa lenteur. Cette re-marque vaut egalement, dans une moindre mesure, pour l’algorithme Reduction_Forte. Ces deuxalgorithmes peuvent rallonger respectivement de 20% et 10% la duree d’une multiplication. Bienque cet allongement s’attenue lorsqu’on augmente d, il peut exploser et atteindre 300% pour les
18
petites valeurs de d (notamment lorsque d◦r = d− 1).Or en pratique, on dispose dans la litterature d’algorithmes specifiques de reduction pour certainspolynomes.Par exemple, pour p(x) = x233 + x74 + 1 et w = 64 :
Reduction_233(a):
//Reduction du mot de poids fort
| T := a[7];
| a[7] := 0;
| a[3] ^= T<<23;
| a[4] ^= T<<33;
//Reduction des mots de poids intermediaires
| for (j = 1...3)
| | T := a[7-j];
| | a[7-j] := 0;
| | a[3-j] ^= T<<23;
| | a[4-j] ^= T>>41 ^ T<<33;
| | a[5-j] ^= T>>31;
| endfor
//Reduction du mot de poids faible
| T := a[3]>>41;
| a[3] &= 0x1ffffffffff;
| a[0] ^= T;
| a[1] ^= T<<10;
end
En s’epargnant nombre de comparaisons et de boucles conditionnelles, cet algorithme effectue lareduction considerablement plus vite que les deux precedents. Seul inconvenient, il doit etre redefinipour chaque valeur de d et pour chaque polynome d’extension p.J’ai donc ete charge de developper un generateur de code capable de calculer et d’afficher, pour toutcorps binaire fini, l’algorithme de reduction associe. La conception et l’ecriture de ce generateurs’avererent particulierement corsees.
La reduction d’un mot machine s’effectue ainsi :1. On copie le mot machine d’indice i dans un mot T avant de l’effacer. Cela correspond au retran-
chement du polynome∑(i+1)∗w−1
i∗w mj ∗ xj.2. Pour tous les pj , on rajoute T a l’indice k + pj , ou k = i · w − d.
Ce qui se traduit ainsi (en bleu sarcelle, ce que le generateur affichera/retournera en sortie) :1.T = tmp[i]; tmp[i] = 0;
2.a. k = j*w - d;.2.b. On cree deux tableaux quo[nb-1], rem[nb-1] qu’on remplit ainsi :quo[j] = (p_j+k)/w; rem[j] = (p_j+k)%w;
2.c. Si (rem[j] == 0), on affiche tmp[quo[j]] ^= T;
2.d. Sinon tmp[quo[j]] ^= T<<rem[j]; tmp[quo[j]+1] ^= T>>(w-rem[j]);
Bien evidemment, le generateur n’affiche pas en sortie quo[j], rem[j], ... mais leurs valeursnumeriques.En suivant ce raisonnement, j’ai programme un premier generateur rudimentaire :
19
Generateur_Basique(a,nb,nw,nw2):
| printf("\nvoid GF2E_Reduction_%lu(const Gf2eData_t*gf,WordList_t tmp,GF2E_t e)\n{\n",d);
| puts(" unsigned long T");
| for(i=nw2-1...nw)
| | printf(" T = a[%u];\n", i);
| | printf(" a[%u] = 0;\n",i);
| | k:= i*w - d;
| | for(j=0...nb-3)
| | | quo[j] := (p[j]+k)/w;
| | | rem[j] := (p[j]+k)%w;
| | | if(rem[j]==0)
| | | | printf(" a[%u] ^= T;\n",quo[j]);
| | | else
| | | | printf(" a[%u] ^= T<<%u;\n",quo[j],rem[j]);
| | | | printf(" a[%u] ^= T;\n",quo[j]+1,(w-rem[j]));
| | | endif
| | endfor
| endfor
| if(d%w != 0)
| | printf(" T = a[%u]>>u;\n",nw-1,d%w);
| | printf(" a[%u] &= %lu;\n",nw-1,gf->mask);
| | for(j=0; j<nb-2; j++)
| | | quo[j] = p[j]/w;
| | | rem[j] = p[j]%w;
| | | if(rem[j]==0)
| | | | printf(" a[%u] ^= T;\n",quo[j]);
| | | else
| | | | printf(" a[%u] ^= T<<%u;\n",quo[j],rem[j]);;
| | | | printf(" a[%u] ^= T>>%u;\n",quo[j]+1,(w-rem[j]));
| | | endif
| | endfor
| endif
| printf(" GF2E_Copy(gf,tmp,e);\n}\n");
end
Cet algorithme de generation affiche, pour d = 66 et p(x) = x66 + x3 + 1 :
void GF2E_Reduction_66(const Gf2eData_t*gf,WordList_t tmp,GF2E_t e)
{
unsigned long T;
T = tmp[2];
tmp[2] = 0;
tmp[0] ^= T<<62;
tmp[1] ^= T>>2;
tmp[1] ^= T<<1;
tmp[2] ^= T>>63;
T = tmp[1]>>2;
tmp[1] &= 0x3;
tmp[0] ^= T;
tmp[0] ^= T<<3;
tmp[1] ^= T>>61;
GF2E_Copy(gf,tmp,e);
}
20
On peut grandement ameliorer Generateur_Basique :
– Cet algorithme ne prend pas en compte le rebouclage !– il vaut mieux ecrire tmp[1] ^= T>>2 ^ T<<1; au lieu de tmp[1] ^= T>>2; tmp[1] ^= T<<1;
– Nous pouvons eviter de recalculer a chaque fois les tableaux quo[] et rem[] (sauf au momentde reduire le mot d’incide nw-1) : en effet, a chaque iteration, rem[] est constant et quo[]
voit tous ses elements decrementes de 1.– l’amelioration ci-dessus nous permet de remarquer qu’on peut ”reutiliser” pour chaque indicei, nw 6 i 6 nw2− 2, la reduction du mot i+ 1 : en effet si on effectue tmp[i+1] ^= T>>k;
au tour i+ 1, alors au tour i on effectuera tmp[i] ^= T>>k;. Cette observation, ainsi que lapremiere, nous pousse a utiliser un tableau de chaınes str[nw2] qui stocke les T>>k
– Certains decalages ne servent a rien. Ici, tmp[2] & 0xfffffffffffffff8 = 0, ie les 61 bitsde poids fort de tmp[2] sont a 0. Par consequent, pour k > 3, tmp[2]>>k == 0.De meme, faire T = tmp[nw-1]>>(d%w); tmp[j] ^= T>>k; est inutile quand k + d%w >= w.
Toutes ces ameliorations ont ete integrees a une nouvelle version de ce generateur de code, qui a etedecline en deux versions. L’une implemente une boucle for pour parcourir les mots intermediairesa reduire. L’autre deroule les boucles for, ce qui donne un code plus volumineux mais plus rapide.
Complexite :– 4nw(nb− 1) operations logiques– 0 operation arithmetique– nw · nbm acces memoire– 0 branchement
ou nbm est le nombre de mots modifies par la reduction d’um mot machine (typiquement nbm = 3ou 4).On elimine les operations logiques et surtout les branchements qui sont les operations les pluscouteuses.Les resultats sont eloquents : pour les corps binaires utilises par la librairie, le temps mis poureffectuer la reduction ne depasse que tres rarement 3% du temps mis pour effectuer la multiplication.
Comparaison avec la reduction forte et la reduction generique
La librairie LibCryptoLCH contient une liste de 256 polynomes creux irreductibles de degre dpour d = 1...256.A l’aide du generateur de code, j’ai genere les 256 fonctions de reduction correspondantes, quej’ai nommees Reduction_Precalculee_d, pour d = 1...256. En plus d’etre correctes, elles sontlargement plus rapides que Reduction_Forte et Reduction_Generique, comme le montrent lesgraphiques 1.5 et 1.6 :
– on gagne un facteur 5 par rapport a Reduction_Forte
– on gagne un facteur 10 par rapport a Reduction_Generique
– on gagne un facteur 1000 par rapport a Reduction_Bit_2 (non presente sur les graphiques)
Si la difference n’est pas tres marquee sur 1.5, elle est tres nette sur 1.6, et souligne l’importanced’avoir une bonne reduction lorsqu’on effectue beaucoup de carres modulaires (comme par exempledans le cas d’une exponentiation).Les fonctions Reduction_Precalculee_d ne rajoutent qu’un temps infime a la multiplication(moins de 4%)et au carre (moins de 20%).
L’annexe contient egalement les fonctions de reduction generees pour les parametres (d, p) re-commandes par le NIST ([?]) pour l’usage d’ECDSA. Ces fonctions ont bien sur ete testees et sontcorrectes.
21
Figure 1.5 – Temps d’execution ajoute a la multiplication pour d = 1...256
Figure 1.6 – Temps d’execution ajoute au carre pour d = 1...256
1.3.6 Reduction tabulaire
L’idee de la reduction tabulaire m’est venue en pensant au defaut de la reduction precalculee :bien qu’ultra-rapide, cette derniere souffrait du defaut de devoir etre precalculee, ce qui imposede connaıtre a l’avance le degre et le polynome de reduction du corps sur lequel on souhaitaittravailler.
22
J’ai donc reflechi a une methode de reduction qui tirerait parti de la possibilite de precalculer lesreductions, sans les contraintes qui pesent sur la reduction precalculee. La seule solution que j’aitrouvee a ete de stocker ces reductions dans les parametres du corps GF (2d) lors de son initialisa-tion, puis de les lire directement a chaque fois qu’une reduction etait necessaire.
La mise en place de cette methode a donc necessite deux algorithmes :– Un generateur, lance lors de l’initialisation du corps pour calculer et stocker toutes les reduc-
tions a effectuer– Un reducteur, qui lit les donnees du generateur chaque fois qu’il est necessaire d’effectuer une
reduction
La generateur fonctionne sur un principe tres similaire au generateur de code de la section pre-cedente, la seule difference est qu’il stocke les reductions a effectuer dans le corps au lieu de lesstocker dans un fichier texte. Ainsi, il calcule plusieurs listes :
– Le nombre nb loop de rebouclages a effectuer pour les mots de poids fort, intermediaire etfaible (3 valeurs a stocker)
– Pour chaque mot T := tmp[i] que l’on reduit, on calcule les listes de reductions de la formetmp[i-ls_1] := T<<ls_2, et ce que tmp[i] soit de poids fort, intermediaire ou faible (3listes de nb− 1 couples (ls_1,ls_2) a stocker)
– Pour chaque mot T := tmp[i] que l’on reduit, on calcule egalement les listes de reductionsde la forme tmp[i-rs_1] := T>>rs_2, (3 listes d’au plus nb − 1 couples (rs_1,rs_2) astocker, ainsi que le nombre nb_rs de reductions de cette forme)
Sachant que chaque valeur a stocker (ls1, ls2, rs1, rs2 ou le nombre de rebouclages) est un unsi-gned int, cela fait 12nb− 6 unsigned int a stocker dans les parametres du corps, ce qui est touta fait acceptable.
Pour le mot de poids fort, le reducteur fonctionne ainsi :
for(i=0...nbloop-1)
| T := tmp[nw2-1];
| tmp[nw2-1] := 0;
| for(j=0...nb-2)
| | tmp[ls1[j]] ^= T<<ls2[j];
| endfor
| for(j=0...nb_rs-1)
| | tmp[rs1[j]] ^= T>>rs2[j];
| endfor
endfor
Il fonctionne de maniere identique pour les mots de poids intermediaires et faible.
On suppose, comme dans les calculs de complexite precedents, que le polynome d’extension pa ete choisi judicieusement pour qu’il n’y ait pas de rebouclage.
Complexite :– 4nw(nb− 1) operations logiques– 0 operations arithmetiques– nw(4nb+ 2) acces memoire– 0 branchement
Bien que le nombre d’affectations, de XOR et de SHIFT soit tres faible, il y a beaucoup de lecturesd’elements de tableaux. Cependant, en pratique, cette reduction est quasiment aussi rapide que lareduction forte... et peut s’appliquer sans la moindre condition sur p.
23
1.4 Reduction de Barrett
La reduction de Barrett est une methode de reduction qui a ete introduite pour effectuer desreductions modulaires dans des anneaux Z/nZ de grand cardinal, mais qui peut etre adaptee a lareduction de polynomes modulo p(x).
1.4.1 Etat de l’art
Sous sa forme originale, la reduction de Barrett impose de precalculer µ(x) = x2d÷ p(x), c’est-a-dire le quotient de la division euclidienne de x2d par p(x).|µ| a un impact direct sur la complexite de la reduction : plus precisement, une etape de la reduc-tion a une complexite proportionnelle en |µ|.
Algorithm 1 Reduction de Barrett sur GF (2d)
Input: p(x) ∈ F2[X] de degre dA(x) ∈ F2[X] de degre < 2dµ(x) = x2d ÷ p(x)
Output: A(x) mod p(x)1: Q1(x)← A(x)÷ xd2: Q2(x)← µ(x)Q1(x)3: Q3(x)← Q2(x)÷ xd4: R1(x)← A(x) mod xd
5: R2(x)← p(x)Q3(x) mod xd
6: return R1(x) +R2(x)
Cependant, dans [?], Knezevic et al. montrent que si d◦r 6 bd2c, alors µ(x) = p(x) (la demons-tration est effectuee dans l’article). L’avantage est double :
– Nous n’avons pas besoin de precalculer µ– Nous savons que |µ| = |p| et pouvons par consequent minimiser la complexite de la reduction.
L’algorithme de reduction sans precalcul est donne par l’algorithme 2.
Algorithm 2 Reduction de Barrett sans precalcul sur GF (2d)
Input: p(x) = xd + r(x) ∈ F2[X] tel que d◦r(x) 6 bd2cA(x) ∈ F2[X] de degre < 2d
Output: A(x) mod p(x)1: Q1(x)← A(x)÷ xd2: Q2(x)← p(x)Q1(x)3: Q3(x)← Q2(x)÷ xd4: R1(x)← A(x) mod xd
5: R2(x)← p(x)Q3(x) mod xd
6: return R1(x) +R2(x)
Nous delaisserons par la suite la reduction avec precalculs pour nous focaliser sur la reductionsans precalcul pour les raisons suivantes :
– C’est plus simple a implementer– C’est tres peu restrictif du point de vue du choix de p(x). En pratique, ce n’est meme
pas du tout restrictif car avant meme de nous interesser a cet algorithme, nous choisissionssystematiquement des polynomes p(x) = xd + r(x) tels que r(x) 6 bd2c.
– Cela accelere donc la reduction car |µ| = |p|.
24
1.4.2 Implementation et contributions personnelles
Une etude de complexite rapide renvoie une tres mauvaise complexite pour la reduction deBarrett : 2 quotients de polynomes, 2 restes de polynomes, une somme de polynomes et surtoutdeux produits de polynomes.Fort heureusement, ces operations peuvent etre effectuees tres rapidement :
1. Les deux quotients en question sont des quotients d’un polynomes de degre 6 2d par xd. Celarevient donc simplement a effectuer des decalages de d dw e mots machine
2. Plutot que d’effectuer
R1(x)← A(x) mod xd;R2(x)← p(x)Q3(x) mod xd; rep← R1(x) +R2(x);
on peut remplacer cette suite d’instructions par
R1(x)← A(x);R2(x)← p(x)Q3(x); rep← R1(x) +R2(x) mod xd;
De plus une reduction modulo xd consiste simplement en 2d dw e mises a zero de mots machineet 2 XOR
3. les deux produits par p(x) sont les operations les plus couteuses : on peut neanmoins profiter
du fait que p est un polynome creux : p(x) = 1 +∑nb−2
i=1 xpi + xd, ou generalement nb 6 5.On peut alors simplifier le calcul de Q3 :
Q3(x) = (p(x) ·Q1(x))÷ xd
=(Q1(x) +
∑nb−2i=1 xpi ·Q1(x) + xd ·Q1(x)
)÷ xd
=(∑nb−2
i=1 xpi ·Q1(x) + xd ·Q1(x))÷ xd
=(∑nb−2
i=1 xpi ·Q1(x))÷ xd +Q1(x)
De maniere analogue, xd ·Q3(x) mod xd = 0, donc
R2(x) = (p(x)Q3(x)) mod xd
=(Q3(x) +
∑nb−2i=1 xpi ·Q3(x) + xd ·Q3(x)
)mod xd
=(Q3(x) +
∑nb−2i=1 xpi ·Q3(x)
)mod xd
Ce qui permet d’eviter quelques calculs inutiles !
Reduction_Barrett(a,e):
| assert(p[nb-2]<d/2); //r(x) est de degre =< d/2
| nw2 = (2d-1 + (w-1))/w; //nombre de mots machine sur lesquels tient a
| for(i=0...nw2-1)
| | Q1[i] = 0;
| | Q2[i] = 0;
| | dM[i] = 0;
| endfor
| dM := p(x) sous sa forme dense;
| Q1 := Div_Par_Xd(a,d); //Div_Par_Xd renvoie le quotient de a(x) par x^d
| Q2 := Q1;
| for(i=1...nb-2)
| | Add_Shift(Q1,Q2,p[i]); //Add_Shift(A, B, p) effectue A := A + B*(x^p)
| endfor
| Q3 := Div_Par_Xd(Q2,d);
| Q3 := Q3 + Q1;
| R1 := a;
| R2 := Q3;
| for(i=1...nb-2)
| | Add_Shift(R2, Q3, p[i]);
25
| endfor
| r = d%w;
| if(r!=0)
| | R1[nw-1] &= mask(r); //mask(r) est le masque dont les bits 0..r-1 sont a 1,
| | R2[nw-1] &= mask(r); //et les bits r..w-1 sont a 0
| endif
| e := R1 + R2; //on effectue donc nw additions de mots machine
end
Complexite :– nw(8nb− 9) operations logiques– nw(8nb− 9) operations arithmetiques– 6nw(nb+ 2) acces memoire– 2nb branchements
Une analyse dynamique de l’execution du programme correspondant nous apprend que l’operationAdd_Shift(.,.,.) prend plus de 60% du temps d’execution total et constitue le goulet d’etran-glement de ce code (les ameliorations sur les calculs de Q3 et R2 visaient d’ailleurs a reduire sonutilisation).
1.5 Comparatif et conclusion
Les nouveaux algorithmes developpes pendant ce stage, Reduction_Generique, Reduction_Forte,Reduction_Table et Reduction_Precalculee, se sont averes beaucoup rapide que les methodeslogicielles connus jusque la, Reduction_Barrett et Reduction_Bit, comme le prouve ce graphique.
Figure 1.7 – Comparatif des reductions avec la reduction bit-a-bit et le produit polynomial
Si vous ne voyez pas les traces de Reduction_Generique, Reduction_Forte, Reduction_Tableet Square sur le graphique 1.7, c’est normal puisqu’il s’agit des traces situes tout en bas du gra-phique, encore en-dessous du trace de Reduction_Barrett.Une analyse plus fine nous permet de hierarchiser Reduction_Generique, Reduction_Forte etReduction_Table entre elles du point de vue de la vitesse, alors que Reduction_Precalculee (qui
26
ne figure pas sur le graphique, voir les graphiques 1.5 et 1.6) reste de loin la reduction la plusrapide.
Figure 1.8 – Comparatif des reductions entre elles
Pour resumer, en terme de rapidite :
Bit < Barrett < Generique < Table < Forte < Precalculee
Le tableau suivant indique plus precisement le poids des differentes operations (logiques, arith-metiques, acces memoire et branchements) dans la complexite de chacunes de ces methodes dereduction :
Methode de Reduction Op. Logiques Op. Arithmetiques Acces memoire BranchementsBit-a-bit 1
2 (nb− 1)(d− 1) 12 (nb+ 1/2)(d− 1) 1
2nb(d− 1) d− 1Barrett nw(8nb− 9) nw(8nb− 9) 6nw(nb+ 2) 2nb
Generique 4nw(nb− 1) + 11 4 + 2nw(nb+ 2) 3nw + 2 3nw + 4Table 4nw(nb− 1) 0 2nw(2nb+ 1) 0Forte 4nw(nb− 1) + 11 4 + 2nw(nb+ 2) 2nw + 2 2nw + 4
Precalculee 4nw(nb− 1) 0 nw · nbm 0
Neanmoins, certaines de ces reductions ne peuvent etre appliquees que sous certaines conditions :
1. Reduction_Precalculee_d,p necessite d’etre precalculee et donc de connaıtre (p, d) a l’avance.En pratique, cela implique de l’integrer au code source pour chaque (d, p) dont on voudraconnaıtre la reduction precalculee.
2. Reduction_Forte peut etre utilisee si et seulement si d◦r < w
3. Reduction_Barrett peut etre utilisee si et seulement si d◦r 6 bd/2c4. Reduction_Table, Reduction_Generique, Reduction_Bit peuvent etre utilisees sans la
moindre condition sur (p, d)
27
La figure 1.9 resume les forces et faiblesses des differentes fonctions de reduction :
Precalculee Forte Barrett Bit, Generique, Table
Moins general Plus general
Bit Barrett Generique Table Forte Precalculee
Moins rapide Plus rapide
Figure 1.9 – Forces et faiblesses des fonctions de reduction
Nous disposons a present de toutes les donnees necessaires pour choisir la fonction de reductionen fonction de p, ou on le rappelle p(x) = xd + r(x) :
1. Si on dispose en memoire d’une fonction de reduction precalculee pour (d, p), alors on utilisela Reduction_Precalculee_d,p adaptee
2. Sinon, si d◦r < w, on utilise la Reduction_Forte
3. Sinon, on utilise la plus rapide entre la Reduction_Generique et la Reduction_Table (surla machine de tests, il s’agit de Reduction_Table, mais cela peut varier en fonction de lamachine)
Une fonction a ete implementee dans la librairie afin d’effectuer ces tests lors de l’initialisation ducorps et de stocker dans ses parametres un pointeur de fonction pointant vers la meilleure fonctionde reduction.
Les fonctions de reduction developpees dans ce chapitre nous seront tres utiles par la suite puis-qu’elles constituent une brique de base de la multiplication modulaire, qui sera l’objet du chapitresuivant.
28
Chapitre 2
Multiplication
La premiere partie du stage, la recherche de methodes efficaces de reduction polynomiale, apour principale application la multiplication modulaire.
En effet, il existe plusieurs methodes pour effectuer un produit dans GF (2d) :
1. Une multiplication de polynomes suivie d’une reduction modulo p
2. Une methode avec precalculs permettant, pour a fixe, de booster le produit d’un element bpar a (Mastrovito)
3. Passer sous une autre representation (Montgomery)
4. D’autres methodes comme la FFT ou l’algorithme de Toom-Cook sont employees pour desvaleurs plus elevees de d, mais ne seront pas etudiees ici
2.1 Multiplication suivie d’une reduction
Il s’agit de la methode implementee a mon arrivee.La methode utilisee dans la librairie pour multiplier modulo p deux elements a(x), b(x) ∈ GF (2d)est la suivante :
– on calcule le produit c0(x) := a(x) · b(x). c0 est au plus de degre 2(d− 1).– on effectue la reduction c(x) := c0(x) mod p(x). c est au plus de degre d− 1.
L’etude des differentes methodes de reduction constituant la premiere partie de mon stage.
La bibliotheque disposait deja d’un algorithme efficace pour le produit de deux polynomesa(x), b(x) ∈ F2[x], construit sur un modele proche de celui presente dans [?] pour les valeurs faibleset moyennes de d :
– Pour multiplier deux polynomes de degre d < w, on utilise la multiplication naıve, qu’onsimule avec des decalages et des XOR de mots machine.Depuis peu de temps, il existe cependant sur certains processeurs grand public, une instruc-tion dediee pour le produit dans F2[x], PCLMULQDQ (voir [?]), que je n’ai pas pu testercar le laboratoire ne disposait pas de tels processeurs.
– Pour multiplier deux polynomes de degre d > w, on utilise les formules de Karatsuba.Par exemple, pour des polynomes tenant sur nw = 2 mots machine,
(a · xw + b)(c · xw + d) = ac · x2w + (a · c+ b · d− (a− b) · (c− d)) · xw + b · d
D’autres formules existent pour des valeurs plus elevees de nw (voir par exemple [?])– le carre polynomial est particulier car dans F2[x] il s’agit du Frobenius :
(a(x) + b(x))2 = a2(x) + b2(x)
Par consequent, si a(x) =d−1∑i=0
aixi, alors a2(x) =
d−1∑i=0
aix2i
29
Les figures suivantes illustrent le temps d’execution de la multiplication modulaire et du carremodulaire, et l’influence qu’a la methode de reduction utilisee dans chacun des cas.Comme prevu, le produit est sous-quadratique (figure 2.1) grace a l’utilisation des formules deKaratsuba generalisees, et le carre est lineaire (figure 2.2).
Figure 2.1 – Temps d’execution de la multiplication pour differentes reductions et d = 1...2048
Figure 2.2 – Temps d’execution du carre pour differentes reductions ,d = 1...2048
30
2.2 Multiplication avec precalculs (Mastrovito)
Supposons que l’on veuille, pour a ∈ GF (2d) fixe, pouvoir calculer rapidement le produit a · bmod p, et ce pour n’importe quel b ∈ GF (2d).Ce cas de figure apparaıt par exemple dans le cas de l’exponentiation binaire ”square-and-multiply”.Le resultat ae est alors calcule par le biais d’un produit intermediaire ak qui est frequemment mul-tiplie par a.
La methode de Mastrovito propose une solution a ce probleme, en procedant en deux parties :– une phase de precalculs nous fournira les valeurs des produits zi = a · yi pour un ensemble
y = {y0, y1, ..., yk−1} judicieusement choisi de yi ∈ GF (2d)– Lorsqu’on voudra multiplier un element b ∈ GF (2d) par a, on l’ecrira comme une combinaison
booleenne des yi : b = λ0 · y0 + ...+ λk−1 · yk−1. Par linearite du produit par a, on aura alorsa · b = λ0 · z0 + ...+ λk−1 · zk−1
2.2.1 Etat de l’art
Par la suite, on prendra y = {1, x, x2, ..., xd−1}.
Algorithm 3 Precalculs pour Mastrovito
Input: a ∈ GF (2d)Output: (1, a, a2, ..., ad−1)1: z0 := 12: z1 := a3: for i = 2 to d− 1 do4: zi := a · zi−1
5: end for6: return z = (z0, z1, ..., zd−1)
La complexite de cette phase de precalculs est simple : (d− 1) ·M(d).
Algorithm 4 Produit de Mastrovito
Input: a, b ∈ GF (2d), z = (1, a, a2, ..., ad−1 ∈ (GF (2d))d)Output: a · b mod p1: c := 02: for i = 0 to d− 1 do3: if (bi = 1) then4: c := c+ zi5: end if6: end for7: return c
La complexite moyenne de cette phase est : d lectures d’elements de GF (2d) et d additions dansGF (2d) (autrement dit, d · d dw e lectures de mots machine et autant de XOR).
31
2.2.2 Implementation
Mastrovito_Init(a):
| z[0] := a;
| for(i=1..d-1)
| | z[i] := X*z[i-1];
| endfor
| return (z[0],...,z[d-1]);
end
Mul_Mastrovito(a, z[d], b):
| rep := 0;
| for(i=0...d-1)
| | if(b_i = 0)
| | | rep := rep + z[i];
| | endif
| endfor
| return rep;
end
Malheureusement, cette approche ne produit pas en pratique de resultats concluants et s’avere,sauf pour de tres faibles valeurs de d(< 12), plus lente que la methode classique de ”Multiplicationpuis reduction”.
Figure 2.3 – Temps d’execution du produit de Mastrovito d = 1...256
2.3 Changement de representation (Montgomery)
Le produit de Montgomery, a l’origine, a ete developpe pour effectuer rapidement la multiplica-tion modulaire dans des anneaux Z/nZ. Il a ete etendu aux corps binaires et c’est a cette versionque nous allons nous interesser.Le principe est le suivant : plutot que de travailler avec des elements a, b ∈ GF (2d), on travailleavec a · r, b · r, ou r est judicieusement choisi de sorte que la reduction s’effectue tres rapidement.
32
2.3.1 Etat de l’art
Definition.Pour a, b, r ∈ GF (2d), on definit les elements suivants :
– Le residu de Montgomery de a relativement a r est a = a · r mod p(x)– La reduction de Montgomery de a relativement a r est RedMr(a) = a · r−1.– Le produit de Montgomery de a et b relativement a r est a · b · r−1 = RedMr(a · b) = a · b– Le carre de Montgomery de a relativement a r est a · a · r−1 = RedMr(a · a) = a · a
Chacune de ces operations est realisee ainsi :– Le residu de Montgomery est un simple produit dans GF (2d). On pourrait egalement le
realiser en effectuant un decalage a gauche de bits suivi d’une reduction polynomiale.Plus trivialement, nous verrons que dans les cas ou nous l’utilisons, il n’est pas necessaired’optimiser cette operation.
– La reduction de Montgomery constitue l’element central de cette section. Elle peut etreeffectuee de plusieurs manieres. Nous en verrons deux qui se distinguent par leur rapidite.
– Le produit de Montgomery est un produit de polynomes dans F2[X] suivi d’une reduc-tion de Montgomery.
– Le carre de Montgomery est un carre de polynomes dans F2[X] suivi d’une reductionde Montgomery.
Algorithm 5 Multiplication basee sur le produit de Montgomery
Input: a, b ∈ GF (2d)Output: a · b mod p1: a := a · r mod p(x) //residu de Montgomery2: b := b · r mod p(x) //residu de Montgomery3: c := RedMr(a · b) //produit de Montgomery4: c := RedMr(c) //reduction de Montgomery5: return c
Algorithm 6 Elevation au carre basee sur le carre de Montgomery
Input: a ∈ GF (2d)Output: a2 mod p1: a := a · r mod p(x) //residu de Montgomery2: c := RedMr(a · a) //carre de Montgomery3: c := RedMr(c) //reduction de Montgomery4: return c
Bien evidemment, en l’etat ces algorithmes sont peu efficaces. Bien qu’ils montrent qu’on peut uti-liser les operations definies par Montgomery pour effectuer des produits et des carres classiques (lasomme se resume quant a elle a XOR-er les bits), les transformations operees au debut (residu(s))et a la fin (reduction de Montgomery) sont a elles seules trop couteuses pour pouvoir rivaliser avecle produit et le carre classiques.L’utilisation des operations de Montgomery n’est alors utile que lorsque’un grand nombre de carreset de produits est effectue, comme dans le cas d’une exponentiation ou d’un polynome multivariede degre eleve.Nous verrons dans le chapitre suivant que la capacite d’une exponentiation basee sur les opera-tions de Montgomery a rivaliser avec une exponentiation classique repose sur les ratios (vitesse duproduit de Montgomery/vitesse du produit classique) et (vitesse du carre de Montgomery/vitessedu carre classique).Pour l’instant, contentons nous d’essayer d’optimiser les produit et carre de Montgomery.
33
Version de Knezevic et al. [?]
Dans leur article, Knezevic et al. presentent une reduction de Montgomery potentiellement tresrapide, mais qui repose sur une condition contraignante : p(x) = xd + q(x) + 1 avec d◦(q) < d etval(q) > dd2e
Algorithm 7 Reduction de Montgomery dans GF (2d) sans precalculs
Input: a(x) ∈ F2[x] de degre < 2dp(x) = xd + q(x) + 1 tel que d◦(q) < d et val(q) > dd2er(x) = xd
Output: a(x)r−1(x) mod p1: S1(x)← a(x) mod r(x)2: S2(x)← p(x)S1(x) mod r(x)3: S3(x)← p(x)S2(x)4: T (x)← (a(x) + S3(x))÷ r(x)5: return T (x)
Version de Koc et Acar [?]
Koc et Acar observent qu’en choisissant r = xwdd/we mod p, la reduction de Montgomery peuts’effectuer tres rapidement puisqu’il s’agit d’effectuer des shifts de w bits et donc des decalages demots machine.Pour rappel, on note a(x) =
∑i>0Aix
iw, c(x) =∑
i>0 Cixiw et p(x) =
∑i>0 Pix
iw, chacun desAi, Ci et Pi tenant ainsi sur exactement un mot machine.De plus, on note P ′0 = P−1
0 mod xw (on rappelle que P0 = p mod xw).
Algorithm 8 Multiplication de Montgomery-Koc-Acar
Input: a, b ∈ GF (2d)Output: a · b · r−1 mod p1: c(x) := 02: for i = 0 to nw − 1 do3: c(x) := c(x) +Ai(x)b(x)4: M(x) := C0(x)P ′0(x) mod xw
5: c(x) := c(x) +M(x)p(x)6: c(x) := c(x)/xw
7: end for8: return c
On observe qu’ici la multiplication et la reduction de Montgomery sont effectuees simultane-ment, ce qui pose un probleme de taille : nous ne pouvons pas utiliser Karatsuba et devons nouscontenter de la multiplication par blocs naıve, qui est de complexite quadratique.
P−10 se calcule ainsi :
Algorithm 9 Inversion mod xw
Input: P0 ∈ F2[X] de degre < wOutput: P−1
0 mod xw
1: P ′0(x) := 12: for i = 2 to w do3: t(x) := P0(x)P ′0(x) mod xw
4: if t(x) 6= 1 then5: P ′0(x) := P ′0(x) + xi−1
6: end if7: end for8: return P ′0
34
Il est bien sur recommande de le calculer lors de l’initialisation du corps puis de le sauvegarderdans les parametres du corps.
2.3.2 Contributions personnelles
J’ai decide d’implementer les deux algorithmes de reduction, celui de Knezevic et celui de Kocet Acar.
Version de Knezevic et al. ([?])
La reduction presente de tres grandes similitudes avec la reduction de Barrett presentee plushaut (ce qui est normal puisqu’elles sont presentees dans le meme article). Par consequent, toutesles astuces d’implementation citees pour la reduction de Barrett sont valables pour la reduction deMontgomery-Knezevic.
Reduction_Montgomery_Knezevic(a, c)
| rem = d%w;
| nwp = ceil((d+1)/w);
| nw2 = ceil((2d-1)/w);
| assert(p[1]>=ceil((d+1)/2);
//Etape 1 : S1 <-- a(x) mod r(x)
| for(i=0...nw-1)
| | S1[i] := a[i];
| endfor
| S1[nw-1] &= mask;
//Etape 2 : S2 <-- p(x)S1(x) mod r(x)
| S2 := S1;
| for(i=1...nb-2)
| | Add_Shift(S2, S1, p[i]); //S2 := S2 + S1*(x^p[i]);
| endfor
| for(i=nw2-1...nw)
| | S2[i] := 0;
| endfor
| S2[nw-1] &= mask;
//Etape 3 : S3 <-- (p(x) - x^d - 1)*S2(x)
| for(i=nwp-1...nw2-1)
| | S3[i] = 0UL;
| endfor
| for(i=1...nb-2)
| | Add_Shift(S3, S2, p[i]); //S3 := S3 + S2*(x^p[i]);
| endfor
//Etape 4 : c <-- (a(x) + S3(x)) div r(x) + S2(x) = T0(x) div r(x) + S2(x)
| for(i=nwp-1...nw2-1)
| | T0[i] := a[i]^S3[i];
| endfor
| c := T0/(x^d);
| c := c + S2;
| c[nw-1] &= mask;
end
En admettant que nwp = nw (ce qui arrive w− 1 fois sur w), la complexite de cette reduction estla suivante :
– 3nw2− 2nw + 2 affectations– 2(nb− 2)(nw + nw2) + nw2 + 1 + nw XOR– 2(nb− 2)(nw + nw2) + 2nw SHIFT.
35
Puis on remarque qu’une fois sur deux, nw2 = 2nw, et une fois sur deux, nw2 = 2nw− 1, donc enmoyenne nw2 = 2nw − 1
2 , ce qui donne la complexite moyenne suivante :– 4nw + 1
2 affectations– 2(nb− 2)(3nw − 1
2 ) + 3nw + 12 ' (2nb− 3)(3nw − 1
2 ) XOR– nw(6nb− 10)− nb + 2 SHIFT.
Version de Koc et Acar ([?])
Dans l’article, l’algorithme realisant le produit de Montgomery a ete pense pour tenir compte dela structure en mots machine, ce qui lui confere des proprietes interessantes en termes de rapidite,certaines de maniere volontaire, d’autres non.En contrepartie, il realise simultanement le produit polynomial et la reduction de Montgomery,ce qui est tres mauvais car le produit polynomial utilise est la multiplication naıve, de complexitepolynomiale.
Mais il est tout a fait possible de separer les deux, comme dans l’algorithme ci-dessous :
Algorithm 10 Multiplication de Montgomery-Koc-Acar - Amelioration 1
Input: a, b ∈ GF (2d)Output: a · b · r−1 mod p1: c(x) := a(x) · b(x)2: for i = 0 to nw − 1 do3: M(x) := C0(x)P ′0(x) mod xw
4: c(x) := c(x) +M(x)p(x)5: c(x) := c(x)/xw
6: end for7: return c
Cette modification a pour consequence immediate de nous permettre d’utiliser une version sous-quadratique de la multiplication polynomiale, comme celle implementee dans la librairie.Mais nous pouvons encore ameliorer cet algorithme afin de nous passer de l’etape 5, couteuse enaffectations de mots machine.
Algorithm 11 Multiplication de Montgomery-Koc-Acar - Amelioration 2
Input: a, b ∈ GF (2d)Output: a · b · r−1 mod p1: c(x) := a(x) · b(x)2: for i = 0 to nw − 1 do3: M(x) := Ci(x)P ′0(x) mod xw
4: c(x) := c(x) +M(x)p(x)xw·i
5: end for6: return c/
(xw·dd/we
)On revient donc ici a une forme classique du produit de Montgomery, qui consiste a realiser un
produit de polynomes suivi d’une reduction de Montgomery.
36
Algorithm 12 Reduction de Montgomery-Koc-Acar dans GF (2d)
Input: a(x) ∈ F2[x] de degre < 2dp(x) = xd + q(x) + 1 tel que d◦(q) < d et val(q) > 1P ′0(x) = p−1(x) mod xw
r(x) = xw·dd/we
Output: a(x)r−1(x) mod p1: c(x) := a(x)2: for i = 0 to nw − 1 do3: M(x) := Ci(x)P ′0(x) mod xw
4: c(x) := c(x) +M(x)p(x)xi
5: end for6: return c(x)
Ci-dessous, une implementation de l’algorithme (on peut choisir de precalculer ou non les valeursp[j]/w et p[j]%w) :
Reduction_Montgomery(a,c):
| for(i=0...nw-1)
| | Mx = a[i];
| | for(j=1...|p0’|-1)
| | | Mx ^= (a[i]<<p0’[j]);
| | endfor
| | a[i] ^= Mx;
| | for(j=1...nb-1)
| | | a[(p[j]/w)+i] ^= Mx<<(p[j]%w);
| | | if((p[j]%w)!=0)
| | | | a[(p[j]/w)+i+1] ^= Mx>>(w-p[j]%w);
| | | endif
| | endfor
| endfor
| for(i=0...nw-1)
| | c[i] = h[i+nw];
| endfor
end
La seule chose qui differencie un produit de Montgomery et un produit normal dans GF (2d) est lareduction employee (et de meme pour le carre). Analysons donc la complexite de la reduction deMontgomery :La reduction de Montgomery effectue :
– nw(2nb + |P′0|+ 1) affectations– nw(2nb + |P′0| − 1) SHIFT– nw(2nb + |P′0|) XOR.
Comment diminuer la complexite de la reduction de Montgomery ? Il existe un solution simple,c’est de minimiser |P−1
0 |. C’est cependant une tache peu aisee car il est difficile, connaissant P0, dequantifier |P−1
0 |, y compris quand P0 est un polynome creux. Essayons de resoudre ce probleme :
1. Si |P−10 | = 1, alors P0 = 1 et P−1
0 = 1
2. Si |P−10 | = 2, alors P0 = 1 + xk et P−1
0 = 1 + xk + x2k...+ xmk, avec m = dwk e − 1.
En effet, on a alors P0 · P−10 = 1 + x(m+1)k = 1 + xd
wk ek = 1(mod xw).
Conclusion : dans ce cas, on a |P−10 | = dwk e
3. Si |P−10 | > 1, il devient tres difficile de quantifier |P−1
0 |.Gardons toutefois a l’esprit que le but n’est pas de calculer |P−1
0 | dans tous les cas, mais justede trouver des P0 tels que |P−1
0 | soit petit. Par exemple, si P0 = 1 + xk ·Q(x), ou k > w/2,alors P 2
0 = 1 + x2k ·Q2(x) et donc P−10 = P0.
On peut meme generaliser cette propriete : si P0 = 1 + xk · Q(x), ou k > w/2j , alors
P 2j
0 = 1 + x2jk ·Q2j
(x) et donc P−10 = P 2j−1
0 .
37
2.3.3 Comparaisons
Les tests sont effectues pour des polynomes d’extension de la forme suivante : p(x) = xd +q(q) + 1, ou d◦(q) < d et val(q) > dd2e, ce qui est une condition necessaire et suffisante pourque la reduction de Montgomery-Knezevic fonctionne, et optimise la rapidite de la reduction deMontgomery-Koc-Acar.
Figure 2.4 – Reductions de Montgomery comparees a celles deja existantes
Les tests sont plutot concluants puisque les deux reductions sont a peu pres aussi rapides quecelles existantes pour la reduction modulaire. On remarque par ailleurs que Reduction_Koc_Acar
et Reduction_Knezevic, bien qu’effectuant la reduction de Montgomery de deux manieres tresdifferentes, ont sensiblement le meme temps d’execution.Cependant, Reduction_Koc_Acar peut etre lancee sans condition sur p, alors Reduction_Knezevicdemande des conditions assez restrictives.Je recommande donc fortement d’utiliser Reduction_Koc_Acar pour effectuer la reduction deMontgomery.
Meme si ici les reductions de Montgomery ne sont pas meilleures que les reduction habituelles,Il existe un cas dans lequel Reduction_Koc_Acar est nettement superieure aux reductions habi-tuelles, il s’agit du cas ou p est un polynome dense.Pour le prouver, j’ai effectue des carres modulaires avec Reduction_Generique, Reduction_Tableet Reduction_Koc_Acar, dans le cas ou p est un polynome dense tel que |p| = bd/3c, sans la moindrecondition supplementaire sur p. Je n’ai teste ni Reduction_Knezevic, ni Reduction_Forte car ellesne pouvaient pas s’appliquer.Les resultats sont sans appel en faveur de Reduction_Koc_Acar, qui si elle prend enormement detemps par rapport au carre polynomial, est toutefois considerablement plus rapide que les autresreductions.
38
Figure 2.5 – Reductions generique, table et de Montgomery pour |p| = bd/3c
Figure 2.6 – Reductions generique, table et de Montgomery pour |p| = bd/3c
En pratique on evite de choisir p dense, precisement a cause du temps tres eleve que prendraitune reduction. Mais meme sans se placer dans le cas ou p est dense, on voit que |p| impacte for-tement les reductions habituelles et a une influence moindre sur Reduction_Koc_Acar, qui peutalors etre plus avantageuse que les autres reductions.Cependant, meme dans les cas ou Reduction_Koc_Acar est plus rapide que les autres reductions,5 et 6 ne sauraient rivaliser avec les multiplication et carre modulaires classiques, car dans les deux
39
algorithmes realisent les meme operations que leurs equivalents classiques, avec en plus une ouplusieurs reductions de Montgomery.
La reduction de Montgomery n’est donc pas adaptee aux cas ou on ne souhaite effectuer qu’unproduit ou un carre, mais prend son sens uniquement lorsque beaucoup de produits et carres deMontgomery sont effectues, comme dans le cas de l’exponentiation de Montgomery, laquelle serala premiere partie du chapitre suivant, consacre a l’exponentiation modulaire, qui s’appuiera ega-lement sur les resultats que nous avons obtenus dans ce chapitre sur la multiplication et le carremodulaires.
40
Chapitre 3
Exponentiation
L’exponentiation est tres frequemment utilisee en cryptographie, et il s’agit egalement d’unedes operations les plus couteuses.La methode usuelle pour l’effectuer est l’algorithme ”square and multiply”.Dans les faits, sa complexite fait rapidement exploser le temps d’execution d’une exponentiation.On se tourne donc vers d’autres methodes plus rapides, comme l’exponentiation de Montgomeryet les methodes m-aires d’exponentiation.
3.1 Exponentiation de Montgomery
3.1.1 Etat de l’art
Le principe de l’exponentiation de Montgomery est d’effectuer un ”changement de representa-tion” : au lieu de travailler avec des elements a, b ∈ GF (2d), on travaille avec leurs residus a = a · rmod p et b = b ·r mod p, ou r ∈ GF (2d) est choisi judicieusement d’une maniere qu’on expliciteraplus tard.Le changement de base prendra alors environ un temps non-negligeable, mais ce temps perdu seralargement compense par la rapidite des calculs dans la nouvelle representation.
Algorithm 13 Montgomery Exponentiation
Input: a, e, r ∈ GF (2d)Output: ae mod p1: c := r2: a := a · r Un decalage de bits + une reduction modulaire3: for i = m− 1 downto 0 do4: c := c · c · r−1
5: if (ei = 1 then6: c := c · a · r−1
7: end if8: end for9: c := c · r−1
10: return c
3.1.2 Implementation et contributions
J’ai choisi d’effectuer un maximum de precalculs :– On pose des le depart r = xdd/wew mod p et on stocke r dans les parametres du corps, cela
afin de ne pas avoir a le recalculer au debut de chaque exponentiation.– On calcule egalement P ′0 = p−1 mod xw des l’initialisation du corps.– En plus de stocker P ′0 dans un mot machine, on stocke la liste de ses cœfficients non-nuls
dans les parametres du corps. Cela permet d’accelerer l’etape 4 du produit de Montgomeryet l’etape 3 du carre de Montgomery.
41
Etude de complexite
Exp_Montgomery(a, exp,r)
| const Pos *p = gf->pExt.pos;
| quo[nb], rem[nb];
| for(j=0...nb-1)
| | quo[j] = p[j]/w;
| | rem[j] = p[j]%w;
| endfor
| GF2E_SetOne(one);
| GF2E_Copy(r,cb);
| ab = GF2E_Mul(a, r);
| for(i=w*nw-1...0)
| | cb := Square_Montgomery(cb, quo[nb], rem[nb], n1);
| | if(exp[i]==1)
| | | cb = Mul_Montgomery(ab, cb, quo[nb], rem[nb], n1);
| | endif
| endfor
| c := Mul_Montgomery(cb, one, quo[nb], rem[nb], n1);
| return(c);
end
Comme son alter ego conventionnel, l’exponentiation de Montgomery coute d − 1 elevations aucarre de Montgomery et en moyenne (d− 1)/2 multiplications de Montgomery dans GF (2d), maisegalement une reduction modulaire et une reduction de Montgomery, d’ou la complexite tempo-relle suivante : EM (d) = d(SM (d) + 1
2MM (d)) + RM (d) + R(d) (ou R(d) est la complexite d’unereduction modulaire).Sachant qu’une multiplication de Montgomery ”coute”une multiplication polynomiale et une reduc-tion de Montgomery, et qu’une elevation de Montgomery ”coute”une elevation au carre polynomialeet une reduction de Montgomery, il est necessaire (et en pratique suffisant) que la reduction deMontgomery soit plus rapide que la reduction ”classique” (il peut s’agir de la reduction Generique,Table, Forte ou Precalculee) pour que l’exponentiation de Montgomery prenne l’ascendant surl’exponentiation normale.
3.2 Methodes 2k-aires d’exponentiation
Le principe des methodes 2k-aires est simple : il s’agit de faire du square-and-multiply, saufqu’au lieu de lire un bit a fois, on en lit k.
Algorithm 14 Exponentiation 2k-aire
Input: f, e ∈ GF (2d), k ∈ N∗Output: fe mod p1: Precalculer tous les f j , pour j = 1...2k − 12: h := 13: for i = dd−1
k e to 0 do
4: h := h2k
5: exp = ek·i...k·i+k−1
6: if (exp 6= 0) then7: h := h · fexp8: end if9: end for
10: return h
Les etudes de complexites realisees dans [?] considerent que le produit et le carre ont la memecomplexite. Ce postulat, deja surprenant et en general faux dans les corps non binaires, doit etre
42
completement abandonne dans les corps GF (2d) puisque le carre s’y calcule en un temps lineaireet le produit en un temps sur-lineaire.C’es pourquoi je substituerai aux resultats d’Henriquez mes propres resultats et conclusions, queje presenterai dans la partie suivante.
3.2.1 Etat de l’art
Supposons qu’on souhaite calculer ae dans GF (2d). L’exponentiation m-aire consiste en plu-sieurs etapes :
– On calcule les valeurs de ai pour i = 0...m− 1 ; il s’agit d’une phase de precalculs– On ecrit e en base m : e =
∑i=0...l eim
i
– Le cœur de l’algorithme consiste en une methode square-and-multiply descendante ou au lieude lire e bit a bit, on lit les ei et si ei 6= 0, on multiplie la ”valeur temporaire” de ae par mei .
Naturellement, cet algorithme est particulierement adapte au cas ou m = 2k est une puissance de2, puisqu’il suffit alors de lire les bits k · i...k · (i+ 1)− 1 pour connaıtre ei.
Cette explication n’est pas forcement tres limpide, mais l’algorithme l’est beaucoup plus :
Algorithm 15 Exponentiation 2k-aire
Input: f, e ∈ GF (2d), k ∈ N∗Output: fe mod p1: Precalculer tous les f j , pour j = 1...2k − 12: h := 13: for i = dd−1
k e − 1 to 0 do
4: h := h2k
5: exp = ek·i...k·i+k−1
6: if (exp 6= 0) then7: h := h · fexp8: end if9: end for
10: return h
Si on met de cote les precalculs, cet algorithme permet d’effectuer k fois moins de produits qu’un
square-and-multiply normal, tout en effectuant autant de carres (x2k
se calcule en k elevations aucarre).
3.2.2 Mes contributions
Interessons-nous a la complexite de cet algorithme :– L’etape 1, le precalcul des f j , coute 2k−1 − 1 carres et 2k−1 − 1 produits : un carre pour
calculer f2, ..., f2k−2 et un produit pour calculer f3 = f ·f2, f5 = f3 ·f2,...,f2k−1 = f2k−3 ·f2
– L’etape 4 est realisee dd−1k e fois, ce qui coute donc k · dd−1
k e carres. En optimisant la premiereiteration de cette etape, on peut se ramener a un cout de d− 1 carres.
– L’etape 5 a un cout quasiment nul : on ne fait que lire des bits.
– L’etape 6 est realisee en moyenne 2k−12k dd−1
k e fois (en effet on ne la realise que pour 2k − 1
des 2k valeurs possibles d’exp), cela coute donc 2k−12k dd−1
k e produits.
En moyenne, on a donc EXB(k, d) = (2k−1 + d− 2)S(d) + (2k−1 − 1 + 2k−12k dd−1
k e)M(d).On souhaite se servir de cette expression d’EXB(k, d) pour determiner, pour un degre d donne,quelle est la valeur de k minimisant EXB(·, d), c’est-a-dire telle que l’exponentiation 2k-aire soitla plus rapide.
43
Deux methodes peuvent permettre de determiner k :
– Calculer EXB(k, d) pour une plage de valeurs de k et choisir le k optimal– Raisonner mathematiquement sur EXB(k, d)
Comparatif des differentes exponentiations 2k-aires pour k = 0..7 et d = 10..2048
Figure 3.1 – Comparatif des exponentiations 2k-aires pour d = 10...512
Figure 3.2 – Comparatif des exponentiations 2k-aires pour d = 10...1024
44
Figure 3.3 – Comparatif des exponentiations 2k-aires pour d = 10...2048
Bien que la seconde methode soit moins facile que la premiere, elle est assurement plus interes-sante. Derivons EXB(k, d) par rapport a k, en admettant que dd−1
k e 'd−1k :
∂EXB
∂k(k, d) = log(2) · 2k−1S(d) +
[log(2) · 2k−1 +
log(2) · 2k · k − 1 + 2−k
k2(d− 1)M(d)
]EXB(., d) est decroissante, puis croissante.La valeur kd telle que ∂EXB
∂k (kd, d) soit nul sera donc la valeur qui minimise EXB(., d).
On trouve
d− 1 =log(2) · 2kd−1 · k2
d
1− 2−kd(1 + kd · log(2))
(1 +
S
M
)= F (kd, d)
Je n’ai pas reussi a inverser cette fonction, mais ai contourne ce probleme : en effet les valeurs dek auxquelles on s’interesse sont entieres. De plus en pratique k ∈ J1; 9K.
Il suffit donc de calculer log(2)·2k−1·k2
1−2−k(1+k·log(2))
(1 + S
M
)pour k ∈ J1; 9K et de considerer que kd est
la valeur minimisant F (., d). Bien que ca ne soit pas rigoureusement prouve, en pratique celadonne de bons resultats.
Une grande inconnue reste cependant la valeur de SM (d). Cette valeur depend de d, mais aussi
de l’architecture de l’ordinateur, de la methode de multiplication et d’elevation au carre choisies,etc.Il est en particulier bon de savoir que le carre s’effectue en un temps lineaire en d et le produit enun temps sur-lineaire en d, c’est pourquoi S
M (d) tend vers 0 quand d tend vers +∞.
Aucune solution n’est parfaite pour connaıtre SM (d) :
– On peut precalculer les valeurs de SM (d) pour une variete de valeurs de d, d’architectures
materielles et logicielles et de methodes de reduction, puis stocker les resultats dans le codesource de la librairie.Mais cette methode n’est que de peu de recours face a une configuration qui ne figurerait pasdans celles testees.
– On peut lancer les benchs lors de l’execution du code pour obtenir des valeurs totalementfiables. Il faut cependant pouvoir faire des compromis entre precision du bench (qui dependdu nombre de fois qu’on l’execute pour un degre d donne), exhaustivite (la plage de valeursde d pour lesquelles on lance le bench) et rapidite.Une maniere efficace d’accelerer cette methode est de remarquer que S
M (d) est a peu pres
45
constant sur les intervalles Jw ·k;w ·(k+1)J. Il suffit donc de ne le calculer que sur un nombrerestreint de d ∈ Jw · k;w · (k + 1)J pour connaıtre sa valeur approchee sur l’intervalle toutentier. On divise le nombre de calculs par w.
– Pour des valeurs suffisamment elevees de d, on peut admettre que SM (d) ' 0.
Voici, a titre indicatif, un tableau indiquant certaines des valeurs de MS (d) pour d = 10...2048 :
Figure 3.4 – Ratio MS (d) pour d = 10...2048 et p un pentanome
On constate que plus la reduction est efficace, plus le ratio est eleve. En effet la reduction aun impact tres important sur le temps d’execution du carre modulaire, qu’elle peut faire doublervoire tripler. On constate ainsi a quel point il est important de disposer d’une methode rapide dereduction.
L’exponentiation, developpee dans cette partie, jouera un role important dans la partie suivante,consacree a l’inversion dans GF (2d), dans laquelle interviennent de nombreux algorithmes utilisantdes exponentiations.
46
Chapitre 4
Inversion
La premiere methode d’inversion, la plus simple, exploite le fait que pour tout corps fini decardinal q = pn, l’ensemble de ses elements inversibles est de cardinal q − 1. Par consequent, pour
tout element inversible x ∈ GF (2d)×, on a x2d−1 = 1 par application du Theoreme de Lagrange,
et donc x−1 = x2d−2.L’autre solution est l’algorithme d’Euclide et ses variantes. Si cette solution reste tres souvent lavoie royale pour realiser l’inversion, nous verrons qu’il est possible de tirer parti des particularitesdes corps binaires pour grandement accelerer les solutions exponentielles.
4.1 Inversion exponentielle rapide
4.1.1 Principe
Introduisons quelques nouvelles notations :– Pour n ∈ N, on note n = nk−1...n1n0, ou nk−1...n1n0 est l’ecriture en binaire de n.
Ainsi, 140 = 27 + 23 + 22 = 10001100– Par ailleurs, on note 11...11k = 2k − 1 l’entier dont l’ecriture binaire est composee de k ”1”.
– Pour k ∈ N, on note yk = a2k−1 = a11...11k et zk = a22k−1 = y2k
– On note S(a) = a2 le carre de a, qui est egalement son Frobenius. Cette notation est pluspratique pour representer des carres iteres.
– On pose ` = blog2(d− 1)c
Proposition.Connaissant a = z0, on peut calculer z0, z1, ..., z` en effectuant ` produits et 2` − 1 carres.
Demonstration.On peut calculer zk a partir de zk−1 en effectuant un produit et 2k−1 carres :
zk = a22k−1
= a(22k−22k−1)+(22k−1
−1)
= (a22k−1−1)22k−1
· a22k−1−1
= z22k−1
k−1 · zk−1
= S2k−1
(zk−1) · zk−1
47
Un exemple pour k = 3 :
z3 = a28−1
= a11111111
= a11110000+1111
= a11110000 · a1111
= S4(a1111) · a1111
= S4(z2) · z2
On calcule les zi dans cet ordre :
z0
⇓ 1 produit, 1 carrez1
⇓ 1 produit, 2 carres
z2
......
...⇓ 1 produit, 2`−1 carresz`
Calculer z0, z1, ..., z` demande ainsi ` produits et`−1∑k=0
2k = 2` − 1 carres.
Proposition.
si on connait k, k′, yk = a2k−1 et yk′ = a2k′−1, alors on peut calculer yk+k′ en k′ carres et un produit.
Demonstration.
yk+k′ = a2k+k′−1
= a(2k+k′−2k′ )+(2k′−1)
= (a2k−1)2k′ · a2k′−1
= Sk′(yk) · yk′
On deduit de ces deux propositions un algorithme pour calculer l’inverse exponentiel d’un elementde GF (2d) :
Algorithm 16 Inversion exponentielle rapide sur GF (2d)
Input: a ∈ GF (2d)Output: a−1 ∈ GF (2d)
1: Calculer ` = blog2(d− 1)c et d− 1 =∑k=0
dk2k
2: z0 := a3: for k = 1 to ` do4: zk := S2k−1
(zk−1) · zk−1 //Precalcul des zk5: end for6: c := z`7: for k = `− 1 down 0 do8: if dk = 1 then9: c := S2k
(c) · zk10: end if11: end for12: return c2 //Ne pas oublier de mettre le resultat final au carre
48
4.1.2 Analyse de complexite
La phase de precalculs coute ` produits et 2` − 1 carres.
Le calcul de a2d−1−1 coute∑`−1
k=0 dk ·2k = d−2` carres et∑`−1
k=0 dk produits (le nombre de produitsest donc egal a Hamming(d− 1)− 1, ou Hamming(d− 1) est le poids de Hamming de l’ecriturebinaire de d− 1). La derniere phase coute un carre. Au total :
– d− 1 carres– `+Hamming(d− 1)− 1 produits (donc au pire 2` produits, et au mieux `)
4.1.3 Comparaison avec la methode ”square-and-multiply”
Cette nouvelle methode est effectivement extremement plus rapide que la methode ”square-and-multiply”, les resultats et graphiques sont donnes en conclusion de ce chapitre.
4.2 Inversion exponentielle par blocs
4.2.1 Principe
Il s’agit ici de realiser une exponentiation par blocs comme celle decrite dans l’algorithme 14.La difference concernant l’inversion exponentielle par blocs est qu’il n’est necessaire de precalculerque deux puissances de a, et non plus 2k.
En effet, a−1 = a2d−2 = (a2d−1−1)2.Or si d− 1 = k · quo+ rem, alors a chaque fois qu’on effectue le produit h := h · fexp dans l’expo-nentiation 2k-aire (a l’etape 7 de l’algorithme 14), exp sera egal a 2quo−1 = 11..11quo ou au plusune fois a 2rem − 1 = 11..11rem.
Nous n’avons donc que deux puissances de a a precalculer : yk = a2k−1 et yrem = a2rem−1.
1. Avec la methode ”square-and-multiply”, ces precalculs prennent k−1 carres et k−1 produits.
2. Avec une adaptation de la methode ”inversion exponentielle rapide”, ces precalculs prennent :– k + rem− blog2(rem)c carres– blog2(k)c+Hamming(k) +Hamming(rem− 2blog2(rem)c)− 1 produitsSoit, en notant ` = blog2(k)c et en supposant que r est aleatoire dans J0; kJ :– au mieux k carres et `+Hamming(k)− 1 produits– au pire 2k − ` carres et 2`+Hamming(k)− 2 produits– en moyenne 3
2k − `+ 12 carres et 3
2`+Hamming(k)− 1
Algorithm 17 Inversion exponentielle par blocs sur GF (2d)
Input: a ∈ GF (2d), k ∈ N∗Output: a−1 ∈ GF (2d)1: Calculer d− 1 = quo · k + rem2: Calculer yk et yrem3: if rem 6= 0 then4: c := yrem5: else6: c := 17: end if8: for i = 1 to quo do9: for j = 1 to k do
10: c := c2
11: end for12: c := c · yk13: end for14: return c2
49
4.2.2 Analyse de complexite
Les calculs (etapes 3 a 13) coutent :– k · bd−1
k c+ 1 carres
– bd−1k c produits
On se pose la question suivante : pour d fixe, quelle est la valeur de k qui optimise l’inversionexponentielle 2k-aire, et quelle est alors la complexite de l’inversion exponentielle 2k-aire ?La reponse a cette question depend de la methode qu’on emploie pour les precalculs (binaire ourapide).
Precalculs avec la methode ”square-and-multiply”
La complexite de l’algorithme est :
INV EXB(d, k) = (k · bd− 1
kc+ k)S(d) + (bd− 1
kc+ k − 1)M(d)
En realisant l’approximation bd−1k c '
d−1k , on a :
INV EXB(d, k)
M(d)= (d− 1 + k)
S
M(d) +
d− 1
k+ k − 1
Nous souhaitons donc trouver k qui minimise fd(k) = INV EXB(d,k)M(d) .
Il suffit de calculer f ′d (laquelle est negative en 0+, positive en +∞ et croissante sur R∗+) pour serendre compte que fd est minimale en :
kd =
√d− 1
1 + S/M(d)
Complexite avec les precalculs naıfs : :
– d− 1 +√
d−11+S/M(d) carres
–√d− 1
(2+S/M(d)√1+S/M(d)
)− 1 produits
Soit environ 2√d produits au lieu de d, et environ le meme nombre de carres.
Precalculs avec la methode rapide
En effectuant les memes approximations que precedemment, on a :
fd(k) =INV EXB(d, k)
M(d)=d− 1
k+ 2 log2(k) + (d+
3
2k − `+
1
2)S
M(d)
Nous souhaitons a nouveau trouver k qui minimise fd(k), et pour ce faire allons a nouveau chercherles racines de f ′d(k) :
(f ′d(k) = 0)⇐⇒(
3S
2M
)k2 +
1
ln(2)
(2− S
M
)k − (d− 1) = 0
On se retrouve face a une equation du second degre du type A · k2 +B · k + C = 0, dont l’unique
solution positive est kd = −B+√
∆2A , avec ∆ = B2 − 4AC.
En admettant que SM � 1� S
M · d, on a ∆ ≈ 6 SM · d et ensuite kd ≈
√2M3S · d
Complexite avec des precalculs rapides :
– d+√
3M2S d−
12 log2( 2M
3S d) carres
–√
3S2M d+ log2( 2M
3S d) produits
50
4.2.3 Tests, comparaison avec la methode ”square-and-multiply”
Le fait de diminuer a l’extreme le nombre de puissances a precalculer s’avere payant puisqu’onpeut choisir une valeur beaucoup plus elevee pour k que si on avait simplement utilise l’algorithme14 d’exponentiation par blocs. Cela aboutit a une tres grande diminution du nombre de multipli-cations, et donc naturellement a une nette amelioration de la rapidite des calculs.Plus precisement, dans l’echelle des valeurs de d testees, on arrive a diminuer le temps de calculd’un facteur pouvant depasser 10, comme le montrent les graphiques 4.1 et 4.2.
Figure 4.1 – Inversion exponentielle par blocs de taille k pour d = 10...512
Figure 4.2 – Inversion exponentielle par blocs de taille k pour d = 10...4096
51
4.3 Inversion par l’algorithme d’Euclide etendu
4.3.1 Etat de l’art et implementation
J’ai ete charge d’implementer un algorithme d’inversion plus rapide, et me suis tout naturelle-ment tourne vers l’algorithme d’Euclide etendu presente dans [?].J’ai implemente les deux methodes du livres etant presentees comme optimales pour l’inversiondans F2d , les algorithmes 2.48 et 2.49.
Inverse_2.48(a,f):
| u := a;
| v := f;
| g1 := 1;
| g2 := 0;
| while (u!=1):
| | j = deg(u) - deg(v);
| | if (j<0):
| | | Echanger(u,v);
| | | Echanger(g1,g2);
| | | j := -j;
| | endif
| | u := u + v<<j;
| | g1 := g1 + g2<<j;
| endwhile
| Return(g1);
end
Quelques ”astuces d’implementation” qui tombent sous le sens mais dont l’oubli peut avoir delourdes consequences sur la rapidite de l’algorithme :
– Utiliser des pointeurs vers u, v, g1 et g2 permet de les echanger instantanement en echangeantleurs pointeurs au lieu d’echanger chacun des mots les composant
– Il faut tenir compte du fait que les degres de u et v diminuent lineairement au fil de l’algo-rithme, de meme que ceux de g1 et g2 augmentent lineairement. Par consequent l’algorithmecalculant le degre tient compte du degre maximal que peut avoir u et v, de meme que celuieffectuant a := a + b<<j
– Naturellement, xj · b s’obtient a partir de b par un simple decalage de bits, et non en utilisantexplicitement l’algorithme de multiplication.
Inverse_2.49(a,f):
| u := a;
| v := f;
| g1 := 1;
| g2 := 0;
| while ((u!=1) et (v!=1)):
| | while(x divise u):
| | | u := u/x;
| | | if (x divise g1):
| | | | g1 := g1/x;
| | | else:
| | | | g1 := (g1+f)/x;
| | | endif
| | endwhile
| | while(x divise v):
| | | v := v/x;
| | | if (x divise g2):
| | | | g2 := g2/x;
| | | else:
| | | | g2 := (g2+f)/x;
52
| | | endif
| | endwhile
| | if (deg(u) > deg(v)):
| | | u := u + v;
| | | g1 := g1 + g2;
| | else:
| | | v := v + u;
| | | g2 := g2 + g1;
| | endif
| endwhile
| if (u==1):
| | return(g1);
| else:
| | return(g2);
| endif
end
Ici aussi, quelques astuces permettent d’accelerer l’algorithme :– Nous ne sommes pas obliges de calculer d◦u et d◦v pour determiner si d◦u > d◦v, il suffit par
exemple de calculer d◦u et de voir si v comporte des monomes de poids > d◦u.– La divisibilite d’un element f par X s’observe simplement en lisant le bit de poids faible de
la representation de f . De meme la division de f par X se fait par decalage de bits.
4.3.2 Tests, comparaison avec les autres methodes
Les methodes d’inversion par Euclide etendu sont, comme attendu, les plus rapides. On noted’ailleurs que l’algorithme Inverse_2.48 est plus rapide que Inverse_2.49.
Figure 4.3 – Comparatif des differentes methodes d’inversion pour d = 10...512 et p un pentanome
On remarque par ailleurs que l’algorithme d’inversion exponentielle rapide est beaucoup plusrapide que toutes les methodes par blocs. Il est de 2 a 6 fois plus lent qu’Inverse_2.48 sur la plagede valeurs testees.Cela dit, dans un environnement disposant d’une instruction rapide pour la multiplication de
53
polynomes, comme cela peut etre le cas dans des cryptoprocesseurs, l’inversion exponentielle rapidepourrait etre encore plus competitive et meme surpasser l’inversion par l’algorithme d’Euclide.En effet, dans certains systemes embarques, comme par exemple dans les cartes a puce, le produitde polynomes est implemente en hardware alors que l’inverse par Euclide etendu est implementeen software.
Figure 4.4 – Comparatif des differentes methodes d’inversion pour d = 10...2048 et p un pentanome
A present que nous avons fait le tour des differentes fonctions essentielles de GF (2d), la dernierepartie sera l’occasion de s’interesser aux outils utlises et methodes mises en œuvre pour optimiserle code et garantir sa robustesse.
54
Chapitre 5
Implementation
5.1 Comparaison avec Magma, NTL et PARI/GP
La vitesse du calcul du produit dans GF (2d) par la librairie LibCryptoLCH a ete comparee acelles obtenues avec les logiciels Magma, NTL et PARI/GP.Les resultats sont les suivants :
– LibCryptoLCH est 1000 fois plus rapide que PARI/GP– LibCryptoLCH est 2 fois plus rapide que Magma 2.13– LibCryptoLCH est 2 fois plus lente que NTL
Le comparatif des differentes librairies est visible sur le graphique 5.1 (qui ne contient pas lesresultats des tests pour Magma) :
Figure 5.1 – Comparatif entre LibCryptoLCH, NTL et PARI/GP
55
5.2 Outils de qualification de code
Au cours de ce stage, j’ai utilise quelques outils informatiques destines a la qualification decode.
5.2.1 Valgrind : analyse dynamique de l’execution d’un programme
Valgrind est un outil d’analyse dynamique de programmes. Je l’ai utilise de maniere intensivependant ce stage pour effectuer du profilage de code, en l’occurence :
– eliminer les fuites memoires (avec l’outil Memcheck)– visualiser les temps d’execution de mes differentes fonctions afin de les optimiser (avec l’outil
Callgrind)
5.2.2 Codecov : couverture de code
La couverture de code vise a s’assurer qu’on a correctement teste toutes les fonctions, quetoutes les lignes de code ont ete executees au moins une fois et que tous les parcours possibles (parexemple dans le cas d’un branchement if ou switch) ont ete parcourus.Le programme Codecov est un outil sous Linux effectuant la couverture de code.
5.2.3 Pmccabe : complexite cyclotomique d’un programme
La complexite cyclomatique est une metrique utilisee pour mesurer la complexite d’un pro-gramme, non pas au sens habituel en informatique mais en terme de nombre de branchementsdans le programme.L’outil Pmccabe sur Linux mesure la complexite cyclotomique d’un code source en C.
5.2.4 Cross-compilation
La portabilite du code etait une exigence vitale. Par consequent, en plus de devoir ecrire uncode le plus generique possible, j’ai utilise de nombreux outils permettant d’effectuer de la cross-compilation sur Linux, Windows et d’autres plateformes, et ce aussi bien en 32 bits que 64 bits.
5.2.5 Autres outils de qualification de code
J’ai egalement utilise d’autres outils destine a rendre le code clair et lisible pour qui voudraittravailler dessus (ce qui est couramment le cas en entreprise) : Astyle pour la mise en forme ducode et Doxygen pour sa documentation.
5.3 Denombrement des polynomes admissibles pour la re-duction forte
Si on ne connaıt pas a l’avance le polynome d’extension qu’on va choisir, alors la meilleurereduction qu’on connaisse est la reduction forte. Seulement cette derniere ne peut pas s’appliquersystematiquement, mais uniquement lorsque d◦r < w. C’est pourquoi j’ai essaye d’estimer, pourun degre d donne, le nombre TPI(d) de trinomes et pentanomes p(x) = xd + r(x) irreductibles etverifiant cette condition.PPI(d) designe le nombre de polynomes potentiellement irreductibles de degre d : il s’agit doncdes polynomes de degre d, n’admettant ni 1 ni 0 comme racines (donc de valuation 0 et avec unpoids de Hamming impair). On a donc PPI(d) = 2d−2 (car parmi les 2d polynomes de degre d, lamoitie est de valuation 0, et dans ceux qui restent, la moitie a un poids de Hamming impair).
56
TPPI(d) designe le nombre de trinomes et pentanomes tels que d◦r < w potentiellement ir-reductibles de degre d, donc de valuation 0 et avec un poids de Hamming impair. On a doncTPPI(d) =
(d−1
1
)+(d−1
3
)si d 6 w, TPPI(d) =
(w−1
1
)+(w−1
3
)sinon.
I(d) est le nombre de polynomes unitaires irreductibles de degre d sur F2.
TheoremeI(d) = 1
d
∑q|dµ(
dq
)2q, ou µ est la fonction de Mobius.
HeuristiqueL’estimation de TPI(d) repose sur l’hypothese suivante :
nombre de T&P xd + r(x) P.I. tels que d◦r < wnombre de polynomes de degre d P.I. = nombre de T&P xd + r(x) irreductibles tels que d◦r < w
nombre de polynomes de degre d irreductiblesTPPI(d,w)
PPI(d) = TPI(d,w)I(d)
D’ou on deduit une formule donnant le nombre de polynomes de la forme recherchee :
TPI(d) =I(d) · TPPI(d,w)
PPI(d)=I(d) · TPPI(d,w)
2d−2
Cette estimation n’est qu’une heuristique, il est possible qu’elle soit eloignee de la realite. Un esti-mation plus rigoureuse aurait pris trop de temps et n’etait de toute facon pas le sujet du stage.
Les resultats de cette estimation figurent sur le graphique 5.2 :
Figure 5.2 – Nombre estime de trinomes et pentanomes irreductibles de la forme p(x) = xd+r(x),ou d◦r < w
En pratique, cette estimation est plutot correcte : les degres d a partir desquels on ne trouveplus de trinomes et pentanomes de la forme recherchee sont :
– d = 35 pour w = 8– d = 339, 414, 451, ... pour w = 16– d = 2048, 2388, ... pour w = 32
En mettant cela en correlation avec l’heuristique, il faut en retenir que des que l’heuristique estimequ’il existe moins de 8 polynomes de degre d de la forme recherchee, il existe des corps de degred′ > d tels qu’on ne trouve aucun polynome de degre d′ de la forme recherchee, ce qui est conformea nos attentes.
57
Conclusion
Dans ce rapport, j’ai presente diverses methodes de reduction, de multiplication, d’exponentia-tion et d’inversion dans GF (2d). Une attention particuliere a ete portee sur l’operation de reductionpolynomiale, brique de base pour les autres methodes.
La rapidite de la fonction de reduction conditionne la rapidite des produit, carre et exponen-tiation dans GF (2d). Par consequent, il est imperatif que la reduction se fasse le plus rapidementpossible. En pratique, les differentes methodes de reduction que j’ai developpees ont permis degagner un facteur 100 sur la reduction polynomiale bit-a-bit.Pour les reductions generees par un generateur de code ecrit par mes soins, on va meme jusqu’agagner un facteur 1000, ces reductions etant encore plus rapides que celles presentees dans [?]comme etant optimales.
Cette diminution drastique du temps d’execution de la reduction a eu un impact important sur lalibrairie qui est devenue, pour le produit dans GF (2d) :
– 100 fois plus rapide que PARI/GP– 2 fois plus rapide que Magma 2.13– 2 fois plus lente que la derniere version de NTL, qui est l’outil le plus rapide que j’aie teste.
J’ai egalement implemente le produit et le carre de Montgomery, dont j’ai fortement augmente lavitesse en ajoutant des corrections aux version proposees dans [?], en permettant notamment derealiser le produit de Montgomery en un temps O(dlog2(3)) au lieu d’un temps O(d2).
L’exponentiation a quant a elle non seulement profite de l’amelioration de la reduction, mais aegalement ete enrichie de nombreuses variantes. J’ai d’abord implemente l’exponentiation de Mont-gomery, qui est dans certains cas plus rapide que son equivalent classique. Les methodes 2k-airespour le calcul de l’exponentiation, ou methodes fenetrees, ont egalement ete implementees, et leursanalyses de complexite completement revues afin de tenir compte des specificites du produit et ducarre dans GF (2d).
L’inversion dans GF (2d) a egalement ete fortement amelioree puisque j’ai developpe un algorithmerealisant l’inversion exponentielle en effectuant au plus 2 log2(d−1) multiplications dans GF (2d) aulieu de d−1 dans le cas de l’inversion par ”square and multiply”. Dans certains systemes embarquesou on dispose d’une instruction hardware pour le produit dans GF (2d), cette inversion pourraitmeme s’averer plus rapide que celle realisee par l’algorithme d’Euclide etendu.
Des methodes d’inversion exponentielles par blocs optimisees ont egalement ete developpees, per-mettant de n’effectuer que 2
√d− 1 produits dans GF (2d), au lieu de d − 1 pour la methode
”square-and-multiply” naıve.
Enfin, une partie importante de mon stage a ete consacree a la qualification de la librairie. Ils’agissait de l’optimiser, de la documenter, de la rendre robuste et utilisable aussi bien :
– sur un systeme d’exploitation Linux ou Windows– avec une architecture i386, x64, SPARC ou ARM– avec des mots machine de taille 8, 16, 32 ou 64
Il etait en effet necessaire d’obtenir un niveau de qualite industrielle operationnelle, rapide, fiableet integrable aussi bien sur des ordinateurs que des cartes a puce.
58
Au total, plus de 5 000 lignes de code ont ete tapees, sans compter les 78 000 lignes de codeecrites par le generateur de code pour la reduction polynomiale.La realisation de ce travail, en plus de me faire progresser en programmation, m’a permis de meformer aux methodes de developpement en entreprise. J’ai egalement decouvert de nombreux outilsde de debuggage, de documention, d’analyse dynamique et de couverture de code. Ces outils m’ontete et me seront surement encore tres utiles.
D’un point de vue plus personnel, j’ai pu me familiariser avec la recherche et le developpementen entreprise. Ce premier contact avec le laboratoire Chiffre de Thales, compose de specialistes encryptographie et informatique, m’a donne envie de poursuivre ma collaboration avec eux, et plusgeneralement la recherche en entreprise.
Apres discussion avec Sylvain Lachartre et Eric Garrido, il a ete decide que je m’inscrive pourune these sur le Chiffrement Homomorphique, sujet pour lequel nous avions un interet communpuisque je l’avais etudie pour mon PER de Master 2, et que Thales demarrage un projet en col-laboration avec Orange sur le Cloud Computing, domaine riche d’applications pour le chiffrementhomomorphique.
Il s’agira d’une these CIFRE conjointement encadree par Thales et l’ENS. Sylvain sera mon enca-drant a Thales, alors que mon directeur de these a l’ENS sera Vadim Lyubashevsky. Le titre de lathese est ”Cryptographie sur les reseaux et chiffrement homomorphique”.
59
Bibliographie
[CKK98] Tolga Acar Cetin K. Koc. Montgomery multiplication in gf(2k). In Boston KluwerAcademic Publishers, editor, Designs, Codes and Cryptography, volume 14(1), pages 57–69. Kluwer Academic Publishers, Boston, 1998.
[CS12] Haining Fan Chen Su. Impact of intel’s new instruction sets on software implementationof gf(2)[x] multiplication. In Information Processing Letters, volume Volume 112 Issue12, June, pages 497–502. Elsevier North-Holland, Inc. Amsterdam, 2012.
[DH04] Scott Vanstone Darrel Hankerson, Alfred J. Menezes. Finite field arithmetic. In Springer,editor, Guide To Elliptic Curve Cryptography, pages 57–61. Springer, 2004.
[MK08] J. Fan I. Verbauwhede M. Knezevic, K. Sakiyama. Modular reduction in gf(2n) withoutpre-computational phase. In .K. Ko J. von zut Gathen, J.L. Imana, editor, WAIFI 2008,volume 5130 of LNCS, pages 77–87. Springer-Verlag Berlin Heidelberg 2008, 2008.
[Mon05] Peter L. Montgomery. Five, six, and seven-term karatsuba-like formulae. In IEEE Tran-sactions on Computers, volume Volume 54 Issue 3, March, pages 362–369. The IEEEComputer Society, 2005.
[oST00] National Institute of Standards and Technology. Federal information processing standardpublication 186-2. US Department of Commerce/National Institute of Standards andTechnology, January 2000.
[RHdf] Francisco Rodrıguez-Henrıquez. Modular exponentiation ˙http ://delta.cs.cinvestav.mx/∼francisco/arith/expo.pdf.
[RPB08] Emmanuel Thome Paul Zimmermann Richard P. Brent, Pierrick Gaudry. Faster multi-plication in gf(2)[x]. In A. Stein A.J. van der Poorten, editor, ANTS-VIII 2008, volume5011 of LNCS, pages 153–166. Springer-Verlag Berlin Heidelberg 2008, 2008.
60
Annexe A
Reductions generees par legenerateur de code pour w=32
Cette annexe contient les reductions generees par le generateur de code pour les couples (d, p)recommandes par le NIST pour l’utilisation d’ECDSA et en prenant comme taille de mot w = 32.
d = 163,p(x) = x163 + x7 + x6 + x3 + 1
static void GF2E_Reduction_163(void *g,WordList_t tmp,GF2E_t e)
{
/** Reduction pour w=32 **/
unsigned int T;
unsigned int j;
/** On traite le mot de poids fort **/
T = tmp[10];
tmp[10] = 0;
tmp[4] ^= T<<29;
tmp[5] ^= T>>3 ^ T ^ T<<3 ^ T<<4;
/** On traite les mots de poids intermediaires **/
for (j=1; j<5; j++)
{
T = tmp[10-j];
tmp[10-j] = 0;
tmp[4-j] ^= T<<29;
tmp[5-j] ^= T>>3 ^ T ^ T<<3 ^ T<<4;
tmp[6-j] ^= T>>29 ^ T>>28;
}
/** On traite le mot de poids faible **/
T = tmp[5]>>3;
tmp[5] &= 0x7;
tmp[0] ^= T ^ T<<3 ^ T<<6 ^ T<<7;
tmp[1] ^= T>>26 ^ T>>25;
/** Fin **/
WordList_CopyOpt(6, tmp, e);
}
61
Pour rappel, voici l’algorithme de reduction pour (d, p) = (163, x163 + x7 + x6 + x3 + 1) etw = 32 donne dans [?] :
Figure A.1 – Reduction polynomiale pour (d, p) = (163, x163 + x7 + x6 + x3 + 1) et w = 32
Comme vous pouvez le constater, les deux algorithmes de reduction sont identiques, sauf pourla reduction du premier mot ou le deuxieme algorithme effectue plus d’operations.Bien que les deux algorithmes soient corrects, celui genere par le generateur de code est plus efficacecar il effectue deux XOR et un acces memoire en moins.
Concernant les autres polynomes preconises par le NIST, les reductions du generateur de codeet celles de [?] sont identiques, sauf pour (d = 571, p(x) = x571 + x10 + x5 + x2 + 1) ou l’etape 4de l’algorithme de [?] est incorrecte : il faut remplacer 0x7FFFFFFF par 0x7FFFFFF (incorrectionconfirmee par les tests sur ordinateur).En plus d’etre automatise, ce generateur accepte n’importe quelle valeur pour d, pour p et pour w.
Dans la suite de l’annexe, seuls les programmes ecrits par le generateur de code seront donnes.
62
d = 233,p(x) = x233 + x74 + 1
static void GF2E_Reduction_233(void *g,WordList_t tmp,GF2E_t e)
{
/** Reduction pour w=32 **/
unsigned int T;
unsigned int j;
/** On traite le mot de poids fort **/
T = tmp[14];
tmp[14] = 0;
tmp[6] ^= T<<23;
tmp[7] ^= T>>9;
tmp[9] ^= T<<1;
/** On traite les mots de poids intermediaires **/
for (j=1; j<7; j++)
{
T = tmp[14-j];
tmp[14-j] = 0;
tmp[6-j] ^= T<<23;
tmp[7-j] ^= T>>9;
tmp[9-j] ^= T<<1;
tmp[10-j] ^= T>>31;
}
/** On traite le mot de poids faible **/
T = tmp[7]>>9;
tmp[7] &= 0x1ff;
tmp[0] ^= T;
tmp[2] ^= T<<10;
tmp[3] ^= T>>22;
/** Fin **/
WordList_CopyOpt(8, tmp, e);
}
63
d = 283,p(x) = x283 + x12 + x7 + x5 + 1
static void GF2E_Reduction_283(void *g,WordList_t tmp,GF2E_t e)
{
/** Reduction pour w=32 **/
unsigned int T;
unsigned int j;
/** On traite le mot de poids fort **/
T = tmp[17];
tmp[17] = 0;
tmp[8] ^= T<<5 ^ T<<10 ^ T<<12 ^ T<<17;
tmp[9] ^= T>>27 ^ T>>22 ^ T>>20 ^ T>>15;
/** On traite les mots de poids intermediaires **/
for (j=1; j<9; j++)
{
T = tmp[17-j];
tmp[17-j] = 0;
tmp[8-j] ^= T<<5 ^ T<<10 ^ T<<12 ^ T<<17;
tmp[9-j] ^= T>>27 ^ T>>22 ^ T>>20 ^ T>>15;
}
/** On traite le mot de poids faible **/
T = tmp[8]>>27;
tmp[8] &= 0x7ffffff;
tmp[0] ^= T ^ T<<5 ^ T<<7 ^ T<<12;
/** Fin **/
WordList_CopyOpt(9, tmp, e);
}
64
d = 409,p(x) = x409 + x87 + 1
static void GF2E_Reduction_409(void *g,WordList_t tmp,GF2E_t e)
{
/** Reduction pour w=32 **/
unsigned int T;
unsigned int j;
/** On traite le mot de poids fort **/
T = tmp[25];
tmp[25] = 0;
tmp[12] ^= T<<7;
tmp[13] ^= T>>25;
tmp[14] ^= T<<30;
tmp[15] ^= T>>2;
/** On traite les mots de poids intermediaires **/
for (j=1; j<13; j++)
{
T = tmp[25-j];
tmp[25-j] = 0;
tmp[12-j] ^= T<<7;
tmp[13-j] ^= T>>25;
tmp[14-j] ^= T<<30;
tmp[15-j] ^= T>>2;
}
/** On traite le mot de poids faible **/
T = tmp[12]>>25;
tmp[12] &= 0x1ffffff;
tmp[0] ^= T;
tmp[2] ^= T<<23;
/** Fin **/
WordList_CopyOpt(13, tmp, e);
}
65
d = 571,p(x) = x571 + x10 + x5 + x2 + 1
static void GF2E_Reduction_571(void *g,WordList_t tmp,GF2E_t e)
{
/** Reduction pour w=32 **/
unsigned int T;
unsigned int j;
/** On traite le mot de poids fort **/
T = tmp[35];
tmp[35] = 0;
tmp[17] ^= T<<5 ^ T<<7 ^ T<<10 ^ T<<15;
tmp[18] ^= T>>27 ^ T>>25 ^ T>>22 ^ T>>17;
/** On traite les mots de poids intermediaires **/
for (j=1; j<18; j++)
{
T = tmp[35-j];
tmp[35-j] = 0;
tmp[17-j] ^= T<<5 ^ T<<7 ^ T<<10 ^ T<<15;
tmp[18-j] ^= T>>27 ^ T>>25 ^ T>>22 ^ T>>17;
}
/** On traite le mot de poids faible **/
T = tmp[17]>>27;
tmp[17] &= 0x7ffffff;
tmp[0] ^= T ^ T<<2 ^ T<<5 ^ T<<10;
/** Fin **/
WordList_CopyOpt(18, tmp, e);
}
66
