Cryptosystème de Goldwasser-Micali

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

Description

Syntaxe générale

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 ${\displaystyle ({\mathsf {sk}},{\mathsf {pk}})}$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 algorithmes

Génération des clés cryptographiques

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

1. Deux nombres premiers ${\displaystyle p}$ et ${\displaystyle q\,}$distincts sont générés, on note ${\displaystyle n=pq}$. La taille de ${\displaystyle p}$ et ${\displaystyle q}$ 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 ${\displaystyle z\in \mathbb {(} \mathbb {Z} /(n))^{\times }}$ est trouvé dont les symboles de Jacobi par rapport à ${\displaystyle p}$ et à ${\displaystyle q}$ sont égaux à -1, c'est-à-dire qu'il ne s'agit pas d'un résidu quadratique modulo ${\displaystyle p}$ ni ${\displaystyle q}$^{[Note 3]}.
3. L'algorithme retourne ${\displaystyle ({\mathsf {sk}}=p,{\mathsf {pk}}=\{n,z\})}$.

Pour l'étape 2, il existe essentiellement deux méthodes. La première méthode consiste à tirer ${\displaystyle z}$ 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 ${\displaystyle (p,q)\equiv 3}$ mod ${\displaystyle 4}$, ce qui garantit que ${\displaystyle z=n-1}$ convient^[11],[12].

Chiffrement d'un bit

Soit ${\displaystyle m}$ un message d'un seul bit, c'est-à-dire ${\displaystyle m\in \{0,1\}}$. Pour chiffrer ce message,

1. L'algorithme tire uniformément un entier ${\displaystyle y}$ dans ${\displaystyle (\mathbb {Z} /(n))^{\times }}$.
2. L'algorithme retourne le message chiffré ${\displaystyle c=z^{m}y^{2}{\bmod {n}}}$

Pour chiffrer un message plus long, constitué de plusieurs bits, chaque bit est chiffré indépendamment^[3]. Ainsi, si ${\displaystyle m=(m_{1},\dotsc ,m_{k})\in \{0,1\}^{k}}$, le message chiffré correspondant est ${\displaystyle c=(c_{1},\dotsc ,c_{k})\in \mathbb {(} \mathbb {Z} /(n))^{k}}$où chaque ${\displaystyle c_{i}}$est le chiffré de ${\displaystyle m_{i}}$.

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 ${\displaystyle c}$ 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 bit

L'algorithme de déchiffrement de ${\displaystyle c}$ consiste en ceci :

1. Si ${\displaystyle c}$ est un résidu quadratique modulo ${\displaystyle n}$, retourner 1. Sinon retourner 0.

Cette étape est efficace puisque l'algorithme de déchiffrement reçoit la clé privée ${\displaystyle {\mathsf {sk}}}$qui donne la factorisation de ${\displaystyle n}$^{[Note 5]}. Si le chiffré correspond à un message de plusieurs bits, ${\displaystyle c=(c_{1},\dotsc ,c_{k})}$, chaque ${\displaystyle c_{i}}$est déchiffré pour donner le bit ${\displaystyle m_{i}}$du message clair.

Sécurité

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 ${\displaystyle n}$ — c'est-à-dire l'hypothèse qu'il est difficile de déterminer si un nombre ${\displaystyle c}$ est un résidu quadratique modulo ${\displaystyle n}$. 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 ${\displaystyle n}$ 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 ${\displaystyle n}$, ce qui détermine la manière de générer les clés pour cet algorithme : pour résister à un attaquant classique, ${\displaystyle p}$ et ${\displaystyle q}$ doivent être individuellement assez grands pour éviter une factorisation par ECM (ainsi ${\displaystyle p\approx q}$) 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 à ${\displaystyle n\approx 2^{3072}}$. Face à un attaquant quantique, l'algorithme de Shor donne la factorisation de ${\displaystyle n}$ en temps polynomial et il n'existe donc pas de paramètres rendant le cryptosystème sûr dans ce contexte.

Malléabilité et homomorphisme

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 ${\displaystyle m_{1},m_{2}}$sont deux bits, chiffrés en ${\displaystyle c_{1},c_{2}}$respectivement, alors ${\displaystyle c_{1}\times c_{2}{\bmod {n}}}$déchiffre en ${\displaystyle m_{1}\oplus m_{2}}$. Autrement dit, la fonction ou exclusif est calculable homomorphiquement sur ce cryptosystème^[14],[15].

Notes et références

Notes

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 ${\displaystyle \left({\frac {z}{n}}\right)=\left({\frac {z}{p}}\right)\left({\frac {z}{q}}\right)=+1}$.
4. Pour chaque bit du chiffré on transmet ${\displaystyle 1/\log _{2}n}$ bit du message.
5. L'algorithme classique consiste à calculer le symbole de Legendre modulo ${\displaystyle p}$et modulo ${\displaystyle q}$, 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 ${\displaystyle n}$et la factorisation de ${\displaystyle n}$. Voir (Dent 2008) pour une discussion.

Références

1. (en) Kazue Sako, « Goldwasser-Micali encryption scheme », dans Henk C. A. van Tilborg, Encyclopedia of Cryptography and Security, Springer US, 2005 (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, 1982, p. 365–377.
3. (en) S. Goldwasser et S. Micali, « Probabilistic encryption », J. Comput. Syst. Sci., vol. 28, n^o 2,‎ 1984, 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, 2014, 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),‎ 2008 (DOI 10.1007/978-3-540-78524-8_24, lire en ligne).
6. (en) Alexander W. Dent, « A Brief History of Provably-Secure Public-Key Encryption », dans Progress in Cryptology – AFRICACRYPT 2008, Springer Berlin Heidelberg, 11 juin 2008 (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,‎ 30 novembre 2002 (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, 19 juin 2013 (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, n^o 2,‎ 1^er janvier 2014 (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, n^o 2,‎ 1^er janvier 2015 (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,‎ 1996 (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],‎ 11 avril 2017 (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, 2005 (ISBN 9783540290018, DOI 10.1007/11556992_27, lire en ligne), p. 374–388

• Portail de la cryptologie