Дискретное логарифмирование в конечномерной алгебре над полем | ПДМ. 2014. № 4(26).

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

Описывается алгоритм, сводящий с полиномиальной сложностью задачу дискретного логарифмирования в конечномерной алгебре к задаче дискретного логарифмирования над конечным полем.

Discrete logarithm problem in finite dimensional algebras over field.pdf Введение В работе [1] предложены варианты обобщения хорошо известного алгоритма Диф-фи - Хеллмана [2], использующего циклические группы для реализации протокола открытого распределения ключей, на случай, когда вместо группы используется неассоциативный группоид. Опишем один из вариантов предложенных обобщений. Для элемента g конечного группоида (П, *) и заданного r G N определим правую r-ю степень равенством g[r] -(... ((g * g) * g)...). r сомножителей Назовём g элементом с перестановочными правыми степенями, или ППС-элементом, если Vm,n G N (g[m][n] - g[n][m]) . Если это тождество выполняется для всех элементов g G П, то будем называть (П, *) ППС-группоидом. Алгоритм открытого распределения ключей. Выбрав (несекретный) ППС-элемент g группоида П, абоненты A и B независимо друг от друга выбирают произвольные числа ГА,Гв G N соответственно и обмениваются элементами g[rA] и g[rB]. Затем формируют общий секретный ключ g[rA][rB 1 - g[rB ][га]. Сложность восстановления наблюдателем секретного ключа по открытой информации g, g[rA], g[rB 1 не превосходит сложности задачи правого дискретного логарифмирования в группоиде, т. е. сложности решения уравнения g[x] - h. В качестве ППС-группоида могут быть выбраны конечномерные алгебры над конечным полем, обладающие свойством перестановочности степеней. В связи с этим представляется интересным решение задачи правого дискретного логарифмирования в неассоциативной конечномерной алгебре над полем. В работе описывается алгоритм, с полиномиальной сложностью сводящий задачу дискретного логарифмирования в конечномерной алгебре к задаче дискретного логарифмирования над конечным полем. 1. Основные определения и предварительные результаты Пусть (P, +, • ) -поле из q элементов с единицей е. P-алгеброй, или алгеброй над полем P, называют P-модуль П с билинейным отображением * : ПхП ^ П, называемым операцией умножения [3]. Условие билинейности операции * означает выполнение законов дистрибутивности справа и слева и условия Vu, v G П, a G P ((u * v)a = u * (va) = (ua) * v = a(u * v)). Размерностью P-алгебры называют размерность = dimP П пространства PП. Пусть е = (е1,..., en) -базис конечномерной алгебры рП. Тогда операция * определяется заданием произведений n (fc) е * ej = E efc j (1) fc=1 поскольку из (1) и условия билинейности * имеем ( n \ I n \ n I n Е eiu0 И Е ejvn = Е ek Е uia(j)v \i=1 / \j=1 / fc=1 \ ij=1 Элементы aj- из (1) называют структурными константами P-алгебры, набор (fc) i ■ ■ матриц Ak = (aj)nxn, k = 1,..., n,- матрицами структурных констант. Рассмотрим представление P-алгебры в базисе е. Пусть u, v" G Pn - строки координат элементов u,v G П в базисе е; тогда строка координат произведения u * v удовлетворяет равенству u = (и A1v^,..., и Anv^). Для удобства изложения будем рассматривать P-алгебру П как её представление Pn в некотором базисе е с операцией (2). P-алгебру Pn с матрицами структурных констант A1,... , An и умножением, определённым равенством (2), будем обозначать G (A1,...,An). Рассмотрим свойства операции умножения в P-алгебре G(A1,...,An), где Ад = = (a^j))nxn, k = 1... , n. Равенство (2) можно записать также следующим образом: и * v = и • R( v), R( v) = (A1v^ ... Anv^) , u * v = v • L(и), L(u) = (Afu^ ... Anu^) . Тогда справедливо Утверждение 1. Для произвольного элемента u P-алгебры G(А1,... , An), для любого натурального k верны равенства и[fc+1]=и R(и)k, [k+1] и = и L(И)к. (4) На основании равенств (4) можно предложить алгоритм вычисления степени u , аналогичный бинарному алгоритму вычисления степени элемента абелевой группы [4], имеющий сложность, полиномиально зависящую от log k. P-алгебры (П, *, +) и (П,*, +) называют изоморфными, если существует невырожденное линейное преобразование ф пространства р П со свойством Vu,v G П (ф(и) *^(v) - * v)). Будем называть элемент u реверсивным (справа), если для некоторого натурального t выполнено u[t+1] - u. Утверждение 2. Если элемент u - (u1,... un) P-алгебры G(A1,... , An) реверси-вен и существует набор c1,... , cn элементов поля P, такой, что C1A1 + ... + CnAn - 0, (5) то выполнено соотношение c1u1 + ... + cnun - 0. a a a Лемма 1. Если вектор ш - (ш1,..., шП) равен произведению векторов a * в, то при условии (5) для его координат выполнено соотношение С1Ш1 + ... + спшп - 0. (6) Доказательство. Верна цепочка равенств С1Ш1 + ... + СпШп - С1 a A^ + ... + Cn a Ane^ -a (C1A1 + ... + CnAn)e4 - 0. ■ Доказательство утверждения 2. Для реверсивного элемента и существует a a[fc] a[fc-11 a k > I, такое, что u - u - u * u. Теперь утверждение 2 следует из леммы 1. ■ Пусть G' - {w- (w1,... , wn) G Pn : c1w1 + ... + cnwn - 0}. Заметим, что G' - подалгебра алгебры G (A1,... , An), причём ввиду утверждения 2 G' содержит все реверсивные элементы. Будем называть G' подалгеброй, определённой тождеством (6). Утверждение 3. Пусть G(A1,... , An) - алгебра над полем P и существует ненулевой набор c1,... , cn-1 элементов поля P, такой, что An - c1A1 + ... + cn-1 An-1. Тогда подалгебра G' алгебры G, определённая тождеством шП - с1ш1 + ... + сп-1шп-1, изоморфна P-алгебре G(B1,...,Bn-1), где матрицы Bk - (bj)(n-1)x(n-1) для k - I, ... , n - I определены соотношениями b^j a^j ++ Cja^n ++ Ci&nj ++ CiCjann, i, j I,..., n I. (7) Доказательство. Зададим отображение ^ : G' ^ G (B1,... ,Bn-1) следующим образом: ^((ш1,... , шп)) - (ш1 , ...,шП-1). Очевидно, ^ биективно. Покажем, что ^ - гомоморфизм. По определению ^ V u, V g G' u * V) - (u A1v^,..., u An-1v4)^ . Для k - I,... , n - I рассмотрим k-ю координату: n- 1 n- 1 u AfcV4 - (u1, . . . un-1 , E Ciui)Afc(V1, . . . Vn-1, E CiVi)T V i=1 i=1 n- 1 n- 1 n- 1 n- 1 n- 1 n- 1 n- 1 n- 1 - E E uivjaj + E u E cjvj al + E E cu0 vj+ E ciu0 E cjvj I аПп. i=1 j=1 i=1 \j=1 j j=1 vi=1 у \i=1 у у=1 Сгруппировав суммы, получаем равенство n- 1 n- 1 a Afcv4 - E E uivj(aj + cjakn + с*аП,- + ccjаПп) - a)Bfca)T. i=1 j=1 Таким образом, и * ии) = ■u)B1

Ключевые слова

открытое распределение ключей, неассоциативные группоиды, конечномерные алгебры, дискретное логарифмирование, open key distribution, Diffie - Hellmann algorithm, non associative groupoids, finite dimensional algebras, discrete logarithm problem

Авторы

ФИООрганизацияДополнительноE-mail
Катышев Сергей ЮрьевичООО «Центр сертификационных исследований», г. Москванаучный сотрудникsairos87@mail.ru
Всего: 1

Ссылки

Катышев С. Ю., Марков В. Т., Нечаев А. А. Использование неассоциативных группоидов для открытого распределения ключей // Дискретная математика. 2014. Т. 46. №3. C. 51-59.
Diffie W. and Bellman M. E. New directories in cryptography // IEEE Trans. Inf. Theory. 1976. V. 22. P. 644-654.
Пирс Р. Ассоциативные алгебры: пер. с англ. М.: Мир, 1986. 543 с.
Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. 2-е изд. М.: МЦНМО, 2007. 326 с.
Глухов М. М, Елизаров В. П., Нечаев А. А. Алгебра. В 2-х т. М.: Гелиос, 2003. 336 + 416 с.
Kurakin V.L., Kuzmin A.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.
 Дискретное логарифмирование в конечномерной алгебре над полем | ПДМ. 2014. № 4(26).

Дискретное логарифмирование в конечномерной алгебре над полем | ПДМ. 2014. № 4(26).