Разработанная интеллектуальная обучающая система (ИОС) алгоритмов шифрования [1] позволяет проводить статистические исследования, примером которых является анализ «лавинного эффекта», т.е. определение зависимости каждого бита шифртекста от соответствующего бита открытого текста с учетом работы исходного ключа.
Математический анализ предлагается начать с алгоритма шифрования «Rijndael» – победителя конкурса AES [1].Предположим, что во входном 32-битовом значении изменен 1 бит. Первая операция функции шифрования – сложение по модулю 232, т.е. с переносом из младших разрядов в старшие. Теоретически, изменение самого младшего бита операнда может привести к изменению всех битов суммы. При условии равновероятного и независимого распределения битов операндов на множестве {0,1} вероятность события «влияние одного бита операнда распространяется влево ровно на n бит результата», равна 2-n. Это означает, что если изменить значение 1 бита операнда на противоположное, то помимо соответствующего ему бита результата, который инвертируется в любом случае, ровно n битов результата, находящихся левее инвертированного, также поменяют значение на противоположное с указанной выше вероятностью. Получаем, что при сложении двух чисел по модулю 232 практическое значение имеет только влияние бита операнда на не более, чем 4 старших бита результата.
Теперь рассмотрим диффузионные характеристики алгоритма «Rijndael». Первая операция раунда шифрования алгоритма – побитовое суммирование с ключом по модулю 2 – не приводит к выходу изменения за пределы 1 бита. Следующая операция – замена по таблице – распространяет изменение в 1 бите на весь байт. Следующий за ней построчный байтовый сдвиг не изменяет ничего. Наконец, завершающая операция раунда – перемешивание байтов в столбцах матрицы – приводит к диффузии изменения на весь столбец. Таким образом, за 1 раунд шифрования изменение в 1 бите входных данных окажет влияние на 1 столбец матрицы данных. На следующем раунде шифрования эти байты в ходе операции построчного байтового сдвига будут «разведены» по разным столбцам, и в результате последующей операции перемешивания байтов в столбцах исходное изменение распространится на 4 столбца. Диаграмма диффузии в алгоритме-финалисте конкурса AES приведена на рисунке.
Таким образом, при шифровании исходного текста изменение в одном бите входных данных распространяется на весь блок ровно за два раунда. В результате за 10-14 раундов алгоритма шифрования «Rijndael» данные успевают полностью перемешаться пять-семь раз.
Диффузия изменения в исходных данных в процессе шифрования «Rijndael»
Сформулируем основные достоинства и недостатки отечественного стандарт шифрования «ГОСТ Р 28147-89» [2]. Исходя из рассуждений Б. Шнайера [2], невосприимчивость алгоритма «ГОСТ Р 28147-89» к дифференциальному и линейному криптоанализу плюс большое количество раундов означают, что российский стандарт шифрования является достаточно надежным. К тому же, лобовое вскрытие данного алгоритма абсолютно невозможно из-за 256-битного ключа, а также возможности использования секретных значений узла замены.
При сравнении производительности алгоритмов «ГОСТ Р 28147-89» и «Rijndael» на 32-битных платформах, российский стандарт шифрования медленнее криптостандарта США, но это разница составляет всего 10-20 % [3]. Преимущество алгоритма AES невелико, потому что отечественный криптостандарт был принят на 10 лет раньше от начала конкурса AES. Однако алгоритм «ГОСТ Р 28147-89» имеет, как минимум, два существенных недостатка:
- основные операции выполняются над 32-битными «полублоками». Алгоритм проигрывает в скорости в 4 раза байт-ориентированному «Rijndael» на 8-битных платформах;
- в тексте стандарта отсутствуют четкие критерии выбора узлов замены. Достаточно часто высказываются опасения, что существуют слабые узлы замены.
Рассмотрим устойчивость обоих алгоритмов к известным видам криптоанализа. Наиболее универсальными и эффективными для алгоритмов широкого класса являются дифференциальный и линейный виды криптоанализа. Дать оценку устойчивости алгоритма «ГОСТ Р 28147-89» к конкретным видам криптоанализа невозможно без спецификации узлов замен, так как качество этого шифра зависит от качества использованных узлов. Но исследования близких по архитектуре шифров с заданными таблицами подстановок показали, что криптоанализ шифра с 16 раундами в принципе осуществим, но требует очень большого числа исходных данных, а при 20-24 раундах становится теоретически бесполезным. Отечественный стандарт шифрования предусматривает 32 раунда шифрования, и этого количества хватает с запасом, чтобы успешно противостоять указанным видам криптоанализа.
По оценкам разработчиков шифра AES, уже на 4 раундах шифрования этот алгоритм приобретает достаточную устойчивость. Теоретической границей, за которой линейный и дифференциальный виды криптоанализа теряют смысл, является рубеж в 6 раундов. Согласно спецификации, в шифре предусмотрено 10-14 раундов. Следовательно, шифр AES также устойчив к указанным видам криптоанализа с определенным запасом. Таким образом, сравниваемые шифры обладают достаточной стойкостью к известным видам криптоанализа. В печати отсутствуют какие-либо сведения об успешных случаях вскрытия указанных шифров, а также описания процедур, которые теоретически позволили бы дешифровать сообщение с меньшими вычислительными затратами, чем полный перебор по всему ключевому пространству.
Рассмотренные алгоритмы обладают сопоставимыми характеристиками быстродействия при реализации на 32-битовых платформах. На 8-битовых платформах картина, вероятно, сходная. Что касается аппаратной реализации, то в отличие от «ГОСТ Р 28147-89», алгоритм шифрования AES позволяет достичь высокой степени параллелизма при выполнении шифрования, оперирует блоками меньшего размера и содержит меньшее число раундов, в силу чего его аппаратное воплощение может оказаться существенно более быстрым. Преимущество длины наибольшего пути в сетевом представлении примерно четырехкратное.
Проведенное выше сопоставление параметров российского стандарта шифрования и алгоритма шифрования AES, принятого за стандарт шифрования США, показало, что, несмотря на различие в архитектурных принципах этих шифров, их основные рабочие параметры сопоставимы. Исключением является тот факт, что «Rijndael»имеет значительное преимущество в быстродействии перед «ГОСТ Р 28147-89» при аппаратной реализации на базе одной и той же технологии. Очевидным шагом в оптимизации отечественного алгоритма шифрования, считаем, является переход байтовым заменам, что должно повысить стойкость алгоритма к известным видам криптоанализа.
[1] Яковлев, С.Л. Разработка интеллектуальной обучающей системы современных алгоритмов шифрования: Магистерская диссертация / под науч. рук. доц. А.В. Меликова. – Волгоград: ВолГАУ, 2015. – 101 с.
[2] ГОСТ 28147-89. Группа П85. Государственный стандарт союза ССCР. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. ОКП 40 4000.Дата введения 1990-07-01.
Библиографическая ссылка
Меликов А.В., Яковлев С.Л. МАТЕМАТИЧЕСКИЙ АНАЛИЗ РОССИЙСКОГО АЛГОРИТМА ШИФРОВАНИЯ В СРАВНЕНИИ С АНАЛОГОМ – ПОБЕДИТЕЛЕМ КОНКУРСА AES // Международный студенческий научный вестник. – 2016. – № 3-1. ;URL: https://eduherald.ru/ru/article/view?id=14772 (дата обращения: 21.11.2024).