Schéma fondé sur l'identité

Le schéma fondé sur l'identité (ou identity-based) est une notion de cryptologie introduite par Adi Shamir en 1984^[1].

La cryptographie par identité permet de résoudre le problème de certification des clefs publiques. En effet si la cryptographie asymétrique a résolu le problème d’échange de clefs^[2], la question de savoir si une clef publique, trouvée sur une page personnelle par exemple, correspond bien à une clef privée que possède l’interlocuteur présumé reste une question importante. GnuPG propose par exemple l’idée de la toile de confiance construite sur le principe de la transitivité de la confiance, et si beaucoup de membres de confiance ont certifié une clef, alors il y a de bonnes chances pour que la clef soit aussi de confiance.

Ainsi, dans le cadre du chiffrement par identité, un utilisateur peut publiquement dériver une clef de chiffrement pour une identité donnée par exemple par une adresse de courrier électronique. L’utilisateur possédant l’adresse e-mail obtient de la part d’une autorité la clef secrète permettant de déchiffrer pour son identité.

Principe

L'idée est de prendre comme clef publique l'identité de l'utilisateur, par exemple ses nom, prénom, date de naissance, ou numéro de sécurité sociale. Si l'on arrive à créer des clefs de chiffrement secrètes relatives à ces identités de telle sorte que deux individus différents ne puissent avoir la même clef secrète, alors il n'est plus utile de certifier les clefs publiques.

Schémas généraux

Les schémas basés sur l'identité permettent à n'importe quelle personne de régénérer la clef publique d'un individu à partir d'une valeur d'identité telle qu'une chaîne ASCII^[3].

Un tiers de confiance, le générateur de clefs privées, est chargé de la fabrication des clefs secrètes qui correspondent à ces clefs publiques. Pour cela, le générateur de clefs privées publie une clef publique « maître » et conserve pour lui la clef privée maître qui correspond.

On combine la clef publique « maître » à la valeur d'identité ${\displaystyle {\mathsf {id}}}$ afin de régénérer la clef publique qui correspond à cette identité. Afin d'obtenir la clef privée associée, la personne à qui correspond cette identité doit contacter le générateur de clefs privées, qui utilise sa clef privée « maître » pour générer la clef privée de l'utilisateur qui correspond à son identité.

En conséquence, il est possible de chiffrer des messages (ou de vérifier des signatures) sans opération préalable d'échange de clef entre les individus. Ceci est extrêmement utile au cas où la pré-distribution des clefs est difficile, ou impossible à cause de contraintes techniques.

Inconvénients

La contrainte de cette approche est que le niveau de confiance qui doit être accordé au générateur de clefs privées est très élevé, car il est intrinsèquement capable de régénérer la clef privée de tout utilisateur, et donc de pouvoir réaliser sans autorisation des signatures ou des déchiffrements. En fait une fonctionnalité de recouvrement de clef est présente de manière inhérente au système.

Un certain nombre de variantes ont été proposées afin d'éviter ce problème tel que le chiffrement basé sur certificat, la génération de clé sécurisée, et la cryptographie sans certificat. Quelques schémas ont été proposés entre 1984 et 2000, mais aucun n'a réuni deux qualités majeures : sécurité et applicabilité.

Il faut attendre 2001, et les publications de quasi simultanées Cocks et de Franklin et Boneh pour voir des cryptosystèmes vraiment prometteurs.

Cette page décrit dans le détail uniquement le schéma de Cocks, qui a l'avantage de l'originalité sur son rival. Il est néanmoins important de remarquer que le système de Boneh et Franklin est pleinement opérationnel, et dispose d'une implémentation pour le chiffrement de courriel.

Classification de Shamir des protocoles de reconnaissance

En 1986, Fiat et Shamir ont classifié les différentes catégories de protocoles de reconnaissance. Ils distinguèrent alors trois niveaux de protections. Supposons qu'Alice veuille prouver son identité à Bob, les différents niveaux sont alors :

1. protocole d'authentification: Alice peut prouver à Bob qu'elle est véritablement Alice, mais personne d'autre ne peut prouver à Bob qu'elle est Alice.
2. protocole d'identification : Alice peut prouver à Bob qu'elle est véritablement Alice, et Bob ne peut extraire aucune information de cette preuve pour tenter de faire croire à quelqu'un d'autre qu'il est Alice.
3. protocole de signature (ou non-répudiation): ce protocole a les mêmes propriétés que le précédent mais, en plus, Alice ne peut pas dire qu'elle n'a pas prouvé son identité à Bob, ou que le message qu'elle a signé était différent de celui que Bob prétend avoir reçu (elle ne peut pas répudier sa signature). En d'autres termes, Bob ne peut pas faire croire qu'Alice lui a prouvé son identité alors qu'elle ne l'a pas fait.

En fait, le protocole d'authentification au sens de Fiat et Shamir ne sera utilisé que lorsqu’Alice et Bob ont leurs intérêts en commun, pour prévenir une attaque venue de l'extérieur. Par contre, lorsqu’Alice et Bob ont des intérêts divergents, l'un des deux autres types de schéma doit être employé. Avec un protocole d'authentification, Bob pourrait a posteriori se faire passer pour Alice auprès d'un troisième intervenant. Ceci n'est plus possible lorsque l'on a affaire à un schéma d'identification. En revanche, dans ce cas, comme dans le cas de l'authentification, Bob peut faire croire qu'il a reçu un message venant d'Alice (en quelque sorte en imitant sa signature), tandis qu'un protocole de signature l'en interdit.

Nous n'utiliserons cependant pas le vocabulaire de Shamir, en ne faisant pas de distinction entre authentification et identification. En effet l'authentification au sens de Shamir présuppose qu'Alice et Bob ne sont pas rivaux, ce qui arrive assez souvent dans la pratique, mais aussi, que personne ne peut écouter une preuve d'authentification entre Alice et Bob, car sinon l'indélicat personnage serait dans les mêmes conditions que Bob pour restituer la clef secrète d'Alice, et pourrait donc se faire passer pour Alice lors des conversations ultérieures. Or, la confidentialité physique est généralement loin d'être parfaitement assurée.

Protocole de Shamir

Ce schéma est sous-jacent au protocole de signature publié par Shamir en 1984. Comme pour le schéma précédent, l'autorité crée une paire de clefs RSA (les mêmes notations seront utilisées et à partir de maintenant, tous les calculs doivent être effectués modulo ${\displaystyle n}$, dans ce protocole et dans les suivants). L'autorité confie à Alice ${\displaystyle V=I^{d}}$, où ${\displaystyle I}$ est l'identité d'Alice. Pour prouver qui elle est, Alice devra montrer qu'elle connaît ${\displaystyle V}$, sans dévoiler ${\displaystyle V}$.

Pour cela, lorsqu'elle envoie un message à Bob, elle choisit un aléa ${\displaystyle x<n}$ et lui envoie ${\displaystyle t=x^{e}}$. Bob prend au hasard un nombre ${\displaystyle c}$ appartenant à l'intervalle ${\displaystyle [1,e-1]}$, et le communique à Alice qui lui retourne alors ${\displaystyle y=Vx^{c}}$. Il ne reste plus à Bob qu'à vérifier que l'on a bien ${\displaystyle y^{e}=It^{c}}$.

Cependant, on ne possède pas de preuve de la sécurité de ce schéma.

Protocole de Cocks

Soit ${\displaystyle i}$ l'ensemble d'informations représentant l'identité d'Alice (par exemple une chaîne de caractères donnant son adresse de courrier électronique). On suppose l'existence d'un procédé public ${\displaystyle h}$ à base de fonctions de hachage tel que ${\displaystyle \left({\frac {h(i)}{M}}\right)=1.}$ On considérera dans la suite l'expression ${\displaystyle a=h(i)}$ comme étant l'identité de Alice.

Supposons que Bob veuille transmettre un courrier à Alice, d'identité ${\displaystyle a.}$ La valeur ${\displaystyle M=P\cdot Q}$ est publique, mais les facteurs ${\displaystyle P}$ et ${\displaystyle Q}$ sont des valeurs secrètes gardées par l’autorité. On supposera de plus sans perte de généralité que ${\displaystyle a}$ est un carré modulo ${\displaystyle M.}$ Bob va traiter son message bit à bit :

Chiffrement

Soit ${\displaystyle x}$ la représentation d'un bit à envoyer, ${\displaystyle x=1}$ ou ${\displaystyle -1.}$ Bob choisit un entier ${\displaystyle t}$ aléatoirement tel que ${\displaystyle \left({\frac {t}{M}}\right)=x.}$ Il peut alors envoyer le cryptogramme ${\displaystyle s}$ correspondant à ${\displaystyle x:}$ ${\displaystyle s=\left(t+{\frac {a}{t}}\right){\bmod {M}}}$

Dérivation de clef

Conformément au principe des cryptosystèmes basés sur l'identité, Alice interagit avec l'autorité de manière à obtenir ${\displaystyle r}$ vérifiant ${\displaystyle r^{2}=a{\bmod {M}}}$. On a vu que seule la connaissance de ${\displaystyle P}$ et ${\displaystyle Q}$ permet de calculer ${\displaystyle r.}$

La valeur ${\displaystyle r}$ devient alors le clef secrète d'Alice, fournie par l'autorité.

Déchiffrement

Comme ${\displaystyle s+2r=t(1+r/t)^{2}{\bmod {M}}}$. Alice peut retrouver ${\displaystyle x}$ par le calcul suivant.

${\displaystyle \left({\frac {s+2r}{M}}\right)=\left({\frac {t}{M}}\right)=x.}$ Dans le cas où ${\displaystyle -a}$ est un carré modulo ${\displaystyle M,}$ on utilise ${\displaystyle s=t-{\frac {a}{t}}{\bmod {M}}}$.

Protocole de Boneh-Franklin

C'est historiquement le premier schéma de chiffrement basé sur l'identité proposé en 2001 par Dan Boneh et Matthew Franklin^[5]. Celui-ci est prouvé sémantiquement sûr dans le modèle de l'oracle aléatoire. Cette construction repose sur l'utilisation de couplages cryptographiques.

Initialisation

Lors de la phase d'initialisation, un couplage ${\displaystyle (G,G_{T},e)}$ est choisi, ainsi qu'un générateur de ${\displaystyle G=\langle g\rangle }$, une fonction de hachage ${\displaystyle H:\{0,1\}^{*}\to G}$ Un aléa ${\displaystyle \alpha }$ est ensuite sélectionné et les paramètres publiques PP consistent en ${\displaystyle ((G,G_{T},e),g,g_{1}=g^{\alpha })}$, et la clef secrète maître MSK est l'exposant secret ${\displaystyle \alpha }$.

Dérivation de clef

Lorsqu'un utilisateur demande une clef pour son identité ${\displaystyle id}$, le possesseur de la clef maître privée ${\displaystyle \alpha }$ l'utilise pour calculer ${\displaystyle sk_{id}=H(id)^{\alpha }}$.

Chiffrer

Pour chiffrer un message pour le possesseur de l'identité ${\displaystyle id}$, un utilisateur va commencer par générer un aléa ${\displaystyle r\hookleftarrow \mathbb {Z} _{p}}$, puis calculer le chiffré ${\displaystyle C=(c_{1},c_{2})=(g^{r},M\cdot e(g_{1},H(id))^{r})}$. On peut reconnaître des similitudes avec le chiffrement El Gamal.

Déchiffrer

En possédant sa clef secrète ${\displaystyle sk_{id}=H(ID)^{\alpha }}$, à la réception d'un chiffré ${\displaystyle C=(c_{1},c_{2})}$, le receveur du message peut annuler le masque jetable sur la seconde composante du chiffré,

${\displaystyle e(g_{1},H(id))^{r}=e(g^{\alpha },H(id)^{r})=e(g^{r},H(id)^{\alpha })=e(c_{1},sk_{id}),}$

avec ces informations. Ce qui donne : ${\displaystyle m=c_{2}\cdot e(c_{1},sk_{id})^{-1}}$.

Chiffrement fondé sur l'identité et signatures

Il existe une construction générique de schémas de signature à partir de schémas de chiffrement fondé sur l'identité (CFI)i décrite dans les travaux initiaux de Boneh et Franklin sur les CFI de 2001^[5]. Dans cet article, ils proposent la construction suivante: étant donné un CFI ${\displaystyle ({\mathsf {Init}},{\mathsf {Deriv}},{\mathsf {Chiffrer}},{\mathsf {Dechiffrer}})}$, on construit le schéma de signature ${\displaystyle ({\mathsf {GenClefs}},{\mathsf {Signer}},{\mathsf {Verifier}})}$:

• GenClefs(1^λ): Cet algorithme commence en lançant l'algorithme d'initialisation du CFI pour obtenir ${\displaystyle (PP,MSK)\gets {\mathsf {Init}}(1^{\lambda })}$. La clef de signature sera la clef secrète maîtresse du CFI: ${\displaystyle {\mathsf {sk}}:=MSK}$ et la clef de vérification sont les paramètres publiques du CFI: ${\displaystyle {\mathsf {vk}}:=PP}$.
• Signer(sk, M): Pour signer un message M, cet algorithme génère une clef dérivée pour l'identité correspondant au message pour en faire la signature: ${\displaystyle \sigma$ :={\mathsf {Deriv}}({\mathsf {sk}},M)} .
• Vérifier(vk, M, σ): Pour vérifier une signature, cet algorithme commence par tirer un challenge ${\displaystyle c\hookleftarrow {\mathcal {U}}({\mathcal {M}})}$ uniformément au hasard dans l'espace des messages, puis accepte la signature si et seulement si ${\displaystyle {\mathsf {Dechiffrer}}(\sigma ,{\mathsf {Chiffrer}}({\mathsf {vk}},M,c))=c}$.

La correction du schéma de signature provient de la correction du CFI, et la sécurité de la signature (résistance aux falsifications) est issue de la sécurité du CFI (impossibilité de générer une clef dérivée sans la clef secrète maîtresse). Cette méthode permet, par exemple, de construire le schéma de signature de Boneh, Lynn et Shacham^[6] à partir du CFI de Boneh et Franklin.

Notes et références

1. Shamir 1984.
2. Diffie et Hellman 1976.
3. Libert et Stehlé 2015.
4. Cocks 2001.
5. Boneh et Franklin 2001.
6. Boneh, Lynn et Shacham 2001.

Annexes

Bibliographie

• [Boneh et Franklin 2001] (en) Dan Boneh et Matthew Franklin, « Identity based encryption from the Weil pairing », Crypto,‎ 2001 (lire en ligne)
• [Boneh, Lynn et Shacham 2001] (en) Dan Boneh, Ben Lynn et Hovav Shacham, « Short Signatures from the Weil Pairing », Asiacrypt,‎ 2001 (lire en ligne)
• [Cocks 2001] (en) Clifford Cocks, « An identity based encryption scheme based on quadratic residues », Cryptography and Coding,‎ 2001 (lire en ligne, consulté le 19 avril 2016).
• [Diffie et Hellman 1976] (en) Whitfield Diffie et Martin Hellman, « Multiuser cryptographic techniques », AFIPS,‎ 1976 (DOI 10.1145/1499799.1499815)
• [Neven et Joye 2008] (en) Gregory Neven et Marc Joye, Identity-Based Cryptography, Amsterdam, IOS Press, 2008, 263 p. (ISBN 978-1-58603-947-9, lire en ligne)
• [Shamir 1984] (en) Adi Shamir, « Identity-based cryptosystems and signature schemes », Crypto,‎ 1984 (lire en ligne, consulté le 19 avril 2016).

Articles connexes

• Cryptographie
• Cryptographie asymétrique
• RSA
• Dan Boneh
• Cryptographie à base de couplages

Liens externes

• (en) Benoît Libert et Damien Stehlé, « Cours de Cryptographie Avancée : IBE and Bilinear maps », septembre 2015

• Portail de la cryptologie
• Portail des mathématiques