Cryptosystème de Goldwasser-Micali

En cryptologie, le cryptosystème de Goldwasser-Micali est un cryptosystème développé par Shafi Goldwasser et Silvio Micali en 1982. Il s'agit du premier cryptosystème prouvé sûr dans le modèle standard, un progrès permis par l'introduction par Goldwasser et Micali de la notion actuelle de sécurité sémantique comme un jeu de sécurité, participant à la naissance de la sécurité prouvable en cryptologie moderne. Pour ces raisons, Goldwasser et Micali ont reçu le prestigieux prix Turing en 2012.

En dépit de ses mérites théoriques et de son importance dans l'histoire cryptologique récente, le cryptosystème de Goldwasser-Micali n'est pas utilisé en pratique : il est bien moins efficace que les alternatives et la sécurité sémantique seule est insuffisante pour de nombreuses applications.

Description

Syntaxe générale

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 $({\mathsf {sk}},{\mathsf {pk}})$constitué d'une clé privée et de la clé publique correspondante ;
• un algorithme de chiffrement, également probabiliste, 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.

Détail des algorithmes

Génération des clés cryptographiques

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

1. Deux nombres premiers $p$ et $q\,$distincts sont générés, on note $n=pq$. La taille de $p$ et $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 $z\in \mathbb {(} \mathbb {Z} /(n))^{\times }$ est trouvé dont les symboles de Jacobi par rapport à $p$ et à $q$ sont égaux à -1, c'est-à-dire qu'il ne s'agit pas d'un résidu quadratique modulo $p$ ni $q$.
3. L'algorithme retourne $({\mathsf {sk}}=p,{\mathsf {pk}}=\{n,z\})$.

Pour l'étape 2, il existe essentiellement deux méthodes. La première méthode consiste à tirer $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 $(p,q)\equiv 3$ mod $4$, ce qui garantit que $z=n-1$ convient.

Chiffrement d'un bit

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

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

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

Cette manière de faire est responsable de la faible bande passante du cryptosystème. L'indépendance entre chaque chiffrement permet également à un attaquant de réordonner les membres de $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).

Déchiffrement d'un bit

L'algorithme de déchiffrement de $c$ consiste en ceci :

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

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

Sécurité

La sécurité sémantique (IND-CPA) du cryptosystème de Goldwasser et Micali a été réduite, dans le modèle standard, à la difficulté du problème de la résiduosité quadratique modulo $n$ — c'est-à-dire l'hypothèse qu'il est difficile de déterminer si un nombre $c$ est un résidu quadratique modulo $n$. Cette preuve est historiquement la première de son genre et a participé à développer la notion de sécurité prouvable en cryptologie.

Lorsque la factorisation de $n$ est connue, le problème de la résiduosité est facile, c'est précisément ce que fait l'algorithme de déchiffrement décrit dans la section précédente. À l'heure actuelle (2018) il ne s'agit que d'une condition suffisante, et il n'est pas exclu qu'existe un algorithme efficace pour résoudre le problème de la résiduosité quadratique, bien qu'aucun ne soit aujourd'hui connu.

La meilleure attaque connue (en 2018) consiste ainsi à calculer la factorisation de $n$, ce qui détermine la manière de générer les clés pour cet algorithme : pour résister à un attaquant classique, $p$ et $q$ doivent être individuellement assez grands pour éviter une factorisation par ECM (ainsi $p\approx q$) et leur produit doit opposer assez de résistance aux meilleurs algorithmes génériques de factorisation, notamment le crible du corps de nombres. Pour un niveau de sécurité classique de 128 bits, cela correspond à $n\approx 2^{3072}$. Face à un attaquant quantique, l'algorithme de Shor donne la factorisation de $n$ en temps polynomial et il n'existe donc pas de paramètres rendant le cryptosystème sûr dans ce contexte.

Malléabilité et homomorphisme

Le cryptosystème de Goldwasser-Micali n'est pas sûr face à des modèles d'attaquants plus forts : il ne possède que la sécurité sématique (IND-CPA). En particulier, comme évoqué dans une section précédente il existe des attaques de malléabilités permettant à un adversaire de manipuler les chiffrés de façon indétectable. L'existence de telles attaques montre que le cryptosystème n'atteint pas la sécurité IND-CCA, c'est-à-dire qu'il est de manière générique vulnérable aux attaques à chiffré choisi. Ces observations sont bien sûr anachroniques, puisque les modèles correspondants ont été développés ultérieurement et précisément pour capturer les limites de ce système.

Un autre point de vue sur le même phénomène est que le cryptosystème de Goldwasser-Micali est partiellement homomorphe : si $m_{1},m_{2}$sont deux bits, chiffrés en $c_{1},c_{2}$respectivement, alors $c_{1}\times c_{2}{\bmod {n}}$déchiffre en $m_{1}\oplus m_{2}$. Autrement dit, la fonction ou exclusif est calculable homomorphiquement sur ce cryptosystème.