ГлавнаяАрхивМетод нелинейного разложения для анализа криптографических схем, использующих автоморфизмы групп

Метод нелинейного разложения для анализа криптографических схем, использующих автоморфизмы групп | Прикладная дискретная математика. 2018. № 41. DOI: 10.17223/20710410/41/4

Показано применение метода нелинейного разложения для криптографического анализа на примере двух схем, которые используют автоморфизмы группы. При некоторых ограничениях на группу, выбранную в качестве платформы шифрования, данный метод работает эффективно и позволяет раскрывать секретную информацию (распределяемый ключ или пересылаемое сообщение) без решения алгоритмически сложных проблем, заложенных в основу схемы. Такими являются нетеровы группы, для которых эффективно решается проблема поиска вхождения элемента в заданную подгруппу. В частности, этим свойством обладают конечно порожденные нильпотентные или, более общо, полициклические группы, часто рекомендуемые в качестве платформ в современной алгебраической криптографии.
  • Title Метод нелинейного разложения для анализа криптографических схем, использующих автоморфизмы групп
  • Headline Метод нелинейного разложения для анализа криптографических схем, использующих автоморфизмы групп
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 41
  • Date:
  • DOI 10.17223/20710410/41/4
Ключевые слова
криптография, криптоанализ, 'распределение ключа, нелинейное разложение, проблема поиска вхождения, cryptography, cryptanalysis, key exchange, nonlinear decomposition, membership search problem
Авторы
Ссылки
Roman'kov V. A. A nonlinear decomposition attack // Groups Complexity Cryptology. 2017. V. 8. P. 197-207.
Mahalanobis A. The Diffie - Hellman key exchange protocol and non-abelian nilpotent groups // Israel J. Math. 2008. V. 165. P. 161-187.
Mahalanobis A. A simple generalization of El-Gamal cryptosystem to non-abelian groups // Communications in Algebra. 2008. V. 36. P. 3878-3889.
Mahalanobis A. A simple generalization of El-Gamal cryptosystem to non-abelian groups II // Communications in Algebra. 2012. V. 40. P. 171-186.
Романьков В. А. Введение в криптографию. Курс лекций. М.: Форум, 2012. 240 с.
Романьков В. А. Алгебраическая криптография. Омск: Изд-во ОмГУ, 2013. 135 с.
Романьков В. А. Криптографический анализ некоторых известных схем шифрования, использующих автоморфизмы // Прикладная дискретная математика. 2013. №3(21). С. 35-51.
Myasnikov A. G. and Roman'kov V. A. A linear decomposition attack // Groups Complexity Cryptology. 2015. V.7. P. 81-94.
Eick B. and Kahrobaei D. Polycyclic groups: A new platform for cryptology? arXiv math.: 0411.077v1 [math.GR].
Gryak K. J. and Kahrobaei D. The status of polycyclic group-based cryptography: A survey and open problems // Groups Complexity Cryptology. 2017. V. 8. P. 171-186.
Cavallo B. and Kahrobaei D. A family of polycyclic groups over which the conjugacy problem is NP-complete. arXiv math.: 1403.4153v2 [math. GR], 19 Mar 2014. P. 1-14.
Macdonald J., Miasnikov A., Nikolaev A., and Vassileva S. Logspace and compressed-word computations in nilpotentgroups. arXiv math.:1503.03888 [math.GR]. 2015.
Macdonald J., Miasnikov A., and Ovchinnikov D. Low-complexity computations for nilpotent subgroup theorem. arXiv math.: 1706.01092v2 [math. GR] 4 Jul 2017. 23 p.
Miasnikov A. and Weift A. TC0 circuits for algorithmic problems in nilpotent groups // 42nd Intern. Symp. MFCS. 2017. Article No. 23.
Метод нелинейного разложения для анализа криптографических схем, использующих автоморфизмы групп | Прикладная дискретная математика. 2018. № 41. DOI: 10.17223/20710410/41/4
Метод нелинейного разложения для анализа криптографических схем, использующих автоморфизмы групп | Прикладная дискретная математика. 2018. № 41. DOI: 10.17223/20710410/41/4