title: Cryptosystème de Paillier
text: # 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 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
  
  * 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
  
  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,$
  
  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
  
  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}$.
  
  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}$.
  
  