Введение в современную криптографию


Основное понятие криптографической стойкости



Pdf көрінісі
бет42/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   38   39   40   41   42   43   44   45   ...   249
Криптография Катц

 3.2.1 Основное понятие криптографической стойкости 
Начнем с наиболее основного понятия криптостойкости при шифровании с 
закрытым ключом: криптостойкость против атаки на основе шифртекста, где 
противник исследует только один шифртекст, или криптостойкость, когда дан-
ный ключ используется для шифрования только одного сообщения. Далее в гла-
ве мы рассмотрим более строгие определения криптостойкости.
Объяснение определения.  Как было сказано ранее, любое определение крип-
тостойкости состоит из двух отдельных компонентов: модели угроз (т.е. опре-
деления допускаемых возможностей противника) и цель безопасности (обычно 
определяется посредством описания того, что подразумевается под «взломом» 
системы). Начнем разбор определения с рассмотрения простейшей модели угроз, 
где противник-перехватчик исследует единственное зашифрованное сообщение. 
Это именно так модель угроз, которую мы рассматривали в предыдущей главе, за 
исключением того, что, как уже говорилось в предыдущем разделе, нас интере-
суют противники, обладающие ограниченными вычислительными возможностя-
ми, и, как следствие, работающие в полиномиальном времени.
И хотя мы сделали два допущения относительно возможностей противника (он 
только перехватывает сообщение и работает в полиномиальном времени), мы не 
сделали никаких допущений касательно стратегии противника, пытающегося рас-
шифровать исследуемый им шифртекст. Это особенно важно для значимого поня-
тия криптостойкости. Определение обеспечивает защиту от любого вычислительно 
ограниченного противника вне зависимости от используемого им алгоритма.
Правильное определение цели безопасности шифрования не просто, но мы уже 
подробно рассмотрели этот вопрос в разделе 1.4.1 и в предыдущей главе. Так или 
иначе, напомним, что смысл определения заключается в том, что противник не дол-
жен суметь узнать любой частичной информации об открытом тексте из шифртек-
ста. Определение семантической криптостойкости (см. Раздел 3.2.2) точно фор-


63
мализует это понятие и представляет собой первое из когда-либо предложенных 
определений вычислительно надежного шифрования. Семантическая криптостой-
кость - сложно е понятие, с которым трудно работать. К счастью, существует равно-
сильное и более простое определение, называемое неразличимостью.
Определение неразличимости сформулировано по образцу альтернативного 
определения совершенной криптостойкости (см. Определение 2.5). (Еще одна 
причина того, почему определение неопределенности хорошо.) Напомним, что 
Определение 2.5 включает в себя эксперимент 
, в котором противник 
A выводит два сообщения m0 и m1, а затем получает одно из этих сообщений, 
зашифрованное с помощью унифицированного ключа. В определении говорит-
ся, что система Π надежна, если ни один противник A не сможет определить, 
какое из сообщений m0, m1 было зашифровано, с вероятностью, отличной от 
1/2, которая равносильна вероятности того, что A правильно угадает ответ.
А теперь перейдем к эксперименту 
почти аналогичному (за ис-
ключением некоторых технических различий, указанных ниже) тому, что мы уже 
проводили, однако, мы внесем два ключевых изменения в само определение:
1. Теперь мы рассматриваем только противников, работающих в полиноми-
альном времени, хотя в определении 2.5 рассматривались даже противники с 
неограниченным временем работы.
2. Теперь мы допускаем, что противник может определить зашифрованное 
сообщение с вероятностью пренебрежимо большей, чем 1/2.
Как уже было сказано в предыдущем разделе, упомянутые выше ослабления 
являются ключевыми элементами вычислительной криптостойкости.
Что же касается других отличий, основным является то, что теперь мы пара-
метризуем эксперимент посредством параметра безопасности n. Тогда мы из-
меряем как время работы противника A, так и вероятность его успеха в качестве 
функций по n. Запишем 
(n), чтобы обозначить, что эксперимент про-
водится с учетом параметра безопасности n, и запишем
(n) = 1]
(3.1)
для обозначения вероятности того, что результатом эксперимента Pr 
(n) является 1. Обратите внимание, что при фиксированных A, Π, уравнение 
(3.1) является функцией по n.
Второе отличие эксперимента 
заключается в том, что теперь нам 
явно требуется, чтобы противник вывел два сообщения m0, m1 равной длины
(В определении 2.5 это требование подразумевается, если пространство сооб-
щения M содержит только сообщения фиксированной длины, как это происхо-
дит при шифровании Вернама.) Это означает, что по умолчанию для надежного 


64
шифрования на не требуется скрывать длину открытого текста. Мы вернемся к 
этому моменту в конце данного раздела (также см. упражнения 3.2 и 3.3).


Достарыңызбен бөлісу:
1   ...   38   39   40   41   42   43   44   45   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет