Probabilités et statistiquesNotion · Glossaire
chiffrement de Goldwasser-Micali
Le cryptosystème de Goldwasser-Micali est un chiffrement probabiliste à clé publique qui représente chaque bit par un résidu quadratique ou par un non-résidu de symbole de Jacobi +1 modulo un entier composé. La factorisation secrète permet de distinguer ces deux classes et donc de déchiffrer ; sous l’hypothèse de résiduosité quadratique et avec un hasard indépendant pour chaque bit, le chiffré ne révèle aucune information calculable sur le message, ce qui assure la sécurité sémantique.
Sommaire
Ce que vous allez apprendre
- Suivre la génération des clés, le chiffrement probabiliste et le déchiffrement d'un bit.
- Recalculer le chiffrement du message 01 avec N = 77.
- Relier résidus quadratiques, difficulté calculatoire et sécurité sémantique.
- Identifier le coût, les mauvais choix de paramètre et le danger d'un hasard réutilisé.
En clair
Imaginez que chaque bit soit enfermé dans une boîte différente. Pour chiffrer 0 ou 1, Goldwasser-Micali choisit à chaque fois un nombre au hasard et produit un nouveau résultat. Deux chiffrements du même bit ont donc de fortes chances d'être différents.
La clé privée sait pourtant reconnaître deux familles de nombres : l'une code 0, l'autre code 1. Sans cette clé, les distinguer doit être trop difficile à calculer. C'est l'intuition de la sécurité sémantique : le chiffré ne révèle pas utilement le bit caché.
Définition
Le cryptosystème de Goldwasser-Micali est un chiffrement probabiliste à clé publique qui traite un message bit par bit. La génération choisit deux grands nombres premiers secrets p et q, puis forme leur produit N. Elle choisit aussi un entier x qui est un non-résidu quadratique modulo p et modulo q, tout en ayant un symbole de Jacobi égal à +1 modulo N. La clé publique est le couple (N, x) ; la clé privée contient p et q.
Pour chiffrer un bit b, égal à 0 ou 1, on tire au hasard un entier y inversible modulo N. Le chiffré c est le reste modulo N donné par . Si b vaut 0, c est un résidu quadratique ; si b vaut 1, il est un non-résidu de symbole de Jacobi +1. Connaître p ou q permet de tester cette différence et de retrouver b.
La sécurité repose sur une difficulté calculatoire : avec les seules données publiques, distinguer ces deux familles modulo N est supposé impraticable. Le tirage de y empêche aussi un observateur de reconnaître un bit par comparaison avec un chiffré déjà vu. Cette propriété a servi de formulation fondatrice à la sécurité sémantique et à la sécurité prouvable.
Un exemple, pas à pas
Chiffrons le message binaire 01 avec de petits nombres destinés uniquement au calcul. Le schéma récapitule les deux chemins : un carré code 0, tandis qu'un carré multiplié par x code 1.
Données.
Nombres premiers secrets : p = 7 et q = 11.
Produit public : N = 7 × 11 = 77.
Paramètre public : x = 10, non-résidu quadratique modulo 7 et modulo 11.
Tirages : y0 = 8 pour le premier bit et y1 = 13 pour le second.
Nombres premiers secrets : p = 7 et q = 11.
Produit public : N = 7 × 11 = 77.
Paramètre public : x = 10, non-résidu quadratique modulo 7 et modulo 11.
Tirages : y0 = 8 pour le premier bit et y1 = 13 pour le second.
Étape 1. Pour le bit 0, l'exposant de x vaut 0. Le premier chiffré est donc .
Étape 2. Pour le bit 1, on multiplie le carré du tirage par x. Le second chiffré est . Le message chiffré est le couple (64, 73).
Étape 3. La clé privée permet de réduire modulo 7. On obtient 64 ≡ 1, qui est un carré modulo 7, puis 73 ≡ 3, qui n'en est pas un. Le déchiffrement restitue donc 0 puis 1.
Contrôle. Modulo 11, 64 ≡ 9 est aussi un carré, tandis que 73 ≡ 7 n'en est pas un. Les deux facteurs secrets donnent le même verdict : le message retrouvé est bien 01.
En pratique
Dans un cours de cryptographie, Goldwasser-Micali sert à observer directement l'effet du hasard : rechiffrer un même bit avec un nouveau tirage produit normalement un autre entier. Un chiffrement déterministe ne convient pas à cette démonstration, car une entrée identique y redonnerait le même résultat.
Pour étudier la sécurité prouvable, le schéma relie une attaque contre le message à un problème arithmétique supposé difficile. On le choisit donc comme modèle théorique lorsque l'objectif est de suivre une réduction mathématique, et non d'optimiser la taille des chiffrés.
Dans une application courante, son coût est un signal défavorable : chaque bit du clair devient un entier modulo N. Lorsque le débit ou le stockage compte, un système plus efficace est généralement préférable, conformément à la faible utilisation pratique signalée par la définition de référence.
À ne pas confondre
Chiffrement probabiliste et génération probabiliste des clés. La génération aléatoire crée une paire de clés, tandis que le chiffrement aléatoire intervient à chaque message. Avec une clé publique déjà fixée, chiffrer deux fois 0 avec deux tirages distincts peut produire deux chiffrés distincts.
Résidu quadratique et symbole de Jacobi +1. Ces propriétés ne sont pas équivalentes modulo un entier composé. Dans l'exemple, x = 10 a un symbole de Jacobi +1 modulo 77, mais ce n'est un carré ni modulo 7 ni modulo 11. Cette ambiguïté est précisément exploitée.
Sécurité sémantique et secret absolu. La sécurité annoncée est calculatoire : elle affirme qu'un adversaire aux ressources bornées ne peut extraire d'information utile du chiffré. Elle ne dit pas que les deux familles de nombres sont mathématiquement identiques.
Limites et pièges
Les petits nombres ne protègent rien. Avec N = 77, retrouver les facteurs 7 et 11 est immédiat. Cet exemple sert seulement à vérifier les opérations ; une instance réelle part d'un paramètre de sécurité et de nombres premiers assez grands pour rendre l'attaque impraticable.
Le hasard doit être renouvelé. Réutiliser le même y pour chiffrer deux bits annule le masque commun lorsqu'on combine leurs chiffrés. Le résultat peut révéler si les bits sont égaux ou différents. Chaque bit exige donc un tirage indépendant et adapté.
Un symbole de Jacobi égal à +1 ne suffit pas pour choisir x. Si x était en réalité un carré modulo N, les deux valeurs possibles de b produiraient toutes deux des carrés. Le déchiffrement ne pourrait plus les séparer ; x doit être non-résidu modulo chacun des deux facteurs secrets.
L'expansion est structurelle. Le schéma chiffre séparément chaque bit par un élément modulo N. Un message de plusieurs bits devient donc une suite de grands entiers, ce qui explique son inefficacité relative et limite son emploi dans les applications courantes.
Pour aller plus loin
Le mécanisme possède une propriété algébrique utile : multiplier deux chiffrés modulo N revient à additionner leurs bits modulo 2. Les carrés se combinent entre eux, tandis que les facteurs x s'additionnent dans l'exposant ; une puissance paire de x redevient un carré. On obtient ainsi le chiffrement du ou exclusif des deux bits sans les déchiffrer.
Cette propriété éclaire la portée historique du schéma : Goldwasser-Micali ne fournit pas seulement une recette de chiffrement. Il donne un cadre où une propriété de confidentialité se formule précisément, puis se rattache par une démonstration à une hypothèse de difficulté arithmétique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres