Алгоритмы Twofish и Twofish-FK

Алгоритм Twofish разработан коллективом известных криптологов под руководством Брюса Шнайера — автора множества работ в области криптологии (в т. ч. известнейшей книги [28]), разработчика известного алгоритма шифрования Blowfish (см. разд. 3.8) и основателя американской компании Counterpane Systems (http://www.counterpane.com), являющейся одним из мировых лидеров в области разработки средств криптографической защиты информации. Кроме него, в разработке алгоритма принимали участие Джон Келси, Крис Холл и Нильс Фергюсон из той же компании Counterpane Systems, а также Дуг Уайтинг (Doug Whiting) из Hifn Incorporated (разработка аппаратных средств защиты интернет-коммуникаций, http://www.hifn.com) и Дэвид Вагнер из Университета Беркли (http://www.berkeley.edu).

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

Алгоритм Twofish разбивает шифруемые данные на четыре 32-битных субблока (обозначим их Л, 5, С, D), над которыми производится 16 раундов преобразований, в каждом из которых выполняются следующие операции (рис. 3.216) [347]:

1.    Содержимое субблока В циклически сдвигается влево на 8 битов.

2.    Субблок А обрабатывается операцией #(), которая будет подробно описана далее.

3.       Субблок В также обрабатывается операцией g().

49

4.       Субблок В накладывается на Л с помощью сложения по модулю 2 , после чего аналогичным образом выполняется наложение субблока А на субблок В.

5.       Фрагмент расширенного ключа K2r+g (где г— номер текущего раунда, начиная с 0) складывается с субблоком А по модулю 232 .

6.       Аналогично предыдущему шагу, К+9 накладывается на субблок В.

7.       Субблок А накладывается на С операцией XOR.

8.       Содержимое субблока D циклически сдвигается влево на 1 бит.

9.       Субблок В накладывается на D операцией XOR.

10.     Содержимое субблока С циклически сдвигается вправо на 1 бит.

Описанные выше действия можно представить следующим образом:

Операция g() обрабатывает 32-битный входной субблок выполнением следующих шагов (рис. 3.217):

1.    Субблок делится на 4 фрагмента по 8 битов каждый.

2.    Фрагменты «прогоняются» через таблицы замен 8×8 битов S0…S3. Таблицы замен вычисляются динамически и зависят от ключа шифрования; алгоритм построения таблиц замен будет подробно описан далее.

где ?о—?з — байты выходного значения функции g().

3.    Результат замен (обозначим его s0…s3) умножается на фиксированную матрицу Мх:

Умножение выполняется в конечном поле GF( 2 ) с образующим полиномом

Матрица Мх приведена в табл. 3.136 (здесь и далее в таблицах указаны шестнадцатеричные значения).

Таблица 3.136

01

EF

EF

EF

01

EF

01

EF

EF

01

EF

В конце каждого раунда, за исключением последнего, субблоки А (значение до описанной выше обработки) и С меняются местами; субблоки В (значение до обработки) и D также меняются местами.

Перед первым раундом выполняется входное отбеливание — наложение операцией XOR на обрабатываемые субблоки четырех фрагментов расширенного ключа К0…К3. Аналогично выполняется выходное отбеливание— после заключительного раунда с использованием подключей К4…К7 .

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

Процедура расширения ключа формирует 40 32-битных подключей для использования в 16 раундах алгоритма и для выполнения операций отбеливания. Кроме того, на основе ключа шифрования вычисляются таблицы замен S0…S3.

Как и Serpent (см. разд. 3.48), алгоритм Twofish использует ключи шифрования любого размера до 256 битов включительно. Однако дополнение ключа выполняется несколько иначе: исходный ключ, при необходимости, дополняется нулевыми битами до ближайшего стандартного размера, т. е. до 128, 192 или 256 битов. Процедура расширения ключа обрабатывает дополненный таким образом ключ.

Сначала производится предварительная обработка ключа, включающая в себя следующие шаги:

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

где N— размер дополненного ключа шифрования в битах, т.е. к принимает значение 2, 3 или 4. Ключ шифрования представляется в виде

8к байтов m0.-.mU-\ или в виде ^к 32-битных слов, обозначаемых как М Q…M 2к-\ •

2. Формируются 3 массива, каждый из которых состоит из к 32-битных слов:

где:

Матрица М2 приведена в табл. 3.137.

Таблица 3.137

01

А4

55

87

58

DB

А4

56

82

F3

С6

68

Е5

02

А1

FC

С1

47

АЕ

3D

19

А4

55

87

58

DB

03

Генерация подключей к0…к39 производится на основе вычисленных на предварительном этапе массивов Ме и Ма следующим образом:

где / = 0…19,а At и Bi —промежуточные величины, вычисляемые так:

Рис. 3.218. Функция h алгоритма Twofish

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

Эта функция схематично представлена на рис. 3.218. Она выполняется в несколько шагов, состав которых зависит от размера дополненного ключа в 64- битных фрагментах, т. е. от описанного выше значения к. В качестве параметров функция h() принимает 32-битное слово и массив 32-битных слов

размерностью к. Последовательность выполнения такова:

Шаг 1. Входное слово делится на 4 8-битных фрагмента, которые «прогоняются» через специфические операции замены q0 и qx (как показано на рис. 3.218). Результат замены объединяется в 32-битное слово, которое складывается с третьим словом входного массива (на рис. 3.218 в качестве входного массива показан массив Ме). Данный шаг не выполняется, если к <4 (т. е. к = 2 или к = 3). На рис. 3.218 показаны все возможные шаги функции h().

Шаг 2. Результат предыдущего шага или входное слово обрабатывается аналогичным образом (с другой последовательностью применения q0 и qx, которая различна для каждого шага— см. рис. 3.218), но складывается со вторым словом входного массива. Шаг 2 не выполняется, если к- 2.

Шаги 3 и 4. Выполняются всегда и включают в себя обработку результата предыдущего шага (или входного слова — для шага 3 и к = 2), аналогичную предыдущим шагам с использованием, соответственно, первого и нулевого слов входного массива.

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

где:

•                  Уо—Уз — байты результата выполнения замен на шаге 5;

•                матрица Мх была описана выше;

•                Н — выходное значение функции h().

Операции q0 и qx представляют собой не табличные замены 8×8 битов, а вычисляют выходные значения с использованием нескольких таблиц замен 4×4 следующим образом:

где:

?      х — входное значение;

?      у — выходное значение;

?      »>4 — операция циклического вращения вправо 4-битных величин, т. е. раздельное вращение каждого нибла обрабатываемого байта;

?      t{ — табличные замены, различные для q0 и qx; f, для q0 представлена в табл. 3.138.

Таблица 3.138

‘о

8

1

7

D

6

F

3

2

0

В

5

9

Е

С

А

4

‘1

Е

С

В

8

1

2

3

5

F

4

А

6

7

0

9

D

h

В

А

5

Е

6

D

9

0

С

8

F

3

2

4

7

1

h

D

7

F

4

1

2

6

Е

9

В

3

0

8

5

С

А

Выходное значение таблицы берется из позиции, соответствующей входному значению; например, tx заменяет 0 на Е, 1 на С и т. д.

Таблицы для qx приведены в табл. 3.139.

Таблица 3.139

‘о

2

8

В

D

F

7

6

Е

3

1

9

4

0

А

С

5

‘l

1

Е

2

В

4

С

3

7

6

D

А

5

F

9

0

8

h

4

С

7

5

1

6

9

А

0

Е

D

8

2

В

3

F

h

В

9

5

1

С

3

D

Е

6

4

7

F

2

0

8

А

Осталось описать зависимость от ключа таблиц замен S0…S3. Фактически в алгоритме шифрования вместо описанной выше функции g() применяется функция й(), использующая в качестве входного значения 32-битный субблок А или 5, а в качестве входного массива— описанный ранее массив V. Таким образом, замена выполняется на основе тех же таблиц г0…г3, которые используются в процедуре расширения ключа.

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

?      доступный объем энергонезависимой и оперативной памяти;

?      предполагаемую частоту смены ключа при шифровании данных;

?      требования к скорости шифрования блоков данных.

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

Алгоритм Twofish-FK

Помимо описанного выше «стандартного» варианта алгоритма Twofish, авторы предложили еще и Twofish Family Key (или Twofish-FK) — шаблон для формирования на основе Twofish вариантов алгоритма, несовместимых между собой [347] и предназначенных, таким образом, для ограниченных применений, например, в рамках конкретных организаций для защиты внутреннего документооборота.

Несовместимость вариантов достигается путем применения дополнительного ключа (FK), одинакового для всех субъектов, использующих конкретный вариант алгоритма Twofish-FK. То есть конкретное значение используемого FK формирует некий «контур совместимости» криптосредств, реализующих Twofish-FK.

Дополнительный ключ FK «подмешивается» на этапе расширения ключа следующим образом:

1. Инициализируются переменные, используемые в дальнейших операциях (этот шаг выполняется однократно для конкретного FK)\

где:

•                   Efk{N) — результат зашифровывания алгоритмом Twofish на ключе FK 128-битного блока, первый байт которого содержит значение N, а остальные байты обнулены;

•                  • — операция конкатенации.

Стоит отметить, что переменные Т0 и Тх имеют размерность 256 битов,

Т2 и Т3 — по 128 битов, а Г4 — 64 бита.

2. Наложение ключа FK выполняется однократно для каждого ключа шифрования, используемого совместно с данным FK.

•                 Перед выполнением процедуры расширения ключа шифрования производится наложение Т0 на ключ шифрования операцией XOR. Если ключ шифрования имеет размер, меньший 256 битов, то используется необходимое количество битов Т0.

•                 После выполнения процедуры расширения ключа операциями XOR Т2 накладывается на подключи К0…К3, Тъ— на подключи ЛГ4…АГ7, а ТА — на каждую пару подключей, используемых в раундах шифрования.

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

Криптостойкость алгоритмов, построенных на основе Twofish-FK, по словам авторов алгоритма, полностью эквивалентна криптостойкости стандартного Twofish, поскольку подобное наложение дополнительного ключа никак не влияет на основные параметры алгоритма [347].

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

Сравнительный анализ достоинств и недостатков алгоритмов — финалистов конкурса AES приведен в разд. 2.1.

 

Вы можете следить за любыми ответами на эту запись через 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