Cryptosysteme de Blum-Goldwasser

Le cryptosystème de Blum-Goldwasser (BG) est un algorithme de chiffrement asymétrique proposé par Manuel Blum et Shafi Goldwasser en 1984. Blum-Goldwasser est un cryptosystème probabilistique et sémantiquement sûr avec une augmentation de taille de chiffrement constante.

L'algorithme de chiffrement implémente un chiffrement de flot basé sur l'opérateur XOR, utilisant le générateur de nombres pseudo-aléatoires Blum Blum Shub (BBS) pour générer la clé de chiffrement. Le déchiffrement est accompli en travaillant sur l'état final du générateur BBS en utilisant la clé secrète, dans le but de retrouver la valeur initiale de la graine et reconstruire la clé de chiffrement.

Le cryptosystème BG est sémantiquement sûr de par sa construction basée sur le problème de la décomposition en produit de facteurs premiers ; c’est-à-dire la factorisation d'une valeur composite N = pq où p,q sont des grands nombres premier. BG a de nombreux avantages sur les précédents schémas de chiffrement probabilistiques tels que le cryptosystème Goldwasser-Micali. En premier lieu, sa sécurité sémantique se réduit seulement à la factorisation de nombres premiers sans autre forme de supposition (par exemple, le Problème de la résiduosité quadratique ou le problème RSA). En second lieu, BG est efficace en termes de stockage, conduisant à une augmentation constante de la taille du chiffrement indépendamment de la longueur du message en clair. Les implémentations logicielles de BG sont aussi relativement efficaces et l'algorithme se comporte bien, même en face de cryptosystèmes comme RSA (dépendant de la longueur du message et des choix d'exposants). Cependant, BG est très vulnérable aux attaques à textes clairs choisis (voir ci-dessous).

Grâce à l'algorithme probabilistique, un texte clair donné peut produire des résultats très différents à chaque chiffrement. Cet propriété est significative car elle empêche de reconnaître les messages interceptés, par comparaison à un dictionnaire de textes chiffrés connus.

Sécurité et efficacité

Le schéma de Blum-Goldwasser est sémantiquement sûr en regard de la difficulté à découvrir les bits de la clé de chiffrement de flux avec seulement l'état final y du BBS et la clé publique N. Cependant, les textes chiffrés de la forme sont vulnérables aux attaques à textes clairs choisis dans lesquelles l'adversaire demande le déchiffrement d'un texte chiffré donné . Le déchiffrement m du texte original chiffré peut être calculé par .

Dépendant de la longueur initiale du texte en clair, BG peut coûter plus ou moins en temps de calcul par rapport à RSA. C'est parce que les implémentations de RSA utilisent un exposant de chiffrement fixe optimisé pour minimiser le temps de calcul qu'il dépasse BG en performance pour tous les messages sauf les plus courts. Néanmoins, comme l'exposant de déchiffrement RSA est distribué aléatoirement, l'exponentation modulaire peut nécessiter un nombre comparable de multiplications au déchiffrement via BG, et ce pour un texte de même longueur. BG a l'avantage de s'adapter plus efficacement aux textes plus longs, où RSA nécessite de multiples chiffrements séparés. Dans ces cas, BG peut se révéler bien plus efficace.

Références

• An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information, M. Blum, S. Goldwasser, Proceedings of Advances in Cryptology - CRYPTO '84, pp. 289-299, Springer Verlag, 1985.
• Handbook of Applied Cryptography. Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. CRC Press, October 1996. ISBN 0-8493-8523-7

Liens externes

• (en) Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography (free PDF downloads), see Chapter 8

• Portail de la cryptologie