Математика и математическое моделирование. 2018; : 88-111
Асимметричная схема передачи секретного ключа по открытому каналу в k-детерминированных группах с условиями C(3)-T(6)
https://doi.org/10.24108/mathm.0618.0000151Аннотация
В данной статье решается следующая задача: построение схемы обмена секретными ключами по открытому каналу связи. Основная идея построения такой схемы общеизвестна. Она базируется на понятии односторонней функции. Это функции, значения которых вычисляются гораздо проще, чем значения обратных функций. При построении односторонних функций используется алгоритм распознавания равенства слов в группах с условиями малого сокращения С(3)-Т(6). При этом группа представляется множеством своих образующих и определяющих соотношений. Вся работа, связанная с построением алгоритмов и оценкой их сложности, проводится с групповыми диаграммами равенства. Существование таких диаграмм доказано в известной лемме Ван Кампена. Итогом работы является следующий результат. Предложенная в статье схема обмена секретными ключами обладает следующими свойствами. Прямые алгоритмы имеют линейную сложность, а обратные – экспоненциальную. Следует отметить, что сложность алгоритмов оценивалась площадями соответствующих групповых диаграмм, которые определяются числом входящих в них областей. Построенный секретный ключ представляет собой некоторый элемент заранее выбранной группы с условиями С(3)-Т(6). Он может быть представлен бесконечным числом способов словами в алфавите из образующих группы. Таким образом, оставшимся препятствием к практическому применению построенной схемы обмена ключами является неоднозначность записи секретного ключа. Поиск общего представителя как лексикографически кратчайшего слова в классе равных слов оказывается слишком сложной задачей. Таким образом, этот вопрос остаётся открытым. Хотя сама задача обмена секретными ключами формально может считаться решённой.
Список литературы
1. Магнус В., Каррас А., Солитэр Д. Комбинаторная теория групп: пер. с англ. М.: Наука, 1974. 455 с. [Magnus W., Karrass A., Solitar D. Combinatorial group theory. N.Y.: Interscience Publ., 1966. 444 p.].
2. Линдон Р.К., Шупп П. Комбинаторная теория групп: пер. с англ. М.: Мир, 1980. 447 с. [Lyndon R.C., Schupp P.E. Combinatorial group theory. B.; N.Y.: Springer, 1977. 339 p.].
3. Ольшанский А.Ю. Геометрия определяющих соотношений в группах. М.: Наука, 1989. 446 с.
4. Gersten S.M., Short H.B. Small cancellation theory and automatic groups // Inventiones mathematicae. 1990. Vol. 102. No. 1. Pp. 305 - 334. DOI: 10.1007/BF01233430
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 - 46.
8. Безверхний В.Н. О нормализаторах элементов в C(p)-T(q)-группах // Алгоритмические проблемы теории групп и полугрупп: Межвуз. сб. науч. тр. Тула: Изд-во Тул. гос. педагогич. ун-та им. Л.Н.Толстого, 1994. С. 4 - 58.
9. Безверхний Н.В. О кручении о и разрешимости проблемы вхождения в циклическую подгруппу в группах с условием C(6). Деп. в ВИНИТИ 1995. № 2033-В95.
10. Bogley W.A., Pride S.J. Aspherical relative presentations // Proc. of the Edinburgh Math. Soc. 1992. Vol. 35. No. 1. Pp. 1 - 39. DOI: 10.1017/S0013091500005290
11. Безверхний Н.В. Односторонние функции и композиция проблем сопряжённости и дискретного логарифмирования в C(3)-T(6)-группах // Математика и математическое моделирование. 2015. № 5. С. 43-63. DOI: 10.7463/mathm.0515.0820675
12. Безверхний Н.В., Чернышёва О.А. Односторонние функции, основанные на проблеме дискретного логарифмирования в группах с условиями C(3)-T(6) // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 10. С. 70-101. DOI: 10.7463/1014.0729483
13. Безверхний В.Н., Паршикова Е.В. Решение проблемы вхождения в циклическую подгруппу в группах с условием C(4)-T(4) // Алгоритмические проблемы теории групп и полугрупп: Межвуз. сб. науч. тр. Тула: Изд-во Тул. гос. педагогич. ун-та им. Л.Н. Толстого, 2001. С. 120 - 139.
14. Глухов М.М. К анализу некоторых систем открытого распределения ключей, основанных на неабелевых группах // Математические вопросы криптографии. 2010. T. 1. № 4. С. 5 - 22.
15. Паршикова Е.В. Проблема слабой степенной сопряжённости в группах с условием C(4)-T(4) // Алгоритмические проблемы теории групп и полугрупп: Межвуз. сб. науч. тр. Тула: Изд-во Тул. гос. педагогич. ун-та им. Л.Н. Толстого, 2001. С. 179 - 184.
16. Shor P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM J. on Computing. 1997. Vol. 26. No. 5. Pp. 1484 - 1509. DOI: 10.1137/S0097539795293172
17. Anshel I., Anshel M., Goldfeld D. An algebraic method for public-key cryptography // Mathematical Research Letters. 1999. Vol. 6. No. 3. Pp. 287 - 291. DOI: 10.4310/MRL.1999.v6.n3.a3
18. Ko K.H., Lee S.J., Cheon J.H., Han J.W., Kang J.-S., Park C. New public-key cryptosystem using braid groups // Advances in cryptology – CRYPTO 2000: 20th Annual intern. cryptology conf. (Santa Barbara, CA, USA, August 20-24, 2000): Proc. B.; Hdbl.: Springer, 2000. Pp. 166 - 183. DOI: 10.1007/3-540-44598-6_10
19. Yamamura A. Public-key cryptosystems using the modular group // Public-key cryptography: PKC 1998: 1st Intern. Workshop on practice and theory in public key cryptography (Pacifico Yokohama, Japan, February 5-6, 1998): Proc. B.; Hdbl.: Springer, 1998. Pp. 203-216. DOI: 10.1007/BFb0054026
20. Yamamura A. A functional cryptosystem using a group action // Information security and privacy: 4th Australasian conf. on information security and privacy: ACISP 1999 (Wollongong, NSW, Australia, April 7-9, 1999): Proc. B.; Hdbl.: Springer, 1999. Pp. 314-325. DOI: 10.1007/3-540-48970-3_26
21. Paeng S.H., Ha K.C., Kim J.H., Chee S., Park C. New public key cryptosystem using finite non abelian groups // Advances in cryptology – CRYPTO 2001: 21st Annual intern. cryptology conf. (Santa Barbara, CA, USA, August 19-23, 2001): Proc. B.; Hdbl.: Springer, 2001. Pp. 470-485. DOI: 10.1007/3-540-44647-8_28
22. Paeng S.H., Kwon D., Ha K., Kim J.H. Improved public key cryptosystem using finite non abelian groups. Cryptology ePrint Archive: Report 2001/066. Режим доступа: http://eprint.iacr.org/2001/066 (дата обращения 15.12.2018).
23. Sakalauskas E., Tvarijonas P., Raulynaitis A. Key agreement protocol (KAP) using conjugacy and discrete logarithm problems in group representation level // Informatica. 2007. Vol. 18. No. 1. Pp. 115 - 124.
24. Новиков П.С. Об алгоритмической неразрешимости проблемы тождества слов в теории групп // Тр. Матем. ин-та АН СССР. 1955. Т. 44. С.1-144
Mathematics and Mathematical Modeling. 2018; : 88-111
Asymmetric Secret Key Transfer Scheme over an Open Channel in K-Deterministic Groups with the Conditions C (3) –T (6)
https://doi.org/10.24108/mathm.0618.0000151Abstract
The article solves a problem of developing a scheme to provide a secret key exchange over an open communication channel. The basic idea of creating such a scheme is well known. It is based on a concept of the one-way function. This refers to the functions whose values are calculated much easier than the inverse function values. When developing the one-way functions a recognition algorithm of words equality in groups with conditions of small cancellation C (3) - T (6) is used. In this case, the group is represented by a set of its generating and determining relations. All the work to accomplish development of algorithms and evaluate their complexity is carried out using the group diagrams of equality. The existence of such diagrams is proved in the well-known van Campen lemma. The paper result is that the proposed scheme for the exchange of secret keys has the following properties. Direct algorithms have a linear complexity, and a complexity of the inverse algorithms is exponential. It should be noted that the algorithms complexity was estimated by the areas of the corresponding group diagrams, which are determined by the number of areas they include. The constructed secret key represents some element of a pre-selected group with conditions C (3) – T (6). It can be represented in an infinite number of ways by words in the alphabet from the generators of the group. Thus, the remaining obstacle to the practical application of the key exchange scheme developed is the ambiguity of the secret key record. Finding a common representative as the lexicographically shortest word in the class of equal words turns out to be too difficult. Thus, this question remains open. Although the task of exchanging secret keys itself can be formally considered as solved.
References
1. Magnus V., Karras A., Soliter D. Kombinatornaya teoriya grupp: per. s angl. M.: Nauka, 1974. 455 s. [Magnus W., Karrass A., Solitar D. Combinatorial group theory. N.Y.: Interscience Publ., 1966. 444 p.].
2. Lindon R.K., Shupp P. Kombinatornaya teoriya grupp: per. s angl. M.: Mir, 1980. 447 s. [Lyndon R.C., Schupp P.E. Combinatorial group theory. B.; N.Y.: Springer, 1977. 339 p.].
3. Ol'shanskii A.Yu. Geometriya opredelyayushchikh sootnoshenii v gruppakh. M.: Nauka, 1989. 446 s.
4. Gersten S.M., Short H.B. Small cancellation theory and automatic groups // Inventiones mathematicae. 1990. Vol. 102. No. 1. Pp. 305 - 334. DOI: 10.1007/BF01233430
5. Bezverkhnii N.V. Razreshimost' problemy vkhozhdeniya v tsiklicheskuyu podgruppu v gruppe s usloviem C(6) // Fundamental'naya i prikladnaya matematika. 1999. T.5. № 1. S. 39 - 46.
6. Bezverkhnii N.V. Normal'nye formy dlya elementov beskonechnogo poryadka v gruppakh s usloviem C(3)-T(6) // Izv. Tul'skogo gos. un-ta. Estestvennye nauki. 2010. Vyp. 1. S. 6 - 25.
7. Bezverkhnii N.V. Problema sopryazhennogo vkhozhdeniya v tsiklicheskuyu podgruppu v gruppakh s usloviem C(3)-T(6) // Diskretnaya matematika. 2012. T. 24. Vyp. 4. S. 27 - 46.
8. Bezverkhnii V.N. O normalizatorakh elementov v C(p)-T(q)-gruppakh // Algoritmicheskie problemy teorii grupp i polugrupp: Mezhvuz. sb. nauch. tr. Tula: Izd-vo Tul. gos. pedagogich. un-ta im. L.N.Tolstogo, 1994. S. 4 - 58.
9. Bezverkhnii N.V. O kruchenii o i razreshimosti problemy vkhozhdeniya v tsiklicheskuyu podgruppu v gruppakh s usloviem C(6). Dep. v VINITI 1995. № 2033-V95.
10. Bogley W.A., Pride S.J. Aspherical relative presentations // Proc. of the Edinburgh Math. Soc. 1992. Vol. 35. No. 1. Pp. 1 - 39. DOI: 10.1017/S0013091500005290
11. Bezverkhnii N.V. Odnostoronnie funktsii i kompozitsiya problem sopryazhennosti i diskretnogo logarifmirovaniya v C(3)-T(6)-gruppakh // Matematika i matematicheskoe modelirovanie. 2015. № 5. S. 43-63. DOI: 10.7463/mathm.0515.0820675
12. Bezverkhnii N.V., Chernysheva O.A. Odnostoronnie funktsii, osnovannye na probleme diskretnogo logarifmirovaniya v gruppakh s usloviyami C(3)-T(6) // Nauka i obrazovanie. MGTU im. N.E. Baumana. Elektron. zhurn. 2014. № 10. S. 70-101. DOI: 10.7463/1014.0729483
13. Bezverkhnii V.N., Parshikova E.V. Reshenie problemy vkhozhdeniya v tsiklicheskuyu podgruppu v gruppakh s usloviem C(4)-T(4) // Algoritmicheskie problemy teorii grupp i polugrupp: Mezhvuz. sb. nauch. tr. Tula: Izd-vo Tul. gos. pedagogich. un-ta im. L.N. Tolstogo, 2001. S. 120 - 139.
14. Glukhov M.M. K analizu nekotorykh sistem otkrytogo raspredeleniya klyuchei, osnovannykh na neabelevykh gruppakh // Matematicheskie voprosy kriptografii. 2010. T. 1. № 4. S. 5 - 22.
15. Parshikova E.V. Problema slaboi stepennoi sopryazhennosti v gruppakh s usloviem C(4)-T(4) // Algoritmicheskie problemy teorii grupp i polugrupp: Mezhvuz. sb. nauch. tr. Tula: Izd-vo Tul. gos. pedagogich. un-ta im. L.N. Tolstogo, 2001. S. 179 - 184.
16. Shor P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM J. on Computing. 1997. Vol. 26. No. 5. Pp. 1484 - 1509. DOI: 10.1137/S0097539795293172
17. Anshel I., Anshel M., Goldfeld D. An algebraic method for public-key cryptography // Mathematical Research Letters. 1999. Vol. 6. No. 3. Pp. 287 - 291. DOI: 10.4310/MRL.1999.v6.n3.a3
18. Ko K.H., Lee S.J., Cheon J.H., Han J.W., Kang J.-S., Park C. New public-key cryptosystem using braid groups // Advances in cryptology – CRYPTO 2000: 20th Annual intern. cryptology conf. (Santa Barbara, CA, USA, August 20-24, 2000): Proc. B.; Hdbl.: Springer, 2000. Pp. 166 - 183. DOI: 10.1007/3-540-44598-6_10
19. Yamamura A. Public-key cryptosystems using the modular group // Public-key cryptography: PKC 1998: 1st Intern. Workshop on practice and theory in public key cryptography (Pacifico Yokohama, Japan, February 5-6, 1998): Proc. B.; Hdbl.: Springer, 1998. Pp. 203-216. DOI: 10.1007/BFb0054026
20. Yamamura A. A functional cryptosystem using a group action // Information security and privacy: 4th Australasian conf. on information security and privacy: ACISP 1999 (Wollongong, NSW, Australia, April 7-9, 1999): Proc. B.; Hdbl.: Springer, 1999. Pp. 314-325. DOI: 10.1007/3-540-48970-3_26
21. Paeng S.H., Ha K.C., Kim J.H., Chee S., Park C. New public key cryptosystem using finite non abelian groups // Advances in cryptology – CRYPTO 2001: 21st Annual intern. cryptology conf. (Santa Barbara, CA, USA, August 19-23, 2001): Proc. B.; Hdbl.: Springer, 2001. Pp. 470-485. DOI: 10.1007/3-540-44647-8_28
22. Paeng S.H., Kwon D., Ha K., Kim J.H. Improved public key cryptosystem using finite non abelian groups. Cryptology ePrint Archive: Report 2001/066. Rezhim dostupa: http://eprint.iacr.org/2001/066 (data obrashcheniya 15.12.2018).
23. Sakalauskas E., Tvarijonas P., Raulynaitis A. Key agreement protocol (KAP) using conjugacy and discrete logarithm problems in group representation level // Informatica. 2007. Vol. 18. No. 1. Pp. 115 - 124.
24. Novikov P.S. Ob algoritmicheskoi nerazreshimosti problemy tozhdestva slov v teorii grupp // Tr. Matem. in-ta AN SSSR. 1955. T. 44. S.1-144
