Some methods are given for cryptanalysis of encryption schemes and key establishment protocols based on a group (loop) algebra or on a graded algebra with multiplicative base and proposed by Rososhek; Mihalev et. al.; Mahalanobis, etc. These cryptosystems have a common feature that all of them (except the scheme of Mihalev) use automorphisms. Also, a cryptanalysis of the key exchange protocol proposed by Megre-leshvili and Djindjihadze is given. An original approach is described to find a secret message or a shared key based on usual tools of linear algebra assuming that platform can be chosen as a finite dimensional algebra, e. g., a matrix algebra over a field. The approach does not suppose to find the secret automorphism used in protocol. A theoretical foundation of this approach and a series of attacks on some cryptosystems based on different generalizations of discrete logarithm and Diffie — Hellman's ideas to noncommutative groups are described by the author earlier. Here the approach is developed by presenting its new applications in cryptanalysis of different schemes and protocols.
Download file
Counter downloads: 96
- Title Cryptanalysis of some schemes applying automorphisms
- Headline Cryptanalysis of some schemes applying automorphisms
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(21)
- Date:
- DOI
Keywords
automorphism, El Gamal protocol, Diffie — Hellman scheme, generalized discrete logarithm, discrete logarithm, graded algebra, matrix algebra, loop algebra, group algebra, cryptographic scheme, автоморфизм, протокол ЭльГамаля, схема Диффи — Хеллмана, обобщения дискретного логарифма, дискретный логарифм, градуированная алгебра, матричная алгебра, луповая алгебра, групповая алгебра, схема шифрованияAuthors
References
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.
Cryptanalysis of some schemes applying automorphisms | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 3(21).
Download full-text version
Download fileCounter downloads: 320