Brevet FR3044790A1 — publié le 20170609

La présente invention concerne un procédé de chiffrement basé sur l'identité. L'invention s'applique notamment aux infrastructures de gestion de clefs publiques (IGC/PKI). Avec l'explosion des communications et des supports de communication ainsi que l'augmen5 tation des attaques informatique résultantes, le besoin de sécuriser l'information qui transite à travers ces moyens de communication est devenu de plus en plus important. Une méthode connue et classique participant à la sécurisation des moyens de communication est l'infrastructure de gestion des clefs publiques (1GC) plus connue sous le nom de PKI (public key infrastructure). Pour ce système connu, la communication se sécurise avec rutin- 10 sation d'une fonction de chiffrement asymétrique, d'une clef publique et d'une clef privée qui sont toutes les deux liées par une propriété algébrique (voir Fig 1). Ces deux clefs ont une entropie d'autant plus importante que le niveau de sécurité requis est important. Le chiffrement de la méthode classique se déroule selon les étapes suivantes : - soit KpubA = clef publique d'Alice (Fig 1 - 1) et KpriA = clef privé d'Alice (Fig 1 - 2) 15 - Bob envoie à Alice le message M chiffré qui devient M' = f(KpubA, M) (Fig 1 - 3) - Alice déchiffre le message M' avec sa clef privé KpriA M = t1(KpriA,M3) (Fig 1 - 4) Afin d'authentifier une communication et d'assurer la non répudiation, le procédé bien connu de signature est utilisé avec de nouveau, l'utilisation de deux clefs liées algébriquement (voir 20 Fig 2). La signature de la méthode classique se déroule selon les étapes suivantes : - soit KpubB = clef publique de Bob (Fig 2 -1) et KpriB = clef privé de Bob (Fig 2 - 2) - soit h est une emprunte de M (Fig 2 -1) (Fig 2 - 2) - Bob signe le message M et l'envoie à Alice S = signature(KpriB, h(M)) (Fig 2 - 3) - Alice vérifie la signature h(M) =? signature-i(KpubB,M) (Fig 2 - 4) 25 Lorsqu'il faut sécuriser toutes les communications entre les membres d'un groupe, l'homme du métier a recourt à une infrastructure à clef publique. En particulier il faut protéger l'ensemble des clefs privées, gérer les révocations et l'enrôlement (pour l'arriver d'un nouveau membre dans le groupe, ou le départ d'un ancien membre du groupe). Une des contraintes de ce système provient du fait qu'il faille stocker les clefs publiques dans des certificats élec- 30 toniques et qu'il nécessite des clefs différentes pour la signature et le chiffrement asymé- trique. D'autres contraintes sont liées à la lourdeur du système qui est complexe et couteux à gérer, ce qui est bien connu de l'homme du métier. 35 3044790 -2- Le but de l'invention est de remédier aux problèmes liés à la gestion des certificats. Ainsi dans le système que l'on propose, toutes les clefs publiques peuvent être recalculées à partir d'une donnée publique. Il n'est plus nécessaire de mémoriser la liste des clefs publiques 5 de chaque partenaire. Une alternative de ce type existe cependant et remédie au problème de gestion des certificats. Il s'agit du chiffrement basé sur l'identité tel que l'ont défini D. Boneh et M. Franklin (Cf [1] et Fig 3). Nous concentrerons notre rédaction sur le procédé de chiffrement puisque les auteurs de [1 ] ont montré que d'un schéma IBE (chiffrement basé sur l'identité) 10 découlait automatiquement un schéma de signature possédant le même niveau de sécurité. Ce système introduit une tierce partie généralement appelée PKG (générateur de clefs privées) qui gère et octroie les clefs privées des utilisateurs d'un groupe bien défini. La clef publique maîtresse de ce PKG (Mpub) est distribuée aux utilisateurs (Fig 3 - 1). Ensuite chaque utilisateur est authentifié et reçoit sa clé privée (Fig 3 - 2). Ceux-ci peuvent alors construire 15 n'importe quelle clef publique et n'ont plus besoin de les stocker. Contrairement aux systèmes PK1, il n'y a plus de relation algébrique forte entre la clef publique et la clef privée associée. Ainsi Bob peut utiliser l'Id = Alice@exemple.com pour forger la clef publique d'Alice et ainsi peut signer et chiffrer des messages à destination d'alice (Fig 3 - 3). Alice à son tour peut utiliser l'Id = Bob@exemple.com pour forger la clef publique de Bob et ainsi déchiffrer 20 les messages de Bob et vérifier sa signature (Fig 3 - 4). Ce système de chiffrement requière l'utilisation d'une forme bilinéaire admissible comme cela est décrit dans [1] que l'on notera par la suite BL. Il requière également l'utilisation de 3 groupes (au sens mathématique) G1, G2, G3 tels que : BL : G1 G2 - G3 soit défini avec G1 et G2 additifs. 25 Lorsque nous effectuerons une multiplication entre un scalaire s du groupe Z/qZ et un élément g d'un groupe additif G, nous noterons sg = g+g+...+g. Cette notation est bien connue de l'homme de métier. Les fonctions bilinéaires évoquées dans tout le document satisfont la propriété suivante : Pour g, Gl, g G2 et s Z/qZ, nous avons BL(sg,,g2) = BL(g,,sg2) = BL(g,,g2)s. 30 Ainsi, nous pouvons résumer les étapes de chiffrement asymétrique du système de D. Boneh et M. Franklin par les trois phases suivantes : 35 3044790 -3- 1) L'initialisation : - Une fonction de hachage (empreinte bien connu de l'homme de métier) HG2 : {0,1 ? -> G2-(e} = G2* ou e désigne l'élément neutre du groupe G2 et k est la longueur en bits du 5 message à chiffrer; - Une fonction de hachage Hm : G3 -3 {0,1}x; - Trois groupes cycliques G1, G2 et G3 d'ordre q; - Un générateur P de Gl; - La clef maitresse et privée de PKG : s Z/qZ-{0} (ensemble des entiers naturels non 10 nuls modulo q) ; - La clef publique de PKG : P0 = sP ; - Paramètres publiques : PP = (BL, q, HG2, Hm, G1, G2, G3, P0) ; - Paramètre privé de PKG : s 2) Chiffrement : 15 - Entrée : un message m {0,1} et une identité ID ; - La clef publique de l'identité ID : QID = HG2(ID) G2 ; - Tirage aléatoire de r Z/qZ-{0}; - go = BL(P0,QID) G3 ; - Sortie : le message C = (rP, m Hn(gor)) GT {0,1}, ou désigne le Xsor bit à bit de 20 deux entiers. 3) Déchiffrement : - Entrée : C = (U,V) G1* {0,1} ; - La clef privée (secrète) de ID : SID = sQID ; Sortie : m = V 11,,(BL(U,SID)) ; 25 II existe un certain nombre de variantes de ce système qui possède tous un certain nombre d'inconvénients que nous allons énumérer : - La confiance attribuée au PKG : celui-ci peut signer et chiffrer à la place de n'importe quel membre du groupe (usurpation d'identité). - Si le PKG est compromis, le système tombe. 30 Le but de notre invention est de remédier à ces deux inconvénients en construisant une clef secrète à partir de deux entités distinctes, ainsi seule la connaissance des secrets respectifs de ces entités permettrait de générer la clef secrète d'un membre du groupe. Notre système fonctionne avec deux PKGs : PKGdy (PKG dynamique dont l'identité 35 est IDdy) et PKGst (PKG statique dont l'identité est IDst). Le PKGst n'intervient que pendant la phase d'enregistrement des nouveaux membres, il est ensuite déconnecté (hors ligne). 3044790 -4- Afin de décrire notre procédé de chiffrement, nous reprenons les mêmes notations que pour la description du schéma des auteurs de [1] auxquelles nous ajoutons des notations complémentaires. Voici les phases de fonctionnement de notre infrastructure à clefs publiques : 1) Initialisation des paramètres du système : - Choisir trois groupes cycliques d'ordre q : Gl, G2 et G3, G1 et G2 étant des groupes additifs. - Choisir une application bilinéaire BL : G1 G2 G3 ; Choisir des générateurs P G1 et P' G2 des groupes G1 et G2 respectivement. - Choisir trois fonctions de Hachage avec k la longueur du message à chiffrer en bits : o HG : {0,1 G-{e} = G* ou e désigne l'élément neutre du groupe G ; O Hm : G3 -> {0,1 }d ou d est la dimension de q (en nombre de bits) ; o H$ : {0,1 y-d -> {0,1y ou d est la dimension de q (en nombre de bits) et f un entier suffisamment grand pour éviter les attaques bien connues de l'homme de métier sur les 15 fonctions de hachage. 2) Initialisation de la clef publique du système (Fig 4): - PKGst tire une clef secrète so Z/qZ; (Fig 4 - 1) - Les clefs publiques de PKGst : Po = soP G1et P'o = soP' G2; (Fig 4 - 1) 20 - PKGdy tire une clef secrète sl Z/qZ ; (Fig 4 - 2) - La clef publique de PKGdy = s,P G1; (Fig 4 - 2) - La clef publique du système pour le PKGst: Y = siPo Gl; (Fig 4 - 3) - La clef publique du système pour le PKGdy: Y = sisoP G1; (Fig 4 - 4) - La clef publique du système : Y = s,Po = sisoP Gl; 25 - L'exactitude de la clef publique peut être contrôlée en vérifiant que BL(Y,P') BL(P,,Fo) ; (Fig 4 - 5) 3) Phase d'enregistrement d'un membre : - Enregistrement d'un membre auprès du PKGst hors ligne avec initialisation et vérifi 30 cation de sa clé secrète partielle (Fig 5): o MEMBRU. o Le membre envoie son ID au PKGst ;(Fig 5 -1) - PKGst 35 - Le PKGst vérifie l'ID du membre. Le PKGst calcule la clef publique de ID : QID = HG2(IDIIDstIlDdy) ; (Fig 5 - 2) Le PKGst calcule la clef secrète partielle Sp = soQID G2; Fig 5 - 3) 40 3044790 -5- Le PKGst calcule la signature : Sign(Sp) = soSp G2; Fig 5 - 4) Le PKGst envoie Sp et Sign(Sp) au membre ID. (Fig 5 - 5) 5 o MEMBRE : Le membre ID vérifie que BL(Sign(Sp),P) = BL(Sp,P0) ;(Fig 5 - 6) - Enregistrement d'un membre auprès du PKGdy en ligne avec initialisation et véri fica- 10 tion de sa clé secrète partielle (Fig 6): o MEMBRE : - Le membre envoie son ID au PKGdy ; (Fig 6 -1) - Le membre ID choisit t Z/qZ un masque secret temporaire; (Fig 6 - 2) - Le membre ID calcule sa clef publique: QID = HG2(1DIIDstlIDdy) ; (Fig 6 - 3) - Le membre ID calcule sa clef secrète partielle masquée : Sp,t = tSp = tsoQID G2; (Fig 6 - 4) Le membre ID calcule la signature : Sign(Sp,t) = t Sign(Sp) G2.(Fig 6 - 5) o PKGdy : Le PKGdy vérifie la signature de PKGst : BL(P,Sign(Sp,t)) = BL(P0,Sp,t) ; (Fig 6 - 6) - Le PKGdy calcule et envoie au membre la clef secrète masquée St = siSp.t= tsostQlD ; (Fig 6 - 7) - Le PKGdy calcule et envoie au membre la signature : Sign(St) = siSt. (Fig 6 - 8) 0 MEMBRE : - Le membre ID vérifie que BL(P,Sign(St)) = BL(P0,St) ; (Fig 6 - 9) - Le membre ID extrait la clef secrète SID = Stft = soselD ou (/t désigne la multiplication par l'inverse de t dans le groupe multiplication des inversibles de Z/qZ, bien connu de l'homme de métier); (Fig 6 - 10) Nous avons choisi une méthode de chiffrement ci dessous similaire à [1] mais la méthode de chiffrement authentifié de [4] est tout aussi applicable ainsi que toute autre méthode et shéma de chiffrement: 3044790 -6- 4) Opération de chiffrement (Fig 7) : Un membre ID1 chriffre un message pour un membre ID2 5 - Le membre ID1: Entrée : un message m {0,1} et une identité ID2 ; (Fig 7 - 1) - Le membre 101 calcule QID2 = HG2(1011DstIlDdy) et 91D2 =BL(Y,QID2) ; (Fig 7 - 2) - Le membre ID1 tiret aléatoirement un entier r Z/qZ; (Fig 7 - 3) - Le membre ID1 calcule la sortie : le message C = (U,V) = (rP, m Fé2(g1D29) GT {0,1}k ou désigne le Xsor bit à bit de deux entiers; (Fig 7 - 4) 10 - Le membre ID1 envoie te message C au membre ID2 ;(Fig 7 - 5) 5) Opération de déchiffrement (Fig 7) : un membre ID déchiffre un message - Le membre ID reçoit C = (U,V) = (rP, m Ii2(gior)) GT {0,1}k et calcule m = V HG2(BL(U,SID)). (Fig 7 - 6) 15 6) Opération de signature (Fig 8): - Entrée : le membre ID avec sa clef publique QID et sa clef secrète SID veut signer le message m {0,1}; (Fig 8 - 1) - Le membre ID tire aléatoirement x Z/qZ--{0}et calcule z = BL(Y,QID)x ;(Fig 8 - 20 2) - Le membre ID calcule la signature de m = (v,U)=(Hs(m11-1,(z)),xSID-vQ1D) {0,1} G2. (Fig 8 - 3) - Le membre ID envoie ta signature au membre qui souhaite ta vérifier . (Fig 8 - 4) 25 7) Vérification d'une signature (Fig 8): - Entrée = le message m {0,1} et sa signature par ID : (v,U) {0,1} G2 ; (Fig 8 - 5) - Calculer z = BL(P,U)BL(P,QID)v ; (Fig 8 - 6) - Vérifier que v = Fls(m1Hm(z)). (Fig 8 - 7) 30 8) Procédure de mise à jour des clés : - PKGdy choisit une nouvelle clef secrète Z/qZ-{0}; - PKGdy calcule les nouvelles clefs publiques P'1 = s'iP et Y' = s'i Po ; - PKGdy envoie une requête à tous les membres du système ; - Les membres du système reproduisent la phase décrite en 3) « Authentification de ID 35 par PKGdy » et « Authentification de PKGdy par ID ». 3044790 9) procédure de révocation d'un membre : - PKGdy révoque un membre en retirant le membre de la liste des membres autorisés 5 et lance la procédure 8) de mise à jour des clefs des membres du système. Notre système se différentie de l'état de l'art par plusieurs aspects : - Nous avons généralisé ce type chiffrement basé sur l'identité aux fonctions bilinéaires 10 asymétrique tandis que [1] et [2] ne proposent que des schémas utilisant des fonctions symétriques. - Nous n'avons aucune clé à stocker car elles peuvent toutes être régénérées par l'invention. - L'invention permet au membre utilisateur d'être le seul à pouvoir signer et chiffer avec 15 son identité. Notre invention à l'inverse des autres travaux empêche le PKGst ou le PKGdy de signer ou chiffrer à la place de l'utilisateur. - Dans notre invention, le PKGst centrale étant hors ligne, le système est donc protégé car il est impossible de faire tomber l'autorité centrale. - Une faille réside dans les travaux de [2] comme l'atteste l'article [3]. Ainsi nous avons 20 modifié la procédure d'échange de clef qui comporte un enrôlement hors ligne et physique avec une autorité centrale qui reste hors ligne (PKGst) et un enrôlement en ligne avec une autorité centrale dynamique qui reste en ligne (PKGdy). Nous avons également modifié l'algorithme qui permet de délivrer une clef secrète à chaque membre (Fig 5 et Fig 6). 25 Les dessins annexés illustrent l'invention : La figure 1 représente le procédé de chiffrement asymétrique de l'état de l'art antérieur. La figure 2 représente le procédé de signature asymétrique de l'état de l'art antérieur. 30 La figure 3 représente la méthode de chiffrement et signature basée sur l'identité [1] de l'état de l'art antérieur. La figure 4 représente l'initialisation des paramètres publiques (procédure hors ligne) de l'invention. La figure 5 représente l'initialisation et vérification de la clef secrète partielle du membre ID 35 auprès du PKGst hors ligne de l'invention. La figure 6 représente l'initialisation et vérification de la clef secrète du membre ID en ligne auprès de PKGdy de l'invention. La figure 7 représente le procédé de chiffrement et déchiffrement d'un membre ID de l'invention. 40 La figure 8 représente le procédé de signature et de vérification de signature d'un membre ID de l'invention. 3044790 -8- L'invention est susceptible d'être appliqué partout ou il est usuel d'utiliser une IGC pour protéger l'information (Banques, Assurances, Armée, PME innovantes...). 5 Ajoutons qu'une simple modification du protocole de transport d'information TLS permet de rendre compatible ce procédé avec la plupart des VPN existants, Internet (https), les web services... Notons également que la plupart des SIEMs (système d'analyse de log et d'événements) protègent le transport des logs avec le protocol TLS, ce qui les rend de faite compatibles 10 avec le procédé exposé dans ce document. 15 20 25 30 35 40 REVENDICATIONS1) Un procédé mis en oeuvre par ordinateur pour la gestion d'un système d'authentification. La méthode comprend: a) Le calcul sur chacun des deux ordinateurs des paramètres secrets respectifs comprend une clef secrète so E Z/qZ sur l'ordinateur PKGst et si E Z/qZ sur l'ordinateur PKGdy. b) L'obtention par utilisation des deux ordinateurs PKGst et PKGdy des paramètres publics publiés sur un troisième ordinateur PKGpub comprent trois groupes cycliques d'ordre q : Gl, G2 et G3, G1 et G2 étant des groupes additifs, une application bilinéaire BL : G1 G2 G3 , des générateurs PEG1 et P'EG2 , trois fonctions de Hachage HG 11, H, , k la longueur du message à chiffrer en bits, e l'élément neutre du groupe G, d la dimension de q (en nombre de bits) , f un entier suffisamment grand pour éviter les attaques bien connues de l'homme de métier sur les fonctions de hachage, les clés publiques Po et Pio deux points dans G2 calculés par l'ordinateur PKGst et publié sur l'ordinateur PKGpub, la clé publique Pi un point dans G2 calculé par l'ordinateur PKGdy et publié sur l'ordinateur PKGpub et la clée publique du système Y calculée par l'ordinateur PKGst et/ou l'ordinateur PKGdy et publiée sur l'ordinateur PKGpub. c) Un enrôlement des utilisateurs qui permet de leur attribuer un secret qui ne sera détenu que par eux seuls. Le membre envoie son identité ID à l'ordinateur PKGst qui calcule la clé publique de l'utilisateur QID basée sur le hash dans le groupe cyclique G2 de la concaténation de l'identité ID du membre, l'identité Idst du PKGst et l'identité Iddy du PKGdy HG2(IDI IDstilDdy) . L'ordinateur PKGst calcule la clé secrète partielle du membre Sp= soQID E G2 basée sur la clé publique de l'utilisateur QID et la clé secète du PKGst. L'ordinateur PKGst calcule la signature de la clé secète partielle du membre Sign(Sp) = soSp E G2 basée sur la clé secrète partielle du membre Sp et sur la clé secrète du PKGst. L'ordinateur du PKGst envoie la clé secrète partielle du membre Sp et la signature Sign(Sp) au membre utilisateur. Le membre utilisateur verifie la clé secrète partielle et la signature de cette clé reçu de l'ordinateur PKGst avec une fonction bilinéaire BL(Sign(Sp),P) = BL(Sp ,P0). Le membre utilisateur envoie son identité ID à l'ordinateur PKGdy . Le membre utilisateur choisit t E Z/qZ un masque secret temporaire . Le membre utilisateur calcule sa clef publique: QID = HG2(IDIIDstilDdy) le hash dans le groupe cyclique G2 de la concaténation de l'identité du membre, l'identité du PKGst et l'identité du PKGdy. Le membre utilisateur calcule sa clef secre te partielle masque e : rt= tSp à partir de Sp qui est délivré par PKGst. Le membre utilisateur calcule la signature de sa clé secrète partielle delivrée par l'ordinateur PKGst Sp et du masque secret temporaire t : Sign(Sp,t) = t Sign(Sp) E G2 . L'ordinateur PKGdy vérifie la signature de PKGst avec la fonction bilinéiare BL: BL(P,Sign(Sp,t)) = BL(Po,Sp,t) . L'ordinateur PKGdy calcule et envoie au membre utilisateur la clef secrète masquée St= siSp,t basée sur la clé secrète du PKGdy si et Sp,t . 3044790 -10- L'ordinateur PKGdy calcule et envoie au membre la signature de la clé secrète 5 masquée du membre St et de la clé secrète du PKGdy ss : Sign(St) = siSt. Le membre utilisateur vérifie avec la fonction bilinéaire que la signature est valide BL(P,Sign(St)) = BL(Po,St) . Le membre utilisateur extrait la clef secrète SID = St/t = sosiQID ou (/t désigne la multiplication par l'inverse de t dans le groupe multiplication des inversibles de Z/qZ, bien connu de l'homme de métier) 10 2) L'autorité appelé PKGdy ne possède pas les clefs de chiffrement ou de signature des utilisateurs. Il ne possède que la clef masquée des utilisateurs. 15 3) L'autorité appelé PKGst ne possède pas les clefs de chiffrement ou de signature des utilisateurs. Il ne possède que la clé secrète partielle du membre utilisateur. 4) Seule l'obtention des secrets de PKGdy et de PKGst peux permettre de reconstruire la clef 20 secrète d'un utilisateur: IDmv = sosig, 5) Le renouvellement des clefs secrètes ne fait pas intervenir PKGst.Il faut décrire la procédure : PKGdy recalcule un secret divise les anciens paramètres par l'ancien secret et multiplie par le nouveau, puis publie les nouveaux paramètres publiques, ensuite on 25 réitère le c). 6) La révocation d'un utilisateur se fait par renouvellement des clefs secrètes des utilisateurs. 7) Un procédé mis en oeuvre par ordinateur pour le chiffrement des données basé sur le 30 shema [1] . 8) Un procédé mis en oeuvre par ordinateur pour la signature basé sur le shema [1] . 35 40 3044790 References [1] Dan Boneh, Matthew Franklin, Identity-Based Encryption from the Weil Pairing, 2001. 5 [2] Lee B., Boyd E., Daeson E., Kim K., Yang J. and Yoo S., Secure key issuing in ID-based cryptography, In proceedings of the Second Australian Information Security Workshop-AISW 2004, pp.69-74. [3] Saeran Kwon, Sang-Ho Lee, Security Analysis and Improvement for Key Issuing Schemes in ID-Based Cryptography. 10 [4] Ben Lynn, Authenticated Identity-Based Encryption, 2002, available from https://eprint. iacr.org/2002J072.pdf.