L'invention concerne un procédé cryptographique mis en oeuvre par un module de calcul sécurisé dans un système comprenant également un module de calcul non sécurisé mais disposant de ressources matérielles plus importantes. L'invention est notamment intéressante pour la mise en oeuvre de procédés cryptographiques dans une carte à puce associée à un lecteur, ou plus généralement dans tout module de calcul sécurisé (par exemple un module TMP pour "Trusted Module Platform) installé dans un PC non sécurisé mais disposant de ressources matérielles importantes, ou même dans un PC associé à un serveur distant.

Pour sécuriser des données secrètes, une carte est souvent amenée à mettre en oeuvre des protocoles cryptographiques complexes avant dé transmettre des données chiffrées au lecteur de carte, qui ne doit pas avoir accès aux données secrètes. A titre d'exemple, on peut citer le protocole de chiffrement basé sur l'identité, le protocole de chiffrement par clé publique avec recherche de mots clés, le protocole d'échange de clés entre trois utilisateurs, la signature courte, etc.

Si ces protocoles ont montré leur efficacité pour la protection de données, ils ont cependant l'inconvénient d'être particulièrement coûteux, en terme de ressources matérielles de calcul nécessaires à leur mise en oeuvre. En particulier, certaines opérations élémentaires utilisées dans ces protocoles sont particulièrement coûteuses comme par exemple les opérations d'inversion d'un nombre entier ou les opérations de couplage ("pairing" en anglais) sur courbes elliptiques. Une courbe elliptique est un ensemble de points ayant des caractéristiques communes et dont les coordonnées peuvent notamment être calculées à partir des coordonnées de certains points de la courbe, appelés points générateurs, par des opérations simples telles qu'une multiplication par un scalaire. Pour plus de détails sur les courbes elliptiques, on pourra se reporter notamment à la publication FR 2 828 779. La mise en oeuvre classique d'une opération de couplage de type C = <A, B> est détaillée notamment dans le document "Identity based encryption from the Weil pairing" D. Boneh et M. Franklin (http://crypto.stanford.edu/~dabo/abstracts/ibe.html) . Les points A, B que l'on cherche à coupler sont par exemple une clé, publique ou privée, et un message, à chiffrer ou à déchiffrer, dans le cadre d'un protocole de cryptographie à clés asymétriques.

Parce que certaines opérations sont coûteuses, les protocoles cryptographiques sont particulièrement difficiles à implémenter dans une carte à puce ou un module de calcul sécurisé car les temps de calcul deviennent prohibitifs, les ressources matérielles de la carte ou du module sécurisé étant nécessairement limitées de par leur taille réduite .

L'invention a pour but de remédier à cette difficulté, pour permettre l'utilisation de protocoles cryptographiques complexes et coûteux dans un module de calcul sécurisé.

Ce but est atteint avec un procédé cryptographique selon l'invention mis en oeuvre par un module de calcul sécurisé, et caractérisé en ce que, au cours du procédé, le module sécurisé sous-traite la réalisation d'un couplage f de deux points A, B d'une courbe elliptique, à un module de calcul non sécurisé disposant de ressources matérielles plus importantes, puis le module sécurisé vérifie l'exactitude du résultat fourni par le module non sécurisé.

Ainsi, l'idée essentielle de l'invention est de sous- traiter au module non sécurisé la réalisation des opérations les plus coûteuses sur les courbes elliptiques, tout en vérifiant que le résultat fourni par le module non sécurisé est exact.

Dans un même procédé, plusieurs opérations, éventuellement de types différents, peuvent ainsi être sous-traitées, au fur et à mesure du calcul. Le module non sécurisé disposant de moyens de calcul beaucoup plus importants que la carte, la mise en oeuvre des protocoles cryptographiques les plus complexes devient possible avec l'invention. Le module sécurisé quant à lui se limite à des opérations simples, demandant peu de ressources et donc rapides à mettre en oeuvre, comme par exemple des opérations d'adition, de multiplication, etc., comme on le verra mieux par la suite dans des exemples.

De préférence, et notamment si l'un au moins des points A, B étant un point secret, le module sécurisé : • masque le ou les points secrets par un ou des nombres aléatoires pour produire un ou des points secrets masqués, • sous-traite au module non sécurisé la réalisation du couplage f à partir du ou des points secrets masqués (Al, Bl, etc.), le module non sécurisé produisant un résultat intermédiaire (Sl) , • déduit le résultat attendu S à partir du résultat intermédiaire (Sl) et du ou des nombres aléatoires utilisés pour le masquage du ou des points secrets. vérifie l'exactitude du résultat attendu S.

Ainsi, le module non sécurisé n'a jamais accès aux éventuelles données secrètes manipulées au cours du procédé, toutes les données secrètes étant masquées par un ou plusieurs nombres aléatoires.

Selon un premier mode de réalisation selon l'invention, pour vérifier le résultat S fourni par le module non sécurisé, le module sécurisé : • sous-traite au module non sécurisé la réalisation d'au moins un couplage f supplémentaire à partir d'au moins un point Al obtenu par combinaison linéaire du point A avec un coefficient ri, le module non sécurisé produisant au moins un résultat supplémentaire, puis • vérifie la cohérence entre le résultat intermédiaire précédemment fourni et le ou les résultats supplémentaires en combinant linéairement le résultat intermédiaire précédemment fourni et le ou les résultats supplémentaires.

Ce premier mode de réalisation sera privilégié notamment pour la réalisation de toute fonction f présentant des propriétés de linéarité ou de bilinéarité. Si la fonction f prend plusieurs variables d'entrée, il est possible de masquer une ou plusieurs de ces variables d'entrée, par des combinaisons linéaires plus ou moins complexes, en fonction du niveau de sécurité que l'on souhaite pouvoir garantir. Ainsi, si une ou plusieurs variables d'entrée de la fonction f sont des données publiques, il n'est pas indispensable de les masquer, ce qui permet d'alléger les calculs réalisés par le module sécurisé pour vérifier les résultats fournis par le module non sécurisé et déterminer le résultat initial attendu. Inversement, si un ou plusieurs variables d'entrée de la fonction f sont des données secrètes, on utilisera des combinaisons linéaires plus ou moins complexes pour les masquer. Ces principes font être détaillés ci-dessous dans des exemples.

Le premier mode de réalisation de l'invention peut être choisi pour la réalisation d'un couplage de deux points A, B d'une courbe elliptique.

Selon une première variante, pour calculer le couplage de deux points A, B d'une courbe elliptique comprenant également deux points générateurs G, H, le module sécurisé : • sous-traite au module non sécurisé le calcul des couplages S = <A, B>, Sl = <G, B>, S2 = <A, H> et S3 = <A3, B3>, avec A3 = r3.A+s3.G et B3 = t3.B+u3.H, r3, s3, t3, u3 étant des coefficients entiers, • vérifie l'exactitude du résultat S en vérifiant l'égalité : S3 = r3.t3.S + s3.t3.Sl + r3.u3.S2 + s3.u3.<G, H>

Dans cette première variante, on utilise la propriété de bilinéarité de la fonction de couplage sur courbe elliptique.

La propriété permet d'écrire : S3 = <A3, B3> = <r3.A+s3.G, t3.B+u3.H> = r3.t3.<A,B> + s3.t3.<G,B> + r3.u3.<A,H> + s3.u3.<G,H>

Selon cette propriété, le résultat C = <A, B> du couplage entre deux points A et B est un élément d'un ensemble mathématique possédant une structure de groupe. Pour plus de simplicité, dans la suite du brevet, les opérations effectuées dans cet ensemble seront notées additivement, c'est à dire que l'on notera par exemple <A+A'> = <A,B> + <A',B> et <A,B+B> = <A,B> + <A,B'> pour exprimer la propriété de bilinéarité de l'opération de couplage entre deux points.

On utilise également deux paramètres, à savoir deux points générateurs de la courbe elliptique. Les coordonnées de ces points, ainsi que la valeur du couplage de ces deux points <G, H> sont mémorisées dans le module sécurisé, par exemple au cours d'une phase d'initialisation du procédé.

Le calcul du résultat S = <A, B> et sa vérification par le module sécurisé est ici très rapide, dans la mesure où l'intervention du module sécurisé est limitée à la réalisation d'additions ou de multiplications par un scalaire entier.

Cette première variante pourra notamment être utilisée lorsque les points A, B sont des données publiques.

Dans une deuxième variante, pour calculer le couplage de deux points A, B d'une courbe elliptique comprenant également deux points générateurs G, H, le module sécurisé : • sous-traite au module non sécurisé le calcul des couplages Sl = <G, B>, S2 = <A2, B>, S3 = <A2, H> et S4 = <A4, B4> avec : A2 = A+s2.G, A4 = r4.A+s4.G, B4 = t4.B+u4.H, • détermine S = <A, B> en résolvant l'équation S2 = S + s2.<G, B>, • détermine <A, H> en résolvant l'équation S3 = <A, H> + s2.<G, H> • vérifie l'exactitude des calculs de couplages précédents en vérifiant l'équation : S4 = r4.t4.S + s4.t4.Sl + r4.u4.<A, H> + s4.u4.<G, H> A noter dans ce mode de réalisation, que le module non sécurisé n'a pas accès au point A et ignore ses coordonnées, puisque il reçoit du module sécurisé uniquement les points G, B, A2, A3, H, A4 et B4, nécessaires pour calculer les couplages Sl à S4 demandés. Si de plus, les coefficients s2, s3, r4, s4, t4 et u4 sont choisis aléatoirement à chaque mise en oeuvre du procédé, alors le module non sécurisé ne dispose d'aucun moyen de retrouver des informations relatives au point A. Cette variante pourra par exemple être utilisée dans le cas où A est une donnée secrète et B une donnée publique.

Dans une troisième variante, pour calculer le couplage de deux points A, B d'une courbe elliptique comprenant également deux points générateurs G, H, le module sécurisé : • sous-traite au module non sécurisé le calcul des couplages Sl = <G, B2>, S2 = <A2, H>, S3 = <A2, B2> et S4 = <A4, B4> avec : A2 = A+s2.G, A4 = r4.A+s4.G, B2 = B+U2.H, et B4 = t4.B+u4.H, • détermine <G, B> en résolvant l'équation Sl = <G, B>+ul.<G, H> • détermine <A, H> en résolvant l'équation S2 = <A, H> + s2.<G, H> • détermine S = <A, B> en résolvant l'équation S3 = <A, B> + u2.<A, H> + s2.<G, B> + s2.u2.<G, H> • vérifie l'exactitude des calculs de couplages précédents en vérifiant l'équation : S4 = r4.t4.S + s4.t4.Sl + r4.u4.<A, H> + s4.u4.<G, H>

Dans cette variante, les données A, B ne sont jamais directement accessibles par le module non sécurisé, ce qui est intéressant notamment si A et B sont des données secrètes.chacune Selon une quatrième variante, pour calculer le couplage de deux points A, B d'une courbe elliptique comprenant également deux points générateurs G, H, le module sécurisé : • sous-traite au module non sécurisé le calcul des couplages Sl = <A1, Bl>, S2 = <A2, B2>, S3 = <A3, B3> et S4 = <A4, B4> avec : Al = rl.A+sl.G, A2 = r2.A+s2.G, A3 = r3.A+s3.G, A4 = r4.A+s4.G, Bl = tl.B+ul.H, B2 = t2.B+u2.H, B3 = t3.B+u3.H, B4 = t4.B+u4.H, • détermine <A, B>, <A, H> et <G, B> en résolvant un système de trois équations à 3 inconnues^: Si = ri.ti.<A,B>+Si.ti.<G,B>+ri.Ui.<A,H>+Si.ui. <G,H>/ pour i variant de 1 à 3 • vérifie la cohérence des calculs de couplages précédents en vérifiant l'équation : S4 = r4.t4.<A,B>+s4.t4.<G,B>+r4.u4.<A,H>+s4.u4. <G,H>,

La quatrième variante décrite précédemment nécessite pour le module sécurisé le calcul de plusieurs inverses modulaires, lors de la résolution du système de trois équations à trois inconnues.

Selon un deuxième mode de réalisation, le module sécurisé peut sous-traiter le calcul d'un inverse modulaire au module non sécurisé, en procédant de la manière suivante, pour un nombre A dont le module sécurisé doit calculer l'inverse modulaire.

Ce deuxième mode de réalisation est notamment intéressant pour des opérations sous-traitées f dont l'inverse 1/f est peu coûteuse à calculer pour le module sécurisé.

C'est le cas par exemple de l'opération f(A) = 1/A, dont l'inverse 1/f(A) est immédiat. Ainsi, dans cet exemple, pour vérifier l'exactitude du résultat S fourni par le module non sécurisé, le module sécurisé multiplie simplement le nombre A au résultat fourni par le module non sécurisé.

Si de plus le nombre A doit être masqué au module non sécurisé, alors le module sécurisé : • masque le nombre entier A en le multipliant par un nombre aléatoire a, • sous-traite au module non sécurisé la réalisation de l'inversion du nombre entier masqué a.A, • vérifie l'exactitude du résultat intermédiaire fourni par le module non sécurisé en multipliant le résultat intermédiaire l/(a.A) par le nombre entier A, • calcule le résultat attendu 1/ A en multipliant le résultat intermédiaire l/(a.A) par le nombre aléatoire a.

Là encore, l'intervention du module sécurisé est limitée à la réalisation de multiplications de nombres entiers.

Le deuxième mode de réalisation de l'invention, qui permet une réalisation rapide d'une inversion peut être utilisé pour réaliser des opérations plus complexes comme par exemple une division de type B/A : le module sécurisé sous-traite avantageusement la réalisation de l'opération T = 1/A puis réalise ensuite l'opération S = B*T, beaucoup moins coûteuse

La mise en oeuvre d'une telle division peut être utilisée notamment pour résoudre des équations linéaires telles que celles que l'on peut être amené à résoudre lors de la réalisation d'une opération de couplage sur courbe elliptique selon l'invention.