Cryptosystème de Goldwasser-Micali

En cryptologie, le cryptosystème de Goldwasser-Micali<ref>Modèle:Chapitre</ref> est un cryptosystème développé par Shafi Goldwasser et Silvio Micali en 1982<ref>Modèle:Chapitre.</ref><ref name=":0">Modèle:Article.</ref>. 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é<ref>Modèle:Ouvrage.</ref><ref>Modèle:Article.</ref>, participant à la naissance de la sécurité prouvable en cryptologie moderne<ref name=":1">Modèle:Chapitre</ref><ref group="Note">D'après (Dent 2008), le cryptosystème de Rabin et celui de Goldwasser-Micali sont responsables de la prise de conscience, dans les années 1990, de la nécessité de formaliser (et prouver) la sécurité des schémas cryptographiques. Voir aussi (Goldwasser 2002).</ref><ref>Modèle:Article</ref>. Pour ces raisons, Goldwasser et Micali ont reçu le prestigieux prix Turing en 2012<ref>Modèle:Lien web</ref><ref>Modèle:Lien web</ref><ref>Modèle:Lien web</ref>.

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 <math>(\mathsf{sk}, \mathsf{pk})</math>constitué d'une clé privée et de la clé publique correspondante ;
• un algorithme de chiffrement, également probabiliste<ref group="Note">Un algorithme de chiffrement déterministe ne peut pas être sémantiquement sûr.</ref>, 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 <math>p</math> et <math>q \,</math>distincts sont générés, on note <math>n = pq</math>. La taille de <math>p</math> et <math>q</math> 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 <math>z \in \mathbb (\mathbb Z/(n))^\times</math> est trouvé dont les symboles de Jacobi par rapport à <math>p</math> et à <math>q</math> sont égaux à -1, c'est-à-dire qu'il ne s'agit pas d'un résidu quadratique modulo <math>p</math> ni <math>q</math><ref group="Note">Le symbole de Jacobi étant une fonction multiplicative, on a <math>\left( \frac{z}{n} \right) = \left( \frac{z}{p} \right)\left( \frac{z}{q} \right) = +1</math>.</ref>.
3. L'algorithme retourne <math>(\mathsf{sk} = p, \mathsf{pk} = \{n, z\})</math>.

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

Chiffrement d'un bit

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

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

Pour chiffrer un message plus long, constitué de plusieurs bits, chaque bit est chiffré indépendamment<ref name=":0" />. Ainsi, si <math>m = (m_1, \dotsc, m_k) \in \{0, 1\}^k</math>, le message chiffré correspondant est <math>c = (c_1, \dotsc, c_k) \in \mathbb (\mathbb Z/(n))^k</math>où chaque <math>c_i</math>est le chiffré de <math>m_i</math>.

Cette manière de faire est responsable de la faible bande passante du cryptosystème<ref group="Note">Pour chaque bit du chiffré on transmet <math>1/\log_2 n</math> bit du message.</ref>. L'indépendance entre chaque chiffrement permet également à un attaquant de réordonner les membres de <math>c</math> 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 <math>c</math> consiste en ceci :

1. Si <math>c</math> est un résidu quadratique modulo <math>n</math>, retourner 1. Sinon retourner 0.

Cette étape est efficace puisque l'algorithme de déchiffrement reçoit la clé privée <math>\mathsf{sk}</math>qui donne la factorisation de <math>n</math><ref group="Note">L'algorithme classique consiste à calculer le symbole de Legendre modulo <math>p</math>et modulo <math>q</math>, ce qui requiert essentiellement l'algorithme d'Euclide.</ref>. Si le chiffré correspond à un message de plusieurs bits, <math>c = (c_1, \dotsc, c_k) </math>, chaque <math>c_i</math>est déchiffré pour donner le bit <math>m_i</math>du message clair.

Sécurité

Modèle:Article détaillé 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 <math>n</math> — c'est-à-dire l'hypothèse qu'il est difficile de déterminer si un nombre <math>c</math> est un résidu quadratique modulo <math>n</math>. Cette preuve est historiquement la première de son genre et a participé à développer la notion de sécurité prouvable en cryptologie<ref name=":1" /><ref group="Note">Le cryptosystème de Rabin (1979) précède de quelques années celui de Goldwasser-Micali, et a été présenté avec une preuve de l'équivalence entre le calcul de racines carrées modulo <math>n</math>et la factorisation de <math>n</math>. Voir (Dent 2008) pour une discussion.</ref>.

Lorsque la factorisation de <math>n</math> 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<ref>Modèle:Article</ref>.

La meilleure attaque connue (en 2018) consiste ainsi à calculer la factorisation de <math>n</math>, ce qui détermine la manière de générer les clés pour cet algorithme : pour résister à un attaquant classique, <math>p</math> et <math>q</math> doivent être individuellement assez grands pour éviter une factorisation par ECM (ainsi <math>p \approx q</math>) 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 à <math>n \approx 2^{3072}</math>. Face à un attaquant quantique, l'algorithme de Shor donne la factorisation de <math>n</math> 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<ref name=":1" />.

Un autre point de vue sur le même phénomène est que le cryptosystème de Goldwasser-Micali est partiellement homomorphe : si <math>m_1, m_2</math>sont deux bits, chiffrés en <math>c_1, c_2</math>respectivement, alors <math>c_1 \times c_2 \bmod n</math>déchiffre en <math>m_1 \oplus m_2</math>. Autrement dit, la fonction ou exclusif est calculable homomorphiquement sur ce cryptosystème<ref>Modèle:Article</ref><ref>Modèle:Chapitre</ref>.

Notes et références

Notes

<references group="Note"/>

Références

<references/>