Приводится криптографический анализ протокола аутентификации Ушакова - Шпильрайна, базирующегося на проблеме бинарно скрученной сопряжённости относительно пары эндоморфизмов полугруппы 2 х 2-матриц над кольцом срезанных многочленов с коэффициентами из поля F2. Показано, что закрытый ключ протокола может быть вычислен путём решения системы линейных уравнений над полем F2. Представлена теоретическая оценка сложности алгоритма данного криптографического анализа и дано краткое описание практических результатов, полученных с помощью подготовленной программы. Анализ показывает, что рассматриваемый протокол аутентификации является теоретически и практически нестойким.
Скачать электронную версию публикации
Загружен, раз: 450
- Title Криптографический анализ протокола аутентификации Ушакова - Шпильрайна, основанного на проблеме бинарно скрученной сопряжённости
- Headline Криптографический анализ протокола аутентификации Ушакова - Шпильрайна, основанного на проблеме бинарно скрученной сопряжённости
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 2 (28)
- Date:
- DOI
Ключевые слова
криптография, аутентификация, эндоморфизм, скрученная сопряжённость, срезанные многочлены, cryptography, authentication, endomorphism, twisted conjugacy, truncated polynomialsАвторы
Ссылки
Myasnikov A., Shpilrain V., and Ushakov A. Group-Based Cryptography. Advances courses in Math., CRM, Barselona. Basel, Berlin, New York: Birkhauser Verlag, 2008. 183 p.
Myasnikov A., Shpilrain V., and Ushakov A. Non-commutative Cryptography and Complexity of Group-Theoretic Problems. Amer. Math. Soc. Surveys and Monographs. Providence R.I.: Amer. Math. Soc., 2011. 385 p.
Романьков В А. Диофантова криптография на бесконечных группах // Прикладная дискретная математика. 2012. №2(16). С. 15-42.
Романьков В. А. Алгебраическая криптография. Омск: ОмГУ, 2013. 135 с.
Shpilrain V. and Ushakov A. An authentication scheme based on the twisted conjugacy problem // ACNS'2008. LNCS. 2008. V. 5037. P. 366-372.
Fel'shtyn A. and Troitsky E. Twisted Burnside - Frobenius theory for discrete groups // J. Reine Angew. Math. 2007. V. 613. P. 193-210.
Goncalves D. and Wong P. Twisted conjugacy classes in nilpotent groups // J. Reine Angew. Math. 2009. V. 633. P. 11-27.
Roman'kov V. The twisted conjugacy problem in polycyclic groups // J. Group Theory. 2010. V. 13. No. 3. P. 353-364.
Вентура Э., Романьков В. А. Проблема скрученной сопряжённости для эндоморфизмов метабелевых групп // Алгебра и логика. 2009. Т. 48. №2. С. 157-173.
Roman'kov V. Twisted conjugacy classes in nilpotent groups // J. Pure Appl. Algebra. 2011. V. 215. No. 4. P. 664-671.
Fel'shtyn A. and Goncalves D. L. Reidemeister spectrum for metabelian groups // Int. J. Algebra Comput. 2011. V.21. No.3. P. 1-16.
Ремесленников В.Н., Романьков В. А. Теоретико-модельные и алгоритмические проблемы теории групп // Итоги науки и техн. Сер. Алгебра. Геометрия. Топология. Т. 21. М.: ВИНИТИ, 1983. С. 3-79.
Miller C. F. Decision problems for groups: survey and reflections // Algorithms and Classification in Combinatorial Group Theory /eds. G. Baumslag and C.F. Miller III. MSRI Publications, 1992. V.23. P. 1-59.
Романьков В А. Криптографический анализ некоторых схем шифрования, использующих автоморфизмы // Прикладная дискретная математика. 2013. №3(21). С. 36-51.
Roman'kov V. and Myasnikov A. A linear decomposition attack. arXiv:1412.6401v1[math. GR]. 19 Dec. 2014.
Roman'kov V. A polynomial time algorithm for the braid double shielded public key cryptosystem. arXiv:1412.5277v1[math.GR]. 17 Dec. 2014.
Roman'kov V. Linear decomposition attack on public key exchange protocols using semidirect products of (semi)groups. arXiv:1501.0052v1[cs.CR]. 15 Jan. 2015.
Biirgisser P., Clausen M., and Shokrollalu M. A. Algebraic Complexity Theory. Berlin: Springer, 1997.
Криптографический анализ протокола аутентификации Ушакова - Шпильрайна, основанного на проблеме бинарно скрученной сопряжённости | Прикладная дискретная математика. 2015. № 2 (28).
Скачать полнотекстовую версию
Загружен, раз: 1302