New Practical Algebraic Public-Key Cryptosystem and Some Related Algebraic and Computational Aspects

Author(s)
S. K. Rososhek

ABSTRACT

The most popular present-day public-key
cryptosystems are RSA and ElGamal cryptosystems. Some practical algebraic
generalization of the ElGamal cryptosystem is considered-basic modular matrix
cryptosystem (BMMC) over the modular matrix ring *M*_{2}(Z_{n}).
An example of computation for an artificially small number *n* is presented. Some possible attacks on the cryptosystem and
mathematical problems, the solution of which are necessary for implementing
these attacks, are studied. For a small number *n*, computational time for compromising some present-day public-key
cryptosystems such as RSA, ElGamal, and Rabin, is compared with the
corresponding time for the ВММС. Finally, some open mathematical and computational problems are
formulated.

Cite this paper

S. Rososhek, "New Practical Algebraic Public-Key Cryptosystem and Some Related Algebraic and Computational Aspects,"*Applied Mathematics*, Vol. 4 No. 7, 2013, pp. 1043-1049. doi: 10.4236/am.2013.47142.

S. Rososhek, "New Practical Algebraic Public-Key Cryptosystem and Some Related Algebraic and Computational Aspects,"

References

[1] A. Menezes, P. van Ooshot and S. Vanstone, “Handbook of Applied Cryptography,” CRC Press, Waterloo, 1996. doi:10.1201/9781439821916

[2] P. W. Shor, “Algorithms for Quantum Computation: Discrete Logarithm and Factoring,” Proceedings of the IEEE 35th Communications Annual Symposium on Foundations of Computer Science, Santa Fe, 20-22 November 1994, pp. 124-134.

[3] S. K. Rososhek, “Cryptosystems in Automorphism Groups of Group Rings of Abelian Groups,” Fundamentalnaya I prikladnaya matematica, Vol. 13, No. 8, 2007, pp. 157-164 (in Russian).

[4] S. K. Rososhek, “Cryptosystems in Automorphism Groups of Group Rings of Abelian Groups,” Journal of Mathematical Sciences, Vol. 154, No. 3, 2008, pp. 386-391. doi:10.1007/s10958-008-9168-2

[5] A. N. Gribov, P. A. Zolotykh and A. V. Mikhalev, “A Construction of Algebraic Cryptosystem over the Quasigroup Ring,” Mathematical Aspects of Cryptography, Vol. 1, No. 4, 2010, pp. 23-32 (in Russian).

[6] K. N. Ponomarev, “Automorphically Rigid Group Alge bras I. Semisimple Algebras,” Algebra and Logic, Vol. 48, No. 5, 2009, pp. 654-674. doi:10.1007/s10469-009-9064-y

[7] K. N. Ponomarev, “Automorphically Rigid Group Alge bras II. Modular Algebras,” Algebra and Logic, Vol. 49, No. 2, 2010, pp. 216-237.

[8] K. N. Ponomarev, “Rigid Group Rings,” In: A. G. Pinus and K. N. Ponomarev, Eds., Algebra and Model Theory, 6, Novosobirsk Technical University Press, Novosibirsk, 2007, pp. 73-83 (in Russian). doi:10.1007/s10469-010-9086-5

[9] A. Popova and E. Poroshenko, “Units Group of Integral Group Rings of Finite Groups,” In: A. G. Pinus and K. N. Ponomarev, Eds., Algebra and Model Theory, 4, Novosi birsk Technical University Press, Novosibirsk, 2003, pp. 99-106 (in Russian).

[10] A. Dooms and E. Jespers, “Normal Complements of the Trivial Units in the Unit Group of Some Integral Group Rings,” Communications in Algebra, Vol. 31, No. 1, 2003, pp. 475-482. doi:10.1081/AGB-120016770

[11] Y. I. Merzlyakov, “Matrix Representations of Free Groups,” Doklady Akademii Nauk, Vol. 238, No. 3, 1978, pp. 527-533 (in Russian).

[12] A. Popova, “Group of Automorphisms of the Ring ,” In: A. G. Pinus and K. N. Ponomarev, Eds., Alge bra and Model Theory, 6, Novosibirsk Technical University Press, Novosibirsk, 2007, pp. 84-90 (in Russian).

[13] A. Mahalanobis, “A Simple Generalization of the ElGa mal Cryptosystem to Non-Abelian Groups,” Communications in Algebra, Vol. 36, No. 10, 2008, pp. 3878-3889. doi:10.1080/00927870802160883

[14] S.-H. Paeng, K.-C. Ha, J. N. Kim, S. Chee and C. Park, “New Public Key Cryptosystem Using Finite Non-Abelian Groups,” Proceedings of the Crypto 2001, Lecture Notes in Computer Sciences, Santa Barbara, 19-23 August 2001, pp. 470-485.

[15] M. I. Kargapolov and Y. I. Merzlyakov, “Foundations of Group Theory,” Nauka, Moscow, 1977 (in Russian).

[16] R. C. Lyndon and P. E. Schupp, “Combinatorial Group Theory,” Springer-Verlag, Berlin, Heidelberg, New York, 1977.

[1] A. Menezes, P. van Ooshot and S. Vanstone, “Handbook of Applied Cryptography,” CRC Press, Waterloo, 1996. doi:10.1201/9781439821916

[2] P. W. Shor, “Algorithms for Quantum Computation: Discrete Logarithm and Factoring,” Proceedings of the IEEE 35th Communications Annual Symposium on Foundations of Computer Science, Santa Fe, 20-22 November 1994, pp. 124-134.

[3] S. K. Rososhek, “Cryptosystems in Automorphism Groups of Group Rings of Abelian Groups,” Fundamentalnaya I prikladnaya matematica, Vol. 13, No. 8, 2007, pp. 157-164 (in Russian).

[4] S. K. Rososhek, “Cryptosystems in Automorphism Groups of Group Rings of Abelian Groups,” Journal of Mathematical Sciences, Vol. 154, No. 3, 2008, pp. 386-391. doi:10.1007/s10958-008-9168-2

[5] A. N. Gribov, P. A. Zolotykh and A. V. Mikhalev, “A Construction of Algebraic Cryptosystem over the Quasigroup Ring,” Mathematical Aspects of Cryptography, Vol. 1, No. 4, 2010, pp. 23-32 (in Russian).

[6] K. N. Ponomarev, “Automorphically Rigid Group Alge bras I. Semisimple Algebras,” Algebra and Logic, Vol. 48, No. 5, 2009, pp. 654-674. doi:10.1007/s10469-009-9064-y

[7] K. N. Ponomarev, “Automorphically Rigid Group Alge bras II. Modular Algebras,” Algebra and Logic, Vol. 49, No. 2, 2010, pp. 216-237.

[8] K. N. Ponomarev, “Rigid Group Rings,” In: A. G. Pinus and K. N. Ponomarev, Eds., Algebra and Model Theory, 6, Novosobirsk Technical University Press, Novosibirsk, 2007, pp. 73-83 (in Russian). doi:10.1007/s10469-010-9086-5

[9] A. Popova and E. Poroshenko, “Units Group of Integral Group Rings of Finite Groups,” In: A. G. Pinus and K. N. Ponomarev, Eds., Algebra and Model Theory, 4, Novosi birsk Technical University Press, Novosibirsk, 2003, pp. 99-106 (in Russian).

[10] A. Dooms and E. Jespers, “Normal Complements of the Trivial Units in the Unit Group of Some Integral Group Rings,” Communications in Algebra, Vol. 31, No. 1, 2003, pp. 475-482. doi:10.1081/AGB-120016770

[11] Y. I. Merzlyakov, “Matrix Representations of Free Groups,” Doklady Akademii Nauk, Vol. 238, No. 3, 1978, pp. 527-533 (in Russian).

[12] A. Popova, “Group of Automorphisms of the Ring ,” In: A. G. Pinus and K. N. Ponomarev, Eds., Alge bra and Model Theory, 6, Novosibirsk Technical University Press, Novosibirsk, 2007, pp. 84-90 (in Russian).

[13] A. Mahalanobis, “A Simple Generalization of the ElGa mal Cryptosystem to Non-Abelian Groups,” Communications in Algebra, Vol. 36, No. 10, 2008, pp. 3878-3889. doi:10.1080/00927870802160883

[14] S.-H. Paeng, K.-C. Ha, J. N. Kim, S. Chee and C. Park, “New Public Key Cryptosystem Using Finite Non-Abelian Groups,” Proceedings of the Crypto 2001, Lecture Notes in Computer Sciences, Santa Barbara, 19-23 August 2001, pp. 470-485.

[15] M. I. Kargapolov and Y. I. Merzlyakov, “Foundations of Group Theory,” Nauka, Moscow, 1977 (in Russian).

[16] R. C. Lyndon and P. E. Schupp, “Combinatorial Group Theory,” Springer-Verlag, Berlin, Heidelberg, New York, 1977.