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

В современных блочных криптосистемах раундовые шифры строятся в основном с использованием операций замены двоичных кодов небольшой разрядности (схемы, реализующие эту нелинейную операцию, называются S-блоками; как правило, именно от их свойств в первую очередь зависит стойкость всей системы), перестановки элементов двоичных кодов, арифметических и логических операций над двоичными кодами.

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

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

Представим шифруемый блок данных (открытого p^~_i или закрытого с_i текста) длиной n (|p^~_i| =(|c_i|= n) в виде пары полублоков в 2 раза меньшего размера p^~_i =с_i, = (L, R), |L| = |R| = n /2.

Выполним зашифрование старшего полублока L (Left) блока p^~_i с помощью младшего R (Right), используя некоторую функцию f_i зависящую от раундового ключа k_t, и обратимую бинарную операцию ° над n/2-битовыми блоками данных. Для подготовки к следующему аналогичному раунду выполним перестановку частей блока p^~_i : L°f_i (R) - R. Таким образом, раундовая функция зашифрования будет иметь вид F_i(p^~_i)= F_t (L, R) = (r, L°f_i (R)) (рис.14), для которой легко построить обратное, или расшифровывающее, преобразование F_i^-1(c):

F_i^-1 (c_i) = F_i^-1 (L, R) = (r, L*f_i (R)),

где * - операция, обратная о. Композиционный шифр, использующий раундовые функции такого вида, называется шифром Фейстеля [16, 17]. В подавляющем большинстве шифров рассматриваемой структуры используется разрядность блока, равная 64 битам, а в качестве операций о и * - поразрядное сложение по модулю 2 (XOR).

a

б

Рис.14. Схема петли Фейстеля:

а - зашифрование; б - расшифрование

Первыми широко известными практическими реализациями итерационного блочного шифра были разработанные X. Фейстелем, Д. Копперсмитом и другими сотрудниками фирмы IBM криптоалгоритмы Lucifer и созданный на его основе в 1974 г. в качестве стандарта шифрования данных в государственных и частных организациях DES (Data Encryption Standard). DES работает с блоками данных разрядностью 64 бита с применением 56-рапрядного ключа, из которого по специальному фиксированному алгоритму, использующему перестановки и сдвиги, вырабатываются раундовые ключи). Применяемые преобразования- поразрядное сложение по модулю 2, подстановки и перестановки; число раундов равно 16; перед началом первого раунда выполняется начальная фиксированная перестановка IР, после 16-го раунда выполняется обратная перестановка IР^-1. Следуя рекомендациям Шеннона, в каждом раунде выполняется один шаг перемешивания (с использованием соответствующего раундового ключа и S-блоков), после которого следует шаг рассеивания, не зависящий от ключа.

Интересно отметить, что в первоначальной схеме, предложенной IBM, все шестнадцать 48-разрядных раундовых ключей выбирались независимо, т. е. размер ключа был равен 768 битам. Однако по требованию Агентства национальной безопасности США (АНБ), во-первых, размер ключа был уменьшен до 64 бит, из которых только 56 являются секретными, во-вторых, в алгоритме определены перестановки лишь специального вида, не зависящие от ключа, что наводило критиков этого алгоритма на мысль, что АНБ могла использовать известные ей слабости алгоритма для его взлома. На протяжении последних десятилетий DES подвергался интенсивному и всестороннему исследованию и по современным понятиям уже не считается надежным.

Существует несколько предложений, направленных на усовершенствование DES. Наиболее известное из них заключается в трехкратном применении алгоритма (Triple DES).

Наиболее известные блочные шифры - IDEA, BLOWFISH, SKIPJACK.

IDEA (International Data Encryption Algorithm) разработан в 1991 г, работает с блоками данных длиной 64 бита, используя ключ длиной 128 бит, число раундов равно восьми. Используемые преобразования - умножение по модулю 2¹⁶ + 1, сложение по модулю 2, сложение по модулю 2¹⁶. Авторы - К. Лэй, Д. Мэссей.

BLOWF1SH - разработан в 1994 г. Б. Шнайером; работает с блоками данных разрядностью 64 бита, используя ключ переменной длины (максимальная разрядность равна 448 битам), число раундов равно 16. Используемые преобразования - подстановка, сложение по модулю 2, сложение по модулю 2³².

SKIPJACK - разработан в 1990 г. NSA в качестве криптоалгоритма для микросхем Clipper и Capstone. Первоначально алгоритм был объявлен секретным, однако впоследствии его описание "просочилось" в Интернет. Шифр работает с блоками данных разрядностью 64 бита с использованием 80-разрядного ключа. Число раундов равно 32.

Поточные цифры

Шифр Вернама можно считать исторически первым поточным шифром. Так как поточные шифры, в отличие от блочных, осуществляют поэлементное шифрование потока данных без задержки в криптосистеме, их важнейшим достоинством является высокая скорость преобразования, соизмеримая со скоростью поступления входной информации. Таким образом обеспечивается шифрование практически в реальном масштабе времени вне зависимости от объема и разрядности потока преобразуемых данных.

Простейшие устройства синхронного и самосинхронизирующегося шифрования с использованием ГПК, реализованного на основе N-разрядного регистра сдвига с лилейной обратной связью - LFSR (Linear Feedback Shift Register), называются скремблерами, а сам процесс преобразования -- скремблированием.

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

Контрольные вопросы и задания

1. Приведите примеры шифров, для которого сам открытый текст является ключом.

2. Какие шифры называются омофонами? В чем их преимущество перед шифрами простой замены?

3. Что является ключом шифра Вижинера?

4. Приведите пример шифра, допускающего неоднозначное зашифрование.

5. В чем отличие симметричных шифрсистем от ассиметричных?

6. Перечислите виды активных угроз и виды пассивных угроз.

7. На основе каких характеристик в общем случае строится классификация криптографических систем?

8. Приведите пример безусловно защищенной (абсолютно стойкой) схемы шифрования.

9. Продолжите фразу: "Схема шифрования называется защищенной по вычислениям, если…".

10. В чем различие между алгебраической и вероятной моделями шифра?

11. Приведите пример шифра перестановки, который может рассматриваться и как блочный шифр замены.

12. Что более целесообразно для надежной защиты информации: архивация открытого текста с последующим шифрованием или шифрование открытого текста с последующей архивацией?

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

2. Алгоритмы блочного шифрования и элементы криптоанализа

Алгоритмы блочного шифрования - одна из фундаментальных областей криптографии. За последние десятилетия были разработаны сртни алгоритмов, большинство из которых представляет собой последовательное применение простого преобразования. В итоге получается достаточно стойкий шифр, даже если одно преобразование (один раунд) является нестойким (слабым).

К коротким сообщениям алгоритм можно применять непосредственно. Если же длина сообщения больше длины ключа (чаще всего бывает именно так), то необходимо использовать один из режимов работы блочных шифров.

Мы начинаем изучение блочных шифров с алгоритма , который является хорошей "моделью", т. к. обладает многими свойствами, присущими большинству алгоритмов.

2.1 Стандарт шифрования данных des (data encryption standard)

В 1972 году Национальное бюро стандартов (National Bureau of Standards, NBS), теперь называющееся Национальным институтом стандартов и техники (National Institute of Standards and Technology, NIST), выступило инициатором программы защиты линий связи и компьютерных данных. Одной из целей этой программы была разработка единого, стандартного криптографического алгоритма. Этот алгоритм мог бы быть проверен и сертифицирован, а использующие его различные криптографические устройства могли бы взаимодействовать. Он мог бы, к тому же, быть относительно недорогим и легко доступным [17].

15 мая 1973 года в Federal Register NBS опубликовало требования к криптографическому алгоритму, который мог бы быть принят в качестве стандарта. Было приведено несколько критериев оценки проекта:

Алгоритм должен обеспечивать высокий уровень безопасности.

Алгоритм должен быть полностью определен и легко понятен.

Безопасность алгоритма должна основываться на ключе и не должна зависеть от сохранения в тайне самого алгоритма.

Алгоритм должен быть доступен всем пользователям.

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

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

Алгоритм должен быть эффективным в использовании.

Алгоритм должен предоставлять возможности проверки.

Алгоритм должен быть разрешен для экспорта.

Реакция общественности показала, что к криптографическому стандарту существует заметный интерес, но опыт в этой области чрезвычайно мал. Ни одно из предложений не удовлетворяло предъявленным требованиям.

27 августа 1972 года в Federal Register NBS опубликовало повторное предложение. Наконец, у Бюро появился подходящий кандидат: алгоритм под именем Люцифер, в основе которого лежала разработка компании IBM, выполненная в начале 70-х

Несмотря на определенную сложность алгоритм был прямолинеен. Он использовал только простые логические операции над небольшими группами битов и мог быть довольно эффективно реализован в аппаратуре.

17 марта 1975 года в Federal Register NBS опубликовало и подробности алгоритма, и заявление IBM о предоставлении неисключительной, бесплатной лицензии на алгоритм.

В 1976 году NBS провело два симпозиума по оценке предложенного стандарта. На первом обсуждались математика алгоритма и возможность потайной дверцы. На втором - возможности увеличения длины ключа алгоритма. Были приглашены создатели алгоритма, люди, оценивавшие алгоритм, разработчики аппаратуры, поставщики, пользователи и критики. По всем отчетам симпозиумы были весьма оживленными.

Несмотря на критику Стандарт шифрования данных DES 23 ноября 1976 года был принят в качестве федерального стандарта и разрешен к использованию на всех несекретных правительственных коммуникациях. Официальное описание стандарта, FIPS PUB 46, "Data Encryption Standard", было опубликовано 15 января 1977 года и вступило в действие шестью месяцами позже.

Принятие стандарта

Американский национальный институт стандартов (American National Standards Institute, ANSI) одобрил DES в качестве стандарта для частного сектора в 1981 году (ANSI X3.92.), назвав его Алгоритмом шифрования данных (Data Encryption Algorithm, DEA). ANSI опубликовал стандарт режимов работы DEA (ANSI Х3.106), похожий на документ NBS, и стандарт для шифрования в сети, использующий DES (ANSI X3.105).

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

В стандарте DES было оговорено, что он будет пересматриваться каждые пять лет. В 1983 DES был повторно сертифицирован без всяких проблем. 6 марта 1987 года в Federal Register NBS попросило прокомментировать предложение на следующие пять лет. NBS предложило на обсуждение следующие три альтернативы: вновь подтвердить стандарт на следующие пять лет, отказаться от стандарта или пересмотреть применимость стандарта.

Было отмечено, что DES широко используется в бизнесе (особенно в финансах), и что приемлемой альтернативы не существует. Отказ от стандарта оставил бы многие организации без защиты данных. После длительных споров DES был вновь утвержден в качестве правительственного стандарта США до 1992 года.

Наконец было разрешено сертифицировать и программные реализации DES.

2.1.1 Описание DES

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

Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.) Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент времени. Ряд чисел считаются слабыми ключами, но их можно легко избежать. Безопасность полностью определяется ключом.

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

Рис. 15. DES.

Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому он легко реализовывался в аппаратуре второй половины 70-х. Изобилие повторений в алгоритме делает его идеальным для реализации в специализированной микросхеме.

Схема алгоритма

Для описания воспользуемся сведениями [17]. DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 этапов одинаковых действий, называемых функцией f, в которых данные объединяются с ключом. После шестнадцатого этапа правая и левая половины объединяются и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной).

На каждом этапе (см. рисунок 16) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f Затем результат функции f объединяется с левой половиной с помощью другого XOR. В итоге этих действий появляется новая правая половина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 этапов DES.

Рис. 16. Один этап DES.

Если B_i - это результат i-ой итерации, L_i и R_i - левая и правая половины B_i, K_i - 48-битовый ключ для этапа i, a f - это функция, выполняющие все подстановки, перестановки и XOR с ключом, то этап можно представить как:

L_i = R_i-1

R_i = L_i-1f(R_i-1,K_i)

Начальная перестановка

Начальная перестановка выполняется еще до этапа 1, при этом входной блок переставляется, как показано в 11-й. Эту и все другие таблицы этой главы надо читать слева направо и сверху вниз. Например, начальная перестановка перемещает бит 58 в битовую позицию 1, бит 50 - в битовую позицию 2, бит 42 - в битовую позицию 3, и так далее.

Табл. 1 Начальная перестановка
58	50	42	34	26	18	10	2	60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6	64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1	59	51	43	35	27	19	14	3
61	53	45	37	29	21	13	5	63	55	47	39	31	23	15	7

Начальная перестановка и соответствующая заключительная перестановка не влияют на безопасность DES. (Как можно легко заметить, эта перестановка в первую очередь служит для облегчения побайтной загрузки данных открытого текста и шифротекста в микросхему DES. Не забывайте, что DES появился раньше 16- и 32-битовых микропроцессорных шин.) Так как программная реализация этой многобитовой перестановки нелегка (в отличие от тривиальной аппаратной), во многих программных реализациях DES начальная и заключительные перестановки не используются. Хотя такой новый алгоритм не менее безопасен, чем DES, он не соответствует стандарту DES и, поэтому, не может называться DES.

Преобразования ключа

Сначала 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита, как показано в 10-й. Эти биты используются только для контроля четности, позволяя проверять правильность ключа. После извлечения 56-битового ключа для каждого из 16 этапов DES генерируется новый 48-битовый подключ. Эти подключи, K_i, определяются следующим образом.

Табл. 2 Перестановка ключа
57	49	41	33	25	17	9	1	58	50	42	34	26	18
10	2	59	51	43	35	27	19	14	3	60	52	44	36
63	55	47	39	31	23	15	7	62	54	46	38	30	22
14	6	61	53	45	37	29	21	13	5	28	20	12	4

Во-первых, 56-битовый ключ делится на две 28-битовых половинки. Затем, половинки циклически сдвигаются налево на один или два бита в зависимости от этапа. Этот сдвиг показан в 9-й.

Табл. 3 Число битов сдвига ключа в зависимости от этапа

Этап	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Число	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

После сдвига выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, эта операция называется перестановка со сжатием. Ее результатом является набор из 48 битов. Перестановка со сжатием (также называемая переставленным выбором) определена в 8-й. Например, бит сдвинутого ключа в позиции 33 перемещается в позицию 35 результата, а 18-й бит сдвинутого ключа отбрасывается.



Табл. 4 Перестановка со сжатием
14	17	14	24	1	5	3	28	15	6	21	10
23	19	14	4	26	8	16	7	27	20	13	2
41	52	31	37	47	55	30	40	51	45	33	48
44	49	39	56	34	53	46	42	50	36	29	32

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

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

Эта операция расширяет правую половину данных, R_i, от 32 до 48 битов. Так как при этом не просто повторяются определенные биты, но и изменяется их порядок, эта операция называется перестановкой с расширением. У нее две задачи: привести размер правой половины в соответствие с ключом для операции XOR и получить более длинный результат, который можно будет сжать в ходе операции подстановки. Однако главный криптографический смысл совсем в другом. За счет влияния одного бита на две подстановки быстрее возрастает зависимость битов результата от битов исходных данных. Это называется лавинным эффектом. DES спроектирован так, чтобы как можно быстрее добиться зависимости каждого бита шифротекста от каждого бита открытого текста и каждого бита ключа.

Перестановка с расширением показана на 9-й. Иногда она называется Е-блоком (от expansion). Для каждого 4-битового входного блока первый и четвертый бит представляют собой два бита выходного блока, а второй и третий биты - один бит выходного блока. В 7-й показано, какие позиции результата соответствуют каким позициям исходных данных. Например, бит входного блока в позиции 3 переместится в позицию 4 выходного блока, а бит входного блока в позиции 21 - в позиции 30 и 32 выходного блока.

Хотя выходной блок больше входного, каждый входной блок генерирует уникальный выходной блок.

Табл. 5 Перестановка с расширением

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

Подстановка с помощью S-блоков

После объединения сжатого блока с расширенным блоком с помощью XOR над 48-битовым результатом выполняется операция подстановки. Подстановки производятся в восьми блоках подстановки, или S-блоках (от substitution). У каждого S-блока 6-битовый вход и 4-битовый выход, всего используется восемь различных S-блоков. (Для восьми S-блоков DES потребуется 256 байтов памяти.) 48 битов делятся на восемь 6-битовых подблока. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок - S-блоком 1, второй - S-блоком 2, и так далее.

Рис. 18 Подстановка - S-блоки.

Каждый S-блок представляет собой таблицу из 2 строк и 16 столбцов. Каждый элемент в блоке является 4-битовым числом. По 6 входным битам S-блока определяется, под какими номерами столбцов и строк искать выходное значение. Все восемь S-блоков показаны в таблице.



Табл. 6 S-блоки
S-блок 1:
14	4	13	1	2	15	14	8	3	10	6	12	5	9	0	7
0	15	7	4	14	2	13	1	10	6	12	14	9	5	3	8
4	1	14	8	13	6	2	14	15	12	9	7	3	10	5	0
15	12	8	2	4	9	1	7	5	14	3	14	10	0	6	13
S-блок 2:
15	1	8	14	6	14	3	4	9	7	2	13	12	0	5	10
3	13	4	7	15	2	8	14	12	0	1	10	6	9	14	5
0	14	7	14	10	4	13	1	5	8	12	6	9	3	2	15
13	8	10	1	3	15	4	2	14	6	7	12	0	5	14	9
S-блок 3:
10	0	9	14	6	3	15	5	1	13	12	7	14	4	2	8
13	7	0	9	3	4	6	10	2	8	5	14	12	14	15	1
13	6	4	9	8	15	3	0	14	1	2	12	5	10	14	7
1	10	13	0	6	9	8	7	4	15	14	3	14	5	2	12
S-блок 4:
7	13	14	3	0	6	9	10	1	2	8	5	14	12	4	15
13	8	14	5	6	15	0	3	4	7	2	12	1	10	14	9
10	6	9	0	12	14	7	13	15	1	3	14	5	2	8	4
3	15	0	6	10	1	13	8	9	4	5	14	12	7	2	14
S-блок 5:
2	12	4	1	7	10	14	6	8	5	3	15	13	0	14	9
14	14	2	12	4	7	13	1	5	0	15	10	3	9	8	6
4	2	1	14	10	13	7	8	15	9	12	5	6	3	0	14
14	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3
S-блок 6:
12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	14
10	15	4	2	7	12	9	5	6	1	13	14	0	14	3	8
9	14	15	5	2	8	12	3	7	0	4	10	1	13	14	6
4	3	2	12	9	5	15	10	14	14	1	7	6	0	8	13
S-блок 7:
4	14	2	14	15	0	8	13	3	12	9	7	5	10	6	1
13	0	14	7	4	9	1	10	14	3	5	12	2	15	8	6
1	4	14	13	12	3	7	14	10	15	6	8	0	5	9	2
6	14	13	8	1	4	10	7	9	5	0	15	14	2	3	12
S-блок 8:
13	2	8	4	6	15	14	1	10	9	3	14	5	0	12	7
1	15	13	8	10	3	7	4	12	5	6	14	0	14	9	2
7	14	4	1	9	12	14	2	0	6	10	13	15	3	5	8
2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

Входные биты особым образом определяют элемент S-блока. Рассмотрим 6-битовый вход S-блока: b₁, b₂, bз, b₄, b₅ и b₆. Биты b₁ и b₆ объединяются, образуя 2-битовое число от 0 до 3, соответствующее строке таблицы. Средние 4 бита, с b₂ по b₅, объединяются, образуя 4-битовое число от 0 до 15, соответствующее столбцу таблицы.

Например, пусть на вход шестого S-блока (т.е., биты функции XOR с 31 по 36) попадает 110011. Первый и последний бит, объединяясь, образуют 11, что соответствует строке 3 шестого S-блока. Средние 4 бита образуют 1001, что соответствует столбцу 9 того же S-блока. Элемент S-блока 6, находящийся на пересечении строки 3 и столбца 9, - это 14. (Не забывайте, что строки и столбцы нумеруются с 0, а не с 1.) Вместо 110011 подставляется 1110.

Конечно же, намного легче реализовать S-блоки программно в виде массивов с 64 элементами. Для этого потребуется переупорядочить элементы, что не является трудной задачей. (Изменить индексы, не изменяя порядок элементов, недостаточно. S-блоки спроектированы очень тщательно.) Однако такой способ описания S-блоков помогает понять, как они работают. Каждый S-блок можно рассматривать как функцию подстановки 4-битового элемента: b₂ по b₅ являются входом, а некоторое 4-битовое число - результатом. Биты b₁ и b₆ определяются соседними блоками, они определяют одну из четырех функций подстановки, возможных в данном S-блоке.

Подстановка с помощью S-блоков является ключевым этапом DES. Другие действия алгоритма линейны и легко поддаются анализу. S-блоки нелинейны, и именно они в большей степени, чем все остальное, обеспечивают безопасность DES.

В результате этого этапа подстановки получаются восемь 4-битовых блоков, которые вновь объединяются в единый 32-битовый блок. Этот блок поступает на вход следующего этапа - перестановки с помощью Р-блоков.

Перестановка с помощью Р-блоков

32-битовый выход подстановки с помощью S-блоков, перетасовываются в соответствии с Р-блоком. Эта перестановка перемещает каждый входной бит в другую позицию, ни один бит не используется дважды, и ни один бит не игнорируется. Этот процесс называется прямой перестановкой или просто перестановкой. Позиции, в которые перемещаются биты, показаны в 5-й. Например, бит 21 перемещается в позицию 4, а бит 4 - в позицию 31.

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

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

Наконец, результат перестановки с помощью Р-блока объединяется посредством XOR с левой половиной первоначального 64-битового блока. Затем левая и правая половины меняются местами, и начинается следующий этап.

Заключительная перестановка

Заключительная перестановка является обратной по отношению к начальной перестановки и описана в 4-й. Обратите внимание, что левая и правая половины не меняются местами после последнего этапа DES, вместо этого объединенный блок R₁₆L₁₆ используется как вход заключительной перестановки. В этом нет ничего особенного, перестановка половинок с последующим циклическим сдвигом привела бы к точно такому же результату. Это сделано для того, чтобы алгоритм можно было использовать как для шифрования, так и для дешифрирования.

Табл. 8 Заключительная перестановка
40	8	48	16	56	24	64	32	39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30	37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28	35	3	43	14	51	19	59	27
34	2	42	10	50	18	58	26	33	1	41	9	49	17	57	25

2.1.2 Режимы работы блочных шифров

Алгоритм DES является базовым строительным блоком защиты передачи данных. Для применения DES в различных приложениях были определены четыре режима его работы . Предполагается, что этих четырех режимов должно быть достаточно для того, чтобы использовать DES практически в любой области, для которой этот алгоритм подходит. Эти режимы представлены в таблице, а в оставшейся части раздела даны их краткие описания. Эти режимы применимы и для других блочных шифров симметричной схемы.

Режим электронной шифровальной книги

Простейшим режимом является режим электронной шифровальной книги, (ЕСВ), когда открытый текст обрабатывается блоками по 64 бита и каждый блок шифруется с одним и тем же ключом . Термин шифровальная книга объясняется тем, что при заданном ключе каждый 64-битовый блок открытого текста представляется уникальным блоком шифрованного текста. Такое соответствие вызывает аналогию с воображаемой гигантской шифровальной книгой, в которой для каждой 64-битовой последовательности открытого текста указана соответствующая последовательность шифрованного текста.

Если длина сообщения превышает 64 бита, оно разделяется на 64-битовые блоки с добавлением при необходимости заполнителей к последнему блоку. Дешифрование тоже выполняется поблочно на основе одного и того же ключа.

Метод ЕСВ идеален для небольших объемов данных, например для ключей шифрования. Поэтому, если необходимо переслать ключ DES, обеспечив его защиту от разглашения, можно для этого воспользоваться режимом ЕСВ.

Самой важной особенностью режима ECB является то, что одинаковые 64-битовые блоки открытого текста при условии, что таковые встречаются в исходном сообщении, в шифрованном тексте тоже будут представляться одинаковыми блоками

Таблица. Режимы работы DES

Режим	Описание	Типичные области применения
Электронная шифровальная книга (ЕСВ - Electronic Code-book)	Каждый 64-битовый блок открытого текста шифруется независимо от других с одним и тем же ключом	Защищенная передача отдельных значений (например, ключа шифрования)
Сцепление шифрованных блоков (СВС -- Cipher Block Chaining)	Входной блок данных для алгоритма шифрования вычисляется как XOR-разность текущего 64-битового блока открытого текста и предшествующего 64-битового блока шифрованного текста	Поблочная передача данных общего назначения Аутентификация
Шифрованная обратная связь (CFB - Cipher Feedback)	Входные данные обрабатываются порциями по J битов. Полученный на предыдущем шаге шифрованный текст используется как входные данные для алгоритма шифрования с целью получения псевдослучайной последовательности, XOR-разность которой и блока открытого текста определяет очередную порцию шифрованного текста	Потоковая передача данных общего назначения Аутентификация
Обратная связь по выходу (OFB - Output Feedback)	Подобна CFB, но в качестве входных данных для алгоритма шифрования используются ранее полученные выходные данные DES	Потоковая передача данных по каналам с помехами (например, по спутниковой связи)

Поэтому при передаче достаточно длинных сообщений режим ECB может не обеспечивать необходимый уровень защиты. Если сообщение имеет явно выраженную структуру, у криптоаналитика появляется возможность использовать регулярности текста. Например, если известно, что в начале сообщения всегда размещается определенный заголовок, криптоаналитик может получить в свое распоряжение целый набор соответствующих пар блоков открытого и шифрованного текста. Или если сообщение содержит повторяющиеся элементы с периодом их повторения, кратным 64 битам, такие элементы тоже могут быть выявлены аналитиком. Подобные сведения упрощают задачу криптоаналитика или предоставляют возможность для замещения или реорганизации блоков текста в передаваемом сообщении.

Режим сцепления шифрованных блоков

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

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

Тогда

Чтобы получить первый блок шифрованного текста, рассматривается XOR-разность некоторого инициализационного вектора (IV) и первого блока открытого текста. При дешифровании для восстановления первого блока открытого текста необходимо будет тоже выполнить операцию XOR по отношению к тому же вектору IV и первому блоку на выходе алгоритма дешифрования.

Значение IV должно быть известно и отправителю, и получателю сообщения. Для обеспечения максимальной безопасности значение IV должно быть защищено точно так же, как и ключ. Можно, например, отправить значение IV, зашифровав его в режиме ЕСВ. Одной из причин, по которым необходимо защищать IV, является следующая: если противник имеет возможность обмануть адресата сообщения, предоставив подложный IV, то противник получает возможность инвертировать избранные биты в первом блоке открытого текста. Чтобы убедиться в этом, рассмотрим следующие уравнения:

Обозначив i-й бит 64-битового значения X через X[i], получим

Поэтому, используя свойства операции XOR, можем заключить, что

где штрих означает дополнение бита. Как видите, если противник имеет возможность управляемым образом менять биты значения IV, он сможет поменять и соответствующие значения Р,.

В заключение заметим, что благодаря механизму сцепления блоков СВС этот режим оказывается подходящим для шифрования сообщений, длина которых превышает 64 бита.

Помимо обеспечения конфиденциальности, режим СВС можно использовать для аутентификации .

Режим шифрованной обратной связи

Схема DES представляет собой блочный шифр с размером блока 64 бита. Но DES можно преобразовать и в потоковый шифр, используя либо режим шифрованной обратной связи (CFB), либо режим обратной связи по выходу (ОГВ). Использование поточного шифра избавляет от необходимости дополнять сообщение до целого числа блоков. Кроме того, с поточным шифром можно работать в режиме реального времени. Например, при передаче потока символов с помощью посимвольного поточного шифра каждый символ можно шифровать и сразу же передавать адресату, не дожидаясь окончания шифрования остальной части сообщения.

Для поточного шифра необходимо, чтобы длина шифрованного текста в точности соответствовала длине открытого. Так, при передаче 8-битовых символов следует обратиться к 8-битовому шифрованию. Если при этом использовать шифрование блоками длиной более 8 битов, часть ресурсов канала передачи данных будет расходоваться зря.

Единицей передачи данных являются j битов (обычноj = 8). Как и в режиме СВС, происходит сцепление элементов открытого текста, поэтому шифрованный текст, соответствующий любому элементу открытого текста, будет зависеть от всех предыдущих элементов открытого текста.

Сначала рассмотрим шифрование. На входе функции шифрования размещается 64-битовый регистр сдвига, в котором изначально размещается некоторое значение инициализационного вектора (IV). Крайние слева (главные) j битов этого значения связываются операцией XOR с первой порцией открытого текста Pt, в результате чего получается первая порция шифрованного текста С!, который подается на линию передачи данных. Содержимое регистра сдвига смещается влево на / битов, а в крайние справа (наименее значимые) j битов помещается значение С,. Затем весь процесс повторяется до тех пор, пока не будут зашифрованы все элементы открытого текста.

Для дешифрования используется та же схема, но для получения очередной порции открытого текста с помощью операции XOR связываются полученная по связи порция шифрованного текста и получаемые на выходе функции шифрования данные. Обратите внимание, что в данном случае используется функция шифрования, а не дешифрования. Объяснить это просто. Обозначим крайние слева ; битов значения X через S,(X). Тогда

и поэтому

Те же самые выкладки имеют место и для последующих шагов дешифрования. Режим CFB может использоваться как для обеспечения конфиденциальности, так и для аутентификации.

Режим обратной связи по выходу

Режим обратной связи по выходу (OFB), как видно из рис. 3.14, во многом подобен режиму CFB. В режиме OFB в регистр сдвига подается значение, получаемое на выходе функции шифрования, а в режиме CFB в этот регистр подается порция шифрованного текста.

Режим OFB обладает тем преимуществом, что влияние возможных искажений битов при передаче данных не распространяется на последующие порции данных. Например, если искаженные биты появились при передаче С,, это повлияет только на восстановленное из C_t значение Р,, а все последующие порцииоткрытого текста из-за этой шибки передачи данных повреждены не будут. В случае CFB значение С_х используется в качестве входного для регистра сдвига, вследствие чего искажение d выльется в дополнительные искажения для всего потока принимаемых данных.

Недостатком режима OFB, с другой стороны, является то, что он обеспечивает меньшую, чем CFB, надежность в отношении нарушений типа модификации потока данных. Например, изменение одного бита шифрованного текста отражается в изменении соответствующего бита восстановленного открытого текста. Это дает возможность осуществления контролируемых изменений в получаемом адресатом открытом тексте. Практически, чтобы программа коррекции ошибок не заметила подмены, противник должен внести необходимые ему изменения как в данные, представляющие собой порцию шифрованного текста, так и в данные, представляющие контрольную сумму для этой порции текста.

2.1 Расшифрование DES

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

DES позволяет использовать для шифрования или дешифрирования блока одну и ту же функцию. Единственное отличие состоит в том, что ключи должны использоваться в обратном порядке. То есть, если на этапах шифрования использовались ключи К₁, К₂, К₃, ..., K₁₆, то ключами дешифрирования будут K₁₆, K₁₅, K₁₄, ..., К₁. Алгоритм, который создает ключ для каждого этапа, также цикличен. Ключ сдвигается направо, а число позиций сдвига равно 0, 1,2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.

Режимы DES

FIPS PUB 81 определяет четыре режима работы: ЕСВ, СВС, OFB и CFB. Банковские стандарты ANSI определяют для шифрования ЕСВ и СВС, а для проверки подлинности - СВС и n-битовый CFB.

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

Аппаратные и программные реализации DES

Утверждается, что самой быстрой является микросхема DES, разработанная в Digital Equipment Corporation. Она поддерживает режимы ЕСВ и СВС и основана на вентильной матрице GaAs, состоящей из 50000 транзисторов. Данные могут зашифровываться и дешифрироваться со скоростью 1 гигабит в секунду, обрабатывая 16.8 миллионов блоков в секунду. Кажущиеся противоречия между тактовой частотой и скоростью обработки данных обусловлены конвейеризацией внутри микросхемы, в которой может быть реализовано несколько работающих параллельно DES-механизмов.

Наиболее выдающейся микросхемой DES является 6868 VLSI (ранее называвшаяся "Gatekeeper" - Вратарь). Она не только может выполнять шифрование DES за 8 тактов (лабораторные прототипы могут делать это за 4 такта), но также выполнять троекратный DES в режиме ЕСВ за 25 тактов, а троекратный DES в режимах OFB или СВС - за 35 актов.

Программная реализация DES на мэйнфрейме IBM 3090 может выполнить 32000 шифрований DES в секунду. На других платформах скорость ниже, но все равно достаточно велика. В 2-й приведены действительные результаты и оценки для различных микропроцессоров Intel и Motorola.

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

Люди давно интересуются безопасностью DES. Было много рассуждений о длине ключа, количестве итераций и схеме S-блоков. S-блоки были наиболее таинственными - какие-то константы, без видимого объяснения для чего и зачем они нужны. Хотя IBМ утверждала, что работа алгоритма была результатом 17 человеко-лет интенсивного криптоанализа, некоторые люди опасались, что NSA вставило в алгоритм лазейку, которая позволит агентству легко дешифрировать перехваченные сообщения.

Комитет по разведке Сената США чрезвычайно тщательно расследовал этот вопрос в 1978 году. Результаты работы комитета были засекречены, но в открытых итогах этого расследования с NSA были сняты все обвинения в неуместном вмешательстве в проектирование алгоритма. "Было сказано, что NSA убедило IBМ в достаточности более короткого ключа, косвенно помогло разработать структуры S-блоков и подтвердило, что в окончательном варианте DES, с учетом всех знаний NSA, отсутствовали статистические или математические бреши".

Слабые ключи

Из-за того, что первоначальный ключ изменяется при получении подключа для каждого этапа алгоритма, определенные первоначальные ключи являются слабыми. Вспомните, первоначальное значение расщепляется на две половины, каждая из которых сдвигается независимо. Если все биты каждой половины равны 0 или 1, то для всех этапов алгоритма используется один и тот же ключ. Это может произойти, если ключ состоит из одних 1, из одних 0, или если одна половина ключа состоит из одних 1, а другая - из одних 0. Кроме того, у два слабых ключа обладают другими свойствами, снижающими их безопасность.

Четыре слабых ключа показаны в шестнадцатиричном виде в 1-й. (Не забывайте, что каждый восьмой бит - это бит четности.)

Табл. 9 Слабые ключи DES

Значение слабого ключа (с битами четности)	Действительный ключ
0101 0101 0101 0101	0000000 0000000
1F1F1F1F 0Е0Е0Е0Е	0000000 FFFFFFF
E0E0 Е0Е0 F1F1 F1F1	FFFFFFF 0000000
FEFE FEFE FEFE FEFE	FFFFFFF FFFFFFF

Кроме того, некоторые пары ключей при шифровании переводят открытый текст в идентичный шифротекст. Иными словами, один из ключей пары может расшифровать сообщения, зашифрованные другим ключом пары. Это происходит из-за метода, используемого DES для генерации подключей - вместо 16 различных подключей эти ключи генерируют только два различных подключа. В алгоритме каждый из этих подключей используется восемь раз. Эти ключи, называемые полуслабыми ключами, в шестнадцатиричном виде приведены в 0-й.

Табл.10 Полуслабые пары ключей DES

01FE 01FE 01FE 01FE	и	FE01 FE01 FE01 FE01
1FE0 1FE0 0EF1 0EF1	и	E01F E01F F10E F10E
01Е0 01Е0 01F1 01F1	и	Е001 Е001 F101 F101
1FFE 1EEE 0EFE 0EFE	и	FE1F FE1F FE0E FE0E
011F 011F 010Е 010E	и	1F01 1F01 0Е01 0Е01
E0FE E0FE F1FE F1FE	и	FEE0 FEE0 FEE1 FEE1

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

Эти возможно слабые ключи перечислены в табл. 11.

Табл. 11 Возможно слабые ключи DES

1F

1F

01

01

0E

0E

01

01

E0

01

01

E0

Fl

01

01

Fl

01

1F

1F

01

01

0E

0E

01

FE

1F

01

E0

FE

0E

01

Fl

1F

01

01

1F

0E

01

01

0E

FE

01

1F

E0

FE

01

0E

Fl

01

01

1F

1F

01

01

0E

0E

E0

1F

IF

E0

Fl

0E

0E

Fl

Е0

E0

01

01

F1

Fl

01

01

FE

01

01

FE

FE

01

01

FE

FE

FE

01

01

FE

FE

01

01

E0

IF

01

FE

Fl

0E

01

FE

FE

E0

1F

01

FE

Fl

0E

01

E0

01

1F

FE

Fl

01

0E

FE

Е0

FE

1F

01

Fl

FE

0E

01

FE

1F

1F

FE

FE

0E

0E

FE

FE

E0

01

1F

FE

Fl

01

0E

IF

FE

01

E0

0E

FE

01

Fl

Е0

FE

01

1F

Fl

FE

01

0E

01

FE

1F

E0

01

FE

0E

Fl

Е0

E0

1F

1F

Fl

Fl

0E

0E

IF

E0

01

FE

0E

Fl

01

FE

FE

FE

1F

1F

FE

FE

0E

0E

01

E0

IF

FE

01

Fl

0E

FE

FE

IF

E0

01

FE

0E

Fl

01

01

01

E0

E0

01

01

Fl

Fl

Е0

1F

FE

01

Fl

0E

FE

01

IF

IF

E0

E0

0E

0E

Fl

Fl

FE

01

E0

1F

FE

01

Fl

0E

IF

01

FE

E0

0E

01

FE

Fl

Е0

01

FE

1F

Fl

01

FE

0E

01

IF

FE

E0

01

0E

FE

Fl

01

E0

E0

01

01

Fl

Fl

01

IF

01

E0

FE

0E

01

Fl

FE

1F

FE

E0

01

0E

FE

F0

01

01

IF

E0

FE

01

0E

Fl

FE

1F

E0

FE

01

0E

Fl

FE

01

01

01

FE

FE

01

01

FE

FE

01

FE

FE

01

01

FE

FE

01

IF

IF

FE

FE

0E

0E

FE

FE

1F

E0

E0

1F

0E

Fl

Fl

0E

FE

FE

E0

E0

FE

FE

Fl

Fl

01

FE

E0

1F

01

FE

Fl

0E

E0

FE

FE

E0

Fl

FE

FE

Fl

01

E0

FE

1F

01

Fl

FE

0E

FE

E0

E0

FE

FE

Fl

Fl

FE

1F

FE

FE

1F

0E

FE

FE

0E

E0

E0

FE

FE

Fl

Fl

FE

FE

Заметим, что эти 64 ключа - это крошечная часть полного набора из 72057594037927936 возможных ключей. Если вы выбираете ключ случайно, вероятность выбрать один из слабых ключей пренебрежимо мала. Можно всегда проверять "на слабость" сгенерированный ключ. Некоторые думают, что нечего и беспокоиться на этот счет. Другие утверждают, что проверка очень легка, почему бы ее и не выполнить.

Других слабых ключей в процессе исследований найдено не было.

Ключи-дополнения

Выполним побитное дополнение ключа, заменяя все 0 на 1 и все 1 - на 0. Теперь, если блок открытого текста зашифрован оригинальным ключом, то дополнение ключа при шифровании превратит дополнение блока открытого текста в дополнение блока шифротекста. Если х' обозначает дополнение х, то следующее верно:

Ек(Р) = С

Е_К'(P) = С'

В этом нет ничего таинственного. На каждом этапе после перестановки с расширением подключи подвергаются операции XOR с правой половиной. Прямым следствием этого факта и является приведенное свойство комплиментарности.

Это означает, что при выполнении вскрытия DES с выбранным открытым текстом нужно проверять только половину возможных ключей: 2⁵⁵ вместо 2⁵⁶. Эли Бихам (Eli Biham) и Ади Шамир показали, что существует вскрытие с известным открытым текстом, имеющее ту же сложность, для которого нужно не меньше известных открытых текстов.

Остается вопросом, является ли такое свойство слабостью, так как в большинстве сообщений нет комплиментарных блоков открытого текста (для случайного открытого текста шансы "против" чрезвычайно велики), а пользователей можно предупредить не пользоваться дополняющими.

Алгебраическая структура

Все возможные 64-битовые блоки открытого текста можно отобразить на 64-битовые блоки шифротекста 2⁶⁴! Различными способами. Алгоритм DES, используя 56-битовый ключ, предоставляет нам 2^5б (приблизительно 10¹⁷) таких отображений. Использование многократного шифрования на первый взгляд позволяет значительно увеличить долю возможных отображений. Но это правильно только, если действие DES не обладает определенной алгебраической структурой.

Если бы DES был замкнутым, то для любых К₁ и К₂ всегда существовало бы такое К₃, что

Другими словами, операция шифрования DES образовала бы группу, и шифрование набора блоков открытого текста последовательно с помощью К1 и К2 было бы идентично шифрованию блоков ключом КЗ. Что еще хуже, DES был бы чувствителен к вскрытию "встреча посередине" с известным открытым текстом, для которого потребовалось бы только 2²⁸ этапов [807].

Если бы DES был чистым, то для любых К₁,К₂ и К₃ всегда существовало бы такое К₄, что

Тройное шифрование было бы бесполезным. (Заметьте, что замкнутый шифр обязательно является и чистым, но чистый шифр не обязательно является замкнутым.)

Ряд подсказок можно найти в ранней теоретической работе Дона Копперсмита, но этого недостаточно. Различные криптографы пытались решить эту проблему. В повторяющихся экспериментах собирались "неопровержимые доказательства" того, что DES не является группой, но только в 1992 году криптографам удалось это доказать окончательно. Копперсмит утверждает, что команда IBM знала об этом с самого начала.

Длина ключа

В оригинальной заявке фирмы IBM в NBS предполагалось использовать 112-битовый ключ. К тому времени, когда DES стал стандартом, длина ключа уменьшилась до 56 бит. Многие криптографы настаивали на более длинном ключе. Основным их аргументом было вскрытие грубой силой.

В 1976 и 1977 гг. Диффи и Хеллман утверждали, что специализированный параллельный компьютер для вскрытия DES, стоящий 20 миллионов долларов, сможет раскрыть ключ за день. В 1981 году Диффи увеличил время поиска до двух дней, а стоимость - до 50 миллионов долларов. Диффи и Хеллман утверждали, что вскрытие в тот момент времени находилось за пределами возможностей любой организации, кроме подобных NSA, но что к 1990 году DES должен полностью утратить свою безопасность.

Хеллман продемонстрировал еще один аргумент против малого размера ключа: разменивая объем памяти на время, можно ускорить процесс поиска. Он предложил вычислять и хранить 2^5б возможных результатов шифрования каждым возможным ключом единственного блока открытого текста. Тогда для взлома неизвестного ключа криптоаналитику потребуется только вставить блок открытого текста в шифруемый поток, вскрыть получившийся результат и найти ключ. Хеллман оценил стоимость такого устройства вскрытия в 5 миллионов долларов.

Шнайер отмечает в [17], что аргументы за и против существования в каком-нибудь тайном бункере правительственного устройства вскрытия DES продолжают появляться. Многие указывают на то, что среднее время наработки на отказ для микросхем DES никогда не было большим настолько, чтобы обеспечивать работу устройства. Было показано, что этого возражения более чем достаточно. Другие исследователи предлагают способы еще больше ускорить процесс и уменьшить эффект отказа микросхем.

Между тем, аппаратные реализации DES постепенно приблизились к реализации требования о миллионе шифрований в секунду, предъявляемого специализированной машиной Диффи и Хеллмана. В 1984 году были выпущены микросхемы DES, способные выполнять 256000 шифрования в секунду. К 1987 году были разработаны микросхемы DES, выполняющие 512000 шифрований в секунду, и стало возможным появление варианта, способного проверять свыше миллиона ключей в секунду. А в 1993 Майкл Винер (Michael Wiener) спроектировал машину стоимостью 1 миллион долларов, которая может выполнить вскрытие DES грубой силой в среднем за 3.5 часа.

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

В 1990 году два израильских математика, Бихам (Biham) и Шамир, открыли дифференциальный криптоанализ, метод, который позволил оставить в покое вопрос длины ключа. Прежде, чем мы рассмотрим этот метод, вернемся к некоторым другим критическим замечаниям в адрес DES.

Количество этапов

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

В течение многих лет версии DES с уменьшенным числом этапов успешно вскрывались. DES с тремя и четырьмя этапами был легко взломан в 1982 году. DES с шестью этапами пал несколькими годами позже. Дифференциальный криптоанализ Бихама и Шамира объяснил и это: DES с любым количеством этапов, меньшим 16, может быть взломан с помощью вскрытия с известным открытым текстом быстрее, чем с помощью вскрытия грубой силой. Конечно, грубый взлом является более вероятным способом вскрытия, но интересен тот факт, что алгоритм содержит ровно 16 этапов.

Проектирование S-блоков

Помимо уменьшения длины ключа NSA также обвиняют в изменении содержания S-блоков. Настаивая на подтверждении схемы S-блоков, NSA заявило, что детали алгоритма являются "чувствительными" и не могут быть опубликованы. Многие криптографы подозревали, что разработанные в NSA S-блоки содержат лазейку, позволяющую NSA легко выполнять криптоанализ алгоритма.

С момента появления алгоритма для анализа схемы и работы S-блоков были предприняты значительные усилия. В середине 70-х Lexar Corporation и Bell Laboratories исследовали работу S-блоков. Ни одно из исследований не обнаружило никаких слабостей, хотя оба исследования обнаружили непонятный свойства. S-блоки имеют больше свойств, общих с линейным преобразованием, чем можно было ожидать при их формировании случайным образом. Команда Bell Laboratories констатировала, что S-блоки могут содержать скрытые лазейки, а доклад Lexar завершался следующей фразой: