15
Тогда пространство сообщений
M - любая конечная последовательность це-
лых чисел из этого множества. Шифрование сообщения m = m1 • • • mA (где mi
∈
{0, . . . , 25}) с помощью
ключа k задается выражением
Enck (
m1 • • • mA ) = c1 • • • cA, где ci = [(mi + k) mod 26].
(Запись [
a mod
N ] обозначает остаток от деления на
N , при 0 ≤ [
a mod
N ] <
N
. Мы называем процесс отображения a в [
a mod
N ] как деление по модулю
N;
мы поговорим об этом подробнее в начале Г лавы 8.) Расшифровка шифртекста
c = c1 • • •
cA с помощью ключа k задана выражением
Dec
k (
c1 • • •
cA ) =
m1 • • •
mA, где
mi = [(
ci − k) mod 26].
Хорошо ли защищен сдвиговый шифр? Перед тем как продолжить чтение,
попытайтесь
расшифровать следующий текст, зашифрованный с помощью
сдвигового
шифра и секретного ключа k:
OVDTHUFWVZZPISLRLFZHYLAOLYL.
Можно ли восстановить сообщение не зная
k? На самом деле все просто! При-
чина в том, что всего существует только 26 возможных ключей. Поэтому можно
попытаться расшифровать шифрограмму с помощью перебора всех возмож-
ных ключей и тем самым получить 26 образцов открытого текста. Несомнен-
но среди них будет и верный образец; более того, если шифртекст «достаточно
большой», тогда правильный текст будет по всей вероятности единственным
образцом среди всех, который «обладает смыслом». (Последнее утверждение
необязательно должно быть верным, но оно справедливо в большинстве слу-
чаев. Даже когда это не так, атака сужает множество потенциальных текстов
максимум до 26.) Просмотрев весь перечень из 26 образцов, легко обнаружить
первоначальный открытый текст.
Атака, которая заключается в переборе всех возможных ключей, называется
ата-
кой методом грубой силы или
перебором всех возможных вариантов. Очевидно,
что стойкая криптосистема не должна быть уязвима атакам такого рода.³ Данное
замечание известно, как п
ринцип достаточности пространства ключей:
В любой стойкой криптосистеме пространство ключей должно
быть достаточно большим, чтобы свести на нет любые попыт-
ки атак методом перебора.
Можно дискутировать на тему того, сколько попыток должно быть, чтобы
считать взлом «неосуществимым», а точное определение осуществимости за-
висит, как от ресурсов потенциальной нападающей стороны, так и от длитель-
ности времени, в течение которого отправляющая и принимающая стороны
хотят обеспечивать секретность обмена данными. Сегодня злоумышленники
могут использовать суперкомпьютеры, тысячи персональных компьютеров или
16
графических процессоров для ускорения атак методом грубой силы. Для защиты
от таких атак необходимо, чтобы пространство ключей было очень большим - ска-
жем, размером как минимум 270 и даже больше, если имеется заинтересованность
в длительной защите от нападающих противников с хорошим финансированием.
Принцип достаточности пространства ключей предоставляет
необходимое
условие для безопасности, но НЕ достаточное. Это
проиллюстрировано в сле-
дующем примере.
Достарыңызбен бөлісу: