Вероятностное шифрование

Вероятностное шифрование - это использование случайности в алгоритме шифрования , так что при многократном шифровании одного и того же сообщения, как правило, получаются разные зашифрованные тексты . Термин «вероятностное шифрование» обычно используется в отношении алгоритмов шифрования с открытым ключом ; однако различные алгоритмы шифрования с симметричным ключом достигают аналогичного свойства (например, блочные шифры при использовании в режиме цепочки, таком как CBC ), и потоковые шифры, такие как Freestyle ^[1], которые по своей природе являются случайными. Чтобы быть семантически безопасным , то есть скрывать даже частичную информацию ооткрытый текст , алгоритм шифрования должен быть вероятностным .

История [ править ]

Первая доказуемо-безопасная вероятностная схема шифрования с открытым ключом была предложена Шафи Голдвассером и Сильвио Микали , основанная на жесткости проблемы квадратичной остаточности и имеющая коэффициент расширения сообщения, равный размеру открытого ключа. Более эффективные алгоритмы вероятностного шифрования включают алгоритмы Эльгамаля , Пайе и различные конструкции в рамках модели случайного оракула , включая OAEP.

Безопасность [ править ]

Вероятностное шифрование особенно важно при использовании криптографии с открытым ключом . Предположим, что злоумышленник наблюдает за зашифрованным текстом и подозревает, что открытый текст имеет вид «ДА» или «НЕТ», или подозревает, что открытый текст может быть «АТАКА НА САЙТ». Когда используется детерминированный алгоритм шифрования , злоумышленник может просто попытаться зашифровать каждое из своих предположений открытым ключом получателя и сравнить каждый результат с целевым зашифрованным текстом. Для борьбы с этой атакой схемы шифрования с открытым ключом должны включать элемент случайности, гарантирующий, что каждый открытый текст отображается в один из большого числа возможных зашифрованных текстов.

Интуитивно понятный подход к преобразованию детерминированной схемы шифрования в вероятностную состоит в том, чтобы просто дополнить открытый текст случайной строкой перед шифрованием с помощью детерминированного алгоритма . И наоборот, дешифрование включает применение детерминированного алгоритма и игнорирование случайного заполнения. Однако ранние схемы, в которых применялся этот наивный подход, были сломаны из-за ограничений некоторых детерминированных схем шифрования. Такие методы, как оптимальное асимметричное шифрование (OAEP), интегрируют случайное заполнение безопасным способом с использованием любой перестановки лазейки .

Примеры [ править ]

Пример вероятностного шифрования с использованием любой перестановки лазейки:

x - однобитовый открытый текст
f - перестановка лазейки (детерминированный алгоритм шифрования)
б - твердое ядро предикат из F
r - случайная строка

${\ Displaystyle {\ rm {Enc}} (х) = (е (г), х \ oplus b (r))}$

${\ displaystyle {\ rm {Dec}} (y, z) = b (f ^ {- 1} (y)) \ oplus z}$

Это неэффективно, потому что зашифрован только один бит. Другими словами, коэффициент расширения сообщения равен размеру открытого ключа.

Пример вероятностного шифрования в модели случайного оракула:

x - открытый текст
f - перестановка лазейки (детерминированный алгоритм шифрования)
h - случайный оракул (обычно реализуется с использованием публично указанной хеш-функции )
r - случайная строка

${\ Displaystyle {\ rm {Enc}} (х) = (е (г), х \ oplus ч (г))}$

${\ displaystyle {\ rm {Dec}} (y, z) = h (f ^ {- 1} (y)) \ oplus z}$

См. Также [ править ]

Ссылки [ править ]

^ Puthuparambil, Arun Баба; Томас, Джитин Хосе (01.12.2019). «Freestyle, рандомизированная версия ChaCha для противодействия офлайн-брутфорсу и атакам по словарю». Журнал информационной безопасности и приложений . 49 : 102396. arXiv : 1802.03201 . DOI : 10.1016 / j.jisa.2019.102396 . ISSN 2214-2126 .

Внешние ссылки [ править ]

Шафи Гольдвассер и Сильвио Микали, Вероятностное шифрование , Специальный выпуск журнала Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, апрель 1984 г.
Freestyle, рандомизированная версия ChaCha для противодействия офлайн-брутфорсу и атакам по словарю [1] .

[1] Puthuparambil, Arun Баба; Томас, Джитин Хосе (01.12.2019). «Freestyle, рандомизированная версия ChaCha для противодействия офлайн-брутфорсу и атакам по словарю». Журнал информационной безопасности и приложений . 49 : 102396. arXiv : 1802.03201 . DOI : 10.1016 / j.jisa.2019.102396 . ISSN 2214-2126 .

[1],