Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

Название	Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
Дата	29.04.2022
Размер	3.25 Mb.
Формат файла
Имя файла	Shnayer_Prikladnaya-kriptografiya.352928.pdf
Тип	Протокол #504484
страница	29 из 78

1 ... 25 26 27 28 29 30 31 32 ... 78

выбранных открытых текстов [611], но его не удалось расширить на большее количество этапов. Если лучшим способом вскрыть Khufu является грубая сила, то его надежность производит сильное впечатление. 512-битовый ключ обеспечивает сложность 2 512
- огромное число при любых условиях.
Khafre
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.0. 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 12
возможными ключами, составляет 8 терабайтов - вполне реально. По поводу лицензирования RC2 обращайтесь в RSADSI
(см. раздел 25.4).
13.9 IDEA
Первый вариант шифра IDEA, предложенный Ксуеджа Лай (Xuejia Lai) и Джеймсом Масси (James Massey),
появился в 1990 году [929]. Он назывался PES (Proposed Encryption Standard, предложенный стандарт шифр о- вания). В следующем году, после демонстрации Бихамом и Шамиром возможностей дифференциального кри п- тоанализа, авторы усилили свой шифр против такого вскрытия и назвали новый алгоритм IPES (Improved
Proposed Encryption Standard, улучшенный предложенный стандарт шифрования) [931, 924]. В 1992 году назв а- ние IPES было изменено на IDEA (International Data Encryption Algorithm, международный алгоритм шифров а- ния данных) [925].
IDEA основывается на некоторых впечатляющих теоретических положениях и, хотя криптоанализ добился некоторых успехов в отношении вариантов с уменьшенным количеством этапов, алгоритм все еще кажется сильным. По моему мнению это самый лучший и самый безопасный блочный алгоритм, опубликованный сег о- дня.
Будущее IDEA пока неясно. Попыток заменить им DES предпринято не было, частично потому, что он зап а- тентован и должен быть лицензирован для коммерческих приложений, и частично потому, что люди пока все еще ждут, наблюдая насколько хорошо поведет себя алгоритм в предстоящие годы криптоанализа. Его сег о-

дняшняя известность объясняется тем, что он является частью PGP (см. раздел 24.12).
Обзор IDEA
IDEA является блочным шифром, он работает с 64-битовыми блоками открытого текста. Длина ключа - 128
битов. Для шифрования и дешифрирования используется один и тот же алгоритм.
Как и другие, уже рассмотренные блочные шифры IDEA использует и запутывание, и рассеяние. Флософия,
лежащая в основе проекта, представляет собой "объединение операций из различных алгебраических групп".
Смешиваются три алгебраические группы, и все они могут быть легко реализованы как аппаратно, так и пр о- граммно:
— XOR
— Сложение по модулю 2 16
— Умножение по модулю 2 16
+ 1. (Это операцию можно рассматривать как S-блок IDEA.)
Все эти операции (а в алгоритме используются только они, перестановки на битовом уровне не применяю т- ся) работают с 16-битовыми подблоками. Этот алгоритм даже эффективнее на 16-битовых процессорах.
Описание IDEA
Схема IDEA представлена на Рис. 13-9. 64-битовый блок данных делится на четыре 16-битовых подблока:
X
1
, X
2
, X
3
и X
4
. Эти четыре подблока становятся входными данными для первого этапа алгоритма. Всего в алг о- ритме восемь этапов. На каждом этапе четыре подблока подвергаются операциям XOR, сложениям и умнож е- ниям друг с другом и с шестью 16-битовыми подключами. Между этапами обмениваются местами второй и третий подблоки. Наконец четыре подблока объединяются с четырьмя подключами в окончательном преобраз о- вании. На каждом этапе события происходят в следующей последовательности:
(1) Перемножаются X
1
и первый подключ.
(2) Складываются X
2
и второй подключ.
(3) Складываются X
3
и третий подключ.
(4) Перемножаются X
4
и четвертый подключ.
(5) Выполняется XOR над результатами этапов (1) и (3).
(6) Выполняется XOR над результатами этапов (2) и (4).
(7) Перемножаются результаты этапа (5) и пятый подключ.
(8) Складываются результаты этапов (6) и (7).
(9) Перемножаются результаты этапа (8) и шестой подключ.
(10) Складываются результаты этапов (7) и (9).
(11) Выполняется XOR над результатами этапов (1) и (9).
(12) Выполняется XOR над результатами этапов (3) и (9).
(13) Выполняется XOR над результатами этапов (1) и (10).
(14) Выполняется XOR над результатами этапов (4) и (10).

: побитовое "исключающее или" (XOR) 16-битовых подблоков
: сложение по модулю 2 16 16-битовых целых
: умножение по модулю 2 16
+1 16-битовых целых при условии, что нулевой подблок соответствует 2 16
X
i
: 16-битовый подблок открытого текста
Y
i
: 16-битовый подблок шифротекста
Z
i
(r)
: 16-битовый подблок ключа
Выход еще семь этап один этап
X
1
Z
1
(1)
Z
2
(1)
X
2
Z
3
(1)
X
3
X
4
Z
4
(1)
Z
6
(1)
Z
5
(1)
Z
1
(9)
Z
2
(9)
Y
2
Y
1
Z
3
(9)
Z
4
(9)
Y
4
Y
3
Рис. 13-9. IDEA.
Выходом этапа являются четыре подблока - результаты действий (11), (12), (13) и (14). Поменяйте местами два внутренних подблока (но не в последнем этапе), и вы получите исходные данные для следующего этапа.
После восьмого этапа выполняется заключительное преобразование:
(1) Перемножаются X
l и первый подключ.
(2) Складываются X
2
и второй подключ.
(3) Складываются X
3
и третий подключ.
(4) Перемножаются X
4
и четвертый подключ.
Наконец четыре подблока снова соединяются, образуя шифротекст.
Также несложно создавать подключи. Алгоритм использует 52 из них (шесть для каждого из восьми этапов и еще четыре для заключительного преобразования). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это первые восемь подключей алгоритма (шесть для первого этапа и два - для второго). Затем ключ циклически сдвигается налево на 25 битов и снова делится на восемь подключей. Первые четыре используются на этапе 2, а оставшиеся четыре - на этапе 3. Ключ циклически сдвигается налево на 25 битов для получения следующих восьми подключей, и так до конца алгоритма.
Дешифрирование выполняется точно также за исключением того, что подключи инвертируются и слегка и з- меняются. Подключи при дешифрировании представляют собой обратные значения ключей шифрования по отношению к операциям либо сложения, либо умножения. (Для IDEA подблоки, состоящие из одних нулей,
считаются равными 2 16
= -1 для умножения по модулю 2 16
+ 1, следовательно, обратным значением 0 относ и- тельно умножения является 0.) Эти вычисления могут занять некоторое время, но их нужно выполнить один раз для каждого ключа дешифрирования. В Табл. 13-4 представлены подключи шифрования и соответствующие

подключи дешифрирования.
Табл. 13-4.
Подключи шифрования и дешифрирования IDEA
Этап
Подключи шифрования
Подключи дешифрирования
1
Z
1
(1)
Z
2
(1)
Z
3
(1)
Z
4
(1)
Z
5
(1)
Z
6
(1)
Z
1
(9)-1
-Z
2
(9)
-Z
3
(9)
Z
4
(9)-1
Z
5
(8)
Z
6
(8)
2
Z
1
(2)
Z
2
(2)
Z
3
(2)
Z
4
(2)
Z
5
(2)
Z
6
(2)
Z
1
(8)-1
-Z
2
(8)
-Z
3
(8)
Z
4
(8)-1
Z
5
(7)
Z
6
(7)
3
Z
1
(3)
Z
2
(3)
Z
3
(3)
Z
4
(3)
Z
5
(3)
Z
6
(3)
Z
1
(7)-1
-Z
2
(7)
-Z
3
(7)
Z
4
(7)-1
Z
5
(6)
Z
6
(6)
4
Z
1
(4)
Z
2
(4)
Z
3
(4)
Z
4
(4)
Z
5
(4)
Z
6
(4)
Z
1
(6)-1
-Z
2
(6)
-Z
3
(6)
Z
4
(6)-1
Z
5
(5)
Z
6
(5)
5
Z
1
(5)
Z
2
(5)
Z
3
(5)
Z
4
(5)
Z
5
(5)
Z
6
(5)
Z
1
(5)-1
-Z
2
(5)
-Z
3
(5)
Z
4
(5)-1
Z
5
(4)
Z
6
(4)
6
Z
1
(6)
Z
2
(6)
Z
3
(6)
Z
4
(6)
Z
5
(6)
Z
6
(6)
Z
1
(4)-1
-Z
2
(4)
-Z
3
(4)
Z
4
(4)-1
Z
5
(3)
Z
6
(3)
7
Z
1
(7)
Z
2
(7)
Z
3
(7)
Z
4
(7)
Z
5
(7)
Z
6
(7)
Z
1
(3)-1
-Z
2
(3)
-Z
3
(3)
Z
4
(3)-1
Z
5
(2)
Z
6
(2)
8
Z
1
(8)
Z
2
(8)
Z
3
(8)
Z
4
(8)
Z
5
(8)
Z
6
(8)
Z
1
(2)-1
-Z
2
(2)
-Z
3
(2)
Z
4
(2)-1
Z
5
(1)
Z
6
(1)
заключительное преобразование
Z
1
(9)
Z
2
(9)
Z
3
(9)
Z
4
(9)
Z
1
(1)-1
-Z
2
(1)
-Z
3
(1)
Z
4
(1)-1
Скорость IDEA
Современные программные реализации IDEA примерно в два раза быстрее, чем DES. На компьютере с i386/33 МГц IDEA шифрует данные со скоростью 880 Кбит/с, а на компьютере с i486/33 МГц - со скоростью
2400 Кбит/с. Вы могли подумать, что IDEA должен был быть побыстрее, но умножения - недешевое удовольс т- вие. Умножение двух 32-битовых чисел на процессоре i486 занимает 40 тактов (10 на процессоре Pentium).
Реализация PES на базе СБИС шифрует данные со скоростью 55 Мбит/с при тактовой частоте 25 МГц
[208,398]. Другая СБИС, разработанная ETH Zurich и состоящая из of 251000 транзисторов на кристалле пл о- щадью 107.8 мм
2
, шифрует данные с помощью алгоритма IDEA со скоростью 177 Мбит/с при тактовой частоте
25 МГц [926, 207, 397].
Криптоанализ IDEA
Длина ключа IDEA равна 128 битам - более чем в два раза длиннее ключа DES. При условии, что наиболее эффективным является вскрытие грубой силой, для вскрытия ключа потребуется 2 128
(10 38
) шифрований. Соз- дайте микросхему, которая может проверять миллиард ключей в секунду, объедините миллиард таких микр о- схем, и вам потребуется 10 13
лет для решения проблемы - это больше, чем возраст вселенной. 10 24
таких микро- схем могут найти ключ за день, но во вселенной не найдется столько атомов кремния, чтобы построить такую машину. Наконец мы чего-то достигли, хотя в некоторых темных вопросах я лучше останусь сторонним набл ю- дателем.
Может быть вскрытие грубой силой - не лучший способ вскрытия IDEA. Алгоритм все еще слишком нов,
чтобы можно было говорить о каких-то конкретных криптографических результатах. Разработчики сделали все возможное, чтобы сделать алгоритм устойчивым к дифференциальному криптоанализу. Они определили пон я- тие марковского шифра и продемонстрировали, что устойчивость к дифференциальному криптоанализу может быть промоделирована и оценена количественно [931, 925]. (Для сравнения с алгоритмом IDEA, устойчивость которого к дифференциальному криптоанализу была усилена, и который показан на Рис. 13-9, на Рис. 13-10
приведен первоначальный алгоритм PES. Удивительно, как такие незначительные изменения могут привести к столь большим различиям.) В [925] Лай (Lai) утверждал (он привел подтверждение, но не доказательство), что
IDEA устойчив к дифференциальному криптоанализ уже после 4 из 8 этапов. Согласно Бихаму, его попытка вскрыть IDEA с помощью криптоанализа со связанными кл ючами также не увенчалась успехом [160].

1 ... 25 26 27 28 29 30 31 32 ... 78