Le cryptosystème de Paillier est un cryptosystème basé sur un algorithme asymétrique conçu par Pascal Paillier en 1999. Son principe repose sur des travaux de Okamoto et Uchiyama présentés en 1998.
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 Génération des clefs 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 Soit un message à chiffrer avec . Soit , un entier aléatoire tel que (appelé l'aléa). Le chiffré est alors :
Déchiffrement Pour 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 Le 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 .
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
Annexes Bibliographie
Articles connexes Cryptographie asymétrique Chiffrement homomorphe Malléabilité
Liens externes Paillier's Cryptosystem Revisited Extensions to the Paillier Cryptosystem with Applications to Cryptological Protocols
Paillier, cryptosystème de Catégorie:Protocole cryptographique