Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра
Рассмотрена алгебраическая модель Rijndael-подобного блочного шифра, s-блоки которого имеют тривиальную линейную структуру. Получены необходимые и достаточные условия, при которых раундовые шифрующие преобразования данного шифра порождают примитивную группу подстановок, что исключает возможность про...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2004 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2004
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50652 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра / А.Н. Алексейчук // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 2. — С. 11-18. — Бібліогр.: 17 назв. — pос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859814549440430080 |
|---|---|
| author | Алексейчук, А.Н. |
| author_facet | Алексейчук, А.Н. |
| citation_txt | Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра / А.Н. Алексейчук // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 2. — С. 11-18. — Бібліогр.: 17 назв. — pос. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Рассмотрена алгебраическая модель Rijndael-подобного блочного шифра, s-блоки которого имеют тривиальную линейную структуру. Получены необходимые и достаточные условия, при которых раундовые шифрующие преобразования данного шифра порождают примитивную группу подстановок, что исключает возможность проведения на шифр ряда известных алгебраических атак. Показано, что группа, порожденная раундовыми преобразованиями шифра Rijndael, является примитивной.
Розглянуто алгебраїчну модель Rijndael-подібного блокового шифру, s-блоки якого мають тривіальну лінійну структуру. Отримано необхідні та достатні умови, за якими раундові шифруючі перетворення даного шифру породжують примітивну групу підстановок, що виключає можливість проведення на шифр ряду відомих алгебраїчних атак. Показано, що група, яка породжується раундовими перетвореннями шифру Rijndael, є примитивною.
The algebraic model of an Rijndael-like block cipher with s-blocks that have no linear structure, is considered. Necessary and sufficient conditions, under which the group generated by the round functions of this cipher is primitive, what excludes the possibility of realisation of well-known algebraic attacks on the cipher, are obtained. It is shown that group generated by the round functions of Rijndael is primitive.
|
| first_indexed | 2025-12-07T15:21:38Z |
| format | Article |
| fulltext |
Математичні методи обробки даних
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 2 11
УДК 621.391: 519.7
А. Н. Алексейчук
Специальный факультет СБ Украины в составе Военного института
телекоммуникаций и информатизации НТУУ «КПИ»
ул. Московская, 45/1, 01011 Киев, Украина
Критерий примитивности группы подстановок,
порожденной раундовыми преобразованиями
Rijndael-подобного блочного шифра
Рассмотрена алгебраическая модель Rijndael-подобного блочного
шифра, s-блоки которого имеют тривиальную линейную структуру.
Получены необходимые и достаточные условия, при которых раундо-
вые шифрующие преобразования данного шифра порождают прими-
тивную группу подстановок, что исключает возможность проведения
на шифр ряда известных алгебраических атак. Показано, что группа,
порожденная раундовыми преобразованиями шифра Rijndael, является
примитивной.
Ключевые слова: криптографическая защита информации, блочный
шифр, примитивная группа подстановок, Rijndael.
Одной из важных задач, связанных с повышением информационной безопас-
ности современных телекоммуникационных систем, является совершенствование
криптографических методов и средств защиты информации, циркулирующей в
этих системах. К таким средствам относятся, в частности, блочные шифры (БШ),
широко используемые в автоматизированных системах обработки данных для
обеспечения конфиденциальности передаваемой или хранимой информации.
При изучении криптографических свойств блочных шифров, не связанных с
особенностями их технической (программной) реализации или процессами функ-
ционирования соответствующих шифрующих устройств, как правило, использу-
ются две основные математические модели БШ: алгебраическая и вероятностная
[1, 2]. В настоящей статье рассматривается алгебраическая модель блочно-итера-
ционного шифра, формальное описание которой приведено ниже.
Пусть даны конечная абелева группа G, непустые конечные множества K, L и
семейство (fk: Gn ® Gn, k Î K) взаимно однозначных преобразований множества
Gn = {(g1, …, gn): gi Î G, ni ,1Î }. Согласно определению [1], r-раундовый блочно-
итерационный шифр Á c множеством открытых (шифрованных) сообщений Gn,
множеством ключей L, множеством тактовых ключей K, расписанием ключей
А. Н. Алексейчук
А. Н. Алексейчук
12
q: L ® Kr и функцией шифрования F: Gn´L ® Gn представляет собой систему (Gn,
L, K, F, q) такую, что для любых x Î Gn, l Î L выполняется равенство
F(x, l) = fk(r) … fk(1)(x),
где (k(1), …, k(r)) = q(l) и fk(r) … fk(1) есть произведение (последовательное выпол-
нение) указанных преобразований. Элементы k(1), …, k(r) называются тактовыми
ключами, а отображения fk(1), …, fk(r) — раундовыми шифрующими преобразова-
ниями шифра Á в тактах (раундах) шифрования с номерами 1, …, r соотвественно.
Как правило, при анализе стойкости данного блочного шифра Á относитель-
но криптоаналитических атак, не использующих конкретные особенности распи-
сания ключей q, в приведенном выше определении полагают L = Kr, q(l) = l =
= (k(1), …, k(r)), т.е. считают, что последовательность тактовых ключей может
быть произвольным элементом множества Kr. В дальнейшем это соглашение при-
нимается в настоящей статье.
Одним из общих требований к современным блочным шифрам является их
обоснованная стойкость относительно алгебраических методов криптоанализа,
основанных на группировании открытых, шифрованных сообщений или ключей
шифра в классы эквивалентных (или близких, в том или ином смысле) объектов,
позволяющем понизить трудоемкость алгоритмов решения соответствующих
криптоаналитических задач. Стойкость БШ к подобным методам криптоанализа,
получившим в ряде публикаций название методов гомоморфных образов или го-
моморфизмов [2–4], как правило, определяется алгебраическими свойствами раз-
личных групп подстановок, связанных с системой раундовых преобразований
данного блочного шифра Á.
Обозначим через G(Á) = >Î< Kkfk : подгруппу симметрической группы
множества Gn, порожденную подстановками fk: Gn ® Gn, k Î K. Напомним [5], что
группа G(Á) называется транзитивной, если для любых x, y Î Gn существует под-
становка g Î G(Á) со свойством g(x) = y. Транзитивная группа G(Á) называется
импримитивной, если она имеет нетривиальный блок (т.е. такое множество D Í
Í Gn, что 1 < ½D½ < ½Gn½, и для любого gÎG(Á) выполняется одно из условий
g(D) = D, g(D) Ç D = Æ), и примитивной — в противном случае.
Изучению взаимосвязи между криптографической стойкостью шифра Á и
свойствами группы G(Á) посвящены статьи [6–10] и ряд других работ. В частно-
сти, в [6, 7, 10] показано, что необходимым условием стойкости шифра Á к опре-
деленным алгебраическим атакам на основе известных или подобранных откры-
тых сообщений является выполнение следующих требований:
1) группа G(Á) примитивна;
2) эта группа имеет достаточно большой порядок (например, такой, при ко-
тором исключена возможность практического перечисления всех шифрующих
преобразований Fl = fk(r) … fk(1), l Î L в r раундах шифрования).
В [6] показано также, что импримитивность группы G(Á) может свидетельст-
вовать о наличии в конструкции шифра Á, так называемых «потайных лазеек»,
существенно снижающих его практическую стойкость. В доказательство этого в
[6] приводится пример 32-раундового шифра с длинами блока и ключа шифрова-
Критерий примитивности группы подстановок,
порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 2 13
ния, равными соответственно 64 и 80 битам. Этот шифр по своей структуре ана-
логичен алгоритму DES, за исключением конструкции s-блоков, и, как показано в
[6], является практически стойким к линейному и разностному криптоанализу.
Вместе с тем, импримитивность группы данного шифра позволяет осуществить на
него алгебраическую атаку с использованием 232 подобранных открытых текстов.
Необходимо отметить, что на практике вычисление группы, порожденной ра-
ундовыми шифрующими преобразованиями данного блочного шифра Á, как пра-
вило, представляет собой достаточно трудную задачу, которая становится практи-
чески неразрешимой при отсутствии полной информации о криптографической
схеме шифра. В этом случае скрытые в конструкции шифра «лазейки», основан-
ные на импримитивности указанной группы подстановок, практически не удается
обнаружить [6]. Таким образом, установление факта примитивности группы G(Á)
является первым шагом на пути обоснования стойкости шифра Á к алгебраиче-
ским атакам и отсутствия в конструкции этого шифра определенных cкрытых
«лазеек».
Целью настоящей статьи является доказательство теоремы, устанавливающей
необходимые и достаточные условия примитивности группы подстановок, поро-
жденной раундовыми преобразованиями Rijndael-подобного блочного шифра
[11]. (Эти шифры получили свое название в честь нового американского стандар-
та шифрования данных, утвержденного в США в 2001 году [12]). Приведенные
ниже условия примитивности группы G(Á) допускают простую алгоритмическую
проверку; в частности, с их помощью нетрудно показать, что раундовые преобра-
зования шифра Rijndael порождают примитивную группу подстановок.
Приведем точные определения основных понятий, используемых в дальней-
шем изложении. Рассмотрим блочный шифр Á = (Gn, L, K, F, q) над алфавитом
Gn, где G является аддитивной группой конечного поля порядка q = 2l, L = 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 ( ni ,1Î ) — s-блоками этого шифра.
В дальнейшем линейное преобразование M отождествляется с квадратной
матрицей порядка n над полем GF(q). В этом случае запись Ms(x) в выражении (2)
обозначает результат умножения вектор-столбца s(x) длины n на матрицу M; ана-
логичное соглашение действует относительно умножения матриц на вектор-
строки.
А. Н. Алексейчук
14
Введем ряд вспомогательных понятий. Следуя [13], назовем матрицу A по-
рядка n над полем GF(q) разложимой, если существуют натуральное число k,
1 £ k < n, и подстановочная матрица P такие, что
A = P
AA
A
P ÷÷
ø
ö
çç
è
æ-
32
11
0
,
где A1 — матрица порядка k над полем GF(q). Матрица A, не являющаяся разло-
жимой, называется неразложимой.
Обозначим через c нетривиальный аддитивный характер поля GF(q) [5]. Для
любой подгруппы L абелевой группы Gn символом L^ обозначим подгруппу, ду-
альную к L: L^ = {xÎGn: c(xy) = 1 для любого y Î L} (напомним, что в соответст-
вии с принятым выше соглашением запись xy обозначает скалярное произведение
векторов x и y над полем из q элементов).
Рассмотрим произвольное отображение s: GF(q) ® GF(q). Будем говорить,
что s имеет тривиальную линейную структуру, если не существует элементов
a, b Î GF(q) \ 0 таких, что функция c(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(Á) являются также блоками импримитивности группы подстановок
>Î< - Kkkff kk 21
1 , :)(
21
, которая в силу равенства (1) совпадает с группой сдвигов
абелевой группы Gn. Отсюда следует (см., например, [5]), что каждая система
блоков импримитивности группы G(Á) является системой смежных классов груп-
пы Gn по некоторой ее подгруппе.
Предположим теперь, что G(Á) — импримитивная группа подстановок и L —
нетривиальный блок этой группы, содержащий нулевой вектор (нейтральный
элемент группы Gn). Тогда L является собственной подгруппой группы Gn, и на
основании равенства (1) и определения дуальной подгруппы для любых векторов
a = (a1, …, an) Î L, b = (b1, …, bn) Î L^, x = (x1, …, xn) Î Gn выполняется равенство
c(bf(x + a) + bf(x)) = 1. (3)
Положим L¢ = {bM: b Î L^}. Из равенств (2), (3) следует, что
Критерий примитивности группы подстановок,
порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 2 15
Õ
=
++
n
i
iiiiiii xscaxsc
1
))()((c = 1
для любых a = (a1, …, an) Î L, с = (с1, …, сn) Î L¢, x = (x1, …, xn) Î Gn, откуда, в
свою очередь, вытекает тождество
))()(( iiiiiii xscaxsc ++c º const, xi Î GF(q), (4)
справедливое для всех aÎL, сÎL¢, ni ,1Î .
Итак, на основании соотношений (4) и условия теоремы для любых a Î L, с Î
L¢, ni ,1Î неравенство ai ¹ 0 (ci ¹ 0) влечет равенство сi = 0 (ai = 0). Отсюда выте-
кает, что c(сa) = c(0) = 1 для всех a Î L, с Î L¢, и, следовательно, L¢ Í L^. По-
скольку M является невырожденным линейным преобразованием, то множества L¢
и L^ имеют одинаковую мощность. Следовательно, L¢ = L^, и подгруппа L^ инва-
риантна относительно преобразования M.
Положим IL = { ni ,1Î : ai = 0 для любого aÎL}, k = |IL|. Заметим, что 1 £ k < n,
так как L является нетривиальным блоком группы G(Á). Перенумеруем координа-
ты векторов, принадлежащих группе Gn, таким образом, чтобы выполнялось ра-
венство IL = {1, 2, …, k}. Из определения дуальной подгруппы следует, что для
любого a = (a1, …, an) Î L
L^(a)
def
= {(с1, …, сn) Î Gn: с1, …, сk Î Gk, c(сk+1ak+1 + … + сnan) = 1} Í L^.
Если при этом ci ¹ 0 для некоторых (с1, …, сn) Î L^(a), nki ,1+Î , то, согласно
полученному выше равенству 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 = ÷÷
ø
ö
çç
è
æ
32
1
0
MM
M
, (6)
где M1 — матрица порядка k над полем GF(q), 1 £ k < n. Несложная проверка по-
казывает, что подпространство L^ вида (5) инвариантно относительно матрицы M
А. Н. Алексейчук
16
вида (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 =
nnijb
´
носитель матрицы M =
nnijm
´
, т.е. веществен-
ную (0, 1)-матрицу с элементами bij = 1, если mij ¹ 0; bij = 0 — в противном случае,
nji ,1, Î . Согласно [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 =
÷÷
÷
÷
÷
ø
ö
çç
ç
ç
ç
è
æ
00 0 000 000 000
000 000 000 000
0 00 000 000 0 00
0 00 0 00 000 000
4444
4444
4444
4444
eeee
eeee
eeee
eeee
, (8)
Критерий примитивности группы подстановок,
порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 2 17
где e4 = (1, 1, 1, 1)T и 0 = (0, 0, 0, 0)T — вектор-столбцы длины 4, состоящие из
единиц и нулей соответственно. Используя соотношение (8), нетрудно убедиться
в том, что все элементы матрицы B2 положительны. Следовательно, матрица М
вида (7) является неразложимой.
Итак, справедливо следующее утверждение.
Следствие 2. Раундовые преобразования шифра Rijdael порождают прими-
тивную группу подстановок.
В плане дальнейших исследований, отметим, прежде всего, задачи вычисле-
ния или оценки значений различных числовых параметров [17], связанных с
группами, порожденными раундовыми преобразованиями Rijdael-подобных блоч-
ных шифров. Несомненный практический интерес представляет также ответ на
вопрос о том, совпадает ли группа, порожденная раундовыми преобразованиями
шифра Rijdael, с симметрической или знакопеременной группой подстановок на
множестве блоков шифруемых сообщений.
1. Харин Ю.С., Берник В.И., Матвеев Г.В. Математические основы криптологии. — Минск:
Изд-во БГУ, 1999. — 319 с.
2. Бабаш А.В., Шанкин Г.П. Криптография. — М.: Солон-Р, 2002. — 511 с.
3. Горчинский Ю.Н. О гомоморфизмах многоосновных универсальных алгебр в связи с
криптографическими применениями // Труды по дискретной математике. — Т. 1. — М.: ТВП,
1997. — С. 67–84.
4. Шапошников И.Г. О конгруэнциях конечных многоосновных универсальных алгебр //
Дискретная математика. — 1999. — Т. 11. — Вып. 3. — С. 48–62.
5. Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра: Учебник. В 2-х т. Т.II. — М.: Гелиос
АРВ, 2003. — 416 с.
6. Paterson K.G. Imprimitive Permutation Groups and Trapdoors in Iterated Block Ciphers // Fast
Software Encryption. — FSE’99, Proceedings. — Springer Verlag, 1999. — P. 201–214.
7. Campbell K.W., Wiener M. DES is Not a Group // Advances in Cryptology — CRYPTO’92,
Proceedings. — Springer Verlag, 1993. — P. 512–520.
8. Even S., Goldreich O. DES-Like Functions Can Generate the Alternating Group // IEEE Trans.
on Information Theory. — 1983. — V. 29. — P. 863–865.
9. Hornauer G., Stephan W., Wernsdorf R. Markov ciphers and alternating groups // Advances in
Cryptology — EUROCRYPT’93, Proceedings. — Springer Verlag, 1994. — P. 453–460.
10. 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.
11. 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.
12. Daemen J., Rijmen D. AES Proposal: Rijndael. htpp://csrc.nist.gov/encription/aes/rijndael/
Rijndael.pdf.
13. Сачков В.Н., Тараканов В.Е. Комбинаторика неотрицательных матриц. — М.: ТВП, 2000.
— 447 с.
А. Н. Алексейчук
18
14. Chabaud F., Vaudenay S. Links Between Differential and Linear Cryptanalysis // Advances in
Cryptology — EUROCRYPT’ 94, Proceedings. — Springer Verlag, 1995. — P. 356–365.
15. Canteaut A. Cryptographic Functions and Design Criteria for Block Ciphers // Advances in
Cryptology — INDOCRYPT’2001, Proceedings. — Springer Verlag, 2001. — P. 1–16.
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.
17. Глухов М.М. О числовых параметрах, связанных с заданием конечных групп системами
образующих элементов // Труды по дискретной математике. — Т. 1. — М.: ТВП, 1997. — С. 43–66.
Поступила в редакцию 22.03.2004
УДК 621.391: 519.7
УДК 621.391: 519.7
УДК 621.391: 519.7
УДК 621.391: 519.7
УДК 621.391: 519.7
УДК 621.391: 519.7
УДК 621.391: 519.7
А. Н. Алексейчук
А. Н. Алексейчук
Основной результат настоящей статьи содержит следующая теорема.
|
| id | nasplib_isofts_kiev_ua-123456789-50652 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Russian |
| last_indexed | 2025-12-07T15:21:38Z |
| publishDate | 2004 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Алексейчук, А.Н. 2013-10-27T00:50:24Z 2013-10-27T00:50:24Z 2004 Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра / А.Н. Алексейчук // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 2. — С. 11-18. — Бібліогр.: 17 назв. — pос. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50652 621.391: 519.7 Рассмотрена алгебраическая модель Rijndael-подобного блочного шифра, s-блоки которого имеют тривиальную линейную структуру. Получены необходимые и достаточные условия, при которых раундовые шифрующие преобразования данного шифра порождают примитивную группу подстановок, что исключает возможность проведения на шифр ряда известных алгебраических атак. Показано, что группа, порожденная раундовыми преобразованиями шифра Rijndael, является примитивной. Розглянуто алгебраїчну модель Rijndael-подібного блокового шифру, s-блоки якого мають тривіальну лінійну структуру. Отримано необхідні та достатні умови, за якими раундові шифруючі перетворення даного шифру породжують примітивну групу підстановок, що виключає можливість проведення на шифр ряду відомих алгебраїчних атак. Показано, що група, яка породжується раундовими перетвореннями шифру Rijndael, є примитивною. The algebraic model of an Rijndael-like block cipher with s-blocks that have no linear structure, is considered. Necessary and sufficient conditions, under which the group generated by the round functions of this cipher is primitive, what excludes the possibility of realisation of well-known algebraic attacks on the cipher, are obtained. It is shown that group generated by the round functions of Rijndael is primitive. ru Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Математичні методи обробки даних Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра Критерій примітивності групи підстановок, що породжується раундовими перетвореннями Rijndael-подібного блокового шифру A Criterion for the Primitivity of the Permutation Group Generated by the Round Functions of an Rijndael-Like Block Cipher Article published earlier |
| spellingShingle | Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра Алексейчук, А.Н. Математичні методи обробки даних |
| title | Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра |
| title_alt | Критерій примітивності групи підстановок, що породжується раундовими перетвореннями Rijndael-подібного блокового шифру A Criterion for the Primitivity of the Permutation Group Generated by the Round Functions of an Rijndael-Like Block Cipher |
| title_full | Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра |
| title_fullStr | Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра |
| title_full_unstemmed | Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра |
| title_short | Критерий примитивности группы подстановок, порожденной раундовыми преобразованиями Rijndael-подобного блочного шифра |
| title_sort | критерий примитивности группы подстановок, порожденной раундовыми преобразованиями rijndael-подобного блочного шифра |
| topic | Математичні методи обробки даних |
| topic_facet | Математичні методи обробки даних |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50652 |
| work_keys_str_mv | AT alekseičukan kriteriiprimitivnostigruppypodstanovokporoždennoiraundovymipreobrazovaniâmirijndaelpodobnogobločnogošifra AT alekseičukan kriteríiprimítivnostígrupipídstanovokŝoporodžuêtʹsâraundovimiperetvorennâmirijndaelpodíbnogoblokovogošifru AT alekseičukan acriterionfortheprimitivityofthepermutationgroupgeneratedbytheroundfunctionsofanrijndaellikeblockcipher |