Презентация на тему Алгоритмы симметричного шифрования

криптографии.
Рис. 2.1.  Общая схема симметричного шифрования

вход которому подаются исходное незашифрованное сообщение, называемое также plaintext,

и ключ. Выходом алгоритма является зашифрованное сообщение, называемое также ciphertext. Ключ является значением, не зависящим от шифруемого сообщения. Изменение ключа должно приводить к изменению зашифрованного сообщения.
Зашифрованное сообщение передается получателю. Получатель преобразует зашифрованное сообщение в исходное незашифрованное сообщение с помощью алгоритма дешифрования и того же самого ключа, который использовался при шифровании, или ключа, легко получаемого из ключа шифрования.
Незашифрованное сообщение будем обозначать P или M, от слов plaintext и message. Зашифрованное сообщение будем обозначать С, от слова ciphertext.

Криптография. Основные понятия

нескольких факторов.
Во-первых, криптографический алгоритм должен быть достаточно сильным, чтобы

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

конфузии для описания стойкости алгоритма шифрования.
Диффузия - это рассеяние

статистических особенностей незашифрованного текста в широком диапазоне статистических особенностей зашифрованного текста. Это достигается тем, что значение каждого элемента незашифрованного текста влияет на значения многих элементов зашифрованного текста или, что то же самое, любой элемент зашифрованного текста зависит от многих элементов незашифрованного текста.
Конфузия - это уничтожение статистической взаимосвязи между зашифрованным текстом и ключом.
Если Х - это исходное сообщение и k - криптографический ключ, то зашифрованный передаваемый текст можно записать в виде
Y = Ek[X].
Получатель, используя тот же ключ, расшифровывает сообщение
X = Dk[Y]
Противник, не имея доступа к K и Х , должен попытаться узнать Х, K или и то, и другое.

обрабатывается исходный текст. Возможно шифрование блоками или шифрование потоком.
Блок

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

Табличная подстановка, при которой группа битов отображается в другую группу битов. Это так называемые S-box.
Перемещение, с помощью которого биты сообщения переупорядочиваются.
Операция сложения по модулю 2, обозначаемая XOR или

Операция сложения по модулю 232 или по модулю 216.
Циклический сдвиг на некоторое число битов.

называемые раунды. Входом каждого раунда является выход предыдущего раунда

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

Криптография. Основные понятия

во многих приложениях:

Шифрование данных. Алгоритм должен быть эффективен при

шифровании файлов данных или большого потока данных.
Создание случайных чисел. Алгоритм должен быть эффективен при создании определенного количества случайных битов.
Хэширование. Алгоритм должен эффективно преобразовываться в одностороннюю хэш-функцию.

различных платформах, которые, соответственно, предъявляют различные требования.

Алгоритм должен эффективно

реализовываться на специализированной аппаратуре, предназначенной для выполнения шифрования/дешифрования.
Большие процессоры. Хотя для наиболее быстрых приложений всегда используется специальная аппаратура, программные реализации применяются чаще. Алгоритм должен допускать эффективную программную реализацию на 32-битных процессорах.
Процессоры среднего размера. Алгоритм должен работать на микроконтроллерах и других процессорах среднего размера.
Малые процессоры. Должна существовать возможность реализации алгоритма на смарт-картах, пусть даже с учетом жестких ограничений на используемую память.

дополнительным требованиям.

Алгоритм должен быть простым для написания кода, чтобы

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

в n-битный блок зашифрованного текста. Число блоков длины n

равно 2n. Для того чтобы преобразование было обратимым, каждый из таких блоков должен преобразовываться в свой уникальный блок зашифрованного текста. При маленькой длине блока такая подстановка плохо скрывает статистические особенности незашифрованного текста. Если блок имеет длину 64 бита, то он уже хорошо скрывает статистические особенности исходного текста. Но в данном случае преобразование текста не может быть произвольным в силу того, что ключом будет являться само преобразование, что исключает эффективную как программную, так и аппаратную реализации.
Наиболее широкое распространение получили сети Фейштеля, так как, с одной стороны, они удовлетворяют всем требованиям к алгоритмам симметричного шифрования, а с другой стороны, достаточно просты и компактны.

делится на несколько равной длины подблоков, называемых ветвями. В

случае, если блок имеет длину 64 бита, используются две ветви по 32 бита каждая. Каждая ветвь обрабатывается независимо от другой, после чего осуществляется циклический сдвиг всех ветвей влево. Такое преобразование выполняется несколько циклов или раундов. В случае двух ветвей каждый раунд имеет структуру, показанную на рисунке:

из вычисления функции F для одной ветви и побитового

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

сети Фейштеля для 128-битного блока с четырьмя ветвями. Увеличение

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

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

или и то, и другое, называется криптоанализом. Одной из

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

незашифрованных сообщений вместе с их зашифрованным видом. Или криптоаналитик

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

Цена расшифровки сообщения больше цены самого сообщения.
Время, необходимое для расшифровки сообщения, больше срока жизни сообщения.

подход, используемый при дифференциальном и линейном криптоанализе. И в

том, и в другом случае предполагается, что известно достаточно большое количество пар (незашифрованнный текст, зашифрованный текст).
Понятие дифференциального криптоанализа было введено Эли Бихамом (Biham) и Ади Шамиром (Shamir) в 1990 году. Конечная задача дифференциального криптоанализа - используя свойства алгоритма, в основном свойства S-box, определить подключ раунда. Конкретный способ дифференциального криптоанализа зависит от рассматриваемого алгоритма шифрования.

сеть Фейштеля, то можно считать, что блок m состоит

из двух половин - m0 и m1. Дифференциальный криптоанализ рассматривает отличия, которые происходят в каждой половине при шифровании. (Для алгоритма DES "отличия" определяются с помощью операции XOR, для других алгоритмов возможен иной способ). Выбирается пара незашифрованных текстов с фиксированным отличием. Затем анализируются отличия, получившиеся после шифрования одним раундом алгоритма, и определяются вероятности различных ключей. Если для многих пар входных значений, имеющих одно и то же отличие Х, при использовании одного и того же подключа одинаковыми (Y) оказываются и отличия соответствующих выходных значений, то можно говорить, что Х влечет Y с определенной вероятностью. Если эта вероятность близка к единице, то можно считать, что подключ раунда найден с данной вероятностью. Так как раунды алгоритма независимы, вероятности определения подключа каждого раунда следует перемножать. Как мы помним, считается, что результат шифрования данной пары известен. Результаты дифференциального криптоанализа используются как при разработке конкретных S-box, так и при определении оптимального числа раундов.

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

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

Целью линейного криптоанализа является поиск линейного уравнения вида

i, βi
и γi
- фиксированные позиции
в блоках сообщения

и ключе. Чем больше р отклоняется от 0.5, тем более подходящим считается уравнение.

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

значения левой части для большого числа пар соответствующих фрагментов

незашифрованного и зашифрованного блоков. Если результат оказывается равен нулю более чем в половине случаев, то полагают, что K[γ1, …, γс] = 0. Если в большинстве случаев получается 1, полагают, что K[γ1, …, γс] = 1. Таким образом получают систему уравнений, решением которой является ключ.

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

требования, обычно считается, что алгоритм симметричного шифрования должен:

Манипулировать

данными в больших блоках, предпочтительно размером 16 или 32 бита.
Иметь размер блока 64 или 128 бит.
Иметь масштабируемый ключ до 256 бит.
Использовать простые операции, которые эффективны на микропроцессорах, т.е. исключающее или, сложение, табличные подстановки, умножение по модулю. Не должно использоваться сдвигов переменной длины, побитных перестановок или условных переходов.
Должна быть возможность реализации алгоритма на 8-битном процессоре с минимальными требованиями к памяти.

На системах с большим количеством памяти эти подключи могут

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

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

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

Используемые критерии при разработке алгоритмов

Большинство блочных алгоритмов основано на использовании сети Фейштеля, все имеют плоское пространство ключей, с возможным исключением нескольких слабых ключей.

алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм

был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technolody США) в качестве стандарта (FIPS PUB 46).

DES является классической сетью Фейштеля с двумя ветвями. Данные шифруются 64-битными блоками, используя 56-битный ключ. Алгоритм преобразует за несколько раундов 64-битный вход в 64-битный выход. Длина ключа равна 56 битам. Процесс шифрования состоит из четырех этапов. На первом из них выполняется начальная перестановка (IP) 64-битного исходного текста (забеливание), во время которой биты переупорядочиваются в соответствии со стандартной таблицей.

раундов одной и той же функции, которая использует операции

сдвига и подстановки. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами. Наконец, на четвертом этапе выполняется перестановка IP-1 результата, полученного на третьем этапе. Перестановка IP-1 инверсна начальной перестановке.

рисунке показан способ, которым используется 56-битный ключ. Первоначально ключ

подается на вход функции перестановки. Затем для каждого из 16 раундов подключ Ki является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи Ki для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.

определяются стандартной таблицей. Если М - это произвольные 64

бита, то X = IP (M) - переставленные 64 бита. Если применить обратную функцию перестановки Y = IP-1 (X) = IP-1 (IP(M)), то получится первоначальная последовательность битов.

Последовательность преобразований отдельного раунда

Теперь рассмотрим последовательность преобразований, используемую в каждом раунде.

этом на каждой итерации получается промежуточное 64-битное значение. Левая

и правая части каждого промежуточного значения трактуются как отдельные 32-битные значения, обозначенные L и R. Каждую итерацию можно описать следующим образом:

Алгоритм DES. Шифрование

Li = Ri-1

Ri = Li-1

F(Ri-1, Ki)

Где обозначает операцию

XOR.

Таким образом, выход левой половины Li равен входу правой половины Ri-1. Выход правой половины Ri является результатом применения операции XOR к Li-1 и функции F, зависящей от Ri-1 и Ki.

подается на вход функции F, имеет длину 32 бита.

Вначале Ri расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Расширение происходит следующим образом. 32 бита разбиваются на группы по 4 бита и затем расширяются до 6 битов, присоединяя крайние биты из двух соседних групп. Например, если часть входного сообщения

. . . efgh ijkl mnop . . .

то в результате расширения получается сообщение

. . . defghi hijklm lmnopq . . .

После этого для полученного 48-битного значения выполняется операция XOR с 48-битным подключом Ki. Затем полученное 48-битное значение подается на вход функции подстановки, результатом которой является 32-битное значение.

каждый из которых на входе получает 6 бит, а

на выходе создает 4 бита. Эти преобразования определяются специальными таблицами. Первый и последний биты входного значения S-box определяют номер строки в таблице, средние 4 бита определяют номер столбца. Пересечение строки и столбца определяет 4-битный выход. Например, если входом является 011011, то номер строки равен 01 (строка 1) и номер столбца равен 1101 (столбец 13). Значение в строке 1 и столбце 13 равно 5, т.е. выходом является 0101.
Далее полученное 32-битное значение обрабатывается с помощью перестановки Р, целью которой является максимальное переупорядочивание битов, чтобы в следующем раунде шифрования с большой вероятностью каждый бит обрабатывался другим S-box.

состоит из 48 битов. Ключи Ki получаются по следующему

алгоритму. Для 56-битного ключа, используемого на входе алгоритма, вначале выполняется перестановка в соответствии с таблицей Permuted Choice 1 (РС-1). Полученный 56-битный ключ разделяется на две 28-битные части, обозначаемые как C0 и D0 соответственно. На каждом раунде Ci и Di независимо циклически сдвигаются влево на 1 или 2 бита, в зависимости от номера раунда. Полученные значения являются входом следующего раунда. Они также представляют собой вход в Permuted Choice 2 (РС-2), который создает 48-битное выходное значение, являющееся входом функции F(Ri-1, Ki).

Создание подключей

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

в обратной последовательности. K16 используется на первом раунде, K1 используется на последнем раунде. Пусть выходом i-ого раунда шифрования будет Li||Ri. Тогда соответствующий вход (16-i)-ого раунда дешифрования будет Ri||Li.
После последнего раунда процесса расшифрования две половины выхода меняются местами так, чтобы вход заключительной перестановки IP-1 был R16||L16. Выходом этой стадии является незашифрованный текст.

Дешифрование

текст и ключ и используем их в качестве входа

в алгоритм. На первом шаге выполним начальную перестановку IP и получим 64-битное значение Ld0||Rd0. Известно, что IP и IP-1 взаимнообратны. Следовательно

Ld0||Rd0 = IP (зашифрованный текст)

Зашифрованный текст = IP-1(R16||L16)

Ld0||Rd0 = IP(IP-1(R16||L16)) = R16||L16

Таким образом, вход первого раунда процесса дешифрования эквивалентен 32-битному выходу 16-ого раунда процесса шифрования, у которого левая и правая части записаны в обратном порядке.

первого раунда процесса дешифрования эквивалентен 32-битному входу 16-ого раунда

процесса шифрования. Во-первых, рассмотрим процесс шифрования. Мы видим,что

L16 = R15

L16 = R15

F(R15, K16)

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

Ld1 = Rd0 =

L16 = R15

Rd1 = Ld0

F(Rd0, K16) =

= R16

F(Rd0, K16) =

= (L15

F(R15, K16))

F(R15, K16))

B) C = A (B

C)

(A B) C = A (B C)

D D = 0
E 0 = E

Таким образом, мы имеем Ld1 = R15 и Rd1 = L15. Следовательно, выход первого раунда процесса дешифрования есть L15||R15, который является перестановкой входа 16-го раунда шифрования. Легко показать, что данное соответствие выполняется все 16 раундов. Мы можем описать этот процесс в общих терминах. Для i-ого раунда шифрующего алгоритма:

Li = Ri-1

Ri = Li-1

F(Ri-1, Ki)

Li
Li-1 = Ri
F(Ri-1, Ki) = Ri

F(Li, Ki)

Таким образом, мы описали входы i-ого раунда как функцию выходов.
Выход последней стадии процесса дешифрования есть R0||L0. Чтобы входом IP-1 стадии было R0||L0, необходимо поменять местами левую и правую части. Но

IP-1(R0||L0) = IP-1(IP (незашифрованный текст)) = незашифрованный текст

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

56 битам, существует 256 возможных ключей. На сегодня такая

длина ключа недостаточна, поскольку допускает успешное применение лобовых атак. Альтернативой DES можно считать тройной DES, IDEA, а также алгоритм Rijndael, принятый в качестве нового стандарта на алгоритмы симметричного шифрования.
Также без ответа пока остается вопрос, возможен ли криптоанализ с использованием существующих характеристик алгоритма DES. Основой алгоритма являются восемь таблиц подстановки, или S-boxes, которые применяются в каждой итерации. Существует опасность, что эти S-boxes конструировались таким образом, что криптоанализ возможен для взломщика, который знает слабые места S-boxes. В течение многих лет обсуждалось как стандартное, так и неожиданное поведение S-boxes, но все-таки никому не удалось обнаружить их фатально слабые места.

DES считается маленькая длина ключа, поэтому уже давно начали

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

состоит в повторном применении DES с двумя разными ключами.

Используя незашифрованное сообщение P и два ключа K1 и K2, зашифрованное сообщение С можно получить следующим образом:
C = Ek2 [Ek1 [P]]
Для дешифрования требуется, чтобы два ключа применялись в обратном порядке:
P = Dk1 [Dk2 [C]]
В этом случае длина ключа равна 56 * 2 = 112 бит.

DES существует так называемая атака "встреча посередине". Она основана

на следующем свойстве алгоритма. Мы имеем
С = Ek2 [Ek1 [P]]
Тогда
X = Ek1 [P] = Dk2 [C].
Атака состоит в следующем. Требуется, чтобы атакующий знал хотя бы одну пару незашифрованный текст и соответствующий ему зашифрованный текст: (Р, С). В этом случае, во-первых, шифруется Р для всех возможных 256 значений K1. Этот результат запоминается в таблице, и затем таблица упорядочивается по значению Х. Следующий шаг состоит в дешифровании С, с применением всех возможных 256 значений K2. Для каждого выполненного дешифрования ищется равное ему значение в первой таблице. Если соответствующее значение найдено, то считается, что эти ключи могут быть правильными, и они проверяются для следующей известной пары незашифрованный текст, зашифрованный текст.

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

число неверных значений ключей. Но если противник имеет возможность перехватить хотя бы две пары значений (незашифрованный текст - зашифрованный текст), то сложность взлома двойного DES фактически становится равной сложности взлома обычного DES, т.е. 256.

"встреча посередине" состоит в использовании третьей стадии шифрования с

тремя различными ключами. Это поднимает стоимость лобовой атаки до 2168, которая на сегодняшний день считается выше практических возможностей. Но при этом длина ключа равна 56 * 3 = 168 бит, что иногда бывает громоздко.
В качестве альтернативы предлагается метод тройного шифрования, использующий только два ключа. В этом случае выполняется последовательность зашифрование-расшифрование-зашифрование (EDE).

C = EK1 [DK2 [EK1 [P]]]

тройным DES

второй стадии: шифрование или дешифрование. В случае использования дешифрования

существует только то преимущество, что можно тройной DES свести к обычному одиночному DES, используя
K1 = K2:
C = EK1 [DK1 [EK1 [P]]] = EK1 [P]

Тройной DES является достаточно популярной альтернативой DES и используется при управлении ключами в стандартах ANSI X9.17 и ISO 8732 и в PEM (Privacy Enhanced Mail).

Известных криптографических атак на тройной DES не существует. Цена подбора ключа в тройном DES равна 2112.