Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
В настоящее время, особенно после изобретения криптографии с открытым ключом, уже не требуется, чтобы алгоритм шифрования отображал пространство сообщений в самого себя (хотя многие криптосистемы, как с секретным, так и с открытым ключом, обладают этим свойством). Несмотря на это, семантическое требование Шеннона, чтобы алгоритм шифрования перемешивал сообщения, остается весьма актуальным. Современное определение семантической стойкости (semantic security) алгоритма шифрования, которое будет дано в разделе 14.3, по существу означает, что распределение зашифрованного текста по пространству сообщений невозможно отличить от равномерного распределения в том же пространстве.
7.1.1 Структурная схема главы
В главе рассматриваются основные понятия, связанные с криптосистемами, несколько известных криптосистем и стандартные операции. Глава начинается с формального определения криптосистемы (раздел 7.2). Затем описываются несколько классических шифров (разделы 7.3, 7.4). В разделе 7.5 продемонстрирована важная роль, которую классические шифры играют при создании современных шифров и криптографических протоколов. После классических шифров в главе описаны два современных блочных шифра: Data Encryption Standard (DES) — в разделе 7.6 и Advanced Encryption Standard (AES) — в разделе 7.7. Кроме того, в этих разделах излагается стратегия их разработки. Раздел 7.7.5 содержит краткое обсуждение положительного влияния стандарта AES на прикладную криптографию. Разделы, посвященные симметричным методам, содержат описание стандартных операций над блочными шифрами, обеспечивающими вероятностное шифрование (раздел 7.8). Введение в современные симметричные методы шифрования завершается постановкой классической задачи об установлении канала для обмена ключами (раздел 7.9).
(7.1.1)
п
Глава 7. Шифрование — симметричные методы
249
7.2 Определение
Формальное определение криптосистемы выглядит следующим образом.
Определение 7.1 (Криптографическая система). Криптографическая система состоит из таких компонентов.
• Пространство исходных сообщений Л4: множество строк над некоторым алфавитом.
• Пространство зашифрованных текстов С: множество возможных зашифрованных сообщений.
• Пространство ключей шифрования /С — множество возможных ключей шифрования и пространство ключей расшифровки KJ — множество возможных ключей расшифровки.
• Эффективный алгоритм генерации ключей Q : N i—> /С х /С'.
• Эффективный алгоритм шифрования ? : Л4 х /С •—>• С.
• Эффективный алгоритм расшифровки Т> : С х /С' ¦—» Л4.
Для целого числа Iе результатом алгоритма G{le) является пара ключей (ke, kd) е/Сх /С', имеющих длину L
Для числа fee € /С и сообщения т € Л4 обозначение
С = ?ке{т)
относится к преобразованию шифрования и читается как "преобразование с является шифрованием сообщения т ключом ke ", а обозначение
т = Т>ы(с)
относится к преобразованию расшифровки и читается как "преобразование т является расшифровкой сообщения с с помощью ключа kd". Необходимо, чтобы для всех сообщений т G Л4 и всех ключей ke ? К, существовал ключ kd € К,', удовлетворяющий условию
ШИ) = т. (7.2.1)
В остальной части книги для описания абстрактной криптосистемы будет использоваться формальное определение, за исключением нескольких мест, где будут применяться общепринятые обозначения. Понятие криптосистемы проиллюстрировано на рис. 7.1.
Определение 7.1 относится к криптосистемам, использующим как секретные (secret), так и открытые (public) ключи (криптосистемы с открытым ключом будут
250
Часть III. Основные методы криптографии
Исходный текст
Шифрование
ке
Зашифрованный текст
Канал для обмена сообщениями Канал для обмена ключами
Расшифровка
т—
kd
Исходный текст
Генерация ключей
Криптосистема с закрытым ключом: ke=kd Канал для обмена ключами: например, Курьер
Криптосистема с открытым ключом: ke =\= kd Канал для обмена ключами: например. Каталог
Рис. 7.1. Упрощенная схема криптографической системы
введены в следующей главе). В криптосистемах с секретным ключом (secret-key cryptosystems) шифрование и расшифровка осуществляются с помощью одного и того же ключа. Отправитель, шифрующий сообщение, должен передать ключ расшифровки адресату, получающему и расшифровывающему зашифрованное сообщение. Благодаря условию kd = ке криптосистемы с секретным ключом получили другое название: симметричные криптосистемы (symmetric cryptosystem). В криптосистемах с открытым ключом (public-key cryptosystem) шифрование и расшифровка используют разные ключи: для каждого ключа ке е 1С существует ключ kd б К!, причем они отличаются друг от друга и взаимосвязаны. Ключ шифрования ке не обязательно держать в секрете, и пользователь, владеющий ключом ке, может расшифровать текст, зашифрованный с помощью этого ключа, используя соответствующий закрытый (private) ключ kd. Благодаря условию ке ф kd криптосистемы с открытым ключом получили другое название: асимметричные криптосистемы (asymmetric cryptosystems).
Требование эффективности, предъявляемое к алгоритмам шифрования, позволяет отнести их к классу полиномиальных алгоритмов. Следовательно, несмотря на то, что абстрактное определение алгоритма ? выглядит как определение детерминированного алгоритма, он может иметь внутренний случайный такт, а значит, зашифрованный текст может быть случайной величиной, зависящей от этого такта. Заметим также, что целочисленный вход алгоритма генерации ключей Q определяет размер результирующих ключей шифрования-расшифровки. Поскольку алгоритм генерации ключей является эффективным, и его временная сложность полиномиально зависит от размера исходных данных, входное целое число следует представлять в унарном виде (причины этого требования указаны в разделе 4.4.6.1).
