54

Преобразование g определяется через функцию h следующим образом: g( X ) = h( X , S) ,

то есть S-box, используемые в функции g , обеспечивают преобразование из xi в yi с помощью

функции h , для которой L = S , полученному из исходного ключа в соответствии со схемой генерации ключа, описанной ранее. Таким образом, для генерации ключа и для преобразования информационных блоков используется одна и та же функция h , с той лишь разницей, что в функции генерации ключей вторым аргументом являются элементы исходного ключа K , а в функции преобразования информационных блоков — векторы, полученные из исходного ключа с помощью порождающей матрицы кода Рида-Соломона.

Функция генерации ключей K j

Ключи K j генерируются, используя функцию h :

K2i = ( Ai + Bi ) mod 232 ,

K2i+1 = ЦСЛ(( Ai + 2Bi ) mod 232 , 9),

где

Ai = h(2iρ, Mч),

Bi = ЦСЛ(h((2i +1)ρ, Mн),8),

ρ = 224 + 216 + 28 + 20.

Константа ρ используется для создания вектора из четырех повторяющихся байт для всех i = 0, …, 255 .

Преобразования q0 , q1

Эти преобразования обеспечивают трансформацию компонент 8-битного вектора. Каждое из преобразований строится по четырем различным 4-битным подстановочным функциям t0 , t1 , t2 , t3 . Из исходного 8-битного вектора x результирующий вектор y получается следующим образом:

a0 , b0 = x /16 , x mod16; a1 = a0 b0 ;

b1 = a0 ЦСП(b0 ,1) 8a0 mod16; a2 , b2 = t0[a1 ], t1[b1 ];

a3 = a2 b2 ;

b3 = a2 ЦСП(b2 ,1) 8a2 mod16; a4 , b4 = t2 [a3 ], t3[b3 ];

y =16b4 + a4 .

Для преобразования q0 4-битные подстановки (S-box) задаются следующими векторами: t0 =[817 D6 F320 B59 E C A 4] ,

t1 =[EC B81235F4 A 6709 D] , t2 =[BA5E6 D90C8F32471], t3 =[D7 F4126 E 9 B3085C A] ,

где вектора t0 , t1 , t2 , t3 состоят из значений выходных полубайтов, при этом значение входного полубайта указывает порядковый номер (от 0 до 15) выходного полубайта.

55

Аналогично для преобразования q1 : t0 =[28 BD F76 E 319 40 A C5] , t1 =[1E 2 B4C376 D A5F908] , t2 =[4C75169 A 0 E D82 B3F], t3 =[B951C3D E 647 F208A] .

На Рис. 4.11 более подробно представлена схема работы одного цикла функции F для случая, когда длина ключа равна 128 бит.

Рис.4.11. Один цикл функции F (ключ 128 бит)

56

Примечание

Ниже приведено краткое обоснование выбора конкретных значений МДР-матрицы кода РидаСоломона и подстановочных преобразований q0 , q1 .

МДР-матрицы, используемые в алгоритме Twofish, обладают следующими свойствами:

1.Сумма числа байтов, измененных в исходном 4-байтовом векторе, и числа байтов, изменившихся в 4-байтовом векторе результата, должна быть не менее 5. Иными словами, любое изменение в каком либо байте в исходном векторе должно повлечь изменение значения всех четырех байт в векторе результата, любые изменения в любых двух байтах исходного векто-

ра должны привести к изменениям в, по крайней мере, трех байтах результата, и так далее (этому требованию удовлетворяют более 2127 МДР-матриц размером 4 ×4 байта).

2.Никакая строка (столбец) матрицы не может быть получена циклическим сдвигом другой строки (столбца).

3.Любое изменение любого байта в исходном векторе приводит к изменению по меньшей мере восьми бит в векторе результата.

Валгоритме используется (12,8,5)-код РС с порождающим многочленом

x4 + (α +α−1 )x3 +αx2 + (α +α−1 )x +1,

где α — корень примитивного многочлена w(x) , используемого для задания поля GF(28). Такой

порождающий многочлен был выбран для обеспечения максимальной простоты реализации алгоритма. Кроме того, РС-код с порождающим многочленом 4-й степени имеет расстояние Хэмминга, равное 5, и следовательно, гарантирует, что любые два его слова будут различаться как минимум в пяти символах (байтах).

Преобразования q0 , q1 выбирались методом случайного поиска. Для каждого возможного преобразования q вычислялись две граничные вероятности [Mat96]:

DPmax (q) = max Pr[q( X a) q( X ) = b]

a ≠0,b X

X

LP (q) = max (2 Pr[q( X a = q( X ) b] −1)2
max	a,b≠0	X

X

Учитывались только такие преобразования, у которых DPmax ≤10 / 256 и LPmax ≤1/16 . Такому критерию удовлетворяло лишь 0,2 процента всех возможных 4-битных перестановок. Преобразования q0 , q1 , выбранные для алгоритма, имеют DPmax =10 / 256 и LPmax =1/16 .