- •Глава 6. Блочные шифры гост 28147-89 и rijndael
- •6.1. Схемы шифрования гост 28147-89 и Rijndael
- •6.2. Сравнение раундов шифрования гост 28147-89 и Rijndael
- •6.3. Формирование ключевых элементов
- •6.4. Выбор узлов замен и констант, диффузионные характеристики
- •6.5 Показатели стойкости, производительность и удобство реализации алгоритмов
- •Вопросы к главе 6
6.2. Сравнение раундов шифрования гост 28147-89 и Rijndael
Алгоритм ГОСТ реализует относительно несложную функцию шифрования, состоящаю из операции сложения по модулю входного полублока с ключевым элементом раунда, восьми подстановок, выполняемых независимо в восьми тетрадах, и битовой перестановки – вращения на 11 бит в сторону старших разрядов.
Схема раунда шифрования по ГОСТ изображена на рис. 6.1а.
В Rijndael шифруемый блок и его промежуточные состояния в ходе преобразования представляются в виде матрицы байтов , где, в зависимости от размера блока.
Аналог цикловой функции шифрования в алгоритме Rijndael состоит из трех следующих элементарных преобразований, выполняемых последовательно.
1. Байтовая подстановка: каждый байт блока заменяется новым значением из общего для всех байтов матрицы вектора замены.
2. Побайтовый циклический сдвиг строк матрицы: первая строка остается неизменной, вторая строка сдвигается влево на один байт, третья и четвертая строка для сдвигаются влево на 2 и 3 байта соответственно, а дляна 3 и 4 байта.
3. Умножение матриц (смешивание колонок): полученная на предыдущем шаге матрица умножается слева на матрицу-циркулянт размера 4х4, где
.
Операции с элементами матриц (сложение и умножение) выполняются в конечном поле , порожденном неприводимым надполиномом.
В этом поле сложение байтов выполняется как побитовое суммирование по mod 2. При умножении двух байтов, каждый из них преобразуется в многочлен, вектор коэффициентов которого является последовательностью битов, образующих соответствующий байт. Эти многочлены перемножаются над , а затем вычисляется вычет произведения по модулю. Коэффициенты вычета составляют байт, являющийся результатом операции.
Схема раунда алгоритма Rijndael изображена на 6.2 б.
Рис. 6.2. Схема преобразования данных для 1-го раунда шифрования по алгоритмам ГОСТ 28147-89 (а) и Rijndael (б).
Обозначения, принятые на рис. 6.2 обозначают следующее:
–преобразуемый алгоритмом Rijndael блок;
старший и младший полублоки на входе раунда ГОСТ соответственно;
старший и младший полублоки на выходе раунда ГОСТ соответственно;
–ключевой элемент раунда;
–функция подстановки – группами по 4 бита для ГОСТ и байтами для алгоритма Rijndael;
–операция циклического сдвига 32-битового слова на 11 битов в сторону старших разрядов;
–операция построчного вращения матрицы в алгоритме Rijndael;
–умножение в алгоритме Rijndael матрицы промежуточных данных слева на матрицу .
Если в алгоритме ГОСТ перестановку полублоков отнести к раунду шифрования, как это показано на рисунке 6.2а, то можно заметить, что в обоих алгоритмах все раунды шифрования идентичны друг другу, за исключением последнего раунда, в котором отсутствует часть операций.
Такой подход позволяет получить наиболее компактную реализацию, как аппаратную, так и программную.
В последнем раунде ГОСТа отсутствует операция перестановки полублоков шифруемого блока, в последнем раунде алгоритма Rijndael – умножение слева на матрицу .
В обоих обсуждаемых алгоритмах это сделано для того, чтобы обеспечить эквивалентность структуры прямого и обратного шифрующих преобразований, о чем будет речь далее.
В алгоритме ГОСТ эквивалентность структуры прямого и обратного криптографического преобразования не обеспечивается специально, а является простым следствием использованного архитектурного решения.
В любой однородной сбалансированной сети Файстеля оба эти преобразования алгоритмически идентичны и различаются только порядком использования ключевых элементов: при расшифровании элементы используются в порядке, обратном тому, в котором они используются при зашифровании.
Шифр Rijndael построен на базе прямых преобразований. Как и для всех подобных алгоритмов, обратное преобразование строится из обращений шагов прямого преобразования, применяемых в обратном порядке.
В силу сказанного, обеспечить такую же степень идентичности прямого и обратного преобразования, которая достигается в сетях Файстеля, не представляется возможным.
Однако за счет алгоритмических решений можно достичь идентичности прямого и обратного преобразований с точностью до используемых в преобразованиях констант.
В таблице 6.2 представлены последовательности операций двух последних раундов алгоритма Rijndael, их формальное обращение, а также модифицированное обратное преобразование, которое построено с учетом соотношений между параметрами и алгоритмически подобное прямому.
Таблица 6.2. Два последних раунда алгоритма Rijndael и их обращение
Прямое преобразование |
Обратное преобразование |
Обратное преобразование (модифицированное) |
X=XkR-1 |
X=XkR+1 |
X=XkR+1 |
X=S(X) |
X=R(X) |
X=S-1(X) |
X=R(X) |
X=S-1(X) |
X=R(X) |
X=MX |
X=XkR |
X=M-1X |
X=XkR |
X=M-1X |
X=X( M-1kR) |
X=S(X) |
X=R(X) |
X=S-1(X) |
X=R(X) |
X=S-1(X) |
X=R(X) |
X=XkR+1 |
X=XkR-1 |
X=XkR-1 |
Через обозначена обратная коперация циклического сдвига строк матрицы. Как видно из первых двух столбцов таблицы 6.2, алгоритмическая структура прямого и обратного преобразований существенно различается. Однако путем тождественных преобразований можно добиться большего соответствия между ними.
Прежде всего, отметим, что операция побайтовой замены коммутативна с процедурой побайтового сдвига строк матрицы:
.
Кроме того, согласно правилам матричной алгебры по закону ассоциативности можно также поменять порядок побитового прибавления ключа по модулю два и умножения на матрицу:
Применяем указанные изменения ко второму столбцу таблицы 6.2, получаем в третьем столбце модифицированную последовательность операций при двух раундах обратного преобразования:
Сравнение 1-го и 3-го столбцов таблицы свидетельствует о том, что алгоритмическая структура прямого и обратного преобразований идентична. Результат легко обобщается на произвольное число раундов.
Таким образом, в алгоритме Rijndael процедуры зашифрования и расшифрования алгоритмически идентичны и различаются только в следующих деталях:
– в обратном преобразовании используется вектор замен, обратный в операционном смысле вектору замен прямого преобразования;
– в обратном преобразовании число байтов, на которые сдвигается каждая строка матрицы данных в операции построчного байтового сдвига другое;
– в обратном преобразовании в шаге матричного умножения блок данных умножается слева на матрицу
,
обратную той, что используется при прямом преобразовании;
– в обратном преобразовании ключевые элементы используются в обратном порядке, и, кроме того, все элементы за исключением первого и последнего, должны быть умножены слева на матрицу .
Таким образом, аналогично ГОСТу, в алгоритме Rijndael возможно совместить реализацию процедур шифрования как при аппаратной, так и при программной реализации.