Материал: MSZI_2003
366
Глава
18.
Криптографическая
защита
Иногда
код
состоит
из
списка
слов
и
фраз
вместе
с
соответствующими
им
случайны
-
ми
группами
чисел
и
букв
,
называемыми
кодовыми
группами
.
Поскольку
кодовые
груп
-
пы
обычно
короче
выражений
,
которые
они
представляют
,
коды
,
помимо
секретности
,
обеспечивают
также
и
сжатие
информации
.
При
правильном
использовании
коды
намного
труднее
раскрыть
,
чем
другие
класси
-
ческие
системы
.
Успех
их
использования
объясняется
тремя
причинами
.
Наиболее
важ
-
ной
их
них
является
большая
длина
используемого
ключа
.
В
типичной
системе
шифро
-
вания
используется
ключ
длиной
максимум
несколько
сотен
бит
.
Например
,
ключом
шифра
на
основе
простой
подстановки
является
переставленный
алфавит
,
представляю
-
щий
в
среднем
90
бит
,
тогда
как
кодовая
книга
хорошего
размера
может
содержать
сот
-
ни
тысяч
и
даже
миллион
бит
.
Как
показал
Шеннон
,
работа
криптоаналитика
затрудня
-
ется
,
когда
из
сообщения
удаляется
избыточность
,
а
коды
удаляют
избыточность
.
При
-
чем
,
коды
работают
с
относительно
большими
блоками
открытого
текста
(
словами
и
фразами
)
и
,
следовательно
,
скрывают
локальную
информацию
,
которая
в
противном
случае
могла
бы
дать
ценные
“
зацепки
”
для
криптоанализа
.
К
недостаткам
следует
отнести
то
,
что
ключ
при
кодировании
используется
недос
-
таточно
хорошо
,
так
как
при
кодировании
отдельного
слова
и
фразы
используется
лишь
очень
малая
часть
кодовой
книги
.
В
результате
код
при
интенсивном
использовании
поддается
частичному
анализу
и
оказывается
особенно
чувствительным
к
вскрытию
при
наличии
известного
открытого
текста
.
По
этим
причинам
для
обеспечения
большей
на
-
дежности
коды
необходимо
чаще
менять
.
К
другим
видам
криптографического
закрытия
отнесены
рассечение
/
разнесение
и
сжатие
данных
.
Рассечение
/
разнесение
данных
состоит
в
том
,
что
массив
защищаемых
данных
рассекается
на
такие
элементы
,
каждый
из
которых
не
позволяет
раскрыть
со
-
держание
защищаемой
информации
,
и
выделенные
таким
образом
элементы
размеща
-
ются
в
различных
зонах
памяти
.
Обратная
процедура
называется
сборкой
данных
.
Со
-
вершенно
очевидно
,
что
алгоритм
разнесения
и
сборки
данных
должен
сохраняться
в
тайне
.
Шифрование
с
открытым
ключом
Одно
из
главных
ограничений
использования
обычных
криптографических
систем
связано
с
трудностью
распространения
ключей
.
Диффи
и
Хеллман
,
а
также
,
независимо
от
них
,
Меркль
,
показали
,
что
можно
исключить
защищенный
канал
передачи
ключей
и
при
этом
обеспечить
защиту
при
передаче
сообщений
по
незащищенному
каналу
без
осуществления
каких
-
либо
предварительных
мероприятий
.
Как
видно
из
рис
. 18.6,
меж
-
ду
отправителем
и
получателем
допускается
двухсторонний
обмен
,
но
перехватчик
здесь
пассивный
и
только
слушает
.
В
отличие
от
обычных
систем
,
в
которых
ключ
должен
со
-
хранятся
в
секрете
,
системы
,
допускающие
такую
работу
,
называются
системами
с
от
-
крытым
ключом
.
Анализ
основных
криптографических
методов
ЗИ
367
Рис
. 18.6.
Поток
информации
в
криптографической
системе
с
открытым
ключом
Для
решения
этой
проблемы
предлагаются
два
подхода
.
При
открытом
распростра
-
нении
ключей
отправитель
и
получатель
могут
договориться
о
ключе
,
используемом
в
обычной
криптографической
системе
.
Несмотря
на
то
,
что
противник
слушает
все
пере
-
говоры
,
он
не
в
состоянии
вычислить
ключ
и
не
может
понять
последующего
обмена
со
-
общениями
.
Второй
подход
реализует
криптографические
системы
с
открытыми
ключа
-
ми
,
в
которых
для
шифрования
используются
разные
ключи
.
Причина
,
по
которой
ключи
в
обычных
криптографических
системах
должны
столь
тщательно
защищаться
,
состоит
в
том
,
что
функции
шифрования
и
дешифрования
в
ней
неразделимы
.
Любое
лицо
,
получившее
ключ
для
шифрования
сообщений
,
может
также
дешифровать
сообщения
.
Если
средства
шифрования
разделены
,
то
секретность
можно
обеспечить
без
засекречивания
ключа
шифрования
,
так
как
его
нельзя
исполь
-
зовать
для
расшифровывания
.
Взаимодействуя
по
открытым
каналам
связи
,
абоненты
А
и
В
решают
следующие
за
-
дачи
:
•
вначале
у
А
и
В
нет
никакой
общей
секретной
информации
,
но
в
конце
процедуры
такая
общая
секретная
информация
(
общий
ключ
)
у
А
и
В
появляется
,
т
.
е
.
вырабаты
-
вается
;
•
противник
,
который
перехватывает
все
передачи
и
знает
,
что
хочет
получить
А
и
В
,
тем
не
менее
не
может
восстановить
выработанный
общий
ключ
А
и
В
.
Предложено
решать
эти
задачи
с
помощью
функции
F(x) =
α
x
(mod p)
,
где
р
—
большое
простое
число
,
x
—
произвольное
натуральное
число
,
α
—
некоторый
прими
-
тивный
элемент
поля
G F(p)
.
Примитивным
называется
такой
элемент
α
из
G F(p)
,
что
каждый
элемент
поля
,
может
быть
представлен
в
виде
степени
α
.
Доказывается
,
что
примитивный
элемент
все
-
гда
существует
.
Общепризнанно
,
что
инвертирование
функции
α
x
(mod p)
,
т
.
е
.
дискретное
логариф
-
мирование
,
является
трудной
математической
задачей
.
Саму
же
процедуру
или
,
как
принято
говорить
,
протокол
выработки
общего
ключа
,
можно
описать
следующим
образом
.
Числа
р
и
α
считаются
общедоступными
.
368
Глава
18.
Криптографическая
защита
Абоненты
А
и
В
независимо
друг
от
друга
случайно
выбирают
по
одному
натураль
-
ному
числу
—
скажем
x
A
и
x
B
и
.
Эти
элементы
они
держат
в
секрете
.
Далее
каждый
из
них
вычисляет
новый
элемент
:
у
A
=
α
x
A
(mod p)
,
у
B
=
α
x
B
(mod p)
Потом
они
обмениваются
этими
элементами
по
каналу
связи
.
Теперь
абонент
А
,
получив
у
B
и
зная
свой
секретный
элемент
x
A
,
вычисляет
новый
элемент
:
у
B
x
A
=
(
α
x
B
)
x
A
(mod p)
Аналогично
поступает
абонент
В
:
у
A
x
B
=
(
α
x
A
)
x
B
(mod p)
Из
свойств
поля
следует
,
что
тем
самым
у
А
и
В
появится
общий
элемент
,
который
и
является
общим
ключом
А
и
В
.
Из
описания
протокола
видно
,
что
противник
знает
p
,
α
,
α
x
A
,
α
x
B
,
не
знает
x
A
,
x
B
и
хочет
узнать
α
x
A
x
B
.
В
настоящее
время
нет
алгоритмов
действий
противника
,
более
эф
-
фективных
,
чем
дискретное
логарифмирование
,
а
это
—
труднейшая
математическая
за
-
дача
.
Эти
системы
должны
разрабатываться
таким
образом
,
чтобы
облегчить
генерацию
случайных
пар
инверсных
ключей
Е
для
шифрования
и
Д
для
дешифрования
и
работу
с
этими
ключами
,
но
чтобы
вычисления
Д
по
Е
было
вычислительно
нереализуемым
.
Криптографическая
система
с
открытым
ключом
представляет
собой
пару
семейств
алгоритмов
{E
K
}
K
∈
{K}
и
{
Д
K
}
K
∈
{K}
,
определяющих
обратимые
преобразования
EK:{M}
→
{m}
Д
K:{M}
→
{m}
,
на
конечном
пространстве
сообщений
{M}
со
следующими
свойствами
.
1.
Для
каждого
K
∈
{K}
Д
K
обратно
к
E
K
,
т
.
е
.
при
любых
К
и
М
справедливо
Д
К
Е
К
(
М
)
=
М
.
2.
Для
каждого
K
∈
{K}
и
M
∈
{M}
нетрудно
вычислить
величины
Е
К
(
М
)
и
Д
К
(
М
)
.
3.
Для
почти
каждого
K
∈
{K}
невозможно
в
вычислительном
отношении
вывести
из
Е
К
какой
-
либо
легко
выполнимый
алгоритм
,
эквивалентный
Д
К
.
4.
По
каждому
заданному
K
∈
{K}
можно
получить
инверсную
пару
Е
К
и
Д
К
.
Свойство
3
позволяет
не
засекречивать
ключи
шифрования
пользователя
Е
К
и
при
этом
не
компроментировать
секретность
ключа
дешифрования
Д
К
.
Следовательно
,
криптогафические
системы
распадаются
на
две
части
(
семейство
преобразований
шиф
-
рования
и
семейство
преобразований
дешифрования
)
таким
образом
,
что
по
данному
члену
одного
семейства
невозможно
определить
соответствующий
член
другого
.
Свойство
4
гарантирует
наличие
реализуемого
пути
вычисления
соответствующих
пар
обратных
преобразований
,
когда
не
наложено
никаких
ограничений
на
то
,
каким
должно
быть
преобразование
шифрования
или
дешифрования
.
На
практике
криптогра
-
Цифровая
подпись
369
фическое
оборудование
должно
содержать
генератор
истинных
случайных
чисел
для
ге
-
нерации
К
,
а
также
генерирующий
пару
E
К
и
Д
К
по
заданному
K
.
Система
такого
рода
упрощает
проблему
распределения
ключей
.
Каждый
пользова
-
тель
генерирует
пару
взаимно
обратных
преобразований
Е
и
Д
.
Он
держит
преобразова
-
ние
дешифрования
Д
в
секрете
,
а
преобразование
шифрования
публикует
в
открытом
справочнике
наподобие
технического
справочника
.
Теперь
любой
желающий
может
шифровать
сообщения
и
посылать
их
пользователю
,
но
никто
,
кроме
него
,
не
может
де
-
шифровать
предназначенные
для
него
сообщения
.
Если
вместо
приведенных
условий
1–4
множество
преобразований
обеспечивает
,
что
для
каждого
K
∈
{K}
E
K
является
обратным
Д
K
,
т
.
е
.
при
любых
К
и
М
справедливо
ут
-
верждение
Е
К
Д
К
(
М
) =
М
,
то
возможно
,
а
часто
и
желательно
осуществлять
шифрова
-
ние
с
помощью
ключа
Д
,
а
дешифрование
—
с
помощью
ключа
Е
.
По
этой
причине
час
-
то
называют
E
K
открытым
ключом
,
а
Д
K
—
личным
ключом
.
За
время
,
истекшее
после
того
,
как
была
предложены
эта
система
,
разработано
не
-
сколько
путей
ее
реализации
.
Цифровая
подпись
Идея
цифровой
подписи
(
ее
еще
называют
электронной
подписью
)
была
предложе
-
на
Диффи
и
Хеллманом
.
Суть
ее
заключается
в
использовании
односторонней
функции
с
секретом
F
К
.
В
настоящее
время
эта
идея
реализована
в
большом
количестве
систем
пе
-
редачи
данных
.
Сообщение
,
подписанное
цифровой
подписью
,
можно
представить
в
ви
-
де
пары
(x,y)
,
где
x
—
сообщение
,
F
К
: x
→
y —
односторонняя
функция
,
известная
всем
взаимодействующим
абонентам
,
y
—
решение
уравнения
F
К
(y) = x
.
Из
определения
функции
F
К
очевидны
следующие
достоинства
цифровой
подписи
.
1.
Подписать
сообщение
x
,
т
.
е
.
решить
уравнение
F
K
(y) = x
,
может
только
абонент
,
яв
-
ляющийся
обладателем
данного
секрета
К
;
другими
словами
,
подделать
подпись
не
-
возможно
.
3.
Проверить
подлинность
подписи
может
любой
абонент
,
знающий
открытый
ключ
,
т
.
е
.
саму
функцию
F
K
.
4.
При
возникновении
споров
отказаться
от
подписи
невозможно
в
силу
ее
неподделы
-
ваемости
.
5.
Подписанные
сообщения
(x,y)
можно
,
не
опасаясь
ущерба
,
пересылать
по
любым
ка
-
налам
связи
.
Именно
перечисленные
достоинства
и
обусловили
широкой
применение
и
распро
-
странение
систем
цифровой
подписи
.
Как
практически
выглядит
использование
цифровой
подписи
?
Рассмотрим
,
как
осу
-
ществляется
работа
банка
с
платежными
поручениями
своих
клиентов
.
Все
абоненты
этой
сети
знают
одностороннюю
функцию
F
K
,
и
каждый
клиент
имеет
собственный
,
ни
-
кому
неизвестный
секрет
К
.
Клиент
подписывает
платежное
поручение
x
с
помощью
функции
F
K
со
своим
секретом
К
и
посылает
подписанное
платежное
поручение
в
банк
.
Банк
,
получив
сообщение
от
клиента
и
зная
открытый
ключ
,
проверяет
подлинность
370
Глава
18.
Криптографическая
защита
подписи
клиента
и
только
после
этого
выполняет
его
платежное
поручение
.
В
силу
от
-
меченных
достоинств
цифровой
подписи
и
банк
,
и
клиент
уверены
,
что
их
интересы
не
пострадают
.
Широкое
развитие
систем
электронных
платежей
,
электронной
почты
и
других
сис
-
тем
передачи
данных
потребовало
большого
разнообразия
цифровых
подписей
.
Это
привело
к
развитию
теории
протоколов
цифровой
подписи
,
которая
в
настоящее
время
составляет
большой
раздел
теоретической
криптографии
.
В
рамках
этой
теории
система
-
тизированы
различные
виды
взломов
систем
цифровой
подписи
,
различные
виды
успе
-
хов
,
которых
противник
может
достигнуть
,
различные
виды
стойкости
схем
цифровой
подписи
.
Удалось
также
доказать
эквивалентность
существования
двух
гипотетических
объектов
:
односторонней
функции
и
стойкой
схемы
цифровой
подписи
.
Криптографическая
система
RSA
Как
бы
ни
были
сложны
и
надежны
классические
криптографические
системы
,
их
слабым
местом
при
практической
реализации
является
проблема
распределения
ключей
.
Для
того
чтобы
был
возможен
обмен
конфиденциальной
информацией
между
двумя
абонентами
,
ключ
должен
быть
сгенерирован
одним
из
них
,
а
затем
каким
-
либо
образом
передан
другому
в
конфиденциальном
порядке
.
В
общем
случае
для
передачи
ключа
по
каналам
связи
требуется
использование
еще
одной
криптосистемы
,
для
которой
вновь
возникает
проблема
распределения
ключей
и
т
.
д
.
Для
решения
этой
и
ряда
других
проблем
были
предложены
криптосистемы
с
открытым
ключом
,
называемые
также
асимметричными
криптосистемами
.
Перед
отправкой
сообщения
адресату
исходный
текст
шифруется
открытым
(
обще
-
доступным
)
ключом
адресата
.
Алгоритм
шифрования
построен
таким
образом
,
что
рас
-
шифровывание
сообщения
возможно
только
с
использованием
личного
(
секретного
)
ключа
адресата
.
Впервые
модель
системы
секретной
связи
с
открытым
ключом
была
предложена
Диффи
и
Хеллманом
в
1976
году
.
Суть
этой
модели
состоит
в
том
,
что
ключ
известен
полностью
только
получателю
сообщения
и
представляет
собой
тройку
чисел
k = (
е
, d, n)
,
где
подключ
e
служит
клю
-
чом
шифрования
,
а
ключ
d
—
ключом
расшифровывания
.
При
этом
только
d
является
секретным
(
личным
)
ключом
.
Стойкость
системы
обеспечивается
за
счет
особых
свойств
шифрпреобразования
,
которое
представляет
собой
так
называемую
односто
-
роннюю
функцию
с
лазейкой
.
Вычисление
значения
такой
функции
(
от
открытого
текста
и
параметра
e
)
должно
быть
несложным
,
в
то
же
время
ее
обращение
должно
быть
вы
-
числительно
нереализуемым
без
знания
секретной
информации
, “
лазейки
”,
связанной
с
секретным
ключом
d
.
В
криптосистеме
с
открытым
ключом
сообщение
,
предназначенное
абоненту
,
за
-
шифровывается
отправителем
с
помощью
ключа
e
и
расшифровывается
получателем
с
помощью
ключа
d
.
Если
шифрпреобразование
действительно
является
односторонней
функцией
,
то
сам
отправитель
не
в
состоянии
расшифровать
сформированную
им
крип
-
тограмму
.