American Institute of Mathematical Sciences

Advanced
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

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. Google Scholar

[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.  Google Scholar

[3]

M. F. Atiyah and I. G. MacDonald, Introduction to Commutative Algebra, Westview Press, 1969. Google Scholar

[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.  Google Scholar

[5]

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory, IT-22 (1976), 644-654.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[15]

D. Pointcheval, Rabin cryptosystem, in Encyclopedia of Cryptography and Security, Springer, 2011, 1013-1014. doi: 10.1007/978-1-4419-5906-5_151.  Google Scholar

[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.  Google Scholar

[17]

Slavin, Public key cryptography using matrices, available at http://www.patentgenius.com/patent/7184551.html, 2007. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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. Google Scholar

[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.  Google Scholar

[3]

M. F. Atiyah and I. G. MacDonald, Introduction to Commutative Algebra, Westview Press, 1969. Google Scholar

[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.  Google Scholar

[5]

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory, IT-22 (1976), 644-654.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[15]

D. Pointcheval, Rabin cryptosystem, in Encyclopedia of Cryptography and Security, Springer, 2011, 1013-1014. doi: 10.1007/978-1-4419-5906-5_151.  Google Scholar

[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.  Google Scholar

[17]

Slavin, Public key cryptography using matrices, available at http://www.patentgenius.com/patent/7184551.html, 2007. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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

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

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

Lorenza D'Elia. $ \Gamma $-convergence of quadratic functionals with non uniformly elliptic conductivity matrices. Networks & 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]

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

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

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

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

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

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

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (120)
  • HTML views (0)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy