Cryptosystème de Goldwasser-Micali

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Cet article ou une de ses sections doit être recyclé (mars 2015).

Une réorganisation et une clarification du contenu paraissent nécessaires. Discutez des points à améliorer en page de discussion ou précisez les sections à recycler en utilisant {{section à recycler}}.

Le cryptosystème de Goldwasser-Micali est un cryptosystème de cryptographie à clef publique, conçu par Shafi Goldwasser et Silvio Micali en 1982[1]. C’est le premier cryptosystème qui a été prouvé sûr sous des hypothèses cryptographiques standards : le problème de la résiduosité quadratique. Pour prouver la sécurité de ce cryptosystème, Goldwasser et Micali ont introduit la notion de sécurité sémantique, qui est toujours utilisée[2][3].

Il est à noter que la taille des chiffrés subit une expansion de taille de l’ordre de la taille de sa clef publique (2048 bits[4]), ce qui la rend inutilisable en pratique.

Description[modifier | modifier le code]

Le cryptosystème de Goldwasser et Micali est un schéma de chiffrement, il est donc constitué de trois algorithmes: la génération des clés et le chiffrement sont des algorithmes probabilistes, tandis que le déchiffrement est un algorithme déterministe.

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

Le module 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 et de telle sorte que et ce, de façon aléatoire et indépendante.
  2. Alice calcule .
  3. Elle trouve un non-résidu pour lequel le symbole de Jacobi est +1, par exemple, en générant des valeurs aléatoires et en les testant. Si mod (i.e., est un entier de Blum), alors le nombre a cette propriété.

La clé publique est . La clé secrète est la factorisation .

Chiffrement[modifier | modifier le code]

Supposons que Bob veut envoyer un message m à Alice :

  1. Bob encode comme une chaîne de bits .
  2. Pour chaque bit , Bob génère une valeur aléatoire moindre que . Il retourne la valeur de mod .

Bob envoie le texte chiffré : .

Déchiffrement[modifier | modifier le code]

Alice reçoit . Elle peut récupérer en utilisant la procédure suivante :

  1. En utilisant la factorisation , Alice détermine si la valeur est un résidu quadratique; si c'est le cas, , autrement .

Alice produit en sortie le message .

Sécurité[modifier | modifier le code]

La preuve que le cryptosystème de Goldwasser et Micali est sémantiquement sûr se construit sur l'hypothèse de difficulté du problème de la résiduosité quadratique modulo , avec de grands nombres premiers. Ce problème se résout facilement lorsque la factorisation de est connue, et difficilement autrement. D'autre part, n'importe quel participant du protocole peut générer de nouveaux résidus quadratiques, sans connaître la factorisation. Ce cryptosystème 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 destinataire du message chiffré utilise alors la factorisation de en tant que clé secrète et déchiffre le message en testant la résiduosité quadratique des valeurs chiffrées reçues.

Le cryptosystème ayant été conçu pour être prouvé, la réduction de sécurité est assez directe. En supposant un adversaire (algorithme) adversaire contre le cryptosystème, il peut être utilisé pour tester la résiduosité modulo N d’un nombre x en attaquant le cryptosystème pour la clef publique (N, x). Ainsi si x n’est pas un résidu quadratique, alors le cryptosystème fonctionne correctement, et donc l’attaquant aussi. En revanche si x est un carré modulo N, alors les chiffrés seront composés uniquement de carrés aléatoires (en raison de la distribution de ), et l’attaquant ne peut gagner avec une probabilité significativement différente de 1/2. Ce qui prouve que le cryptosystème de Goldwasser et Micali est au moins aussi difficile à casser que le problème de la résiduosité quadratique.

Efficacité[modifier | modifier le code]

Le cryptosystème de Goldwasser et Micali produit un chiffré de taille . 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 soit d'au moins quelques centaines de bits (2048 en 2016).

Ce cryptosystème a été développé pour illustrer les concepts de chiffrement probabiliste (en) et de sécurité sémantique. Depuis lors, d'autres cryptosystèmes prouvés sûrs ont été développés, comme le chiffrement ElGamal.

Notes et références[modifier | modifier le code]

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • [Choi et al. 2008] (en) Seung Geol Choi, Dana Dachman-Soled, Tal Malkin et Hoeteck Wee, « Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One », Theory of Cryptography Conference (TCC),‎ (DOI 10.1007/978-3-540-78524-8_24, lire en ligne)
  • [Goldwasser et Micali 1982] (en) Shafi Goldwasser et Silvio Micali, « Probabilistic Encryption », Journal of Computer and System Science,‎ (DOI 10.1016/0022-0000(84)90070-9)
  • [Katz et Lindell 2014] (en) Jonathan Katz et Yehuda Lindell, Introduction to Modern Cryptography, 2nd Edition, Chapman and Hall, (ISBN 978-1466570269), « Section 3.2 (en)A Definition of Computationally-Secure Encryption. »

Articles connexes[modifier | modifier le code]