10, 2, 59, 51, 43, 35, 27, 19, 11, 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-разрядных блока: левый - Со и правый - Do;

производится левый циклический сдвиг блоков Со и Do s[l] раз для получения блоков Ci и Di;

из сцепления блоков (Ci, Di) выбираются 48 разрядов с помощью перестановки КР-2. Эти разряды используются на первой итерации;

14,17,11,24,1,5,3,28,15,6,21,10, 23, 19, 12, 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 используемые на i-й циклической итерации разряды ключа определяются методом индукции. Для получения блоков С, и D, производим левый циклический сдвиг блоков C/ i и D, i на s[/] позиций:

и вновь применяем КР-2 для получения очередной порции ключа.

Инверсией DES (обеспечивающей расшифрование зашифрованных посредством DES данных) является

DES = IPxtttj xQxxQxnj x IP, (2.2)

Расшифрование зашифрованного посредством DES текста осуществляется с использованием тех же блоков благодаря обратимости преобразования.

Таков общий алгоритм DES. Попробуем проанализировать его эффективность.

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

Однако, данный алгоритм, являясь первым опытом стандарта шифрования имеет ряд недостатков. За время, прошедшее после

создания DES, компьютерная техника развилась настолько быстро, что оказалось возможным осуществлять исчерпывающий перебор ключей и тем самым раскрывать шифр. Стоимость этой атаки постоянно снижается. В 1998 г. была построена машина стоимостью около 100000 долларов, способная по данной паре <исходный текст, шифрованный текст> восстановить ключ за среднее время в 3 суток. Таким образом, DES, при его использовании стандартным образом, уже стал далеко не оптимальным выбором для удовлетворения требованиям скрытности данных.

Было выдвинуто большое количество предложений по усовершенствованию DES, которые отчасти компенсируют указанные недостатки. Мы рассмотрим два из них.

Наиболее широко известным предложением по усилению DES является так называемый «тройной DES», одна из версий которого определяется формулой

EDE3kk,k, (X) = des3 (des-1 (des, (x))).

To есть, 1слюч для EDE3 имеет длину 56x3 = 168 бит, и шифрование 64-битового блока осуществляется шифрованием с одним подключом, расшифрованием с другим и затем шифрованием с третьим. (Причина, по которой вторым шагом является

dest, а не des, , является совместимость с DES: если вы-

брать K=k,k,k, то EDE3k = DESk. Причина использования DES три раза вместо двух заключается в существовании атаки «встреча в середине» на двойной DES.)

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

В 1984 г. Рон Ривест предложил расширение DES, называемое DESX (DES extended), свободное от недостатков тройного DES.

DESX определяется как

DESkk.M =2® DESa(A:i ® x)

To есть, 1СЛЮЧ DESX К = k,k\,k2 состоит из 54+64+64=184 бит и В1слючает три различных подьслюча: 1слюч "DES" к, предварительный «зашумляющий» 1слюч к\ и завершающий «зашумляю-щий» 1СЛЮЧ Агг.

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

В отношении DESX замечательно то, что эти две операции «исключающее ИЛИ» делают шифр гораздо менее уязвимым по отношению к перебору ключей. Укажем, что DESX затрудняет получение даже одной пары <х„ DESXk(x,)> в том случае, когда злоумышленник организует атаку на шифр по выбранному но ходному тексту, получая множество пар <Ру, DESk(P/)>.

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

DES - РЕРдд + DES,(M + X)

где сложение определяется следующим образом: L.R + L.R = (L О L).(R О R), L=R=L=R= 32, а О обозначает сложение по модулю 2.

Сказанное не означает, что невозможно построить машину, раскрывающую DESX за приемлемое время. Но оно подразумевает, что такая машина должна использовать какую-либо радикально новую идею. Это не может быть машина, реализующая перебор ключей в общепринятом смысле.

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

2.4.2. Стандарт AES. Алгоритм Rijndael

В конце 1996 г. Национальным институтом стандартов США (NIST) был объявлен конкурс на создание нового общенационального стандарта шифрования, который должен прийти на замену DES. Разрабатываемому стандарту было присвоено рабочее наименование AES (Advanced Encryption Standard). Отбор проходил в два этапа, после первого среди претендентов осталось 15 кандидатов, после второго - 5.

2 октября 2000 года было принято окончательное решение. В качестве предлагаемого стандарта был выбран алгоритм Rijndael (произносится "Рейн-дал"). Этот алгоритм был разработан Винсентом Райманом (Vincent Rijman) и Йоан Дамен (Joan Daemen) и представляет собой алгоритм, не использующий сети Фейстела.

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

Алгоритм Rijndael представляет собой блочный шифр с переменной длиной блока и переменной длиной ключа Длины блока и ключа могут быть выбраны независимо равными 128, 192 или 256 бит. Шифр является последовательностью итераций, выполняемых над некоторой промежуточной структурой, называемой состоянием. (Эта терминология заимствована из теории конечных автоматов.) Состояние может быть представлено в виде прямоугольного массива байтов. В массиве 4 строки, а число столбцов, обозначаемое как Nb, равно длине блока, деленной на 32. Ключ шифрования аналогичным образом представляется в виде прямоугольного байтового массива с 4 строками. Количество столбцов, обозначаемое Nk, равно длине

1слюча, деленной на 32. Входные и выходные значения алгоритма представляются в виде одномерных байтовых массивов соответствующей длины. Состояние и ьслючевой массив заполняются из этих массивов вначале по столбцам, а затем по строкам. Количество итераций обозначается Nr зависит от Nb и Nk в соответствии со следующей таблицей:

Итерационное преобразование состоит из четырех различных преобразований. На С-подобном псевдокоде это выглядит так:

Round (State, RoundKey) { ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State, RoundKey);

Последняя итерация несколько отличается от всех остальных:

FinalRound (State, RoundKey) { ByteSub(State); ShiftRow(State);

AddRoundKey(State, RoundKey);

Отдельные преобразования описываются ниже.

ByteSub

Это блок нелинейной обратимой байтовой замены (S-бокс), состоящий из двух операций:

Каждый байт заменяется на мультипликативный обратный к нему в поле GF{2). Байт со значением OOh отображается в себя.

Над каждым байтом выполняется аффинное преобразование в поле GF{2), задаваемое следующим уравнением:

о 1 1 1 1 1

о о о о

о о о о

1 о о о

о о о о

Это аффинное преобразование может быть описано в полиномиальном виде как Ь{х) = {х + х + + х) + а(х)( х + х + х + +1) mod(x +1). Полином, на который производится умножение, выбран взаимно простым с модулем, так что умножение является обратимым.

Обратным к ByteSub будет преобразование, состоящее из обратного аффинного преобразования и взятия мультипликативного обратного в GF{2).

ShiftRow

Это преобразование является циклическим сдвигом влево строк массива состояния на различную величину. Строка О не сдвигается, строка 1 сдвигается на С1 позиций, строка 2 - на С2 и строка 3 - на СЗ позиций. Величины сдвига приведены в таблице:

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

В этом преобразовании столбцы массива состояния рассматриваются как полиномы над полем GF{2). Преобразование заключается в умножении столбца по модулю х"* +1 на фиксированный полином

с(х) = ОЗЬх + Olhx + Olhx + 02h.