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

Преобразование AddRoundKey, является обратным для самого себя, так как использует операцию XOR.

Алгоритм шифрования данных ГОСТ 28147-89

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

Алгоритм этот симметричный, т.е. ключ зашифровки совпадает с ключом расшифровки. Длина ключа 256 бит, что обеспечивает очень большую криптостойкость алгоритма. По скорости алгоритм примерно равен скорости подобных алгоритмов (по крайней мере, имеет тот же порядок) или немного быстрее их. ГОСТ 28147-89 относится к блочным шифрам.

Ключи

Ключом в данном алгоритме служит массив из восьми 32-битных чисел. Таким образом, длина ключа составляет 256 бит. Ключ можно представить как таблицу, в которой 8 строк и 32 столбца. Такая конфигурация ключа необходима для работы алгоритма, что будет видно далее.

Таблица замен

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

Таблица замен состоит из 8 строк и 16 столбцов, в каждой ячейке таблицы хранится 4-битное число. Строки таблицы замен называют узлами замен, и на них накладывается ограничение, несоблюдение которого не влечет за собой неработоспособность алгоритма, но значительно снижает криптостойкость. Ограничение следующее: все числа в пределах одной строки (одного узла) таблицы замен должны быть различными. Т.е. в каждой строке таблицы замен не должно быть повторяющихся чисел. Т.о. каждая строка таблицы замен содержит произвольную перестановку чисел от 0 до 15.

Построение алгоритма

Алгоритм как бы состоит из трех уровней. Основной шаг криптопреобразования - самый нижний уровень, на его основе строятся все более высокие части алгоритма. Отталкиваясь от основных шагов строятся базовые циклы: цикл зашифрования (32-З), цикл расшифрования (32-Р) и цикл выработки имитовставки (16-З). На самой верхней ступени стоят собственно реальные алгоритмы или циклы (на самом деле стандарт ГОСТ 28147-89 содержит не один, а несколько алгоритмов шифрования), которые строятся на основе базовых циклов.

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

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

Основной шаг криптопреобразования

На входе основного шага определяется 64-битный блок данных N = (N₁, N₂), где N₁ - младшая 32-битовая часть, а N₂ - старшая 32-битовая часть. Обе части рассматриваются как отдельные 32-битовые числа. На вход основного шага также поступает один из восьми элементов ключа (какой именно, будет рассказано далее). 32-битовый элемент ключа обозначается за X. Далее производятся следующие действия:

S = N₁ + X (mod 2³²).

Число S разбивается на 8 частей: S₀,S₁,S₂,S₃, S₄,S₅,S₆,S₇ по 4 бита каждая, где S₀ - младшая, а S₇ - старшая части числа S.

Для всех i от 0 до 7: S_i = T(i, S_i), где T(a, b) означает ячейку таблицы замен с номером строки a и номером столбца b (счет с нуля).

Новое число S, полученное на предыдущем шаге циклически сдвигается в сторону старших разрядов на 11 бит.

S = S xor N₂, где xor - операция исключающего или.

N₂ = N₁.

N₁ = S.

Как результат основного шага криптопреобразования возвращается блок данных N = (N₁, N₂), где N₂ равно исходному N₁, а N₁ - результат преобразований основного шага.

Базовые циклы

Базовые циклы ГОСТ 28147-89 строятся из основных шагов криптопреобразования путем многократного их повторения с различными элементами ключа. Блок данных, с которым работает базовый цикл поступает на его вход один раз в начале работы, а результатом базового цикла является преобразованный блок данных. Как и в основном шаге 64-битный блок данных обозначим через N = (N₁, N₂), а элементы ключа через X с индексом, означающим номер элемента в ключевом массиве.

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

Для цикла зашифрования (32-З): X₀,X₁,X₂,X₃,X₄, X₅,X₆,X₇,X₀,X₁,X₂,X₃, X₄,X₅,X₆,X₇,X₀,X₁,X₂, X₃,X₄,X₅,X₆,X₇,X₇,X₆, X₅,X₄,X₃,X₂,X₁,X₀.

Для цикла расшифрования (32-Р): X₀,X₁,X₂,X₃, X₄,X₅,X₆,X₇X₇,X₆,X₅, X₄,X₃,X₂,X₁,X₀X₇,X₆, X₅,X₄,X₃,X₂,X₁,X₀X₇, X₆,X₅,X₄,X₃,X₂,X₁,X₀.

Для цикла выработки имитовставки (16-З): X₀,X₁,X₂,X₃, X₄,X₅,X₆,X₇,X₀,X₁,X₂, X₃,X₄,X₅,X₆,X₇.

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

Основные режимы шифрования

ГОСТ 28147-89 определяет три основных режима шифрования: простая замена, гаммирование и гаммирование с обратной связью и один дополнительный режим выработки имитовставки. Данные обрабатываются блоками по 64 бита, на которые разбивается массив, последний блок может быть неполным. В двух последних режимах имеется возможность обрабатывать неполный блок данных, в первом длина данных должна быть кратна 64-м битам.

Простая замена

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

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

Гаммирование

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

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

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

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

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

Рекуррентный генератор последовательности чисел (РГПЧ)

Это и есть тот самый генератор чисел, который используется при шифровании гаммированием. На каждом шаге он выдает 64-битное число, которое по сути состоит из двух 32-битных чисел, которые генерируются по-отдельности. Фактически существуют два РГПЧ для старшей и младшей частей.

Числа, которые выдает РГПЧ, обозначим через Q = (A, B), где A - младшая, а B - старшая части числа. Индекс числа Q обозначает номер шага, на котором числа получены, так индекс i - 1 означает предыдущий шаг. Q₀ - синхропосылка или начальный заполнитель. Выработка происходит следующим образом:

A_i = A_{i - 1} + C₁ (mod 2³²), где C₁ = 1010101₁₆.

B_i = B_{i - 1} + C₂ (mod 2³² - 1), где C₂ = 1010104₁₆.

Если B_i = 0, то B_i = 2³² - 1.

Число B не может получиться нулевым. Константы C₁ и C₂ даны в шестнадцатеричной системе счисления.

Гаммирование с обратной связью

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

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

Выработка имитовставки

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

S = 0.

Для каждого 64-битного блока данных из массива данных: S = F(S xor T_i), где T_i - блок данных, F - базовый цикл выработки имитовставки (16-З), xor - операция исключающего или.

S - полученная имитовставка.

В качестве имитовставки можно использовать лишь часть полученного числа S, но следует помнить, что вероятность успешного навязывания ложных данных равна величине 2^-L, где L - длина используемой части числа в битах. Обычно используются младшие 32 бита числа S.

Заключение

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

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

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

2. Порядок выполнения работы

1. Для реализации алгоритма воспользуемся средой Microsoft Visual Studio.

2. Необходимо реализовать процессы шифрования и дешифрования.

3. Для реализации процесса зашифрования необходимо разработать функции по следующей схеме:
а) Расширение ключа KeyExpansion. Функция «Расширение ключа» может быть реализована, например, так

void KeyExpansion( unsigned char CipherKey[16], unsigned char **w)

{

for(int r=0;r<(Nr+1);r++)           //Цикл по блокам

{

       for(int i=0;i<Nk;i++)         //Цикл по словам

       {

             if(r==0)

             {

                  for(int j=0;j<Nb;j++)

                        w[i][j] = CipherKey[Nk*i+j]; //Слова ключа шифрования К копируются в первые четыре слова расширенного ключа

             }

             else

             {

                  if(i==0) //Если r кратно Nk

                        SubWord( RotWord(w[r*Nk+i-1]) , w[r*Nk+i], r);

                  else

                  {

                        for(int j=0;j<Nb;j++)

                              w[r*Nk+i][j] = w[r*Nk-4+i][j] ^ w[r*Nk-1+i][j];

                  }

             }

       }

}

}

б) Начальная операция ¾ AddRoundKey — суммирование с основным ключом.

void AddRoundKey( unsigned char **state, unsigned char **w)

{

for(int i=0;i<Nk;i++)

for(int j=0;j<Nb;j++)

       state[i][j] = w[i][j] ^ state[i][j] ; //Операция XOR

в) 9 раундов из четырех шагов каждый.

- SubBytes — замена байтов state по таблице замен.

- ShiftRows — циклический сдвиг строк state.

- MixColumns — перестановка столбцов state.

- AddRoundKey — суммирование с раундовым ключом.

г) Заключительный 10-й раунд

- SubBytes — замена байтов state по таблице замен.

- ShiftRows — циклический сдвиг строк state.

- AddRoundKey — суммирование с раундовым ключом.

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

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

Содержание отчета

Отчет должен включать в себя следующие пункты:

1. Задание на выполнение лабораторной работы.

2. Исходный код программы.

3. Скриншоты, демонстрирующие операции шифрования и дешифрования.

Контрольные вопросы

1. Принципы шифрования в блочных шифрах.

2. Понятие симметричной криптосистемы.

3. Возможные размеры ключей в стандарте AES.

4. Как появились названия AES и Rijndael.

5. Основные преобразования, используемые в AES.

Мы поможем в написании ваших работ!