Cryptosystème de Goldwasser-Micali

Cryptosystème à clé publique

En cryptologie, le cryptosystème de Goldwasser-Micali[1] est un cryptosystème développé par Shafi Goldwasser et Silvio Micali en 1982[2],[3]. 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é[4],[5], participant à la naissance de la sécurité prouvable en cryptologie moderne[6],[Note 1],[7]. Pour ces raisons, Goldwasser et Micali on reçu le prestigieux prix Turing en 2012[8],[9],[10].

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.

DescriptionModifier

Syntaxe généraleModifier

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  constitué d'une clé privée et de la clé publique correspondante ;
  • un algorithme de chiffrement, également probabiliste[Note 2], 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 algorithmesModifier

Génération des clés cryptographiquesModifier

La génération des clés est effectuée ainsi :

  1. Deux nombres premiers   et  distincts sont générés, on note  . La taille de   et   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   est trouvé dont les symboles de Jacobi par rapport à   et à   sont égaux à -1, c'est-à-dire qu'il ne s'agit pas d'un résidu quadratique modulo   ni  [Note 3].
  3. L'algorithme retourne  .

Pour l'étape 2, il existe essentiellement deux méthodes. La première méthode consiste à tirer   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   mod  , ce qui garantit que   convient[11],[12].

Chiffrement d'un bitModifier

Soit  un message d'un seul bit, c'est-à-dire  . Pour chiffrer ce message,

  1. L'algorithme tire uniformément un entier   dans  .
  2. L'algorithme retourne le message chiffré  

Pour chiffrer un message plus long, constitué de plusieurs bits, chaque bit est chiffré indépendamment[3]. Ainsi, si  , le message chiffré correspondant est  où chaque  est le chiffré de  .

Cette manière de faire est responsable de la faible bande passante du cryptosystème[Note 4]. L'indépendance entre chaque chiffrement permet également à un attaquant de réordonner les membres de   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 bitModifier

L'algorithme de déchiffrement de   consiste en ceci :

  1. Si   est un résidu quadratique modulo  , retourner 1. Sinon retourner 0.

Cette étape est efficace puisque l'algorithme de déchiffrement reçoit la clé privée  qui donne la factorisation de  [Note 5]. Si le chiffré correspond à un message de plusieurs bits,  , chaque  est déchiffré pour donner le bit  du message clair.

SécuritéModifier

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   — c'est-à-dire l'hypothèse qu'il est difficile de déterminer si un nombre  est un résidu quadratique modulo  . Cette preuve est historiquement la première de son genre et a participé à développer la notion de sécurité prouvable en cryptologie[6],[Note 6].

Lorsque la factorisation de   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[13].

La meilleure attaque connue (en 2018) consiste ainsi à calculer la factorisation de  , ce qui détermine la manière de générer les clés pour cet algorithme : pour résister à un attaquant classique,   et   doivent être individuellement assez grands pour éviter une factorisation par ECM (ainsi  ) 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 à  . Face à un attaquant quantique, l'algorithme de Shor donne la factorisation de   en temps polynomial et il n'existe donc pas de paramètres rendant le cryptosystème sûr dans ce contexte.

Malléabilité et homomorphismeModifier

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[6].

Un autre point de vue sur le même phénomène est que le cryptosystème de Goldwasser-Micali est partiellement homomorphe : si  sont deux bits, chiffrés en  respectivement, alors  déchiffre en  . Autrement dit, la fonction ou exclusif est calculable homomorphiquement sur ce cryptosystème[14],[15].

Notes et référencesModifier

NotesModifier

  1. 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).
  2. Un algorithme de chiffrement déterministe ne peut pas être sémantiquement sûr.
  3. Le symbole de Jacobi étant une fonction multiplicative, on a  .
  4. Pour chaque bit du chiffré on transmet   bit du message.
  5. L'algorithme classique consiste à calculer le symbole de Legendre modulo  et modulo  , ce qui requiert essentiellement l'algorithme d'Euclide.
  6. 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  et la factorisation de  . Voir (Dent 2008) pour une discussion.

RéférencesModifier

  1. (en) Kazue Sako, « Goldwasser-Micali encryption scheme », dans Henk C. A. van Tilborg, Encyclopedia of Cryptography and Security, Springer US, (ISBN 9780387234731, DOI 10.1007/0-387-23483-7_177, lire en ligne), p. 241–242
  2. (en) S. Goldwasser et S. Micali, « Probabilistic encryption and how to play mental poker keeping secret all partial information », dans STOC '82 Proceedings of the 14th annual ACM Symposium on Theory of Computing, , p. 365–377.
  3. a et b (en) S. Goldwasser et S. Micali, « Probabilistic encryption », J. Comput. Syst. Sci., vol. 28, no 2,‎ , p. 270-299 (DOI 10.1016/0022-0000(84)90070-9).
  4. (en) Jonathan Katz et Yehuda Lindell, Introduction to Modern Cryptography, 2nd Edition, Boca Raton, Chapman and Hall, , 583 p. (ISBN 978-1-4665-7026-9, lire en ligne), « Defining Computationally Secure Encryption ».
  5. (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).
  6. a b et c (en) Alexander W. Dent, « A Brief History of Provably-Secure Public-Key Encryption », dans Progress in Cryptology – AFRICACRYPT 2008, Springer Berlin Heidelberg, (ISBN 9783540681595, DOI 10.1007/978-3-540-68164-9_24, lire en ligne), p. 357–370
  7. (en) Shafi Goldwasser, « Mathematical foundations of modern cryptography: computational complexity perspective », arXiv:cs/0212055,‎ (lire en ligne, consulté le 24 août 2018)
  8. (en) « Shafi Goldwasser - A.M. Turing Award Laureate », sur amturing.acm.org (consulté le 24 août 2018)
  9. (en) « Silvio Micali - A.M. Turing Award Laureate », sur amturing.acm.org (consulté le 24 août 2018)
  10. (en) Association for Computing Machinery (ACM), « ACM Turing Award 2012 », sur youtube.com, (consulté le 24 août 2018)
  11. (en) Benjamin Justus, « The distribution of quadratic residues and non-residues in the Goldwasser–Micali type of cryptosystem », Journal of Mathematical Cryptology, vol. 8, no 2,‎ (ISSN 1862-2976 et 1862-2984, DOI 10.1515/jmc-2013-0001, lire en ligne, consulté le 24 août 2018)
  12. (en) Benjamin Justus, « The distribution of quadratic residues and non-residues in the Goldwasser–Micali type of cryptosystem. II », Journal of Mathematical Cryptology, vol. 9, no 2,‎ (ISSN 1862-2976 et 1862-2984, DOI 10.1515/jmc-2014-0004, lire en ligne, consulté le 24 août 2018)
  13. (en) René Peralta et Eiji Okamoto, « Some combinatorial problems of importance to cryptography », Proceedings of the IEICE 1996 Symposium on Cryptography and Information Security,‎ (lire en ligne)
  14. (en) Abbas Acar, Hidayet Aksu, A. Selcuk Uluagac et Mauro Conti, « A Survey on Homomorphic Encryption Schemes: Theory and Implementation », arXiv:1704.03578 [cs],‎ (lire en ligne, consulté le 24 août 2018)
  15. (en) Kun Peng, Colin Boyd et Ed Dawson, « A Multiplicative Homomorphic Sealed-Bid Auction Based on Goldwasser-Micali Encryption », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540290018, DOI 10.1007/11556992_27, lire en ligne), p. 374–388