Алгоритм AES

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Алгоритм AES



Инициатива в разработке AES (AdvancedEncryptionStandard) принад-лежит NIST. Основная цель состояла в создании алгоритма симметричного шифрования, который мог бы использоваться для защиты информации как в государственном, так и в частном секторе.

В результате длительного процесса оценки был выбран алгоритм Rijndael в качестве алгоритма AES. Мы кратко рассмотрим основные принципы выбора алгоритма, характеристики алгоритмов, которые рассматривались в качестве претендентов на AES.

В январе 1997 года NIST объявил о начале разработки AES, и в сентяб-ре 1997 года были представлены официальные требования к алгоритмам. В этих требованиях указывалось, что целью NIST является разработка неклассифицированного, хорошо проанализированного алгоритма шифрования, доступного для широкого применения. Алгоритм должен быть сим-метричным, блочным, поддерживать длину блока 128 бит и длину ключа 128, 192 и 256 бит.

В августе 1998 года NIST анонсировал пятнадцать кандидатов на алгоритм AES на первой конференции по кандидатам AES. Данные алгоритмы были разработаны промышленными и академическими кругами двенадцати стран. Вторая конференция по кандидатам AES была проведена в марте 1999 года с целью обсуждения результатов анализа предложенных алгоритмов. В августе 1999 года были представлены выбранные NIST пять финалистов. Ими стали MARS, RC6TM, Rijndael, Serpent и Twofish.

Обзор алгоритмов

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

Первое и последнее преобразования могут отличаться от преобразования остальных раундов. Такие операции, используемые на начальном шаге первого раунда и заключительном шаге последнего раунда, называются pre- и post-забеливанием (whitening) и могут быть определены отдельно.

Рассмотрим основные особенности алгоритмов. В четырех алгоритмах существуют таблицы подстановки, называемые S-box: A x B-битный S-box преобразует А входных битов в В выходных битов. Три алгоритма основаны на сети Фейштеля. В классической сети Фейштеля в каждом раунде преобразуется только одна половина блока данных, затем половины блока меняются местами. Два алгоритма не используют сеть Фейштеля, в результате этого в каждом раунде обрабатывается весь блок данных, используя различные подстановки и преобразования.

MARS выполняет последовательность преобразований в следующем порядке: сложение с ключом в качестве pre-whitening, 8 раундов прямого перемешивания без использования ключа, 8 раундов прямого преобразова-ния с использованием ключа, 8 раундов обратного преобразования с использованием ключа, 8 раундов обратного перемешивания без использования ключа и вычитание ключа в качестве post-whitening. 16 раундов с использованием ключа называются криптографическим ядром. Раунды без ключа используют два 8X16- битных S-box и операции сложения и XOR. В дополнение к этим элементам раунды с ключом используют 32-битное умножение ключа, зависимые от данных циклические сдвиги и добавление ключа. Как раунды перемешивания, так и раунды ядра являются раундами модифицированной сети Фейштеля, в которых четверть блока данных используется для изменения остальных трех четвертей блока данных. MARS был предложен корпорацией IBM.

RC6 является параметризуемым семейством алгоритмов шифрования, основанных на сети Фейштеля; в качестве AES было предложено использовать 20 раундов. Функция раунда в алгоритме RC6использует переменные циклические сдвиги, которые определяются квадратичной функцией от данных. Каждый раунд также включает умножение по модулю 32, сложение, XOR и сложение с ключом. Сложение с ключом также используется для pre- и pos-whitening. RC6 был предложен лабораторией RSA.

Rijndael представляет собой алгоритм, использующий линейно-подстановочные преобразования и состоящий из 10, 12 или 14 раундов в зависимости от длины ключа. Блок данных, обрабатываемый алгоритмом Rijndael, представляется в виде последовательности байтов, и в этом смысле каждое преобразование является байт-ориентированным. Функция раунда Rijndael состоит из четырех слоев. В первом слое для каждого байта применяется S-box размерностью 8х8 бит. Второй и третий слои являются линейными перемешиваниями, в которых строки рассматриваются в качестве сдвигаемых массивов и столбцы перемешиваются. В четвертом слое выполняется операция XOR байтов подключа и массива. В последнем раунде перемешивание столбцов опущено. Rijndael предложен JoanDaemen (ProtonWorldInternational) и VincentRijmen (KatholiekeUniversiteitLeuven).

Serpent является алгоритмом, использующим линейно-подстановочные преобразования и состоящим из 32 раундов. Serpent также определяет не криптографические начальную и заключительную перестановки, которые облегчают альтернативный режим реализации, называемый bitslice. Функция раунда состоит из трех слоев: операция XOR с ключом, 32-х параллельное применение одного из восьми фиксированных S-box и линейное преобразование. В последнем раунде слой операции XOR с ключом заменен на линейное преобразование. Serpent предложен Ross Anderson (University of Cambridge), Eli Biham (Technion) и Lars Knudsen (University of California San Diego).

Twofish является сетью Фейштеля с 16 раундами. Сеть Фейштеля не-значительно модифицирована с использованием однобитных ротаций. Функция раунда влияет на 32-битные слова, используя четыре зависящих от ключа S-box, за которыми следуют фиксированные максимально удаленные отдельные матрицы в GF(28), преобразование псевдо-Адамара и добавление ключа. Twofish был предложен BruceSchneier, JohnKelsey и NielsFerguson (CounterpaneInternetSecurity, Inc.), DougWhiting (Hi/fn, Inc.), DavidWagner (UniversityofCaliforniaBerkley) и ChrisHall (PrincetonUniversity).

Критерий оценки

В сентябре 1997 года были определены общие критерии, которые должны использоваться для сравнения алгоритмов.

В сентябре 1997 года были определены общие критерии, которые должны использоваться для сравнения алгоритмов.

Безопасность.

Стоимость.

Характеристики алгоритма и его реализации.

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

Стоимость является вторым по важности параметром оценки, который характеризует лицензионные требования, вычислительную эффективность (скорость) на различных платформах и требования к памяти. Так как одной из целей была возможность широкого использования алгоритма AES без лицензионных ограничений, обсуждались в основном требования защиты интеллектуальной собственности и потенциальные конфликты, связанные с этим. Рассматривалась также скорость работы алгоритма на различных платформах. В первую очередь основное внимание уделялось скорости, связанной со 128-битными ключами. Затем рассматривались аппаратные реализации и производительность алгоритма при использовании 192- и 256-битных ключей. Также рассматривались требования к памяти и ограничения программной реализации.

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

управлять размером ключа и блока, отличных от тех, которые обязательно должны поддерживаться;

безопасно и эффективно реализовываться в различных типах окружений;

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

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

Принципы выбора алгоритма

До выбора алгоритма следовало принять несколько фундаментальных решений:

Использовать количественный или качественный критерий при выборе алгоритма.

Выбрать один или несколько алгоритмов в качестве AES.

Выбрать запасной алгоритм(ы).

Рассмотреть предложения по модификации алгоритмов.

Качественный или количественный критерий

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

Количество алгоритмов AES

Высказывались несколько аргументов относительно количества алго-ритмов, которые должны быть выбраны в качестве AES. Также обсуждался вопрос относительно "запасного" алгоритма для случая, если будет выбран единственный AES-алгоритм, и его модификация в случае обнаружения уязвимости окажется невозможной.

Это необходимо в интересах безопасности. Если один алго-ритм AES будет взломан, в приложениях должны уже быть ре-ализованы другие AES-алгоритмы. Считается, что применение единственного алгоритма является рискованным, если этот ал-горитм окажется небезопасным.

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

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

Были также высказаны мнения в пользу единственного алгоритма (против нескольких алгоритмов). Некоторые из этих аргументов таковы:

Использование нескольких AES-алгоритмов уменьшает инте-роперабельность и увеличивает стоимость приложений.

Наличие нескольких алгоритмов может являться своеобразной "атакой на интеллектуальную собственность", направленной на реализации алгоритмов.

Определение нескольких алгоритмов может вызвать обсужде-ние вопросов безопасности любого из алгоритмов.

Аппаратные реализации могут лучше использовать доступные ресурсы, оптимизируя выполнение единственного алгоритма, а не нескольких алгоритмов.

Существует вероятность, что в подавляющем большинстве случаев приложения будут реализовывать несколько алгоритмов, что определяется нуждами потребителей, требованиями интероперабельности с наследуемыми или собственными системами и так далее. Тройной DES, который NIST предлагает оставить в обозримом будущем FIPS-алгоритмом, доступен во многих коммерческих продуктах, как и другие FIPS и не-FIPS алгоритмы. Считается, что наличие подобных нескольких алгоритмов в конкретном приложении обеспечивает большую степень надежности, как и наличие нескольких длин ключей в AES. В случае атаки на выбранный алгоритм предлагается задействовать соответствующие исследованные параметры других кандидатов AES, у которых отсутствуют подобные атаки, либо в случае необходимости определить полностью новые подходы.

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

В результате было решено выбрать единственный алгоритм.

Запасной алгоритм

Как уже отмечалось, существует взаимосвязь между проблемой, связанной с выбором нескольких алгоритмов AES и выбором запасного алгоритма, особенно в случае единственного алгоритма AES. Запасной алгоритм может иметь несколько форм, от алгоритма, который требуется реализовывать в продуктах AES ("hotbackup"), до определяемого в AES за-пасного алгоритма ("coldbackup"). Было доказано, что запасной алгоритм во многом эквивалентен второму AES-алгоритму, так как многие пользова-тели пожелают, чтобы даже "coldbackup" был реализован в продуктах.

Итак, имея

представления о том, что запасной алгоритм должен defacto требоваться в продуктах;

омнения относительно необходимости запасного алгоритма в связи с достижениями криптоанализа;

заинтересованность в обеспечении интероперабельности;

доступность в коммерческих продуктах других алгоритмов;

было принято решение не выбирать запасной алгоритм.

Модификация алгоритмов

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

Было принято решение не изменять количество раундов AES-алгоритма. Причины этого в следующем:

В этом случае не ясно строгое определение алгоритма, включая управление ключом. Также не понятно как изменение числа раундов влияет на безопасность алгоритма.

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

Безопасность AES

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

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

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

Одним из возможных критериев резерва безопасности является число, на которое полное число раундов алгоритма превышает наибольшее число раундов, при котором возможна атака. Существует ряд причин, объясняющих, почему не следует полагаться исключительно на подобную метрику для определения силы алгоритма; тем не менее, данная метрика резерва безопасности может быть полезна.

Программные реализации

Программные реализации алгоритмов могут быть выполнены в широком диапазоне языков программирования и аппаратных архитектур. В некоторых случаях память никак не ограничена; в других случаях RAM и/или ROM могут быть существенно ограничены. Иногда большое количество данных шифруется и расшифровываются единственным ключом. В остальных случаях ключ изменяется часто, возможно, для каждого блока данных.

Скорость шифрования и/или расшифрования часто является противоположностью безопасности. Это означает, что число раундов, указанное для алгоритма, является фактором безопасности; скорость шифрования или расшифрования приблизительно пропорциональна числу раундов. Таким образом, скорость не может исследоваться независимо от безопасности.

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

Размер машинного слова

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

Считается, что в ближайшие годы 8-битные, 32-битные и 64-битные архитектуры будут играть важнейшую роль (в какой-то момент будут добавлены 128-битные архитектуры). Хотя 8-битные архитектуры используются приложениями, которые имеют и 32-битные версии, 8-битные архитектуры не исчезнут окончательно. Между тем некоторые 32-битные архитектуры будут вытеснены 64-битными версиями, но 32-битные архитектуры будут использоваться приложениями с более низкими требованиями, т.е. важность 32-битных архитектур также останется высокой. Важность 64-битных архитектур будет возрастать. Таким образом, AES должен хорошо выполняться на различных архитектурах.

Следует заметить, что выполнение не может оцениваться только на основе длины слова. Должны учитываться также дополнительные факторы, предоставляемые ПО, которые обсуждаются далее.

Языки реализации

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

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

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

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

Окружения с ограничениями пространства

В некоторых окружениях, обладающих небольшими объемами RAM и/или ROM для таких целей, как хранение кода (обычно в ROM), представление объектов данных, таких как S-box (которые могут храниться в RAM или ROM в зависимости от того, известны ли они заранее или нет) и хранение подключей (в RAM), существуют значительные ограничения. Теоретически могут использоваться промежуточные формы хранения, например, EEPROM, для таких значений как подключи. Тем не менее, можно предполагать, что подключи также хранятся в RAM.

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

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

Алгоритм Rijndael

В качестве AES был выбран алгоритм Rijndael.

Предварительные математические понятия

Практически все операции Rijndael определяются на уровне байта. Байты можно рассматривать как элементы конечного поля GF (28). Некоторые операции определены в терминах четырехбайтных слов. Введем основные математические понятия, необходимые для обсуждения алгоритма.

Поле GF (2^8)

Элементы конечного поля могут быть представлены несколькими различными способами. Для любой степени простого числа существует един-ственное конечное поле, поэтому все представления GF (28) являются изоморфными. Несмотря на подобную эквивалентность, представление влияет на сложность реализации. Выберем классическое полиномиальное представление.

Байт b, состоящий из битов b7, b6, b5, b4, b3, b2, b1, b0, можно записать в виде полинома с коэффициентами из {0, 1}:

Пример: байт с шестнадцатеричным значением 57 (двоичное значение 01010111) соответствует полиному

Определим операцию сложения.

Сумма двух элементов, представленных в виде полинома, является полиномом с коэффициентами, равными сумме по модулю 2 (т.е. 1 + 1 = 0) коэффициентов слагаемых.

Пример: 

В полиномиальной нотации:

В бинарной нотации:

Введенное таким образом сложение есть XOR битов в байте.

Выполнены все необходимые условия Абелевой группы: определена операция сложения, обладающая свойством, что каждой паре элементов сопоставляется третий элемент группы, называемый их суммой. Существует нулевой элемент, равный `00', обратный элемент относительно опера-ции сложения. Операция обладает свойствами ассоциативности и коммутативности.

Определим операцию умножения.

В полиномиальном представлении умножение в GF (28) соответствует умножению полиномов по модулю неприводимого двоичного полинома степени 8. Полином называется неприводимым, если он не имеет делителей, кроме 1 и самого себя. Для Rijndael такой полином является m(x):

или `11B' в шестнадцатеричном представлении.

Пример: 

Сначала перемножим два полинома

Теперь найдем остаток от деления на полином m(x)

Таким образом, получили

В этом случае результат будет полиномом не выше 7 степени. В отличие от сложения, простой операции умножения на уровне байтов не существует.

Введенная операция умножения является ассоциативной, существует единичный элемент `01'. Для любого двоичного полинома b(x) не выше 7-й степени можно использовать расширенный алгоритм Евклида для вычисления полиномов a(x) и c(x) таких, что

Это можно записать как

Или

Более того, можно показать, что

Из всего этого следует, что множество из 256 возможных значений байта образует конечное поле GF (28) c XOR в качестве сложения и умножением, определенным выше.

Умножение на х

При умножении b(x)на полином х получаем:

Для вычисления x * b(x) необходимо результат взять по модулю m(x). Если b7 = 0, то результатом является исходный полином, для которого выполнен сдвиг на 1 бит влево. Если b7 = 1, то кроме сдвига влево на 1 бит следует выполнить операцию XOR с m(x). Следовательно, умножение на х на уровне байта есть левый сдвиг и в зависимости от значения b7 побитовый XOR c `1B'. Данная операция обозначается как xtime (b).

Использование данной операции позволяет более быстро выполнить умножение двух байтов.

Полиномы с коэффициентами из GF (2^8)

Полиномы могут быть определены с коэффициентами из GF (28). В этом случае четырехбайтный вектор соответствует полиному степени 4.

Операцию сложения можно ввести как XOR соответствующих коэффи-циентов.

Умножение вводится более сложным способом. Предположим, что мы имеем два полинома в GF (28).

 определяется следующим образом:

Ясно, что в таком виде с(х)не может быть представлен четырехбайтным вектором. Если понизить с(х) по модулю полинома 4-й степени, то результат будет полиномом не выше 3 степени. В Rijndael для этого используется полином

В этом случае

Остаток от деления а(х)*b(x)на M(x)обозначим d(x) = a(x)? b(x).

Коэффициенты d(x)равны:

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

Рис. 2.1. Умножение на фиксированный полином в GF (2^8)

Заметим, что х4+ 1 не является несократимым полиномом в GF (28), следовательно, умножение на фиксированный полином необязательно обратимо. В алгоритме Rijndael выбран фиксированный полином, который имеет обратный.

Умножение на х

При умножении b(x)на полином х имеем:

x Ч b(x)получается понижением полученного результата по модулю х4+1. Получаем

Умножение на х эквивалентно умножению на матрицу, как описано выше, со всеми ai=`00' за исключением а1 = `01'.

Имеем:

Рис. 2.2. Умножение на х в GF (2^8)

Следовательно, умножение на х соответствует циклическому сдвигу байтов внутри вектора.

Обоснование разработки

В основу разработки алгоритма были положены следующие три критерия:

Противодействие всем известным атакам;

Достаточно хорошая скорость выполнения и компактность ко-да для широкого круга платформ;

Простота разработки.

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

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

Нелинейное преобразование состоит в применении S-box, которые улучшают нелинейные свойства в наихудшем случае.

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

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

Слой сложения с ключом состоит из простого XOR текущего состояния с ключом раунда.

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

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

Описание алгоритма

Rijndael является блочным алгоритмом шифрования с переменной длиной блока и переменной длиной ключа. Длина блока и длина ключа могут быть независимо друг от друга установлены в 128, 192 или 256 бит.

Понятие состояния, ключ шифрования и число раундов

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

Состояние можно рассматривать как двумерный массив байтов. Этот массив имеет четыре строки и различное число столбцов, обозначаемое как Nb, равное длине блока, деленной на 32. Ключ также можно рассматривать как двумерный массив с четырьмя строками. Число столбцов ключа шифрования, обозначаемое как Nk, равно длине ключа, деленной на 32.

В некоторых случаях блок шифруемого сообщения рассматривается как одномерный массив четырехбайтных векторов, где значениями каждого вектора являются значения соответствующего столбца. Такие массивы имеют длину 4, 6 или 8 соответственно, и индексы в диапазонах 0…3, 0…5 или 0…7. Четырехбайтные вектора иногда мы будем называть словами.

Если необходимо указать четыре отдельных байта в четырехбайтном векторе, будет использоваться нотация (a, b, c, d), где a, b, cи d являются байтами в позициях 0, 1, 2 и 3, соответственно, в рассматриваемом столбце, векторе или слове.

Рис. 2.3. Пример состояния (с Nb = 6) и ключа шифрования (с Nk = 4)

Входы и выходы Rijndael считаются одномерными массивами из 8 бай-тов, пронумерованными от 0 до 4* Nb - 1. Следовательно, эти блоки имеют длину 16, 24 или 32 байта, и массив индексируется в диапазонах 0 … 15, 0 … 23 или 0 … 31. Ключ считается одномерным массивом 8-битных байтов, пронумерованных от 0 до 4* Nk - 1. Следовательно, эти блоки имеют длину 16, 24 или 32 байта, и массив индексируется в диапазонах 0 … 15, 0 … 23 или 0 … 31.

Входные байты алгоритма отображаются в байты состояния в следующем порядке: А0,0, А1,0, А2,0, А3,0, А0,1, А1,1, А2,1, А3,1, А0,2, … Байты ключа шифрования отображаются в массив в следующем порядке: K0,0, K1,0, K2,0, K3,0, K0,1, K1,1, K2,1, K3,1, … После выполнения операции шифрования выход алгоритма получается из байтов состояния аналогичным образом.

Следовательно, если одномерный индекс байта в блоке есть n, и двухмерный индекс есть (i,j), то мы имеем:

Более того, индекс i является также номером байта в четырехбайтном векторе или слове, j является индексом вектора или слова во вложенном блоке.

Число раундов обозначается Nr и зависит от значений Nb и Nk, что показано в следующей таблице.

Рис. 2.4. Число раундов как функция от длины блока и длины ключа)

Преобразование раунда

Преобразование раунда состоит из четырех различных преобразований. В нотации на псевдо С это можно записать следующим образом:

Round (State, RoundKey)

{

ByteSub (State);

ShiftRow (State);

MixColumn (State);

AddRoundKey (State, RoundKey);

}

Заключительный раунд алгоритма немного отличается и выглядит сле-дующим образом:

FinalRound (State, RoundKey)

{ алгоритм шифрование машинный раунд

ByteSub (State);

ShiftRow (State);

AddRoundKey (State, RoundKey);

}

Как мы видим, заключительный раунд эквивалентен остальным, за ис-ключением того, что отсутствует слой MixColumn.

Преобразование ByteSub

Преобразование ByteSub является нелинейной байтовой подстановкой, выполняющейся независимо для каждого байта состояния. Подстановка является обратимой и определена в виде композиции двух преобразований:

Во-первых, выполняется мультипликативная инверсия в GF (28) для определенного выше представления байта в виде полинома 7 степени. `00' отображается сам в себя.

Затем выполняется аффинное (в GF (2)) преобразование, определяемое следующим образом:

Рис. 2.5. Аффинное преобразование

Применение описанного S-box ко всем байтам состояния обозначается как ByteSub (State)

На следующем рисунке показан результат применения преобразования ByteSub к State.

Рис. 2.6. Применение ByteSub для каждого байта в State

Обратное преобразование ByteSub есть применение байтовой подста-новки в соответствии с инверсной таблицей. Это получается инверсией аффинного отображения и мультипликативной инверсией в GF (28).

Преобразование ShiftRow

В ShiftRow строки состояния циклически сдвигаются на различные значения. Нулевая строка не сдвигается. Строка 1 сдвигается на С1байтов, строка 2 на С2 байтов, строка 3 на С3 байтов. Величины С1, С2 и С3 зависят от Nb. Значения приведены в следующей таблице.

Рис. 2.7. Величина сдвига в зависимости от длины блока

Операция сдвига строк на указанные значения обозначается как

ShiftRow (State)

Инверсией для ShiftRow является циклический сдвиг трех нижних строк соответственно на Nb - С1, Nb - С2 и Nb - С3 байт, чтобы байт в позиции j в строке i перемещался в позицию (j + Nb - Ci) modNb.

Преобразование MixColumn

В MixColumn столбцы состояния рассматриваются как полиномы в GF(28) и умножаются по модулю х4 + 1 на фиксированный полином:

Данный полином является взаимно простым с х4 + 1 и, следовательно, имеет обратный. Как обсуждалось, это может быть записано в виде умножения матрицы.

Пусть b(x) = c(x) /otimes a(x)

Рис. 2.8. Преобразование MixColumn умножением на полином c(x)

Применение данной операции ко всем столбцам состояния обозначает-ся как

MixColumn (State)

Инверсия MixColumn является преобразованием, аналогичным MixColumn. Каждый столбец преобразуется умножением его на полиномd(x), определяемый следующим образом:

В результате получаем

Сложение с ключом раунда

Выполняется операция побитового XOR ключа раунда с текущим состоянием. Длина ключа раунда равна длине блока Nb. Данное преобразование обозначается как

AddRoundKey (State, RoundKey)

AddRoundKey является инверсией самого себя.

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

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

Общее число битов для ключей раундов равно длине блока, умноженной на количество раундов плюс 1. Например, для длины блока 128 бит и 10 раундов необходимо 1408 битов для ключей раундов.

Сначала выполняется расширение ключа.

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

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

Расширенный ключ является линейным массивом четырехбайтных слов и обозначается как W [Nb * (Nr + 1)]. Первые Nk слов состоят из ключа шифрования. Остальные слова определяются рекурсивно. Функция расширения ключа зависит от значения Nk: существует версия функции для Nk, равным или меньшим 6, и версия для Nk больше 6.

Для Nk ? 6 мы имеем:

KeyExpansion (byte Key [4*Nk] word W[Nb * (Nr + 1)])

{

for (i = 0; i<Nk; i++)

W[i] =(Key [4*i], Key [4*i+1], Key [4*i+2], Key [4*i+3]);

for (i = Nk; i<Nb * (Nr + 1); i++) {

temp = W [i - 1];

if (i % Nk == 0)

temp = SubByte (RotByte (temp)) ^ Rcon [i / Nk];

W [i] = W [i- Nk] ^ temp;

}

}

В данном случае SubByte (W) является функцией, которая возвращает четырехбайтное слово, в котором каждый байт является результатом применения S-box Rijndael к байту в соответствующей позиции во входном слове. Функция RotByte(W) возвращает слово, в котором байты циклически переставлены таким образом, что для входного слова (a, b, c, d) создается выходное слово (b, c, d, a).

Можно заметить, что первые Nk слов заполняются ключом шифрования. Каждое следующее слово W[i] равно XOR предыдущего словаW[i-1] и позиций слова Nk до W[i - Nk]. Для слов в позициях, которые кратны Nk, сначала применяется преобразование XOR кW[i-1] и константой раунда. Данное преобразование состоит из циклического сдвига байтов в слове (RotByte), после чего выполняется табличная подстановка для всех четырех байтов в слове (SubByte).

Для Nk> 6 мы имеем:

KeyExpansion (byte Key [4*Nk] word W [Nb* (Nr+1)])

{

for (i=0; i<Nk; i++)

W[i]= (key [4*i], key [4*i+1], key [4*i+2], key [4*i+3]);

for (i = Nk; i<Nb * (Nr + 1); i++) {

temp = W [i-1];

if (i % Nk == 0)

temp = SubByte (RotByte (temp)) ^ Rcon [i / Nk];

else if (i % Nk == 4)

temp = SubByte (temp);

W[i] = W[i - Nk] ^ temp;

}

}



Отличие для Nk ? 6 состоит в том, что для i-4, кратных Nk, SubByte применяется для W[i-1] перед выполнением XOR.

Константы раунда не зависят от Nk и определяются следующим образом:

Rcon [i] = (RC [i], `00', `00', `00')

RC [i] являются элементами в GF (28) со значением x(i-1) таким, что:

RC [1] = 1 (т.е. `01')

RC [i] = x (т.е. `02') * (RC [i-1]) = x(i-1)

Ключ раунда i получается из слов буфера ключа раунда W [Nb * i] до W [Nb * (i+1)].

Преимущества алгоритма

Преимущества, относящиеся к аспектам реализации:

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

Rijndael можно реализовать в смарткарте в виде кода, используя небольшой RAM и имея небольшое число циклов. Выполнена оптимизация размера ROM и скорости выполнения.

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

Алгоритм шифрования не использует арифметические операции, поэтому тип архитектуры процессора не имеет значения.

Простота разработки:

Алгоритм шифрования полностью "само определяемый". Он не использует других криптографических компонентов, S-box, взятых из хорошо известных алгоритмов, битов, полученных из специальных таблиц, чисел типа p и тому подобных уловок.

Алгоритм не основывает свою безопасность или часть ее на неясностях или плохо понимаемых итерациях арифметических операций.

Компактность алгоритма не дает возможности спрятать люки.

Переменная длина блока:

Длины блоков от 192 до 256 бит позволяют создавать хэш-функции без коллизий, использующие Rijndael в качестве функции сжатия. Длина блока 128 бит сегодня считается для этой цели недостаточной.

Расширения:

Определение алгоритма позволяет специфицировать варианты длины блока и длины ключа в диапазоне от 128 до 256 бит с шагов в 32 бита.

Хотя число раундов Rijndael для AES фиксировано, в случае возникновения проблем с безопасностью алгtоритм можно модифицировать, сделав число раундов параметром алгоритма.

Расширения алгоритма

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

Алгоритм вычисления подключей поддерживает вычисление ключей, длина которых кратна 4 байтам. Единственный параметр, который необходимо учитывать при определении длины ключа, является количество раундов алгоритма.

Структура алгоритма допускает длину блока, кратную 4 байтам. Минимальная длина блока должна быть 16 байтов. Увеличение длины ключа, ByteSub и MixColumn преобразования не зависят от длины блока. Единственным преобразованием, которое зависит от длины блока, является ShiftRow. Для каждой длины блока должны быть определены соответствующие константы С1, С2, С3.

Можно определить расширение Rijndael, которое также поддерживает длины блока и ключа между 128 и 256 битами с шагом 32 бита. Число раундов определяется следующим образом:

Данное выражение задает правило определения количества раундов для альтернативных значений длины блока и длины ключа.

Соответствующие значения С1, С2 и С3 указаны в следующей таблице.

Таблица 2.1.
Nb	C1	C2	C3
5	1	2	3
7	1	2	4

Размещено на Allbest.ru

...