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. 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 uniquement la clé publique et le chiffrement de $m_{1}~$ et $m_{2}~$, il est possible de calculer le chiffrement de $m_{1}+m_{2}~$.

Fonctionnement

Génération des clefs

1. Choisir deux nombres premiers de grande taille, indépendants et aléatoires : $p~$ et $q~$;
2. Calculer la clef publique ${\mathsf {pk}}\triangleq N=p\cdot q$ (un module RSA) et la clé privée ${\mathsf {sk}}\triangleq \varphi (N)=(p-1)\cdot (q-1)~$.

Chiffrement

Soit $m~$ un message à chiffrer avec $0\leq m<N~$. Soit $r~$, un entier aléatoire tel que $0<r<N~$. Le chiffré est alors :

$c=(1+N)^{m}\cdot r^{N}\mod N^{2}$

Déchiffrement

Pour retrouver le texte clair $m$ :

$c\equiv r^{N}\mod N$

et

${\begin{aligned}{\frac {c}{r^{N}}}&=(1+N)^{m}\mod N^{2}\\&=1+m\cdot N+N^{2}+N^{2}\cdot \left(\sum _{i=2}^{m}{\binom {m}{i}}m^{i}N^{m-i-2}\right)\mod N^{2}\\&=1+m\cdot N\mod N^{2}\end{aligned}}$

On obtient ainsi :

$r=c^{N^{-1}\mod \phi }\mod N$

$m={\frac {(c\cdot r^{-N}\mod N^{2})-1}{N}}$

Annexes

Bibliographie

• [Okamoto et Uchiyama 1998] Tatsuaki Okamoto et Shigenori Uchiyama, « A new public-key cryptosystem as secure as factoring », Eurocrypt,‎ 1998, p. 308–318 (DOI 10.1007/BFb0054135, lire en ligne)
• [Paillier 1999] Pascal Paillier, « Public-Key Cryptosystems Based on Composite Degree Residuosity Classes », Eurocrypt,‎ 1999, p. 223–238 (DOI 10.1007/3-540-48910-X_16, lire en ligne [PDF])

Voir aussi

• Cryptographie asymétrique
• Chiffrement homomorphe
• Malléabilité

Liens externes

• (en) Paillier's Cryptosystem Revisited
• (en) Extensions to the Paillier Cryptosystem with Applications to Cryptological Protocols