cryptosystème de Blum-Goldwasser

Alice chiffre deux fois le mot « OUI » avec la même clé publique. Les deux résultats peuvent être différents, car un nouvel aléa intervient à chaque chiffrement. Pourtant, le destinataire retrouve « OUI » dans les deux cas avec sa clé privée.

Cette variation est au cœur du cryptosystème de Blum-Goldwasser. Elle empêche de reconnaître un message intercepté en le comparant simplement à un chiffré déjà observé.

Le cryptosystème de Blum-Goldwasser, abrégé BG, est un algorithme de chiffrement asymétrique probabiliste proposé en 1984 par Manuel Blum et Shafi Goldwasser. Le chiffrement emploie une clé publique, tandis que le déchiffrement repose sur une clé privée. Le mot « probabiliste » indique que le calcul fait intervenir un aléa renouvelé : un même message et une même clé publique ne déterminent donc pas toujours le même chiffré.

La clé publique est un entier composite, noté N, obtenu comme produit de deux grands nombres premiers de Blum distincts, notés p et q, chacun congru à 3 modulo 4 : $N=p\times qN=p\backslash times\; q$. La factorisation de N permet au détenteur de la clé privée d'effectuer le déchiffrement. La sécurité sémantique, elle, est justifiée sous l'hypothèse de résiduosité quadratique et avec un module correctement généré, en s'appuyant sur l'imprévisibilité du générateur Blum-Blum-Shub : une simple comparaison ne doit pas révéler si deux interceptions correspondent au même message.

BG se distingue des schémas probabilistes antérieurs comme Goldwasser-Micali. La possibilité pour l'attaquant de choisir des textes clairs relève du modèle standard auquel sa sécurité sémantique est destinée à résister, sous l'hypothèse de résiduosité quadratique. Son emploi doit cependant être apprécié dans des modèles plus forts, notamment face à des attaques à textes chiffrés choisis.

Alice veut transmettre le message « OUI ». Elle dispose de la clé publique N, et le destinataire possède la clé privée correspondante. Deux essais, A et B, utilisent chacun un aléa neuf.

1. Lors de l'essai A, Alice chiffre « OUI » avec N et le premier aléa. Elle obtient un chiffré que l'on note C₁.

2. Lors de l'essai B, elle reprend exactement « OUI » et N, mais emploie le second aléa. Elle obtient C₂.

3. Dans le cas illustré, le mécanisme probabiliste donne $C_1\mathrm{\ne }{C}_{2}C\_1\backslash neq\; C\_2$, même si le message en clair et la clé publique n'ont pas changé. Le renouvellement de l'aléa peut conduire à cette différence, sans la garantir à chaque tirage.

4. Pour observer la variation, relevez les entrées : message = « OUI », clé publique = N, aléa de A = r_A et aléa de B = r_B. La trace est : (message, N, r_A) donne C₁, puis (message, N, r_B) donne C₂ ; dans le cas illustré, $C_1\mathrm{\ne }{C}_{2}C\_1\backslash neq\; C\_2$. Le résultat à identifier est donc que le message et N restent fixes, tandis que l’aléa est renouvelé. Il s’agit d’une observation guidée du rôle de l’aléa, et non d’un calcul à refaire : aucune clé privée ni procédure de calcul intégrale n’est fournie ici.

Pour envoyer une information, l'expéditeur utilise la clé publique du destinataire et renouvelle l'aléa à chaque chiffrement. Réemployer mécaniquement un résultat antérieur ferait perdre la variation recherchée.

Face à deux chiffrés différents, on ne conclut pas que les messages en clair diffèrent. Le bon geste consiste à tenir compte du caractère probabiliste avant toute comparaison.

Avant de retenir BG dans un contexte donné, on identifie les actions permises à un attaquant. Le choix de textes clairs relève du modèle standard auquel la sécurité sémantique de BG est destinée à résister ; des modèles plus forts, comme les attaques à textes chiffrés choisis, demandent une analyse distincte.

Chiffrement déterministe. Avec un procédé déterministe, le même message traité avec les mêmes données produit le même chiffré. Avec BG, deux aléas différents peuvent donner C₁ et C₂ pour le même « OUI ».

Factorisation. Factoriser N consiste à retrouver les nombres premiers p et q dont N est le produit. BG est le système de chiffrement dont la sécurité s'appuie sur la difficulté de cette opération ; les deux notions ne désignent pas la même tâche.

Goldwasser-Micali. Goldwasser-Micali est cité comme un schéma probabiliste antérieur. Un chiffrement probabiliste n'est donc pas automatiquement BG : le nom de l'algorithme employé tranche entre les deux.

Textes clairs choisis. Le modèle d'attaque à textes clairs choisis doit être inclus explicitement dans l'analyse de sécurité : l'attaquant peut faire chiffrer des messages qu'il choisit, et la sécurité sémantique de BG est destinée à résister à ce modèle. Il ne faut donc pas conclure à partir de la seule variabilité des chiffrés ; des modèles plus forts demandent une analyse distincte.

Aléa absent ou répété. Si les deux essais emploient exactement le même aléa, l'argument « même message, chiffrés différents » ne s'applique plus. Il faut renouveler l'aléa à chaque chiffrement pour obtenir la propriété illustrée.

Clé publique mal interprétée. Connaître N ne revient pas à connaître sa décomposition. Le symptôme du piège est l'affirmation que p et q sont publics ; il faut distinguer le produit publié des deux facteurs sur lesquels repose le déchiffrement privé.

Factorisation — Pour approfondir l'opération dont la difficulté protège la clé publique N.

nombre premier — Pour préciser la nature des deux facteurs p et q utilisés dans la construction de N.