« Cryptosystème de Goldwasser-Micali » : différence entre les versions

Un article de Wikipédia, l'encyclopédie libre.
Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
m Diffusion des articles à recycler dans une sous-catégorie : informatique
Ϛ (discuter | contributions)
198 modifications
reprise intégrale :)
Ligne 1 : Ligne 1 :
{{Confusion|signatures de Goldwasser-Micali-Rivest|cryptosystème de Blum-Goldwasser}}
{{à recycler|date=mars 2015|thème=informatique}}

Le '''cryptosystème de Goldwasser-Micali''' est un [[cryptosystème]] de [[cryptographie]] à [[cryptographie asymétrique|clef publique]], conçu par [[Shafi Goldwasser]] et [[Silvio Micali]] en [[1982 en science|1982]]<ref>{{Chapitre|lang=en|auteur=S. Goldwasser|auteur2=S. Micali|titre=Probabilistic encryption and how to play mental poker keeping secret all partial information|titre ouvrage=STOC '82 Proceedings of the 14th annual [[Association for Computing Machinery|ACM]] [[Symposium on Theory of Computing]]|year=1982|page=365–377}}.</ref>{{,}}<ref>{{Article|lang=en|auteur=S. Goldwasser|auteur2=S. Micali|titre=Probabilistic encryption|périodique=[[Liste de revues d'informatique#J|J. Comput. Syst. Sci.]]|volume=28|numéro=2|année=1984|p.=270-299|doi=10.1016/0022-0000(84)90070-9}}.</ref>. C’est le premier cryptosystème qui a été [[preuve de sécurité|prouvé sûr]] sous des [[hypothèse calculatoire|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<ref>{{ouvrage|langue=en
En [[cryptologie]], le '''cryptosystème de Goldwasser-Micali'''<ref>{{Chapitre|langue=en|auteur1=|prénom1=Kazue|nom1=Sako|titre chapitre=Goldwasser-Micali encryption scheme|auteurs ouvrage=Henk C. A. van Tilborg|titre ouvrage=Encyclopedia of Cryptography and Security|lieu=|éditeur=Springer US|année=2005|date=|pages totales=|isbn=9780387234731|doi=10.1007/0-387-23483-7_177|lire en ligne=http://www.springerlink.com/index/10.1007/0-387-23483-7_177|consulté le=2018-08-24|passage=241–242}}</ref> est un [[cryptosystème]] développé par [[Shafi Goldwasser]] et [[Silvio Micali]] en [[1982 en science|1982]]<ref>{{Chapitre|lang=en|auteur=S. Goldwasser|auteur2=S. Micali|titre=Probabilistic encryption and how to play mental poker keeping secret all partial information|titre ouvrage=STOC '82 Proceedings of the 14th annual [[Association for Computing Machinery|ACM]] [[Symposium on Theory of Computing]]|year=1982|page=365–377}}.</ref>{{,}}<ref name=":0">{{Article|lang=en|auteur=S. Goldwasser|auteur2=S. Micali|titre=Probabilistic encryption|périodique=[[Liste de revues d'informatique#J|J. Comput. Syst. Sci.]]|volume=28|numéro=2|année=1984|p.=270-299|doi=10.1016/0022-0000(84)90070-9}}.</ref>. Il s'agit du premier cryptosystème [[preuve de sécurité|prouvé sûr]] dans le [[Modèle standard (cryptologie)|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 [[Théorie des jeux|jeu de sécurité]]<ref>{{ouvrage|langue=en
| auteur1 = Jonathan Katz
| auteur1 = Jonathan Katz
| auteur2 = Yehuda Lindell
| auteur2 = Yehuda Lindell
Ligne 8 : Ligne 9 :
| isbn = 978-1466570269
| isbn = 978-1466570269
|numéro chapitre=3.2|chapitre=Defining Computationally Secure Encryption|url={{Google Livres|OWZYBQAAQBAJ|page=52}}
|numéro chapitre=3.2|chapitre=Defining Computationally Secure Encryption|url={{Google Livres|OWZYBQAAQBAJ|page=52}}
}}.</ref>{{,}}<ref>{{article|langue=en|titre=Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One|auteur1=Seung Geol Choi|auteur2=Dana Dachman-Soled|auteur3=Tal Malkin|auteur4=Hoeteck Wee|doi=10.1007/978-3-540-78524-8_24|lire en ligne=http://ia.cr/2016/720|périodique=Theory of Cryptography Conference (TCC)|année=2008}}.</ref>, participant à la naissance de la [[Preuve de sécurité|sécurité prouvable]] en cryptologie moderne<ref name=":1">{{Chapitre|langue=en|prénom1=Alexander W.|nom1=Dent|titre chapitre=A Brief History of Provably-Secure Public-Key Encryption|titre ouvrage=Progress in Cryptology – AFRICACRYPT 2008|éditeur=Springer Berlin Heidelberg|date=2008-06-11|isbn=9783540681595|doi=10.1007/978-3-540-68164-9_24|lire en ligne=http://link.springer.com/10.1007/978-3-540-68164-9_24|consulté le=2018-08-24|passage=357–370}}</ref>{{,}}<ref group="Note">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).</ref>{{,}}<ref>{{Article|langue=anglais|auteur1=|prénom1=Shafi|nom1=Goldwasser|titre=Mathematical foundations of modern cryptography: computational complexity perspective|périodique=arXiv:cs/0212055|date=2002-11-30|issn=|lire en ligne=http://arxiv.org/abs/cs/0212055|consulté le=2018-08-24|pages=}}</ref>. Pour ces raisons, Goldwasser et Micali on reçu le prestigieux [[prix Turing]] en 2012<ref>{{Lien web|langue=en|titre=Shafi Goldwasser - A.M. Turing Award Laureate|url=https://amturing.acm.org/award_winners/goldwasser_8627889.cfm|site=amturing.acm.org|consulté le=2018-08-24}}</ref>{{,}}<ref>{{Lien web|langue=en|titre=Silvio Micali - A.M. Turing Award Laureate|url=https://amturing.acm.org/award_winners/micali_9954407.cfm|site=amturing.acm.org|consulté le=2018-08-24}}</ref>{{,}}<ref>{{Lien web|langue=anglais|nom1=Association for Computing Machinery (ACM)|titre=ACM Turing Award 2012|url=https://www.youtube.com/watch?v=ftTYooCjhuo|site=youtube.com|date=2013-06-19|consulté le=2018-08-24}}</ref>.
}}.</ref>{{,}}<ref>{{article|langue=en|titre=Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One|auteur1=Seung Geol Choi|auteur2=Dana Dachman-Soled|auteur3=Tal Malkin|auteur4=Hoeteck Wee|doi=10.1007/978-3-540-78524-8_24|lire en ligne=http://ia.cr/2016/720|périodique=Theory of Cryptography Conference (TCC)|année=2008}}.</ref>.


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.
Il est à noter que la taille des chiffrés subit une [[facteur d'échelle|expansion de taille]] de l’ordre de la taille de sa clef publique (2048 bits<ref>{{Lien web|url=https://www.keylength.com/|langue=en|titre=BlueKrypt – Cryptographic Key Length Recommendation|site=keylength.com}}.</ref>), ce qui la rend inutilisable en pratique.


== Description ==
== Description ==
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 [[algorithme probabiliste|algorithmes probabilistes]], tandis que le déchiffrement est un [[algorithme déterministe]].


=== Génération des clés ===
=== Syntaxe générale ===
Le cryptosystème de Goldwasser et Micali est un schéma de [[Cryptographie asymétrique|chiffrement à clé publique]] : il est constitué de trois [[Algorithme|algorithmes]] :
Le module <math>N</math> est généré comme pour le cryptosystème [[Rivest Shamir Adleman|RSA]]. (Voir [[Rivest Shamir Adleman|RSA]], ''Fonctionnement détaillé'' pour les détails.)


* un algorithme de génération des clés, [[algorithme probabiliste|probabiliste]], qui prend en entrée un [[paramètre de sécurité]] et retourne un couple <math>(\mathsf{sk}, \mathsf{pk})</math>constitué d'une clé privée et de la clé publique correspondante ;
# [[Alice et Bob|Alice]] génère deux grands [[nombre premier|nombres premiers]] <math>p \,</math> et <math>q \,</math> de telle sorte que <math>p \ne q</math> et ce, de façon [[aléatoire]] et indépendante.
* un algorithme de chiffrement, également probabiliste<ref group="Note">Un algorithme de chiffrement déterministe ne peut pas être sémantiquement sûr.</ref>, qui prend en entrée le paramètre de sécurité, un message clair, et une clé publique, et retourne un message chiffré ;
# Alice calcule <math>N = p q</math>.
* 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.
# Elle trouve un non-résidu <math>z</math> pour lequel le [[symbole de Jacobi]] est +1, par exemple, en générant des valeurs aléatoires et en les testant. Si <math>(p, q) \equiv 3</math> mod <math>4</math> ({{c.-à-d.}}, <math>N</math> est un [[entier de Blum]]), alors le nombre <math>N-1</math> a cette propriété.


=== Détail des algorithmes ===
La clé publique est <math>(N, z)</math>. La clé secrète est la factorisation <math>(p, q)</math>.


==== Génération des clés cryptographiques ====
=== Chiffrement ===
La génération des clés est effectuée ainsi :
Supposons que Bob veut envoyer un message ''m'' à Alice :


# Deux [[nombre premier|nombres premiers]] <math>p</math> et <math>q \,</math>distincts sont générés, on note <math>n = pq</math>. La taille de <math>p</math> et <math>q</math> est déterminée en fonction du paramètre de sécurité à partir de la preuve de sécurité (voir plus bas).
# Bob [[codage de caractères|encode]] <math>m</math> comme une chaîne de bits <math>(m_0, \dots, m_n)</math>.
# Un entier <math>z \in \mathbb (\mathbb Z/(n))^\times</math> est trouvé dont les [[symbole de Jacobi|symboles de Jacobi]] par rapport à <math>p</math> et à <math>q</math> sont égaux à -1, c'est-à-dire qu'il ne s'agit pas d'un [[résidu quadratique]] modulo <math>p</math> ni <math>q</math><ref group="Note">Le symbole de Jacobi étant une [[fonction multiplicative]], on a <math>\left( \frac{z}{n} \right) = \left( \frac{z}{p} \right)\left( \frac{z}{q} \right) = +1</math>.</ref>.
# Pour chaque bit <math>m_i</math>, Bob génère une valeur [[aléatoire]] <math>y</math> moindre que <math>N</math>. Il retourne la valeur de <math>c_i = y^2 z^{m_i}</math> mod <math>N</math>.
#L'algorithme retourne <math>(\mathsf{sk} = p, \mathsf{pk} = \{n, z\})</math>.


Pour l'étape 2, il existe essentiellement deux méthodes. La première méthode consiste à tirer <math>z</math> 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 <math>(p, q) \equiv 3</math> mod <math>4</math>, ce qui garantit que <math>z = n-1</math> convient<ref>{{Article|langue=en|prénom1=Benjamin|nom1=Justus|titre=The distribution of quadratic residues and non-residues in the Goldwasser–Micali type of cryptosystem|périodique=Journal of Mathematical Cryptology|volume=8|numéro=2|date=2014-01-01|issn=1862-2976|issn2=1862-2984|doi=10.1515/jmc-2013-0001|lire en ligne=https://www.degruyter.com/view/j/jmc.2014.8.issue-2/jmc-2013-0001/jmc-2013-0001.xml|consulté le=2018-08-24}}</ref>{{,}}<ref>{{Article|langue=en|prénom1=Benjamin|nom1=Justus|titre=The distribution of quadratic residues and non-residues in the Goldwasser–Micali type of cryptosystem. II|périodique=Journal of Mathematical Cryptology|volume=9|numéro=2|date=2015-01-01|issn=1862-2976|issn2=1862-2984|doi=10.1515/jmc-2014-0004|lire en ligne=https://www.degruyter.com/view/j/jmc.2015.9.issue-2/jmc-2014-0004/jmc-2014-0004.xml|consulté le=2018-08-24}}</ref>.
Bob envoie le texte chiffré : <math>(c_0, \dots, c_n)</math>.


=== Déchiffrement ===
==== Chiffrement d'un bit ====
Alice reçoit <math>(c_0, \dots, c_i)</math>. Elle peut récupérer <math>m</math> en utilisant la procédure suivante :
Soit <math>m</math>un message d'un seul [[bit]], c'est-à-dire <math>m \in \{0, 1\}</math>. Pour chiffrer ce message,


# L'algorithme tire uniformément un entier <math>y</math> dans <math>(\mathbb Z/(n))^\times</math>.
# En utilisant la factorisation <math>(p, q)</math>, Alice détermine si la valeur <math>c_i</math> est un [[problème de la résiduosité quadratique|résidu quadratique]]; si c'est le cas, <math>m_i = 0</math>, autrement <math>m_i = 1</math>.
# L'algorithme retourne le message chiffré <math>c = z^m y^2 \bmod n</math>


Pour chiffrer un message plus long, constitué de plusieurs bits, chaque bit est chiffré indépendamment<ref name=":0" />. Ainsi, si <math>m = (m_1, \dotsc, m_k) \in \{0, 1\}^k</math>, le message chiffré correspondant est <math>c = (c_1, \dotsc, c_k) \in \mathbb (\mathbb Z/(n))^k</math>où chaque <math>c_i</math>est le chiffré de <math>m_i</math>.
Alice produit en sortie le message <math>m = (m_0, \dots, m_n)</math>.

Cette manière de faire est responsable de la faible [[bande passante]] du cryptosystème<ref group="Note">Pour chaque bit du chiffré on transmet <math>1/\log_2 n</math> bit du message.</ref>. L'indépendance entre chaque chiffrement permet également à un attaquant de réordonner les membres de <math>c</math> sans jamais déchiffrer : il s'agit d'une vulnérabilité de [[Malléabilité (cryptographie)|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 <math>c</math> consiste en ceci :

# Si <math>c</math> est un [[résidu quadratique]] modulo <math>n</math>, retourner 1. Sinon retourner 0.

Cette étape est efficace puisque l'algorithme de déchiffrement reçoit la clé privée <math>\mathsf{sk}</math>qui donne la factorisation de <math>n</math><ref group="Note">L'algorithme classique consiste à calculer le [[symbole de Legendre]] modulo <math>p</math>et modulo <math>q</math>, ce qui requiert essentiellement l'[[algorithme d'Euclide]].</ref>. Si le chiffré correspond à un message de plusieurs bits, <math>c = (c_1, \dotsc, c_k) </math>, chaque <math>c_i</math>est déchiffré pour donner le bit <math>m_i</math>du message clair.


== Sécurité ==
== Sécurité ==
{{Article détaillé|Sécurité sémantique|Problème de la résiduosité quadratique}}
La preuve que le cryptosystème de Goldwasser et Micali est [[sécurité sémantique|sémantiquement sûr]] se construit sur l'[[hypothèse calculatoire|hypothèse de difficulté]] du [[problème de la résiduosité quadratique]] modulo <math>N</math> où <math>N=pq</math>, avec <math>p,q</math> de grands [[nombre premier|nombres premiers]]. Ce problème se résout facilement lorsque la factorisation de <math>N</math> est connue, et difficilement autrement. D'autre part, n'importe quel [[Alice et Bob|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 <math>N</math> en tant que [[clé secrète]] et déchiffre le message en testant la résiduosité quadratique des valeurs chiffrées reçues.
La [[sécurité sémantique]] (IND-CPA) du cryptosystème de Goldwasser et Micali a été réduite, dans le [[Modèle standard (cryptologie)|modèle standard]], à la difficulté du [[problème de la résiduosité quadratique]] modulo <math>n</math> — c'est-à-dire l'[[Hypothèse calculatoire|hypothèse]] qu'il est difficile de déterminer si un nombre <math>c</math>est un résidu quadratique modulo <math>n</math>. Cette preuve est historiquement la première de son genre et a participé à développer la notion de sécurité prouvable en cryptologie<ref name=":1" />{{,}}<ref group="Note">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 <math>n</math>et la factorisation de <math>n</math>. Voir (Dent 2008) pour une discussion.</ref>.


Lorsque la [[Décomposition en produit de facteurs premiers|factorisation]] de <math>n</math> 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<ref>{{Article|langue=anglais|auteur1=René Peralta|auteur2=Eiji Okamoto|titre=Some combinatorial problems of importance to cryptography|périodique=Proceedings of the IEICE 1996 Symposium on Cryptography and Information Security|date=1996|issn=|lire en ligne=https://www.researchgate.net/profile/Rene_Peralta2/publication/277294300_Some_Combinatorial_Problems_of_Importance_to_Cryptography/links/5628e71608ae518e347c69ee/Some-Combinatorial-Problems-of-Importance-to-Cryptography.pdf|pages=}}</ref>.
Le cryptosystème ayant été conçu pour être prouvé, la [[preuve de sécurité|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 <math>y</math>), 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 à [[cryptanalyse|casser]] que le [[problème de la résiduosité quadratique]].


La meilleure attaque connue (en 2018) consiste ainsi à calculer la factorisation de <math>n</math>, ce qui détermine la manière de générer les clés pour cet algorithme : pour résister à un attaquant classique, <math>p</math> et <math>q</math> doivent être individuellement assez grands pour éviter une [[Factorisation de Lenstra par les courbes elliptiques|factorisation par ECM]] (ainsi <math>p \approx q</math>) et leur produit doit opposer assez de résistance aux meilleurs algorithmes génériques de factorisation, notamment le [[Crible algébrique|crible du corps de nombres]]. Pour un [[Paramètre de sécurité|niveau de sécurité]] classique de 128 bits, cela correspond à <math>n \approx 2^{3072}</math>. Face à un [[Calculateur quantique|attaquant quantique]], l'[[algorithme de Shor]] donne la factorisation de <math>n</math> en [[BQP|temps polynomial]] et il n'existe donc pas de paramètres rendant le cryptosystème sûr dans ce contexte.
== Efficacité ==
Le cryptosystème de Goldwasser et Micali produit un chiffré de taille <math>|N| \cdot |m|</math>. C'est ainsi que le chiffrement par GM produit une importante {{Lien|trad=Ciphertext expansion|expansion de texte chiffré}}. Pour se prémunir contre les attaques, il est recommandé que <math>N</math> soit d'au moins quelques centaines de bits (2048 en [[2016]]).


== Malléabilité et homomorphisme ==
Ce cryptosystème a été développé pour illustrer les concepts de {{lien|langue=en|trad=Probabilistic encryption|chiffrement probabiliste}} et de [[sécurité sémantique]]. Depuis lors, d'autres cryptosystèmes [[preuve de sécurité|prouvés sûrs]] ont été développés, comme le [[Cryptosystème de ElGamal|chiffrement ElGamal]].
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 [[Attaque à chiffré choisi|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<ref name=":1" />.

Un autre point de vue sur le même phénomène est que le cryptosystème de Goldwasser-Micali est [[Chiffrement homomorphe|partiellement homomorphe]] : si <math>m_1, m_2</math>sont deux bits, chiffrés en <math>c_1, c_2</math>respectivement, alors <math>c_1 \times c_2 \bmod n</math>déchiffre en <math>m_1 \oplus m_2</math>. Autrement dit, la fonction [[Fonction OU exclusif|ou exclusif]] est calculable homomorphiquement sur ce cryptosystème<ref>{{Article|langue=anglais|auteur1=|prénom1=Abbas|nom1=Acar|prénom2=Hidayet|nom2=Aksu|prénom3=A. Selcuk|nom3=Uluagac|prénom4=Mauro|nom4=Conti|titre=A Survey on Homomorphic Encryption Schemes: Theory and Implementation|périodique=arXiv:1704.03578 [cs]|date=2017-04-11|issn=|lire en ligne=http://arxiv.org/abs/1704.03578|consulté le=2018-08-24|pages=}}</ref>{{,}}<ref>{{Chapitre|langue=en|prénom1=Kun|nom1=Peng|prénom2=Colin|nom2=Boyd|prénom3=Ed|nom3=Dawson|titre chapitre=A Multiplicative Homomorphic Sealed-Bid Auction Based on Goldwasser-Micali Encryption|titre ouvrage=Lecture Notes in Computer Science|éditeur=Springer Berlin Heidelberg|date=2005|isbn=9783540290018|doi=10.1007/11556992_27|lire en ligne=http://link.springer.com/10.1007/11556992_27|consulté le=2018-08-24|passage=374–388}}</ref>.


== Notes et références ==
== Notes et références ==
{{Traduction/Référence|en|Goldwasser–Micali cryptosystem|583929557|type=n}}
⚫
{{Références}}


== Articles connexes==
=== Notes ===
<references group="Note"/>
* [[Cryptographie asymétrique]]

* [[Preuve de sécurité]]
⚫
=== Références ===
<references/>


{{Palette|Sécurité prouvable}}
{{Portail|cryptologie}}
{{Portail|cryptologie}}


[[Catégorie:Algorithme de cryptographie asymétrique|Goldwasser-Micali]]
[[Catégorie:Algorithme de cryptographie asymétrique|Goldwasser-Micali]]
[[Catégorie:Cryptologie]]

Version du 24 août 2018 à 12:22

Page d’aide sur l’homonymie

Ne doit pas être confondu avec signatures de Goldwasser-Micali-Rivest ou cryptosystème de Blum-Goldwasser.

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.

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

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 bit

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é

Articles détaillés : Sécurité sémantique et Problème de la résiduosité quadratique.

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 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 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é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 .
  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érences

  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, Chapman and Hall, (ISBN 978-1466570269, lire en ligne), chap. 3.2 (« 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 )
  8. ↑ (en) « Shafi Goldwasser - A.M. Turing Award Laureate », sur amturing.acm.org (consulté le )
  9. ↑ (en) « Silvio Micali - A.M. Turing Award Laureate », sur amturing.acm.org (consulté le )
  10. ↑ (en) Association for Computing Machinery (ACM), « ACM Turing Award 2012 », sur youtube.com, (consulté le )
  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 )
  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 )
  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 )
  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
v · m
Modèles de sécurité
Outils et techniques de preuve
Hypothèses calculatoires
Propriétés de sécurité
Modèles d'attaques
  • Attaque sans message (NMA)
  • Clairs/messages choisis (CPA/CMA)
  • Chiffrés choisis (CCA)
  • Chiffrés choisis de façon adaptative (CCA2)
  • Attaque par sondes (ISW)
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Cryptosystème_de_Goldwasser-Micali&oldid=151588815 ».