Материал: MSZI_2003
356
Глава
18.
Криптографическая
защита
В
случае
безусловно
стойких
систем
их
стойкость
может
быть
доказана
,
но
что
каса
-
ется
теории
вычислительной
сложности
,
то
при
нынешнем
уровне
ее
развития
она
не
в
состоянии
продемонстрировать
вычислительную
нереализуемость
любой
криптографи
-
ческой
задачи
.
Поэтому
в
криптографии
возникло
и
развивается
направление
,
посвя
-
щенное
разработке
формальных
процессов
проверки
стойкости
.
Такие
процессы
сводят
-
ся
к
криптоаналитическому
нападению
на
предлагаемые
для
проверки
криптографиче
-
ские
системы
при
условиях
,
благоприятных
для
криптоаналитика
.
Единственной
безусловно
стойкой
системой
,
находящейся
в
широком
пользовании
,
является
лента
однократного
использования
,
в
которой
открытый
текст
объединяется
со
случайным
ключом
такой
же
длины
.
Обычно
открытый
текст
представляет
собой
строку
из
n
бит
,
которая
объединяются
со
случайным
ключом
такой
же
длины
с
помо
-
щью
сложения
по
модулю
2.
Как
видно
из
самого
названия
,
этот
ключ
никогда
больше
не
используется
.
Даже
если
бы
криптоаналитик
попытался
осуществить
дешифрирование
,
используя
все
2
n
возможных
ключей
,
он
просто
увидел
бы
все
2
n
возможных
открытых
текстов
одинаковой
длины
.
Поскольку
перехват
криптограммы
не
позволяет
криптоаналитику
вывести
какое
-
либо
сообщение
в
виде
открытого
текста
,
то
он
не
узнает
ничего
,
кроме
длины
сообщения
.
Клод
Шеннон
анализировал
абсолютную
стойкость
более
подробно
.
Если
криптоаналитик
располагает
неограниченным
временем
для
вычислений
,
то
он
не
связан
рамками
вычислительной
эффективности
и
может
провести
полный
криптоана
-
лиз
,
испытывая
все
возможные
ключи
и
сохраняя
в
качестве
результата
все
осмыслен
-
ные
тексты
.
В
случае
ленты
однократного
использования
необходимо
сохранить
все
ос
-
мысленные
тексты
,
имеющие
одинаковую
с
криптограммой
длину
,
но
в
других
безус
-
ловно
стойких
системах
может
быть
меньшее
количество
осмысленных
решений
.
Например
,
криптограмма
XMDA,
полученная
в
результате
простой
подстановки
годится
для
любого
четырехбуквенного
слова
с
неповторяющимися
буквами
.
По
мере
того
как
количество
перехваченных
текстов
возрастает
,
может
быть
достиг
-
нута
точка
,
в
которой
оказывается
возможным
получение
однозначного
решения
.
Шен
-
нон
назвал
это
интервалом
однозначности
N
0
.
В
случае
ленты
однократного
использова
-
ния
этого
никогда
не
случиться
,
и
N
0
=
∞
,
тогда
как
в
случае
простого
подстановочного
шифра
значение
N
0
конечно
.
Шеннон
предложил
модель
для
предсказания
интервала
однозначности
шифра
.
Полученные
с
помощью
этой
модели
результаты
согласуются
с
практикой
.
В
соответствии
с
этой
моделью
“
случайного
шифра
”
N
0
=
H(K)
D
(18.7)
где
H(K)
—
энтропия
ключа
(
обычно
это
просто
длина
ключа
,
измеренная
в
битах
,
или
log
2
от
количества
ключей
),
D
—
избыточность
языка
,
измеренная
в
битах
на
1
знак
.
(
Например
,
в
английском
языке
за
буквой
Q
всегда
следует
буква
U,
которая
является
избыточной
.)
Качественно
модель
можно
показать
,
переписав
(18.7)
в
виде
требования
для
однозначности
решения
H(K)
≤
N
0
D
(18.8)
Безусловная
и
теоретическая
стойкость
357
где
H(K)
характеризует
количество
неизвестных
в
двоичном
представлении
ключа
,
а
N
0
D
в
широком
смысле
определяет
количество
уравнений
,
которые
необходимо
решить
для
нахождения
ключа
.
Когда
количество
уравнений
меньше
количества
неизвестных
,
однозначное
решение
невозможно
и
система
является
безусловно
стойкой
.
Когда
коли
-
чество
уравнений
больше
количества
неизвестных
,
т
.
е
.
как
в
(18.8),
однозначное
реше
-
ние
возможно
и
система
не
является
безусловно
стойкой
,
хотя
она
все
еще
может
быть
вычислительно
стойкой
.
Несмотря
на
то
,
что
в
теории
кодирования
Шеннона
(
т
.
е
.
в
предположении
,
что
крип
-
тоаналитик
располагает
неограниченными
ресурсами
)
обычно
рассматривается
нападе
-
ние
при
наличии
только
шифрованного
текста
,
но
иногда
используются
и
комбинации
шифрованного
и
открытого
текста
,
что
повышает
избыточность
.
Уравнение
(18.7)
показывает
ценность
снятия
данных
,
производимого
перед
шифро
-
ванием
.
Согласно
Фридмэну
,
почти
любая
криптограмма
из
25
букв
и
более
,
полученная
подстановкой
,
может
быть
раскрыта
.
Поскольку
криптоаналитик
располагает
ограни
-
ченными
вычислительными
возможностями
,
он
не
может
перепробовать
все
26!
≈
4.10
26
ключей
и
должен
полагаться
на
субоптимальные
методы
,
такие
как
частотный
анализ
.
Таким
образом
,
можно
сказать
,
что
N
0
= 25
знаков
.
В
случае
ленты
однократного
использования
H(K) =
∞
,
откуда
,
согласно
(7),
N
0
=
∞
.
После
простой
подстановки
получаем
H(K) = log
2
(26!) = 88,4
бит
,
поэтому
для
вычис
-
ления
N
0
принято
находить
D
.
Каждый
знак
мог
бы
переносить
максимум
log
2
(26) = 4,7
бит
информации
,
если
бы
все
комбинации
были
возможны
.
Но
поскольку
правила
пра
-
вописания
и
грамматики
запрещают
использование
большинства
комбинаций
,
то
в
сред
-
нем
каждый
знак
переносит
всего
лишь
1,5
бит
информации
.
Оставшиеся
3,2
бит
оказы
-
ваются
избыточными
,
откуда
D = 3,2
бит
/
знак
.
Таким
образом
,
уравнение
(18.7)
пред
-
ставляет
величину
N
0
= 28
знаков
,
что
хорошо
согласуется
с
практикой
.
Например
,
если
перехвачено
сообщение
длиной
в
1000
знаков
и
известна
некоторая
последовательность
из
100
знаков
открытого
текста
,
то
общая
избыточность
составит
не
3200
бит
,
а
(
900
знаков
)
×
(
3,2
бит
/
знак
)
+
(
100
знаков
)
×
(
4,7
бит
/
знак
)
= 3350
бит
.
Сжатие
данных
устраняет
избыточность
,
увеличивая
тем
самым
интервал
однознач
-
ности
.
Избыточная
информация
может
быть
добавлена
после
дешифрирования
.
Совер
-
шенное
сжатие
данных
устранило
бы
всю
избыточность
и
привело
бы
к
N
0
=
∞
при
лю
-
бой
длине
ключа
,
но
это
довольно
дорогое
мероприятие
.
Важным
подготовительным
этапом
для
проверки
стойкости
шифра
является
проду
-
мывание
различных
предполагаемых
возможностей
,
с
помощью
которых
противник
мо
-
жет
вскрыть
шифр
.
Появление
таких
возможностей
у
противника
обычно
не
зависит
от
собственно
используемого
криптографического
метода
,
а
является
следствием
некото
-
рой
внешней
подсказки
,
наличие
которой
существенно
влияет
на
стойкость
шифра
.
По
-
этому
оценки
стойкости
шифра
всегда
содержат
те
предположения
о
противнике
,
в
ус
-
ловиях
которых
эти
оценки
получены
.
Прежде
всего
,
обычно
считается
,
что
противник
знает
сам
шифр
и
имеет
возможность
его
предварительного
изучения
.
Противник
также
знает
некоторые
характеристики
откры
-
358
Глава
18.
Криптографическая
защита
тых
текстов
(
защищаемой
информации
),
например
,
общую
тематику
сообщений
,
их
стиль
,
некоторые
стандарты
,
форматы
и
т
.
д
.
Приведем
три
примера
специфических
возможностей
противника
:
•
противник
может
перехватывать
все
шифрованные
сообщения
,
но
не
имеет
соответ
-
ствующих
им
открытых
текстов
;
•
противник
может
перехватывать
все
шифрованные
сообщения
и
добывать
соответст
-
вующие
им
открытые
тексты
;
•
противник
имеет
доступ
к
шифру
(
но
не
к
ключам
!)
и
поэтому
может
зашифровать
любую
информацию
.
На
протяжении
многих
веков
среди
специалистов
не
утихали
споры
о
стойкости
шифров
и
о
возможности
построения
абсолютно
стойкого
шифра
.
“
Отец
кибернетики
”
Норберт
Винер
отмечал
: “
Любой
шифр
может
быть
вскрыт
,
если
только
в
этом
есть
настоятельная
необходимость
и
информация
,
которую
предпо
-
лагается
получить
,
стоит
затраченных
средств
,
усилий
и
времени
…”
Поэтому
у
пользователя
остается
единственный
путь
—
получение
практических
оценок
стойкости
.
Этот
путь
состоит
из
следующих
этапов
.
1.
Понять
и
четко
сформулировать
,
от
какого
противника
необходимо
защищать
ин
-
формацию
.
Следует
уяснить
,
что
именно
противник
знает
или
может
узнать
о
систе
-
ме
шифра
,
какие
силы
и
средства
он
сможет
применить
для
его
вскрытия
.
2.
Мысленно
стать
в
положение
противника
и
попытаться
с
его
позиций
вскрыть
шифр
,
т
.
е
.
разработать
различные
алгоритмы
вскрытия
шифра
,
обеспечивая
при
этом
в
мак
-
симальной
мере
моделирование
сил
,
средств
и
возможностей
противника
.
3.
Наилучший
из
разработанных
алгоритмов
использовать
для
практической
оценки
стойкости
шифра
.
Следует
упомянуть
о
двух
простейших
методах
вскрытия
шифра
:
случайного
угады
-
вания
ключа
(
он
срабатывает
с
малой
вероятностью
,
но
является
самую
низкую
вычис
-
лительную
сложность
)
и
перебора
всех
подряд
ключей
вплоть
до
нахождения
истинного
(
он
срабатывает
всегда
,
но
имеет
самую
высокую
вычислительную
сложность
).
Анализ
основных
криптографических
методов
ЗИ
Иногда
криптографические
методы
ЗИ
разделяют
на
три
группы
:
методы
подста
-
новки
,
методы
перестановки
и
аддитивные
методы
.
Методы
перестановки
и
подста
-
новки
характеризуются
хорошими
ключами
,
а
их
надежность
связана
со
сложным
алго
-
ритмом
преобразования
.
При
аддитивных
методах
пользуются
простыми
алгоритмами
преобразования
,
обеспечивая
надежность
с
помощью
ключей
большого
объема
.
Иногда
говорят
о
блочных
методах
,
имея
в
виду
первые
две
группы
,
в
которых
ал
-
горитм
работает
сразу
над
большим
блоком
информации
,
и
о
потоковых
методах
,
где
шифрование
происходит
знак
за
знаком
.
Однако
при
использовании
аддитивных
мето
-
дов
преобразование
может
осуществляться
сразу
над
целым
машинным
словом
и
метод
приобретает
признаки
блочного
.
Анализ
основных
криптографических
методов
ЗИ
359
Шифрование
методом
подстановки
(
замены
)
В
этом
,
наиболее
простом
,
методе
символы
шифруемого
текста
заменяются
другими
символами
,
взятыми
из
одного
(
моноалфавитная
подстановка
)
или
нескольких
(
полиал
-
фавитная
подстановка
)
алфавитов
.
Самой
простой
разновидностей
является
прямая
за
-
мена
,
когда
буквы
шифруемого
текста
заменяются
другими
буквами
того
же
самого
или
некоторого
другого
алфавита
.
Если
объем
зашифрованного
текста
большой
,
то
частоты
появления
букв
в
зашифро
-
ванном
тексте
будут
ближе
к
частотам
появления
букв
в
алфавите
(
того
языка
,
на
кото
-
ром
написан
текст
)
и
расшифровка
будет
очень
простой
.
Поэтому
простую
замену
в
настоящее
время
используют
редко
и
в
тех
случаях
,
когда
шифруемый
текст
короток
.
Для
повышения
стойкости
шифра
используют
так
называемые
полиалфавитные
под
-
становки
,
в
которых
для
замены
символов
исходного
текста
используются
символы
не
-
скольких
алфавитов
.
Существует
несколько
разновидностей
полиалфавитной
подста
-
новки
,
наиболее
известными
из
которых
являются
одно
- (
обыкновенная
и
монофониче
-
ская
)
и
многоконтурная
.
При
полиалфавитной
одноконтурной
обыкновенной
подстановке
для
замены
симво
-
лов
исходного
текста
используется
несколько
алфавитов
,
причем
смена
алфавитов
осу
-
ществляется
последовательно
и
циклически
,
т
.
е
.
первый
символ
заменяется
соответст
-
вующим
символом
первого
алфавита
,
второй
—
символом
второго
алфавита
и
т
.
д
.
до
тех
пор
,
пока
не
будут
использованы
все
выбранные
алфавиты
.
После
этого
использование
алфавитов
повторяется
.
В
качестве
примера
рассмотрим
шифрование
с
помощью
таблицы
Виженера
.
Таблица
Виженера
представляет
собой
матрицу
с
n
2
элементами
,
где
n
—
количество
символов
используемого
алфавита
.
Каждая
строка
матрицы
получена
циклическим
сдвигом
алфа
-
вита
на
символ
.
Для
шифрования
выбирается
буквенный
ключ
,
в
соответствии
с
кото
-
рым
формируется
рабочая
матрица
шифрования
.
Осуществляется
это
следующим
обра
-
зом
.
Из
полной
таблицы
выбирается
первая
строка
и
те
строки
,
первые
буквы
которых
соответствуют
буквам
ключа
.
Первой
размещается
первая
строка
,
а
под
нею
—
строки
,
соответствующие
буквам
ключа
в
порядке
следования
этих
букв
в
ключе
.
Сам
процесс
шифрования
осуществляется
следующим
образом
:
•
под
каждой
буквой
шифруемого
текста
записывают
буквы
ключа
(
ключ
при
этом
по
-
вторяется
необходимое
количество
раз
);
•
каждая
буква
шифруемого
текста
заменяется
по
подматрице
буквами
,
находящимися
на
пересечении
линий
,
соединяющих
буквы
шифруемого
текста
в
первой
строке
подматрицы
и
находящихся
под
ними
букв
ключа
;
•
полученный
текст
может
разбиваться
на
группы
по
несколько
знаков
.
Исследования
показали
,
что
при
использовании
такого
метода
статистические
харак
-
теристики
исходного
текста
практически
не
проявляются
в
зашифрованном
тексте
.
Не
-
трудно
заметить
,
что
замена
по
таблице
Виженера
эквивалентна
простой
замене
с
цик
-
лическим
изменением
алфавита
,
т
.
е
.
здесь
мы
имеем
полиалфавитную
подстановку
,
при
-
360
Глава
18.
Криптографическая
защита
чем
число
используемых
алфавитов
определяется
числом
букв
в
ключе
.
Поэтому
стой
-
кость
такой
замены
определяется
произведением
прямой
замены
на
количество
исполь
-
зуемых
алфавитов
,
т
.
е
.
на
количество
букв
в
ключе
.
Одним
из
недостатков
шифрования
по
таблице
Виженера
является
то
,
что
при
не
-
большой
длине
ключа
надежность
шифрования
остается
невысокой
,
а
формирование
длинных
ключей
сопряжено
с
определенными
трудностями
.
Нецелесообразно
выбирать
ключи
с
повторяющимися
буквами
,
так
как
при
этом
стойкость
шифра
не
возрастает
.
В
то
же
время
ключ
должен
легко
запоминаться
,
чтобы
его
можно
было
не
записывать
.
Последовательность
же
букв
,
не
имеющих
смысла
,
за
-
помнить
трудно
.
С
целью
повышения
стойкости
шифрования
можно
использовать
усовершенствован
-
ные
варианты
таблицы
Виженера
.
Отметим
некоторые
из
них
:
•
во
всех
(
кроме
первой
)
строках
таблицы
буквы
располагаются
в
произвольном
по
-
рядке
;
•
в
качестве
ключа
используются
случайные
последовательности
чисел
.
Из
таблицы
Виженера
выбираются
десять
произвольных
строк
,
которые
кодируются
натуральными
числами
от
0
до
10.
Эти
строки
используются
в
соответствии
с
чередова
-
нием
цифр
в
выбранном
ключе
.
Частным
случаем
рассмотренной
полиалфавитной
подстановки
является
так
назы
-
ваемая
монофоническая
подстановка
.
Особенность
этого
метода
состоит
в
том
,
что
ко
-
личество
и
состав
алфавитов
выбираются
таким
образом
,
чтобы
частоты
появления
всех
символов
в
зашифрованном
тексте
были
одинаковыми
.
При
таком
положении
затрудня
-
ется
криптоанализ
зашифрованного
текста
с
помощью
его
статической
обработки
.
Вы
-
равнивание
частот
появления
символов
достигается
за
счет
того
,
что
для
часто
встре
-
чающихся
символов
исходного
текста
предусматривается
использование
большего
чис
-
ла
заменяющих
элементов
,
чем
для
редко
встречающихся
.
Полиалфавитная
многоконтурная
подстановка
заключается
в
том
,
что
для
шифро
-
вания
используется
несколько
наборов
(
контуров
)
алфавитов
,
используемых
цикличе
-
ски
,
причем
каждый
контур
в
общем
случае
имеет
свой
индивидуальный
период
приме
-
нения
.
Этот
период
исчисляется
,
как
правило
,
количеством
знаков
,
после
зашифровки
которых
меняется
контур
алфавитов
.
Частным
случаем
многоконтурной
полиалфавит
-
ной
подстановки
является
замена
по
таблице
Вижинера
,
если
для
шифрования
использу
-
ется
несколько
ключей
,
каждый
из
которых
имеет
свой
период
применения
.
Общая
модель
шифрования
подстановкой
может
быть
представлена
в
следующем
виде
:
t
i
c
= t
i
p
+
ω
mod (K – 1)
где
t
i
c
—
символ
зашифрованного
текста
;
t
i
p
—
символ
исходного
текста
;
ω
—
целое
чис
-
ло
в
диапазоне
от
0
до
(
К
–1
);
К
—
количество
символов
используемого
алфавита
.
Если
ω
фиксировано
,
то
формула
описывает
моноалфавитную
подстановку
,
если
ω
выбирается
из
последовательности
ω
1
,
ω
2
, …,
ω
n
,
то
получается
полиалфавитная
под
-
становка
с
периодом
n
.