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 1999Modèle:Sfn. Son principe repose sur des travaux de Okamoto et Uchiyama présentés en 1998Modèle:Sfn.

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

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~$ (appelé l'aléa). Le chiffré est alors :

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

Déchiffrement

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

$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}{\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{\bmod {N}}=c^{r^{N^{-1}}{\bmod {\varphi }}(N)}{\bmod {N}}$ 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

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}$Modèle:Sfn.

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}$.

Annexes

Bibliographie

• Modèle:Article
• Modèle:Article

Articles connexes

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

Liens externes

• Modèle:En Paillier's Cryptosystem Revisited
• Modèle:En Extensions to the Paillier Cryptosystem with Applications to Cryptological Protocols