Menu

Бит бокс видео

бит бокс видео

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

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

Став финалистом конкурса AES, алгоритм Serpent в результате голосования занял 2 место.

Шифр Serpent не запатентован и является общественным достоянием.

Основные принципы

Алгоритм создавался под лозунгом криптографический алгоритм 21 века для участия в конкурсе AES. При создании нового алгоритма Serpent его авторы придерживались консервативных взглядов на проектирование, что подтверждается первоначальным решением об использовании таблиц подстановок из известного много лет ранее алгоритма шифрования DES, который в течение долгого времени изучался ведущими специалистами в области криптографии и защиты информации и чьи свойства и особенности были хорошо известны научному миру. Одновременно с этим к новому алгоритму мог быть применен исчерпывающий анализ, уже разработанный для DES. Не использовались новые, непроверенные и неиспытанные технологии при создании шифра, который в случае принятия был бы использован для защиты огромных массивов финансовых транзакций и правительственной информации. Основным требованием к участникам конкурса AES было то, что алгоритм-претендент должен быть быстрее, чем 3DES, и предоставлять как минимум такой же уровень безопасности: он должен иметь блок данных длиной 128 бит и ключ длиной 256 бит. 16-раундовый Serpent был бы таким же надежным, как 3DES, но в два раза быстрее. Однако, авторы посчитали, что для большей надежности стоит увеличить количество раундов до 32. Это сделало шифр таким же быстрым, как DES, и намного более надежным, чем 3DES.

Структура алгоритма

Алгоритм Serpent представляет собой SP-сеть, в которой весь блок данных длиной 128 бит на каждом раунде разбивается на 4 слова длиной по 32 бита. Все значения, использующиеся при шифровании, представляются битовыми потоками. Индексы бит пробегают значения от 0 до 31 для 32-битных слов, от 0 до 127 для 128-битных блоков, от 0 до 255 для 256-битных ключей и так далее. Для внутренних вычислений все биты величин представлены в прямом порядке (little-endian).

Serpent шифрует открытый текст P длиной 128 бит в шифротекст C длиной так же 128 бит за 32 раунда с помощью 33 подключей длиной 128 бит. Длина используемого ключа может принимать различные значения, но для конкретики зафиксируем их длину в 128, 192 или 256 бит. Короткие ключи длиной менее 256 бит дополняются до полной длины в 256 бит.

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

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

Уравнения структуры алгоритма:

,

где

,

где  это применение таблицы подстановки 32 раз параллельно и  линейное преобразование.

Расшифрование

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

Расширение ключа

Как и другие алгоритмы, участвовавшие в конкурсе AES, Serpent имеет возможные длины ключа 128, 192 или 256 бит. Неполный ключ длиной меньше 256 бит дополняется по следующему правилу: прибавляется единичный бит справа, за ним следует столько нулевых битов, чтобы длина ключа стала равна 256 битам.

Алгоритм выбора подключей из ключа

Сначала при необходимости ключ дополняется до 256 бит и преобразуется в 33 подключа длиной 128 бит следующим способом:

Исходный ключ представляется в виде 8 32-битных слов для вычисления промежуточного ключа по правилу:

,

где  это дробная часть золотого сечения или 0x9e3779b9 в шестнадцатеричной системе счисления, а  это циклический битовый сдвиг.

Раундовые ключи вычисляются из промежуточных ключей использованием таблиц подстановок следующим образом:

Промежуточные 32-битные величины перенумеровываются и получаются 128-битные подключи:

При стандартном описании алгоритма мы должны применить начальную перестановку к раундовому ключу, чтобы расположить биты ключа в надлежащем порядке, то есть

Данная перестановка задается следующей таблицей, где указывается позиция, на которую перейдет соответствующий бит (например, бит 1 перейдет на 32 позицию):

(таблицы замен)

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

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

Ниже представлены таблицы подстановок:

И инверсные таблицы подстановок:

Линейное преобразование задается следующей таблицей, где биты перечислены от 0 до 127 (например, выходной 2 бит образован 2, 9, 15, 30, 76, 84, 126 битами, сложенными по модулю 2). В каждой строке описывается 4 выходных бита, которые вместе составляют входные данные на одну таблицу замен в следующем раунде. Стоит отметить, что данный набор представляет собой таблицу , где и есть то линейное преобразование.

Таблица линейного преобразования:

Таблица обратного линейного преобразования, которое используется при расшифровке:

Данная перестановка является обратной к начальной, то есть , и задается следующей таблицей:

Эффективная реализация

Желание авторов сделать алгоритм именно таким, какой он есть становится понятным при рассмотрении его эффективной низкоуровневой реализации.

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

Шифрование состоит из 32 раундов. Открытый текст является первыми промежуточными данными . Затем выполняется 32 раунда, каждый i раунд состоит из:

,

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

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

Вторая причина состоит в простоте преобразования. Оно может быть реализовано на любом современном процессоре с минимальными затратами.

При разработке и анализе алгоритма Serpent не было выявлено каких-либо уязвимостей в полной 32-раундовой версии. Но при выборе победителя конкурса AES, это было справедливо и к остальным алгоритмам-финалистам.

По мнению создателей Serpent, алгоритм может быть взломан, только если будет создана новая мощная математическая теория.

Стоить отметить, что XSL-атака, если будет доказана эффективность ее проведения, ослабит криптостойкость Serpent.

Сайт управляется системой uCoz