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



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

Необходимость ослаблений 
Вычислительная стойкость вводит два ослабления совершенной стойкости: во-
первых, криптографическая стойкость гарантируется только против эффективных 
противников; во-вторых, допускается малая вероятность успеха. Оба эти ослабле-
ния обязательны для создания практических систем шифрования и, в частности, 
для игнорирования отрицательных результатов абсолютного криптографически 
стойкого шифрования. Неформально обсудим, почему это именно так. Допустим, 
у нас есть система шифрования, где размер пространства ключа K гораздо меньше 
размера пространства сообщения M. (Как говорилось ранее в предыдущей главе, 
это значит, что система не может быть совершенно криптографически надежной.) 
Проводятся две атаки вне зависимости от конструкции системы шифрования:
• Задан шифртекст c, противник может расшифровать c, используя все ключи 
k ∈ K. Таким образом он получает перечень всех сообщения, к которым может 
относиться c. Поскольку этот перечень не содержит всех M (|K| < |M|), эта атака 
приводит к утечке некоторой информации о зашифрованном сообщении.
Кроме того, скажем, противник осуществляет атаку на основе открытых тек-
стов и узнает шифртексты c1, ..., cA, соответствующие сообщениям m1,..., mA. 
Противник может снова попытаться расшифровать эти шифртексты со всеми 
возможными ключами, пока не найдет ключ k, для которого Deck (ci) = mi для 
всех i. Позднее задан шифртекст c зашифрованного неизвестного сообщения m, 
почти наверняка окажется, что Deck (c) = m.
Атаки методом перебора, как указанные выше, позволяют противнику до-
биться успеха преимущественно один раз линейно от |K|.
• Снова рассмотрим случай, когда противник узнает шифртексты c1, ..., cA, 
соответствующие сообщениям m1, ..., mA. Противник может угадать унифици-
рованный ключ k ∈ K и проверить, верно ли Deck (ci) = mi для всех i. Если все 
так, как указано выше, то противник может использовать k для расшифровки 


61
всего, что в дальнейшем будет зашифровано честными участниками.
Здесь противник работает в главным образом постоянном времени и преуспе-
вает с ненулевой (хотя и очень малой) вероятностью 1/|K|.
Отсюда следует, что если мы хотим зашифровать множество сообщений с исполь-
зованием одного короткого ключа, криптографическая стойкость может быть достиг-
нута только при ограничении времени работы противника (тогда у противника не 
будет достаточного количества времени для поиска методом перебора) и готовности 
допустить очень малую вероятность успеха (тогда вторая «атака» исключена).


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




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

    Басты бет