Cryptanalysis of Tropical Encryption Scheme Based on Double Key Exchange
DOI:
https://doi.org/10.13052/jcsm2245-1439.1224Keywords:
Tropical semiring, Key-exchange protocol, Tropical linear equations, KU attackAbstract
A tropical encryption scheme is analyzed in this paper, which uses double key exchange protocol (KEP). The key exchange protocol is divided into two stages: The first stage of the key exchange uses matrix power function in a tropical semiring; the obtained shared key at the first phase of the key exchange serves as an input for the second phase. This paper proves that the common secret key of the first key exchange phase can be obtained by solving linear equations, and when the order of the matrix is 50, the time to solve the shared key is less than 1 second. Finally, the common secret key of the second phase can be obtained through KU attack and common secret key of the first key exchange. So the protocol isn’t secure.
Downloads
References
Rivest R L, Shamir A and Adleman L M. A method for obtaining digital signatures and public-key cryptosystems. Commun, ACM, 21, 120–126, 1978.
Diffie W, Hellman M E, “New directions in cryptography”. IEEE Transactions on Information Teory, 22(6), 644–654, 1976.
ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory, 31, 469–472, 1985.
Shor P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput, 26, 1484–1509, 1997.
Baumslag G, Fine B and Xu X. Cryptosystems using linear groups. Appl. Algebra Eng. Commun. Comput, 17, 205–217, 2006.
Kahrobaei D, Koupparis C and Shpilrain V. Public key exchange using matrices over group rings. Groups-Complex. Cryptol, 5, 97–115, 2013.
Rososhek S K. New practical algebraic public-key cryptosystem and some related algebraic and computational aspects. Appl. Math, 4, 1043–1049, 2013.
Rososhek S K. Modified matrix modular cryptosystems. Br. J. Math. Comput. Sci, 5, 613–636, 2015.
Anshel I, Anshel M and Goldfeld D. An algebraic method for public-key cryptography. Math. Res. Lett, 6, 287–291, 1999.
Garber D. Braid group cryptography. In Braids: Introductory Lectures on Braids, Configurations and Their Applications; World Scientific: Singapore, 329–403, 2010.
Paeng S H, Ha K C, Kim J H, Chee S and Park C. New public key cryptosystem using finite non Abelian groups. In Proceedings of the 21st Annual International Cryptology Conference, Santa Barbara, CA, USA, 19–23 August 2001, Springer: Berlin/Heidelberg, Germany, 470–485, 2001.
Hoffstein J, Pipher J, Silverman J H. NTRU: A ring-based public key cryptosystem. In Proceedings of the International Algorithmic Number Theory Symposium, Portland, OR, USA, 21–25 June 1998; Springer: Berlin/Heidelberg, Germany, 267–288, 1998.
Eftekhari M. Cryptanalysis of some protocols using matrices over group rings. In Proceedings of the 9th International Conference on Cryptology in Africa, Dakar, Senegal, 24–26 May 2017; Springer: Cham, Switzerland, 223–229, 2017.
Steinwandt R. Loopholes in two public key cryptosystems using the modular group. In Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2001, Cheju Island, Korea, 13–15 February 2001; Springer: Berlin/Heidelberg, Germany, 180–189, 2001.
Hofheinz D, Steinwandt R. A practical attack on some braid group based cryptographic primitives. In Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography, Miami, FL, USA, 6–8 January 2003; Springer: Berlin/Heidelberg, Germany, 187–198, 2003.
Gentry C, Szydlo M. Cryptanalysis of the revised NTRU signature scheme. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, 28 April–2 May 2002; Springer: Berlin/Heidelberg, Germany, 299–320, 2002.
Maze G, Monico C and Rosenthal J. Public Key Cryptography based on semigroup Actions. Adv. Math. Commun, 1, 489–507, 2007.
Atani R E, Atani S E, and Mirzakuchaki S. “Public key cryptography based on semimodules over quotient semirings,” International Mathematical Forum, 2(52), 2561–2570, 2007.
Durcheva M. “Public key cryptosystem based on two sided action of different Exotic semirings,” International Mathe-matical Forum, 2(52), 2561–2570, 2007.
David S, Bernd S. Tropical Mathematics. Mathematics Magazine, 82(3), 163–173, 2004.
Grigoriev D, Shpilrain V. Tropical cryptography, Communications in Algebra, 42(6): 2624–2632, 2014.
Grigoriev D, Shpilrain V. Tropical cryptography II: Extensions by homomorphis-ms. Communications in Algebra, 47(10): 4224–4229, 2019.
Kotov M, Ushakov A. Analysis of a key exchange protocol based on tropical matrix algebra. Journal of Mathematical Cryptology, 12(3): 137–141, 2018.
Rudy D, Monico C. Remarks on a Tropical Key Exchange System. J. Math. Cryptol, 15, 280–283, 2021.
Isaac S, Kahrobaei D. A closer look at the tropical cryptography. International Journal of Computer Mathematics: Computer Systems Theory, 6 (2):137–42, 2021.
Muanalifah A, Sergeev S. On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product. Communications in Algebra 49:1–19, 2021.
Muanalifah A, Sergeev S N. Modifying the Tropical Version of Stickel’s Key Exchange Protocol. Applications of Mathematics, 65(6). 727–753, 2020.
Huang H, Li C. Tropical Cryptography Based on Multiple Exponentiation Problem of Matrices. Security and Communication Networks, 1–9, 2022.
Huang H, Li C and Deng L. Public-Key Cryptography Based on Tropical Circular Matrices. Applied Sciences, 12. 7401, 2022.
Durcheva M. TrES: Tropical Encryption Scheme Based on Double Key Exchange. European Journal of Information Technologies and Computer Science, 10(24018), 2736–5492, 2022.
Golan J S. Semirings and their Applications. Dordrecht: Kluwer Academic Publishers, Chapter 1–18, 1999.
Butkovi¡ C P. Max-linear Systems: Theory and Algorithms. Springer, London, Springer Monographs in Mathematics, Chapter 3, 2010.
Litvinov G L, Rodionov A Y and Sergeev S N. et al. Universal algorithms for solving the matrix Bellman equations over semirings. Soft Comput 17, 1767–1785, 2013.
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Journal of Cyber Security and Mobility
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
