Шифры перестановки и замены

Министерство образования и науки Российской Федерации

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

Уфимский государственный авиационный технический университет

                            Кафедра АСУ

Реферат

на тему «Шифры перестановки и замены»

по дисциплине «Информационная безопасность»

Группа       ПИЭ-404з       

Студент        _______________        _______________      Манапов Р.Т.          

                          (подпись)                               (дата)                                         

Принял         _______________       _______________        Виссарионов В.С.     

                                                                                                 ________________

                                                                                                            (оценка)

Уфа – 2011

Содержание

Введение……………………………………………………………….... 3

1.      Анализ существующих алгоритмов……………………………..4

2.      Критерии выборов………………………………………………..12

3.      Сравнение алгоритмов…………………………………………...13

Заключение ……………………………………………………………...14

Список литературы………………………………………………. …….15

Введение

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

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

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

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

С помощью криптографических методов возможно:

- шифрование информации;
- реализация электронной подписи;
- распределение ключей шифрования;
- защита от случайного или умышленного изменения информации.

В данной работе рассматриваются симметричные блочные алгоритмы, использующие в своей основе подстановочно-перестановочную сеть.

1.      Анализ существующих алгоритмов

Симметричное шифрование — способ шифрования, в котором для шифрования и расшифровывания применяется один и тот же криптографический ключ.

В настоящее время симметричные шифры — это:

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

- поточные шифры, в которых шифрование проводится над каждым битом либо байтом исходного (открытого) текста с использованием гаммирования. Поточный шифр может быть легко создан на основе блочного (например, ГОСТ 28147-89 в режиме гаммирования), запущенного в специальном режиме.

Типичным способом построения алгоритмов симметричного шифрования является сеть Фейстеля. Алгоритм строит схему шифрования на основе функции F(D, K), где D — порция данных, размером вдвое меньше блока шифрования, а K — «ключ прохода» для данного прохода. От функции не требуется обратимость — обратная ей функция может быть неизвестна. Достоинства сети Фейстеля — почти полное совпадение дешифровки с шифрованием (единственное отличие — обратный порядок «ключей прохода» в расписании), что сильно облегчает аппаратную реализацию.

Большинство симметричных шифров используют сложную комбинацию большого количества подстановок и перестановок. Многие такие шифры исполняются в несколько (иногда до 80) проходов, используя на каждом проходе «ключ прохода». Множество «ключей прохода» для всех проходов называется «расписанием ключей» (key schedule). Как правило, оно создается из ключа выполнением над ним неких операций, в том числе перестановок и подстановок. Такая разновидность блочного шифра называется SP-сеть (Substitution-Permutation network, подстановочно-перестановочная сеть). В простейшем варианте представляет собой «сэндвич» из слоёв двух типов, используемых многократно по очереди. Первый тип слоя — P-слой, состоящий из P-блока большой разрядности, за ним идёт второй тип слоя — S-слой, представляющий собой большое количество S-блоков малой разрядности, потом опять P-слой и т. д.

Первым криптографическим алгоритмом на основе SP-сети был «Люцифер». Lucifer — исследовательский проект фирмы IBM 1970-х годов по созданию криптоустойчивого блочного шифра. Результаты исследования привели к созданию двух методов построения устойчивых ко взлому симметричных шифров - сети Фейстеля и подстановочно-перестановочной сети. «Люцифер» заложил основы современной симметричной криптографии. В проекте участвовали, ставшие позднее известными криптографами Хорст Фейстель и Дон Копперсмит. Развития «Люцифера» привело к созданию алгоритма DES.

Структура алгоритма Люцифер образца июня 1971 года представляет из себя SP-сеть. Первый тип слоя — P-блок разрядности 128 бит, за ним идёт второй слой, представляющий из себя 32 модуля, каждый из которых состоит их двух четырёхбитных S-блоков, чьи соответствующие входы закорочены и на них подаётся одно и то же значение с выхода предыдущего слоя. Но сами блоки подстановок различны (отличаются таблицами замен). На выход модуля подаются значения только с одного из S-блоков, какого конкретно определяется одним из битов в ключе, номер которого соответствовал номеру S-блока в структуре. Упрощённая схема алгоритма меньшей разрядности и неполным числом раундов приведена на рисунке 1. В ней используется 16 модулей выбора S-блоков (всего 32 S-блока), таким образом такая схема использует 16-битный ключ.

Рис. 1. Упрощённая схема алгоритма «Люцифер» (неполное число раундов и меньшая разрядность)

Рассмотрим теперь, как будет меняться шифротекст, в приведённом выше алгоритме, при изменении всего одного бита. Для простоты возьмём таблицы замен S-блоков такими, что если на вход S-блока подаются все нули, то и на выходе будут все нули. В силу нашего выбора S-блоков, если на вход шифрующего устройства подаются все нули, то и на выходе устройства будут все нули (рис 2.). В реальных системах такие таблицы замен не используются, так как они сильно упрощают работу криптоаналитика, но в нашем примере они наглядно иллюстрируют сильную межсимвольную взаимосвязь при изменении одного бита шифруемого сообщения. Видно, что благодаря первому P-блоку единственная единица сдвигается перемещается в центр блока, затем следующий нелинейный S-блок «размножает» её, и уже две единицы за счёт следующего P-блока изменяют своё положение и т. д. В конце устройства шифрования, благодаря сильной межсимвольной связи, выходные биты стали сложной функцией от входных и от используемого ключа. В среднем на выходе половина бит будет равна «0» и половина «1».

Рис. 2. Демонстрация «перестановки» и «подстановки» в алгоритме «Люцифер».

В настоящее время из алгоритмов на основе SP-сетей широко используется AES. Advanced Encryption Standard (AES), также известный как Rijndael— симметричный алгоритм блочного шифрования (размер блока 128 бит, ключ 128/192/256 бит), принятый в качестве стандарта шифрования правительством США по результатам конкурса AES. Этот алгоритм хорошо проанализирован и сейчас широко используется, как это было с его предшественником DES. Национальный институт стандартов и технологий США опубликовал спецификацию AES 26 ноября 2001 года после пятилетнего периода, в ходе которого были созданы и оценены 15 кандидатур. 26 мая 2002 года AES был объявлен стандартом шифрования.

Еще одним финалистом 2-го этапа конкурса AES является алгоритм Serpent («змея») — симметричный блочный алгоритм шифрования, разработанный Россом Андерсоном, Эли Бихамом и Ларсом Кнудсеном. Как и другие алгоритмы, участвующие в конкурсе AES, Serpent имеет размер блока 128 бит и возможные длины ключа 128, 192 или 256 бит. Алгоритм представляет собой 32-раундовую SP-сеть, работающую с блоком из четырёх 32-битных слов. Serpent был разработан так, что все операции могут быть выполнены параллельно, используя 32 1-битных «потока».

При разработке Serpent использовался более консервативный подход к безопасности, нежели у других финалистов AES, проектировщики шифра считали, что 16 раундов достаточно, чтобы противостоять известным видам криптоанализа, но увеличили число раундов до 32, чтобы алгоритм мог лучше противостоять ещё не известным методам криптоанализа.

Шифрование состоит из следующих основных шагов:

- начальная перестановка;

- 32 раунда, каждый из которых состоит из операции смешивания с 128-битным ключом (побитовое логическое исключающее «или»), табличная замена (S-box) и линейное преобразование. В последнем раунде линейное преобразование заменяется дополнительным наложением ключа;

- конечная перестановка;

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

SÁFER (англ. Secure And Fast Encryption Routine — безопасная и быстрая процедура шифрования) — в криптографии семейство симметричных блочных криптоалгоритмов на основе подстановочно-перестановочной сети. Существует несколько вариантов шифра, отличающихся друг от друга длиной ключа шифрования и размерами блоков исходного текста.

Первая разновидность алгоритма — SAFER K-64 была разработана Джэймсом Мэсси для калифорнийской корпорации «Cylinc» в 1993 году. Опубликованный в том же году, алгоритм имел блок и ключ шифрования длиной в 64 бита. Для него рекомендовалось использовать 6 раундов шифрования. Однако из-за необходимости увеличить длину ключа до 128 бит (так как была обнаружена слабость в первоначальном варианте алгоритма), Мэсси разработал новый вариант шифра SAFER K-128, который был опубликован на следующий год после SAFER K-64. Новый алгоритм включал в себя расписание ключей, разработанное министерством внутренних дел Сингапура, и в дальнейшем использовался им для различных целей. Также для этого алгоритма рекомендовалось использовать 10 (максимум 12) раундов шифрования.

Спустя некоторое время в первых вариантах алгоритма выявились некоторые слабости, обнаруженные Ларсом Кнудсеном и Шоном Мёрфи . Это повлекло за собой создание новых версий алгоритма, названных SAFER SK-64 и SAFER SK-128, в которых расписание ключей было изменено в соответствии со схемой, предложенной Кнудсеном. Также был разработан вариант с длиной ключа, уменьшенной до 40 бит — SAFER SK-40. Сокращение «SK» в названии алгоритмов расшифровывается как «Strengthened Key schedule» (Усиленное расписание ключей). Для новых вариантов шифра предлагалось использовать не 6, а, по крайней мере, 8 (максимум 10) раундов шифрования.

Алгоритм SAFER+ был разработан в 1998 году калифорнийской корпорацией Cylinc совместно с Армянской академией наук для участия в конкурсе AES, на котором прошёл лишь первый отборочный тур. Данный шифр имеет входной блок длиной 128 бит и размер ключа 128, 192 или 256 бит.

Последней из созданных разновидностей алгоритма SAFER является SAFER++, разработанный Мэсси в 2000 году и ставший дальнейшим развитием алгоритма SAFER+. Алгоритм принял участие в европейском конкурсе алгоритмов NESSIE, где был представлен в двух вариантах: шифр с 64-битным блоком и 128-битным блоком. Он прошёл во вторую фазу конкурса, но не был выбран в набор рекомендуемых NESSIE криптографических примитивов. Эксперты сочли, что шифр слишком медленный на всех машинах, кроме 8-битных (таких как смарт-карты), а запас безопасности шифра слишком мал. Для полнораундового алгоритма SAFER++ не было найдено никаких новых атак. При этом был осуществлён ряд атак на варианты шифра с уменьшенным числом раундов шифрования. Одна из них, будучи неосуществимой вследствие огромного числа необходимых вычислений, теоретически способна взломать SAFER++ с 5,5 раундами вместо семи. Эта атака послужила одной из основных причин, по которым алгоритм не победил в конкурсе. Также, по мнению некоторых экспертов, алгоритм вполне может содержать невыявленные на настоящий момент слабости. Основной же причиной явилось недостаточное быстродействие алгоритма при реализации на многоразрядных устройствах.             

CRYPTON — алгоритм симметричного блочного шифрования (размер блока 128 бит, ключ длиной до 256 бит), разработанный южнокорейским криптологом Че Хун Лим в качестве шифра — участника конкурса AES.

Шифр CRYPTON оперирует с блоками длиной 128 бит в форме матрицы из 4×4 байт. Раундовое преобразование состоит из следующих четырёх этапов: побайтовая подстановка, пермутация бит в колонке, транспозиция из колонки в строку, финальное добавление ключа. Каждый этап может быть выполняется параллельно, что важно при реализации на современных многоядерных и мультипоточных системах.

Особенностью шифра является то, что для зашифрования и расшифрования может использоваться одна и та же процедура, но с разными подключами. Алгоритм эффективен как при программной, так и при аппаратной реализации. Шифр достаточно быстр — на конкурсе AES при использовании компилятора Borland C показал наилучшие результаты среди всех участников.

Во время проведения конкурсного отбора было выявлено, что у шифра нет каких-либо явных недостатков. Однако, поскольку шифр очень схож с Rijndael по своей структуре типа «квадрат» и также является своеобразным потомком шифра SQUARE бельгийских криптографов Дамена и Рэмена, но при этом сам Rijndael в целом выглядел лучше, алгоритм CRYPTON в финалисты выбран не был.