Первая страница / Теория / Кодирование / Криптография /

Симметричные системы и блочные шифры

О классификации шифров

Существует три самостоятельных классификации шифрсистем. В первую очередь, как мы уже упоминали, системы бывают симметричные и асимметричные. Вне зависимости от этого различают блочные и поточные шифры. Шифры, в которых преобразование производится последовательно (посимвольно) называют поточными, а те, в которых прямое и обратное преобразование выполняются над блоками фиксированной длины, называются блочными. И, наконец, третий вид классификации основан на виде криптографического преобразования, используемого шифром. В эту классификацию входят шифры замены, шифры перестановки и составные (комбинация первых двух видов). Про эту классификацию мы тоже уже рассказывали.

Блочные шифры

Криптографическое преобразование составляет основу любого блочного шифра. Прямое криптографическое преобразование (шифрование) переводит блок открытого текста в блок шифротекста той же длины. Обратное криптографическое преобразование (дешифрование) переводит блок шифротекста в исходный блок открытого текста. Необходимое условие выполнения как прямого, так и обратного криптографического преобразования — наличие секретного ключа. Для многих блочных шифров разрядность блока составляет 64 бита. Прямое криптографическое преобразование обладает следующим свойством: различные блоки открытого текста отображаются в различные блоки шифротекста. При обратном преобразовании соответствие сохраняется. Прямое преобразование можно рассматривать как перестановку на множестве сообщений с фиксированным размером блока. Результат перестановки носит секретный характер, что обеспечивается секретным компонентом — ключом.

Принцип итерирования

Принцип итерирования является основным при разработке криптографических преобразований и заключается в многократной, состоящей из нескольких циклов обработке одного блока открытого текста. На каждом цикле данные подвергаются специальному преобразованию при участии вспомогательного ключа, полученного из заданного секретного ключа. Выбор числа циклов определяется требованиями криптостойкости и эффективности реализации шифра. Как правило, чем больше циклов, тем выше криптостойкость и ниже эффективность реализации (больше задержка при шифровании/дешифровании), и наоборот. Так, например, в случае DES (федеральный криптостандарт США) для того, чтобы все биты шифротекста зависели от всех битов ключа и всех битов открытого текста, необходимо 5 циклов криптографического преобразования. DES с 16 циклами обладает высокой криптостойкостью по отношению к ряду криптоаналитических атак.

Конструкция Фейстеля

Схема конструкции Фейстеля

Конструкция Фейстеля (Н. Feistel), или сеть Фейстеля, представляет собой разновидность итерированного блочного шифра. При шифровании блок открытого текста разбивается на две равные части правую и левую. Очевидно, что длина блока при этом должна быть четной. На каждом цикле одна из частей подвергается преобразованию при помощи функции f и вспомогательного ключа ki, полученного из исходного секретного ключа. Результат операции суммируется по модулю 2 (операция XOR) с другой частью. Затем левая и правая части меняются местами. Схема конструкции Фейстеля представлена на рисунке. Преобразования на каждом цикле идентичны, но на последнем не выполняется перестановка. Процедура дешифрования аналогична процедуре шифрования, однако ki выбираются в обратном порядке. Конструкция Фейстеля хороша тем, что прямое и обратное криптографические преобразования для такого блочного шифра имеют идентичную структуру.

Конструкция Фейстеля применяется в криптоалгоритмах DES, ГОСТ 28147-89, Lucifer, FEAL, Khufu, Khaire, JOKI, COST, CAST, Blowfish, и др. Блочный шифр, использующий такую конструкцию, является обратимым и гарантирует возможность восстановления входных данных функции на каждом цикле. Сама функция не обязательно должна быть обратимой. При задании произвольной функции не потребуется реализовывать две различные процедуры — одну для шифрования, а другую для дешифрования. Структура сети Фейстеля автоматически позаботится об этом.

Существует еще одно объяснение идеи конструкции Фейстеля. В своих лекциях известный криптограф Дж. Мэсси (J. L. Massey) вводит понятие инволютивного отображения. Так, некоторая функция является инволюцией, если f(f(x)) = x для всех х. Для такой функции область определения (множество аргументов х) и область значений (множество значений f(x)) совпадают. Например, функция f(x) = −x является инволюцией, так как f(f(x)) = f( −x) = −(−x) = х. Другой пример инволюции: f(x) = хс, где с — некоторая константа. Действительно, f(f(x)) = f(xс) = хсс = х.

Инволюция является полезным свойством при конструировании блочных шифров. Рассмотрим композиционный блочный шифр, включающий n последовательных криптографических преобразований ЕiK(*), 1 ≤ i ≤ n на ключе К.

Тогда шифротекст С получается в результате преобразования

C = ЕKn(ЕKn−1(…ЕK1(P)…)),

где Р — открытый текст. Если функция ЕK является инволюцией, открытый текст может быть восстановлен в результате преобразования

P = ЕK1(ЕK2(…ЕKn(C)…)).

Действительно, согласно описанному выше свойству имеем:

P = ЕK1(ЕK2(…ЕKn(ЕKn(ЕKn−1(…ЕK1(P)…)))…)),

так как ЕKn(ЕKn(*)) = * и ЕKn−1(ЕKn−1(*)) = * и так далее вплоть до получения тождества Р = P.

Режимы шифрования блочных шифров

При использовании блочных шифров применяются различные режимы шифрования. Очевидно, что применение того или иного режима шифрования не должно отрицательно сказываться на эффективности и тем более криптостойкости блочного шифра. Режимы шифрования позволяют реализовать дополнительные, отсутствующие в исходной конструкции блочного шифра функции.

Шифрование в режимах ECB и CBC

Шифрование в режиме ECB

Стандарт режимов шифрования для блочных шифров (применительно к криптоалгоритму DES) опубликован в материалах Национального института стандартов США. В более общем виде, применительно к произвольному блочному шифру с переменной длиной блока, стандарт опубликован в материалах и включает шифрование в следующих режимах: Электронной кодовой книги (Electronic Code Book, ECB), Сцепления блоков шифра (Cipher Block Chaining, CBC), Обратной связи по шифротексту (Cipher Feedback, CFB) и Обратной связи по выходу (Output Feedback, OFB). В режиме ECB шифрование/дешифрование j-гo блока открытого текста/шифротекста выполняется независимо: mi = Dk(ci), cj = EK(mi), где через Еk и Dk обозначены процедуры шифрования/дешифрования на секретном ключе k.

Криптостойкость режима ECB не ниже, чем криптостойкость используемого блочного шифра. Недостаток заключается в том. что фиксированные блоки открытого текста (например, последовательность нулей длины l = nb бит, где b длина блока) будут соответствовать фиксированным блокам шифротекста. Следовательно, открытый текст может быть легко изменен путем удаления, реплицирования и перестановки блоков шифротекста. Скорость обработки блоков в режиме ECB фиксирована и определяется эффективностью реализации блочного шифра. Режим ECB допускает эффективное распараллеливание вычислений. Однако конвейерная обработка блоков в данном режиме невозможна.

Шифрование в режиме CBC

В режиме CBC каждый i-й блок открытого текста суммируется по модулю 2 {операция XOR) с (i−1)-м блоком шифротекста и затем шифруется. Начальное значение (в наших обозначениях c0) задается вектором инициализации.

Криптостойкость режима CBC определяется криптостойкостью используемого блочного шифра. Применение режима CBC позволяет устранить недостаток режима ECB: каждый блок открытого текста маскируется блоком шифротекста, полученным на предыдущем этапе. Таким образом, возможность изменения открытого текста при использовании режима CBC весьма ограничена — любые манипуляции с блоками шифротекста, за исключением удаления первого и последнего блоков, будут обнаружены. Скорость обработки в данном режиме не ниже производительности блочного шифра — задержка при выполнении операции XOR пренебрежимо мала. Процедура шифрования в режиме CBC с трудом поддается распараллеливанию, процедуру дешифрования распараллелить значительно проще.

Шифрование в режимах CFB и OFB

В режиме СFВ i-й блок шифротекста формируется путем шифрования (i−1)-го блока шифротекста и его суммированием (операция XOR) с i-м блоком открытого текста.

Шифрование в режиме CFB

Режим СFВ можно задать таким образом, что обратная связь будет захватывать не целый n-битный блок, а только k бит предыдущего блока, kn. Начальное значение c0 так же, как в режиме CBC, задается при помощи вектора инициализации.

Криптостойкость СFВ определяется криптостойкостью используемого шифра. Фиксированные блоки открытого текста маскируются блоками шифротекста. Возможности изменения открытого текста те же, что и в режиме CBC. Если в режиме CFB с полноблочной обратной связью имеется два идентичных блока шифротекста, результат, например, DES-шифрования на следующем шаге будет тем же. Скорость шифрования CFB-режима с полноблочной обратной связью та же, что и у блочного шифра, причем возможности распараллеливания процедуры шифрования ограничены.

Режим OFB аналогичен CFВ, за исключением того, что суммируемые с открытым текстом биты генерируются независимо от открытого текста и шифротекста. Вектор инициализации s0 задает начальное значение последовательности блоков si. И каждый блок si получается путем шифрования предыдущего блока si−1. Открытый текст шифруется суммированием (операция XOR) i-го блока открытого текста с si из независимой последовательности блоков.

Шифрование в режиме OFB

Обратная связь по выходу на k разрядов не рекомендуется из соображений криптостойкости. Режим OFB имеет следующее преимущество по сравнению с режимом CFB: ошибки, возникающие в результате передачи по каналу с шумом, при дешифровании не «размазываются» по всему шифротексту, а локализуются в пределах одного блока. Однако открытый текст может быть изменен путем определенных манипуляций с блоками шифротекста. Скорость шифрования в режиме OFB та же, что и у блочного шифра. Несмотря на то, что OFB-шифрование не поддается распараллеливанию, эффективность процедуры может быть повышена за счет предварительной генерации независимой последовательности блоков.

Шифрование в режимах усовершенствованного OFB и PCBC

Известные недостатки привели к появлению усовершенствованного варианта шифрования в режиме OFB. Основные изменения касаются метода генерации независимой последовательности блоков: для получения очередного блока предлагается шифровать не si, a si + IV(mod 264), где IV — некоторый вектор инициализации.

Режим шифрования PCBC (Propagating Cipher Block Chaining) применяется в протоколе Кеrbеrоs и позволяет обнаруживать ошибки. Данный режим шифрования не является федеральным или международным стандартом. Режим PCBC — вариант режима CBC, обладающий специфическим свойством — в результате дешифрования единичная ошибка распространяется на весь шифротекст (решается обратная задача с точки зрения режима OFB). Данное свойство позволяет с высокой надежностью обнаруживать ошибки, возникающие при передаче сообщений по каналам с шумом. Шифрование в режиме PCBC выполняется по правилу:

ci = Ek(mimi−1ci−1),

дешифрование:

mi = Dk(ci)⊕ci−1mi−1,

где m0m0 — вектор инициализации.

< Назад (Содержание раздела) Дальше >

Воробьева Е., Лукьянова А.