Brevet FR2871970A1 — publié le 20051223

PROCEDE DE REALISATION D'UNE OPERATION DE COUPLAGE SUR UNE COURBE ELLIPTIQUE, PAR UN SYSTEME COMPRENANT UNE CARTE A PUCE ET UN LECTEUR DE CARTE 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 de 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 = 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'une opération mathématique f produisant un résultat S en fonction d'au moins un nombre A, à 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 des protocoles cryptographiques, 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 le nombre A, variable d'entrée de la fonction sous-traitée, est un nombre secret, le module sécurisé : É masque le nombre secret A par un nombre aléatoire, É sous-traite au module non sécurisé la réalisation de l'opération f à partir du nombre secret masqué (Al, B1, etc.) transmis par le module sécurisé, pour produire un résultat intermédiaire (Sl), É déduit le résultat attendu S à partir du résultat intermédiaire (Sl) fourni par le module non sécurisé et du nombre aléatoire utilisé pour le masquage, et É 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 de l'invention, pour vérifier le résultat S fourni par le module non sécurisé, le module sécurisé : É sous-traite également au module non sécurisé la réalisation d'au moins une opération f supplémentaire en fonction d'au moins un nombre Al obtenu par masquage du nombre A avec un coefficient r1 puis É vérifie la cohérence entre le résultat initialement fourni et le ou les résultats supplémentaires en combinant linéairement le résultat initialement 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 = , S1 = , S2 = et S3 = , 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.S1 + r3.u3.S2 + s3.u3. 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 = = = r3. t3. + s3.t3. + r3.u3. + s3.u3. Selon cette propriété, le résultat C = 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 = + et = + 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 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 = 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 S1 = , S2 = , S3 = et S4 = avec: A2 = A+s2.G, A4 = r4.A+s4.G, B4 = t4.B+u4.H, É détermine S = en résolvant l'équation S2 = S + s2. , É détermine en résolvant l'équation S3 = + s2. É vérifie l'exactitude des calculs de couplages précédents en vérifiant l'équation: S4 = r4.t4.S + s4.t4.S1 + r4.u4. + s4.u4. 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 S1 à 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 S1 = , S2 = , S3 = et S4 = avec: A2 = A+s2. G, A4 = r4. A+s4. G, B2 = B+u2.H, et B4 = t4.B+u4.H, É détermine en résolvant l'équation S1 = +u1. É détermine en résolvant l'équation S2 = + s2. É détermine S = en résolvant l'équation S3 = + u2. + s2. + s2.u2. É vérifie l'exactitude des calculs de couplages précédents en vérifiant l'équation: S4 = r4.t4.S + s4.t4.S1 + r4.u4. + s4.u4. 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 S1 = , S2 = , S3 = et S4 = avec: Al = rl.A+sl.G, A2 = r2.A+s2.G, A3 = r3.A+s3.G, A4 = r4.A+s4.G, B1 = tl.B+ul.H, B2 = t2.B+u2. H, B3 = t3.B+u3.H, B4 = t4.B+u4.H, É détermine , et en résolvant un système de trois équations à 3 inconnues Si = ri.ti. +si.ti. +ri.ui. +si.ui. , 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. +s4.t4. +r4.u4. +s4.u4. , 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 soustraiter 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 1/(a.A) par le nombre entier A, É calcule le résultat attendu 1/ A en multipliant le résultat intermédiaire 1/(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 notamment pour résoudre des que celles que l'on peut être réalisation d'une opération elliptique selon l'invention. division peut être utilisée équations linéaires telles amené à résoudre lors de la de couplage sur courbe REVENDICATIONS 1. Procédé cryptographique mis en oeuvre par un module de calcul sécurisé, caractérisé en ce que, au cours du procédé, le module sécurisé soustraite la réalisation d'une opération mathématique f produisant un résultat S en fonction d'au moins un nombre A, à 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é. IO 2. Procédé selon la revendication 1, au cours duquel, le nombre A étant un nombre secret, le module sécurisé : É masque le nombre secret par un nombre aléatoire, É sous-traite au module non sécurisé la réalisation de l'opération f à partir du nombre secret masqué (Al, B1, etc.) transmis par le module sécurisé, pour produire un résultat intermédiaire (Si), É déduit le résultat attendu S à partir du résultat intermédiaire (Si) fourni par le module non sécurisé et.du nombre aléatoire utilisé pour le masquage. É vérifie l'exactitude du résultat attendu S. 3. Procédé selon la revendication 1 ou 2, dans lequel, pour vérifier le résultat fourni par le 25 module non sécurisé, le module sécurisé : É sous-traite au module non sécurisé la réalisation d'au moins une opération f supplémentaire en fonction d'au moins un nombre Al obtenu par combinaison linéaire du nombre A avec un coefficient ri puis É vérifie la cohérence entre le résultat initialement fourni et le ou les résultats supplémentaires en combinant linéairement le résultat initialement fourni et le ou les résultats supplémentaires. 4. Procédé selon la revendication 3, dans lequel, 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 = , S1 = , S2 = et S3 = , 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.S1 + r3.u3.S2 + s3.u3. 5. Procédé selon la revendication 3, dans lequel, 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 Si = , S2 = , S3 = et S4 = avec A2 = A+s2.G, A4 r4.A+s4. G, B4 = t4.B+u4.H, É détermine S = en résolvant l'équation S2 = S + s2. , É détermine en résolvant l'équation S3 = + s2. É vérifie l'exactitude des calculs de couplages précédents en vérifiant l'équation S4 = r4.t4.S + s4.t4.S1 + r4.u4. + s4.u4. 6. Procédé selon la revendication 3, dans lequel, 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 S1 = , S2 = , S3 = et S4 = avec: A2 = A+s2.G, A3 = A+ s3.G, A4 = r4.A+s4.G, B1 = B+u1.H, B3 = B+u3.H et B4 = t4.B+u4.H, É détermine en résolvant l'équation Si = +u1. É détermine en résolvant l'équation S2 = + s2. É détermine S = en résolvant l'équation S3 = + u3. + s3. + s3.u3. É vérifie l'exactitude des calculs de couplages précédents en vérifiant l'équation S4 = r4.t4.S + s4.t4.S1 + r4.u4. + s4.u4. 7. Procédé selon la revendication 3, dans lequel, 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 S1 = , S2 = , S3 = et S4 = avec: Al = rl.A+sl.G, A2 = r2.A+s2.G, A3 = r3.A+s3.G, A4 = r4.A+s4.G, B1 = tl.B+ul.H, B2 = t2.B+u2. H, B3 = t3.B+u3.H, B4 = t4.B+u4.H, É détermine , et en résolvant un système de trois équations: Si = ri.ti. +si.ti. +ri.ui. +si.ui. , 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. +s4.t4. +r4.u4. +s4.u4. , 8. Procédé selon l'une des revendications 3 à 7, dans lequel au moins un des coefficients ri, si, ti, ui, pour i variant entre 1 à 4, est un nombre aléatoire. 9. Procédé selon la revendication 1 ou 2, dans lequel le module sécurisé vérifie l'exactitude du résultat fourni par le module non sécurisé en calculant l'inverse de la fonction sous-traitée au module non sécurisé. 10. Procédé selon la revendication précédente dans lequel l'opération sous-traitée au module non sécurisé est une inversion d'un nombre entier A, et dans lequel, pour vérifier l'exactitude du résultat S fourni par le module non sécurisé, le module sécurisé multiplie le nombre A au résultat fourni par le module non sécurisé. 11. Procédé selon la revendication précédente en combinaison avec la revendication 2, dans lequel le 30 module sécurisé : Ait É 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 A masqué, É vérifie l'exactitude du résultat intermédiaire fourni par le module non sécurisé en multipliant le résultat intermédiaire par le nombre entier A, É calcule le résultat attendu en multipliant le résultat intermédiaire par le nombre aléatoire.