17.3 WAKE

WAKE - сокращение от Word Auto Key Encryption (Автоматическое шифрование слов ключом)- это алгоритм, придуманный Дэвидом Уилером (David Wheeler) [1589]. Он выдает поток 32-битовых слов, которые с помощью XOR могут быть использованы для получения шифротекста из открытого текста или открытого текста из шифротекста. Это быстрый алгоритм.

WAKE работает в режиме CFB, для генерации следующего слова ключа используется предыдущее слово шифротекста. Алгоритм также использует S-блок из 256 32-битовых значений. Этот S-блок обладает одним особым свойством: Старший байт всех элементов представляет собой перестановку всех возможных байтов, а 3 младших байта случайны.

Сначала по ключу сгенерируем элементы S-блока, Si. Затем проинициализируем четыре регистра с использованием того же или иного ключа: a0, b0, c0 и d0. Для генерации 32-битового слова потока ключей K,-.

K, = d,

Слово шифротекста Ci представляет собой XOR слова открытого текста Pi с K,-. Затем обновим четыре регистра:

a,+i = M(a,,d,)

b,+i = M(bi,a,+i)

c,+i = M(c,A+i)

= M(di,Ci+i)

Функция M представляет собой

M(x,y) = (x + y) >> 8 © S(X + у)л255

Схема алгоритма показана на !5-й. Знак >> обозначает обычный, не циклический сдвиг вправо . Младшие 8 битов x+y являются входом S-блока. Уилер приводит процедуру генерации S-блока, но на самом деле она неполна. Будет работать любой алгоритм генерации случайных байтов и случайной перестановки .

Рис. 17-2. WAKE.

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

17.4 Сдвиговые регистры с обратной связью по переносу

Сдвиговый регистр с обратной связью по переносу, или FCSR (feedback with carry shift register), похож на LFSR. В обоих есть сдвиговый регистр и функция обратной связи, разница в том, что в FCSR есть также регистр переноса (см. !4-й). Вместо выполнения XOR над всеми битами отводной последовательности эти биты скл а-

дываются друг с другом и с содержимым регистра переноса . Результат mod 2 и становится новым битом. Результат, деленный на 2, становится новым содержимым регистра переноса .

Сдвиговый регистр

Сумма mod 2

Выходной бит

Сумма div 2

Рис. 17-3. Сдвиговый регистр с обратной связью по переносу.

На 13-й приведен пример 3-битового FCSR с ответвлениями в первой и второй позициях. Пусть его начальное значение 001, а начальное содержимое регистра переноса равно 0. Выходом будет является крайний правый бит сдвигового регистра.

Сдвиговый регистр

10 1 1 1 0 1 1 1

0 1 0 0 0 1

Регистр переноса

0 0 0 0 0 0

Сумма mod 2

Выходной бит

♦ Сумма Г

Сумма div 2

Рис. 17-4. 3-битовый FCSR.

Заметим, что конечное внутреннее состояние (включая содержимое регистра переноса ) совпадает со вторым внутренним состоянием. С этого момента последовательность циклически повторяется с периодом, равным 10 .

Стоит упомянуть и еще о нескольких моментах . Во первых, регистр переноса является не битом, а числом . Размер регистра переноса должен быть не меньше log2t, где t - это число ответвлений. В предыдущем примере

только три ответвления, поэтому регистр переноса однобитовый . Если бы было четыре ответвления, то регистр переноса состоял бы из двух битов и мог принимать значения 0, i, 2 или 3.

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

В третьих, максимальный период FCSR не 2", где n - длина сдвигового регистра. Максимальный период равен q-i, где q - это целое число связи. Это число задает ответвления и определяется как:

q = 2ql + 22q2 + 23q3 + . . . + 2nqn-i

(Да, qi отсчитываются слева направо.) И даже хуже, q должно быть простым числом, для которого 2 является примитивным корнем. В дальнейшем предполагается, что q удовлетворяет этому условию.

В приведенном примере q = 2*0 + 4*i + 8*i - i == ii. ii - это простое число, примитивным корнем которого является 2. Роэтому максимальный период равен i0.

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

Сдвиговый регистр Регистр переноса

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

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

Для определения, чем закончится конкретное начальное состояние, существует математическая формула, но намного проще проверить это опытным путем. Запустите на некоторое время FCSR. (Если m - это начальный объем памяти, а t - количество ответвлений, то достаточно log2(t) + log2(m) +i тактов.) Если выходной поток вырождается в бесконечную последовательность нулей или единиц за n битов, где n - это длина FCSR, не используйте это начальное состояние. В противном случае его можно использовать . Так как начальное состояние FCSR соответствует ключу потокового шифра, это означает, что ряд ключей генератора на базе FCSR будут слабыми.

В !6-й перечислены все целые числа связи, меньшие i0000, для которых 2 является примитивным корнем . Для всех этих чисел максимальный период равен q-i. Чтобы получить по одному из этих чисел последовател ь-ность ответвлений, рассчитаем бинарный состав q+i. Например, 9949 дает последовательность ответвлений в позициях i, 2, 3, 4, 6, 7, 9, i0 и i3, так как

9950 = 2i3 + 2i0 + 29 + 27 + 26 + 24 + 23 + 22 + 2i

В !5-й перечислены все отводные последовательности из четырех ответвлений, которые дают FCSR максимальной длины для сдвиговых регистров с длиной 32 бита, 64 бита и i28 битов . q, простое число, примитивным корнем которого является 2, получается объединением всех четырех значений , a, b, c и d.

q = 2a + 2b + 2C + 2d - i

Для создания FCSR с периодом q - i можно использовать любую из этих последовательностей .

Идея использовать в криптографии FCSR все еще является очень новой, впервые она была выдвинута Энди Клаппером (Andy Klapper) и Марком Горески (Mark Goresky) [844, 845, 654, 843, 846]. Также, как анализ LFSR основан на сложении примитивных многочленов mod 2, анализ FCSR основан на сложении неких чисел, называемых 2-adic. Соответствующая теория выходит далеко за пределы этой книги, но в мире 2-adic чисел существуют аналоги для всего. Точно также, как определяется линейная сложность, можно определить и 2-adic сложность. Существует 2-adic аналог и для алгоритма Berlekamp-Massey. Это означает, что перечень возможных потоковых шифров по крайней мере удвоился . Все, что можно делать с LFSR, можно делать и с FCSR.

Существуют работы, развивающие эту идею и рассматривающие несколько регистров переноса . Анализ этих генераторов последовательностей основан на сложении разветвленных расширений 2-adic чисел [845, 846].