Квазигруппы и кольца в кодировании и построении криптосхем | ПДМ. 2012. № 4(18).

Квазигруппы и кольца в кодировании и построении криптосхем

Исследуются различные криптосхемы и коды над ассоциативными и неассоциативными структурами. Построены схема шифрования над градуированным кольцом, криптосхема над лупой Муфанг, протокол выработки общего ключа и линейно оптимальные коды.

Quasigroups and rings in coding theory and cryptography.pdf Введение В работе в п. 1 представлены необходимые теоретические сведения. В п. 2 построена криптосхема над градуированным кольцом с мультипликативным базисом. Это обобщает построение криптосхемы над групповым кольцом. При этом неоднозначность выбора градуировки и мультипликативного базиса расширяет множество подходящих алгебраических структур для шифрования. Похожая схема была построена в [1]. В п. 3 построен протокол выработки общего секретного ключа и сконструирована криптосхе-ма, где все вычисления проводятся в лупе Муфанг. В п. 4 с помощью квазигрупповых колец построены две цепочки линейно оптимальных [n, n — 3, 3]q-кодов для n = 2q и n = 2q — 2. Для построения [2q, 2q — 2, 3]q-кодов используется представление кодов Рида — Соломона как идеалов группового кольца Fpn G, где G — это p-элементарная абелева группа порядка pn. В качестве иллюстрации приводятся линейно оптимальные коды, построенные с помощью коммутаторных квазигрупп для группы диэдра Dn. 1. Основные понятия Приведём основные понятия и утверждения, необходимые для дальнейшего изложения (см., например, [2]). Определение 1. Группоид — непустое множество с заданной бинарной операцией. Пусть (G, •) —группоид и a — некоторый элемент из G. Рассмотрим отображения L(a) : G X G, R(a) : G X G для любого a Е G. Определим их следующим образом: xL(a) = x • a, xR(a) = a • x для любых x E G. Определение 2. Квазигруппа — такой группоид (G, •), что отображения L(a), R(a) являются биекциями для любого a Е G. Это определение эквивалентно следующему: группоид (G, •) называется квазигруппой, если для любых a, b Е G уравнения x • a = b, a • y = b всегда разрешимы, причём однозначно. Определение 3. Группоид (G, •) называется лупой, если (G, •) является квазигруппой с единицей. Для любого элемента a лупы (G, •) определим элементы аЛ и ap условиями aA • a =1 и a • ap =1 Определение 4. Лупа (L, •) с единичным элементом 1 называется лупой Муфанг, если выполняется тождество (xy)(zx) = [x(yz)]x для любых x,y,z Е L. Свойства элементов лупы Муфанг описывает Теорема 1 [3]. Для элементов лупы Муфанг верны следующие тождества: 1) yA = Ур, что позволяет обозначить yA = yp = y-1; 2) (xy)x = x(yx); 3) (xy)(zx) = x[(yz)x]; 4) (xy)y-1 = x; 5) [(yx)z]x = y[x(zx)]; 6) [(xz)x]y = x[z(xy)]; 7) (xx)y = x(xy); 8) (xy)y = x(yy). Лемма 1 [4]. Пусть (L, •) —лупа Муфанг, тогда для любых x,y Е L (xy)-1 = y-1x-1. Доказательство. Ясно, что (xy)-1(xy) = 1. Тогда [(xy)-1(xy)]y-1 = y-1 = = ((xy)-1)[(xy)y-1] = (xy)-1[x(yy-1)] = (xy)-1x, а следовательно, (xy)-1 = y-1 x-1. ■ Одной из наиболее важных является следующая теорема. Теорема 2 [3]. Пусть (L, •) —лупа Муфанг. Если для x,y,z Е L выполняется x(yz) = (xy)z, то x,y,z порождают подгруппу в L. Следствие 1. Любая лупа Муфанг (M, •) является ди-ассоциативной, т. е. любые два элемента порождают подгруппу в M. Следствие 2. Любая лупа Муфанг (M, •) является лупой с ассоциативными степенями. Рассмотрим класс луп, который называется лупами Пейджа. Определение 5. Неассоциативная, конечная и простая лупа Муфанг M называется лупой Пейджа. Следующее описание луп Пейджа представлено в работе [5]. Пусть Fq — конечное поле. Для а, в Е Fq3 определим операции •, х следующим образом: а • в = а1в1 + а2в2 + азвз, а х в = (а2вз - азв2, азв1 - а1вз, а1в2 - а2в1). Алгеброй Цорна Z(q) называется множество (2 х 2)-матриц ^в ^^ , где a, b Е Fq и а, в Е F3, со следующей операцией: a ^ /с = / ac + а^ a7 + ^а - в х 5 в b) ^ U ^ = V св + b5 + а х 7 в • 7 + bd Все элементы Z(q) с определителем M = ab — ав = 1 образуют лупу Пейджа M*(q) ( 1 (0,0,0)N с нейтральным элементом e =1(0 0 0^ 1 Л. Пейдж в [6] показал, что |M*(q)| = q3(q4 — 1), когда q чётное, и |M*(q)| = = q3(q4 — 1)/2, если q нечётное. Пусть SL2(q) —специальная линейная группа (2 x 2)-матриц с определителем, равным 1, над полем Fq. Обозначим через L2(q) проективную группу SL2(q)/Z(SL2(q)). П. Войтеховски [7] доказал следующую теорему. Теорема 3. Пусть S С Z — множество порядков всех элементов лупы M*(q) и T — множество порядков элементов L2(q). Тогда S = T и порядок элемента a а^ Е M*(q) совпадает с порядком элемента b^ Е L2(q) при (а, в) = (0, 0) и с порядком элемента ^^в ^ из L2(q) при а = 0. Введём понятие квазигруппового (лупового) кольца. Пусть K — ассоциативное кольцо с единицей, L — лупа или квазигруппа. Рассмотрим множество KL, состоящее из всех формальных сумм вида £ а^ • l (а^ Е K), в которых конечное число элементов а^ zeL отлично от нуля. Два элемента a, b Е KL считаются равными тогда и только тогда, когда а1 = в1 для всех l Е L. На множестве KL определены операции сложения и умножения следующим образом: если a = £ а1 • l и b = £ в1 • l — элементы KL, то a + b = £(а1 + в1) • l, zeL zeL zeL ab = £ атвм l. Относительно этих операций множество KL является неассо- ZeL^ m,heL: / mh=l циативным кольцом с единицей. Удобно отождествить l Е L с элементом 1 • l Е KL, а а Е K — с элементом а • e, где e — единица лупы, тогда K и L являются подмножествами в KL. Пусть теперь R — ассоциативное кольцо с единицей 1 Е R. Рассмотрим группу G в мультипликативной записи с нейтральным элементом e Е G. Определение 6. Кольцо R называется G-градуированным, если существует такое семейство {Ro : а Е G} аддитивных подгрупп Ro аддитивной группы R, что R =0 Ro, RoRT С ROT для всех а, т Е G. Строго градуированным называется o-ec G-градуированное кольцо R, для которого выполнено равенство RoRT = ROT для всех а, т Е G. Однородным степени а называется элемент x Е Ro. Будем обозначать множество обратимых по умножению элементов в кольце R символом U (R). Лемма 2. Пусть R = ф Ro — G-градуированное кольцо. Тогда oec 1) 1 Е Re и Re является подкольцом кольца R; 2) обратный элемент r-1 к обратимому однородному элементу r также однородный; 3) G-градуированное кольцо R строго градуированно тогда и только тогда, когда 1 Е RoRo-1 для любого а Е G. Доказательство. 1. По определению ReRe С Re; поэтому достаточно показать, что 1 Е Re. Пусть 1 = £ ro, где ro Е Ro. Для любого hA Е Ra получаем hA = Лл • 1 = £ hAro и oec oec h^ra Е Дла. Поэтому для любого а = е выполнено h^ra = 0. Итак, 1 • га = 0, следовательно, га = 0 для любого а = е. Отсюда 1 = re Е Re 2. Пусть r Е U(R) П Ял. Если r-1 = Е (г-1)а, то 1 = rr-1 = Е r(r-1)a. Так как 1 Е Re и r(r-1)a Е ДЛа, то r(r )a = 0 для любых а = Л-1. Но из того, что r Е U(R) —обратимый элемент, следует соотношение (r-1)a = 0 для а = Л-1, и в итоге r-1 = (r-1 )л-1 Е ДЛ-1 —тоже однородный элемент степени Л-1. 3. Предположим, что 1 Е RaRa-1 для любого а Е G, и докажем, что градуировка строгая. В самом деле, для любых а, т Е G имеем цепочку равенств Дат = ЯеЛат = (RaR-1 )RaT = Ra(Ra- RaT) ^ RaRt. Это показывает, что RaT = RaRt, что означает строгость градуировки. Обратное утверждение очевидно: 1 Е Re = RaRa-1. ■ Следствие 3. Справедливы равенства ReRa = RaRe = Ra, т.е. Ra есть Re-бимо-дуль. Пусть R — конечномерная некоммутативная алгебра над полем F. Определение 7. Мультипликативным базисом конечномерной алгебры R называется такой её базис B, что B U {0} замкнуто относительно умножения. Пример 1. Для алгебры (n х п)-матриц Mn(F) над полем F естественным мультипликативным базисом является стандартный базис, состоящий из матричных единиц Ej, у которых на ij-й позиции стоит 1, а остальные элементы — нули. Пример 2. Для любой конечномерной (полу)групповой алгебры FG моноида G в качестве мультипликативного базиса можно выбрать моноид G. Для обобщения предыдущего примера рассмотрим обобщенные полугрупповые алгебры, обозначаемые Е(Д, R) и введённые в [8]. Здесь А — некоторое конечное множество, снабжённое частичным ассоциативным умножением. В свою очередь, Е(Д, R) — действительное векторное пространство функций из Д в R. Мультипликативная структура на Е(Д, R) индуцируется умножением на Д. Пример 3. Любая конечномерная обобщённая полугрупповая алгебра E(A,R) имеет мультипликативный базис — так называемые характеристические функции Хг, 5 Е Д. 2. Криптосхемы над градуированными кольцами с мультипликативным базисом 2.1. Конструирование автоморфизмов г р а д у и р о в а н н о г о к о л ь ц а В [9] рассматриваются автоморфизмы лупового кольца KL. Из автоморфизмов Е Aut(K) и ф Е Aut(L) конструируется х Е Aut(KL) по следующему правилу: для любого h = al1 /1 + ... + a1n/га, h Е KL, по определению полагается x(h) = = ^(al1 )ф(11) + ... + ^(a1n)ф(/га). Таким образом, если известна структура групп автоморфизмов Aut(K) и Aut(L) по отдельности, то есть возможность строить достаточно много автоморфизмов из Aut(KL). Заметим, что даже для произвольного группового кольца полного описания его группы автоморфизмов ещё не получено. Пусть теперь R — кольцо, градуированное конечной группой G. По лемме 2 Re — подкольцо в R, а по следствию 3 подгруппа Ra есть Re-бимодуль для любого а Е G. Если описана группа автоморфизмов для подкольца Re, то в общем случае, фиксируя ' e Е ^ • -1 -1) , -1 -1 a€G аес 1 1 1 ^ Е Aut(Re), мы ещё не определяем однозначно автоморфизм для всего R. В самом деле, для этого необходимо распространить действие ^ и на модули Ro и таким образом получить х Е Aut(R). Для этого необходимо, чтобы x(ro1 r02) = x(ro1 )x(r02) для roi E ROl , r02 E R02 , roi r02 E R0l02 . Но если у кольца R существует мультипликативный базис B над Re, то R = ReB. Поэтому автоморфизм ^ естественным образом продолжается до автоморфизма х всего кольца R. В силу того, что B образует полугруппу по умножению, зададим ф Е Aut(B) по аналогии с [9]. Этот автоморфизм будет перемешивать сам мультипликативный базис. Заметим, что в случае (полу)группового кольца, рассматриваемого в естественной градуировке, такая конструкция в точности совпадает с построением его автоморфизма по отдельным автоморфизмам кольца и (полу)группы. Но даже для (по-лу)группового кольца, меняя градуировку или выбирая другой мультипликативный базис, получаем, вообще говоря, уже новые структуры для шифрования со своими автоморфизмами. Это расширяет множество подходящих для криптосхемы структур. Пример 4. Рассмотрим Mn(F), где F = Rn(K, J) —радикальное кольцо матриц. Пусть K — ассоциативное кольцо с единицей, J — идеал в K, Mn(J) —кольцо (n x n)-матриц над идеалом J. По определению из [10] Rn(K, J) = NT„(K) + M„(J), где NTn(K) — нижнетреугольные матрицы над кольцом K. Тогда | Aut(Rn(Zpm, (pd))) | = = (pm — pm-1)n-1 ■ p(2m-d)cn +d(n-2), где d|m, d < m. Автоморфизм ф E Aut(B) зададим по правилу ф(Еу) = Eo(j)o(j), причём а Е Sn. Так как Re = F, то Aut(Re) = Aut(F), а следовательно, количество индуцированных автоморфизмов равно |Aut(Re)| ■ |Aut(B)| ^ |Sn| ■ |Aut(R„(Zpm, (pd)))| = n! ■ (pm — pm-1)n-1 ■ p(2m-d)C +d(n-2). Таким образом, данная структура имеет достаточно богатую индуцированную группу автоморфизмов. 2.2. Построение криптосхем ы Участник A : 1) Выбирает градуированное кольцо R с мультипликативным базисом, такое, что группы автоморфизмов Aut(B) и Aut(Re) некоммутативны. Предполагается, что группы Aut(B) и Aut(Re) достаточно богаты некоммутирующими элементами большого порядка с нетривиальными централизаторами большого порядка. Положим |Aut(B)| ^ ^ t1, |Aut(Re)| ^ t2. Здесь и далее t — параметры безопасности, которые по предположению экспоненциально зависят от порядка градуированного кольца R. Фиксирует градуировку и этот базис (в случае, если кольцо допускает несколько различных базисов) с учётом вышеперечисленных условий. Эта информация объявляется по открытому каналу. Обозначим базис через B, а группу, по которой градуировано кольцо, — через G, тогда общеизвестны R, B, G . 2) Задает автоморфизм а Е Aut(Re) так, чтобы порядок |а| ^ t3, причём а должен иметь нетривиальный централизатор и |C(а) \ (а)| ^ t4. Конструирует автоморфизм n Е Aut(B) так, чтобы |n| ^ t5, причём п должен иметь нетривиальный централизатор и |C(n) \ (n)| ^ t6. 3) Случайно выбирает автоморфизм т Е C(а) \ (а). 4) Случайно выбирает ш Е C(n) \ (n). 5) По т и ш строит секретный автоморфизм ^ Е Aut(R) так: для любого h Е R вида h = ab1 b1 + ... + abnbn, где ab1,..., abn Е Re, полагает

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

неассоциативные алгебраические структуры, градуированное кольцо, квазигрупповое кольцо, лупа Муфанг, коммутаторные квазигруппы, схема шифрования, линейно оптимальный код, nonassociative algebraic structure, graded ring, quasigroup ring, Moufang loop, commutator quasigroup, cryptoschemes, linearly optimal code

Авторы

ФИООрганизацияДополнительноE-mail
Марков Виктор ТимофеевичМосковский государственный университет им. М. В. Ломоносовакандидат физико-математических наук, доцентmarkov@mech.math.msu.su
Михалёв Александр ВасильевичМосковский государственный университет им. М. В. Ломоносовадоктор физико-математических наук, профессор
Грибов Алексей ВикторовичМосковский государственный университет им. М. В. Ломоносовааспирантalexey.gribov@yandex.ru
Золотых Павел АндреевичМосковский государственный университет им. М. В. Ломоносовааспирантpzolotykh@gmail.com
Скаженик Сергей СергеевичМосковский государственный университет им. М. В. Ломоносовааспирантsergey_skazhenik@hotmail.com
Всего: 5

Ссылки

Росошек С. К. Криптосистемы групповых колец // Вестник Томского госуниверситета. Приложение. 2003. №6. С. 57-62.
Белоусов В. Д. Основы теории квазигрупп и луп. М.: Наука, 1967. 223с.
Pflugfelder H. O. Quasigroups and Loops: Introduction. Berlin: Heldermann, 1990.
Smith J. D. H. An Introduction to Quasigroups and their Representations. Boca Raton: Chapman&HalljCRC, 2007.
Vojtechovsky P. Generators for finite simple Moufang loops // J. Group Theory. 2003. No. 6. P. 169-174.
Paige L. J. A class of simple Moufang loops // Proc. Amer. Math. Soc. 1956. V. 7. No. 3. P. 471-482.
Vojtechovsky P. Finite simple Moufang loops // PhD thesis. Department of Mathematics, Iowa State University, Ames, 2001.
Conrad P. Generalized semigroup rings // J. Indian Math. Soc. 1957. V. 21. P. 73-95.
Грибов А. В., Золотых П. А., Михалёв А. В. Построение алгебраической криптосистемы над квазигрупповым кольцом // Математические вопросы криптографии. 2010. Т. 1. №4. С.23-33.
Kuzucuoglu F. and Levchuk V. M. The automorphism group of certain radical matrix rings // J. Algebra. 2001. V.243. No. 2. P. 473-485.
Magliveras S. S., Stinson D. R., and Tran van Trung. New approaches to designing public key cryptosystem using one-way functions and trap-doors in finite groups // J. Cryptology. 2008. V. 15. No. 4. P. 285-297.
МакВилльямс Ф. Дж., СлоэнН.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
Heise W. and Quattrocci P. Informations und Codierungstheorie. Berlin; Heidelberg: Springer, 1995.
Гонсалес С., Коусело Е., Марков В. Т., Нечаев А. А. Рекурсивные МДР-коды и рекурсивно дифференцируемые квазигруппы // Дискретная математика. 1998. Т. 10. №2. С. 3-29.
Гонсалес С., Коусело Е., Марков В. Т., Нечаев А. А. Групповые коды и их неассоциативные обобщения // Дискретная математика. 2004. Т. 14. №1. С. 146-156.
Brouwer A. E. Bounds on linear codes // Handbook of Coding Theory. Amsterdam: Elsevier, 1998. P. 295-461.
Grassl M. Searching for linear codes with large minimum distance // Discovering Mathematics with Magma. Berlin; Heidelberg: Springer, 2006. V. 19. P. 287-313.
Couselo E., Gonzalez S., Markov V., et al. Some constructions of linearly optimal group codes // Linear Algebra and its Applications. 2010. No. 433. P. 356-364.
Charpin P. Les codes e Reed-Solomon en tant qu'id^eaux d'une alg'ebre modulaire (French. English summary) // C. R. Acad. Sci. Paris. 1982. V.294. No. 17. P. 597-600.
Landrock P. and Manz O. Classical codes as ideals in group algebras // Designs, Codes and Cryptography. 1992. No. 2. P. 273-285.
 Квазигруппы и кольца в кодировании и построении криптосхем | ПДМ. 2012. № 4(18).

Квазигруппы и кольца в кодировании и построении криптосхем | ПДМ. 2012. № 4(18).

Полнотекстовая версия