Étude sur les échanges de clés multipartites Diffie-Hellman
Attention : cette page contient des formules en LaTeX qui ne sont pas correctement supportées sur le site web, pour une meilleure expérience veuillez consultez la page sur Github.
- 3PBDH
La cryptographie asymétrique permet d'assurer la confidentialité et l'authenticité des échanges entre deux ou plusieurs partis. Pour cela, chaque utilisateur possède une clé publique qu'il peut divulguer publiquement et une clé privée grâce à laquelle il assure être l'origine des messages qu'il envoie. Un message chiffré à l'aide d'une clé privée peut être déchiffré par tout le monde grâce à la clé publique correspondante prouvant l'authenticité du message, un message chiffré avec une clé publique ne peut être déchiffré qu'avec la clé privée assurant la confidentialité.
En pratique, le chiffrement asymétrique est assez couteux en énergie et en temps de calcul, on préfère donc la cryptographique symétrique, à l'aide d'une clé partagée entre les utilisateurs créée à partir de leurs clés privées et publiques. Le processus de création de cette clé partagée assure que la confidentialité et l'authenticité sont conservées.
Cette création de clé partagée fonctionne très bien avec deux utilisateurs, c'est la méthode utilisée dans le monde entier pour sécuriser les échanges notamment sur Internet via HTTPS.
Mais dans le cas d'un échange chiffré de bout en bout sur une application de messagerie instantanée où trois utilisateurs ou plus souhaitent créer une telle clé, le processus ne fonctionne pas. Il faut alors avoir recours soit à du chiffrement asymétrique coûteux, soit à du chiffrement symétrique entre chaque paire d'utilisateurs ce qui multiplie les chiffrements, soit à la signature tour à tour de la clé par chaque utilisateur.
Il n'existe pas de protocole qui permette la création d'une clé partagée symétrique entre trois partis ou plus en un seul tour à partir de la clé privée d'un utilisateur et des clés publiques de tous les autres.
L'échange de clés Diffie-Hellman permet de créer une clé partagée à partir d'une clé privée, de la clé publique de l'autre utilisateur et de paramètres définis au préalable. Cet échange repose sur la méthode de chiffrement RSA, qui utilise la congruence des nombres entiers et la difficulté algorithmique de la décomposition en facteurs premiers.
Le calcul de la clé partagée fonctionne de la manière suivante : soient
Depuis plusieurs années, le chiffrement asymétrique est plutôt réalisé grâce à la cryptographie sur les courbes elliptiques (Elliptic Curve Cryptography ou ECC) qui a progressivement remplacé le chiffrement RSA grâce ses clés bien plus courtes. Une courbe elliptique est un ensemble de points qui font partie de la courbe d'équation
Dans la cryptographie sur les courbes elliptiques, les clés publiques sont des points de la courbe tandis que les clés privées sont des scalaires, c'est-à-dire des nombres entiers. Le calcul de clé partagée fonctionne ainsi : soient
En pratique, les courbes utilisées sont des courbes elliptiques sur corps finis, car les calculs y sont réalisés modulo
Une démonstration est disponible dans demo.py
, qui va choisir des clés privées aléatoires pour Alice, Bob et Charlie et calculer les clés partagées du point de vue de chacun d'entre eux avec la cryptographie RSA et sur les courbes elliptiques. Les calculs sur les courbes elliptiques sont fait en important classes.py
, qui peut aussi être exécuté seul.
Les options sont disponibles avec python3 demo.py --help
:
usage: demo.py [-h] [-v] [-p PRIME] [-g NUM] [-a NUM] [-b NUM] [-m NUM] [-c] [-d] [-P]
options:
-h, --help show this help message and exit
-v, --version show program's version number and exit
-p PRIME, --prime PRIME
prime number used for modulo in RSA and Finite fields ECC
-g NUM, --generator NUM
number used for Diffie-Hellman exchange
-a NUM coefficient a of the Weierstrass form
-b NUM coefficient b of the Weierstrass form
-m NUM, --max-key NUM
maximum value for random private key generation
-c, --continuous run the regular Elliptic Curve take quite a long
-d, --debug print additionnal information
-P, --plot plot graph with curve and points
Par défault, l'exécution ne prend pas en compte le calcul sur courbe elliptique sans corps finis. Pour cela, il faut utiliser l'option --continuous
et il est conseillé de réduire la valeur maximale possible des clés privées à l'aide de --max-key
pour diminuer considérablement le temps d'exécution.
Le but de cette implémentation est de montrer de manière non rigoureuse que RSA et les courbes elliptiques ne permettent pas de créer des clés identiques au delà de deux partis.
La cryptographie à base de couplage (Pairing Based Cryptography ou PBC) utilise des courbes elliptiques ainsi qu'une fonction entre ces courbes appelée couplage
Le calcul de la clé partagée fonctionne de la manière suivante : soient
Si le couplage n'est pas symétrique, alors Alice, Bob et Charlie doivent se mettre d'accord sur deux points
$P_1\in G_1$ et$P_2\in G_2$ . Ils calculent et divulguent alors deux clés publiques chacun, une sur chaque courbe. Cela ne change pas le calcul de la clé partagée.
Pour construire un couplage à partir d'une courbe elliptique sur corps fini, il existe différentes méthodes.
Note : section incomplète
Soit
Soit
Pour généraliser le cas à trois partis avec
Dans le cas d'usage d'une application de messagerie instantanée, cette méthode implique que le couplage nécessaire à l'échange de la clé partagée doit être recalculé à chaque fois qu'un utilisateur entre ou sort de la conversation. Alternativement, un ensemble de couplages peut être prédéfini pour
Que ce soit grâce à la cryptographie à base de couplage ou autrement, la méthode de calcul de clé partagée doit encore être trouvée, prouvée et implémentée pour la généralisation à
En l'absence de généralisation à
-
clé partagée aléatoire créé par un utilisateur maître
- point négatif : la clé partagée est envoyée, il suffirait de casser le chiffrement d'un message pour compromettre toute la sécurité
- point négatif : la clé partagée est envoyée plusieurs fois avec différents chiffrements, ce qui peut faciliter une attaque
- point négatif : la clé partagée est créée par un seul utilisateur, auquel les autres doivent faire confiance et dont la génération de nombre aléatoires pourrait être défaillante
- point positif : la procédure ne prend qu'un seul tour, les messages sont envoyés en parallèle
-
point positif : le faible nombre de messages,
$n-1$ pour$n$ utilisateurs - point positif : la procédure n'a pas besoin d'être réalisée de nouveau lors de l'ajout d'un nouvel utilisateur
- point positif : l'ajout d'un nouvel utilisateur peut être fait de manière synchrone par un seul utilisateur
-
clé partagée aléatoire créée conjointement par tous les utilisateurs
- point négatif : la clé partagée est envoyée, il suffirait de casser le chiffrement de quelques messages pour compromettre toute la sécurité
-
point négatif : le très grand nombre de messages,
$n(n-1)$ pour$n$ utilisateurs - point négatif : l'ajout d'un nouvel utilisateur doit être fait de manière synchrone par tous les utilisateurs
- point positif : la clé partagée est créée à partir de tous les utilisateurs
- point positif : la procédure ne prend qu'un seul tour, les messages sont envoyés en parallèle
- point positif : la procédure n'a pas besoin d'être réalisée de nouveau lors de l'ajout d'un nouvel utilisateur
-
signature successive de la clé partagée coordonnée par un utilisateur maître
- point négatif : la clé partagée est envoyée, il suffirait de casser le chiffrement d'un message pour compromettre toute la sécurité
-
point négatif : le grand nombre de messages,
$3n-5$ pour$n$ utilisateurs - point négatif : certains utilisateurs connaissent des clés partagées desquelles ils ne font pas partie, exemple B connait la clé entre A et D
- point négatif : l'ajout d'un nouvel utilisateur doit être fait de manière synchrone par tous les utilisateurs
- point positif : la clé partagée est créée à partir de tous les utilisateurs
-
échanges de clés Diffie-Hellman circulaires
- point négatif : de nombreux utilisateurs connaissent des clés partagées desquelles ils ne font pas partie, exemple B connait la clé entre A et D
-
point négatif : le très grand nombre de messages,
$n(n-2)$ pour$n$ utilisateurs - point négatif : l'ajout d'un nouvel utilisateur doit être fait de manière synchrone par tous les utilisateurs
- point positif : la clé partagée est créée à partir de tous les utilisateurs
- point positif : la clé partagée finale n'est pas envoyée
Ces quatre solutions, la clé partagée aléatoire créé par un utilisateur maître, la clé partagée aléatoire créée conjointement par tous les utilisateurs, la signature successive de la clé partagée coordonnée par un utilisateur maître et les échanges de clés Diffie-Hellman circulaires peuvent probablement utiliser la cryptographie à base de couplage afin de réduire le nombre d'échanges nécessaires.
Cependant, tant qu'il y aura strictement plus de trois utilisateurs et que la cryptographie à base de couplage ou autre cryptographie ne permet pas de généralisation à
- Elliptic Curves as Python Objects - Jeremy Kun
- Elliptic Curve Cryptography - Daniel Volya
- Elliptic Curves over Finite Field - RareSkills
- Elliptic Curves over Finite Fields - Sascha Grau
- Crypto Stack Exchange - ECDH for more than two parties
- YouTube - Pairing-based Cryptography
- Pairing-Based Cryptography Lecture - Ran Canetti and Ron Rivest
- Introduction to Pairings - Diego F. Aranha
- Implement all the pairings in software! - Diego F. Aranha
- Bilinear Pairings - Ben Lynn
- The Tate Pairing - Ben Lynn
- Joux, Antoine. "The Weil and Tate Pairings as Building Blocks for Public Key Cryptosystems: Survey." International Algorithmic Number Theory Symposium. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002.
- Joux, Antoine. "A one round protocol for tripartite Diffie–Hellman." Journal of cryptology 17.4 (2004): 263-276.
- Cohn-Gordon, Katriel, et al. "On ends-to-ends encryption: Asynchronous group messaging with strong security guarantees." Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018.
- Ma, Fermi, and Mark Zhandry. "Encryptor combiners: a unified approach to multiparty nike,(h) ibe, and broadcast encryption." Cryptology ePrint Archive (2017).
- Boneh, Dan, and Mark Zhandry. "Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation." Algorithmica 79 (2017): 1233-1285.
- Boneh, Dan, and Alice Silverberg. "Applications of multilinear forms to cryptography." Contemporary Mathematics 324.1 (2003): 71-90.
- Alamati, Navid, Hart Montgomery, and Sikhar Patranabis. "Multiparty Noninteractive Key Exchange from Ring Key-Homomorphic Weak PRFs." Cryptographers’ Track at the RSA Conference. Cham: Springer International Publishing, 2023.