Cryptanalysis of some schemes applying automorphisms

V. A. Romankov

Prikladnaâ diskretnaâ matematika, no. 3 (2013), pp. 35-51.

Résumé

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 Megreleshvili 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.

Détail

Keywords: cryptographic scheme, group algebra, loop algebra, graded algebra, discrete logarithm, generalized discrete logarithm, Diffie–Hellman scheme
Mots-clés : matrix algebra, El Gamal protocol, automorphism.

Bibliographie

[1] Diffie W., Hellman M. E., “New directions in cryptography”, IEEE Trans. Inform. Theory, 22 (1976), 644–654 | DOI | MR | Zbl

[2] Hellman M. E., “An overview of public key cryptography”, IEEE Communication Magazine, 40:5 (2002), 42–49 | DOI

[3] Menezes A., Vanstone S., “A note on cyclic groups, finite fields, and the discrete logarithm problem”, Applicable algebra in Engineering, Communication and Computing, 3 (1992), 67–74 | DOI | MR | Zbl

[4] Menezes A. J., Wu Y.-H., “The discrete logarithm problem in $\mathrm{GL}(n,q)$”, Ars Combinatoria, 47 (1997), 23–32 | MR | Zbl

[5] Romankov V. A., Algebraicheskaya kriptografiya, Izd-vo Om. un-ta, Omsk, 2013, 207 pp.

[6] Myasnikov A., Shpilrain V., Ushakov A., Group-based cryptography, Advances courses in Math., CRM, Barselona, Birkhäuser Verlag, Basel–Berlin–New York, 2008, 183 pp. | MR | Zbl

[7] Myasnikov A., Shpilrain V., Ushakov A., Non-commutative cryptography and complexity of group-theoretic problems, Amer. Math. Soc. Surveys and Monographs, Amer. Math. Soc., Providence, RI, 2011, 385 pp. | MR | Zbl

[8] ElGamal T., “A public key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Trans. Inform. Theory, IT-31:4 (1985), 469–472 | DOI | MR | Zbl

[9] Menezes A. J., van Oorschot P. C., Vanstone S. A., Handbook of Applied Cryptography, CRC Press, 1996, 816 pp.

[10] Koblitz N., A Course in Number Theory and Cryptology, Springer Verlag, New York–Heidelberg–Berlin, 1994 | MR | Zbl

[11] Romankov V. A., Vvedenie v kriptografiyu, Kurs lektsii, Forum, M., 2012, 240 pp.

[12] Krammer D., “Braid groups are linear”, Ann. Math., 151 (2002), 131–156 | DOI | MR

[13] Dehornoy P., “Braid-based cryptography”, Contemp. Math., 360 (2004), 5–33 | DOI | MR | Zbl

[14] Garber D., Braid group cryptography, Lecture notes of Tutorials given at Braids PRIMA Summer School at Singapore, June 2007, 27 Sep. 2008, 39 pp., arXiv: 0711.3941v2[math.cs.CR] | MR

[15] Mahlburg K., An overview of braid groups cryptography, , 2004 www.math.wisc.edu/~boston/mahlburg.pdf

[16] Kargapolov M. I., Merzlyakov Yu. I., Osnovy teorii grupp, Nauka, M., 1972 | MR | Zbl

[17] Lennox J. C., Robinson D. J. S., The Theory of Infinite Soluble Groups, Oxford Math. Monographs, Oxford Science Publications, Oxford, 2004 | MR | Zbl

[18] Megrelishvili R. P., Dzhindzhikhadze M. V., “Odnonapravlennaya matrichnaya funktsiya dlya obmena kriptograficheskimi klyuchami, metod generatsii multiplikativnykh matrichnykh grupp”, Proc. Intern. Conf. SAIT (2011, May 23–28, Kyiv, Ukraine), 472

[19] Megrelishvili R., Chelidze M., Chelidze K., “On the construction of secret and public-key cryptosystems”, Appl. Math., Inform. Mech., 11:2 (2006), 29–36 | MR | Zbl

[20] Megrelishvili R., Chelidze M., Besiashvili G., “One-way matrix function – analogy of Diffie–Hellman protocol”, Proc. Seventh Intern. Conf. IES-2010 (28 Sept.–3 Oct., 2010, Vinnytsia, Ukraine), 341–344

[21] Rososhek S. K., “Kriptosistemy gruppovykh kolets”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2003, no. 6, 57–62

[22] Rososhek S. K., “Kriptosistemy v gruppakh avtomorfizmov gruppovykh kolets abelevykh grupp”, Fundamentalnaya i prikladnaya matematika, 13:3 (2007), 157–164 | MR | Zbl

[23] Markov V. T., Mikhalev A. V., Gribov A. V. i dr., “Kvazigruppy i koltsa v kodirovanii i postroenii kriptoskhem”, Prikladnaya diskretnaya matematika, 2012, no. 4(18), 31–52

[24] Belousov V. D., Osnovy teorii kvazigrupp i lup, Nauka, M., 1967 | MR | Zbl

[25] Pflugfelder H. O., Quasigroups and Loops: Introduction, Heldermann Verlag, Berlin, 1990 | MR

[26] Smith J. D. H., An Introduction to Quasigroups and their representations, Chapman Hall/CRC, Boca Raton, FL, 2007 | MR | Zbl

[27] Gribov A. V., Zolotykh P. A., Mikhalev A. V., “Postroenie algebraicheskoi kriptosistemy nad kvazigruppovym koltsom”, Matematicheskie voprosy kriptografii, 1:4 (2010), 23–32

[28] Mahalanobis A., “The Diffie-Hellman key exchange protocol and non-abelian nilpotent groups”, Israel J. Math., 165 (2008), 161–187 | DOI | MR | Zbl

[29] Merzlyakov Yu. I., “Tselochislennoe predstavlenie golomorfov politsiklicheskikh grupp”, Algebra i logika, 9:5 (1970), 539–558 | MR | Zbl

[30] Romanczuk U., Ustimenko V., On the $PSL2(q),$ Ramanujan graphs and key exchange protocols, http://aca.aulonapress.com/index.php/aca2010/aca2010/paper/viewFile/80/3

[31] Blackburn S. R., Cid C., Mullan C., “Cryptanalysis of three matrix-based key establishment protocols”, J. Mathematical Cryptology, 5 (2011), 159–168 | MR | Zbl