ГЛАВА 4. КАК УСТРОЕНЫ СОВРЕМЕННЫЕ ШИФРЫ

.

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

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

Про эту классификацию мы тоже уже рассказывали.

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

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

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

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

Сеть Фейстеля

DES с 16 циклами обладает высокой криптостойкостью по отношению к ряду криптоаналитических атак.

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

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

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

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

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

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

 = (−1(…1()…)),

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

P = Е1(2(…()…)).

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

 = 1(2(…((−1(…1()…)))…)),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 = (⊕−1−1),

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

 = D()⊕−1−1,

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

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

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

Сеть Фейстиля — алгоритм

Основное определение

Сеть Фейстеля — это многократно повторяющиеся преобразования состояния блока данных (для упрощения будем читать что это — последовательность бит) — для очередной ячейки сети входными значениями (для преобразования) служат выходные значения предыдущей ячейки (то есть данные преобразованные ранее). Является симметричным алгоритмом

Блоки

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

Иллюстрация схемы работы

посматривайте на эту схему, когда будете читать про алгоритм =))

Алгоритм — принцип работы (шифрование)

  1. Каждый блок данных который мы шифруем, мы разбиваем на два подблока — правый и левый
  2. Правый подблок мы преобразуем с помощью некоторой функции $\Large f$ используя при этом ключ $\Large k_{n}$ (n — номер ячейки(очередного преобразования) для каждого следующего преобразования — то есть каждой следующей ячейки сети ключ $\Large k$ будет меняться 0 в этом-то и есть вся фишка ))) а затем складываем выходное значение $\Large f$ по модулю 2 с правым подблоком
  3. ————————————————————
    Так, здесь я даю вам время перевести дух (немного отдохнуть) — и заодно уточнить — преобразование с помощью функции $\Large f$ подразумевает что входными значениями для этой функции являются -во первых — левый подблок, а во-вторых — ключ $\Large k$ — а вот результат функции, при этих двух аргументах мы и складываем по модулю 2 с правым подблоком ——-
    Следующий этап — формирование значений для входа следующей ячейки — как вы догадались нам снова нужны правый и левый подблоки
    ——————————————————————
  4. Итак, теперь левым подблоком (для очередного применения функции $\Large f$ но теперь уже с ключом $\Large k_{n+1}$ ) мы будем считать выход функции $\Large f$ из предыдущей ячейки (см. пункт 2), а правым — опять же левый подблок предыдущего этапа (ячейки) функцией $\Large f$
  5. Подобный переход от ячейки к ячейки повторяется некоторое число раз (в зависимости от конкретной реализации алгоритма)

Расшифровка

Расшифровка происходит в обратном порядке, а именно (первым будет использовать тот ключ, который на этапе шифрования использовался последним) -применяется всё так же функция $\Large f$

.

DES (Data Encryption Standart) — Симметричный алгоритм шифрования, в котором один ключ используется, как для шифрования, так и для расшифрования данных. DES разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FTPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:

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

Преобразования Сетью Фейстеля

Это преобразование над векторами (блоками) представляющими собой левую и правую половины регистра сдвига. В алгоритме DES используются прямое преобразование сетью Фейстеля в шифровании (см. Рис.1) и обратное преобразование сетью Фейстеля в расшифрование (см. Рис.2).

Схема шифрования алгоритма DES

Исходный текст — блок 64 бит.
Шифрованный текст — блок 64 бит.

Процесс шифрования состоит в начальной перестановке, 16 циклах шифрования и конечной перестановке.
Рассмотрим подробную схему алгоритма DES:
LiRi=1,2\ldots.левая и правая половины 64-битового блока LiRi
ki — 48 битовые ключи
f — функция шифрования
IP — начальная перестановка
IP-1 — конечная перестановка.

По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58, 50, 42 входного блока Т, а его 3 последние бита являются битами 23, 15, 7 входного блока. Дальше 64-битовой блок IP(T) участвует в 16-циклах преобразования Фейстеля.

— 16 циклов преобразования Фейстеля:

Разбить IP(T) на две части L0,R0, где L0,R0 — соответствено 32 старших битов и 32 младших битов блока T0 IP(T)= L0R0

Пусть Ti -1 = Li -1Ri -1 результат (i-1) итерации, тогда результат i-ой интерации Ti = LiRi определяется:

Li = Ri — 1

Левая половина Li равна правой половине предыдущего вектора Li — 1Ri — 1.

А правая половина Ri — это битовое сложение Li — 1 и f(Ri — 1,ki) по модулю 2.

В 16-циклх преобразования Фейстеля функция f играет роль шифрования. Рассмотрим подробно функцию f.

Аргументы функции f являются 32 битовой вектор Ri — 1, 48 битовой ключ ki, которые являются результатом преобразования 56 битового исходного ключа шифра k.

Для вычисления функции f используются фукция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков , и перестановка P.

Функция Е расширяется 32 битовой вектор Ri — 1 до 48 битовой вектор E(Ri — 1) путем дублирования некоторых битов из Ri — 1 при этом порядок битов вектора E(Ri — 1) указан в таблице 2.

Первые три бита вектора E(Ri — 1) являются битами 32, 1, 2 вектора Ri -1. По таблице 2 видно что биты 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 дублируются. Последние 3 биты вектора E(Ri — 1) — это биты 31, 32, 1 вектора Ri — 1. Полученный после перестановки блок E(Ri -1) складывается по модулю 2 с ключами ki и затем представляются в виде восьми последовательных блоков B1,B2,…B8.
E(Ri — 1) = B1B2…B8
Каждый Bj является 6-битовым блоком. Далее каждый из блоков Bj трансформируется в 4 битовой блок B’j с помощью преобразований Sj. Преобразования Sj определяется таблицей 3.
Предположим что B3 = 101111 и мы хотим найти B’3. Первый и последний разряды B3 являются двоичной записью числа а, 0<=a<=3, средние 4 разряды представляют число b, 0<=b<=15. Строки таблицы S3 нумеруются от 0 до 3, столбцы таблицы S3 нумеруются от 0 до 15.Пара числа(а,b) определяет число,находящее в пересечении строки а и столбцы b. Двоичное представление этого числа дает B’3 .В нашем случае a = 112 = 3,b = 01112 = 7, число определяется парой (3,7) равно 7, следует B’3=0111.
Значение функции f(Ri — 1,ki) (32 бит) получается перестановкой Р, применяемой к 32 битовому блоку B’1B’2…B’8. Перестановка Р задана таблицей 4.

f(Ri — 1,ki) = P(B’1B’2…B’8)
Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f — это бита 16, 7, 20, 21 вектора B’1B’2…B’8

Генерирование ключей ki.
Ключи ki получаются из начального ключа k (56 бит = 7 байтов или 7 символов в АSCII) таким образом. Восемь битов, находящих в позициях 8, 16, 24, 32, 40, 48, 56, 64 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определенна как в таблице 5.

Блочные шифры. Сеть Фейcтеля.

Эта перестановка определяется двумя блоками C0 и D0 по 28 бит каждый. Первые 3 бита C0 есть биты 57, 49, 41 расширенного ключа. А первые три бита D0 есть биты 63, 55, 47 расширенного ключа. Ci,Di i=1,2,3…получаются из Ci — 1,Di — 1 одним или двумя левыми циклическими сдвигами согласно таблице 6.

Ключ ki, i=1,…16 состоит из 48 бит, выбранных из битов вектора CiDi (56 бит) согласно таблице 7. Первый и второй биты ki есть биты 14, 17 вектора CiDi

Конечная перестановка IP — 1 действует на T16 и используется для востановления позиции. Она является обратной к перестановке IP. Конечная перестановка определяется таблицей 8.


Режимы использования DES
DES может используется в четырех режимах.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *