Le chiffrement de Paillier

Introduction

Le cryptosystème de Paillier a été créé en 1999 par Pascal Paillier. Il s'agit également d'un chiffrement asymétrique. Il est homomorphe pour l'addition, c'est pourquoi il peut être utilisé dans le cadre du vote électronique.

Algorithme

1. Générer 2 grands nombres premiers, \(p\) et \(q\), de même taille et tel que leur produit \(N = p*q\) ait le nombre de bits requis.
2. Calculer \(N = p*q\) et \( \lambda = ppcm(p-1,q-1) \).
3. Choisir un entier aléatoire \(g\) tel que \( \mu = (L(g^\lambda \mod N^2))^{(-1)} \mod N \) existe.
4. Choisir \(r\) premier aléatoirement, de même nombre de bits que \( N \), tel que \(0 < r < N\).
5. Simplificaiton : comme \( p \) et \( q\) sont de longueur équivalente, on a :

   $$pgdc(pq, (p-1)(q-1)) = 1$$

   $$\lambda = ppcm(p-1,q-1) = (p-1)(q-1)$$

   $$g = 1 + N$$

   $$\mu = \lambda^{(-1)} \mod N$$

6. La clef publique est \( (g,N) \).
7. La clef privée est \( (\lambda, \mu, N) \).

Chiffrement

Le chiffré est $$ c = (1+N)^m * r^N \mod N^2 $$

Déchiffrement

Pour retrouver le texte original, il faut calculer : $$L : u \rightarrow (u-1)/ N$$ $$m = L(c^\lambda \mod N^2) * \mu \mod N$$

Homomorphisme pour l'addition

Paillier est homomorphe pour l'addition. Pour additionner deux messages chiffrés, il faut ici multiplier ces deux chiffrés. Lors du déchiffrement, nous obtenons bien la somme de nos messages d'origine.

$$c_1 * c_2 = (g)^{m_1} r_1^N * g^{m_2} * r_2^N \mod N^2\\ \Leftrightarrow c_1 * c_2 = (g)^{m_1 + m_2} * (r_1 * r_2)^N \mod N^2$$ $$ \Leftrightarrow D(c_1 * c_2) = L(g^{m_1 + m_2} * (r_1 * r_2)^N \mod N^2) * \mu \mod N \\ \Leftrightarrow D(c_1 * c_2) = m_1+m_2$$

Démonstration

+ Calculer

Résultats attendus

Génération de deux grands nombres premiers différents.

Calcul de \( N = p*q \) et \( \lambda = (p-1) * (q-1) \)

Calcul de \( \mu = \lambda^{-1} \mod N \) et \(g = n+1\).

Environnement chiffré

Chiffrement avec la clef publique avant l'envoi sur le cloud.

Opérations sur les chiffrés sur un cloud

Déchiffrement

Récupération des données du cloud et déchiffrement avec la clé privée.

Pour aller plus loin

Une implémentation du chiffrement de Paillier en Python:
https://github.com/mikeivanov/paillier.