Шифр Rijndael (AES)

Шифр ГОСТ 28147-89

Шифр ГОСТ 28147-89 [5], как следует из его обозначения, был принят в качестве стандарта в 1989 году. Основные параметры ГОСТ 28147-89: длина ключа 256 бит, размер блока 64 бита, 32 раунда. ГОСТ 28147-89 более удобен для программной реализации, чем DES, имеются сведения о выигрыше по времени примерно в 1.5 раза. В отличие от DES, ГОСТ 28147-89, по-видимому, не был предметом столь глубокого анализа со стороны мирового криптологического сообщества. Тем не менее, как отмечают специалисты, консервативный дизайн и величина основных параметров (длина ключа, размер блока, количество раундов) позволяют утверждать, что шифр вряд ли может быть слабым. Никаких эффективных атак против шифра ГОСТ 28147-89 не опубликовано.

В основе ГОСТ 28147-89, так же как и DES, лежит так называемая структура Фейстела. Блок разбивается на две одинаковые части, правую R и левую L. Правая часть объединяется с ключевым элементом и посредством некоторого алгоритма шифрует левую часть. Перед следующим раундом левая и правая части меняются местами. Такая структура позволяет использовать один и тот же алгоритм как для шифрования, так и для дешифрования блока. Это особенно важно при аппаратной реализации, так как прямой и обратный шифры формируются одним и тем же устройством (различается только порядок подачи элементов ключа).

Авторами шифра Rijndael (читается «Рейндал») являются бельгийские специалисты В. Рейман (Vincent Rijmen) и Й. Даман (Joan Daemen). Этот шифр победил в упомянутом выше конкурсе AES и в 2001 году был принят в качестве нового стандарта США. Возможно, он будет играть такую же важную роль в практической криптографии, какая на протяжении десятилетий принадлежала DES. Rijndael заметно сложнее для описания, чем RC6 и ГОСТ 28147-89, хотя его компьютерная реализация достаточно эффективна. Мы представим только основную идею построения шифра.

Шифр Rijndael/AES характеризуется размером блока 128 бит, длиной ключа 128, 192 или 256 бит и количеством раундов 10, 12 или 14 в зависимости от длины ключа.

Договоримся об основных обозначениях. Под словом будем понимать последовательность из четырех байт (32 бита). Байты в слове нумеруются с 0 (младший байт) по 3 (старший байт). Блок данных состоит из четырех слов, которые нумеруются также с 0 по 3. Для упрощения обозначений условимся, что номера байтов в слове и слов в блоке всегда приводятся по модулю 4 без явного указания на это. Блок данных рассматривается как матрица размером 4x4 байта, причем слова соответствуют не строкам (как это обычно принято), а столбцам. Например Х _2,3 обозначает второй байт третьего слова блока X. Однако запись с одним индексом обозначает слово, например, Х з - третье слово блока. Мы будем следовать этому соглашению, чтобы не менять связанной с ним терминологии Rijndael.

Для выполнения преобразований в блоке используется раундо-вый ключ W, получаемый из секретного ключа К. Размер секретного ключа l определяет общее число раундов шифра r:

l =128 r =10,

l =192 r =12,

l =256 r =14.

Раундовый ключ состоит из блоков (по 128 бит), количество которых равно числу раундов плюс 1,

W = W ₀, W ₁,..., W_r.

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

1) линейный смешивающий слой гарантирует высокую степень взаимопроникновения символов блока для маскировки статистических связей;

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

3) слой сложения с ключом выполняет непосредственно шифрование.

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

Алгоритм 5.5. RlJNDAEL: ШИФРОВАНИЕ БЛОКА

ВХОД: Блок X, раундовый ключ W.

ВЫХОД: Блок Y.

1. YXW ₀;

2. FOR r =1,2,..., r -1 DO

3. Y SubBytes(Y),

4. Y ShiftRows(Y),

5. Y MixColumns(Y),

6. YYW_i;

7. Y SubBytes(Y),

8. Y ShiftRows(Y),

9. Y Y W_r;

10. RETURN Y.

Процедура SubBytes (замена байтов) реализует слой нелинейного преобразования. Две другие процедуры ShiftRows (сдвиг строк) и MixColumns (перемешивание столбцов) представляют линейный смешивающий слой. Слой сложения с ключом реализован с помощью побитового «исключающего или» (XOR).

Алгоритм 5.6. RlJNDAEL: ДЕШИФРОВАНИЕ БЛОКА

ВХОД: Блок Y, раундовый ключ W.

ВЫХОД: Блок X.

1. XYW_r;

2. FOR i=r -1, r -2,...,1 DO

3. X SubBytes^-1(X),

4. X ShiftRows^-1(X),

5. X MixColumns^-1(X),

6. X X W_i;

7. X SubBytes^-1(X),

8. X ShiftRows^-1(X),

9. Х ХW ₀;

10.RETURN X.

Последнее, что нам осталось рассмотреть, это процесс формирования раундового ключа. В прямом и обратном шифре нам было удобно делить раундовый ключ W на блоки по четыре слова. Однако формирование ключа проходит в пословном режиме, поэтому условимся обозначать буквой w с индексом отдельное слово в W, нумеруя слова с нуля. Как следует из описания шифра, раундовый ключ W должен состоять из r+ 1 блоков, где r - количество раундов в шифре. Поэтому количество слов в W равно 4(r +1). Число же слов в секретном ключе К, которое будем обозначать через с, равно 4, 6 или 8. Вначале опишем алгоритм построения W, затем дадим некоторые пояснения.

Алгоритм 5.9. Rijndael: формирование раундового ключа

ВХОД: Секретный ключ К из с слов.

ВЫХОД: Раундовый ключ W из 4(r +1) слов.

1. WК (с слов);

2. FOR i = c, c +l,...,4(r +l)-l DO

3. tw_{i -1};

4. IF i mod с =0 THEN

5. t SubWord(RotWord(t)) Rcon [ i div c ];

6. ELSE IF с =8 AND i mod с =4 THEN

7. t SubWord(t);

8. w w_i-ct;

9. RETURN w _0… w _4(r+1)-1

В данном алгоритме SubWord(t) - функция, применяющая S-бокс шифра к каждому байту слова t

[ t ₀, t ₁, t ₂, t ₃][S[ t ₁],S[ t ₂],S[ t ₃],S[ t ₀]].

Преобразование RotWord(t) осуществляет циклический сдвиг слова t на один байт влево

[ t ₀, t ₁, t ₂, t ₃][ t ₁, t ₂, t ₃, t ₀].

Массив раундовых констант Rcon состоит из слов

Rcon[ i ]=[ y_i,0,0,0],

где

уi = х^{i- 1} mod m (x).

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

1) затруднить атаки на шифр при частично известном секретном ключе или при использовании зависимых (связанных общими правилами построения) ключей;

2) устранить имеющиеся симметрии внутри раунда шифра и между раундами (для этого используется массив раундовых констант Rcon).

Как отмечалось при рассмотрении обратного шифра, чтобы получить раундовый ключ для дешифрования, необходимо подвергнуть преобразованию MixColumns^-1 блоки W с первого по предпоследний.

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