Введение
Асимметричный алгоритм шифрования с открытым ключом.
Криптосистема Блума — Голдвассера (BG) — это асимметричный алгоритм шифрования с открытым ключом, предложенный Мануэлем Блумом и Шафи Голдвассером в 1984 году. Блум — Голдвассер — это вероятностная, семантически безопасная криптосистема с постоянным расширением шифротекста. Алгоритм шифрования реализует потоковый шифр на основе операции XOR, используя генератор псевдослучайных чисел Блума — Блуба — Шуба (BBS) для генерации ключевого потока. Расшифровка осуществляется путем манипулирования конечным состоянием генератора BBS с использованием секретного ключа для нахождения начального зерна и восстановления ключевого потока. Семантическая безопасность криптосистемы BG основана на предполагаемой вычислительной сложности факторизации целых чисел, а именно факторизации составного числа, где — большие простые числа. BG имеет ряд преимуществ по сравнению с более ранними вероятностными схемами шифрования, такими как криптосистема Голдвассера — Микали. Во-первых, её семантическая безопасность сводится исключительно к факторизации целых чисел, без каких-либо дополнительных предположений (например, сложности задачи об остатках квадратичности или задачи RSA). Во-вторых, BG эффективен с точки зрения хранения, обеспечивая постоянное расширение шифротекста независимо от длины сообщения. BG также относительно эффективен с точки зрения вычислений и хорошо показывает себя даже в сравнении с криптосистемами, такими как RSA (в зависимости от длины сообщения и выбора степени). Однако BG крайне уязвим к адаптивным атакам с выбранным шифротекстом (см. ниже). Поскольку шифрование выполняется с использованием вероятностного алгоритма, один и тот же открытый текст может приводить к получению существенно различных шифротекстов при каждом шифровании. Это имеет значительные преимущества, поскольку не позволяет злоумышленнику распознавать перехваченные сообщения, сравнивая их со словарем известных шифротекстов.
The Blum–Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum–Goldwasser is a probabilistic, semantically secure cryptosystem with a constant size ciphertext expansion. The encryption algorithm implements an XOR based stream cipher using the Blum Blum Shub (BBS) pseudo random number generator to generate the keystream. Decryption is accomplished by manipulating the final state of the BBS generator using the private key, in order to find the initial seed and reconstruct the keystream. The BG cryptosystem is semantically secure based on the assumed intractability of integer factorization; specifically, factoring a composite value where are large primes. BG has multiple advantages over earlier probabilistic encryption schemes such as the Goldwasser–Micali cryptosystem. First, its semantic security reduces solely to integer factorization, without requiring any additional assumptions (e. g., hardness of the quadratic residuosity problem or the RSA problem). Secondly, BG is efficient in terms of storage, inducing a constant size ciphertext expansion regardless of message length. BG is also relatively efficient in terms of computation, and fares well even in comparison with cryptosystems such as RSA (depending on message length and exponent choices). However, BG is highly vulnerable to adaptive chosen ciphertext attacks (see below). Because encryption is performed using a probabilistic algorithm, a given plaintext may produce very different ciphertexts each time it is encrypted. This has significant advantages, as it prevents an adversary from recognizing intercepted messages by comparing them to a dictionary of known ciphertexts.
Операция
Криптосистема Блюма — Голдвассера состоит из трех алгоритмов: вероятностный алгоритм генерации ключей, который выдает публичный и секретный ключ, вероятностный алгоритм шифрования и детерминированный алгоритм дешифрования.
Безопасность и эффективность
Схема Блюма-Голдвассера семантически безопасна, поскольку её стойкость основана на сложности предсказания битов ключевого потока, зная только конечное состояние BBS и открытый ключ. Однако, шифротексты вида уязвимы к адаптивной атаке с выбранным шифротекстом, в которой противник запрашивает расшифровку выбранного им шифротекста. Расшифровка исходного шифротекста может быть вычислена как. В зависимости от размера открытого текста, BG может быть более или менее вычислительно затратной, чем RSA. Поскольку в большинстве реализаций RSA используется фиксированный показатель шифрования, оптимизированный для минимизации времени шифрования, RSA обычно работает быстрее, чем BG, для всех сообщений, кроме самых коротких. Однако, поскольку показатель расшифровки RSA распределен случайным образом, модульное возведение в степень может потребовать сравнимого количества возведений в квадрат и умножений с возведением в степень, как и расшифровка BG для шифротекста той же длины. BG имеет преимущество в более эффективном масштабировании для более длинных шифротекстов, в то время как RSA требует нескольких отдельных операций шифрования. В таких случаях BG может быть значительно эффективнее.
Depending on plaintext size, BG may be more or less computationally expensive than RSA. Because most RSA deployments use a fixed encryption exponent optimized to minimize encryption time, RSA encryption will typically outperform BG for all but the shortest messages. However, as the RSA decryption exponent is randomly distributed, modular exponentiation may require a comparable number of squarings/multiplications to BG decryption for a ciphertext of the same length. BG has the advantage of scaling more efficiently to longer ciphertexts, where RSA requires multiple separate encryptions. In these cases, BG may be significantly more efficient.