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

modifier

Génération des clefs

modifier
  1. Choisir deux nombres premiers de grande taille, indépendants et aléatoires : et ;
  2. Calculer la clef publique (un module RSA) et la clé privée .

Chiffrement

modifier

Soit un message à chiffrer avec . Soit , un entier aléatoire tel que (appelé l'aléa). Le chiffré est alors :

Déchiffrement

modifier

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

modifier

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 [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

Annexes

modifier

Bibliographie

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])

Articles connexes

modifier

Liens externes

modifier