Cryptosystème de Goldwasser-Micali

Le cryptosystème de Goldwasser et Micali est un schéma de chiffrement à clé publique : il est constitué de trois algorithmes :

• un algorithme de génération des clés, probabiliste, qui prend en entrée un paramètre de sécurité et retourne un couple ${\displaystyle ({\mathsf {sk}},{\mathsf {pk}})}$constitué d'une clé privée et de la clé publique correspondante ;
• un algorithme de chiffrement, également probabiliste[Note 2], qui prend en entrée le paramètre de sécurité, un message clair, et une clé publique, et retourne un message chiffré ;
• et un algorithme de déchiffrement, déterministe, qui prend en entrée le paramètre de sécurité, un message chiffré, et une clé privée, et retourne un message.

La génération des clés est effectuée ainsi :

1. Deux nombres premiers ${\displaystyle p}$ et ${\displaystyle q\,}$distincts sont générés, on note ${\displaystyle n=pq}$. La taille de ${\displaystyle p}$ et ${\displaystyle q}$ est déterminée en fonction du paramètre de sécurité à partir de la preuve de sécurité (voir plus bas).
2. Un entier ${\displaystyle z\in \mathbb {(} \mathbb {Z} /(n))^{\times }}$ est trouvé dont les symboles de Jacobi par rapport à ${\displaystyle p}$ et à ${\displaystyle q}$ sont égaux à -1, c'est-à-dire qu'il ne s'agit pas d'un résidu quadratique modulo ${\displaystyle p}$ ni ${\displaystyle q}$[Note 3].
3. L'algorithme retourne ${\displaystyle ({\mathsf {sk}}=p,{\mathsf {pk}}=\{n,z\})}$.

Pour l'étape 2, il existe essentiellement deux méthodes. La première méthode consiste à tirer ${\displaystyle z}$ au hasard, et vérifier ses symbole de Jacobi ; en principe, un nombre sur quatre possède la propriété recherchée. La seconde méthode consiste à fixer ${\displaystyle (p,q)\equiv 3}$ mod ${\displaystyle 4}$, ce qui garantit que ${\displaystyle z=n-1}$ convient[11] - [12].

Soit ${\displaystyle m}$un message d'un seul bit, c'est-à-dire ${\displaystyle m\in \{0,1\}}$. Pour chiffrer ce message,

1. L'algorithme tire uniformément un entier ${\displaystyle y}$ dans ${\displaystyle (\mathbb {Z} /(n))^{\times }}$.
2. L'algorithme retourne le message chiffré ${\displaystyle c=z^{m}y^{2}{\bmod {n}}}$

Pour chiffrer un message plus long, constitué de plusieurs bits, chaque bit est chiffré indépendamment[3]. Ainsi, si ${\displaystyle m=(m_{1},\dotsc ,m_{k})\in \{0,1\}^{k}}$, le message chiffré correspondant est ${\displaystyle c=(c_{1},\dotsc ,c_{k})\in \mathbb {(} \mathbb {Z} /(n))^{k}}$où chaque ${\displaystyle c_{i}}$est le chiffré de ${\displaystyle m_{i}}$.

Cette manière de faire est responsable de la faible bande passante du cryptosystème[Note 4]. L'indépendance entre chaque chiffrement permet également à un attaquant de réordonner les membres de ${\displaystyle c}$ sans jamais déchiffrer : il s'agit d'une vulnérabilité de malléabilité, qui n'est pas capturée par le modèle de sécurité sémantique (voir discussion plus bas).

L'algorithme de déchiffrement de ${\displaystyle c}$ consiste en ceci :

1. Si ${\displaystyle c}$ est un résidu quadratique modulo ${\displaystyle n}$, retourner 1. Sinon retourner 0.

Cette étape est efficace puisque l'algorithme de déchiffrement reçoit la clé privée ${\displaystyle {\mathsf {sk}}}$qui donne la factorisation de ${\displaystyle n}$[Note 5]. Si le chiffré correspond à un message de plusieurs bits, ${\displaystyle c=(c_{1},\dotsc ,c_{k})}$, chaque ${\displaystyle c_{i}}$est déchiffré pour donner le bit ${\displaystyle m_{i}}$du message clair.