Cryptosystème de Goldwasser-Micali

Un article de Wikipédia, l'encyclopédie libre.

En cryptographie, le cryptosystème de Goldwasser-Micali (GM) est un algorithme asymétrique de cryptographie à clé publique, développé par Shafi Goldwasser et Silvio Micali en 1982. Fait notoire, GM est le premier cryptosystème à chiffrement probabiliste qui est prouvablement sûr, avec des hypothèses cryptographiques standards. Toutefois, il n'est pas efficace : les textes chiffrés peuvent être des centaines de fois plus longs que les textes d'origine. Afin de prouver la sécurité de ce cryptosystème, ses auteurs ont proposé la définition de sécurité sémantique qui est, de nos jours, largement utilisée.

La preuve que le cryptosystème GM est sémantiquement sécure est basée sur l'hypothèse d'intractabilité du problème de la résiduosité quadratique modulo $N$ où $N = p q$ , avec $p, q$ de grands nombres premiers. En bref, ce problème se résout facilement lorsque la factorisation de $N$ est connue. D'autre part, n'importe quel parti du protocole peut générer de nouveaux résidus quadratiques, sans connaître la factorisation. Le cryptosystème GM utilise cette asymétrie en chiffrant les bits de messages en les associant avec des résidus ou non-résidus quadratiques, tous avec symbol de Jacobi de +1. Le receveur du message chiffré se sert de la factorisation de $N$ en tant que clé secrète et le déchiffre en testant la résiduosité quadratique des valeurs chiffrées reçues.

GM produit une valeur de grandeur approximative de $| N |$ pour chiffer un seul bit de message. C'est ainsi que le chiffrement par GM produit une importante expansion de texte chiffré. Pour se prémunir contre les attaques, il est recommandé que $N$ soit d'au moins quelques centaines de bits. Par conséquent, l'utlité de GM est pour démonter les concepts de chiffrement probabiliste et de sécurité sémantique. Depuis lors, d'autres cryptosystèmes prouvablement sûrs ont été développés, tel ElGamal.

Sommaire

1 Protocole

[modifier] Protocole

GM a trois parties: la génération de clés et le chiffrement sont des algorithmes probabilistes, tandis que le déchiffrement est un algorithme déterministe.

[modifier] Génération de clés

Le modulus $N$ est généré comme pour le cryptosystème RSA. (Voir RSA, Fonctionnement détaillé pour les détails.)

Alice génère deux grands nombres premiers $p \,$ et $q \,$ de telle sorte que $p \ne q$ et ce, de façon aléatoire et indépendante de l'un de l'autre.
Alice calcule $N = p q$ .
Elle trouve un non-résidu $z$ pour lequel le symbole de Jacobi est +1, par exemple, en générant des valeurs aléatoires et en les testant. Si $(p, q) \equiv 3$ mod $4$ (i.e., $N$ est un entier de Blum), alors le nombre $N - 1$ a cette propriété.

La clé publique est $(N, z)$ . La clé secrète est la factorisation $(p, q)$ .

[modifier] Chiffrement

Supposons que Bob veut envoyer un message m à Alice :

Bob encode $m$ comme une chaîne de bits $(m_0, \dots, m_n)$ .
Pour chaque bit $m i$ , Bob génère une valeur aléatoire $y$ moindre que $N$ . Il retourne la valeur de $c_i = y^2 z^{m_i}$ mod $N$ .

Bob envoie le texte chiffé : $(c_0, \dots, c_n)$ .

[modifier] Déchiffrement

Alice reçoit $(c_0, \dots, c_i)$ . Elle peut récupérer $m$ en utilisant la procédure suivante.

En utilisant la factorization $(p, q)$ , Alice détermine si la valeur $c i$ est un résidu quadratique; si c'est le cas, $m i = 0$ , autrement $m i = 1$ .