Upload
dothuan
View
216
Download
2
Embed Size (px)
Citation preview
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Developpement et qualificationd’une bibliotheque de calculs algebriquesappliques a la cryptographie sur GF (2d)
Thomas Prest
28 septembre 2012
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 1/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
1 Introduction
2 La reduction polynomialeLa reduction bit-a-bitLa reduction mot-a-mot
3 L’inversion dans GF (2d)L’inversion exponentielle par blocsL’inversion exponentielle rapide
4 Conclusion
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 2/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
1 Introduction
2 La reduction polynomialeLa reduction bit-a-bitLa reduction mot-a-mot
3 L’inversion dans GF (2d)L’inversion exponentielle par blocsL’inversion exponentielle rapide
4 Conclusion
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 3/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Rendre le module de calculs sur GF (2d) de LibCryptoLCh :
Complet d’un point de vue algorithmique : reduction, produit,exponentiation, inversion...
Portable sur de nombreux OS×processeurs×architectures de mots
Fiable et rapide
Ameliorations apportees au niveau algorithmique :
Reduction polynomiale mod p(x)
Multiplication dans GF (2d)
Exponentiation dans GF (2d)
Inversion dans GF (2d)
Generation de corps GF (2d) parametrables
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 4/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Rendre le module de calculs sur GF (2d) de LibCryptoLCh :
Complet d’un point de vue algorithmique : reduction, produit,exponentiation, inversion...
Portable sur de nombreux OS×processeurs×architectures de mots
Fiable et rapide
Ameliorations apportees au niveau algorithmique :
Reduction polynomiale mod p(x)
Multiplication dans GF (2d)
Exponentiation dans GF (2d)
Inversion dans GF (2d)
Generation de corps GF (2d) parametrables
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 4/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Rendre le module de calculs sur GF (2d) de LibCryptoLCh :
Complet d’un point de vue algorithmique : reduction, produit,exponentiation, inversion...
Portable sur de nombreux OS×processeurs×architectures de mots
Fiable et rapide
Ameliorations apportees au niveau algorithmique :
Reduction polynomiale mod p(x)
Multiplication dans GF (2d)
Exponentiation dans GF (2d)
Inversion dans GF (2d)
Generation de corps GF (2d) parametrables
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 5/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
1 Introduction
2 La reduction polynomialeLa reduction bit-a-bitLa reduction mot-a-mot
3 L’inversion dans GF (2d)L’inversion exponentielle par blocsL’inversion exponentielle rapide
4 Conclusion
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 6/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Contexte :On travaille sur le corps fini a 2d elements
GF (2d) = F2d =F2[x ]
(p(x))
ou p(x) est un polynome irreductible de degre d sur F2[x ]
Notations :
p(x) = xd + r(x)
nb = |p| est le nombre de coefficients non-nuls de p, ou poids de Hammingde p. En pratique on choisit nb = 3 ou 5 (calculs plus rapides).
Les pi sont les indices des coefficients non-nuls de p : p(x) =nb−1∑i=0
xpi .
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 7/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Representation des elements :On represente un element de GF (2d) comme un polynome binaire, puis commeun entier.On tire parti de la representation en mots machine de taille w
GF (2d) → J0; 2d − 1K → J0; 2w − 1Kdd/we
a(x) =∑d−1
i=0 aixi 7→ N =
∑d−1i=0 ai2
i 7→ [N0,N1, ...,Ndd/we−1]
Exemple pour d = 8 et w = 4 :
GF (28) → J0; 255K → J0; 15K2
a(x) = x7 + x5 + x2 + x + 1 7→ N = 167 = 0xa7 7→ [7, 10] = [0x7, 0xa]
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 8/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Le probleme de la reduction polynomiale
Methode utilisee ici pour multiplier 2 elements a(x), b(x) ∈ GF (2d) :
1 Multiplication polynomiale :c0(x)← a(x) · b(x). c0 est au plus de degre 2(d − 1).
2 Reduction polynomiale :c(x)← c0(x) mod p(x). c est au plus de degre d − 1.
On s’interesse ici a la deuxieme etape, la reduction polynomiale.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 9/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Un algorithme de reduction bit-a-bit
Reduction bit-a-bit :
Reduction_Bit(a):
| for (i = d-2...0)
| | if(a[d+i] == 1)
| | | a[d+i] := 0;
| | | for(j = 0...nb-2)
| | | | a[i+p_j] ^= 1;
| | | endfor
| | endif
| endfor
end
Probleme :Reduction Bit est beaucoup trop lent !
2 fois plus lent que le produit polynomial
100 fois plus lent que le carre polynomial
Il faudrait tirer parti de l’utilisation des mots machine pour reduire w bits d’uncoup au lieu d’un a la fois =⇒ Gain potentiel d’un facteur w
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 10/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Comment effectuer la reduction mot-a-mot
Principe de la reduction mot-a-mot :On a xd = r(x) mod p(x). Donc
T (x) · xk = T (x) · xk−d · r(x) mod p(x)
Pour reduire selon le polynome T (x) · xk , on recupere T (x) · xk , et on le”redistribue” dans les mots d’indices plus faibles.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 11/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Principe de la reduction mot-a-mot
H I I BB
Figure: Reduction mot a mot. Debut.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 12/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Principe de la reduction mot-a-mot
H I I B
Figure: Reduction mot a mot. Etape 1.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 13/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Principe de la reduction mot-a-mot
H I I B
Figure: Reduction mot a mot. Etape 2.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 14/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Principe de la reduction mot-a-mot
H I I B
Figure: Reduction mot a mot. Etape 3.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 15/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Principe de la reduction mot-a-mot
H I I B
Figure: Reduction mot a mot. Etape 4.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 16/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Principe de la reduction mot-a-mot
H I I B
Figure: Reduction mot a mot. Fin.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 17/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Un premier algorithme de reduction mot-a-mot
Reduction_Forte(a)
| k0 = arrondisup(d/w) ;
| quo = k0+d/w;
| rem = d%w;
| for (k = k0...0)
| | 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
end
Par rapport a Reduction Bit :Gain theorique : entre w/2 et w/8.Gain pratique : 100 fois plus rapide !
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 18/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Le phenomene de rebouclage
H I I B
Figure: Rebouclage. Debut.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 19/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Le phenomene de rebouclage
H I I B
Figure: Rebouclage. Etape 1.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 20/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Le phenomene de rebouclage
H I I B
Figure: Rebouclage. Etape 2.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 21/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Le phenomene de rebouclage
H I I B
Figure: Rebouclage. Etape 3.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 22/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Le phenomene de rebouclage
H I II B
Figure: Rebouclage. Etape 4.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 23/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Le phenomene de rebouclage
H I II B
Figure: Rebouclage. Etape 5.
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 24/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Quand et comment gerer le rebouclage ?
On rappelle que p(x) = xd + r(x).Le rebouclage peut arriver des que d − d◦r < w ⇒ Une reduction ne suffit pas !
Deux solutions :
Reduire le mot tant qu’il est nul (boucle while)
Reduire le mot⌈
wd−d◦r
⌉fois (boucle for)
Reduction Generique : Identique a Reduction Forte, mais avec une bouclewhile pour prendre en compte le rebouclage.
Performances de Reduction Generique :Par rapport a Reduction Bit : 50 fois plus rapide.Par rapport a Reduction Forte : 2 fois plus lent, mais s’applique pour toutp(x).
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 25/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Quand et comment gerer le rebouclage ?
On rappelle que p(x) = xd + r(x).Le rebouclage peut arriver des que d − d◦r < w ⇒ Une reduction ne suffit pas !
Deux solutions :
Reduire le mot tant qu’il est nul (boucle while)
Reduire le mot⌈
wd−d◦r
⌉fois (boucle for)
Reduction Generique : Identique a Reduction Forte, mais avec une bouclewhile pour prendre en compte le rebouclage.
Performances de Reduction Generique :Par rapport a Reduction Bit : 50 fois plus rapide.Par rapport a Reduction Forte : 2 fois plus lent, mais s’applique pour toutp(x).
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 25/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Figure: Comparaison des reductions avec le produit et le carre
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 26/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Figure: Comparaison des reductions avec le produit et le carre
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 27/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Un exemple de reduction precalculee
Il existe des algorithmes de reduction ultra-rapides pour certaines valeurs de(d , p) et certaines tailles w de mots machine :
Figure: Algorithme de reduction pour d = 163, p(x) = x163 + x7 + x6 + x3 + 1,w = 32
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 28/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Conception d’un generateur de code
La reduction d’un mot machine par p(x) s’effectue ainsi :
T (x) · x i·w = T (x) · x i·w−d · r(x) mod p(x)
Ce qui se traduit ainsi (en sarcelle, ce que le generateur retourne en sortie) :
1 T = tmp[i]; //On recupere les w bits i ·w ...i ·w + (w − 1)
2 tmp[i] = 0;
3 for(j = 0...nb− 2)k = i ∗ w− d + pj; //On calcule ou redistribuer ces w bitstmp[k/w] = T << (k mod w); //On redistribuetmp[k/w + 1] = T >> (w− (k mod w)); //On redistribue
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 29/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Un premier programme ecrit par le generateur
Pour d = 66, p(x) = x66 + x3 + 1,w = 64 :
void GF2E_Reduction_66(const Gf2eData_t*gf,WordList_t tmp,GF2E_t e)
{unsigned long 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);
}
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 30/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Un premier programme ecrit par le generateur
Pour d = 66, p(x) = x66 + x3 + 1,w = 64 :
void GF2E_Reduction_66(const Gf2eData_t*gf,WordList_t tmp,GF2E_t e)
{unsigned long T = tmp[2];
tmp[2] = 0; //Rebouclage necessaire
tmp[0] ^= T<<62;
tmp[1] ^= T>>2;
tmp[1] ^= T<<1;
tmp[2] ^= T>>63; //Ligne inutile
T = tmp[1]>>2;
tmp[1] &= 0x3;
tmp[0] ^= T; //On peut regrouper
tmp[0] ^= T<<3; //ces deux lignes
tmp[1] ^= T>>61;
GF2E_Copy(gf,tmp,e);
}
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 31/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Un premier programme ecrit par le generateur
Pour d = 66, p(x) = x66 + x3 + 1,w = 64 :
void GF2E_Reduction_66(const Gf2eData_t*gf,WordList_t tmp,GF2E_t e)
{unsigned long T = tmp[2];
tmp[2] = 0; //Rebouclage necessaire
tmp[0] ^= T<<62;
tmp[1] ^= T>>2;
tmp[1] ^= T<<1;
tmp[2] ^= T>>63; //Ligne inutile
T = tmp[1]>>2;
tmp[1] &= 0x3;
tmp[0] ^= T; //On peut regrouper
tmp[0] ^= T<<3; //ces deux lignes
tmp[1] ^= T>>61;
GF2E_Copy(gf,tmp,e);
}
Nouveau generateur tenant compte de ces observations, en deux versions :
Une version avec des boucles for (code plus compact)Une version deroulant les boucles for (code plus rapide)
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 32/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
d = 163,p(x) = x163 + x7 + x6 + x3 + 1,w = 32
static void GF2E_Reduction_163(void *g,WordList_t tmp,GF2E_t e){
unsigned long T, j;
T = tmp[10];tmp[10] = 0;tmp[4] ^= T<<29;tmp[5] ^= T>>3 ^ T ^ T<<3 ^ T<<4;
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;
}
T = tmp[5]>>3;tmp[5] &= 0x7;tmp[0] ^= T ^ T<<3 ^ T<<6 ^ T<<7;tmp[1] ^= T>>26 ^ T>>25;
WordList_CopyOpt(6, tmp, e);}
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 33/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Complexite d’une Reduction Precalculee d
Par rapport a Reduction Forte :∼4 fois plus rapide
Par rapport a Reduction Generique :∼8 fois plus rapide
Par rapport a Reduction Bit :∼800 fois plus rapide
Reduction Op. Logiques Op. Arithmetiques Acces memoire Branchements
Bit-a-bit 12
(nb − 1)(d − 1) 12nb(d − 1) 1
2nb(d − 1) d − 1
Generique 4nw(nb − 1) + 11 4 + 2nw(nb + 2) 3nw + 2 3nw + 4Forte 4nw(nb − 1) + 11 4 + 2nw(nb + 2) 2nw + 2 2nw + 4
Precalculee 4nw(nb − 1) 0 ∼ 3nw 0
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 34/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Comparatif entre les differentes reductions
Figure: Temps ajoute au produit pour d = 1...256
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 35/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Comparatif entre les differentes reductions
Figure: Temps ajoute au carre pour d = 1...256
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 36/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Comparaison avec GP et NTL
Figure: Comparaison avec GP et NTL pour la multiplication dans GF (2d)
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 37/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
1 Introduction
2 La reduction polynomialeLa reduction bit-a-bitLa reduction mot-a-mot
3 L’inversion dans GF (2d)L’inversion exponentielle par blocsL’inversion exponentielle rapide
4 Conclusion
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 38/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
L’inversion dans GF (2d)
Inversion dans GF (2d) couramment utilisee en cryptographie :
AES (avec d = 8)
ECDSA (avec d = 163, 233, 283, 409 ou 571)
Methodes pour realiser l’inversion :
Look-up table (pour les tres petits corps)
Algorithme d’Euclide etendu (tres efficace en software)
Par exponentiation : a−1 = a2d−2 (mauvais en software, mais bon enhardware)
Knuth-Schonhage : complexite O(M(d) log2(d)) (uniquement pour les tresgrands corps)
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 39/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Quelques notations :
Pour n ∈ N, on note nk−1...n1n0 l’ecriture en binaire de n.Ainsi, 140 = 27 + 23 + 22 = 10001100
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
Remarque :
On a a−1 = a2d−2 = (a2d−1−1)2 = (yd−1)2
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 40/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
L’exponentiation par blocs classique
Algorithm 1 Exponentiation 2k -aire
Entree: a ∈ GF (2d), e, k ∈ N∗Sortie: ae mod p
1: Precalculer tous les aj , pour j = 1...2k − 12: c ← 13: for i = d d−1
k e to 0 do4: for j = 1 to k do5: c ← c2
6: end for7: exp = ek·i...k·i+k−1
8: if (exp 6= 0) then9: c ← c · aexp
10: end if11: end for12: return c
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 41/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Remarque :On a 2d−1 − 1 = 11...11d−1.
Si on applique l’algorithme precedent pour calculer a2d−1−1, on aura toujoursexp = 11...11k ou exp = 11...11(d−1) mod k .
Amelioration suggeree :Il suffit de precalculer yk = a11...11k et y(d−1) mod k = a11...11(d−1) mod k au lieu des
2k puissances de a a calculer normalement
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 42/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Complexite de l’inversion exponentielle par blocs
Gain en precalculs par rapport a l’algorithme classique :2 puissances de a a precalculer au lieu de 2k :
2 valeurs a stocker au lieu de 2k − 1
k − 1 carres(resp. produits) au lieu de 2k−1 − 1 carres (resp. produits)
Complexite :INVEXB(d , k) = (k − 1) (S(d) + M(d))+(k · b d−1
k c+ 1)S(d) + b d−1k cM(d)
INVEXB(d , ·) est minimal pour kd =√
d−11+S/M(d) . Ce qui donne :
d − 1 +√
d−11+S/M(d) carres
√d − 1
(2+S/M(d)√
1+S/M(d)
)− 1 produits
Soit environ :
d +√d carres au lieu de d
2√d produits au lieu de d
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 43/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Complexite de l’inversion exponentielle par blocs
Gain en precalculs par rapport a l’algorithme classique :2 puissances de a a precalculer au lieu de 2k :
2 valeurs a stocker au lieu de 2k − 1
k − 1 carres(resp. produits) au lieu de 2k−1 − 1 carres (resp. produits)
Complexite :INVEXB(d , k) = (k − 1) (S(d) + M(d))+(k · b d−1
k c+ 1)S(d) + b d−1k cM(d)
INVEXB(d , ·) est minimal pour kd =√
d−11+S/M(d) . Ce qui donne :
d − 1 +√
d−11+S/M(d) carres
√d − 1
(2+S/M(d)√
1+S/M(d)
)− 1 produits
Soit environ :
d +√d carres au lieu de d
2√d produits au lieu de d
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 43/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Complexite de l’inversion exponentielle par blocs
Gain en precalculs par rapport a l’algorithme classique :2 puissances de a a precalculer au lieu de 2k :
2 valeurs a stocker au lieu de 2k − 1
k − 1 carres(resp. produits) au lieu de 2k−1 − 1 carres (resp. produits)
Complexite :INVEXB(d , k) = (k − 1) (S(d) + M(d))+(k · b d−1
k c+ 1)S(d) + b d−1k cM(d)
INVEXB(d , ·) est minimal pour kd =√
d−11+S/M(d) . Ce qui donne :
d − 1 +√
d−11+S/M(d) carres
√d − 1
(2+S/M(d)√
1+S/M(d)
)− 1 produits
Soit environ :
d +√d carres au lieu de d
2√d produits au lieu de d
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 43/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Comparatif
Figure: Comparaison entre les differentes inversions par blocs pour d = 1...4096
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 44/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Un algorithme d’inversion encore plus rapide
Un autre algorithme exploitant la forme particuliere de l’exposant 2d − 2 dansl’inversion exponentielle.
Des notations supplementaires :
On note S(a) = a2 le carre de a.
Pour k ∈ N, on note zk = y2k = a11...112k = a22k−1
On pose ` = blog2(d − 1)c
On note d − 1 =∑k=0
dk2k
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 45/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Une autre facon d’exploiter la forme de 2d−1 − 1
Proposition.
Si on connait k , k ′, yk = a2k−1 et yk′ = a2k′−1, alors on peut calculer yk+k′ enk ′ carres et un produit.
Demonstration.
yk+k′ = a2k+k′−1 = a(2k+k′−2k′ )+(2k′−1) = (a2k−1)2k′
· a2k′−1 = Sk′(yk) · yk′
Exemple.Pour k = 8, k ′ = 4 :
y12 = a212−1
= a111111111111
= a111111110000+1111
= a111111110000 · a1111
= S4(a11111111) · a1111
= S4(y8) · y4
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 46/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Une autre facon d’exploiter la forme de 2d−1 − 1
Proposition.Connaissant a = z0, on peut calculer z0, z1, ..., z` en effectuant ` produits et2` − 1 carres.
Demonstration.On sait calculer zk = y2k a partir de zk−1 = y2k−1 en 1 produit et 2k−1 carres :
zk = S2k−1
(zk−1) · zk−1
On peut donc calculer les zk dans cet ordre :
z0 = a −→ z1 = S(z0) · z0 1 produit, 1 carre−→ z2 = S2(z1) · z1 1 produit, 2 carres−→ z3 = S4(z2) · z2 1 produit, 4 carres−→ ... ......................
−→ z` = S2`−1
(z`−1) · z`−1 1 produit, 2`−1 carres
Total : ` produits et 2` − 1 carres
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 47/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Un exemple d’inversion exponentielle rapide
Exemple :Dans GF (225), a−1 = a225−2 = (a224−1)2 = (y24)2.Calcul de a−1 :
1 z0 = a1 → z1 = a11 → z2 = a1111 → z3 = a11111111 → z4 = a1111111111111111
2 24 = 16 + 8, donc on peut calculer y24 a partir de z4 = y16 et z3 = y8 :
y24 = S8(z16) · z8
= S8(z4) · z3
= S8(a1111111111111111) · a11111111
= a111111111111111100000000 · a11111111
= a111111111111111111111111
3 a−1 = (y24)2
Total :24 carres et 5 produits
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 48/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Complexite de l’inversion exponentielle rapide
Complexite :
d − 1 carres
`+ Hamming(d − 1)− 1 produits (au pire 2` produits, au mieux `)
Soit environ
le meme nombre de carres : d − 1
log2(d) produits au lieu de d
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 49/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
De l’importance d’avoir une reduction rapide
Comparaison de l’inversion exponentielle rapide selon qu’on reduit avecReduction Generique ou avec une Reduction Precalculee d....-G ⇒ Calculs avec la reduction generique...-P ⇒ Calculs avec la reduction precalculee
d Tps exec. en µs dont % Mul dont % Square dont % Red
163-G 27.14 21.12 14.43 63.42163-P 11.00 40.04 30.33 22.06
233-G 44.69 16.23 15.78 65.98233-P 16.94 37.72 37.76 17.77
283-G 61.20 27.35 16.76 58.17283-P 30.56 42.33 30.68 22.52
409-G 115.75 19.73 18.17 61.89409-P 49.43 39.29 38.88 17.94
571-G 216.77 19.59 16.93 61.85571-P 106.79 37.61 32.69 27.14
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 50/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Figure: Comparaison entre les differentes inversions pour d = 1...512
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 51/55
Introduction La reduction polynomiale L’inversion dans GF (2d ) Conclusion
Conclusion
Travaux realises pendant le stage :
Reduction, exponentiation, inversion
Optimisation des fonctions deja presentes, debogage
Cross-compilation, qualification pour diverses tailles de mots
Generation aleatoire de corps finis avec possibilite de parametrer p (degre,poids de Hamming...)
Benchs avec precision a la microseconde
Tests avec vecteurs aleatoires, couverture de code
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 52/55
Algorithmes detailles
Un algorithme generique de reduction mot-a-mot
Reduction_Generique(a)
| k0 = arrondisup(d/w);
| quo = k0+d/w;
| rem = d%w;
| for (k = k0...0)
| | 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
| | | atmp = Selection_Mot(a, quo, rem);
| | endwhile
| endfor
end
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 53/55
Algorithmes detailles
L’algorithme d’inversion exponentielle par blocs
Algorithm 2 Inversion exponentielle par blocs sur GF (2d)
Entree: a ∈ GF (2d), k ∈ N∗Sortie: a−1 ∈ GF (2d)
1: Calculer quo ← b(d − 1)/kc, rem← d − 1 mod k , yk et yrem2: if rem 6= 0 then3: c ← yrem4: else5: c ← 16: end if7: for i = 1 to quo do8: for j = 1 to k do9: c ← c2
10: end for11: c ← c · yk12: end for13: return c2
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 54/55
Algorithmes detailles
L’algorithme d’inversion exponentielle rapide
Algorithm 3 Inversion exponentielle rapide sur GF (2d)
Entree: a ∈ GF (2d)Sortie: a−1 ∈ GF (2d)
1: Calculer ` = blog2(d − 1)c et d − 1 =∑`
k=0 dk2k
2: z0 ← a3: for k = 1 to ` do
4: zk ← S2k−1
(zk−1) · zk−1 //Precalcul des zk = a22k−1
5: end for6: c ← z` //c = a2`−1−1
7: for k = `− 1 down 0 do8: if dk = 1 then9: c ← S2k
(c) · zk //c = a2exp−1, exp =∑`
i=k dk2k
10: end if11: end for //c = a2d−1−1
12: return c2 //c = a2d−2 = a−1
Thomas Prest — Developpement et qualification d’une bibliotheque de calculs algebriques appliques a la cryptographie sur GF (2d ) 55/55