Cryptosystème de Paillier
Le cryptosystème de Paillier est un cryptosystème basé sur un algorithme asymétrique conçu par Pascal Paillier en 1999[1]. Son principe repose sur des travaux de Okamoto et Uchiyama présentés en 1998[2].
Le système est un homomorphisme additif; en d'autres termes, avec la clef publique et les chiffrés de et , il est possible de calculer le chiffré de . Comme de plus ce chiffrement est prouvé sûr face à un attaquant passif, les chiffrés sont indistinguables, ce qui permet de remélanger un chiffré en rajoutant un chiffrement de zéro à un chiffré existant. Cette propriété est importante dans de nombreuses constructions visant à préserver la vie privée, étant donné qu'elle rend intraçable un message ainsi remélangé.
Fonctionnement
modifierGénération des clefs
modifier- Choisir deux nombres premiers de grande taille, indépendants et aléatoires : et ;
- Calculer la clef publique (un module RSA) et la clé privée .
Chiffrement
modifierSoit un message à chiffrer avec . Soit , un entier aléatoire tel que (appelé l'aléa). Le chiffré est alors :
Déchiffrement
modifierPour retrouver le texte clair , on commence par remarquer que :
car
On obtient ainsi :
D’où :
On remarque que le calcul de n'est possible qu’à l'aide de la clef privée , qui reste secrète sous l'hypothèse de la difficulté de la factorisation.
Homomorphisme
modifierLe cryptosystème de Paillier est un homomorphisme additif, c'est-à-dire qu’avec la clef publique, un chiffré et un chiffré , il est possible de construire un chiffré sans connaître ni ni [3].
Cette opération s'effectue en multipliant et , ce qui mène à:
Qui correspond à un chiffré de sous l'aléa .
Notes et références
modifier- Paillier 1999.
- Okamoto et Uchiyama 1998.
- Paillier 1999, Sec. 8. Properties.
Annexes
modifierBibliographie
modifier- [Okamoto et Uchiyama 1998] (en) Tatsuaki Okamoto et Shigenori Uchiyama, « A new public-key cryptosystem as secure as factoring », Eurocrypt, , p. 308–318 (DOI 10.1007/BFb0054135, lire en ligne)
- [Paillier 1999] (en) Pascal Paillier, « Public-Key Cryptosystems Based on Composite Degree Residuosity Classes », Eurocrypt, , p. 223–238 (DOI 10.1007/3-540-48910-X_16, lire en ligne [PDF])