On key schedule for block ciphers without week keys.pdf Введение Используем следующие обозначения: Vn - множество двоичных n-мерных векторов, n Е N; X^ = {ж0, Xi,...} -последовательность над множеством X; Г(А) -граф автомата Мили A; (H) - линейная оболочка множества векторов H. Свойства ключевого расписания, характеризующие взаимосвязи основного ключа с раундовыми ключами, являются определяющими при оценке стойкости итеративного блочного шифра (ИБШ) относительно ряда методов криптоанализа: согласования, дифференциального и др. Например, нежелательно ключевое расписание, при котором генерируемая из основного ключа последовательность раундовых ключей содержит определённое число повторяющихся элементов. Так, по отношению к основному ключу при криптографическом анализе DES-алгоритма введено понятие слабого ключа, то есть основного ключа, порождающего 16 одинаковых раундовых ключей. В [1, с. 298] для r-раундового блочного алгоритма это понятие обобщено до ^-слабого ключа, порождающего в наборе раундовых ключей q1,... , qr ровно ^ различных элементов, 1 ^ ^ < r. Показано, что при определённых условиях использование слабых ключей может привести к негативным последствиям с точки зрения обеспечения конфиденциальности данных. Криптографические свойства ИБШ считаются хорошими, если шифрующие подстановки близки по свойствам к случайным подстановкам, в частности, когда набор раундовых ключей qi , . . . , qr есть случайная бесповторная выборка из множества двоичных векторов заданной размерности. В связи с этим возникает задача построения ключевого расписания, исключающего возможность повторений раундовых ключей в генерируемом наборе. 1. Постановка задачи Рассмотрим ключевое расписание в для итеративного r-раундового блочного алгоритма, n, m, r Е N. Функция в : Vn ^ Vmr отображает основной n-битовый ключ k = (k1,... , kn) в набор m-битовых раундовых ключей q1,..., qr. Функцию в зададим системой координатных функций {в1,... , вг}, где в^ : Vn ^ Vm отображает основной n-битовый ключ в раундовый ключ q^, i = 1,... , r. Обычно выполнены соотношения m < n < mr, при этих соотношениях функция в не сюръективная и, следовательно, система функций {в1,... , вг} алгебраически зависимая. Требуется построить функцию в со свойством: при любом ключе (k1,..., k„)EV„ набор в1(к1,... , kn),... , вг (k1,... , kn) состоит из r различных m-мерных векторов. Такую функцию в назовем ключевым расписанием без слабых ключей. В [2] такая функция построена на основе генератора «1-2 шага». 2. Бесповторность последовательностей и автономных автоматов Последовательности X^ = {x0,x1,...} над конечным множеством X однозначно соответствует последовательность r-грамм X^ = {(x^, xi+1,... , xi+r-1)}, где i = 0,1,..., / - r для конечной последовательности X^ длины / > r и i = 0,1, 2,..., если X^ бесконечная. Назовём r-грамму (x0,x1,... ,xr-1) бесповторной, если x^ = xj при i = j, i, j E 0,1,..., r - 1. Последовательность X^ назовём r-бесповторной, если последовательность X^ состоит из бесповторных r-грамм (тогда X^ является p-бесповторной, где 1 ^ p ^ r). Показателем бесповторности X^ (обозначается urpX^) назовём наибольшее r, при котором X^ является r-бесповторной. Из определений следует, что периодическая последовательность X^ с длиной периода t является r-бесповторной, если бесповторными являются r-граммы (xi, xi+1, . . . , xi+r-1) , i = 0, 1,...,t - 1. Пусть A = (S, Y, h, /) -перестановочный автономный автомат, где S, Y - соответственно внутренний и выходной алфавиты; h : S ^ S - биективная функция переходов; / : S ^ Y - функция выходов. Известно, что автомат A при начальном состоянии s0, проходя периодическую последовательность состояний {s0,s1, ...,sT-1} с длиной периода т, генерирует периодическую выходную последовательность {y0,y1,... , yT-1} с длиной периода t, где t делит т, = /(sj), i = 0,1,... Рассмотрим слабо инициальный автомат [1, с. 148] (A,W) = ((S, W),Y, h, /), 0 = = W С S, где W - множество допустимых начальных состояний автомата. В частности, при фиксированном начальном состоянии s Е S имеем инициальный автомат (обозначаемый As). Автомат A (автомат (A, W)) называется r-бесповторным, если r-бесповторной является выходная последовательность автомата при любом начальном состоянии s Е S (s Е W). Показателем бесповторности автомата A (автомата (A, W), инициального автомата As) назовём наибольшее натуральное r, такое, что выходная последовательность автомата A является r-бесповторной при любом начальном состоянии s Е S (при любом s Е W, при фиксированном s Е S). Обозначим показатели бесповторности автоматов A, (A, W) и As соответственно через urpA, urp(A, W) и urpAs. Утверждение 1. а) urpA = min{urpAs}, urp(A, W) = min{urpAs}; ses sew б) urpAs не превышает длины периода выходной последовательности автомата As; в) если состояния s и z принадлежат общему циклу графа автомата A, то urpAs = urpAz. 3. Схема ключевого расписания без слабых ключей Пусть p,m, u Е N, где 1 < p ^ u ^ r. Обозначим A = (Vp,VU, h, /) - автономный автомат, где Vp - внутренний алфавит, VU - выходной алфавит, h : Vp ^ Vp - функция переходов, / : Vp ^ Vu - функция выходов; G = (V^, Vm, ф) - автомат с постоянной памятью [1, с. 148], т.е. внутренне автономный автомат с тождественной функцией переходов, где Vu - входной алфавит, Vum - внутренний алфавит, Vm - выходной алфавит. Определим функцию выходов ф : Vu х Vum ^ Vm - если в памяти автомата G записана система векторов k(1),..., k(u) из Vm, то = a1 k(1) ф ... ф auk(u) при входном символе a = (а1,..., au) Е Vu. Рассмотрим последовательное соединение управляющего автономного автомата A и генерирующего автомата G, обозначаемое A ^ G. Представим n-битовый секретный ключ k в виде набора m-битовых подключей: k = (k(1),... , k(u)). Теорема 1. Если автомат As генерирует t-бесповторную периодическую последовательность с длиной периода t и в памяти автомата G записана линейно независимая система векторов k(1),..., k(u), то автомат (A ^ G)z генерирует при z = (s,k(1),..., k(u)) t-бесповторную периодическую последовательность с длиной периода t и urp(A ^ G)z = t. Доказательство. Выходная последовательность автомата A ^ G состоит из элементов линейной оболочки (k(1),... , k(u)). Если a, в Е Vu и a = в, то ф^,^1), ...,k(u)) = ф(в, k(1),... , k(u)) в силу линейной независимости системы векторов Тогда в силу t-бесповторности выходной последовательности автомата As последовательность {ф(ai, k(1),... , k(u)) : i = 0,1,...,t - 1} состоит из различных векторов, то есть автомат (A ^ G)z является t-бесповторным. Вместе с тем ф(^, k(1),..., k(u)) = ф(ai+t, k(1),..., k(u)), i = 0,1,..., значит, urp(A ^ G)z = t. ■ 4. Выбор параметров ключевого расписания без слабых ключей Рассмотрим данную схему в качестве альтернативы ключевому расписанию блочного шифра ГОСТ 28147-89. Параметры в этом случае принимают значения p = u = 8, m = 32. Автомат A построим на основе линейного регистра сдвига длины 8 с примитивным характеристическим многочленом, выходными символами являются 8-граммы (байты) линейной рекуррентной последовательности. Следовательно, автомат A генерирует 255-бесповторную последовательность байтов. В соответствии с теоремой 1 автомат (A ^ G)z при любом ненулевом состоянии s автомата A и линейно независимой системе векторов генерирует 255-бесповторную периодическую последовательность 32-битовых векторов с длиной периода 255 и urp(A ^ G)z = 255. Для ключевого расписания без слабых ключей 32-раундового блочного шифра достаточно взять любую бесповторную выборку размера 32 из выходной последовательности автомата (A ^ G)z, полученную при любом ненулевом состоянии s автомата A. Ограничение на секретный ключ, связанное с линейной независимостью векторов, не является сильным. Если векторы выбраны случайно равновероятно 7 из V32, то вероятность линейной независимости системы равна ]/[(1 - 2i-32), то есть i=0 превышает 1 - 224.

Скачать электронную версию публикации