Preview

Математика и математическое моделирование

Расширенный поиск

Асимметричная схема передачи секретного ключа по открытому каналу в 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


Для цитирования:


Безверхний Н.В., Никитина М.В. Асимметричная схема передачи секретного ключа по открытому каналу в k-детерминированных группах с условиями C(3)-T(6). Математика и математическое моделирование. 2018;(6):88-111. https://doi.org/10.24108/mathm.0618.0000151

For citation:


Bezverkhniy N.V., Nikitina M.V. Asymmetric Secret Key Transfer Scheme over an Open Channel in K-Deterministic Groups with the Conditions C (3) –T (6). Mathematics and Mathematical Modeling. 2018;(6):88-111. (In Russ.) https://doi.org/10.24108/mathm.0618.0000151

Просмотров: 108


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)