Математический анализ российского алгоритма шифрования в сравнении с аналогом – победителем конкурса AES

Размещено на http://www.allbest.ru/

Волгоградский Государственный Аграрный университет Волгоград, Россия

Математический анализ российского алгоритма шифрования в сравнении с аналогом - победителем конкурса AES

Меликов А.В., Яковлев С. Л.

Разработанная интеллектуальная обучающая система (ИОС) алгоритмов шифрования Яковлев, С.Л. Разработка интеллектуальной обучающей системы современных алгоритмов шифрования / Магистерская диссертация под науч. рук. доц. А.В. Меликова. - Волгоград, Издательство ВолГАУ, 2015. - 101 с. позволяет проводить статистические исследования, примером которых является анализ «лавинного эффекта», т.е. определение зависимости каждого бита шифртекста от соответствующего бита открытого текста с учетом работы исходного ключа.

Математический анализ предлагается начать с алгоритма шифрования «Rijndael» - победителя конкурса AES [1].Предположим, что во входном 32-битовом значении изменен 1 бит. Первая операция функции шифрования - сложение по модулю 2³², т.е. с переносом из младших разрядов в старшие. Теоретически, изменение самого младшего бита операнда может привести к изменению всех битов суммы. При условии равновероятного и независимого распределения битов операндов на множестве {0,1} вероятность события «влияние одного бита операнда распространяется влево ровно на битов результата», равна 2^-n. Это означает, что если изменить значение 1 бита операнда на противоположное, то помимо соответствующего ему бита результата, который инвертируется в любом случае, ровно битов результата, находящихся левее инвертированного, также поменяют значение на противоположное с указанной выше вероятностью. Получаем, что при сложении двух чисел по модулю 2³² практическое значение имеет только влияние бита операнда на не более, чем 4 старших бита результата.

Теперь рассмотрим диффузионные характеристики алгоритма «Rijndael». Первая операция раунда шифрования алгоритма - побитовое суммирование с ключом по модулю 2 - не приводит к выходу изменения за пределы 1 бита. Следующая операция - замена по таблице - распространяет изменение в 1 бите на весь байт. Следующий за ней построчный байтовый сдвиг не изменяет ничего. Наконец, завершающая операция раунда - перемешивание байтов в столбцах матрицы - приводит к диффузии изменения на весь столбец. Таким образом, за 1 раунд шифрования изменение в 1 бите входных данных окажет влияние на 1 столбец матрицы данных. На следующем раунде шифрования эти байты в ходе операции построчного байтового сдвига будут «разведены» по разным столбцам, и в результате последующей операции перемешивания байтов в столбцах исходное изменение распространится на 4 столбца. Диаграмма диффузии в алгоритме-финалисте конкурсаAES приведена на рисунке 1.

Таким образом, при шифровании исходного текста изменение в одном бите входных данных распространяется на весь блок ровно за два раунда. В результате за 10-14 раундов алгоритма шифрования «Rijndael» данные успевают полностью перемешаться пять-семь раз.

интеллектуальный шифрование лавинный бита

Рисунок 1 - Диффузия изменения в исходных данных в процессе шифрования «Rijndael»

Сформулируем основные достоинства и недостатки отечественного стандарт шифрования «ГОСТ Р 28147-89» ГОСТ 28147-89. Группа П85. Государственный стандарт союза ССCР. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. ОКП 40 4000.Дата введения 1990-07-01. . Исходя из рассуждений Б. Шнайера [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. Официальная страница NIST США [Электронный ресурс]. - 2015. - Режим доступа: http://csrc.nist.gov/archive/aes/index.html.

2. Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. Пер. с англ. / Б. Шнайер. - М.: Издательство «Триумф», 2012. - 816 с.

3. Сонг Й. Ян. Криптоанализ RSA / Пер. с англ. Ю. Айдарова. - М.: Издательство «Институт компьютерных исследований», 2011. - 312 с.

Размещено на Allbest.ru