Введение
Использование случайности в генерации ключевого кода
Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts. The term "probabilistic encryption" is typically used in reference to public key encryption algorithms; however various symmetric key encryption algorithms achieve a similar property (e. g., block ciphers when used in a chaining mode such as CBC), and stream ciphers such as Freestyle which are inherently random. To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.
Вероятностное шифрование — это использование случайности в алгоритме шифрования, благодаря чему при многократном шифровании одного и того же сообщения, как правило, получаются разные шифротексты. Термин "вероятностное шифрование" обычно применяется к алгоритмам шифрования с открытым ключом, однако различные алгоритмы шифрования с симметричным ключом достигают схожего свойства (например, блочные шифры при использовании в режиме связного шифрования, таком как CBC), а также потоковые шифры, такие как Freestyle, которые по своей природе случайны. Для обеспечения семантической безопасности, то есть для сокрытия даже частичной информации об исходном тексте, алгоритм шифрования должен быть вероятностным.
Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts. The term "probabilistic encryption" is typically used in reference to public key encryption algorithms; however various symmetric key encryption algorithms achieve a similar property (e. g., block ciphers when used in a chaining mode such as CBC), and stream ciphers such as Freestyle which are inherently random. To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.
История
Первая схема вероятностного шифрования открытым ключом с доказанной безопасностью была предложена Шафи Голдвассером и Сильвио Микали, основанная на сложности задачи об определении квадратичных вычетов и имевшая коэффициент расширения сообщения, равный размеру открытого ключа. Более эффективные вероятностные алгоритмы шифрования включают в себя ElGamal, Paillier и различные конструкции в модели случайного оракула, такие как OAEP.
Безопасность
Вероятностное шифрование особенно важно при использовании криптографии с открытым ключом. Предположим, что противник наблюдает зашифрованный текст и подозревает, что исходный текст – либо «ДА», либо «НЕТ», или у него есть подозрение, что исходный текст может быть «АТАКА НА КАЛЕ». При использовании детерминированного алгоритма шифрования противник может просто попытаться зашифровать каждую из своих гипотез с помощью открытого ключа получателя и сравнить каждый результат с целевым зашифрованным текстом. Чтобы противостоять этой атаке, схемы шифрования с открытым ключом должны включать элемент случайности, обеспечивая отображение каждого исходного текста в одно из большого числа возможных зашифрованных текстов. Интуитивно понятный способ преобразования детерминированной схемы шифрования в вероятностную – просто дополнить исходный текст случайной строкой перед шифрованием детерминированным алгоритмом. Соответственно, расшифровка включает применение детерминированного алгоритма и игнорирование случайного дополнения. Однако ранние схемы, использовавшие этот наивный подход, были взломаны из-за ограничений некоторых детерминированных схем шифрования. Методы, такие как оптимальное асимметричное заполнение (OAEP), интегрируют случайное дополнение таким образом, чтобы оно было безопасным при использовании любой односторонней перестановки с «черным ходом».