Приводится криптографический анализ схем шифрования и распределения ключа, базирующихся на групповых (луповых) алгебрах и градуированных алгебрах с мультипликативным базисом, предложенных в работах С. К. Росошека, А. В. Михалева и др., А. Махалонобиса и др. Объединяет эти схемы (кроме одной из схем А. В. Михалева и др.) использование в них автоморфизмов. Приводится также криптографический анализ протокола распределения ключа Мегрелишви-ли и Джинджихадзе. Описывается оригинальный метод нахождения шифрованного сообщения или общего ключа, основанный на обычном аппарате линейной алгебры, при условии, что соответствующая платформа может быть выбрана как конечномерная алгебра, например как матричная алгебра над полем. Метод не предполагает нахождения секретных автоморфизмов, фигурирующих в указанных работах. Теоретические основы метода и ряд атак на его основе схем шифрования и распределения ключа, базирующихся на различных обобщениях задачи дискретного логарифма и идей Диффи — Хеллмана — Меркля на некоммутативные группы, изложены в других работах автора. Здесь метод находит новые применения.
Скачать электронную версию публикации
Загружен, раз: 93
- Title Криптографический анализ некоторых схем шифрования, использующих автоморфизмы
- Headline Криптографический анализ некоторых схем шифрования, использующих автоморфизмы
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 3(21)
- Date:
- DOI
Ключевые слова
automorphism, El Gamal protocol, Diffie — Hellman scheme, generalized discrete logarithm, discrete logarithm, graded algebra, matrix algebra, loop algebra, group algebra, cryptographic scheme, автоморфизм, протокол ЭльГамаля, схема Диффи — Хеллмана, обобщения дискретного логарифма, дискретный логарифм, градуированная алгебра, матричная алгебра, луповая алгебра, групповая алгебра, схема шифрованияАвторы
Ссылки
Blackburn S. R., Cid C., and Mullan C. Cryptanalysis of three matrix-based key establishment protocols // J. Mathematical Cryptology. 2011. V. 5. P. 159-168.
Romanczuk U. and Ustimenko V. On the PSL2(q), Ramanujan graphs and key exchange protocols // http://aca2010.info/index.php/aca2010/aca2010/paper/viewFile/80/3.
Мерзляков Ю. И. Целочисленное представление голоморфов полициклических групп // Алгебра и логика. 1970. Т. 9. №5. С. 539-558.
Mahalanobis A. The Diffie-Hellman key exchange protocol and non-abelian nilpotent groups // Israel J. Math. 2008. V. 165. P. 161-187.
Smith J. D. B. An Introduction to Quasigroups and their representations. Boca Raton, FL: Chapman & Hall/CRC, 2007.
Грибов А. В., Золотых П. А., Михалев А. В. Построение алгебраической криптосистемы над квазигрупповым кольцом // Математические вопросы криптографии. 2010. Т. 1. №4. С.23-33.
Pflugfelder B. O. Quasigroups and Loops: Introduction. Berlin: Heldermann Verlag, 1990.
Белоусов В. Д. Основы теории квазигрупп и луп. М.: Наука, 1967.
Марков В. Т., Михалев А. В., Грибов А. В. и др. Квазигруппы и кольца в кодировании и построении криптосхем // Прикладная дискретная математика. 2012. №4(18). С. 32-52.
Росошек С. К. Криптосистемы в группах автоморфизмов групповых колец абелевых групп // Фундаментальная и прикладная математика. 2007. Т. 13. №3. С. 157-164.
Росошек С. К. Криптосистемы групповых колец // Вестник Томского госуниверситета. Приложение. 2003. №6. С. 57-62.
Megrelishvili R., Chelidze M., and Besiashvili G. One-way matrix function — analogy of Diffie — Hellman protocol // Proc. Seventh Intern. Conf. IES-2010, 28 Sept.-3 Oct., Vinnytsia, Ukraine, 2010. P. 341-344.
Megrelishvili R., Chelidze M., and Chelidze K. On the construction of secret and public-key cryptosystems // Appl. Math., Inform. Mech. 2006. V. 11. No. 2. P. 29-36.
Lennox J. C. and Robinson D. J. S. The Theory of Infinite Soluble Groups. Oxford Math. Monographs. Oxford: Oxford Science Publications, 2004.
Мегрелишвили Р. П., Джинджихадзе М. В. Однонаправленная матричная функция для обмена криптографическими ключами, метод генерации мультипликативных матричных групп // Proc. Intern. Conf. SAIT 2011, May 23-28, Kyiv, Ukraine. P. 472.
Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. М.: Наука, 1972.
Dehornoy P. Braid-based cryptography // Contemp. Math. 2004. V. 360. P. 5-33.
Garber D. Braid group cryptography. Lecture notes of Tutorials given at Braids PRIMA Summer School at Singapore, June 2007. arXivmath.:0711.3941v2[cs.CR] 27 Sep. 2008. P. 1-39.
Mahlburg K. An overview of braid groups cryptography // www.math.wisc.edu/~boston/ mahlburg.pdf, 2004.
Романьков В. А. Введение в криптографию. Курс лекций. М.: Форум, 2012. 240 с.
Krammer D. Braid groups are linear // Ann. Math. 2002. V. 151. P. 131-156.
Koblitz N. A Course in Number Theory and Cryptology. New York, Heidelberg, Berlin: Springer Verlag, 1994.
ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE Trans. Inform. Theory. 1985. V.IT-31. No. 4. P. 469-472.
Menezes A. J., van Oorschot P. C., and Vanstone S. A. Handbook of Applied Cryptography. CRC Press, 1996. 816 p.
Myasnikov A., Shpilrain V., and Ushakov A. Non-commutative cryptography and complexity of group-theoretic problems. (Amer. Math. Soc. Surveys and Monographs). Providence, RI: Amer. Math. Soc., 2011. 385 p.
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.
Романьков В. А. Алгебраическая криптография. Омск: Изд-во Ом. ун-та, 2013. 207с.
Menezes A.J. and Wu Y.-B. The discrete logarithm problem in GL(n, q) // Ars Combinatoria. 1997. V.47. P. 23-32.
Menezes A. and Vanstone S. A note on cyclic groups, finite fields, and the discrete logarithm problem // Applicable algebra in Engineering, Communication and Computing. 1992. V. 3. P. 67-74.
Bellman M. E. An overview of public key cryptography // IEEE Communication Magazine. 2002. Iss. 50. P. 42-49.
Diffie W. and Bellman M. E. New directions in cryptography // IEEE Trans. Inform. Theory. 1976. V. 22. P. 644-654.
Криптографический анализ некоторых схем шифрования, использующих автоморфизмы | Прикладная дискретная математика. 2013. № 3(21).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 317