FR 2796177 A1 20010112 FR 9908949 A 19990709 "Procédé de cryptographie mis en oeuvre entre deux entités échangeant des informations" L'invention se rapporte à un procédé de cryptographie mis en oeuvre entre deux entités échangeant des informations à travers un canal de communication non sécurisé, par exemple un réseau câblé ou hertzien et permettant d'assurer la confidentialité et l'intégrité des transferts d'informations entre ces deux entités. L'invention concerne plus particulièrement un perfectionnement aux cryptosystèmes mettant en oeuvre des calculs sur une courbe elliptique. Le perfectionnement permet principalement de réduire les temps de calcul. On connaît un protocole de cryptographie, plus particulièrement utilisé pour réaliser un échange de clefs sécurisé entre deux entités. II est connu sous l'appellation "Echange de Clefs de Diffie-Hellmann" ou "ECDH". Sa mise en oeuvre nécessite l'utilisation d"un groupe au sens mathématique du terme. Une courbe elliptique du type Y2 +xY = x3 + #X 2+p peut constituer un groupe utilisable dans un tel procédé ; On sait que si P= (x,y) appartient à la courbe elliptique E, on peut définir un "produit" ou "multiplication scalaire " du point P de E par un entier m. Cette opération est définie comme suit [m]P=P+P+P....+P(mfois) On sait que dans un algorithme du type "ECDH", on utilise la multiplication par 2 d'un point P choisi d'une telle courbe elliptique. Cette opération s'appelle "doublement de point" et s'inscrit dans un processus itératif de doublement-et- addition. Une telle multiplication par 2 requiert du temps. La partie la plus lente du protocole d'Echange de Clés de Diffie-Hellman (ECDH) est la multiplication d'un point de la courbe non connu à l'avance par un scalaire aléatoire. On ne considère ici que les courbes elliptiques définies sur un corps de caractéristique 2 ; c'est un choix répandu pour les implémentations, car l'addition dans un tel corps correspond à l'opération "'ou exclusif'. II est connu que la multiplication par un scalaire peut être accélérée pour les courbes définies sur un corps de faible cardinalité en utilisant le morphisme de Frobenius. On peut choisir les courbes de sorte qu'aucune des attaques connues ne s'applique à elles. Cependant, il est évidemment préférable, au moins sur le plan du principe, de pouvoir choisir la courbe que l'on veut utiliser dans une classe de courbes aussi générale que possible. La méthode décrite dans l'invention s'applique, dans sa version la plus rapide, à la moitié des courbes elliptiques. De plus, d'un point de vue cryptographique, cette moitié est la meilleure. Avant de donner le principe de la méthode, on rappelle les concepts de base. Soit n un entier donné, FZ" le corps de 2" éléments, et FZ" sa clôture algébrique. Soit O le point à l'infini. On appelle courbe elliptique E non supersingulière définie sur Fz, l'ensemble E = {(x,Y)E FZ" X F2" IY2 + xY = x3 + axe +P} u {O} a, a E F2", P#0 Les éléments de E sont habituellement appelés "points". II est bien connu que E peut être doté d'une structure de groupe abélien en prenant le point à l'infini comme élément neutre. Dans ce qui suit, on considère le sous-groupe fini des points rationnels de E, défini par E( Fz" ) = {(x,Y) E FZ" X F " (y2 + xY = x3 + axe + P) u {O} a, P E F2 , P#0 N étant l'ensemble des entiers naturels, pour tout m E N, on définit dans E l'application "multiplication par m" par [m] : E -->E P ->P + ....... + P (m fois) et b'P EE :[0]P=0 On note E[m] le noyau de cette application. Les points du groupe E[m] sont appelés les points de m-torsion de E. La structure de groupe des points de m-torsion est bien connue. En se limitant au cas où m est une puissance de 2, on a Vk E N:E[2k]-Z/2kZ où Z est l'ensemble des entiers relatifs. Comme E(Fz" ) est un sous-groupe fini de E, il existe k' >_ 1 tel que E [2 k] est contenu dans E(FZ" ) si et seulement si k _ On est maintenant en mesure d'expliquer le but de l'invention. La multiplication par deux, n'est pas injective lorsqu'elle est définie sur E ou E(FZ" ), car elle a pour noyau : E[2] = { O, T2}. Par ailleurs, si on réduit le domaine de définition de la multiplication par 2 à un sous-groupe d'ordre impair G c E(Fz" ), la multiplication par 2 devient bijective. II en résulte que la multiplication par 2 admet sur ce sous-groupe une application inverse que nous appellerons division par 2 [1/2]: G- >G P-> Q tel que: [2]Q=P On note [1l2] P le point de G auquel l'application de doublement fait correspondre le point P. Pour tout k>_ 1, on écrit Pour représenter k compositions de l'application de division par 2 avec elle-même. De façon générale l'invention concerne donc un procédé de cryptographie mis en oeuvre entre deux entités échangeant des informations à travers un canal de communication non sécurisé, du type comprenant au moins une phase opératoire consistant à multiplier un point d'ordre impair d'une courbe elliptique non supersingulière par un entier, caractérisé en ce qu'une telle phase opératoire comprend des additions et des divisions par deux de points de ladite courbe elliptique; où l'addition de points est une opération connue, et la division par deux d'un point P est définie comme le point unique D d'ordre impair tel que [2]D=P, un tel point étant noté P, et l'opération de division par 2 L'application de division par 2 est intéressante pour la multiplication scalaire d'un point d'une courbe elliptique pour la raison suivante : si l'on travaille en coordonnées affines, il est possible de remplacer toutes les multiplications de point par 2 d'une multiplication scalaire par des divisions de point par 2. La division par 2 d'un point est bien plus rapide à calculer que sa multiplication par 2. D'un point de vue cryptographique, il est bon d'avoir à choisir parmi le plus grand nombre de courbes possible, et on a coutume d'utiliser une courbe pour laquelle la 2-torsion de E(FZ" ) est minimale ou isomorphique à Zl4Z. Pour un corps Fz" donné, les courbes elliptiques de 2-torsion minimale constituent exactement la moitié de l'ensemble des courbes elliptiques définies sur F2,,. C'est pourquoi, bien qu'elle ne soit pas totalement générale, la méthode décrite s'applique, dans sa version la plus rapide, à une bonne partie des courbes intéressantes en cryptographie. Elle est toujours applicable dans le cas où les éléments du corps sont représentés dans une base normale. Dans le cas d'une base polynomiale, l'espace mémoire requis est de l'ordre de 0(n2) bits. On va montrer comment calculer [1I2] P E G à partir de P E G. Puis on montrera comment remplacer les doublements de points par des divisions par 2 pour exécuter une multiplication par un scalaire. On utilisera la représentation affine habituelle d'un point : P=(x,y) et la représentation : (x, a,p ) avec k, =x+y I x On tire de la deuxième représentation y = x (x + a,p ) qui n'utilise qu'une multiplication. En procédant ainsi, pour multiplier un point par un scalaire, on économise les multiplications en calculant les résultats intermédiaires à l'aide de la représentation (x, a,p ) et on ne détermine la coordonnée de la représentation affine qu'en fin de calcul. La division par deux d'un point P s'obtient de la façon suivante Soit à calculer [1I2] P à partir de P. On considère pour cela les deux points de E: P=(x,Y)=(x,x(x+ xp)) et Q = (u,v) = (u, u (u + a, Q)) tels que : [2]Q= P Les formules de multiplication par 2 connues donnent ÂQ=u+vlu (1) x=ÂQ2+ÂQ+a (2) y=(x+u) AQ+X+V (3) Multipliant (1) par u et reportant la valeur de v ainsi obtenue dans (3), ce système devient v=u(u+À Q) /, Q2+Â Q=a,+x y=(x+u)@Q+x+u2+uÂQ=u2+x(ÂQ+1) ou, puisque y = x ( x + x,p ) @ Q2 +Â Q=a+x u2=(x(A Q+1)+y=(@ Q+ #, p+x+1) (ii) v = u (u + Â. Q) En partant de P = (x,y) = (x, x (x + a,p )) en coordonnées affines ou en représentation (x, #,p), ce système d'équations détermine les deux points [1I2] P EG et [1[I2] P+T2E E(F2@)1G qui donnent P par multiplication par 2. La propriété qui suit permet de la distinguer. Soit E une courbe elliptique à 2-torsion minimale, et P E E(FZ" ) = G x {O, T2} l'un de ses éléments d'ordre impair. Soit Q E{[112] P, [1I2] P+ T2} et QI l'un des deux points de E tels que [2]Qj= Q. On a la condition nécessaire et suffisante Q + [1/2]P QI E E(F2" ) (a) On en déduit qu'il est possible de tester si Q = [1l2] P en appliquant les formules (i), (ii) et (iii) à Q et en vérifiant si l'un de points obtenus appartient à E(F2" ). Ce procédé peut être étendu à une courbe elliptique arbitraire E (F2n ) = G x E [2 k]. Pour cela on applique k fois les formules (i), (ii) et (iii) : la 1e"9 fois à Q, pour obtenir QI, tel que [2] QI = Q; la ième fois à Q ;_j pour obtenir un point Q;, tel que [2] Q; = Q ;_1. Le point résultat Qk sera de la forme P+TZ, si et seulement si Q = [1/2]P + T2 et il sera de la forme P +T2; avec 0 _ La relation (a) montre que l'on peut savoir si Q = [1/2]P ou Q = [1/2]P + T2 en regardant si les coordonnées de QI, appartiennent à F2" ou à un sur-corps de FZ" . Comme QI est déterminé par les équations (i), (ii) et (iii), nous avons à étudier les opérations utilisées dans la résolution de ces équations qui ne sont pas internes au corps, mais ont leur résultat dans un sur-corps de FZ" . Le seul cas possible est celui de la résolution de l'équation du 2"d. degré (i) : on doit aussi calculer une racine carrée pour calculer la 1e'e coordonnée de QI, mais en caractéristique 2 la racine carrée est une opération interne au corps. On a donc Q=(u,v) =[1/2]P 3Â E F2" :Â2+A=a+u Cette condition nécessaire et suffisante s'écrit aussi, puisque la racine carrée est interne au corps Q = (u, v) = [1/2] P 3Â E F2" : #Z 2 + /. = a2 + u2 La relation précédente permet d'optimiser l'algorithme énoncé ci-dessous dans les cas où le temps de calcul de la racine carrée n'est pas négligeable. Pour P E G, les 2 solutions de (i) sont Â [1,2]p et Â, [1/21p + 1, et on déduit de (ii) que les 1ères coordonnées des points associés sont u et (u + #x_). On peut donc en déduire un algorithme permettant de calculer [112]P de la façon suivante Si F2" est un corps fini de 2n éléments, E (F " ) est le sous-groupe d'une courbe elliptique E, défini par E(F2., ) = @(x,y) E F2" X F2" 1y2 + xy = x3 + axe + @} U {O} aI@ E F2" O et E[21] est l'ensemble des points P de ladite courbe elliptique tels que P, additionné 2 1 fois à lui même donne l'élément neutre O avec k entier supérieur ou égal à 1, alors, un point P = (x,y) de ladite courbe elliptique donne par ladite division par deux le point P= (uo, vo) de ladite courbe elliptique, obtenu en effectuant les opérations suivantes # on cherche une première valeur Â,, telle que X^2 +#=#+X # on calcule une seconde valeur uô telle que uô = x (X^ + 1) + y # si k vaut 1, on cherche si l'équation : Â. 2+Â =a2 + Uô a des solutions dans F Z" # dans l'affirmative on calcule ladite division par deux par vo = Uo (U0 + Io) et # dans la négative, on ajoute x à ladite deuxième valeur uo2 et on ajoute 1 à ladite première valeur Xo pour calculer ladite division par deux comme dans l'opération précédente; # si k est plus grand que 1, on effectue un calcul itératif consistant à chercher une valeur. i, telle queÂ i 2 + @,i = a + ui-J puis calculer la valeur u2; telle que U2i = u;_, (@,i + + ui-1 +1) en incrémentant i à partir de i=1 jusqu'à obtenir la valeur u k_ 1 2 # on cherche si l'équation @,2 + X = a2 + u2 k-, a des solutions dans FZ# dans l'affirmative on calcule ladite division par deux par vo =Uo(Uo+@o) et # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur a., pour calculer ladite division par deux comme dans l'opération précédente. Si on choisit de représenter le point = (u., vo) de la courbe elliptique par (uo,,Io) avec @,o = uo + vo lu, alors l'algorithme devient # on cherche une première valeur X,, telle que 2 + #,o = a + x # on calcule une seconde valeur uô telle que : uô = x (%,o+ 1)+ y, # si k vaut 1, on cherche si l'équation : 2,2o +X, =a' +u'o a des solutions dans F Z" , # dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur uo2 et on ajoute 1 à ladite première valeur a,, pour calculer ladite division par deux comme dans l'opération précédente, # si k est plus grand que 1, on effectue un calcul itératif consistant à chercher une valeur,; , telle que Â.; 2 + 1; = a + u;_1 puis calculer la valeur u;2 telle que u? = u;_1 (a,; + 1;_1 + u;-1 +1) en incrémentant i à partir de i = 1 jusqu'à obtenir la valeur u2 k_1 # on cherche si l'équation ;,2 + 1. = a2 + U2 k-, a des solutions dans F Z" # dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur @,o pour calculer ladite division par deux comme dans l'opération précédente. Si on choisit de représenter le point P = (x,y) par ( x, # p) en posant Â, p = x+ylx qui donne par ladite division par deux le point = (uo,vo) de ladite courbe elliptique alors l'algorithme devient # on cherche une première valeur À o telle que 1^2 +#=#+X # on calcule une seconde valeur uô telle que uô = x (1o + Ip + x + 1) # si k vaut 1, on cherche si l'équation : A 2+#Z =a2+uô a des solutions dans F Z" # dans l'affirmative on calcule ladite division par deux par vo=uo(uo+lo) et # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur a,, pour calculer ladite division par deux comme dans l'opération précédente; # si k est plus grand que 1, on effectue un calcul itératif consistant à chercher une valeur,; , telle queÂ; 2 + 1; = a + u;_, puis calculer la valeur u2; telle que u2; = u;_, (k,; + 1;_1 + u;_, +1) en incrémentant i à partir de i=1 jusqu'à obtenir la valeur u2 k_1 # on cherche si l'équation X2 + @. = a2 + u2 k_, a des solutions dans F z" # dans l'affirmative on calcule ladite division par deux par vo = u, (u. + ;.o) et = (u., vo) # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur k, pour calculer ladite division par deux comme dans l'opération précédente. Enfin, si on choisit de représenter le point P= (x,y) par (x, ;,p) avec Xp = x + ylx qui donne par ladite division par deux le point = (uo, vo) de la courbe elliptique représenté par (u,, 10) avec 1, = u, + voluo alors l'algorithme devient # on cherche une première valeur Â o telle que @ 2 +,^=#+X # on calcule une seconde valeur uâ telle que uâ = x (@ +@,p + x + 1), # si k vaut 1, on cherche si l'équation : Â 2+Â =a2+uô a des solutions dans F" , # dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur u,2 et on ajoute 1 à ladite première valeur @.o pour calculer ladite division par deux comme dans l'opération précédente ; # si k est plus grand que 1, on effectue un calcul itératif consistant à chercher une valeur, i, telle queÂ i 2 + j,; = a + ui_l puis calculer la valeur u2; telle que u ; 2 = ui_l (@,i + @,i-1 + ui-1 +1) en incrémentant i à partir de i=1 jusqu'à obtenir la valeur u2 k_ 1 # on cherche si l'équation X2 + X = a2 + u2 k_, a des solutions dans F z" # dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur Xo pour calculer ladite division par deux comme dans l'opération précédente. On va maintenant décrire comment effectuer rapidement le test, la résolution de l'équation du second degré, et le calcul de la racine carrée dans l'algorithme de division d'un point par 2. On considérera les deux cas en base normale et polynomiale. Les résultats en base normale sont connus. On peut considérer F2" comme espace vectoriel à n dimensions sur F2. Dans une base normale, un élément du corps est représenté par x; E #0,1j où PEF2" est choisi tel que : #,P 2 ,...,#2"-1 } est une base F2,. Dans une base normale, la racine carrée se calcule par un décalage circulaire gauche, et l'élévation au carré par un décalage circulaire droit. Les temps de calcul correspondants sont donc négligeables. Si l'équation du second degré : @@2 + x a ses solutions dans F2" , une solution est alors donnée par Le temps de calcul de À est négligeable devant le temps de calcul d'une multiplication ou d'une inversion dans le corps. Comme le temps de calcul d'une solution de l'équation du second degré est négligeable, on peut effectuer le test de la manière suivante : calculer un candidat Â. à partir de x et tester si À2 + À x. Si ce n'est pas le cas, l'équation n'a pas de solution dans F2 En base polynomiale, on utilise la représentation avec x; e{0,1}. La racine carrée de x peut être calculée en stockant l'élément #-T si l'on remarque que - dans un corps de caractéristique 2, la racine carrée est un morphisme du corps, Regroupant dans x les puissances paires et impaires de T et prenant la racine carrée, il vient ainsi, pour calculer une racine carrée, il suffit de "réduire" deux vecteurs de moitié, et d'exécuter ensuite une multiplication d'une valeur précalculée par un élément de longueur n12. C'est pourquoi le temps de calcul d'une racine carrée dans une base polynomiale est équivalent à la moitié du temps de calcul d'une multiplication dans le corps. Pour le test et la résolution de l'équation du second degré, considérons FZ" comme un espace vectoriel à n dimensions sur F2 . L'application F définie par: F : F2. .@ F2. @2+@, est alors un opérateur linéaire de noyau {0, 1} Pour un x donné, l'équation: ##2 + 1 = x a ses solutions dans F2. si et seulement si le vecteur x est dans l'image de F. Im(F) est un sous-espace de F2. à n -1 dimensions. Pour une base donnée de F2,,, et le produit scalaire correspondant, il existe un seul vecteur non trivial orthogonal à tous les vecteurs de Im(F). Soit w ce vecteur. On a D,, E F2n: @@2+x G> x.w=0 Ainsi l'exécution du test peut se faire en additionnant les composantes de x auxquelles correspondent des composantes de w égales à 1. Le temps d'exécution de ce test est négligeable. Pour la résolution de l'équation du 2"d .degré : F(X) _ @,2 + 2,, = x dans une base polynomiale, on propose une méthode simple et directe imposant le stockage d'une matrice n x n. Pour cela, on cherche un opérateur linéaire G tel que b'x E Im(F) :F(G(x))=(G(x))2 +G(x)=x Soit Y E F2" un vecteur tel que Y eIm(F) et définissons G par: Etant donné Im(F) alors G(x) est solution de l'équation du 2"d degré. Une implémentation consiste à précalculer la matrice représentant G dans la base {1,T,........., T"-i}. En caractéristique 2, la multiplication d'une matrice par un vecteur se réduit à l'addition des colonnes de la matrice auxquelles correspondent un composante du vecteur égale à 1. II s'ensuit que cette méthode de résolution d'une équation du tnd degré consomme en moyenne n12 additions dans le corps FZ" . On décrit ci-dessous l'application des principes exposés à la multiplication scalaire Soient P E E (F ") un point d'ordre r impair, c un entier aléatoire et m la partie entière de 1092 (r). Calculons le produit [c]P d'un point par un scalaire en utilisant l'application de division d'un point par 2. On démontre que Pour tout entier c; il existe un nombre rationnel de la forme tel que Soit le groupe cyclique généré par P. Comme on a l'isomorphisme d'anneaux: P ZIrZ [k]P k On peut calculer la multiplication scalaire par: en utilisant des divisions par 2 et des additions. L'algorithme bien connu de doublement-addition peut être utilisé pour ces calculs. II suffit pour cela de remplacer dans l'algorithme les doublements par des divisions par 2. II faut exécuter 1092 (r) divisions par 2 et, en moyenne, 1I2 1092 (r) additions. II existe des améliorations à l'algorithme de doublement-addition qui ne demandent que 1I3 1092 (r) additions en moyenne. Par conséquent une multiplication scalaire précitée utilisant une division par deux telle que définie ci-dessus est obtenue par les opérations suivantes - si ledit scalaire de la multiplication est noté S, on choisit m+1 valeurs So... Sm E Q0,1} pour définir S par - r étant l'ordre impair précité et m étant l'entier unique compris entre 1092(r) -1 et 1092(r), - on calcule la multiplication scalaire [S]P d'un point P de ladite courbe elliptique par le scalaire S par application d'un algorithme consistant à déterminer la suite de points (Qn,+1, Qrn..., Q;..., Qo) de ladite courbe elliptique E telle que QM+1 = O (élément neutre) QI=[SI]P+ Qi+1avec o5i Pour additionner le point P initial à un résultat intermédiaire Q;, on utilise l'algorithme suivant, qui est l'algorithme traditionnel, légèrement modifié: Entrée: P = (x,y) en coordonnées affines et Q = (u, u(u + 2.Q )) représenté par (u, XQ) Sortie: P + Q = (s, t) en coordonnées affines algorithme: 1. Calculer: 2. Calculer: s=@,Z+1+a+x+u 3. Calculer: t=(s+x)X+s+y 4. Résultat: (s, t) Cet algorithme utilise 1 inversion, 3 multiplications, et 1 racine carrée. Le gain de temps obtenu en remplaçant les opérations de multiplication par 2 par des divisions par 2 est important. En coordonnées affines, la multiplication par 2 et l'addition demandent toutes deux: une inversion, deux multiplications, et une racine carrée. Si le scalaire de la multiplication par un scalaire est représenté par un vecteur de bits de longueur m et de k composantes non nulles, les opérations pour la multiplication scalaire demandent opération doublement et addition Division par 2 et addition inversions m + k k multiplications 2m + 2k m + 3k carrés m + k k résolution a,`+a,=a+x 0 m racines carrées 0 m tests 0 m Ainsi, en utilisant la division par 2, on économise m inversions, m-k multiplications, et m carrés, au prix de m résolutions du 2"d.degré, m racines carrées et m tests. En base polynomiale, on peut obtenir une amélioration en temps d'exécution voisine de 50%. En base normale, on estime le temps de calcul de la racine carrée, du test et de la résolution d'équation du 2"d. degré négligeable devant le temps de calcul d'une multiplication ou d'une inversion. En supposant en outre que le temps de calcul d'une inversion est équivalent au temps de calcul de 3 multiplications, on arrive à une amélioration du temps d'exécution de 55%. La figure unique illustre schématiquement une application possible des algorithmes décrits ci-dessus, mis en oeuvre entre deux entités A et B échangeant des informations à travers un canal de communication non sécurisé. En l'occurrence, ici l'entité A est une carte à microcircuit et l'entité B est une serveur distant. Une fois mis en relation l'une avec l'autre par ledit canal de communication, les deux entités vont appliquer un protocole de construction d'une clef commune. Pour ce faire - l'entité A possède une clef secrète a - l'entité B possède une clef secrète b Elles doivent élaborer une clef secrète x connue d'elles seules, à partir d'une clef publique constituée par un point P d'ordre impair r d'une courbe elliptique E choisie et non supersingulière. Le protocole mis en ceuvre est du type de Diffie-Hellman en remplaçant les "multiplications par deux " habituelles dites doublements de point par l'opération dite de "division par deux", selon l'invention décrite ci-dessus. Pour ce faire, l'algorithme est le suivant - la première entité (par exemple A) calcule la multiplication scalaire [a]P et envoie le point résultat à la seconde entité, - la seconde entité (B) calcule la multiplication scalaire [b]P et envoie le point résultat à la première entité, - les deux entités calculent respectivement un point commun (C) = (x,y) de ladite courbe elliptique (E) en effectuant respectivement les multiplications scalaires [a] ([b]P) et [b] ([a]P), toutes deux égales à [a.b]P, - les deux entités choisissent comme clef commune la coordonnée x dudit point commun (C) obtenu par ladite multiplication scalaire [a.b]P, au moins l'une des multiplications scalaires précédentes, et de préférence toutes, étant effectuée à l'aide de divisions par deux prédéfinies. Une autre application possible mettant en jeu l'invention est susceptible d'être mise en oeuvre entre deux entités A et B. II s'agit d'un protocole de signature d'un message M transmis entre A et B via un canal non sécurisé. Le but de ce protocole, connu dans ses grandes lignes, est d'apporter la certitude que le message reçu par l'une des entités a bien été émis par celle avec laquelle elle correspond. Pour ce faire, l'entité émettrice (par exemple A) possède deux clefs permanentes, l'une secrète et l'autre publique. Une autre clef publique est constituée par un point P d'ordre impair r d'une courbe elliptique E choisie, non supersingulière. Les opérations mises en jeu impliquent des divisions par deux, au sens défini ci-dessus. Selon un exemple possible - la première entité (A) possédant ladite paire de clefs permanentes construit une paire de clefs à utilisation unique, l'une (g) étant choisie arbitrairement et l'autre, [g] P résultant d'une multiplication scalaire de ladite clef (g) choisie arbitrairement par le point P public de ladite courbe elliptique, les coordonnées de cette clef ([g]P) étant notées (x,y) avec 2 g sinon, considérant le point T de coordonnées x' et y' : T = (x',y'), - ladite seconde entité (B) convertit le polynôme x' de ce point en un entier i' dont la valeur binaire est représentée par la séquence des coefficients binaires dudit polynôme x', - ladite seconde entité (B) calcule c' = i' modulo r et, - vérifie que c' = c pour valider ladite signature ou l'invalider dans le cas contraire, au moins une opération de multiplication scalaire précitée et, de préférence toutes, étant effectuée à l'aide de divisions par deux prédéfinies. REVENDICATIONS 1. Procédé de cryptographie mis en oeuvre entre deux entités échangeant des informations à travers un canal de communication non sécurisé, du type comprenant au moins une phase opératoire consistant à multiplier un point d'ordre impair d'une courbe elliptique non supersingulière par un entier, caractérisé en ce que, dans le but de réaliser l'échange d'informations à travers le canal de communication non sécurisé, une telle phase opératoire comprend des additions et des divisions par deux de points de ladite courbe elliptique où l'addition de points est une opération connue, et la division par deux d'un point P est définie comme le point unique D d'ordre impair tel que [2]D = P, un tel point étant noté P, et l'opération de division par 2 2. Procédé selon la revendication 1, où F " est un corps fini de 2" éléments, E(F2" ) est le sous-groupe d'une courbe elliptique E, défini par E(F2 ) = {(x,y)E F2 X F2" 1y2 + xy = x3 + (,x2 + [3} U {O) a, [3 E F2 , [i # 0 et E [2k] est l'ensemble des points P de ladite courbe elliptique tels que P, additionné 2 k fois à lui-même donne l'élément neutre O, avec k entier supérieur ou égal à 1, caractérisé en ce qu'un point P =(x,y) de ladite courbe elliptique donne par ladite division par deux le point de ladite courbe elliptique, obtenu en effectuant les opérations suivantes # on cherche une première valeur Â o telle que @ 2 + @,o = a + x # on calcule une seconde valeur u,2 telle que uô = x (#0 + 1) + y # si k vaut 1, on cherche si l'équation : @.2 +Â =a2 +u2, a des solutions dans F2n, # dans l'affirmative on calcule ladite division par deux par Vo =uo(uo+%,o) et # dans la négative, on ajoute x à ladite deuxième valeur u02 et on ajoute 1 à ladite première valeur X,o pour calculer ladite division par deux comme dans l'opération précédente; # si k est plus grand que 1, on effectue un calcul itératif consistant à chercher une valeur. i , telle que À i 2 + X; = a + U;_l puis calculer la valeur u2i telle que U2; = U;_, (1i + 1;_1 + u;_J +1) en incrémentant i à partir de i = 1 jusqu'à obtenir la valeur U2 k_ 1 # on cherche si l'équation k2 + X = a2 + U2 k_, a des solutions dans F2" # dans l'affirmative on calcule ladite division par deux par Vo = Uo (Uo + Xo) et # dans la négative, on ajoute x à ladite deuxième valeur u02 et on ajoute 1 à ladite première valeur Xo pour calculer ladite division par deux comme dans l'opération précédente. 3. Procédé selon la revendication 1 où : F2 est un corps fini de 2" éléments, E(F2" )est le sous-groupe d'une courbe elliptique E, défini par E(F2") = {(x,Y)E F2" X F2 IY2 + xY = x3 + axe + P},-) {01 a, p E F2", a # 0 et E[2k] est l'ensemble des points P de ladite courbe elliptique tels que P, additionné 2k fois à lui même donne l'élément neutre O, avec k entier supérieur ou égal à 1, caractérisé en ce qu'un point P = (x,y) de ladite courbe elliptique donne par ladite division par deux le point = (U., Xo) avec 1, = Uo + vOluo obtenu en effectuant les opérations suivantes # on cherche une première valeur X,o telle que X^2 + jo = a + x # on calcule une seconde valeur u02 telle que : u02 = x (j^ + 1) + y # si k vaut 1, on cherche si l'équation : X, 2 +#j =a2 +U02 a des solutions dans 172% # dans l'affirmative on calcule ladite division par deux par et # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur pour calculer ladite division par deux comme dans l'opération précédente ; # si k est plus grand que 1, on effectue un calcul itératif consistant à chercher une valeur.; , telle que Â; 2 + l; = a + u;_J puis calculer la valeur u;2 telle que u;2 = u;_1 (@,; + + u+1) en incrémentant i à partir de i = 1 jusqu'à obtenir la valeur u2 k_1 # on cherche si l'équation @,2 + @, = a2 + u2 M a des solutions dans F2" # dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur X.o pour calculer ladite division par deux comme dans l'opération précédente. 4. Procédé selon la revendication 1 où F2n est un corps fini de 2" éléments, E(F2n) est le sous-groupe d'une courbe elliptique E, défini par E(F2") = @(x,Y) E F2" X F2" JY2 + xY = x3 + axe + P} u {O} a, (3 E F2", (3 # 0 et E [2k] est l'ensemble des points P de ladite courbe elliptique tels que P, additionné 2k fois à lui même donne l'élément neutre O avec k entier supérieur ou égal à 1, caractérisé en ce qu'un point P = (x,y) de ladite courbe elliptique représenté par (x,kp) avec a,p = x + ylx donne par ladite division par deux le point de ladite courbe elliptique obtenu en effectuant les opérations suivantes # on cherche une première valeur 1. telle que X 2 + j^ = a + x # on calcule une seconde valeur uô telle que : uô = x (@o + Ip + x +1), # si k vaut 1, on cherche si l'équation : Â 2+#Z =a2+uo2 a des solutions dans F n 2 , # dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur pour calculer ladite division par deux comme dans l'opération précédente ; # si k est plus grand que 1, on effectue un calcul itératif consistant à chercher une valeur.; , telle queA;2 + ;,; = a + u;_, puis calculer la valeur u;2 telle que u;2 = u;_, (1,; + X,;_, + u;_, +1) en incrémentant i à partir de i =1 jusqu'à obtenir la valeur u2 k_ 1 # on cherche si l'équation X,2 + X = (X2 + U2 k-, a des solutions dans F2 dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur a,, pour calculer ladite division par deux comme dans l'opération précédente. 5. Procédé selon la revendication 1 où : F2^ est un corps fini de 2" éléments, E(F2 ) est le sous-groupe d'une courbe elliptique E, défini par E(F2") = {(x,y) E F2" X F2" ly2 + xY = x3 + axe + a} U {0i a, a E F2", P # 0 et E[2k] est l'ensemble des points P de ladite courbe elliptique tels que P, additionné 2k fois à lui même donne l'élément neutre O, avec k entier supérieur ou égal à 1, caractérisé en ce qu'un point P = (x,y) de ladite courbe elliptique représenté par (x,kp) avec Ip = x + ylx donne par ladite division par deux le point de ladite courbe elliptique représenté par (uo, Xo), avec a,o = uo + v./u,, , obtenu en effectuant les opérations suivantes # on cherche une première valeur k, telle que #.,` + 1, = a + x # on calcule une seconde valeur uô telle que : uô = x (Xo + kp + x +1), # si k vaut 1, on cherche si l'équation : /. 2+Â, =a2+uô a des solutions dans F2@ # dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur 1o pour calculer ladite division par deux comme dans l'opération précédente; # si k est plus grand que 1, on effectue un calcul itératif consistant à chercher une valeur,; , telle que/1 ;2 + 7@; u;_, puis calculer la valeur u;2 telle que u;2 = u;_, (@,; + + u;_, +1) en incrémentant i à partir de i = 1 jusqu'à obtenir la valeur u2 k_ 1 # on cherche si l'équation X,2 + @, = a2 + U2 k-, a des solutions dans FZ" # dans l'affirmative on calcule ladite division par deux par # dans la négative, on ajoute x à ladite deuxième valeur uô et on ajoute 1 à ladite première valeur Xo pour calculer ladite division par deux comme dans l'opération précédente. 6. Procédé selon l'une des revendications précédentes, caractérisé en ce qu'il s'agit d'un protocole de construction d'une clef commune à partir de deux clefs secrètes appartenant respectivement aux deux entités précitées et d'une clef publique constituée par un point P d'ordre impair r d'une courbe elliptique E choisie et non supersingulière. 7. Procédé selon la revendication 6, caractérisé en ce que, de façon connue en soi, a et b étant les clefs secrètes d'une première et d'une seconde entités, respectivement - la première entité calcule la multiplication scalaire [a]P et envoie le point résultat à la seconde entité, - la seconde entité calcule la multiplication scalaire [b]P et envoie le point résultat à la première entité, - les deux entités calculent respectivement un point commun C = (x,y) de ladite courbe elliptique (E) en effectuant respectivement les multiplications scalaires [a] ([b]P) et [b] ([a]P), toutes deux égales à [a.b]P, - les deux entités choisissent comme clef commune la coordonnée (x) dudit point commun (C) obtenu par ladite multiplication scalaire [a.b]P, au moins l'une des multiplications scalaires précédentes, et de préférence toutes, étant effectuée à l'aide de divisions par deux prédéfinies. 8. Procédé selon l'une des revendications 1 à 5, caractérisé en ce qu'il s'agit d'un protocole de signature entre deux entités à partir d'une paire de clefs permanentes appartenant à l'une des entités, l'une secrète (a) et l'autre publique (Q), résultant de la multiplication scalaire de la clef secrète (a) par une autre clef publique constituée par un point (P) d'ordre impair r d'une courbe elliptique (E) choisie et non supersingulière. 9. Procédé selon la revendication 8, caractérisé par les opérations suivantes - la première entité (A) possédant ladite paire de clefs permanentes construit une paire de clefs à utilisation unique, l'une (g) étant choisie arbitrairement et l'autre [g]P résultant d'une multiplication scalaire de ladite clef (g) choisie arbitrairement par le point P public de ladite courbe elliptique, les coordonnées de cette clef ([g]P) étant notées (x,y) avec 2 r étant l'ordre impair précité et m étant l'entier unique compris entre 1092(r) -1 et 1092(r), on calcule la multiplication scalaire [S]P d'un point P de ladite courbe elliptique par le scalaire S par application d'un algorithme consistant à déterminer la suite de points (Qm+1, Qm..., Q;..., Qo) de ladite courbe elliptique E telle que Qm+1 = O (élément neutre) le calcul du dernier point Qo de ladite suite donnant le résultat [S] P de ladite multiplication scalaire.