Этап 2: k3, k4 Этап 3: k5, k6 Этап 4: k7, k8 Этап 5: k4, k3 Этап 6: k2, k1 Этап 7: k8, k7 Этап 8: k6, k5

Сила этого алгоритма заключена в его S-блоках. У CAST нет фиксированных S-блоков, для каждого прил о-жения они конструируются заново. Критерии проектирования описаны в [10], изогнутыми функциями являются столбцы S-блоков, обеспечивающие необходимые свойства S-блоков (см. раздел 14.10). Созданный для данной реализации CAST S-блоков уже больше никогда не меняется. S-блоки зависят от реализации, а не от ключа.

В [10] было показано, что CAST устойчив к дифференциальному криптоанализу, а в [728] - что CAST усто й-чив и к линейному криптоанализу. Неизвестно иного, чем грубая сила, способа вскрыть CAST.

Northern Telecom использует CAST в своем пакете программ Entrust для компьютеров Macintosh, PC и р а-бочих станций UNIX. Выбранные ими S-блоки не опубликованы. Канадское правительство считает CAST н о-вым стандартом шифрования. Патентная заявка на CAST находится в процессе рассмотрения.

14.3 BLOWFISH

Blowfish - это алгоритм, разработанный лично мной для реализации на больших микропроцессорах [1388, 1389]. Алгоритм незапатентован, и его код на языке C приведен в конце этой книги для широкого пользования. При проектировании Blowfish я использовал следующие критерии:

1.Скорость. Blowfish шифрует данные на 32-битовых микропроцессорах со скоростью 26 тактов на байт.

2.Компактность. Blowfish может работать менее, чем в 5 Кбайт памяти.

3.Простота. Blowfish использует только простые операции: сложение, XOR и выборка из таблицы по 32-битовому операнду. Анализ его схемы несложен, что делает при реализации алгоритма уменьшает к о-личество ошибок [1391].

4.Настраиваемая безопасность. Длина ключа Blowfish переменна и может достигать 448 битов.

Blowfish оптимизирован для тех приложений, в которых нет частой смены ключей, таких как линии связи или программа автоматического шифрования файлов. При реализации на 32-битовых микропроцессорах с большим кэшем данных, таких как Pentium и PowerPC, Blowfish заметно быстрее DES. Blowfish не подходит для использования в приложениях с частой сменой ключей, например, при коммутации пакетов, или для и с-пользования в качестве однонаправленной хэш-функции. Большие требования к памяти делают невозможным использование этого алгоритма в интеллектуальных платах.

Описание Blowfish

Blowfish представляет собой 64-битовый блочный шифр с ключом переменной длины. Алгоритм состоит из двух частей: развертывание ключа и шифрование данных. Развертывание ключа преобразует ключ длиной до 448 битов в несколько массивов подключей, общим объемом 4168 байтов.

Шифрование данных состоит из простой функции, последовательно выполняемой 16 раз. Каждый этап с о-стоит из зависимой от ключа перестановки и зависимой от ключа и данных подстановки. Используются только сложения и XOR 32-битовых слов. Единственными дополнительными операциями на каждом этапе являются четыре извлечения данных из индексированного массива.

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

P-массив состоит из 18 32-битовых подключей:

P1, P2, . . P18

Каждый из четырех 32-битовых S-блоков содержит 256 элементов:

S1,b . . v S1,255 . . v S2,255

53,0, 5*3,3, • • •, 5*3,255 5*4,0, £4,4, • • •, 5*4,255

Точный метод, используемый при вычислении этих подключей описан в этом разделе ниже

32 бита

32 бита

P2-«ф

32 бита

Рис. 14-2. Blowfish.

Blowfish является сетью Фейстела (Feistel) (см раздел 14Л0), состоящей из 16 этапов На вход подается 64-битовый элемент данных x Для шифрования:

Разбейте x на две 32-битовых половины: xL, xR

Для i = 1 по 16:

xL = xL © P18 Xr = F(Xl) © xR

Переставить xL и xR (кроме последнего этапа)

Xr = Xr © P17 Xl = Xl © P18

Объединить xL и xR

8 битов

32 бита

S-блок 1

8 битов

8 битов

S-блок 3

8 битов

I 32 бита -►

Рис. 14-3. Функция F.

Функция F представляет собой следующее (см. Рис. 14-3):

Разделить xL на четыре 8-битовых части: a, b, c и d F(xl) = ((S1>e + mod 232) © &>с)+ S4,d mod 232

Дешифрирование выполняется точно также, как и шифрование, но P1, P2, . . P18 используются в обратном порядке.

В реализациях Blowfish, для которых требуется очень большая скорость, цикл должен быть развернут, а все ключи должны храниться в кэше. Подробности приведены в [568].

Подключи рассчитываются с помощью специального алгоритма. Вот какова точная последовательность де й-ствий.

(1)Сначала P-массив, а затем четыре S-блока по порядку инициализируются фиксированной строкой. Эта строка состоит из шестнадцатиричных цифр п.

(2)Выполняется XOR P1 с первыми 32 битами ключа, XOR P2 со вторыми 32 битами ключа, и так далее для всех битов ключа (до P18). Используется циклически, пока для всего P-массива не будет выполнена опер а-ция XOR с битами ключа.

(3)Используя подключи, полученные на этапах (1) и (2), алгоритмом Blowfish шифруется строка из одних нулей.

(4)P1 и P2 заменяются результатом этапа (3).

(5)Результат этапа (3) шифруется с помощью алгоритма Blowfish и измененных подключей.

(6)P3 и P4 заменяются результатом этапа (5).

(7)Далее в ходе процесса все элементы P-массива и затем по порядку все четыре S-блока заменяются вых о-дом постоянно меняющегося алгоритма Blowfish.

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

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

Серж Воденэ (Serge Vaudenay) исследовал Blowfish с известными S-блоками и r этапами, дифференциал ь-ный криптоанализ может раскрыть P-массив с помощью 2 8r+1 выбранных открытых текстов [1568]. Для некоторых слабых ключей, которые генерируют плохие S-блоки (вероятность выбора такого ключа составляет 1 к 2 14), это же вскрытие раскрывает P-массив с помощью всего 24r+1. При неизвестных S-блоках это вскрытие может обнаружить использование слабого ключа, но не может определит сам ключ (ни S-блоки, ни P-массив). Это вскрытие эффективно только против вариантов с уменьшенным числом этапов и совершенно бесполезно против 16-этапного Blowfish.

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