НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o101.pdf (479.11Кб)

УДК 519.40

Россия,  МГТУ им. Н.Э. Баумана

В данной работе рассматривается возможность создания схемы открытого распределения ключей в группах, копредставление которых удовлетворяет условиям C(3)-T(6). При этом используются следующие алгоритмы.
1) Алгоритм, решающий проблему вхождения в циклическую подгруппу,
известную также как проблема дискретного логарифмирования.
2) Алгоритм, решающий проблему равенства слов в данном классе групп.
Исследование проводится с использованием геометрических методов комбинаторной теории групп (метода диаграмм над группами).
При обмене информацией по открытому каналу используют односторонние функции, прямое вычисление которых должно быть гораздо менее сложным, чем вычисление обратной функции. Нашей задачей было построить одностороннюю функцию на группе с условиями малого
сокращения C(3)-T(6) и сравнить сложность её вычисления со сложностью вычисления  обратной функции.
Шором была доказана полиномиальная сложность задачи дискретного логарифмирования в мультипликативных группах конечных полей и колец вычетов. После этого появилась серия исследований по отысканию других сложных математических проблем, которые можно было бы использовать для построения асимметричных криптосистем. Так в работах Аншела И., Аншела М. и Голдфилда Д. были рассмотрены системы открытого распределения ключей, основанные на проблеме сопряжённости в матричных группах и группах кос.
В работе (Паенг С., и др.) за основу была взята проблема дискретного логарифмирования в группах внутренних автоморфизмов полупрямых произведений групп L(2,Zp) и Zp, GL(2,Zp) и Zp. В работе (Сакалаускас Е., и др.) была предложена схема, основанная на композиции двух проблем теории групп: проблемы сопряжённости и проблемы дискретного логарифмирования.
Исследования показывают, что задача, на которой основана разработанная авторами схема, имеет полиномиальную сложность решения. Поэтому криптостойкость такой системы недостаточна для обеспечения необходимого уровня защиты информации. Однако, надежность можно повысить, комбинируя проблему слов с другими алгебраическими проблемами: вхождения в циклическую подгруппу, сопряжённости.

1. Магнус В., Каррас А., Солитэр Д. Комбинаторная теория групп: пер. с англ. М.: Наука, 1974. 456 с.
2. Линдон Р., Шупп П. Комбинаторная теория групп: пер. с англ. М.: Мир, 1980. 448 с.
3. Ольшанский А.Ю. Геометрия определяющих соотношений в группах. М.: Наука, 1989. 448 с.
4. Новиков П.С. Об алгоритмической неразрешимости проблемы тождества слов в теории групп // Тр. Математического ин-та АН СССР. 1955. Т. 44. С. 1-144.
5. Безверхний Н.В. Разрешимость проблемы вхождения в циклическую подгруппу в группах с условием C(6) // Фундаментальная и прикладная математика. 1999. Т.  5 , № 1. С. 39-46.
6. Безверхний Н.В. Нормальные формы для элементов бесконечного порядка в группах с условиями C(3)-T(6) // Известия ТулГУ. Естественные науки. 2010. Вып. 1. С. 6-25.
7. Безверхний Н.В. Проблема сопряжённого вхождения в циклическую подгруппу в группах с условием C(3)-T(6) // Дискретная математика. 2012. Т. 24, вып. 4. С. 27-47.
8. Безверхний В.Н. О нормализаторах элементов в C(p)-T(q)-группах // Алгоритмические проблемы теории групп и полугрупп: межвуз. сб. науч. трудов. Тула: Изд-во ТГПУ им. Л.Н. Толстого, 1994. C . 4-58.
9. Безверхний В.Н., Паршикова Е.В. Решение проблемы вхождения в циклическую подгруппу в группах с условием C(4)-T(4) // Алгоритмические проблемы теории групп и полугрупп: межвуз. сб. науч. трудов. Тула: Изд-во ТГПУ им. Л.Н. Толстого, 2001. С. 120-139.
10. Глухов М.М. К анализу некоторых систем открытого распределения ключей, основанных на неабелевых группах // Математические вопросы криптографии. 2010. T.1, № 4. С. 5-22.
11. Паршикова Е.В. Проблема слабой степенной сопряжённости в группах с условием C(4)-T(4) // Алгоритмические проблемы теории групп и полугрупп: межвуз. сб. науч. трудов. Тула: Изд-во ТГПУ им. Л.Н. Толстого, 2001. С. 179-185.
12. Безверхний Н.В. О кручении и о разрешимости проблемы вхождения в циклическую подгруппу в группах с условием C(6). М., 1995. Деп. в ВИНИТИ, № 2033-В95.
13. Bogley W.A., Pride S.J. Aspherical relative presentations // Proc. of Edinburg Math. Soc. Ser. 2. 1992. Vol. 35, no. 1. P. 1 - 39. DOI: 10.1017/S0013091500005290
14. Gersten S.M., Short H.B. Small cancellation theory and automatic groups // Inventiones Mathematicae. 1990. Vol. 102, iss. 1. P. 305-334. DOI: 10.1007/BF01233430
15. Shor P.W. Polynomial-time algorithm for prime factorization and discrete logarithms on quantum computer // SIAM Journal on Computing. 1997. Vol. 26, no. 5. P. 1484-1509. DOI: 10.1137/S0097539795293172
16. Anshel I., Anshel M., Goldfeld D. An algebraic method for public key cryptography // Mathematical Research Letters. 1999. Vol. 6, no. 3. P. 287-291. DOI: 10.4310/MRL.1999.v6.n3.a3
17. Ko K.H., Lee S.J., Cheon J.H., Han J.W., Kang J., Park C. New Public-Key Cryptosystem Using Braid Groups // In: Advances in Cryptology - CRYPTO 2000 . Springer Berlin Heidelberg , 2000. P. 166-183. (Ser. Lecture Notes in Computer Science; vol. 1880). DOI: 10.1007/3-540-44598-6_10
18. Yamamura A. Public-key cryptosystems using the modular group // In: Public Key Cryptography. Springer Berlin Heidelberg, 1998. P. 203-216. (Ser. Lecture Notes in Computer Science; vol. 1431). DOI: 10.1007/BFb0054026
19. Yamamura A. A Functional Cryptosystem Using a Group Action // In: Information Security and Privacy. Springer Berlin Heidelberg, 1999. P. 314-325. (Ser. Lecture Notes in Computer Science; vol. 1587). DOI: 10.1007/3-540-48970-3_26
20. Paeng S.-H., Ha K.-C., Kim J.H., Chee S., Park C. New Public Key Cryptosystem Using Finite Non Abelian Groups // In: Advances in Cryptology - CRYPTO 2001. Springer Berlin Heidelberg , 2001. P. 470-485. (Ser. Lecture Notes in Computer Science; vol. 2139). DOI: 10.1007/3-540-44647-8_28
21. Paeng S.-H., Kwon D., Ha K.-C., Kim J.H. Improved public key cryptosystem using non abelian groups. Cryptology ePrint Archive: Report 2001/066. Available at: http://eprint.iacr.org/2001/066, accessed 01.09.2014.
22. Sakalauskas E., Tvarijonas P., Raulinaitis A. Key agreement protocol (KAP) using conjugacy and discrete logarithms problems in group representation level // Informatica. 2007. Vol. 18, no. 1. P. 115-124.