Cryptosystème de Paillier

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 à la conférence EUROCRYPT.

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[modifier | modifier le code]

Génération de la clé[modifier | modifier le code]

  1. choisir deux nombres premiers de grande taille, indépendants et aléatoires : p~ et q~.
  2. calculer la clé publique N=pq~ et la clé privée \phi=(p-1)(q-1)~

Chiffrement[modifier | modifier le code]

Soit m~ un message à chiffrer avec 0\le 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[modifier | modifier le code]

Pour retrouver le texte clair m :

 c \equiv r^N \mod N

et

\begin{align} \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{align}

On obtient ainsi :

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

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

  1. Paillier 1999, p. 223-238.

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Pascal Paillier, « Public-Key Cryptosystems Based on Composite Degree Residuosity Classes », EUROCRYPT,‎ (lire en ligne [PDF])

Liens externes[modifier | modifier le code]