≪ Petit ≫ multiplieur/inverseur (PISO) y en base normale dans GF(2m) 

Nous rappellerons tres brievement dans cette section la notion de courbes elliptiques, le lecteur interess par le sujet est invite a se referer au livre [20]. Une courbe elliptique E dans les reels est de nie comme un ensemble de points de l’espace (x; y) 2 R2 respectant une equation (de Weierstrass) du type : y2 = x3 + a x + b:

Si nous reecrivons l’equation precedente comme P (x; y) = y2 x3 a x b = 0, cet ensemble doit egalement posseder la propriet de lissite : il ne doit exister aucun point (x; y) de E tel que @P (x; y) = 0  et @P (x; y) = 0: @x@y

Cette exigence permet d’eviter l’existence de singularites ; points auxquels il est impos-sible de de nir une tangente a la courbe, ce dont nous aurons besoin pour speci er la loi de groupe sur E. Deux exemples d’ensembles sont donnes a la gure 2.1.

Nous munissons ces points d’une loi de groupe + et nous y rajoutons un point a l’in ni O, element neutre de l’operation +.

Pour e ectuer une multiplication scalaire sur les courbes elliptiques de nies sur un corps ni binaire, la methode du double-and-add ou ses nombreux derives sont les plus usites. Dans [45], une approche alternative a et suggeree, celle du halve-and-add. L’algorithme est sensiblement le m^eme, mais au lieu de doubler P (voir Algo. 9 ligne 3) a chaque tour de boucle, P est divise par deux. Cette division fait paradoxalement disparaitre l’in-version au niveau corps GF(2m) qu’il etait necessaire d’e ectuer lors d’un doublement de point (dans un systeme de coordonnees a nes). Nous reviendrons plus precisement sur l’algorithme de halve-and-add [45] dans le chapitre 4. Pour avoir une solution en partie protegee contre des attaques SPA, l’algorithme de Montgomery Algo. 5 est generalement prefer a l’algorithme double-and-add . Nous pou-vons aussi adapter l’algorithme de Montgomery a la methode de halving. L’echelle de Montgomery adaptee au halving necessite d’ailleurs que les points de la courbe elliptique E soient representes en coordonnees a nes. Il y a des lors, au cours d’une multiplication scalaire ECC davantage d’inversions que dans d’autres systemes de coordonnees (comme les coordonnees projectives [20, Sec. 3.2]). Dans le cadre d’une approche de Montgomery basee sur du halving, la base normale apporte de par ses carres faciles a calculer (ce sont des decalages circulaires) et de par un calcul de trace Tr simple un avantage non negligeable.

Il existe pour les extensions du corps ni binaire deux representations populaires : les bases normales et les bases polynomiales. En base normale, A 2 GF(2m) est represent comme Pm 1 ai 2i ou les coe cients ai appartiennent a GF(2) et est un element par- i=0 ticulier generateur du corps. Pour simpli er l’ecriture, nous utiliserons aussi la notation A = (a0; a1; : : : ; am 1) pour designer la representation vectorielle des coe cients de A. En base normale, mettre un element au carre revient a e ectuer un decalage circulaire vers la droite sur le vecteur de ses coe cients. Ainsi, si A = (a0; a1; : : : ; am 1) alors A2 = (am 1; a0; : : : ; am 2). Les racines carrees se calculent des lors en faisant egalement p un decalage, mais cette fois-ci vers la gauche : A = (a1; a2; : : : ; a0). La multiplication de deux elements entre eux est basee sur du calcul matriciel, comme nous allons le voir dans la session 3.2.3 suivante. Nous utiliserons dans le reste de ce chapitre ces bases qui nous apporteront, de par leurs carres faciles a realiser, un avantage clef.
En base polynomiale, A est represent comme Pm 1 a0i xi ou les coe cients a0i appar- i=0 tiennent a GF(2). Les additions et multiplications sont des operations polynomiales le tout modulo un polyn^ome irreductible f 2 GF(2)[x].
Il existe d’autres bases speci ques pour les corps nis binaires comme les bases de Dick-sons [47] ou bien encore, les bases duales [48].

Il y a deux methodes principales pour inverser un element dans GF(2m) : l’algorithme d’Euclide et l’utilisation du petit theoreme de Fermat. Jusqu’a maintenant, les implan-tations de l’inversion reposant sur l’algorithme d’Euclide [56] sont rarement utilisees en materiel. En e et, une telle strategie sous-entend dedier une partie du circuit a l’in-version, ce qui, si elle est une operation rare, n’a pas de sens. L’inversion basee sur le petit theoreme de Fermat n’est qu’une exponentiation et s’appuie sur le multiplieur deja present sur au sein du circuit (les multiplications sont nombreuses dans une systeme de chi rement ECC). Nous factorisons, en quelque sorte, le co^ut en silicium. Le petit theoreme de Fermat (FLT : Fermat’s Little Theorem) a rme que A2m 1 = 1 et en consequence que A 1 = A2m 2. Inverser un element consiste alors a calculer A2m 2, ce n’est donc qu’une exponentiation, une succession de multiplications. Pour ce faire, nous pourrions utiliser l’algorithme square-and-multiply (voir Algo. 11) mais il ne tiendrait pas compte de la speci cit de l’exposant 2m 2. Itoh et Tsujii ont propose en 1988 dans [57] une facon tres e cace d’aborder le probleme d’exponentiation. Ils notent que 2m 2 = (111 : : : 110)2 : la representation binaire de l’exposant est une succession de m 1 bits a 1 suivie d’un 0 (des poids forts vers les poids faibles). Dans une telle situation, un algorithme de type square-and-multiply appliquerait m 1 mises au carre et m 2 multiplications. Itoh et Tsujii reduisent cette complexit a O(log2(m 1)) multiplications. Leur approche exige toujours m 1 carres mais de par la nature de la base normale, ces operations sont quasiment gratuites et negligeables. L’exemple du tableau 3.3 permet de comprendre comment Itoh et Tsujii y sont parvenus : le poids de Hamming de l’exposant des Ti (produits temporaires) peut doubler d’une etape a l’autre, comme entre T2 = A(111)2 et T3 = A(111111)2 . Nous comprenons ainsi le caractere logarithmique de leur approche. Informellement, elle consiste a ajouter a l’exposant d’un Ti autant de 0 que souhaite en procedant a des carres consecutifs et a venir, en n, com-bler ces 0 avec des 1 en venant multiplier cette nouvelle quantite par un autre Tj. Il reste maintenant a savoir comment etablir cette suite de (Ti) construite pour obtenir en dernier lieu A 1 : cela repose sur la notion de cha^nes d’additions. Une cha^ne d’additions (U) est une suite nie d’additions ou tous les operandes sont choisis parmi des valeurs deja calculees. Mathematiquement, chaque terme Ui de la suite (U) est la somme de deux elements Uj et Uk avec j < i et k < i. Un exemple est donne dans le tableau 3.4 dans lequel nous voyons apparaitre une suite (V ). Cette suite (V ) dans laquelle chaque terme est compose d’un couple d’entier (ai; bi) est la suite associee a (U). Si Ui = Uj +Uk alors Vi = (j; k). La de nition d’une telle suite facilite la formalisation de l’algorithme d’Itoh-Tsujii. Nous souhaitons en n que le dernier terme Un de la cha^ne (U) soit egal a m 1. Notons k = A2k 1. La relation qui existe entre k et (U) est mise en exergue par les egalites suivantes : Ui = Uk+Uj = ( Uk ) 2Uj Uj = ( Uj ) 2Uk Uk (3.2) U2 n = m2 1=A 1 (3.3)
Autrement dit, nous pouvons atteindre Un par un enchainement de calculs de type Uk+Uj . L’algorithme d’Itoh-Tsujii est decrit dans Algo. 12. Plus la cha^ne d’additions (U) est courte, moins il y aura de multiplications dans l’exponentiation d’Itoh-Tsujii. Trouver une cha^ne courte dont le dernier terme Un vaut m 1 est un probleme reput di cile (voir par exemple [58, Section 4.6.3]).

Durant l’exponentiation d’Itoh-Tsujii, les produits intermediaires doivent subir des mises au carre successives. Cela implique de devoir decaler (circulairement) les operandes d’un un nombre de bits de nis par la cha^ne d’addition choisie par l’utilisateur. Par exemple, si nous reprenons la cha^ne d’addition de l’exemple 3.4 (c’est a dire U = (1; 2; 4; 5; 8; 13)), les decalages sont les suivants : 1; 3. Pour des cha^nes plus grandes, le nombre de decalages di erents a prendre en compte cro^t de facon logarithmique. Par exemple, pour m = 571, il est necessaire de considerer une dizaine de valeurs de decalage di erentes. Si nous sou-haitions implanter sur circuit un operateur e ectuant ces decalages en un cycle d’horloge, la surface requise explose. Par exemple, pour le corps GF(2571), une telle fonctionna-lite synthetisee sur Spartan 6 occupe 3425 LUTs tandis qu’a titre de comparaison un multiplieur de Massey-Omura complet ne requiert que 2246 LUTs. Nous remplacons ces unites de decalage par un bloc-memoire (BRAM). Plut^ot que stocker chaque bit du (ou des) produit(s) intermediaire(s) dans un (ou des) registre(s) de taille m, nous les dupliquons w fois dans un bloc memoire (BRAM) en nous appuyant sur le schema suivant : [p0; p1; : : : ; pw 1] sera stocke a l’adresse @ = 0, [p1; p2; : : : ; pw] a l’adresse @ = 1, [p2; p3; : : : ; pw+1], . . ., [pm 1; p0; : : : ; pw 2] a l’adresse @ = m 1. Les blocs-memoire (BRAMs) dans les FPGAs actuels sont assez gros pour supporter les m w bits requis pour une telle methode. Avec un bus de largeur w = 32 , 7456 bits sont requis pour m= 233 et 18272 bits pour m= 571. Dans un Spartan 6 (qui est un produit d’entree de gamme), des blocs de 18Kb sont disponibles. Ainsi, pour m= 571, nous en avons besoin de deux. Un exemple est donne dans la gure 3.5.
Le multiplieur de Massey-Omura est un operateur sequentiel qui produit a chaque cycle d’horloge un bit du produit. Nous utilisons un petit registre de w bits a n de stocker les w bits consecutifs ([pi; pi+1; : : : ; pi+w 1]). Le contenu de ce registre est envoy au bloc-memoire a chaque cycle d’horloge (il y a donc une latence de w cycles, le temps que ce registre tampon se remplisse). En consequence, le nombre de cycles d’horloge necessaires pour calculer chaque produit de la sequence d’exponentiation est de fait m + w.
Les mises au carre sont realisees en lisant les mots composants l’element permut a l’adresse (i + w) mod m pour 2 f0; 1; 2; : : : ; bm=wc]g, ou i est la valeur du decalage. Cette methode semble equivalente a une strategie plus na ve, qui consisterait a decaler de 1 bit autant de fois que necessaire (et en autant de cycles d’horloge) le registre en question. Cette strategie nous permettra cependant d’avoir un contr^ole plus aise a im-planter et une plus grande exibilit . Cette methode rentre aussi dans la philosophie selon laquelle le transfert de donnees entre unites fonctionnelles doit se faire sur des bus de tailles moderees.

Dans la sequence d’exponentiation d’Itoh-Tsujii, des termes multiplicatifs speci ques, que nous nommerons SMP (Speci c Multiplication Pattern), apparaissent regulierement : A2k A. Ce motif est lie a l’apparition de Ui = Uj + Uj dans la cha^ne d’addition consideree. Nous modi ons l’algorithme de Massey-Omura (et l’operateur induit) a n qu’il supporte a la fois des multiplications standards (A B) ainsi que des SMPs. Lorsque nous avons a calculer des SMPs, nous remarquons que ROL(A; i) M0 et M0 ROL(A; i)T apparaissent dans la suite des operations. Puisque ces deux valeurs sont egales (en fait, l’une est la transposee de l’autre), nous pourrions factoriser un produit matrice-vecteur a chaque iteration de l’algorithme. A chaque cycle d’horloge, nous evaluons V = M0 ROL(A; i)T et retournons (pi = ROL(A; k i) V; pi+k = ROL(A; i k) V ). Par exemple, si k = 1, l’algorithme retournera a chaque cycle d’horloge les couples de bits (pi; pi+1). Au cycle d’horloge 0, la methode renvoie (p0; p1), au cycle d’horloge 1, (p1; p2) ainsi de suite. Dans cette exemple, quasi pathologique, il faudra m 1 cycles d’horloge a n d’obtenir entierement le produit. Nous aurions pu nous attendre a reduire drastiquement le temps de calcul en produisant deux bits simultanement : nous aurions pu envisager un temps de calcul en m=2 cycles d’hor-loge. Cela dit, la redondance des sorties pourra ^etre minimisee gr^ace a l’astuce que nous presenterons dans la session suivante. Notez que la sortie s’e ectue toujours en serie (1 ou 2 bits a la fois) et qu’une telle particularite peut ^etre exploitee en lancant parallelement des calculs annexes bases sur les bits produits a chaque cycle d’horloge (comme present dans [55]).

Comme nous l’avons vu precedemment, lors du calcul d’un SMP, une redondance dans les bits de sorties appara^t. Dans l’exemple prealablement donne, ce niveau de redondance approche 2 : chacun des bits du produit est gener deux fois lors des m 1 cycles d’horloge necessaires (sauf pm 1 qui lui, n’est produit qu’une fois). Cette redondance est notamment liee a la constante de decalage dans l’algorithme de Massey-Omura. Jusqu’ici, a chaque cycle d’horloge, les registres A; B et P (voir Algo. 10) sont decales de 1 bit vers la gauche. Que se passerait-il si nous changions ce decalage ? Si nous reprenons l’exemple avec k = 1 et choisissons un decalage de 2, les sorties seraient (p0; p1) au cycle d’horloge 0, (p2; p3) au cycle d’horloge 1, (p4; p5) au cycle d’horloge 2, etc. Ainsi, en considerant une autre valeur de decalage, nous parvenons a reduire la redondance puisqu’ici, en m=2 (m pair) ou (m + 1)=2 (m impair) cycles d’horloge, tous les bits du produit ont et generes. Nous proposons ainsi de changer la constante de decalage de facon a reduire la redondance (et ainsi, le temps de calcul). Pour des raisons materielles, ce devra ^etre constant pour chacune des multiplications de la sequence d’Itoh-Tsujii. Il n’est possible de choisir un particulier pour une multiplication particuliere : cela engendrerait une complexit circuit que nous tentons d’eviter jusqu’alors. Aussi, nous avons ecrit un programme Python, qui a partir d’une cha^ne d’addition, teste l’ensemble des possibles et retourne celui qui minimise le temps de calcul (en terme de cycles d’horloge). Pour des raisons pratiques, nous avons choisi des cha^nes d’addition binaires (c’est a dire que chaque terme est calcule comme Ui = Ui 1 + Ui 1 ou Ui = Ui 1 + U0 avec U0 = 1) : implanter l’algorithme d’Itoh-Tsujii avec de telles cha^nes ne requiert que deux registres temporaires (qui sera ici notre BRAM pour Ui 1 et un registre speci que de taille m pour U0). Les cha^nes d’addition generees par la methode binaire ne sont pas toujours les plus courtes, mais en pratique et pour les corps du NIST [51], toutes nos chaines sont au pire un terme plus longues que les plus courtes trouvees sur [60].

Nous avons propose dans le chapitre precedent une unite combinant les operations d’in-version et de multiplication. Ici, nous tentons d’aller plus loin, en proposant une archi-tecture complete d’un crypto-processeur operant dans GF(2m) dont les elements seront representes en base normale. Nous nous interesserons aussi au calcul parallele qu’im-plique le halving. En e et, comme nous l’avons note auparavant, le halving permet de casser, en partie, l’aspect sequentiel du double-and-add habituel (ou l’echelle de Mont-gomery). Comme indique dans [46], nous avons la possibilite de lever cette dependance en lancant parallelement sur une partie de la clef un algorithme de type halve-and-add et sur l’autre morceau un algorithme de type double-and-add. Ce parallelisme devrait nous apporter une protection contre certaines attaques par canaux caches (au moins celles de type SPA) puisque seront lances deux calculs independants simultanement : c’est une facon de semer le trouble chez l’attaquant, les informations fuyantes devraient des lors se m^eler. Nous estimerons aussi la securit physique de notre crypto-processeur en mettant en uvre une attaque dite par templates. Par commodite, cette attaque a et menee sur des simulations plut^ot que sur un banc d’attaques reel.

Nous aurons dans ce chapitre besoin de quelques notions issues de l’arithmetique des corps nis, notamment concernant la trace Tr que nous avons abordee dans 3.2.3. Si nous reprenons les operations de doublement Q = P + P en coordonnees a nes (x; y) dans E(GF(2m)), courbe de nie par : y2 + x y = x3 + a x + b avec a; b 2 GF(2m); (4.1) nous avons les calculs suivants : = x + y=x u = 2 + + a v = x2 + u ( + 1),
avec Q = (u; v). Nous voulons maintenant trouver le point P tel que Q = 2 P . Nous nous assurons, tout d’abord, de son unicite et de son existence dans E(GF(2m)) en remarquant que, si un tel P existe, alors Q=2 = Q (2 1 mod NP ) ou NP est l’ordre de P dans le groupe E(GF(2m)). L’existence de (2 1 mod NP ) est reli au fait que 2 doit ^etre premier avec NP , c’est a dire que NP se doit d’^etre impair. Dans ce cas, le doublement du point P et la division de P est un automorphisme du groupe gener par ce m^eme point [20]. La premiere chose a faire pour trouver P est de resoudre, pour , l’equation : u = 2 + + a (4.2).