Cryptosystème de Goldwasser-Micali

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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ûr est basée sur l'hypothèse d'intractabilité du problème de la résiduosité quadratique modulo NN=pq, 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 participant 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, dont le symbole de Jacobi vaut +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 de d'illustrer 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.

Protocole[modifier | modifier le code]

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.

Génération de clés[modifier | modifier le code]

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

  1. 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.
  2. Alice calcule N = p q.
  3. 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).

Chiffrement[modifier | modifier le code]

Supposons que Bob veut envoyer un message m à Alice :

  1. Bob encode m comme une chaîne de bits (m_0, \dots, m_n).
  2. 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).

Déchiffrement[modifier | modifier le code]

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

  1. En utilisant la factorisation (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.

Alice produit en sortie le message m = (m_0, \dots, m_n).