Харин Ю.С., Берник В.И., Матвеев Г.В. Математические основы криптологии. — Минск: Изд-во БГУ, 1999. — 319 с. Бабаш А.В., Шанкин Г.П. Криптография.





УДК 621.391: 519.7

А. Н. Алексейчук
Специальный факультет СБ Украины в составе Военного института
телекоммуникаций и информатизации НТУУ «КПИ»
ул. Московская, 45/1, 01011 Киев, Украина
Критерий примитивности группы подстановок,
порожденной раундовыми преобразованиями
Rijndael-подобного блочного шифра

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

Одной из важных задач, связанных с повышением информационной безопасности современных телекоммуникационных систем, является совершенствование криптографических методов и средств защиты информации, циркулирующей в этих системах. К таким средствам относятся, в частности, блочные шифры (БШ), широко используемые в автоматизированных системах обработки данных для обеспечения конфиденциальности передаваемой или хранимой информации.
При изучении криптографических свойств блочных шифров, не связанных с особенностями их технической (программной) реализации или процессами функционирования соответствующих шифрующих устройств, как правило, используются две основные математические модели БШ: алгебраическая и вероятностная [1, 2]. В настоящей статье рассматривается алгебраическая модель блочно-итера-ционного шифра, формальное описание которой приведено ниже.
Пусть даны конечная абелева группа G, непустые конечные множества K, ( и семейство (fk: Gn ( Gn, k ( K) взаимно однозначных преобразований множества Gn = {(g1, , gn): gi ( G, 13 EMBED Equation.3 1415}. Согласно определению [1], r-раундовый блочно-итерационный шифр ( c множеством открытых (шифрованных) сообщений Gn, множеством ключей (, множеством тактовых ключей K, расписанием ключей

А. Н. Алексейчук
(: ( ( Kr и функцией шифрования F: Gn(( ( Gn представляет собой систему (Gn, (, K, F, () такую, что для любых x ( Gn, ( ( ( выполняется равенство

F(x, () = fk(r) fk(1)(x),

где (k(1), , k(r)) = ((() и fk(r) fk(1) есть произведение (последовательное выполнение) указанных преобразований. Элементы k(1), , k(r) называются тактовыми ключами, а отображения fk(1), , fk(r) раундовыми шифрующими преобразованиями шифра ( в тактах (раундах) шифрования с номерами 1, , r соотвественно.
Как правило, при анализе стойкости данного блочного шифра ( относительно криптоаналитических атак, не использующих конкретные особенности расписания ключей (, в приведенном выше определении полагают ( = Kr, ((() = ( = = (k(1), , k(r)), т.е. считают, что последовательность тактовых ключей может быть произвольным элементом множества Kr. В дальнейшем это соглашение принимается в настоящей статье.
Одним из общих требований к современным блочным шифрам является их обоснованная стойкость относительно алгебраических методов криптоанализа, основанных на группировании открытых, шифрованных сообщений или ключей шифра в классы эквивалентных (или близких, в том или ином смысле) объектов, позволяющем понизить трудоемкость алгоритмов решения соответствующих криптоаналитических задач. Стойкость БШ к подобным методам криптоанализа, получившим в ряде публикаций название методов гомоморфных образов или гомоморфизмов [2–4], как правило, определяется алгебраическими свойствами различных групп подстановок, связанных с системой раундовых преобразований данного блочного шифра (.
Обозначим через G(() = 13 EMBED Equation.3 1415 подгруппу симметрической группы множества Gn, порожденную подстановками fk: Gn ( Gn, k ( K. Напомним [5], что группа G(() называется транзитивной, если для любых x, y ( Gn существует подстановка g ( G(() со свойством g(x) = y. Транзитивная группа G(() называется импримитивной, если она имеет нетривиальный блок (т.е. такое множество ( ( ( Gn, что 1 < ((( < (Gn(, и для любого g(G(() выполняется одно из условий g(() = (, g(() ( ( = (), и примитивной в противном случае.
Изучению взаимосвязи между криптографической стойкостью шифра ( и свойствами группы G(() посвящены статьи [6–10] и ряд других работ. В частности, в [6, 7, 10] показано, что необходимым условием стойкости шифра ( к определенным алгебраическим атакам на основе известных или подобранных открытых сообщений является выполнение следующих требований:
группа G(() примитивна;
эта группа имеет достаточно большой порядок (например, такой, при котором исключена возможность практического перечисления всех шифрующих преобразований F( = fk(r) fk(1), ( ( ( в r раундах шифрования).
В [6] показано также, что импримитивность группы G(() может свидетельствовать о наличии в конструкции шифра (, так называемых «потайных лазеек», существенно снижающих его практическую стойкость. В доказательство этого в [6] приводится пример 32-раундового шифра с длинами блока и ключа шифрования, равными соответственно 64 и 80 битам. Этот шифр по своей структуре аналогичен алгоритму DES, за исключением конструкции s-блоков, и, как показано в [6], является практически стойким к линейному и разностному криптоанализу. Вместе с тем, импримитивность группы данного шифра позволяет осуществить на него алгебраическую атаку с использованием 232 подобранных открытых текстов.
Необходимо отметить, что на практике вычисление группы, порожденной раундовыми шифрующими преобразованиями данного блочного шифра (, как правило, представляет собой достаточно трудную задачу, которая становится практически неразрешимой при отсутствии полной информации о криптографической схеме шифра. В этом случае скрытые в конструкции шифра «лазейки», основанные на импримитивности указанной группы подстановок, практически не удается обнаружить [6]. Таким образом, установление факта примитивности группы G(() является первым шагом на пути обоснования стойкости шифра ( к алгебраическим атакам и отсутствия в конструкции этого шифра определенных cкрытых «лазеек».
Целью настоящей статьи является доказательство теоремы, устанавливающей необходимые и достаточные условия примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра [11]. (Эти шифры получили свое название в честь нового американского стандарта шифрования данных, утвержденного в США в 2001 году [12]). Приведенные ниже условия примитивности группы G(() допускают простую алгоритмическую проверку; в частности, с их помощью нетрудно показать, что раундовые преобразования шифра Rijndael порождают примитивную группу подстановок.
Приведем точные определения основных понятий, используемых в дальнейшем изложении. Рассмотрим блочный шифр ( = (Gn, (, K, F, () над алфавитом Gn, где G является аддитивной группой конечного поля порядка q = 2l, ( = Kr и K = Gn.
Шифр ( называется Rijndael-подобным [11], если существуют подстановки s1, , sn на множестве G и невырожденное линейное преобразование M векторного пространства Gn над полем GF(q) такие, что для любого k ( K шифрующее преобразование fk в каждом из r раундов имеет вид

fk(x) = f(x + k), x ( Gn, (1)

где

f(x) = Ms(x) = M(s1(x1), , sn(xn))T, x = (x1, , xn) ( Gn. (2)

Отображение f: Gn ( Gn, определяемое по формуле (2), называется раундовой функцией шифра (, а подстановки si (13 EMBED Equation.3 1415) s-блоками этого шифра.
В дальнейшем линейное преобразование M отождествляется с квадратной матрицей порядка n над полем GF(q). В этом случае запись Ms(x) в выражении (2) обозначает результат умножения вектор-столбца s(x) длины n на матрицу M; аналогичное соглашение действует относительно умножения матриц на вектор-строки.
Введем ряд вспомогательных понятий. Следуя [13], назовем матрицу A порядка n над полем GF(q) разложимой, если существуют натуральное число k, 1 ( k < n, и подстановочная матрица P такие, что

A = 13 EMBED Equation.3 1415,

где A1 матрица порядка k над полем GF(q). Матрица A, не являющаяся разложимой, называется неразложимой.
Обозначим через ( нетривиальный аддитивный характер поля GF(q) [5]. Для любой подгруппы L абелевой группы Gn символом L( обозначим подгруппу, дуальную к L: L( = {x(Gn: ((xy) = 1 для любого y ( L} (напомним, что в соответствии с принятым выше соглашением запись xy обозначает скалярное произведение векторов x и y над полем из q элементов).
Рассмотрим произвольное отображение s: GF(q) ( GF(q). Будем говорить, что s имеет тривиальную линейную структуру, если не существует элементов a, b ( GF(q) \ 0 таких, что функция ((bs(x + a) + bs(x)), x ( GF(q) является констатной. Отметим, что тривиальность линейной структуры каждого s-блока данного блочного шифра (, определяемого с помощью соотношений (1), (2), является одним из стандартных необходимых условий стойкости этого шифра к линейному криптоанализу [14, 15]. Известно, например [16], что этому условию удовлетворяют s-блоки шифра Rijndael.
Основной результат настоящей статьи содержит следующая теорема.
Теорема. Пусть ( Rijndael-подобный блочный шифр, раундовые шифрующие преобразования которого определяются по формулам (1), (2). Предположим далее, что s-блоки s1, , sn шифра ( имеют тривиальную линейную структуру. Тогда группа G(() является примитивной в том и только том случае, когда матрица M неразложима.
Доказательство. Заметим, прежде всего, что блоки импримитивности группы G(() являются также блоками импримитивности группы подстановок 13 EMBED Equation.3 1415, которая в силу равенства (1) совпадает с группой сдвигов абелевой группы Gn. Отсюда следует (см., например, [5]), что каждая система блоков импримитивности группы G(() является системой смежных классов группы Gn по некоторой ее подгруппе.
Предположим теперь, что G(() импримитивная группа подстановок и L нетривиальный блок этой группы, содержащий нулевой вектор (нейтральный элемент группы Gn). Тогда L является собственной подгруппой группы Gn, и на основании равенства (1) и определения дуальной подгруппы для любых векторов a = (a1, , an) ( L, b = (b1, , bn) ( L(, x = (x1, , xn) ( Gn выполняется равенство

((bf(x + a) + bf(x)) = 1. (3)

Положим L( = {bM: b ( L(}. Из равенств (2), (3) следует, что

13 EMBED Equation.3 1415= 1

для любых a = (a1, , an) ( L, с = (с1, , сn) ( L(, x = (x1, , xn) ( Gn, откуда, в свою очередь, вытекает тождество

13 EMBED Equation.3 1415( const, xi ( GF(q), (4)

справедливое для всех a(L, с(L(, 13 EMBED Equation.3 1415.
Итак, на основании соотношений (4) и условия теоремы для любых a ( L, с ( L(, 13 EMBED Equation.3 1415 неравенство ai ( 0 (ci ( 0) влечет равенство сi = 0 (ai = 0). Отсюда вытекает, что ((сa) = ((0) = 1 для всех a ( L, с ( L(, и, следовательно, L( ( L(. Поскольку M является невырожденным линейным преобразованием, то множества L( и L( имеют одинаковую мощность. Следовательно, L( = L(, и подгруппа L( инвариантна относительно преобразования M.
Положим IL = {13 EMBED Equation.3 1415: ai = 0 для любого a(L}, k = |IL|. Заметим, что 1 ( k < n, так как L является нетривиальным блоком группы G((). Перенумеруем координаты векторов, принадлежащих группе Gn, таким образом, чтобы выполнялось равенство IL = {1, 2, , k}. Из определения дуальной подгруппы следует, что для любого a = (a1, , an) ( L

L((a)13 EMBED Equation.3 1415{(с1, , сn) ( Gn: с1, , сk ( Gk, ((сk+1ak+1 + + сnan) = 1} ( L(.

Если при этом ci ( 0 для некоторых (с1, , сn) ( L((a), 13 EMBED Equation.3 1415, то, согласно полученному выше равенству L( = L(, имеет место соотношение i ( IL, что противоречит определению множества IL. Таким образом,

L( = {(с1, , сn) ( Gn: с1, , сk ( Gk, сk+1 = = сn = 0}, (5)

в частности, подгруппа L( является подпространством векторного пространства GF(q)n над полем GF(q). Наконец, так как собственное инвариантное относительно матрицы M подпространство L( имеет вид (5), то M является разложимой матрицей, что и требовалось доказать.
Предположим теперь, что матрица M разложима и покажем, что G(() импримитивная группа. Перенумеровав подходящим образом строки и столбцы матрицы M, представим эту матрицу в виде

M = 13 EMBED Equation.3 1415, (6)

где M1 матрица порядка k над полем GF(q), 1 ( k < n. Несложная проверка показывает, что подпространство L( вида (5) инвариантно относительно матрицы M вида (6), и для любых a ( L = {(с1, , сn) ( Gn: с1, , сk = 0, сk+1 = = сn ( Gn–k}, b ( L(, x ( Gn выполняется равенство (3). Отсюда вытекает, что множество L является нетривиальным блоком группы G(() и, следовательно, G(() импримитивная группа подстановок. Теорема доказана.
Непосредственно из утверждения полученной теоремы и известного критерия неприводимости линейного преобразования над полем (см., например, [5], гл. XV, теор. 14) вытекает следующий результат.
Следствие 1. В условиях доказанной выше теоремы G(() является примитивной группой, если характеристический многочлен матрицы M неприводим над полем GF(q). В частности, если M полноцикловое линейное преобразование векторного пространства GF(q)n, то G(() примитивная группа подстановок.
Отметим, что на практике проверить разложимость или неразложимость данной квадратной матрицы M можно с использованием известных алгоритмов, изложенных, например, в [13]. Приведем здесь простое достаточное условие неразложимости матрицы M, позволяющее с помощью несложной проверки убедиться в том, что группа подстановок, порожденная раундовыми преобразованиями шифра Rijdael, является примитивной.
Обозначим через B = 13 EMBED Equation.3 1415 носитель матрицы M = 13 EMBED Equation.3 1415, т.е. вещественную (0, 1)-матрицу с элементами bij = 1, если mij ( 0; bij = 0 в противном случае, 13 EMBED Equation.3 1415. Согласно [13], матрица M является неразложимой, если сушествует натуральное t, для которого все элементы t-й степени матрицы B положительные вещественные числа.
В качестве применения полученных результатов, рассмотрим шифр Rijdael с длиной блока шифруемого сообщения, равной 128 битам (варианты шифрования блоков длины 192 бита или 256 бит рассматриваются аналогично). В этом случае в выражениях (1), (2) G = (GF(28), +), n = 16, и M является произведением двух матриц 16-го порядка над полем из 28 элементов:

M = diag (D, D, D, D) П16, (7)

где D матрица порядка 4 над полем GF(28), все элементы которой отличны от 0, П16 подстановочная матрица, соответствующая подстановке на множестве {0, 1}16, преобразующей двоичный вектор (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) в вектор (x0, x13, x10, x7, x4, x1, x14, x11, x8, x5, x2, x15, x12, x9, x6, x3) [12]. Несложная проверка показывает, что носитель B матрицы M имеет следующий вид:

B = 13 EMBED Equation.3 1415, (8)

где e4 = (1, 1, 1, 1)T и 0 = (0, 0, 0, 0)T вектор-столбцы длины 4, состоящие из единиц и нулей соответственно. Используя соотношение (8), нетрудно убедиться в том, что все элементы матрицы B2 положительны. Следовательно, матрица М вида (7) является неразложимой.
Итак, справедливо следующее утверждение.
Следствие 2. Раундовые преобразования шифра Rijdael порождают примитивную группу подстановок.
В плане дальнейших исследований, отметим, прежде всего, задачи вычисления или оценки значений различных числовых параметров [17], связанных с группами, порожденными раундовыми преобразованиями Rijdael-подобных блоч-ных шифров. Несомненный практический интерес представляет также ответ на вопрос о том, совпадает ли группа, порожденная раундовыми преобразованиями шифра Rijdael, с симметрической или знакопеременной группой подстановок на множестве блоков шифруемых сообщений.



Харин Ю.С., Берник В.И., Матвеев Г.В. Математические основы криптологии. Минск: Изд-во БГУ, 1999. 319 с.
Бабаш А.В., Шанкин Г.П. Криптография. М.: Солон-Р, 2002. 511 с.
Горчинский Ю.Н. О гомоморфизмах многоосновных универсальных алгебр в связи с криптографическими применениями // Труды по дискретной математике. Т. 1. М.: ТВП, 1997. С. 67–84.
Шапошников И.Г. О конгруэнциях конечных многоосновных универсальных алгебр // Дискретная математика. 1999. Т. 11. Вып. 3. С. 48–62.
Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра: Учебник. В 2-х т. Т.II. М.: Гелиос АРВ, 2003. 416 с.
Paterson K.G. Imprimitive Permutation Groups and Trapdoors in Iterated Block Ciphers // Fast Software Encryption. FSE’99, Proceedings. Springer Verlag, 1999. P. 201–214.
Campbell K.W., Wiener M. DES is Not a Group // Advances in Cryptology CRYPTO’92, Proceedings. Springer Verlag, 1993. P. 512–520.
Even S., Goldreich O. DES-Like Functions Can Generate the Alternating Group // IEEE Trans. on Information Theory. 1983. V. 29. P. 863–865.
Hornauer G., Stephan W., Wernsdorf R. Markov ciphers and alternating groups // Advances in Cryptology EUROCRYPT’93, Proceedings. Springer Verlag, 1994. P. 453–460.
Kaliski B.S., Rivest R.L., Sherman A.T. Is the Data Encryption Standard a Group? (Results of Cycling Experiments on DES) // J. Cryptology. 1988. №. 1. P. 3–36.
Park S., Sung S.H., Chee E-J. J., Lim J. On the Security of Rijndael-Like Structures Against Differential and Linear Cryptanalysis // Advances in Cryptology ASIACRYPT’02, Proceedings. Springer Verlag, 2002. P. 176–191.
Daemen J., Rijmen D. AES Proposal: Rijndael. htpp://csrc.nist.gov/encription/aes/rijndael/ Rijndael.pdf.
Сачков В.Н., Тараканов В.Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000. 447 с.
Chabaud F., Vaudenay S. Links Between Differential and Linear Cryptanalysis // Advances in Cryptology EUROCRYPT’ 94, Proceedings. Springer Verlag, 1995. P. 356–365.
Canteaut A. Cryptographic Functions and Design Criteria for Block Ciphers // Advances in Cryptology INDOCRYPT’2001, Proceedings. Springer Verlag, 2001. P. 1–16.
Keliher L., Meier H., Tavares S. Improving the upper bond on the maximum average linear hull probability for Rijndael // Selected Areas in Cryptography. SAC 2001. Proceedings. Springer Verlag, 2001. P. 112–128.
Глухов М.М. О числовых параметрах, связанных с заданием конечных групп системами образующих элементов // Труды по дискретной математике. Т. 1. М.: ТВП, 1997. С. 43–66.


Поступила в редакцию 22.03.2004
А. Н. Алексейчук

Критерий примитивности группы подстановок,
порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра

13PAGE 141215


13PAGE 141315
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 2

Математичні методи обробки даних

ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 2 11




Приложенные файлы

  • doc 4352869
    Размер файла: 120 kB Загрузок: 0

Добавить комментарий