Методы и средства криптографической защиты информации

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

· вычисление имитовставки для заданного открытого массива информации;

· подбор открытых данных под заданную имитовставку.

Схема алгоритма выработки имитовставки приведена на рисунке 6.

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

имитовставки надо принимать во внимание, что вероятность успешного навязывания ложных данных равна величине 2-^|I| на одну попытку подбора, если в распоряжении злоумышленника нет более эффективного метода подбора, чем простое угадывание. При использовании имитовставки

размером 32 бита эта вероятность равна 2-³²=0.23·10-⁹.

2.2.5 Криптографическая стойкость ГОСТа.

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

· можно ли вообще раскрыть данный шифр;

· если да, то насколько это трудно сделать практически.

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

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

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

В шифре ГОСТ используется 256-битовый ключ и объем ключевого пространства составляет 2²⁵⁶. Ни на одной из существующих в настоящее время или предполагаемых к реализации в недалеком будущем ЭВМ общего применения нельзя подобрать ключ за время, меньшее многих сотен лет.

Общеизвестно, что шифр ГОСТ 28147-89 является представителем целого семейства шифров, построенных на одних и тех же принципах. Самым известным его "родственником" является алгоритм DES. Все эти шифры, подобно ГОСТу, содержат алгоритмы трех уровней. В основе всегда лежит некий "основной шаг", на базе которого сходным образом строятся "базовые циклы", и уже на их основе построены практические процедуры шифрования и выработки имитовставки.

2.2.6 Требования к качеству ключевой информации и источники ключей

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

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

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

1. Ключ должен являться массивом статистически независимых битов, принимающих с равной вероятностью значения 0 и 1. При этом некоторые конкретные значения ключа могут оказаться "слабыми", то есть шифр может не обеспечивать заданный уровень стойкости в случае их использования. Однако, предположительно, доля таких значений в общей массе всех возможных ключей ничтожно мала. Поэтому ключи, выработанные с помощью некоторого датчика истинно случайных чисел, будут качественными с вероятностью, отличающейся от единицы на ничтожно малую величину. Если же ключи вырабатываются с помощью генератора псевдослучайных чисел, то используемый генератор должен обеспечивать указанные выше статистические характеристики, и, кроме того, обладать высокой криптостойкостью, не меньшей, чем у самого ГОСТа. Иными словами, задача определения отсутствующих членов вырабатываемой генератором последовательности элементов не должна быть проще, чем задача вскрытия шифра. Кроме того, для отбраковки ключей с плохими статистическими характеристиками могут быть использованы различные статистические критерии. На практике обычно хватает двух критериев, - для проверки равновероятного распределения битов ключа между значениями 0 и 1 обычно используется критерий Пирсона ("хи квадрат"), а для проверки независимости битов ключа - критерий серий. Об упомянутых критериях можно прочитать в учебниках или справочниках по математической статистике.

2. Таблица замен является долговременным ключевым элементом, то есть действует в течение гораздо более длительного срока, чем отдельный ключ. Предполагается, что она является общей для всех узлов шифрования в рамках одной системы криптографической защиты. Даже при нарушении конфиденциальности таблицы замен стойкость шифра остается чрезвычайно высокой и не снижается ниже допустимого предела. К качеству отдельных узлов замен можно предъявить приведенное ниже требование. Каждый узел замен может быть описан четверкой логических функций, каждая из которых имеет четыре логических аргумента. Необходимо, чтобы эти функции были достаточно сложными. Это требование сложности невозможно выразить формально, однако в качестве необходимого условия можно потребовать, чтобы соответствующие логические функции, записанные в минимальной форме (т.е. с минимально возможной длиной выражения) с использованием основных логических операций, не были короче некоторого необходимого минимума. В первом и очень грубом приближении это условие может сойти и за достаточное. Кроме того, отдельные функции в пределах всей таблицы замен должны отличаться друг от друга в достаточной степени. На практике бывает достаточно получить узлы замен как независимые случайные перестановки чисел от 0 до 15, это может быть практически реализовано, например, с помощью перемешивания колоды из шестнадцати карт, за каждой из которых закреплено одно из значений указанного диапазона.

Необходимо отметить еще один интересный факт относительно таблицы замен. Для обратимости циклов шифрования "32-З" и "32-Р" не требуется, чтобы узлы замен были перестановками чисел от 0 до 15. Все работает даже в том случае, если в узле замен есть повторяющиеся элементы, и замена, определяемая таким узлом, необратима, однако в этом случае снижается стойкость шифра. Почему это именно так, убедиться несложно.

2.3 Алгоритм IDEA

Первый вариант шифра IDEA, предложенный Ксуеджа Лай (Xuejia Lai) и Джеймсом Масси (James Massey), появился в 1990 году. Он назывался PES (Proposed Encryption Standard, предложенный стандарт шифрования). В следующем году, после демонстрации Бихамом и Шамиром возможностей дифференциального криптоанализа, авторы усилили свой шифр против такого вскрытия и назвали новый алгоритм IPES (Improved Proposed Encryption Standard, улучшенный предложенный стандарт шифрования). В 1992 году название IPES было изменено на IDEA (International Data Encryption Algorithm, международный алгоритм шифрования данных).

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

Его сегодняшняя известность объясняется тем, что он является частью PGP.

Обзор IDEA

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

Как и другие, уже рассмотренные блочные шифры IDEA использует и запутывание, и рассеяние. Философия, лежащая в основе проекта, представляет собой "объединение операций из различных алгебраических групп". Смешиваются три алгебраические группы, и все они могут быть легко реализованы как аппаратно, так и программно:

-- XOR

-- Сложение по модулю 2^1б

-- Умножение по модулю 2¹⁶ + 1. (Это операцию можно рассматривать как S-блок IDEA.)

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

Описание IDEA

Схема IDEA представлена на рисунке. 64-битовый блок данных делится на четыре 16-битовых подблока: Х₁, Х₂, Х₃ и Х₄. Эти четыре подблока становятся входными данными для первого этапа алгоритма. Всего в алгоритме восемь этапов. На каждом этапе четыре подблока подвергаются операциям XOR, сложениям и умножениям друг с другом и с шестью 16-битовыми подключами. Между этапами обмениваются местами второй и третий подблоки. Наконец четыре подблока объединяются с четырьмя подключами в окончательном преобразовании.

Рис. 23 IDEA.

На каждом этапе события происходят в следующей последовательности:

(1) Перемножаются Х₁ и первый подключ.

(2) Складываются Х₂ и второй подключ.

(3) Складываются Х₃ и третий подключ.

(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).

Выходом этапа являются четыре подблока - результаты действий (11), (12), (13) и (14). Поменяйте местами два внутренних подблока (но не в последнем этапе), и вы получите исходные данные для следующего этапа.

После восьмого этапа выполняется заключительное преобразование:

(1) Перемножаются Х₁ и первый подключ.

(2) Складываются Х₂ и второй подключ.

(3) Складываются Х₃ и третий подключ.

(4) Перемножаются Х₄ и четвертый подключ.

Наконец четыре подблока снова соединяются, образуя шифротекст.

Также несложно создавать подключи. Алгоритм использует 52 из них (шесть для каждого из восьми этапов и еще четыре для заключительного преобразования). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это первые восемь подключей алгоритма (шесть для первого этапа и два - для второго). Затем ключ циклически сдвигается налево на 25 битов и снова делится на восемь подключей. Первые четыре используются на этапе 2, а оставшиеся четыре - на этапе 3. Ключ циклически сдвигается налево на 25 битов для получения следующих восьми подключей, и так до конца алгоритма.

Дешифрирование выполняется точно также за исключением того, что подключи инвертируются и слегка изменяются. Подключи при дешифрировании представляют собой обратные значения ключей шифрования по отношению к операциям либо сложения, либо умножения. (Для IDEA подблоки, состоящие из одних нулей, считаются равными 2¹⁶ = -1 для умножения по модулю 2¹⁶ + 1, следовательно, обратным значением 0 относительно умножения является 0.) Эти вычисления могут занять некоторое время, но их нужно выполнить один раз для каждого ключа дешифрирования.

Скорость IDEA

Программные реализации IDEA примерно в два раза быстрее, чем DES. На компьютере с i386/33 МГц IDEA шифрует данные со скоростью 880 Кбит/с, а на компьютере с i486/33 МГц - со скоростью 2400 Кбит/с. IDEA должен был быть побыстрее, но умножения - недешевое удовольствие. Умножение двух 32-битовых чисел на процессоре i486 занимает 40 тактов (10 на процессоре Pentium).

Реализация PES на базе СБИС шифрует данные со скоростью 55 Мбит/с при тактовой частоте 25 МГц. Другая СБИС, разработанная ЕТН Zurich и состоящая из of 251000 транзисторов на кристалле площадью 107.8 мм², шифрует данные с помощью алгоритма IDEA со скоростью 177 Мбит/с при тактовой частоте 25 МГц.

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

Длина ключа IDEA равна 128 битам - более чем в два раза длиннее ключа DES. При условии, что наиболее эффективным является вскрытие грубой силой, для вскрытия ключа потребуется 2¹²⁸ (10³⁸) шифрований. Создайте микросхему, которая может проверять миллиард ключей в секунду, объедините миллиард таких микросхем, и вам потребуется 10¹³ лет для решения проблемы - это больше, чем возраст вселенной. 10²⁴ таких микросхем могут найти ключ за день, но во вселенной не найдется столько атомов кремния, чтобы построить такую машину.

Может быть вскрытие грубой силой - не лучший способ вскрытия IDEA. Алгоритм все еще слишком нов, чтобы можно было говорить о каких-то конкретных криптографических результатах. Разработчики сделали все возможное, чтобы сделать алгоритм устойчивым к дифференциальному криптоанализу. Они определили понятие марковского шифра и продемонстрировали, что устойчивость к дифференциальному криптоанализу может быть промоделирована и оценена количественно. Лай (Lai) утверждал (он привел подтверждение, но не доказательство), что IDEA устойчив к дифференциальному криптоанализ уже после 4 из 8 этапов. Согласно Бихаму, его попытка вскрыть IDEA с помощью криптоанализа со связанными ключами также не увенчалась успехом.

Рис. 24 PES.

Вилли Майер (Willi Meier) исследовал три алгебраических операции IDEA и показал, что, хотя они несовместимы, есть случаи, когда эти операции можно упростить так, чтобы в некоторой степени облегчить. Его вскрытие 2-этапного IDEA оказалось эффективнее вскрытия грубой силой (2⁴² операций), но для IDEА с 3 и более этапами эффективность этого вскрытия была ниже вскрытия грубой силой. Безопасность полного 8-этапного IDEA осталась непоколебимой.

Джоан Дэймен (Joan Daemen) открыла класс слабых ключей IDEA. Эти ключи не являются слабыми в том смысле, в котором слабы некоторые ключи DES, для которых функция шифрования обратна самой себе. Слабость этих ключей состоит в том, что взломщик может легко определить их с помощью вскрытия с выбранным открытым текстом. Например, слабым является следующий ключ (в шестнадцатиричной записи):

0000, 0000, 0x00, 0000, 0000, 000x, xxxx, x000

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

В любом случае вероятность случайной генерации одного из таких слабых ключей очень мала: 1/2⁹⁶. Опасность случайно выбрать такой ключ практически не существует. К тому же, несложно модифицировать IDEA так, чтобы исключить наличие слабых ключей - достаточно выполнить XOR каждого подключа с числом 0x0dae.

Режимы работы и варианты IDEA

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

Однако, так как ключ IDEА более чем в два раза длиннее ключа DES, это вскрытие непрактично. Объем нужной для такого вскрытия памяти составит 64*2¹²⁸ битов, или 10³⁹ байтов.

Можно увеличить вдвое размер блока. Алгоритм также прекрасно работал бы с 32-битовыми подблоками вместо 16-битовых и с 256-битовым ключом. Шифрование выполнялось бы быстрее, и безопасность возросла бы в 2³² раза. Но теория, на которой основан алгоритм, опирается на то, что 2¹⁶+1 является простым числом. А 2³² + 1 простым числом не является. Может быть, алгоритм и можно изменить так, чтобы он работал, но его безопасность будет совсем иной. Некоторые эксперты считают, что заставить работать такой алгоритм будет нелегко.

2.4. Алгоритм AES

Изложено по статье [Панасенко]. Алгоритм шифрования AES (Advanced Encryption Standard - улучшенный стандарт шифрования) в настоящее время является стандартом блочного симметричного шифрования США.

Конкурс AES

В отличие от многих других криптографических стандартов (например, предыдущего стандарта шифрования США DES или отечественного стандарта ГОСТ 28147-89), AES не был разработан "в недрах спецслужб", а выбран на открытом конкурсе из относительно большого числа алгоритмов-претендентов.

До принятия в качестве стандарта алгоритма AES в данном качестве использовался алгоритм DES (Data Encryption Standard - стандарт шифрования данных). Несмотря на множество найденных криптоаналитических методов, применимых к DES, фактически, не было обнаружено каких-либо серьезных уязвимостей в данном алгоритме, за исключением одного, но весьма принципиального недостатка: весьма короткого ключа, реальный размер которого составляет всего 56 бит. Насколько это мало, можно судить из следующей весьма распространенной оценки: для полного перебора ключей DES достаточно примерно 20 часов работы миллиона процессоров, каждый из которых перебирает миллион ключей DES в секунду. Ясно, что такой стойкости против вскрытия алгоритма методом "грубой силы" категорически недостаточно. Тем не менее, DES оставался стандартом шифрования до начала XXI века.

В 1997 году Институт Стандартов и Технологий США (NIST - National Institute of Standards and Technology) объявил о проведении конкурса по замене стандарта DES. На конкурс могли быть присланы алгоритмы шифрования, разработанные как организациями, так и частными лицами в любой стране. Алгоритм-победитель этого конкурса должен был стать новым стандартом блочного симметричного шифрования США.

Для участия в конкурсе (которому было присвоено название AES) алгоритм шифрования должен был соответствовать всего двум обязательным требованиям:

· 128-битный размер блока шифруемых данных,

· не менее трех поддерживаемых алгоритмом размеров ключей шифрования: 128, 192 и 256 бит.

Кроме того, NIST предъявил большое число требований, носивших рекомендательный характер. Именно по соответствию этим требованиям, фактически, и был выбран алгоритм-победитель конкурса. Рекомендации NIST были таковы:

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

· Структура алгоритма должна быть ясной, простой и обоснованной. Прежде всего, такая структура облегчила бы анализ алгоритма в рамках конкурса. Кроме того, ясность и простота структуры давала бы некоторую гарантию отсутствия в алгоритме специально внедренных авторами "закладок", т.е. некоторых недокументированных особенностей алгоритма, которые могли бы быть использованы авторами для его вскрытия.

· Должны отсутствовать слабые и эквивалентные ключи (т.е. ключи, являющиеся различными, но приводящие к одному и тому же результату шифрования).

· Скорость шифрования данных должна быть высокой на всех потенциальных аппаратных платформах - от 8-битных до 64-битных.

· Структура алгоритма должна позволять распараллеливание операций в многопроцессорных системах и аппаратных реализациях.

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

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

В конкурсе AES приняли участие 15 алгоритмов шифрования:

Алгоритм	Автор	Достоинства и недостатки алгоритма
CAST-256	Entrust Technologies, Inc.	В алгоритме не обнаружено уязвимостей. Однако, скорость шифрования у данного алгоритма невысока; кроме того, у него высокие требования к оперативной и энергонезависимой памяти.
Crypton	Future Systems, Inc.	Алгоритм без явных недостатков. Однако, Crypton уступает по всем характеристикам похожему на него алгоритму Rijndael. Эксперты конкурса сочли, что в финале конкурса Crypton однозначно проиграет Rijndael, поэтому не выбрали его во второй раунд конкурса.
DEAL	Richard Outerbridge, Lars Knudsen	Множество недостатков: наличие подмножеств слабых ключей, подверженность дифференциальному криптоанализу, отсутствие усиления при использовании 192-битных ключей по сравнению с 128-битными.
DFC	CNRS - Centre National pour la Recherche Scientifique - Ecole Normale Superieure	Достоинство алгоритма: очень высокая скорость шифрования на 64-битных платформах. При этом алгоритм весьма медленно шифрует на остальных платформах, а также имеет классы слабых ключей.
E2	NTT - Nippon Telegraph and Telephone Corporation	Аналогично алгоритму CAST-256, в E2 не найдено уязвимостей, но требования к энергонезависимой памяти слишком высоки.
FROG	TecApro Internacional S.A.	Алгоритм с наиболее оригинальной структурой и с наибольшим количеством недостатков: наличие уязвимостей, низкая скорость шифрования и высокие требования к ресурсам.
HPC	Richard Schroeppel	Аналогично алгоритму DFC, HPC очень быстро шифрует на 64-битных платформах, но весьма медленно на остальных. Кроме того, сложная и медленная процедура расширения ключа ограничивает возможные применения алгоритма, а наиболее сложная из всех представленных на конкурс алгоритмов структура раунда усложняет анализ алгоритма и делает недоказуемым отсутствие закладок.
LOKI97	Lawrie Brown, Josef Pieprzyk, Jennifer Seberry	Низкая скорость шифрования, высокие требования к ресурсам, наличие уязвимостей.
Magenta	Deutsche Telekom AG	Алгоритм подвержен атакам методами линейного и дифференциального криптоанализа; медленная скорость шифрования.
MARS	IBM	У алгоритма отсутствуют серьезные недостатки, за исключением низкой скорости шифрования на ряде платформ, не имеющих аппаратной поддержки требуемых операций и некоторых других незначительных недостатков. Алгоритм был незначительно модифицирован в течение первого раунда; измененный вариант вышел в финал конкурса.
RC6	RSA Laboratories	RC6 имеет весьма похожие на MARS проблемы с реализацией на некоторых платформах. Эксперты посчитали это незначительным недостатком - алгоритм вышел в финал конкурса.
Rijndael	Joan Daemen, Vincent Rijmen	Каких-либо недостатков у алгоритма не обнаружено; алгоритм вышел в финал конкурса.
SAFER+	Cylink Corporation	Алгоритм подвержен ряду атак и имеет низкую скорость выполнения.
Serpent	Ross Anderson, Eli Biham, Lars Knudsen	Выявлены некоторые незначительные недостатки, алгоритм вышел в финал конкурса.
Twofish	Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson	Из недостатков эксперты отметили сложность алгоритма, затрудняющую его анализ. Алгоритм вышел в финал конкурса.

Как видно из данной таблицы, список участников конкурса оказался весьма разнообразен, среди них можно отметить:

· всемирно известных криптологов, например, "звездный" коллектив авторов алгоритма Twofish;

· организации, давно работающие в данной области и обладающие как богатым опытом разработки криптоалгоритмов, так и сильнейшими специалистами в данной области, например, американская фирма RSA - автор алгоритма RC6;

· всемирно известные корпорации, обладающие большим научным потенциалом, например японский телекоммуникационный гигант NTT с алгоритмом E2;

· образовательные учреждения, известные своими достижениями в области криптографии, например Ecole Normale Superieure (Париж, Франция) с алгоритмом DFC;

· и наоборот, организации, весьма малоизвестные до проведения конкурса AES, например, фирма Tecnologia Apropriada (автор алгоритма FROG) из латиноамериканского государства Коста-Рика.

Анализ алгоритмов-претендентов проводился как специалистами института NIST, так и различными независимыми экспертами - на конкурс было прислано множество материалов, посвященных участвовавшим в конкурсе алгоритмам; все эти материалы можно найти на сайте института NIST http://csrc.nist.gov. По результатам анализа, как видно из приведенной выше таблицы, во второй раунд конкурса вышли следующие 5 алгоритмов: MARS, RC6, Rijndael, Serpent и Twofish.

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

Здесь подробно рассмотрим алгоритм шифрования Rijndael, которому (как победителю конкурса) было присвоено название AES.

Структура алгоритма

Алгоритм AES представляет блок данных в виде двумерного байтового массива размером 4X4. Все операции производятся над отдельными байтами массива, а также над независимыми столбцами и строками.

Рис.1.Раунд алгоритма.

В каждом раунде алгоритма выполняются следующие преобразования (см. рис. 1):

1 Операция SubBytes, представляющая собой табличную замену каждого байта массива данных согласно следующей таблице (см. рис. 2):

63

7C

77

7B

F2

6B

6F

C5

30

01

67

2B

FE

D7

AB

76

CA

82

C9

7D

FA

59

47

F0

AD

D4

A2

AF

9C

A4

72

C0

B7

FD

93

26

36

3F

F7

CC

34

A5

E5

F1

71

D8

31

15

04

C7

23

C3

18

96

05

9A

07

12

80

E2

EB

27

B2

75

09

83

2C

1A

1B

6E

5A

A0

52

3B

D6

B3

29

E3

2F

84

53

D1

00

ED

20

FC

B1

5B

6A

CB

BE

39

4A

4C

58

CF

D0

EF

AA

FB

43

4D

33

85

45

F9

02

7F

50

3C

9F

A8

51

A3

40

8F

92

9D

38

F5

BC

B6

DA

21

10

FF

F3

D2

CD

0C

13

EC

5F

D7

44

17

C4

A7

7E

3D

64

5D

19

73

60

81

4F

DC

22

2A

90

88

46

EE

B8

14

DE

5E

0B

DB

E0

32

3A

0A

49

06

24

5C

C2

D3

AC

62

91

95

E4

79

E7

C8

37

6D

8D

D5

4E

A9

6C

56

F4

EA

65

7A

AE

08

BA

78

25

2E

1C

A6

B4

C6

E8

DD

74

1F

4B

BD

8B

8A

70

3E

B5

66

48

03

F6

0E

61

35

57

B9

86

C1

1D

9E

E1

F8

98

11

69

D9

8E

94

9B

1E

87

E9

CE

55

28

DF

8C

A1

89

0D

BF

E6

42

68

41

99

2D

0F

B0

54

BB

16

Таблица меняет входное значение 0 на 63 (шестнадцатеричное значение), 1 - на 7C, 2 - на 77 и т.д.

Рис. 2. Операция SubBytes.

Вместо данной табличной замены можно выполнить эквивалентную ей комбинацию двух операций:

1.1. Вычисление мультипликативной обратной величины от входного значения в конечном поле GF(2⁸); обратной величиной от 0 является 0.

1.2. Выходное значение b вычисляется следующим образом:

b_i = a_i ? a_{i + 4 mod 8} ? a_{i+5 mod 8} ? a_{i+6 mod 8} ? a_{i+7 mod 8} ? c_i,

где n_i обозначает i-й бит величины n,

a - результат предыдущей операции,

c - шестнадцатеричная константа 63.

2. Операция ShiftRows, которая выполняет циклический сдвиг влево всех строк массива данных, за исключением нулевой (см. рис. 3). Сдвиг i-й строки массива (для i = 1, 2, 3) производится на i байт.

3. Операция MixColumns. Выполняет умножение каждого столбца массива данных (см. рис. 4), который рассматривается как полином в конечном поле GF(2⁸), на фиксированный полином a(x): a(x) = 3x³ + x² + x + 2.

Умножение выполняется по модулю x⁴ + 1.

4. Операция AddRoundKey выполняет наложение на массив данных материала ключа. А именно, на i-й столбец массива данных (i = 0…3) побитовой логической операцией "исключающее или" (XOR) накладывается определенное слово расширенного ключа W_4r+i, где r - номер текущего раунда алгоритма, начиная с 1 (процедура расширения ключа будет описана ниже). Операция AddRoundKey представлена на рис. 5.

Количество раундов алгоритма R зависит от размера ключа следующим образом:

Размер ключа, бит	R
128	10
192	12
256	14

Перед первым раундом алгоритма выполняется предварительное наложение материала ключа с помощью операции AddRoundKey, которая выполняет наложение на открытый текст первых четырех слов расширенного ключа W₀…W₃.

Последний же раунд отличается от предыдущих тем, что в нем не выполняется операция MixColumns.

Рис. 3.Операция ShiftRows.

Рис. 4.Операция MixColumns.

Рис. 5. Операция AddRoundKey.

Расширение ключа

AES использует ключи шифрования трех фиксированных размеров: 128, 192, и 256 бит. В зависимости от размера ключа, конкретный вариант алгоритма AES может обозначаться как AES-128, AES-192 и AES-256 соответственно. Задача процедуры расширения ключа состоит в формировании нужного количество слов расширенного ключа для их использования в операции AddRoundKey. Как было сказано выше, под "словом" здесь понимается 4-байтный фрагмент расширенного ключа, один из которых используется в первичном наложении материала ключа и по одному - в каждом раунде алгоритма. Таким образом, в процессе расширения ключа формируется 4*(R+1) слов.

Расширение ключа выполняется в два этапа, на первом из которых производится инициализация слов расширенного ключа (обозначаемых как W_i): первые Nk (Nk - размер исходного ключа шифрования K в словах, т.е. 4, 6 или 8) слов W_i (т.е. i = 0…Nk-1) формируются их последовательным заполнением байтами ключа (см. рис. 6).

Рис. 6. Инициализация первых слов расширенного ключа.

Последующие слова W_i формируются следующей последовательностью операций для каждого i = Nk…4*(R+1)-1:

Шаг 1.Инициализируется временная переменная T: T = W_i-1.

Шаг 2.Данная переменная модифицируется следующим образом:

· если i кратно Nk, то: T = SubWord(RotWord(T)) ? RC_?i/Nk?; операции SubWord, RotWord будут описаны ниже, а константы RC_n представляют собой слова, в которых все байты, кроме первого являются нулевыми, а первый байт имеет значение 2^n-1 mod 256;

· если Nk = 8 и (i mod Nk) = 4, то: T = SubWord(T);

· в остальных случаях модификация переменной T не выполняется.

Шаг 3. Формируется i-е слово расширенного ключа: W_i = W_i-Nk ? T.

Операция SubWord выполняет над каждым байтом входного значения табличную замену, которая была описана выше - см. операцию SubBytes.

Операция RotWord побайтно вращает входное слово на 1 байт влево.

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

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

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

Расшифрование выполняется применением обратных операций в обратной последовательности. Соответственно, перед первым раундом расшифрования выполняется операция AddRoundKey (которая является обратной самой себе), выполняющая наложение на шифртекст четырех последних слов расширенного ключа, т.е. W_4R…W_4R+3.

Рис. 7. Раунд расшифрования.

Затем выполняется R раундов расшифрования, каждый из которых выполняет следующие преобразования (см. рис. 7):

1. Операция InvShiftRows выполняет циклический сдвиг вправо трех последних строк массива данных на то же количество байт, на которое выполнялся сдвиг операцией ShiftRows при зашифровании.

2. Операция InvSubBytes выполняет побайтно обратную табличную замену, которая определена следующей таблицей:

52

09

6A

D5

30

36

A5

38

BF

40

A3

9E

81

F3

D7

FB

7C

E3

39

82

9B

2F

FF

87

34

8E

43

44

C4

DE

E9

CB

54

7B

94

32

A6

C2

23

3D

EE

4C

95

0B

42

FA

C3

4E

08

2E

A1

66

28

D9

24

B2

76

5B

A2

49

6D

8B

D1

25

72

F8

F6

64

86

68

98

16

D4

A4

5C

CC

5D

65

B6

92

6C

70

48

50

FD

ED

B9

DA

5E

15

46

57

A7

8D

9D

84

90

D8

AB

00

8C

BC

D3

0A

F7

E4

58

05

B8

B3

45

06

D0

2C

1E

8F

CA

3F

0F

02

C1

AF

BD

03

01

13

8A

6B

3A

91

11

41

4F

67

DC

EA

97

F2

CF

CE

F0

B4

E6

73

96

AC

74

22

E7

AD

35

85

E2

F9

37

E8

1C

75

DF

6E

47

F1

1A

71

1D

29

C5

89

6F

B7

62

0E

AA

18

BE

1B

FC

56

3E

4B

C6

D2

79

20

9A

DB

C0

FE

78

CD

5A

F4

1F

DD

A8

33

88

07

C7

31

B1

12

10

59

27

80

EC

5F

60

51

7F

A9

19

B5

4A

0D

2D

E5

7A

9F

93

C9

9C

EF

A0

E0

3B

4D

AE

2A

F5

B0

C8

EB

BB

3C

83

53

99

61

17

2B

04

7E

BA

77

D6

26

E1

69

14

63

55

21

0C

7D

Данную табличную замену можно выполнить, применив к входному байту преобразование, обратное операции 1.2 (см. описание операции SubBytes), после чего вычислить мультипликативную обратную величину от результата предыдущей операции в конечном поле GF(2⁸).

3. Операция AddRoundKey, как и при зашифровании, выполняет наложение на обрабатываемые данные четырех слов расширенного ключа W_4r…W_4r+3. Однако, нумерация раундов r при расшифровании производится в обратную сторону - от R-1 до 0.

4. Операция InvMixColumns выполняет умножение каждого столбца массива данных аналогично прямой операции MixColumns, однако, умножение производится на полином a^-1(x), определенный следующим образом: a^-1(x) = Bx³ + Dx² + 9x + E.

Аналогично зашифрованию, последний раунд расшифрования не содержит операцию InvMixColumns.

Отличия AES от исходного алгоритма Rijndael

Алгоритм Rindael позволяет шифровать данные не только 128-битными блоками, но и блоками по 192 или 256 бит. Таким образом, AES, фактически, имеет лишь одно принципиальное отличие от Rijndael: он предусматривает использование только 128-битных блоков данных. Рассмотрим изменения в приведенном выше описании алгоритма AES, связанные с другими размерами блоков:

1. Обрабатываемые данные могут представляться не только в виде массива размером 4X4, но и 4X6 или 4X8 для 192- и 256-битных блоков соответственно.

2. Количество раундов R алгоритма Rijndael определяется следующей таблицей в зависимости не только от размера ключа, но и от размера блока:

Размер ключа, бит	Размер блока, бит
	128	192	256
128	10	12	14
192	12	12	14
256	14	14	14

4. Количество бит сдвига строк таблицы также зависит от размера блока:

Номер строки	Размер блока, бит
	128	192	256
1	1	1	1
2	2	2	3
3	3	3	4

4. Поскольку для 192- и 256-битного блоков увеличивается количество столбцов массива данных до 6 и 8 соответственно, в операции AddRoundKey участвуют уже 6 или 8 слов расширенного ключа вместо четырех. Следовательно, в r-м раунде алгоритма выполняется наложение слов расширенного ключа W_Nb*r…W_Nb*r+3, где Nb - количество столбцов массива данных.

5. В связи с вышесказанным, изменяется и процедура расширения ключа, однако, изменение состоит лишь в том, что данная процедура должна выработать Nb*(R+1)-1 слов расширенного ключа, а не 4*(R+1)-1 (что, впрочем, остается справедливым для 128-битного блока).

Первичная оценка криптостойкости

Первичная оценка криптостойкости алгоритма Rijndael была приведена авторами алгоритма в его спецификации, представленной на конкурс AES. Согласно оценкам авторов, Rijndael не подвержен следующим видам криптоаналитических атак:

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

2.К алгоритму не применим дифференциальный криптоанализ.

3.Алгоритм не атакуем с помощью линейного криптоанализа и усеченных дифференциалов.

4.Square-атака (специфичная атака на алгоритмы со структурой "квадрат", к которым относится и AES) также не применима к алгоритму Rijndael.

5.Алгоритм не вскрывается методом интерполяции.

Исследования в рамках конкурса AES

Сначала рассмотрим те результаты криптоанализа, которые были учтены экспертами при выборе алгоритма-победителя конкурса AES. Прежде всего, было найдено несколько атак на усеченные (с уменьшенным количеством раундов) версии алгоритма Rijndael:

· В упомянутой выше первичной оценке криптостойкости были приведены некоторые атаки на усеченные версии Rijndael, из которых стоит отметить Square-атаку на 6-раундовую версию алгоритма, для которой необходимо 2³² выбранных открытых текстов и 2⁷² операций шифрования.

· Square-атака на 6-раундовую версию Rijndael была незначительно усилена Эли Бихамом и Натаном Келлером, которые также предложили атаку методом невозможных дифференциалов на 5-раундовую версию алгоритма; для нее требуется 2^29,5 выбранных открытых текстов и 2³¹ операций. Атака с помощью невозможных дифференциалов рядом корейских специалистов была распространена на 6-раундовую версию Rijndael: для данной атаки требуется 2^91,5 выбранных открытых текстов и 2¹²² операций шифрования.

· Впоследствии Square-атака была расширена на 7 раундов алгоритма Rijndael. Однако, данная атака весьма непрактична: для ее реализации требуется 2³² выбранных открытых текстов и от 2¹⁸⁴ до 2²⁰⁸ операций шифрования.

· Авторы алгоритма Twofish (финалиста конкурса AES) с участием ряда других специалистов продолжили усиление Square-атаки против алгоритма Rijndael: новая Square-атака позволяла вскрыть 6-раундовый Rindael выполнением 2⁴⁴ операций, а 7-раундовый - от 2¹⁵⁵ до 2¹⁷² операций шифрования при том же требуемом количестве выбранных открытых текстов. Кроме того, новая атака позволяет вскрыть 7- и 8-раундовые (последнюю - только при использовании 256-битного ключа) версии Rijndael при наличии от 2¹¹⁹ до 2¹²⁸ выбранных открытых текстов выполнением, соответственно, 2¹²⁰ или 2²⁰⁴ операций.

· Та же команда криптологов предложила атаку на связанных ключах на 9-раундовую версию Rijndael с 256-ключом, которой необходимо 2⁷⁷ выбранных открытых текстов, зашифрованных на 256 связанных ключах, и 2²²⁴ операций шифрования.

С учетом того, что в алгоритме Rijndael выполняется, как минимум, 10 раундов, запас криптостойкости алгоритма экспертами был признан адекватным. С этим, однако, согласны далеко не все специалисты. Утверждается, что алгоритм, выбранный в качестве стандарта AES, должен оставаться криптографически стойким до 2100 года. Ясно, что за почти сто лет будет сделано огромное количество попыток вскрытия AES, некоторые из которых приведут к увеличению количества вскрываемых раундов. Судя по последнему десятилетию, появятся и принципиально новые виды криптоаналитических атак. Поэтому, считая формально, Rijndael должен выполнять, как минимум, 18 раундов.

В рамках исследований в течение первого раунда конкурса AES было также отмечено, что Rijndael имеет ряд потенциальных уязвимостей при реализации данного алгоритма в смарт-картах:

· Rijndael может быть подвержен атаке по потребляемой мощности, нацеленной на его процедуру расширения ключа, что, однако, не доказано Эли Бихамом и Эди Шамиром.

· Весьма интересное исследование на данную тему было проведено специалистами исследовательского центра компании IBM. Они выполнили реализацию алгоритма Twofish для типичной смарт-карты с CMOS-архитектурой и проанализировали возможность атаки на данный алгоритм с помощью дифференциального анализа потребляемой мощности (DPA - Differential Power Analysis). Оказалось, что атаке подвержена процедура входного отбеливания алгоритма Twofish, в результате чего можно вычислить ключ шифрования данного алгоритма. Атака была (теоретически) распространена на остальные алгоритмы-участники конкурса AES. Аналогично алгоритму Twofish, с помощью DPA атакуется предварительное наложение материала ключа, выполняемое в алгоритме Rijndael, после чего вычисляется ключ шифрования целиком.

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

Исследования после конкурса AES

Как и предполагали эксперты, после принятия алгоритма Rijndael в качестве стандарта AES попытки вскрытия данного алгоритма существенно усилились.

Можно сказать, что криптоанализ алгоритма AES стал развиваться, в основном, в следующих четырех направлениях:

Во-первых, попытки усиления "классических" атак или применения других известных атак к данному алгоритму. Например, атаку методом бумеранга на 6-раундовую версию алгоритма со 128-битным ключом, для выполнения которой требуется 2³⁹ выбранных открытых текстов, 2⁷¹ шифртекстов с адаптивным выбором и 2⁷¹ операций шифрования.

Во-вторых, применение различных методов криптоанализа на связанных ключах, в частности:

· Предложено несколько вариантов атак на связанных ключах на 7- и 8-раундовый AES-192 с использованием невозможных дифференциалов.

· Комбинация метода бумеранга и связанных ключей предложена в работе [3]: 9-раундовый AES-192 атакуется при наличии 2⁷⁹ выбранных открытых текстов, каждый из которых шифруется на 256 связанных ключах, выполнением 2¹²⁵ операций шифрования; для атаки на 10-раундовый AES-256 требуется 2^114,9 выбранных открытых текстов (включая зашифрование на 256 связанных ключах) и 2^171,8 операций. Данная атака использует слабость процедуры расширения ключа, состоящую в ее недостаточной нелинейности.

· Эта атака была усилена в работе [17], в которой, в частности, предлагается атака на 10-раундовый алгоритм AES-192, для которой требуется 2¹²⁵ выбранных открытых текстов (на 256 связанных ключах) и 2^146,7 операций.

Несмотря на то, что предложенные атаки на связанных ключах являются весьма непрактичными, настораживает тот факт, что атаке подвержены уже 10 из 12 раундов алгоритма AES-192 (и это после всего 5 лет после принятия стандарта AES!) - возникает опасение, что эксперты (указывающие на недостаточность раундов в алгоритме Rijndael) были правы и полнораундовый алгоритм AES будет вскрыт существенно раньше, чем предполагали эксперты института NIST.

В-третьих, многие исследования посвящены алгебраической структуре алгоритма Rijndael, например:

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

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

· Показано, что вскрытие алгоритма AES эквивалентно решению системы квадратичных уравнений в конечном поле GF(2⁸).

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

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

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

· Не меньше исследований посвящено безопасным (т.е. защищенным от утечек данных по побочным каналам) программным или аппаратным реализациям AES.

Заключение

Итак, на май 2007 г., по прошествии всего 6 лет после принятия алгоритма Rijndael в качестве стандарта AES, криптоаналитики весьма серьезно продвинулись во вскрытии данного алгоритма:

· Предложена теоретическая атака уже на 10 раундов (из 12) алгоритма AES-192.

· Существует множество примеров вскрытия реализаций алгоритма AES с помощью side-channel-атак.

2.5 Обзор некоторых современных блочных шифров

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

Совершенствование средств нападения (линейного и дифференциального методов криптоанализа) поставило перед разработчиками новые задачи.

2.5.1 Алгоритм LUCIFER

В конце 60-х IBM начала выполнение исследовательской программы по компьютерной криптографии, названной Люцифером (Lucifer) и руководимой сначала Хорстом Фейстелем (Horst Feistel), а затем Уолтом Тачменом (Walt Tuchman). Это же название - Lucifer - получил блочный алгоритм, появившийся в результате этой программыв начале 70-х. В действительности существует по меньшей мере два различных алгоритма с таким именем содержит ряд пробелов в спецификации алгоритма. Все это привело к заметной путанице.

Lucifer - это набор перестановок и подстановок, его блоки похожи на блоки DES. В DES результат функции f объединяется с помощью XOR со входом предыдущего этапа, образуя вход следующего этапа. У S-блоков алгоритма Lucifer 4-битовые входы и 4-битовые выходы, вход S-блоков представляет собой перетасованный выход S-блоков предыдущего этапа, входом S-блоков первого этапа является открытый текст. Для выбора используемого S-блока из двух возможных применяется бит ключа. (Lucifer реализует это, как один Т-блок с 9 битами на входе и 8 битами на выходе.) В отличие от DES половины блока между этапами не переставляются и вообще понятие половины блока не используется в алгоритме Lucifer. У этого алгоритма 16 этапов, 128-битовые блоки и более простое, чем в DES, распределение ключей.

Применив дифференциальный криптоанализ к первой реализации Lucifer'a, Бихам и Шамир показали, что Lucifer с 32-битовыми блоками и 8 этапами может быть взломан с помощью 40 выбранных открытых текстов за 2³⁹ шагов, тот же способ позволит вскрыть Lucifer с 128-битовыми блоками и 8 этапами с помощью 60 выбранных открытых текстов за 2⁵³ шагов. 18-этапный, 128-битовый Lucifer вскрывается дифференциальным криптоанализом с помощью 24 выбранных открытых текстов за 2²¹ шагов. Все эти вскрытия использовали сильные S-блоки DES. Применив дифференциальный криптоанализ против второй реализации Lucifer, Бихам и Шамир обнаружили, что S-блоки намного слабее, чем в DES. Дальнейший анализ показал, что более половины возможных ключей не являются безопасными. Криптоанализ со связанными ключами может взломать 128-битовый Lucifer с любым числом этапов с помощью 2³³ выбранных открытых текстов для выбранных ключей или 2⁶⁵ известных открытых текстов для выбранных ключей. Вторая реализация Lucifer еще слабее.

Lucifer является объектом нескольких патентов США. Сроки действия всех этих патентов истекли.

2.5.2 Алгоритм MADRYGA

В.Е. Мадрига (W. E. Madryga) предложил этот блочный алгоритм в 1984 году. Он может быть эффективно реализован как программа: в нем нет надоедливых перестановок, и все операции выполняются над байтами. Стоит перечислить задачи, которые решал автор при проектировании алгоритма:

1. Открытый текст нельзя получить из шифротекста без помощи ключа. (Это означает только то, что алгоритм безопасен.)

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

Известность алгоритма не влияет на силу шифра. (Безопасность полностью определяется ключом.)

Изменение одного бита ключа должно вызывать для того же открытого текста радикальное изменение шифротекста, и изменение одного бита открытого текста должно вызывать для того же ключа радикальное изменение шифротекста. (Это лавинный эффект.)

Алгоритм должен содержать некоммутативную комбинацию подстановок и перестановок.

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

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

Длина шифротекста должна равняться длине открытого текста.

9. Не должно быть простых взаимосвязей между любыми возможными ключами и особенностями шифротекста.

10. Все возможные ключи должны давать сильный шифр. (Не должно быть слабых ключей.)

11. Длина ключа и текста могут регулироваться для реализации различных требований к безопасности.