Алгоритм Crypton

Алгоритм Crypton разработан в 1998 г. Че Хун Лимом (Chae Hoon Lim) из южнокорейской компании Future Systems. Изначально на конкурс AES была представлена версия алгоритма Crypton v0.5 — по словам разработчика алго­ритма, ему не хватило времени на подготовку полноценной версии. Уже в процессе анализа алгоритмов в рамках первого этапа конкурса AES Crypton v0.5 был заменен на Crypton v 1.0. Версия 1.0 отличалась от преды­дущей измененными таблицами замен и модифицированной процедурой расширения ключа, именно она и описана в данной книге.

Основные характеристики и структура алгоритма

Как и другие участники конкурса AES, Crypton шифрует 128-битные блоки данных. Используются ключи шифрования нескольких фиксированных раз­меров — от 0 до 256 битов с кратностью 8 битов.

Структура алгоритма Crypton во многом повторяет структуру алгоритма Square (см. разд. 3.54), разработанного в 1997 г. будущими авторами алго­ритма Rijndael (см. разд. 3.3) — победителя конкурса AES — Винсентом Риджменом и Джоан Деймен.

Алгоритм Crypton представляет 128-битный блок шифруемых данных в виде байтового массива размером 4×4, над которым в процессе шифрования про­изводится несколько раундов преобразований. В каждом раунде предполага­ется последовательное выполнение нижеперечисленных операций [239, 240]:

1. Табличная замена у (рис. 3.41). Алгоритм Crypton использует 4 таблицы замен, каждая из которых замещает 8-битное входное значение на выход­ное такого же размера. Все таблицы S0S3 являются производными от основной таблицы S (см. рис. 3.42, на котором «п обозначает цикличе­ский сдвиг влево значения обрабатываемого байта на п битов) и приведе­ны в Приложении 1.

clip_image002

Рис. 3.41. Операция у

clip_image004

Рис. 3.42. Вычисление производных таблиц замен

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

Уе(УоШ = У0е(А)) = А4-

где А — текущее значение блока шифруемых данных. Операции уе и у0 можно определить следующим образом:

Ye ‘-ty = 5(^+2+1 mod4) У о : fyj = S(j+imod4)(aij)>

где:

ay — текущее значение конкретного байта данных;

• Ьц — значение байта данных после выполнения операции.

clip_image006

2. Линейное преобразование я (рис. 3.43). Здесь используются 4 специаль­ные константы (указаны шестнадцатеричные значения):

т0 = FC;

Ш| =F3;

т2 = CF;

m3 = 3F,

которые объединены в следующие маскирующие последовательности:

М0 = т3т2 • Ш| • т0;

Mj =m0^m3^m2^ml;

М2 – тх • т0 • т3 • т2;

М3 – т2 шт{ • т0 •т3, где • — операция конкатенации.

clip_image008

clip_image010

Сама же операция п представляет собой битовую перестановку. В нечет­ных раундах используется операция п():

clip_image012

где:

• & — логическая побитовая операция «и»;

A[i] и B[i] — значение У-й строки обрабатываемых данных до и после выполнения операции соответственно.

В четных раундах используется операция пе:

clip_image014

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

3. Байтовая перестановка т, простейшим образом преобразующая строку данных в столбец (рис. 3.44):

*:bij=aji-

clip_image016

Рис. 3.44. Операция т

4. Операция а, представляющая собой побитовое сложение всего массива данных с ключом раунда (рис. 3.45):

о:В = А@Кп

clip_image018

clip_image020

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

145

где:

В — новое значение блока шифруемых данных;

Кг — ключ текущего раунда г (процедура формирования ключей раундов описана далее).

clip_image022

Рис. 3.45. Операция а

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

Расшифровывание выполняется применением обратных операций в обратной последовательности. Все операции, кроме уе и у(), являются обратными са­мим себе, а уе и yG связаны следующими соотношениями:

clip_image024

поэтому при расшифровывании у() используется в четных раундах, а уе в нечетных.

Стоит сказать, что в спецификации алгоритма [240] дано подробное матема­тическое обоснование всех используемых в алгоритме операций. С особой подробностью рассмотрены принципы построения исходной таблицы замен S и ее свойства.

Процедура расширения ключа

Алгоритм Crypton требует наличия 128-битного ключа для каждого раунда, а также 128-битного ключа для предварительной операции а. Процедура вы­полняется в два этапа: на первом из ключа шифрования формируется 8 рас­ширенных ключей, а на втором — из расширенных ключей вычисляются ключи раундов.

146

Гпава 3

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

1. Если ключ шифрования имеет размер, меньший 256 битов, он предваряет­ся битовыми нулями до достижения 32-байтного исходного ключа К:

clip_image026

2. Ключ К разбивается на последовательности U и V, первая из которых со­держит только четные байты ключа, вторая — только нечетные:

clip_image028

3. Над U и V выполняется один раунд шифрования (для U выполняются пре­образования нечетного раунда, для V— четного) алгоритма Crypton с ис­пользованием ключа раунда, состоящего из нулевых битов; результирую­щие последовательности обозначаются как LT и V.

4. 8 расширенных ключей вычисляются таким образом:

clip_image030

для / = 0,1,2,3, где Тх и Т0 — последовательности, формируемые согласно формулам:clip_image032

При вычислении ключей раундов из расширенных ключей используется сле­дующий набор констант:

clip_image034

причем псевдослучайные константы A54FF53A и 3C6EF372 образованы зна­чениями дробных частей от V7 и V5″ соответственно.

Сначала вычисляются ключи для предварительной операции а и первого ра­унда:

clip_image036

где Kr[i] iстрока ключа раунда г (аналогично шифруемым данным, ключ представляется в виде таблицы — см. рис. 3.45).

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

147

Константы Мс{ вычисляются путем побитового циклического сдвига каждо­го байта (раздельно) константы Мсм на 1 бит влево.

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

1. Выполняется модификация первых четырех расширенных ключей:

clip_image038

где знаком «< обозначена операция побитового циклического сдвига ка­ждого байта (раздельно) расширенного ключа на указанное число битов влево, а « — операция побитового циклического сдвига всего ключа на указанное число битов влево.

2. Вычисление ключа раунда с помощью модифицированных расширенных ключей:

clip_image040

Аналогичным образом вычисляются ключи для нечетных раундов:

clip_image042

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

Достоинства и недостатки алгоритма

При анализе исходной версии алгоритма — Crypton v0.5 — сразу двое экс­пертов [103, 284] независимо обнаружили класс слабых ключей: таковых оказалось 232 256-битных ключей. Кроме того, была обнаружена атака, ана­логичная известной атаке на алгоритм Square, на 6-раундовую версию алго­ритма Crypton [170]. Возможно, именно эти результаты привели к появлению следующей версии алгоритма.

По правилам конкурса AES разрешалось модифицировать алгоритмы в про­цессе конкурса, чем воспользовались некоторые разработчики [284]. Однако изменения не должны были быть значительными, чтобы к модифицирован­ной версии можно было применить результаты анализа исходной версии ал­горитма. В отношении алгоритма Crypton эксперты посчитали изменения

значительными, поскольку они затрагивали как таблицы замен, так и про­цедуру расширения ключа. Поэтому версия 1.0 не была принята в качестве замены версии 0.5.

На самом деле упомянутые здесь недостатки алгоритма Crypton v0.5 не были существенными, как признали эксперты института NIST (Институт стандар­тов и технологий США — организатор конкурса AES). При этом список дос­тоинств алгоритма оказался весьма внушительным [284]:

□ достаточно высокая скорость на всех целевых платформах;

□ небольшие требования к оперативной памяти и возможность расширения ключа «на лету» позволяют использовать алгоритм в смарт-картах с ми­нимальными ресурсами;

□ алгоритм не подвержен атакам по времени выполнения и потребляемой мощности;

□ быстрое расширение ключа;

□ возможность распараллеливания операций в процессе шифрования;

□ алгоритм поддерживает дополнительные размеры ключей (помимо уста­новленных конкурсом обязательных размеров: 128, 192 и 256 битов).

Признавая отсутствие у алгоритма Crypton существенных недостатков и на­личие явных достоинств, эксперты NIST все же не пропустили Crypton во второй раунд конкурса. Причиной тому было наличие двух алгоритмов со схожими характеристиками: Rijndael (будущий победитель конкурса) и Twofish, каждый из которых быстрее алгоритма Crypton на целевых плат­формах. Кроме того, проблем, аналогичных слабым ключам алгоритма Crypton, у Rijndael и Twofish не оказалось. Поэтому эксперты логично пред­положили, что при подведении итогов конкурса AES Crypton проиграет од­ному из этих алгоритмов, и исключили его из рассмотрения во втором раунде конкурса.

есть ли скидки студентам на ж д билеты

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

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100