Алгебраический анализ. 
Криптографическая защита информации: симметричное шифрование

Сущность алгебраических методов анализа заключается в получении уравнений, описывающих нелинейные преобразования замены S-блоков, с последующим решением найденных систем уравнений и получением ключа шифрования. Данный метод криптоанализа относится к атакам с известным открытым текстом, поэтому для успешного анализа достаточно иметь одну пару открытый текст/шифр-текст. Алгебраические методы криптоанализа состоят из следующих этапов:

• — составление системы уравнений, описывающей преобразования в нелинейных криптографических примитивах анализируемого шифра (чаще всего для симметричных алгоритмов шифрования такими нелинейными компонентами являются Sблоки замены);
• — решение полученной системы уравнений.

Рассмотрим подробнее первый этап алгебраического криптоанализа. Для шифров, подобных Rijndacl, при составлении уравнений используется таблица замены S-блоков. Ограничимся рассмотрением одночленов, состоящих из произведения двух переменных. Тогда уравнения, описывающие работу S-блоков, имеют вид [21]:

где XjXj — комбинация входных битов S-блока; у, У1 — комбинация выходных битов S-блока;

Xjyj — комбинация входных и выходных битов;

Xj и у; - соответственно входные и выходные биты S-блока; ц — коэффициент, принимающий значения 0 или I.

При получении уравнений нужно рассмотреть все возможные комбинации данных одночленов. В случае, когда число битов на входе S-блоков равно s, получаем, что число одночленов,.

2s

встречающихся в системе, вычисляется по формуле t= +2s+l и включает в себя входные и выходные значения S-блока (2s),.

(2s

все их возможные произведения ^ J и коэффициент г|. Число всех возможных комбинаций одночленов составляет 2'.

Для произвольного блока замены число линейно независимых уравнений r>t-2^s.

Для проверки всех полученных комбинаций на соответствие заданному S-блоку требуется составить таблицу истинности на основании замен, выполняемых в исследуемом S-блоке (табл. 39).

Для проверки комбинаций на соответствие таблице истинности следует осуществить построковую подстановку значений одночленов из таблицы и выполнить операцию сложения по модулю 2. Таким образом, для каждой комбинации выполняется подстановка и сложение для всех возможных входных значений S-блока (2^s раз). Результаты суммирования сравниваются с нулем. Если для всех строк таблицы истинности равенство оказывается верным, то уравнение, заданное данной комбинацией одночленов, удовлетворяет таблице замены исследуемого S-блока, и его следует отобрать для составления искомой системы. Далее необходимо провести анализ уравнений и выбрать для формирования системы линейно независимые уравнения, содержащие минимальное число нелинейных элементов.

Таблица 39.

Общий вид таблицы истинности для S-блока.

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

XL-метод (extended Linearization) предложен Nicolas Courtois, Alexander Klimov, Jacques Patarin и Adi Shamir в работе [22].

Пусть имеется нелинейная система, содержащая m уравнений и 2s переменных. XL-метод базируется на умножении каждого уравнения l… m на произведения переменных степени, меньшей или равной D-2. Рассмотрим вычисление параметра D алгоритма XL атаки. При умножении исходных уравнений системы на одночлены степени <(D-2) получаем примерно.

(2s) «__.

R я т новых уравнении. Оощсс число одночленов,.

ID-2J.

встречающихся в этих уравнениях, составляет r = f^J. Так как система будет решаться способом линеаризации, то есть путем замены всех нелинейных одночленов на новые переменные, необходимо чтобы число уравнений было больше числа.

( 2. v ^ Г2лЛ одночленов R = т > = Т . Отсюда получаем, что.

1°-2/ W.

^f2s' ^ 2s ' э Э 2.S.

m > / «(2sг ID^A. Следовательно, D «—==. При этом.

_KDJ (D-2J v/?7.

должно выполняться условие D>2, иначе не будет получено новых уравнений, гак как степень отобранных для умножения уравнений одночленов, определяемая разностью D-2, будет равна нулю.

Алгоритм XL метода состоит из двух шагов.

• 1. Multiply — умножение каждого уравнения исходной системы на произведение переменных в степени < D-2.
• 2. Linearize — замена каждого одночлена в степени < D на новую переменную и применение метода исключения Гаусса.

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

Болес подробно об алгебраическом криптоанализе различных блочных алгоритмов шифрования можно прочитать в работах [21−25].