32 бита

8 битов

8 битов

8 битов

8 битов

S-блок 1

З-блок 2

S-блок 3

З-блок 4

i 32 бита

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

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

Разделить xL на четыре 8-битовых части: a, b, c и d F(Xi) = ((S1,a + S2,b mod 232) e S3,c)+ 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-блока идентичны. До выполнения развертывания ключа невозможно определить, является ли он слабым. Если вы беспокоитесь об этом, вам придется выполнить ра з-

вертывание ключа и проверить, нет ли в S-одинаковых элементов. Хотя я не думаю, что это так уж необходимо.

Мне неизвестно об успешном криптоанализе Blowfish. Для безопасности не реализуйте Blowfish с умен ь-шенным числом этапов.

Kent Marsh Ltd. встроила Blowfish в свой продукт обеспечения безопасности FolderBolt, предназначенный для Microsoft Windows и Macintosh. Алгоритм также входит в Nautilus и PGPfone.

14.4 SAFER

SAFER K-64 означает Secure And Fast Encryption Routine with a Key of 64 bits - Безопасная и быстрая проц е-дура шифрования с 64-битовым ключом [1009]. Этот не являющийся частной собственностью алгоритм, разр а-ботанный Джеймсом Массеем (James Massey) для Cylink Corp., используется в некоторых из продуктов этой компании. Правительство Сингапура собирается использовать этот алгоритм - с 128-битовым ключом [1010] -для широкого спектра приложений. Его использование не ограничено патентом, авторскими правами или др у-гими ограничениями.

Алгоритм работает с 64-битовым блоком и 64-битовым ключом. В отличие от DES он является не сетью Фейстела (см. раздел 14.10), а итеративным блочным шифром: для некоторого количества этапов применяется одна и та же функция. На каждом этапе используются два 64-битовых подключа. Алгоритм оперирует только байтами.

Описание SAFER K-64

Блок открытого текста делится на восемь байтовых подблоков: В1, В2, . . . , В7, В8. Затем подблоки обрабатываются в ходе r этапов. Наконец подблоки подвергаются заключительному преобразованию. На каждом этапе используется два подключа: K2r-1 и K2r.

На Рис. 14-4 показан один этап SAFER K-64. Сначала над подблоками выполняется либо операция XOR, л ибо сложени с байтами подключа K2r-1. Затем восемь подблоков подвергаются одному из двух нелинейных пр е-образований:

y = 45x mod 257. (Если x = 0, то y = 0.)

y = log45 x. (Если x = 0, то y = 0.)

Вход этапа (8 байтов) 1 2 3 4 5 6 7 8

45()

log45

log45

45()

45()

log45

xor add add xor xor add add xor

log45

45()

1 2 3 4 5 6 7 8

Выход этапа (8 байтов)

Рис. 14-4. Один этап SAFER.

Это операции в конечном поле GF(257), а 45 - элемент поля, являющийся примитивом. В реализациях SAFER K-64 быстрее выполнять поиск в таблице, чем все время рассчитывать новые результаты.

Затем подблоки либо подвергаются XOR, либо складываются с байтами подключа K2r. Результат этого действия проходит через три уровня линейных операций, целью которых является увеличение лавинного эффекта. Каждая операция называется псевдоадамаровым преобразованием (Pseudo-Hadamard Transform, PHT). Если на входе PHT a1 и a2, то на выходе:

b1 = (2a1 + a2) mod 256

b2 = (a1 + a2) mod 256

После r этапов выполняется заключительное преобразование. 0но совпадает с преобразованием, являющи м-ся первым действием каждого этапа. Над В1, В4, В5 и В8 выполняется XOR с соответствующими байтами последнего подключа, а В2, В3, В6 и В7 складываются с соответствующими байтами последнего подключа. В р е-зультате и получается шифротекст.

Дешифрирование представляет собой обратный процесс: сначала заключительное преобразование (с выч и-танием вместо сложения), затем r инвертированных этапов. 0братное PHT (Inverse PHT, IPHT) - это:

a1 = (b1 - b2) mod 256

a2 = (-b1 + 2b2) mod 256

Массей рекомендует использовать 6 этапов, но для большей безопасности количество этапов можно увел и-чить.

Генерировать подключи совсем не трудно. Первый подключ, K1, - это просто ключ пользователя. Последующие ключи генерируются в соответствии со следующей процедурой:

= (Ki «<3i) + Ci

Символ "<<<" обозначает циклический сдвиг налево. Сдвиг выполняется побайтно, а ci является константой этапа. Если с,, - это у-ый байт константы i-го этапа, то можно рассчитать все константы этапов по следующей