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

Cryptanalysis of a noncommutative key exchange protocol

1. 

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

Received  July 2014 Revised  February 2015 Published  May 2015

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.
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, (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. 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), (2000), 392. 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.

[6]

T. ElGamal, A public-key cryptosystem and a signature scheme based on discrete logarithms,, IEEE Trans. Inf. Theory, 31 (1985), 469. 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. 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. 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. doi: 10.3934/amc.2007.1.489.

[10]

G. Micheli, J. Rosenthal and P. Vettori, Linear spanning sets for matrix spaces,, preprint, ().

[11]

G. Micheli and M. Schiavina, A general construction for monoid-based knapsack protocols,, Adv. Math. Commun., 8 (2014), 343. doi: 10.3934/amc.2014.8.343.

[12]

D. Naccache and J. Stern, A new public key cryptosystem,, in Advances in Cryptology, (1997), 27. 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., (1998), 59. 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.

[15]

D. Pointcheval, Rabin cryptosystem,, in Encyclopedia of Cryptography and Security, (2011), 1013. 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. doi: 10.1145/359340.359342.

[17]

Slavin, Public key cryptography using matrices,, available at , (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. 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. 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, (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. 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), (2000), 392. 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.

[6]

T. ElGamal, A public-key cryptosystem and a signature scheme based on discrete logarithms,, IEEE Trans. Inf. Theory, 31 (1985), 469. 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. 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. 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. doi: 10.3934/amc.2007.1.489.

[10]

G. Micheli, J. Rosenthal and P. Vettori, Linear spanning sets for matrix spaces,, preprint, ().

[11]

G. Micheli and M. Schiavina, A general construction for monoid-based knapsack protocols,, Adv. Math. Commun., 8 (2014), 343. doi: 10.3934/amc.2014.8.343.

[12]

D. Naccache and J. Stern, A new public key cryptosystem,, in Advances in Cryptology, (1997), 27. 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., (1998), 59. 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.

[15]

D. Pointcheval, Rabin cryptosystem,, in Encyclopedia of Cryptography and Security, (2011), 1013. 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. doi: 10.1145/359340.359342.

[17]

Slavin, Public key cryptography using matrices,, available at , (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. 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. 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]

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

[4]

Angelo Favini, Rabah Labbas, Stéphane Maingot, Maëlis Meisner. Boundary value problem for elliptic differential equations in non-commutative cases. Discrete & Continuous Dynamical Systems - A, 2013, 33 (11&12) : 4967-4990. doi: 10.3934/dcds.2013.33.4967

[5]

Timoteo Carletti. The lagrange inversion formula on non--Archimedean fields, non--analytical form of differential and finite difference equations. Discrete & Continuous Dynamical Systems - A, 2003, 9 (4) : 835-858. doi: 10.3934/dcds.2003.9.835

[6]

Leonid Golinskii, Mikhail Kudryavtsev. An inverse spectral theory for finite CMV matrices. Inverse Problems & Imaging, 2010, 4 (1) : 93-110. doi: 10.3934/ipi.2010.4.93

[7]

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

[8]

Igor E. Shparlinski. On some dynamical systems in finite fields and residue rings. Discrete & Continuous Dynamical Systems - A, 2007, 17 (4) : 901-917. doi: 10.3934/dcds.2007.17.901

[9]

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

[10]

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

[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]

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

[13]

Stephen M. Gagola III, Joanne L. Hall. Constructing commutative semifields of square order. Advances in Mathematics of Communications, 2016, 10 (2) : 291-306. doi: 10.3934/amc.2016006

[14]

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

[15]

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

[16]

Liren Lin, Hongwei Liu, Bocong Chen. Existence conditions for self-orthogonal negacyclic codes over finite fields. Advances in Mathematics of Communications, 2015, 9 (1) : 1-7. doi: 10.3934/amc.2015.9.1

[17]

Konstantinos Drakakis, Rod Gow, Scott Rickard. Parity properties of Costas arrays defined via finite fields. Advances in Mathematics of Communications, 2007, 1 (3) : 321-330. doi: 10.3934/amc.2007.1.321

[18]

Uwe Helmke, Jens Jordan, Julia Lieb. Probability estimates for reachability of linear systems defined over finite fields. Advances in Mathematics of Communications, 2016, 10 (1) : 63-78. doi: 10.3934/amc.2016.10.63

[19]

Vincent Naudot, Jiazhong Yang. Finite smooth normal forms and integrability of local families of vector fields. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 667-682. doi: 10.3934/dcdss.2010.3.667

[20]

David Grant, Mahesh K. Varanasi. Duality theory for space-time codes over finite fields. Advances in Mathematics of Communications, 2008, 2 (1) : 35-54. doi: 10.3934/amc.2008.2.35

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]