Патенты

Khafre

Khufu

KHUFU и KHAFRE

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

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

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

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

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

5. Все быстрые реализации DES заранее рассчитывают ключи для каждого этапа. При данном условии нет смысла усложнять эти вычисления.

6. В отличие от DES критерии проектирования S-блоков должны быть общедоступны.

К этому перечню Меркл, возможно, теперь добавил бы "устойчивость к дифференциальному и линейному криптоанализу", ведь в то время эти способы вскрытия не были известны.

Khufu - это 64-битовый блочный шифр. 64-битовый открытый тест сначала разбивается на две 32-битовые половины, L и R. Над обеими половинами и определенными частями ключа выполняется операция XOR. Затем, аналогично DES, результаты проходят через некоторую последовательность этапов. На каждом этапе младший значащий байт L используется в качестве входных данных S-блока. У каждого S-блока 8 входных битов и 32 выходных бита. Далее выбранный в S-блоке 32-битовый элемент подвергается операции XOR с R. Затем L цик­лически сдвигается не несколько из восьми битов, L и R меняются местами, и этап заканчивается. Сам S-блок не является статическим, но меняется каждые восемь этапов. Наконец после последнего этапа над L и R выпол­няется операция XOR с другими частями ключа, и половины объединяются, образуя блок шифротекста.

Хотя части ключа используются для XOR с блоком шифрования в начале и в конце алгоритма, главная цель ключа -генерация S-блоков. Эти S-блоки - секретны, по сути являются они являются частью ключа. Полный размер ключа Khufu равен 512 битам (64 байтам), алгоритм предоставляет способ генерации S-блоков по кл то­чу. Количество этапов алгоритма остается открытым. Меркл упомянул, что 8-этапный Khufu чувствителен к вскрытию с выбранным открытым текстом и рекомендует 16, 24 или 32 этапа [1071]. (Он ограничивает выбор количества этапов числами, кратными восьми.)

Так как в Khufu используются зависимые от ключа и секретные S-блоки, он устойчив к дифференциальному криптоанализу. Существует дифференциальное вскрытие 16-этапного Khufu, которое раскрывает ключ после 2 ³¹ выбранных открытых текстов [611], но его не удалось расширить на большее количество этапов. Если лучшим способом вскрыть Khufu является грубая сила, то его надежность производит сильное впечатление. 512-битовый ключ обеспечивает сложность 2⁵¹² - огромное число при любых условиях.

Khafre - это вторая из криптосистем, предложенных Мерклом [1071]. (Khufu (Хуфу) и Khafre (Хафр) - это имена египетских фараонов.) По конструкции этот алгоритм похож на Khufu, но он спроектирован для прил о-жений, не использующих предварительных вычислений. S-блоки не зависят от ключа. Вместо этого Khafre и с-пользует фиксированные S-блоки. Блок шифрования подвергается операции XOR с ключом не только перед первым этапом и после последнего, но и после каждых 8 этапов шифрования.

Меркл предположил, что с Khafre должны использоваться 64- или 128-битовые ключи, и что для Khafre п о-требуется больше этапов, чем для Khufu. Это наряду с тем, что каждый этап Khafre сложнее этапа Khufu, делает Khafre более медленным. Зато для Khafre не нужны никакие предварительны расчеты, что позволяет быстрее шифровать небольшие порции данных.

В 1990 году Бихам и Шамир применили свой метод дифференциального анализа против Khafre [170]. Им удалось взломать 16-этапный Khafre с помощью вскрытия с выбранным открытым текстом после 1500 разли ч-ных шифрований. На их персональном компьютере это заняло около часа. Преобразование этого вскрытия во вскрытие с известным открытым текстом потребует около 238 шифрований. Khafre с 24 этапами может быть вскрыт с помощью вскрытия с выбранным открытым текстом за 253 шифрования, а с помощью вскрытия с и з-вестным открытым текстом - за 259 шифрования.

И Khufu, и Khafre запатентованы [1072]. Исходный код этих алгоритмов содержится в патенте. При желании получить лицензию на любой или оба алгоритма следует обратиться к директору по лицензированию корпор а-ции Xerox (Director of Licensing, Xerox Corporation, P.O. Box 1600, Stamford, CT, 06904-1600).

13.8 RC2

RC2 представляет собой алгоритм с переменной длиной ключа, спроектированный Роном Ривестом (Ron Rivest) для RSA Data Security, Inc. (RSADSI). Очевидно "RC" - это сокращенное "Ron's Code" ("Код Рона"), хотя официально это "Rivest Cipher" ("Шифр Ривеста"). (RC3 был взломан в RSADSI в процессе разработки, RC1 не вышел за пределы записной книжки Ривеста.) Он представляет собой частную собственность, и его детали не были опубликованы. Не думайте ни минуты, что это увеличивает его безопасность. RC2 уже появился в ко м-мерческих продуктах. Насколько мне известно, RC2 не был запатентован и защищен только как торговый се к-рет.

RC2 - это шифр с 64-битовым блоком и переменной длиной ключа, предназначенный заменить DES. В соо т-ветствии с утверждениями компании программные реализации RC2 в три раза быстрее DES. Алгоритм может использовать ключ переменной длины, от 0 байтов до максимальной длины строки, поддерживаемой компь ю-терной системой, скорость шифрования не зависит от размера ключа. Этот ключ предварительно используется для заполнения 128-байтовой таблицы, зависящей от ключа. Поэтому множество действительно различных ключей составляет 21024. RC2 не использует S-блоков [805], используются две операции - "смешивание" и "перемешивание" ("mix" и "mash"), для каждого этапа выбирается одна из них. В соответствии с литературой [1334]:

... RC2 не является итеративным блочным шифром. Это предполагает, что RC2 более устойчив к дифференциальному и линейному криптоанализу, чем другие блочные шифры, безопасность которых опирается на копирование схемы DES.

Отказ RSADSI опубликовать RC2 заставляет сомневаться в намерениях этой компании. Она обещает пр е-доставить детали алгоритма всем, кто подпишет соглашение о нераспространении информации, и утверждает, что позволит криптоаналитикам опубликовать любые обнаруженные негативные результаты. Мне неизвестно ни об одном криптоаналитике, не работающем в этой компании, кто бы исследовал алгоритм, так как это по сути означало бы выполнить работу по анализу для компании.

Тем не менее, Рон Ривест - не шарлатан. Он уважаемый и компетентный криптограф. Я лично в значител ь-ной степени верю в этот алгоритм, хотя я лично и не видел кода. RC4, также являющийся интеллектуальной собственностью RSADSI, был опубликован в Internet (см. раздел 17.1), и, вероятно, опубликование RC2 являе т-ся только вопросом времени.

По соглашению между Ассоциацией издателей программного обеспечения (Software Publishers Association, SPA) и правительством США RC2 и RC4 (см. раздел 17.1) получили специальный экспортный статус (см. ра з-дел 25.14). Процесс получения разрешения на экспорт продуктов, реализующих один из этих двух алгоритмов, значительно упрощен при условии, что длина ключа не превышает 40 битов.

Достаточен ли 40-битовый ключ? Существует всего один триллион возможных ключей. При условии, что наиболее эффективным методом криптоанализа является вскрытие грубой силой (большое допущение, ведь а л-горитм никогда не был опубликован), и что микросхема грубого вскрытия может проверить миллион ключей в секунду, поиск правильного ключа займет 12.7 дней. Тысяча машин, работающих параллельно, смогут ра с-крыть ключ за двадцать минут.

RSA Data Security, Inc., утверждает, что, хотя шифрование и дешифрирования выполняются для быстро, и с-черпывающего поиска потребуется намного больше времени. Заметное количество времени тратится на форм и-рование плана использования ключа. Хотя это время пренебрежимо мало при шифровании и дешифрировании сообщений, это не так при проверке каждого возможного ключа.

Правительство США никогда не позволило бы экспортировать любой алгоритм, который оно, по крайней мере в теории, не смогло бы вскрыть. Оно может создать магнитную ленту или CD с конкретным блоком о т-крытого текста, зашифрованным каждым возможным ключом. Для вскрытия сообщения остается только вст а-вить ленту и сравнить блоки шифротекста в сообщении с блоками шифротекста на ленте. При совпадении мо ж-но проверить возможный ключ и посмотреть, имеет ли сообщение какой-нибудь смысл. Если они выберут часто встречающийся блок (все нули, ASCII-символы пробела, и т.д.), этот метод будет работать. Объем данных, нужный для хранения результатов шифрования 64-битового блока открытого текста всеми 10 ^п возможными ключами, составляет 8 терабайтов - вполне реально. По поводу лицензирования RC2 обращайтесь в RSADSI (см. раздел 25.4).

Дата добавления: 2014-11-29