Sécurité des Couplages

La sécurité des couplages sur les courbes elliptiques repose essentiellement sur la difficulté de la résolution du problème du logarithme discret sur les courbes elliptiques (G1 et G2) et sur les corps finis (G3). Le niveau de sécurité est défini par le nombre d’opérations nécessaires sur le corps de base pour résoudre le problème de logarithme discret. Le niveau de sécurité est donné en bits et nous utilisons la notion de sécurité équivalente pour le définir. Par exemple, le niveau de sécurité 128 bits signifie qu’il nous faut au minimum 2128 opérations pour résoudre le problème du logarithme discret sur les groupes en considération. En cryptographie basée sur les couplages, pour définir le niveau de sécurité, nous devons définir deux bornes. La première est la taille du sous groupe de la courbe elliptique dans lequel nous travaillons qui vaut log2(r). La deuxième borne est la taille du corps fini où vivent les résultats d’un couplage c’est-à-dire la taille binaire de F_ pk qui vaut log2(pk). Par conséquent, lorsque le niveau de sécurité augmente les deux bornes log2(r) et k log2(p) augmentent aussi mais avec des rythmes différents. Il est clair que la deuxième borne, k log2(p) augmente d’une manière plus rapide que la première.

Nous donnons dans le tableau les tailles de r et pk en bits selon les recommandations du NIST [oST] pour les niveaux standards de sécurité . Il faut toutefois prendre en compte les résultats récents sur le calcul du logarithme discret sur les corps finis [KB16]. Les valeurs de la dernière colonne devraient donc être plus élevées. D’après ce tableau, pour assurer un niveau de sécurité de 80 bits par exemple, il faut que choisir p et k tels que pk soit de taille 1024 bits. Les tailles des paramètres sont fixées les unes en fonction des autres et on note _ = log2(p) log2(r) Ayant la taille de r et de p, nous pouvons déduire le degré de plongement idéal de la courbe k. Remarque 1.14. Les courbes elliptiques pour lesquelles le paramètre _ est proche de 1 sont favorisées pour les applications cryptographiques [FST10]. Lors du calcul du couplage, nous nous ramenons à des opérations dans le corps de base Fp. Cela signifie que l’implémentation efficace des couplages dépend directement du corps de base utilisé, c’est-à-dire de la taille de p en bits. Donc, pour avoir un couplage efficace, il vaut mieux bien choisir k afin d’atteindre le niveau de sécurité souhaité que d’augmenter la taille de p. Dans le tableau suivant, nous présentons les valeurs de k pour atteindre un niveau de sécurité précis en fonction de la taille de r et de celle de p (pour plus de détails voir [FST10]). Nous avons choisi ici d’utiliser un intervalle pour la taille de pk tenant compte des résultats de [KB16] mais ces données sont approximatives car elles n’ont pas encore été étudiées sérieusement par la communauté.

Le Couplage Optimal Ate

Le couplage Optimal Ate a été proposé par Vercauteren dans [Ver10]. Définition 1.23. Soit e : G1 _ G2 7􀀀! G3 un couplage j G1 j=j G2 j=j G3 j= r. e est dit un couplage optimal s’il peut être calculé en exactement log2(r)=_(k) + _(k) itérations de l’algorithme de Miller, où k est le degré de plongement relativement à r et _(k) 6 log2(k). Remarque 1.17. La définition du couplage Optimal Ate que nous venons de donner ne spécifie pas que e soit calculé en évaluant une seule fonction de Miller f_;Q comme le cas du couplage de Ate. Par contre, ce couplage peut être défini par le produits des f_i;Q ou autres combinaisons sous la contrainte que le calcul à faire ne dépasse pas log2(r)=_(k) itérations au total. Dans les Chapitres 3 et 4 , nous allons étudier le couplage Optimal Ate sur des catégories différentes de courbes elliptiques. Nous allons définir le groupe G2 en faisant intervenir la courbe tordue que nous avons défini dans la Section 1.3.4. L’utilisation d’une telle courbe optimise le calcul des couplages au niveau de l’algorithme de Miller. Dans notre travail, nous sommes intéressés aux courbes tordues pour un twist de degré pair, c’està- dire pour d = 2; 4; et 6. Pour montrer l’importance de l’utilisation de la courbe tordue lors de calcul des couplages, nous traitons le cas de d = 2 (les autres cas se font de la même manière). Soit _ 2 Fpk=2 tel que _ n’est pas un carré dans Fpk=2 . La tordue E0 de E est définie sur Fpk=2 par l’équation _y2 = x3+ax+b: L’isomorphisme envoyant un point de Fpk sur un point de E(Fpk ) 40 CHAPITRE 1. GÉNÉRALITÉS est donné par : 2 : E0 􀀀 Fpk _ ! E(Fpk ) (x; y) 7! (x; y_1=2) On choisit alors G2 dans l’image de E0 􀀀 Fpk=2 _ par 2. Le point Q 2 E(Fpk ) peut alors s’écrire (xQ; yQ_) avec xQ; yQ 2 Fpk=2 .

Remarque 1.18. La non non-dégénérescence du couplage défini en utilisant la courbe tordue est prouvée dans [BLS03]. En utilisant les coordonnées Jacobiennes présentées dans le Paragraphe 1.2.2, les équations de droites intervenant dans le calcul de l’algorithme de Miller sont [CLN10] : l1(xQ; yQ_) = Z2P (Z2TDyQ_ 􀀀 B(DxQ 􀀀 XT ) 􀀀 2YT )), v1(xQ; yQ_) = Z2 2TZP xQ + 4Y 2 P (XPD + XTZ2P ) 􀀀 9Z2P (X2 T 􀀀 Z4T )2, l2(xQ; yQ_) = Z2T +P 􀀀 Z3T EyQ_ 􀀀 ZTF(Z2T xQ) 􀀀 YTE _ , v2(xQ; yQ_) = Z3T E 􀀀 Z3T +P xQ + E(A + B) 􀀀 Z2T Z2P F _ D’après ces équations, nous remarquons que les additions et les multiplications intervenant dans ces formules s’effectuent dans le corps Fp et dans Fpk=2 au lieu d’être effectuées dans le corps Fpk . Ce résultat est important car l’arithmétique sur le corps fini Fpk=2 est moins coûteuse que celle dans Fpk . (Voir Chapitre 2). De plus, nous remarquons aussi que les droites verticales v1 et v2 ne font pas intervenir l’ordonnée du point Q, et donc _ non plus. Il est clair que v1(XQ; yQ_) et v2(xQ; yQ_) sont des éléments de Fpk=2 . Ces expressions seront donc éliminées par l’exponentiation finale et il n’est donc pas nécessaire de les calculer. Cela est dû au résultat suivant Proposition 1.3. Soit r un diviseur premier de ]E(Fp) pour E une courbe elliptique de degré de plongement k pair et relativement à r. Alors pk􀀀1 r est un multiple de pk=2 􀀀 1. Preuve. Nous avons,

Arithmétique sur les corps finis pour les couplages

Dans la suite de cette thèse, nous utilisons les notations suivantes pour décrire les opérations dans le corps fini Fpk . Ak est le coût d’une addition dans Fpk , A0 k est le coût d’une multiplication par 2 dans Fpk , Mk est le coût d’une multiplication dans Fpk , sMk est le coût d’une multiplication creuse ’sparse multiplication’ dans Fpk (voir la Définition 2.2.3), mk;c désigne le coût de la multiplication par une constante c dans Fpk . Sk est le coût d’une élévation au carré dans Fpk , Fk est le coût d’un Frobenius dans Fpk (voir la Définition 2.3), Ik est le coût d’une inversion dans Fpk Pour faciliter les notations et comme nous l’avons noté dans le chapitre 1, la multiplication dans Fp est notée par M, le carré par S et l’inversion par I. Dans ce chapitre, nous allons présenter l’arithmétique sur les corps finis pour les couplages. Plus précisément, nous nous intéressons dans notre travail aux couplages optimaux et nous allons présenter l’arithmétique sur les corps finis utilisés pour le calcul du couplage Optimal Ate. Pour calculer le couplage Optimal Ate sur les courbes elliptiques nous avons besoin de l’arithmétique dans les corps Fp, Fpk=d et Fpk . Dans notre travail, nous allons plutôt étudier les courbes elliptiques de degré de plongement k = 12, c’est le cas des courbes de Barreto et Naehrig [BN05] et aussi les courbes de Barreto, Lynn et Scott [BLS02]. Nous allons également considérer les courbes elliptiques de degré de plongement égal à 16 qui sont les courbes de Kachisa, Schafer et Scott [KSS07]. Pour cette raison, nous allons présenter deux types d’extensions de Fp qui sont Fp2i et Fp3i pour qu’on puisse définir l’arithmétique nécessaire pour le calcul du couplage sur ces catégories de courbes. Nous supposons que toutes les opérations : la multiplication, le carré, l’inversion et l’addition sur Fp sont déjà implémentées.

Partie difficile de l’exponentiation finale

Une fois calculée la première partie de l’exponentiaton finale, f pk􀀀1 _k(p) 1 , dite partie facile, il reste à évaluer ce résultat à la puissance _k(p) r . Cette deuxième étape de calcul est dite la partie difficile de l’exponentiation finale vu qu’elle est coûteuse. Soit f le résultat de f pk􀀀1 _k(p) 1 . Le calcul de f _k(p) r peut se faire de différentes manières possibles. Les premières méthodes apparues sont les algorithmes des exponentiations rapides. Dans ce contexte, nous citons deux algorithmes. Le premier est dit square and multiply. C’est une méthode classique de calcul apparue il y a plus de 2000 ans. Nous traitons cette méthode en détail dans le Chapitre 3. Le deuxième algorithme de multi-exponentiations est celui de la fenêtre glissante. C’est une optimisationde l’algorithme square and multiply. La méthode des suites de Lucas est une alternative remarquable à ces deux algorithmes. L’idée est d’effectuer les opérations dans le corps intermédiaire Fpk=2 au lieu de Fpk . Ceci est un avantage important puisque l’arithmétique y sera bien plus simple. La meilleure méthode à ce jour pour le calcul de la partie difficile de l’exponentiation finale est celle proposée par Scott et al. dans [Sco05]. Le principe de cette méthode est de développer la partie difficile de l’exponentiation finale en base p, c’est-à-dire : _k(p) r = ‘(Xk)􀀀1 i=0 _i _ pi; avec ‘(k) est l’indicatrice d’Euler de k (et donc le degré de _k). Ce développement permet de calculer la partie difficile de l’exponentiation finale d’une manière plus simple, (voir Chapitre 3), car il fait intervenir des exposants qui sont des puissances de p, c’est à dire des Frobenius, dont nous allons maintenant étudier la complexité. Nous reprendrons en détail l’étude de l’exponentiation finale dans le chapitre suivant où nous détaillerons toutes les méthodes permettant le calcul de la partie coûteuse de l’exponentiation finale ainsi que leurs complexités.