Дискретное логарифмирование в конечномерной алгебре над полем

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

2014 Теоретические основы прикладной дискретной математики № 4(26)
УДК 512. 548. 2
ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ В КОНЕЧНОМЕРНОЙ АЛГЕБРЕ НАД ПОЛЕМ1
С. Ю. Катышев
ООО «Центр сертификационных исследований», г. Москва, Россия E-mail: sairos87@mail. ru
Описывается алгоритм, сводящий с полиномиальной сложностью задачу дискретного логарифмирования в конечномерной алгебре к задаче дискретного логарифмирования над конечным полем.
Ключевые слова: открытое распределение ключей, неассоциативные группоиды, конечномерные алгебры, дискретное логарифмирование.
Введение
В работе [1] предложены варианты обобщения хорошо известного алгоритма Диф-фи — Хеллмана [2], использующего циклические группы для реализации протокола открытого распределения ключей, на случай, когда вместо группы используется неассоциативный группоид. Опишем один из вариантов предложенных обобщений.
Для элемента g конечного группоида (П, *) и заданного r Е N определим правую r-ю степень равенством
g[r] = (… ((g*g) *g)…).

r сомножителей
Назовём д элементом с перестановочными правыми степенями, или ППС-элементом, если
Ут, и Е N (д[т][п] = дмм).
Если это тождество выполняется для всех элементов д Е П, то будем называть (П, *) ППС-группоидом.
Алгоритм открытого распределения ключей. Выбрав (несекретный) ППС-элемент д группоида П, абоненты, А и В независимо друг от друга выбирают произвольные числа га, г в Е N соответственно и обмениваются элементами д[гА] и д[гв ]. Затем формируют общий секретный ключ д[ГАПГв ] = д[гвПГа].
Сложность восстановления наблюдателем секретного ключа по открытой информации д, д[гА], д[гв 1 не превосходит сложности задачи правого дискретного логарифмирования в группоиде, т. е. сложности решения уравнения
д[х] = К.
В качестве ППС-группоида могут быть выбраны конечномерные алгебры над конечным полем, обладающие свойством перестановочности степеней.
В связи с этим представляется интересным решение задачи правого дискретного логарифмирования в неассоциативной конечномерной алгебре над полем.
В работе описывается алгоритм, с полиномиальной сложностью сводящий задачу дискретного логарифмирования в конечномерной алгебре к задаче дискретного логарифмирования над конечным полем.
1 Работа выполнена при поддержке гранта Президента Р Ф НШ-6260. 2012. 10 и Академии криптографии РФ.
1. Основные определения и предварительные результаты
Пусть (Р, +, •) -поле из д элементов с единицей е.
Р-алгеброй, или алгеброй над полем Р, называют Р-модуль П с билинейным отображением *: ПхП ^ П, называемым операцией умножения [3]. Условие билинейности операции * означает выполнение законов дистрибутивности справа и слева и условия
Уи, V Е П, а Е Р ((и * г& gt-)а = и * (ш) = (иа) * V = а (и * V)).
Размерностью Р-алгебры называют размерность & amp-шП = & amp-шр П пространства рП.
Пусть е = (е1,…, еп) -базис конечномерной алгебры рП. Тогда операция * определяется заданием произведений
п (к
е *е. = Е ек. (!)
к=1
поскольку из (1) и условия билинейности * имеем
/га (П п I п к)
Е еги0 И Е е7vn = Е ек Е ига. V
г=1 / ^=1 / к=1 ?,. 7=1
Элементы a^- из (1) называют структурными константами P-алгебры, набор
(к) 7..
матриц Ак = (а-)пхп, к = 1,…, п, — матрицами структурных констант.
Рассмотрим представление Р-алгебры в базисе е. Пусть V, V€ Рп — строки координат элементов и^ Е П в базисе е- тогда строка координат произведения и * V удовлетворяет равенству
u
~*v = (u Aiv^,…, u An v^).
Для удобства изложения будем рассматривать Р-алгебру П как её представление Рп в некотором базисе е с операцией (2). Р-алгебру Рп с матрицами структурных констант Аь…, Ап и умножением, определённым равенством (2), будем обозначать ^ (А1,…, Ап).
Рассмотрим свойства операции умножения в Р-алгебре (А1,…, Ап), где Ак =
= (а (.))пхп) к = 1.. , п.
Равенство (2) можно записать также следующим образом:
и * v = и -R (v), R (v) = … Anv^), u * v = v -L (и), L (u) = (Afu^ … u^).
Тогда справедливо
Утверждение 1. Для произвольного элемента u P-алгебры G (A1,…, An), для любого натурального k верны равенства
И[fc+1] = и R (И)fc, [fc+1l и = и L (и). (4)
о л иИ
На основании равенств (4) можно предложить алгоритм вычисления степени u ,
аналогичный бинарному алгоритму вычисления степени элемента абелевой группы [4],
имеющий сложность, полиномиально зависящую от log k.
Р-алгебры (П, *, +) и (П,*, +) называют изоморфными, если существует невырожденное линейное преобразование ^ пространства р П со свойством
Уи,^ Е П (^(и) = -0(и * V)).
Будем называть элемент и реверсивным (справа), если для некоторого натурального? выполнено и[4+1] = и.
Утверждение 2. Если элемент и = (и1,… ип) Р-алгебры У (А1,…, Ап) реверси-вен и существует набор с1,…, сп элементов поля Р, такой, что
С1А1 + … + с"А" = 0, (5)
то выполнено соотношение с1и1 + … + спип = 0.
а, а а
Лемма 1. Если вектор ш = (ш1,…, шп) равен произведению векторов, а * в, то
при условии (5) для его координат выполнено соотношение
С1Ш1 + … + с"шга = 0. (6)
Доказательство. Верна цепочка равенств С1Ш1 + … + с"ш" = С1 а А^ + … + с" а А"в4 =а (С1А1 + … + с"А")в4 = 0. ¦
Доказательство утверждения 2. Для реверсивного элемента и существует
а аИ а[к1 а
к & gt- I, такое, что и = и = и * и. Теперь утверждение 2 следует из леммы I. ¦
Пусть У'- = {ги= …, Е Рп: с11 + … + спип = 0}. Заметим, что У'- - подалгебра алгебры У (А1,…, Ап), причём ввиду утверждения 2 У'- содержит все реверсивные элементы. Будем называть У'- подалгеброй, определённой тождеством (6).
Утверждение 3. Пусть У (А1,…, Ап) — алгебра над полем Р и существует ненулевой набор с1,…, сп-1 элементов поля Р, такой, что Ап = с1А1 + … + сп-1 Ап-1. Тогда подалгебра У'- алгебры У, определённая тождеством = с1ш1 + … + сп-1шп-1, изоморфна Р-алгебре У (В1,…, Вп-1), где матрицы Вк = (6-)(п-1)х (п-1) для К = I, …, п — I определены соотношениями
++ с, а^п ++ с^Оу^ ++ с^с^а^п, 3 I,…, п I. (7)
Доказательство. Зададим отображение: У'- ^ У (В1,…, Вп-1) следующим образом: ^((ш1,…, шп)) = (ш1 ,…, шп-1). Очевидно, ^ биективно. Покажем, что ^ - гомоморфизм. По определению ^
У и, Vе У'- и * V) = (и А4,…, и.
Для К = I,…, п — I рассмотрим К-ю координату:
} / п-1 п-1
и А*. V4 = (иь… и"-1, Е с*и*)Ай (^1,… Е с V г=1 г=1
п1 п1 п1 /га1 п1 / п1 /га1 /га1
= Е Е, а 7 + Е иг Е С7V'- + Е Е Си0 V+ Е сгиг Е С7V I
г=1 7=1 г=1 ^=1) 7=1 г=1 / г=1 / ^=1
Сгруппировав суммы, получаем равенство
а Ак ^ = Е Е + С7 + ^ + С С7 О = а) Вк, а) Т.
г=1 7=1
Таким образом, и * И) = и) В1^(¦и)т и) Вга-1^(И = и) * И), где
* - операция в У (Вь…, Вп-1). ¦
Следующий результат иногда позволяет решить задачу проверки перестановочности степеней и дискретного логарифмирования в алгебре меньшей размерности.
Теорема 1. В алгебре У (А1-…, Ап) существует подалгебра У'-, содержащая все реверсивные элементы и изоморфная некоторой алгебре У (Вь…, В4), Ь ^ п, такой, что система матриц В1,…, В линейно независима.
Доказательство. Индукция по к = п — гапк{Аь…, с применением утверждения 3. ¦
Алгебру У (В1-…, В4) из теоремы 1 будем называть приведённым видом алгебры У (А1,…, Ап).
Пусть и -произвольный элемент алгебры У (А1-…, Ап). Для произвольного к € N положим и = (мЦ (к),…, м^(к)). Тогда последовательность векторов
и" И и[2] и[к]
и = (и, и ,…, и ,…) (8)
можно рассматривать как вектор и = (иЦ,…, и^) из п координатных последовательностей
& lt- = (& lt-(1) = иг,& lt-(2),… ,<-(к),…), г =1,…, п. (9)
и [N1 и [г]
Через и обозначим множество всех различных элементов вида и, г € N.
Следующее утверждение показывает, что задачи логарифмирования и определения потенциала элемента алгебры иногда могут быть перенесены в алгебру ещё меньшей размерности.
Утверждение 4. Пусть и -элемент Р-алгебры У (А1,…, Ап). Тогда для некоторой Р-алгебры У (В1,…, В4), Ь ^ п, существует инъективное отображение: и ^ ^ У (В1,…, В4), обладающее следующими свойствами:
1) система координатных последовательностей {& lt-^(и)Г: г = 1,… ,?} линейно независима-
2) для любого натурального к верно равенство ^(и[к]) = (^(и))[к].
Лемма 2. Пусть и € У (А1,…, Ап) и существует ненулевой набор с1,…, сп-1 элементов поля Р, такой, что система последовательностей {и!,…, и^} удовлетворяет соотношению
& lt- = С1и1 + … + сга1& lt-_1. (10)
Рассмотрим алгебру У (В1,…, Вга-1) с операцией *, где матрицы структурных кон-
и[М]
стант В^ определены соотношением (7). Тогда отображение ф: и ^ У (В1,…, Вп-1), …, ¦")) = (¦1,…, ¦п-1) есть инъективное отображение со свойством
ф (им) = (ф (и))К (11)
Доказательство. В силу соотношения (10) ф инъективно. Докажем равенство (11) методом математической индукции. При г = 1 равенство очевидно. Пусть при г = т утверждение верно, докажем его при г = т +1. Пусть V = и[*т], тогда по определению ф
и[*т+1], ,/И и /И. I И. I.
ф (и) = ф (V * и) = (V Л1и+,…, V Лга-1и+).
п-1 П-1
В силу (10) un = Е и vn = Е CiVj- Для k = 1,…, n- 1 рассмотрим k-ю координату
i=1 i=1
v[*(m+1)]
вектора u:
n- 1 n- 1
Afc U4 = ((V1,.. Vn-1, E CiVi) Afc (U1,.. Un-Ci Ui) T
i=1 i=1
n- 1 n- 1 n- 1 n- 1 n- 1 n- 1 n- 1 n- 1
= E E viuj+ E v E cju Hn + E E cu+ E ед E cju) аПп
i=1 j=1 i=1 y=1 J j=1 V i=1 / i=1 / y=1
Сгруппировав суммы, получаем равенство
n- 1 n- 1
v Afcu4 = E E Viuj (a| + Cjal, + Ci^ + CiCjаПп) = V) Bfc^(u)T.
i=1 j = 1
Тогда ^^ u [ (= V) B1^(u)T,… ,^(v)Bn-= V) * u) =
= (^(u))[*(m+1)]. ¦
Доказательство утверждения 4- Индукция с применением леммы 2 по параметру k = n — rank{^(V)Г: i = 1,…, n}. ¦
Алгебру G (B1,…, Bt) из утверждения 4 будем называть приведённой алгеброй для
V
элемента u.
Замечание 1. Для нахождения линейной зависимости между координатными
V
последовательностями степеней элемента u достаточно найти линейную зависимость
V v[2] V[n]
между столбцами матрицы, составленной из строк u, u ,.. , u.
2. Дискретное логарифмирование
Для любого унитарного многочлена F (x) G P[x] и любого n G N обозначим через Lpn (F) семейство всех линейных рекуррентных последовательностей (ЛРП) над пространством pPn с характеристическим многочленом F (x) [5, 6].
vN
Утверждение 5. Последовательности u из (8) и u[, i = 1,…, n, из (9) суть ЛРП с характеристическим многочленом, равным характеристическому многочлену XD,^(x) матрщы R (V) из (3): uN G Lpn (v.) — ur G lp (Y.), i = 1,…, n.
R (u) R (и) R (и)
Доказательство проводится стандартным способом, с использованием соотношений (4) и теоремы Гамильтона — Кэли (см., например, [6, Example 1. 6]). ¦
Пусть Q — поле разложения многочлена x (x) над P и
R (и)
XR (U)(x) = (x — «1)fc1 ¦ … ¦ (x — at) fct (12)
R (и)
— каноническое разложение этого многочлена над Q. Тогда существует представление координатных последовательностей u[ через соответствующие биномиальные последовательности [5, 6]:
Следствие 1. Для любого i G {1,…, n} существует вектор-столбец d4 G Q (n),
u (k)= (ak-1,Cfc1−1"k-1 ,…, C|--1ak-1, ak-1,…, C|--1a|-1,…, C|--11ak-^ & lt- 4. (13)
такой, что
Для краткости будем использовать запись
& lt- (к) = («Г,…, Ск__11ак1) & lt- +, г € {1,…, п}.
Следствие 2. При условии (12) существует матрица Д €га, га, такая, что для любого натурального к правая степень элемента и представляется в виде
Uu 11= (а^,… ,^*-1) D. (14)
При этом следующие утверждения равносильны:
a) система координатных последовательностей «,…, «П последовательности «линейно независима-
b) матрица D обратима.
Доказательство. Ввиду (13) матрица D = (rfj^, …, dn G Qra, ra удовлетворяет условию (14).
(a) ^ (b). Если D — вырожденная матрица, то Dc^ = для некоторого c^ G G Q (n) {0+}, и ввиду (14) («1,… ,"П)с^ = 0, что противоречит условию (а).
(b) ^ (а). Если система координатных последовательностей «1, …, «П линейно зависима, то («1,… ,"П)с^ = 0 для некоторого c^ G Q (n) {0^}. Тогда ввиду (14) для вектора d^ = Dc^ = 0^ выполнено равенство (ak-1,…, C^t-^a^-1) d^ = 0^. Противоречие, так как система биномиальных последовательностей линейно независима. ¦
Следствие 3. В условиях следствия 2 если матрица D обратима, то Xr u) есть минимальный многочлен последовательности «N.
Доказательство. Пусть G (x) G P[x] -минимальный многочлен ЛРП «N. Тогда G (x)|x _& gt-. (x), и если G (x) = x _& gt-. (x), то deg G (x) = m & lt- n. В таком случае система из
R (u) R (и)
n координатных последовательностей «1,…, «П принадлежит подпространству Lp (G) размерности m и является линейно зависимой. Ввиду (14) это означает, что линейно независимая система из n биномиальных последовательностей (а^-1,…, C^t-^a^-1) при умножении на матрицу D становится линейно зависимой, что противоречит обратимости матрицы D. ¦
На основании равенства (14) можно предложить метод дискретного логарифмирования. Пусть G (A1,…, An) -произвольная алгебра над некоторым полем P. Для
^ ^ г/& gt-! Л Л ^
элементов «, v G G (A1,…, An) решается уравнение «= v.
Ввиду утверждения 4 можем считать, что рассматриваемая алгебра является приведённой алгеброй для элемента «, то есть система координатных последовательностей {"1,…, «П} линейно независима.
Пусть Q — расширение поля P, являющееся полем разложения характеристического многочлена Xr (x) матрицы R = (A1"^,…, Ara"^). Элементы а1,…, at — корни многочлена Xr (x), k — кратность корня а^, i = 1,…, t.
Замечание 2. Задача нахождения корней многочлена, очевидно, сводится к разложению многочлена на неприводимые сомножители (над полем разложения). Разложение многочлена степени n на множители имеет полиномиальную трудоёмкость относительно величины n log | P |, то есть относительно размера задачи (log | Pn |). Подробный обзор методов разложения многочлена на множители можно найти в [4].
Последовательность степеней элемента P-алгебры представляется в виде (14), причём матрица D обратима, так как система координатных последовательностей {»?(k): k = 1,…, n} линейно независима.
Для нахождения матрицы О можно решать систему, составленную из равенств (14), для различных степеней К Е {I,…, п}. Однозначность нахождения матрицы О следует из линейной независимости системы биномиальных последовательностей в правой части равенства (14). Сложность вычисления матрицы Ог полиномиальна относительно размера матрицы, её можно оценить величиной 0(п3).
При умножении обеих частей равенства (14) на матрицу О _1 справа получаем
а П1 а[х] П_ 1 («х-1 /-у1 _ х- 1 /& quot-А1» х-1 _ х-1 1» х- 1 /'--уА-^_1» х-1
V О = и О = (а1, Сх_ 1а1 ,…, Сх1 1 а1, а2 ,…, Сх1 1 а2 ,…, С 1
—, Cx-,…, Cx-1, ,…, Cx-1 ,…, Cx-1 а^
Пусть v D-1 — (wi,…, wn), тогда нахождение решения уравнения (14) равносильно решению системы уравнений
аХ-1 — w1, СХ- 1аХ-1 — W2,
/& quot-«kl — 1 «x- 1 » ,
Cx — 1 — w fc1, аХ-1 — Wki+1,
, 11аХ 1 — wn.
Нетрудно показать, что решение данной системы уравнений не сложнее однократного логарифмирования в поле Q по основанию примитивного элемента. В качестве вывода сформулируем результат.
Теорема 2. Задача дискретного логарифмирования на P-алгебре П размерности n с полиномиальной сложностью сводится к задаче дискретного логарифмирования в поле Q, являющемся расширением степени l поля P, где l & lt- n.
Сложность задачи дискретного логарифмирования в конечном поле имеет субэкспоненциальную оценку. Подробный обзор методов дискретного логарифмирования в конечном поле можно найти, например, в [4].
ЛИТЕРАТУРА
1. Катышев С. Ю., Марков В. Т., Нечаев А. А. Использование неассоциативных группоидов для открытого распределения ключей // Дискретная математика. 2014. Т. 46. № 3. C. 51−59.
2. Diffie W. and Bellman M. E. New directories in cryptography // IEEE Trans. Inf. Theory. 1976. V. 22. P. 644−654.
3. Пирс Р. Ассоциативные алгебры: пер. с англ. М.: Мир, 1986. 543 с.
4. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. 2-е изд. М.: МЦНМО, 2007. 326 с.
5. Глухое М. М, Елизаров В. П., Нечаев А. А. Алгебра. В 2-х т. М.: Гелиос, 2003. 336 + 416 с.
6. Kurakin V.L., KuzminA.S., Mikhalev A. V., and Nechaev A. A. Linear recurring sequences over rings and modules // J. Math. Sci. 1995. V. 76. No. 6. P. 2793−2915.

ПоказатьСвернуть
Заполнить форму текущей работой