Protocolos asimétricos con criptografía no conmutativa y matrices elementales

Ernesto Rafael  Carbonell Rigores; Ricardo Araujo Rodríguez

Authors

Ernesto Rafael Carbonell Rigores Technological University of Havana "José Antonio Echeverría"
Ricardo Araujo Rodríguez Independent researcher

Keywords:

Asymmetric cryptography, cryptographic protocol, elementary matrix, Generalized Symmetric Decomposition Problem, non-commutative cryptography

Abstract

This paper presents an implementation of four asymmetric cryptographic protocols: key transport, key exchange, digital signature and ciphering, based on a theoretical proposal made by Juan Pedro Hecht, at the University of Buenos Aires, Argentina. In all of the four cases, non-commutative cryptography is used by means of the algebraic group of Hill matrices. As a one-way function, the Generalized Symmetric Decomposition Problem is used, considered a computationally intractable problem, which requires the application of "brute force" to attack it. These protocols use single-precision arithmetic, which makes them usable on devices with low computational performance. In the original proposal, some matrices are required to be generated “randomly” and to be non-singular. However, the "randomness" of a matrix does not guarantee its non-singularity, so that proposal suggests iterating this process until an invertible matrix is obtained, which implies a high computational cost. In this work, an alternative solution to this problem is proposed, which consists of the "random" generation of elementary matrices, imposing certain conditions that guarantee their non-singularity. The operations applied on elementary matrices require a lower computational effort than when applying them on general matrices and a smaller space than the necessary to store the entries of the general matrices.

References

Araujo Rodríguez, R. (2021). Diseño e implementación de variantes eficientes de protocolos asimétricos compactos mediante el uso de matrices elementales. Tesis de Grado en Ingeniería Informática, Universidad Tecnológica de La Habana "José Antonio Echeverría", Cujae.

Bishop, M. (2003). What is computer security? IEEE Security & Privacy, 1(1), 67-69.

Delgado Vargas, K. A., de Abiego L´Eglisse, A. F., Gallegos-García, G., & Cabarcas, D. (2019). Un acercamiento a la línea del tiempo de los algoritmos criptográficos. Revista Digital Universitaria, Universidad Nacional Autónoma de México, 20(5), 10. doi: http://doi.org/10.22201/codeic.16076079e.2019.v20n5.a7.

Diffie, W., & Hellman, M. (1976). New directions in cryptography. . IEEE Transaction on Information Theory, 22(6), 644-654.

Dixon, J. D. (1981). Asymptotically fast factorization of integers. Mathematics of computation, 36(153), 255-260.

ElGamal, T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4), 469-472.

Gerritzen, L., Goldfeld, D., Kreuzer, M., Rosenberger, G., & Shpilrain, V. (2006). Algebraic Methods in Cryptography: AMS/DMV Joint International Meeting, June 16-19, 2005, Mainz, Germany: International Workshop on Algebraic Methods in Cryptography, November 17-18, 2005, Bochum, Germany (Vol. 10): American Mathematical Soc.

Gil Rosell, B. (2020). CSIDH: criptografía postcuántica basada en isogenias de curvas Elípticas. Tesis de Grado en Matemáticas, Universitat de Barcelona, España.

Golub, G. H., & Van Loan, C. F. (1996a). Matrix Computations: Baltimore, The Johns Hopkins University Press.

Hecht, J. P. (2015). A post-quantum set of compact asymmetric protocols using a general linear group. Actas del VIII Congreso Iberoamericano de Seguridad Informática CIBSI, 15, 96-101.

Hecht, J. P. (2016). Post-Quantum Cryptography: generalized ElGamal cipher over GF(2518). Theoretical and Applied Informatics, 28(4), 14. doi: 10.20904/284001

Hernández Basco, B. E. (2022). Test de primalidad y algoritmos de factorización en criptografía: aspectos matemáticos y computacionales. Tesis de Grado en Ingeniería en Computación y en Licenciatura en Matemáticas, Universidad de La República, Uruguay.

Kallenberg, O. (1975) Random measures. Berlin and London: Akademie-Verlag.

Menezes, A. J., van Oorschot, P. C., Vanstone, S. A., & Rosen, K. (1996). Handbook of Applied Cryptography: CRC Press.

Meyer, C. D. (2000b). Matrix Analysis and Applied Linear Algebra. : Society for Industrial and Applied Mathematics.

Mieres, J. (2009). Ataques informáticos. Debilidades de seguridad comúnmente explotadas. Recuperado http://proton.ucting.udg.mx/tutorial/hackers/hacking.pdf.

Miguel Salgado, A. (2021). Criptografía Postcuántica. Tesis de Grado en Matemáticas, Universidad del País Vasco, España.

Pomerance, C. (1996). A tale of two sieves. Paper presented at the Notices Amer. Math. Soc.

Rambaut Lemus, D. F. (2021). Introducción a la Criptografía post-cuántica basada en teoría de códigos. Tesis de Grado en Matemáticas Aplicadas y Ciencias de la Computación, Universidad del Rosario, Colombia.

Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.

Sevillano Castellano, E. (2018). Leyes de reciprocidad (cuatro demostraciones de la Ley de Reciprocidad Cuadrática).

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring Proceedings 35th annual symposium on foundations of computer science (pp. 124-134): Ieee.

Sicard, A. (1999). Algunos elementos introductorios acerca de la computación cuántica. Memorias VII Encuentro ERM, Universidad de Antioquia, Medelln, 23.

Sun, X. (1996). Aggregations of Elementary Transformations.