Слабые ключи итеративного шифра

Понятие слабого ключа, впервые введенное при анализе Л?5-алгоритма, связано со свойствами ключевого расписания и естественно обобщается на итеративные СБШ.

Криптографическая стойкость итеративного СБШ тем выше, чем ближе свойства шифрующей подстановки Е_к к свойствам случайных подстановок. Такая близость подразумевает, что набор раундовых ключей …, д,. есть случайная выборка из множества Поскольку г много меньше, чем (), то последнее условие означает, что среди цикловых ключей …, д,.не должно быть одинаковых. В связи с этим условием было введено понятие слабого ключа.

Ключ k итеративного /'-циклового СБШ назовем [{-слабым, если набор раундовых ключей q_v…, <7_Г содержит р различных ключей, 1 < р < г. Слабый ключ — это 1-слабый ключ.

Покажем, насколько опасным может быть использование слабого ключа.

Теорема 15.3. Пусть k — слабый ключ итеративного г-раундового СБШ и d = ord ф_г/. Тогда при ключе k СБШ является т-раундовым, где т = = r (mod d).

4 При слабом ключе k, порождающем г одинаковых раундовых ключей, равных q, подстановка Е_к итеративного СБШ в соответствии с равенством (15.3) имеет вид E_k(x) = n_ffr+i((p_qyb (х). Разделим г на d с остатком: r= dq + т. Тогда (ф_г/)^г = (Ф_г/)^т, так как (ф_г/)" = е. Следовательно, подстановка Е_к реализует т-раундовый итеративный СБШ. ?

Следствие. Если в условиях теоремы 15.3 d / г и подстановки 5,_/о и я^₊₁ — взаимно обратные, то шифрующая подстановка Е_к является тождественной. [>

В шифрах с отбеливанием подстановки 5^₍ и взаимно обратные, если г/₀= q_t4__x.

Теорема 15.4. Если — слабый ключ.

• 2г-раундового шифра Фейстеля, то шифрующая подстановка Е_к — инволюция, имеющая 2^п неподвижных элементов.
• 4 В соответствии с теоремой 15.2 подстановки Е_к и Е_к^{ отличаются лишь взаимно обратным порядком использования раундовых ключей. При слабом ключе k порождаются 2г цикловых ключей, равных q, тогда при q₀ = q,+_x из равенства (15.6) имеем для всех х е V_2n

Тогда Е_к — инволюция (зашифрование блока на ключе k равносильно его расшифрованию).

Определим число единичных циклов в Е_к. Пусть 5,_/()(а) = (х), где а, х е g V_2n. Из выражения (15.9) следует, что а — неподвижный элемент Е_к х — неподвижный элемент подстановки Т^п(

g)^2r или равносильно: х — корень уравнения Т^п(ф_г/)^г(х) = (ф_г/)^_г(х). В соответствии с леммой 15.1 (Фг/)~^{Г =} ^(ф_(/УТ^п, тогда равносильно: х — корень уравнения (ф^)^г(х) = (ф_г/) ^гТ^п(х). Домножив это уравнение слева на ф"^г, получаем: х — корень уравнения х = Т^п(х)> где Tⁿ(x_v х₂) = (х₂, х_х) при х = (х_{, х₂). Значит, число единичных циклов в Е_к равно числу 2/7-битовых блоков вида (х, х), т. е. 2″. ?

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

В ключевом множестве DES имеются и 2™-слабые ключи, m = 1, 2, 3. В частности, имеется 12 различных 2-слабых ключей (их называют также полуслабыми), составляющих шесть пар ключей, где каждой паре ключей соответствует пара взаимно обратных подстановок шифра.

Число слабых ключей шифра ГОСТ 28 147–89 равно числу двоичных матриц размера 8×32 с одинаковыми строками, т. е. равно 2³².

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