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 $m_{1}$ et $m_{2}$ , il est possible de calculer le chiffré de $m_{1}+m_{2}$ . 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 | modifier le code]

Génération des clefs[modifier | modifier le code]

Choisir deux nombres premiers de grande taille, indépendants et aléatoires : $p~$ et $q~$ ;
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[modifier | modifier le code]

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

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

Déchiffrement[modifier | modifier le code]

Pour retrouver le texte clair $m$ , on commence par remarquer que :

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

car

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

On obtient ainsi :

r=c^{N^{-1}{\bmod {\varphi }}(N)}\mod N.

D’où :

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

On remarque que le calcul de $r$ n'est possible qu’à l'aide de la clef privée ${\mathsf {sk}}=\varphi (N)$ , qui reste secrète sous l'hypothèse de la difficulté de la factorisation.

Homomorphisme[modifier | modifier le code]

Le cryptosystème de Paillier est un homomorphisme additif, c'est-à-dire qu’avec la clef publique, un chiffré $c_{1}={\mathsf {Chiffrer}}(m_{1})$ et un chiffré $c_{2}={\mathsf {Chiffrer}}(m_{2})$ , il est possible de construire un chiffré $c_{1+2}={\mathsf {Chiffrer}}(m_{1}+m_{2})$ sans connaître ni $m_{1}$ ni $m_{2}$ ^[3].

Cette opération s'effectue en multipliant $c_{1}$ et $c_{2}$ , ce qui mène à:

{\begin{aligned}c_{1}\cdot c_{2}&=(1+N)^{m_{1}}r_{1}^{N}\cdot (1+N)^{m_{2}}\cdot r_{2}^{N}{\bmod {N}}^{2}\\&=(1+N)^{m_{1}+m_{2}}(r_{1}\cdot r_{2})^{N}{\bmod {N}}^{2}\end{aligned}}

Qui correspond à un chiffré de $m_{1}+m_{2}$ sous l'aléa $r_{1}\cdot r_{2}$ .

Notes et références[modifier | modifier le code]

↑ Paillier 1999.
↑ Okamoto et Uchiyama 1998.
↑ Paillier 1999, Sec. 8. Properties.

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

[Okamoto et Uchiyama 1998] (en) 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] (en) 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])

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Portail de la cryptologie

[Paillier1999-1] Paillier 1999.

[OkamotoUchiyama1998-2] Okamoto et Uchiyama 1998.

[Paillier1999Sec._8._Properties-3] Paillier 1999, Sec. 8. Properties.

[1]

[2]

[3]