2.75 Мбит/с. Вуд оценил, что конвейеризированная реализация на СБИС с 64 битовой шиной данных могла бы шифровать данные со скоростью свыше 1.28 Гбит/с при тактовой частоте 20 МГц.

REDOC III не безопасен [1440]. 0н чувствителен к дифференциальному криптоанализу. Для восстановления обеих масок нужно всего примерно 223 выбранных открытых текстов.

Патенты и лицензии

0бе версии REDOC запатентованы в Соединенных штатах [1614]. Рассматриваются и иностранные патенты. При заинтересованности в REDOC II или REDOC III обращайтесь к Майклу Вуду (Michael C. Wood, Delta Computec, Inc., 6647 Old Thompson Rd., Syracuse, NY 13211).

13.6 LOKI

LOKI разработан в Австралии и впервые был представлен в 1990 году в качестве возможной альтернативы DES [273]. В нем используются 64-битовый блок и 64-битовый ключ. 0бщая структура алгоритма и использ о-вания ключа описана в [274, 275], а схема S-блоков - в [1247].

Используя дифференциальный криптоанализ, Бихам и Шамир смогли взломать LOKI с 11 и менее этапами быстрее, чем грубой силой [170]. Более того, алгоритм обладает 9-битовой комплиментарностью, что уменьш а-ет сложность вскрытия грубой силой в 256 раз [170, 916, 917].

Ларс Кнудсен (Lars Knudsen) показал, что LOKI с 14 и менее этапами чувствителен к дифференциальному криптоанализу [852, 853]. Кроме того, если в LOKI используются альтернативные S-блоки, получающийся шифр вероятно также будет чувствителен к дифференциальному криптоанализу.

LOKI91

В ответ на эти вскрытия разработчики LOKI вернулись за чертежную доску и пересмотрели свой алгоритм. Результатом было появление LOKI91 [272]. (Предыдущая версия LOKI была переименована в LOKI89.)

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

1. Алгоритм генерации подключей был изменен так, чтобы половины переставлялись не после каждого, а после каждого второго этапа.

2. Алгоритм генерации подключей был изменен так, чтобы количество позиций циклического сдвига л е-вого подключа было равно то 12, то 13 битам.

3. Были устранены начальная и заключительная операции XOR блока и ключа.

4. Б1ла изменена функция S-блока с целью сгладить XOR профили S-блоков (чтобы повысить их усто й-чивость к дифференциальному криптоанализу), и не допустить, чтобы для какого-то значения выпо л-нялось f(x) = 0, где f - это комбинация E-, S- и P-блоков.

Описание LOKI91

Механизм LOKI91 похож на DES (см. Рис. 13-8). Блок данных делится на левую и правую половины и пр о-ходит через 16 этапов, что очень походе на DES. На каждом этапе правая половина сначала подвергается оп е-рации XOR с частью ключа, а затем над ней выполняется перестановка с расширением (см. Табл. 13-1).

Открытый текст

L 32

(>-G>©-(i>e

R 32

Шифротекст

K(2)

JK2L

K(4L

K(i6)

Kr 32

Рис. 13-8. LOKI91.

Табл. 13-1.

Перестановка с расширением

48-битовый результат делится на четыре 12-битовых блока, для каждого из которых выполняется следующая подстановка с использованием S-блока: берется каждый 12-битовый вход, по 2 крайних левых и крайних пр а-вых бита используются для получения номера r, в 8 центральных бит образуют номер c. Результатом S-блока -O - является следующее значение:

O(r,c) = (c + ((r* 17) © 0xff) & 0xff)31 mod Pr

Pr приведено в Табл. 13-2.

Табл. 13-2.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16"

Pr: 375, 279, 391, 395, 397, 415, 419, 425, 433, 445, 451, 463, 471, 477, 487, 488

Затем четыре 8-битовых результата снова объединяются, образуя 32-битовое число, которое подвергается операции перестановки, описанной в Табл. 13-3. Наконец для получения новой левой половины выполняется XOR правой половины с прежней левой половиной, а левая половина становится новой правой половиной. П осле 16 этапов для получения окончательного шифротекста снова выполняется XOR блока и ключа.

Табл. 13-3. Перестановка с помощью P-блока

32, 24, 16, 8, 31, 23, 15, 7, 30, 22, 14, 6, 29, 21, 13, 5, 28, 20, 12, 4, 27, 19, 11, 3, 26, 18, 10, 2, 25, 17, 9, 1

Подключи из ключа выделяются достаточно прямолинейно. 64-битовый ключ разбивается на левую и пр а-вую половины. На каждом этапе подключом является левая половина. Далее она циклически сдвигается влево на 12 или 13 битов, затем после каждых двух этапов левая и правая половины меняются местами. Как и в DES для шифрования и дешифрирования используется один и тот же алгоритм с некоторыми изменениями в испол ь-зовании подключей.

Криптоанализ LOKI91

Кнудсен предпринял попытку криптоанализа LOKI91 [854, 858], но нашел, что этот алгоритм устойчив к дифференциальному криптоанализу. 0днако ему удалось обнаружить, что вскрытие со связанными ключами для выбранных открытых текстов уменьшает сложность вскрытия грубой силой почти вчетверо. Это вскрытие использует слабость использования ключа и может быть также применено, если алгоритм используется в кач е-стве однонаправленной хэш-функции (см. раздел 18.11).

Другое вскрытие со связанными ключами может вскрыть LOKI91 с помощью 2 32 выбранных открытых текстов для выбранных ключей или с помощью 2 48 известных открытых текстов для выбранных ключей [158]. Это вскрытие не зависит от числа этапов алгоритма. (В той же работе Бихам вскрывает LOKI89, используя кри п-тоанализ со связанными ключами, с помощью 2 17 выбранных открытых текстов для выбранных ключей или с помощью 233 известных открытых текстов для выбранных ключей.) Несложно повысить устойчивость LOKI91 к вскрытию такого типа, усложнив схему использования ключа.

Патенты и лицензии

LOKI не запатентован. Кто угодно может реализовать алгоритм и использовать его. Исходный код, прив еденный в этой книге, написан в Университете Нового Южного Уэльса. При желании использовать эту реализ а-цию (или другие реализации, которые на несколько порядков быстрее) в коммерческом продукте обращайтесь к Директору CITRAD, Факультет компьютерных наук, Университетский колледж, Университет Нового Южного Уэльса, Академия австралийских вооруженных сил, Канберра, Австралия (Director CITRAD, Department of Computer Science, University College, UNSW, Australian Defense Force Academy, Canberra ACT 2600, Australia;

FAX: +61 6 268 8581.

13.7 KHUFU и KHAFRE

В 1990 году Ральф Меркл (Ralph Merkle) предложил два алгоритма. В основе их проектирования лежали следующие принципы [1071]:

1. 56-битовый размер ключа DES слишком мал. Так как стоимость увеличения размера ключа прене б-режимо мала (компьютерная память недорога и доступна), он должен быть увеличен.

2. Интенсивное использование перестановок в DES хотя и удобно для аппаратных реализаций, чрезв ы-чайно затрудняет программные реализации. Наиболее быстрые реализации DES выполняют перест а-новки табличным образом. Просмотр таблицы может обеспечить те же характеристики "рассеяния", что и собственно перестановки, и может сделать реализацию намного более гибкой.

3. S-блоки DES, всего с 64 4-битовыми элементами, слишком малы. Теперь с увеличением памяти должны увеличиться и S-блоки. Более того, все восемь S-блоков используются одновременно. Хотя это и удобно для аппаратуры, для программной реализации это кажется ненужным ограничением. Должны быть реализованы больший размер S-блоков и последовательное (а не параллельное) их и с-пользование.

4. Широко признано, что начальная и заключительная перестановки криптографически бессмысленны, поэтому они должны быть устранены.