Cryptanalysis of a noncommutative key exchange protocol

Previous Article
AMC Home
This Issue
Next Article
Families of nested completely regular codes and distance-regular graphs

May 2015, 9(2): 247-253. doi: 10.3934/amc.2015.9.247

Cryptanalysis of a noncommutative key exchange protocol

Giacomo Micheli ^1,

1.	Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, Zürich, Switzerland

Received July 2014 Revised February 2015 Published May 2015

Abstract
Related Papers

In the papers by Alvarez et al. and Pathak and Sanghi a non-commutative based public key exchange is described. A similiar version of it has also been patented (US7184551). In this paper we present a polynomial time attack that breaks the variants of the protocol presented in the two papers. Moreover we show that breaking the patented cryptosystem US7184551 can be easily reduced to factoring. We also give some examples to show how efficiently the attack works.

Keywords: cryptanalysis, finite fields., Cryptography, non commutative protocols, matrices.

Mathematics Subject Classification: Primary: 94A60; Secondary: 11T7.

Citation: Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247

References:

[1]	R. Álvarez, F. Martinez, J. Vicent and A. Zamora, A new public key cryptosystem based on matrices, in 6th WSEAS Int. Conf. Inform. Secur. Privacy, Tenerife, Spain, 2007.
[2]	R. Álvarez, L. Tortosa, J. Vicent and A. Zamora, Analysis and design of a secure key exchange scheme, Inform. Sci., 179 (2009), 2014-2021. doi: 10.1016/j.ins.2009.02.008.
[3]	M. F. Atiyah and I. G. MacDonald, Introduction to Commutative Algebra, Westview Press, 1969.
[4]	N. Courtois, A. Klimov, J. Patarin and A. Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, in Advances in Cryptology - EUROCRYPT 2000 (ed. B. Preneel), Springer, Berlin, 2000, 392-407. doi: 10.1007/3-540-45539-6_27.
[5]	W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory, IT-22 (1976), 644-654.
[6]	T. ElGamal, A public-key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inf. Theory, 31 (1985), 469-472. doi: 10.1109/TIT.1985.1057074.
[7]	J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139 (1999), 61-88. doi: 10.1016/S0022-4049(99)00005-5.
[8]	J. Hoffstein, J. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, in Algorithmic Number Theory, 1998, 267-288. doi: 10.1007/BFb0054868.
[9]	G. Maze and C. Monico and J.Rosenthal, Public key cryptography based on semigroup actions, Adv. Math. Commun., 1 (2007), 489-507. doi: 10.3934/amc.2007.1.489.
[10]	G. Micheli, J. Rosenthal and P. Vettori, Linear spanning sets for matrix spaces, preprint, arXiv:1409.3020
[11]	G. Micheli and M. Schiavina, A general construction for monoid-based knapsack protocols, Adv. Math. Commun., 8 (2014), 343-358. doi: 10.3934/amc.2014.8.343.
[12]	D. Naccache and J. Stern, A new public key cryptosystem, in Advances in Cryptology, EUROCRYPT, 1997, 27-36. doi: 10.1007/3-540-69053-0_3.
[13]	D. Naccache and J. Stern, A new public key cryptosystem based on higher residues, in Proc. 5th ACM Conf. Computer Commun. Secur., San Francisco, 1998, 59-66. doi: 10.1145/288090.288106.
[14]	H. K. Pathak and M. Sanghi, Public key cryptosystem and a key exchange protocol using tools of non-abelian groups, Int. J. Comput. Sci. Engin., 2 (2010), 1029-1033.
[15]	D. Pointcheval, Rabin cryptosystem, in Encyclopedia of Cryptography and Security, Springer, 2011, 1013-1014. doi: 10.1007/978-1-4419-5906-5_151.
[16]	R. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21 (1978), 120-126. doi: 10.1145/359340.359342.
[17]	Slavin, Public key cryptography using matrices, available at http://www.patentgenius.com/patent/7184551.html, 2007.
[18]	R. Steinwandt and A. S. Corona, Cryptanalysis of a 2-party key establishment based on a semigroup action problem, Adv. Math. Commun., 5 (2011), 87-92. doi: 10.3934/amc.2011.5.87.
[19]	M. I. G. Vasco, A. L. Pérez del Pozo, P. T. Duarte and J. L. Villar, Cryptanalysis of a key exchange scheme based on block matrices, Inf. Sc., 276 (2014), 319-331. doi: 10.1016/j.ins.2013.11.009.

show all references

References:

[1]	R. Álvarez, F. Martinez, J. Vicent and A. Zamora, A new public key cryptosystem based on matrices, in 6th WSEAS Int. Conf. Inform. Secur. Privacy, Tenerife, Spain, 2007.
[2]	R. Álvarez, L. Tortosa, J. Vicent and A. Zamora, Analysis and design of a secure key exchange scheme, Inform. Sci., 179 (2009), 2014-2021. doi: 10.1016/j.ins.2009.02.008.
[3]	M. F. Atiyah and I. G. MacDonald, Introduction to Commutative Algebra, Westview Press, 1969.
[4]	N. Courtois, A. Klimov, J. Patarin and A. Shamir, Efficient algorithms for solving overdefined systems of multivariate polynomial equations, in Advances in Cryptology - EUROCRYPT 2000 (ed. B. Preneel), Springer, Berlin, 2000, 392-407. doi: 10.1007/3-540-45539-6_27.
[5]	W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory, IT-22 (1976), 644-654.
[6]	T. ElGamal, A public-key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inf. Theory, 31 (1985), 469-472. doi: 10.1109/TIT.1985.1057074.
[7]	J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139 (1999), 61-88. doi: 10.1016/S0022-4049(99)00005-5.
[8]	J. Hoffstein, J. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, in Algorithmic Number Theory, 1998, 267-288. doi: 10.1007/BFb0054868.
[9]	G. Maze and C. Monico and J.Rosenthal, Public key cryptography based on semigroup actions, Adv. Math. Commun., 1 (2007), 489-507. doi: 10.3934/amc.2007.1.489.
[10]	G. Micheli, J. Rosenthal and P. Vettori, Linear spanning sets for matrix spaces, preprint, arXiv:1409.3020
[11]	G. Micheli and M. Schiavina, A general construction for monoid-based knapsack protocols, Adv. Math. Commun., 8 (2014), 343-358. doi: 10.3934/amc.2014.8.343.
[12]	D. Naccache and J. Stern, A new public key cryptosystem, in Advances in Cryptology, EUROCRYPT, 1997, 27-36. doi: 10.1007/3-540-69053-0_3.
[13]	D. Naccache and J. Stern, A new public key cryptosystem based on higher residues, in Proc. 5th ACM Conf. Computer Commun. Secur., San Francisco, 1998, 59-66. doi: 10.1145/288090.288106.
[14]	H. K. Pathak and M. Sanghi, Public key cryptosystem and a key exchange protocol using tools of non-abelian groups, Int. J. Comput. Sci. Engin., 2 (2010), 1029-1033.
[15]	D. Pointcheval, Rabin cryptosystem, in Encyclopedia of Cryptography and Security, Springer, 2011, 1013-1014. doi: 10.1007/978-1-4419-5906-5_151.
[16]	R. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21 (1978), 120-126. doi: 10.1145/359340.359342.
[17]	Slavin, Public key cryptography using matrices, available at http://www.patentgenius.com/patent/7184551.html, 2007.
[18]	R. Steinwandt and A. S. Corona, Cryptanalysis of a 2-party key establishment based on a semigroup action problem, Adv. Math. Commun., 5 (2011), 87-92. doi: 10.3934/amc.2011.5.87.
[19]	M. I. G. Vasco, A. L. Pérez del Pozo, P. T. Duarte and J. L. Villar, Cryptanalysis of a key exchange scheme based on block matrices, Inf. Sc., 276 (2014), 319-331. doi: 10.1016/j.ins.2013.11.009.

[1]	Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281
[2]	Shengtian Yang, Thomas Honold. Good random matrices over finite fields. Advances in Mathematics of Communications, 2012, 6 (2) : 203-227. doi: 10.3934/amc.2012.6.203
[3]	Kishan Chand Gupta, Sumit Kumar Pandey, Indranil Ghosh Ray, Susanta Samanta. Cryptographically significant mds matrices over finite fields: A brief survey and some generalized results. Advances in Mathematics of Communications, 2019, 13 (4) : 779-843. doi: 10.3934/amc.2019045
[4]	Thomas Westerbäck. Parity check systems of nonlinear codes over finite commutative Frobenius rings. Advances in Mathematics of Communications, 2017, 11 (3) : 409-427. doi: 10.3934/amc.2017035
[5]	Timoteo Carletti. The lagrange inversion formula on non--Archimedean fields, non--analytical form of differential and finite difference equations. Discrete and Continuous Dynamical Systems, 2003, 9 (4) : 835-858. doi: 10.3934/dcds.2003.9.835
[6]	Angelo Favini, Rabah Labbas, Stéphane Maingot, Maëlis Meisner. Boundary value problem for elliptic differential equations in non-commutative cases. Discrete and Continuous Dynamical Systems, 2013, 33 (11&12) : 4967-4990. doi: 10.3934/dcds.2013.33.4967
[7]	Leonid Golinskii, Mikhail Kudryavtsev. An inverse spectral theory for finite CMV matrices. Inverse Problems and Imaging, 2010, 4 (1) : 93-110. doi: 10.3934/ipi.2010.4.93
[8]	Stefania Fanali, Massimo Giulietti, Irene Platoni. On maximal curves over finite fields of small order. Advances in Mathematics of Communications, 2012, 6 (1) : 107-120. doi: 10.3934/amc.2012.6.107
[9]	Igor E. Shparlinski. On some dynamical systems in finite fields and residue rings. Discrete and Continuous Dynamical Systems, 2007, 17 (4) : 901-917. doi: 10.3934/dcds.2007.17.901
[10]	Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459
[11]	Francis N. Castro, Carlos Corrada-Bravo, Natalia Pacheco-Tallaj, Ivelisse Rubio. Explicit formulas for monomial involutions over finite fields. Advances in Mathematics of Communications, 2017, 11 (2) : 301-306. doi: 10.3934/amc.2017022
[12]	Robert Granger, Thorsten Kleinjung, Jens Zumbrägel. Indiscreet logarithms in finite fields of small characteristic. Advances in Mathematics of Communications, 2018, 12 (2) : 263-286. doi: 10.3934/amc.2018017
[13]	Lorenza D'Elia. $ \Gamma $-convergence of quadratic functionals with non uniformly elliptic conductivity matrices. Networks and Heterogeneous Media, 2022, 17 (1) : 15-45. doi: 10.3934/nhm.2021022
[14]	Joan-Josep Climent, Elisa Gorla, Joachim Rosenthal. Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications, 2007, 1 (1) : 1-11. doi: 10.3934/amc.2007.1.1
[15]	M. J. Jacobson, R. Scheidler, A. Stein. Cryptographic protocols on real hyperelliptic curves. Advances in Mathematics of Communications, 2007, 1 (2) : 197-221. doi: 10.3934/amc.2007.1.197
[16]	Fatma-Zohra Benahmed, Kenza Guenda, Aicha Batoul, Thomas Aaron Gulliver. Some new constructions of isodual and LCD codes over finite fields. Advances in Mathematics of Communications, 2019, 13 (2) : 281-296. doi: 10.3934/amc.2019019
[17]	Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[18]	Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101
[19]	Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475
[20]	Nian Li, Qiaoyu Hu. A conjecture on permutation trinomials over finite fields of characteristic two. Advances in Mathematics of Communications, 2019, 13 (3) : 505-512. doi: 10.3934/amc.2019031

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Giacomo Micheli
on Google Scholar
Giacomo Micheli

[Back to Top]