Goldwasser-Micali

Goldwasser-Micali

Cryptosystème de Goldwasser-Micali

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 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 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

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.

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.)

  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 de l'un de l'autre.
  2. Alice calcule N = pq.
  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

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 mi, 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

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

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

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

  • Portail de la cryptologie Portail de la cryptologie
Ce document provient de « Cryptosyst%C3%A8me de Goldwasser-Micali ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Goldwasser-Micali de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Goldwasser-Micali cryptosystem — The Goldwasser Micali cryptosystem (GM) is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public key encryption scheme which is provably… …   Wikipedia

  • Cryptosysteme de Goldwasser-Micali — Cryptosystème de Goldwasser Micali 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… …   Wikipédia en Français

  • Cryptosystème De Goldwasser-Micali — 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… …   Wikipédia en Français

  • Cryptosystème de goldwasser-micali — 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… …   Wikipédia en Français

  • Cryptosystème de Goldwasser-Micali — 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… …   Wikipédia en Français

  • Shafi Goldwasser — Infobox Scientist name = Shafrira Goldwasser image width = 150px caption = Shafrira Goldwasser birth date = 1958 birth place = death date = death place = residence = citizenship = nationality = ethnicity = field = Computer Science, Cryptography… …   Wikipedia

  • Blum-Goldwasser cryptosystem — The Blum Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum Goldwasser is a probabilistic, semantically secure cryptosystem with a constant size ciphertext expansion.… …   Wikipedia

  • Cryptosysteme de Blum-Goldwasser — Cryptosystème de Blum Goldwasser Le cryptosystème de Blum Goldwasser (BG) est un algorithme de chiffrement asymétrique proposé par Manuel Blum et Shafi Goldwasser en 1984. Blum Goldwasser est un cryptosystème probabilistique et sémantiquement sûr …   Wikipédia en Français

  • Cryptosystème De Blum-Goldwasser — Le cryptosystème de Blum Goldwasser (BG) est un algorithme de chiffrement asymétrique proposé par Manuel Blum et Shafi Goldwasser en 1984. Blum Goldwasser est un cryptosystème probabilistique et sémantiquement sûr avec une augmentation de taille… …   Wikipédia en Français

  • Cryptosystème de blum-goldwasser — Le cryptosystème de Blum Goldwasser (BG) est un algorithme de chiffrement asymétrique proposé par Manuel Blum et Shafi Goldwasser en 1984. Blum Goldwasser est un cryptosystème probabilistique et sémantiquement sûr avec une augmentation de taille… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”