Лекции по криптологии / Y28_M03_L15

Лекция 15. Слабые и сильные ключи в алгоритме ГОСТ 28147-89.

15.1. Выражение псевдогаммы для режима простой замены.

Влияние долговременного ключа на выходы циклов (последовательность ) можно проследить, исходя из того, что блок || поразрядно отличается от входного блока ||, на слагаемое ||, где подблоки и являются линейными комбинациями вида .

Действительно, по определению, .

Таким образом, из и следует .

По индукции: , .

Аналогично, , .

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

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

Рассмотрим долговременный ключ как таблицу, колонки которой являются правыми частями булевых функций от четырех переменных.

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

Наименьшее (на два бита) возможное преобладание нулей в колонке соответствует распределению вероятностей единицы и нуля при котором .

Действительно, пусть количество нулей и единиц в колонке равно и соответственно.

Очевидно, сумма нулей и единиц равна , а их разность равна преобладанию: . Поэтому - минимальное четное число большее нуля, т.е. , откуда .

Легко получить формулу для вычисления вероятности нуля в сумме из битов, при заданном преобладании : .

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

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

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

15.2. Зависимость стойкости долговременного ключа от качества псевдогаммы.

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

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

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

Аналогично, не удается полностью описать и множество сильных ключей, но очень часто возникает ситуация, когда можно выявить часть множества сильных ключей, достаточную для приложений.

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

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

Назовем псевдогаммой, поскольку гамма, используемая в шифре гаммирования, от открытого текста не зависит.

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

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

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

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

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

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

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

Однако набор можно получить, выбирая их не одновременно, а последовательно, что эквивалентно выбору значений четырех функций (для каждого узла замены - своих) .

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

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

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

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

15.3. Возможность ослабления режима простой замены за счет структуры сеансового ключа.

Заметим, что выбор с равновероятным распределением битов в колонках, строго говоря, не обеспечивает качественную псевдогамму ||, т.к. для каждого существуют блок и сеансовый ключ , такой, что .

Действительно, рассмотрим четырехцикловой алгоритм с последовательностью и пусть . Если выход после четвертого цикла имеет вид ||, то дополнительное преобразование его не меняет. Заметим, что для . Поэтому для восьмициклового с последовательностью получим .

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

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

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