Блочные шифры. Сети Фейштеля (лекция 3)

Август 10, 2022

Главная
Информатика
Блочные шифры. Сети Фейштеля (лекция 3)

Содержание

2. Блочный шифр разновидность симметричного шифра, оперирующего группами бит фиксированной длины — блоками, размер которых меняется в
3. Схему работы блочного шифра можно описать функциями Z=EnCrypt(X,Key) - шифрование X=DeCrypt(Z,Key) – дешифрование Ключ Key -
4. Принципы построения блочных шифров Перемешивание - маскирует взаимосвязи между открытым текстом, шифртекстом и ключом (подстановка) Рассеивание
5. Примеры блочных алгоритмов
6. По теории вероятности искомый ключ будет найден с вероятностью ½ после перебора половины всех ключей, на
7. Требования к блочным шифрам Функция EnCrypt должна быть обратимой. Не должно существовать иных методов прочтения сообщения
8. Все действия, производимые над данными блочным криптоалгоритмом, основаны на том факте, что преобразуемый блок может быть
9. Над этими числами блочным криптоалгоритмом и производятся по определенной схеме следующие действия :
10. В качестве параметра V для любого из этих преобразований может использоваться: фиксированное число (например, X'=X+125) число,
11. Последовательность выполняемых над блоком операций, комбинации вариантов V и сами функции F и составляют «ноу-хау» каждого
12. Поскольку операция зашифровки или расшифровки отдельного блока в процессе кодирования выполняется многократно, а значение ключа и,
13. Сеть Фейштеля
14. Структура сети Независимые потоки информации, порожденные из исходного блока, называются ветвями сети. В классической схеме их
15. увеличение количества раундов значительно увеличивает криптоскойстость любого блочного шифра к криптоанализу. Возможно, эта особенность и повлияла
17. Для получения криптопреобразования, обладающего хорошими криптографическими свойствами, функция усложнения f , используемая в раунде, реализуется в
18. Свойства схемы: Обратима. Даже если в качестве образующей функции F будет использовано необратимое преобразование, то и
19. Если мы рассмотрим граф состояний криптоалгоритма, на котором точками отмечены блоки входной и выходной информации, то
20. Модификацию сети Фейштеля для большего числа ветвей применяют гораздо чаще. Это в первую очередь связано с
21. Сеть Фейштеля надежно зарекомендовала себя как криптостойкая схема произведения преобразований, и ее можно найти практически в
22. Архитектура блочных шифров Сбалансированная сеть Фейштеля – размеры ветвей равны (DES) Несбалансированная сеть Фейштеля – размеры
23. 3. Подстановочно-перестановочная сеть обрабатывают за один раунд целиком шифруемый блок. Обработка данных сводится, в основном, к
24. 4. Архитектура "квадрат"(Square). Шифруемый блок данных - в виде двумерного байтового массива. Криптографические преобразования могут выполняться
25. Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байт размером 4х4, 4х6 или 4х8
26. побайтовый циклический сдвиг в строках матрицы: первая строка остается неизменной, вторая строка циклически сдвигается влево на
27. матричное умножение – полученная на предыдущем шаге матрица умножается слева на матрицу–циркулянт размера 4х4: - операцияоперация
28. добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в
29. В каждом раунде над шифруемыми данными поочередно выполняются перечисленные преобразования. Расшифрование выполняется с помощью следующих обратных
30. Параметры: - размер блока 128, 192, 256 бит,; - размер ключа 128, 192, 256 бит -
31. 5. Алгоритмы с нестандартной структурой В качестве примера алгоритма с нестандартной структурой можно привести уникальный по
32. Режимы шифрования электронная кодовая книга - ECB (Electronic Code Book); сцепление блоков шифротекста - CBC (Cipher
33. ЭЛЕКТРОННАЯ КОДОВАЯ КНИГА Каждый блок шифруют независимо от других с использованием одного ключа шифрования. режим применяется
34. СЦЕПЛЕНИЕ БЛОКОВ ШИФРОТЕКСТА Исходный текст разбивается на блоки, а затем обрабатывается по следующей схеме: Первый блок
35. ОБРАТНАЯ СВЯЗЬ ПО ШИФРОТЕКСТУ Шифрование в режиме CFB Вначале IV заполняется неким значением, которое называется синхропосылкой,
36. ОБРАТНАЯ СВЯЗЬ ПО ВЫХОДУ O0 = IV Oi = Ek(Oi - 1) Принцип работы схож с
37. Алгоритм DES
44. Алгоритм ANSI X9.17 Этот алгоритм является национальным стандартом США для генерации двоичной псевдослучайной последовательности. Используется в
46. Скачать презентацию

Слайд 2

Блочный шифр
разновидность симметричного шифра, оперирующего группами бит фиксированной длины — блоками,

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

Слайд 3

Схему работы блочного шифра можно описать функциями
Z=EnCrypt(X,Key) - шифрование
X=DeCrypt(Z,Key)

– дешифрование
Ключ Key - параметр блочного криптоалгоритма, представляет собой некоторый блок двоичной информации фиксированного размера.
Исходный (X) и зашифрованный (Z) блоки данных также имеют фиксированную разрядность, равную между собой, но необязательно равную длине ключа.

Слайд 4

Принципы построения блочных шифров
Перемешивание - маскирует взаимосвязи между открытым текстом, шифртекстом

и ключом (подстановка)
Рассеивание - распространяет влияние отдельных битов открытого текста на возможно больший объем шифртекста (перестановка)
Итерирование - заключается в многократной, состоящей из нескольких циклов обработке одного блока открытого текста. На каждом цикле данные подвергаются специальному преобразованию при участии вспомогательного ключа, полученного из заданного секретного ключа. Выбор числа циклов определяется требованиями криптостойкости и эффективности реализации шифра. Как правило, чем больше циклов, тем выше криптостойкость и ниже эффективность реализации.
Практически все современные блочные шифры являются композиционными - т.е состоят из композиции простых преобразований или F=F1oF2oF3oF4o..oFn, где F - преобразование шифра, Fi - простое преобразование, называемое также i-ым циклом шифрования.

Слайд 5

Примеры блочных алгоритмов

Слайд 6

По теории вероятности искомый ключ будет найден с вероятностью ½ после

перебора половины всех ключей, на взлом стойкого криптоалгоритма с ключом длины N потребуется в среднем 2N-1 проверок.
стойкость блочного шифра зависит от длины ключа и возрастает экспоненциально с ее ростом. Если на проверку 1 ключа требуется 1 такт, то на взлом 128 битного ключа не менее 1021.

Слайд 7

Требования к блочным шифрам
Функция EnCrypt должна быть обратимой.
Не должно существовать

иных методов прочтения сообщения X по известному блоку Z, кроме как полным перебором ключей Key.
Не должно существовать иных методов определения, каким ключом Key было произведено преобразование известного сообщения X в сообщение Z, кроме как полным перебором ключей

Слайд 8

Все действия, производимые над данными блочным криптоалгоритмом, основаны на том факте,

что преобразуемый блок может быть представлен в виде целого неотрицательного числа из диапазона, соответствующего его разрядности.
32-битный блок данных можно интерпретировать как число из диапазона 0..4'294'967'295.
блок, разрядность которого является «степенью двойки», можно трактовать как несколько независимых неотрицательных чисел из меньшего диапазона (32-битный блок можно представить в виде 2 независимых чисел из диапазона 0..65535 или в виде 4 независимых чисел из диапазона 0..255).

Слайд 9

Над этими числами блочным криптоалгоритмом и производятся по определенной схеме следующие

действия :

Слайд 10

В качестве параметра V для любого из этих преобразований может использоваться:
фиксированное

число (например, X'=X+125)
число, получаемое из ключа (например, X'=X+F(Key))
число, получаемое из независимой части блока (например, X2'=X2+F(X1))

Слайд 11

Последовательность выполняемых над блоком операций, комбинации вариантов V и сами функции

F и составляют «ноу-хау» каждого конкретного блочного криптоалгоритма.
Характерным признаком блочных алгоритмов является многократное и косвенное использование материала ключа. Для решения этой задачи чаще всего используется не само значение ключа или его части, а некоторая, иногда необратимая функция от материала ключа. В подобных преобразованиях один и тот же блок или элемент ключа используется многократно. Это позволяет при выполнении условия обратимости функции относительно величины X сделать функцию необратимой относительно ключа Key.

Слайд 12

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

многократно, а значение ключа и, следовательно, функций Vi(Key) остается неизменным, то иногда становится целесообразно заранее однократно вычислить данные значения и хранить их в оперативной памяти совместно с ключом. Данная операция не изменяет ни длину ключа, ни криптостойкость алгоритма в целом. Здесь происходит лишь оптимизация скорости вычислений путем кеширования промежуточных результатов. Описанные действия встречаются практически во многих блочных криптоалгоритмах и носят название расширение ключа (англ. key scheduling)

Слайд 13

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

Слайд 14

Структура сети
Независимые потоки информации, порожденные из исходного блока, называются ветвями сети.

В классической схеме их две.
Величины Vi именуются параметрами сети, обычно это функции от материала ключа.
Функция F называется образующей.
Действие, состоящее из однократного вычисления образующей функции и последующего наложения ее результата на другую ветвь с обменом их местами, называется циклом или раундом (англ. round) сети Фейштеля. Оптимальное число раундов K – от 8 до 32.

Слайд 15

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

Возможно, эта особенность и повлияла на столь активное распространение сети Фейштеля – ведь при обнаружении, какого-либо слабого места в алгоритме, почти всегда достаточно увеличить количество раундов на 4-8, не переписывая сам алгоритм. Часто количество раундов не фиксируется разработчиками алгоритма, а лишь указываются разумные пределы (обязательно нижний, и не всегда – верхний) этого параметра.

Слайд 16

Слайд 17

Для получения криптопреобразования, обладающего хорошими криптографическими свойствами, функция усложнения f ,

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

Слайд 18

Свойства схемы:
Обратима. Даже если в качестве образующей функции F будет использовано

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

Слайд 19

Если мы рассмотрим граф состояний криптоалгоритма, на котором точками отмечены блоки

входной и выходной информации, то при каком-то фиксированном ключе для классической сети Фейштеля мы будем иметь картину, изображенную на рис.а, а во втором случае каждая пара точек получит уникальную связь, как изображено на рис. б. Модификация сети Фейштеля, обладающая подобными свойствами, характеризуется повторным использованием данных ключа в обратном порядке во второй половине цикла.

Слайд 20

Модификацию сети Фейштеля для большего числа ветвей применяют гораздо чаще. Это

в первую очередь связано с тем, что при больших размерах кодируемых блоков (128 и более бит) становится неудобно работать с математическими функциями по модулю 64 и выше.

Слайд 21

Сеть Фейштеля надежно зарекомендовала себя как криптостойкая схема произведения преобразований, и

ее можно найти практически в любом современном блочном шифре. Незначительные модификации касаются обычно дополнительных начальных и оконечных преобразований (англоязычный термин – whitening) над шифруемым блоком. Подобные преобразования, выполняемые обычно также либо "исключающим ИЛИ" или сложением имеют целью повысить начальную рандомизацию входного текста. Таким образом, криптостойкость блочного шифра, использующего сеть Фейштеля, определяется на 95% функцией F и правилом вычисления Vi из ключа. Эти функции и являются объектом все новых и новых исследований специалистов в области криптографии

Слайд 22

Архитектура блочных шифров
Сбалансированная сеть Фейштеля – размеры ветвей равны (DES)
Несбалансированная сеть

Фейштеля – размеры ветвей различны, функция шифрования F может зависеть не от всех битов исходного блока данных или иметь разные зависимости в разных раундах (MARS)

Слайд 23

3. Подстановочно-перестановочная сеть обрабатывают за один раунд целиком шифруемый блок. Обработка

данных сводится, в основном, к заменам в соответствии с таблицей замен, которая может зависеть от значения ключа и перестановкам, зависящим от ключа.. SP-сети являются гораздо менее распространенными (Safer+)

Слайд 24

4. Архитектура "квадрат"(Square).
Шифруемый блок данных - в виде двумерного байтового

массива. Криптографические преобразования могут выполняться над отдельными байтами массива, а также над его строками или столбцами. Недостатком алгоритмов со структурой "квадрат" является их недостаточная изученность, что не помешало алгоритму Rijndael стать новым стандартом США.
.

Слайд 25

Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байт

размером 4х4, 4х6 или 4х8 в зависимости от установленной длины блока.
Функция нелинейного преобразования в алгоритме Rijndael состоит из трех следующих элементарных преобразований, выполняемых последовательно:
байтовая подстановка – каждый байт преобразуемого блока заменяется новым значением, извлекаемым из общего для всех байтов матрицы вектора замены;

Слайд 26

побайтовый циклический сдвиг в строках матрицы: первая строка остается неизменной,

вторая строка циклически сдвигается влево на один байт, третья и четвертая строка циклически сдвигаются влево соответственно на 2 и 3 байта для n = 4 или 6, и на 3 и 4 байта для n = 8;

Слайд 27

матричное умножение – полученная на предыдущем шаге матрица умножается слева на

матрицу–циркулянт размера 4х4: - операцияоперация над независимыми столбцами массива когда каждый столбец по определенному правилу умножается на фиксированную матрицу c(x)

Слайд 28

добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим

битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования

Слайд 29

В каждом раунде над шифруемыми данными поочередно выполняются перечисленные преобразования.
Расшифрование выполняется

с помощью следующих обратных операций. Выполняется обращение таблицы и табличная замена на инверсной таблице (относительно применяемой при зашифровании). Обратная операция к SR - это циклический сдвиг строк вправо, а не влево. Обратная операция для MC - умножение по тем же правилам на другую матрицу d(x), удовлетворяющую условию: c(x) * d(x) = 1. Добавление ключа AK является обратным самому себе, поскольку в нем используется только операция XOR. Эти обратные операции применяются при расшифровании в последовательности, обратной той, что использовалась при зашифровании.

Слайд 30

Параметры:
- размер блока 128, 192, 256 бит,;
- размер ключа 128, 192,

256 бит
- число раундов 10, 12, 14. Зависит от размера блока (Nb) и ключа (Nk), заданных в битах, по следующей формуле: Nr=max(Nb,Nk)/32+6;
Rijndael стал новым стандартом шифрования данных благодаря целому ряду преимуществ перед другими алгоритмами. Прежде всего он обеспечивает высокую скорость шифрования на всех платформах: как при программной, так и при аппаратной реализации. Его отличают несравнимо лучшие возможности распараллеливания вычислений по сравнению с другими алгоритмами, представленными на конкурс. Кроме того, требования к ресурсам для его работы минимальны, что важно при его использовании в устройствах, обладающих ограниченными вычислительными возможностями

Слайд 31

5. Алгоритмы с нестандартной структурой В качестве примера алгоритма с нестандартной

структурой можно привести уникальный по своей структуре алгоритм FROG, в каждом раунде которого по достаточно сложным правилам выполняется модификация двух байт шифруемых данных

Слайд 32

Режимы шифрования
электронная кодовая книга - ECB (Electronic Code Book);
сцепление блоков

шифротекста - CBC (Cipher Block Chaining);
обратная связь по шифротектсту - CFB (Cipher Feed Back);
обратная связь по выходу - OFB (Output Feed Back);

Слайд 33

ЭЛЕКТРОННАЯ КОДОВАЯ КНИГА
Каждый блок шифруют независимо от других с использованием одного

ключа шифрования.

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

Слайд 34

СЦЕПЛЕНИЕ БЛОКОВ ШИФРОТЕКСТА
Исходный текст разбивается на блоки, а затем обрабатывается по

следующей схеме:
Первый блок складывается побитно по модулю 2 (XOR) с неким значением IV - начальным вектором (Init Vector), который выбирается независимо перед началом шифрования. Полученное значение шифруется. Полученный в результате блок шифротекста отправляется получателю и одновременно служит начальным вектором IV для следующего блока открытого текста. Расшифрование осуществляется в обратном порядке.
C0 = IV

Типичные приложения - общая блокоориентированная передача, аутентификация.

Слайд 35

ОБРАТНАЯ СВЯЗЬ ПО ШИФРОТЕКСТУ
Шифрование в режиме CFB
Вначале IV заполняется неким значением,

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

Расшифрование в режиме CFB

Слайд 36

ОБРАТНАЯ СВЯЗЬ ПО ВЫХОДУ
O0 = IV Oi = Ek(Oi - 1)
Принцип работы схож с

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

Слайд 37

Алгоритм DES

Слайд 38

Слайд 39

Слайд 40

Слайд 41

Слайд 42

Слайд 43

Слайд 44

Алгоритм ANSI X9.17
Этот алгоритм является национальным стандартом США для генерации двоичной

псевдослучайной последовательности. Используется в приложениях, обеспечивающих безопасность финансовых платежей, и PGP. В этом генераторе в качестве односторонней функции используется алгоритм шифрования TripleDES (3DES, «тройной DES»). Этот алгоритм использует два 64-битных ключа и следующим образом:
Входные данные: некоторое случайное (и секретное) 64-битное начальное значение s0, 128-битный составной ключ K и m – количество генерируемых 64-битных двоичных слов.
Выходные данные: последовательность m 64-битных двоичных слов x1, x2, …, xm

Блочные шифры. Сети Фейштеля (лекция 3)

Содержание

Блочный шифр разновидность симметричного шифра, оперирующего группами бит фиксированной длины — блоками,

Схему работы блочного шифра можно описать функциями Z=EnCrypt(X,Key) - шифрование X=DeCrypt(Z,Key)

Принципы построения блочных шифровПеремешивание - маскирует взаимосвязи между открытым текстом, шифртекстом