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 $𝗉𝗄\triangleq N=p\cdot q$ (un module RSA) et la clé privée $𝗌𝗄\triangleq \phi (N)=(p-1)\cdot (q-1)$.

Chiffrement

Soit $m$ un message à chiffrer avec $0\le 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}modN,$

car

$\begin{array}{cc}\frac{c}{r^N}& =(1+N{)}^{m}mod{N}^2\\ & =1+m\cdot N+N^2\cdot \left(\sum _{i=2}^m(\genfrac{}{}{0ex}{}{m}{i})N^{i-2}\right)mod{N}^2\\ & =1+m\cdot Nmod{N}^2.\end{array}$

On obtient ainsi :

$r=c^{N^{-1}mod\phi (N)}modN.$

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 $𝗌𝗄=\phi (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=𝖢𝗁𝗂𝖿𝖿𝗋𝖾𝗋(m_1)$ et un chiffré $c_2=𝖢𝗁𝗂𝖿𝖿𝗋𝖾𝗋(m_2)$, il est possible de construire un chiffré $c_{1+2}=𝖢𝗁𝗂𝖿𝖿𝗋𝖾𝗋(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{array}{cc}{c}_1\cdot c_2& =(1+N{)}^{m_1}{r}_1^N\cdot (1+N{)}^{m_2}\cdot r_2^N{modN}^2\\ & =(1+N{)}^{m_1+m_2}(r_1\cdot r_2{)}^N{modN}^2\end{array}$

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