Megrelishvili protocol is a linear algebraic-based key exchange procedure between two parties. Unlike the well-known Diffie-Hellman protocol or its variants, the security of this protocol does not rely on the generic discrete logarithm problem in a particular group. In this article we investigate Megrelishvili Vector-Matrix Problem (MVMP) as a computational problem that underlies the security of Megrelishvili protocol. We propose two types of collision algorithms which solve MVMP faster than the exhaustive search approach. In particular, we prove that the running time of our algorithms asymptotically outperforms that of the exhaustive search approach in solving the MVMP in Fqn by a factor of (1/n logg) · qn/2. Moreover, we also conducted numerical experiments to test the actual running time of our algorithms. The results from theoretical and experimental analyses show that our algorithms are generally faster than the brute-force approach.
In this paper, we investigate the algebraic properties of the public parameters for Megrelishvili protocol. We provide mathematical formulations for optimal conditions of each parameter. We prove that optimal condition for both parameters is attained whenever the minimal polynomial the public matrix is also a primitive polynomial of degree n, where n is the size of the matrix.
This article presents an investigation of asymptotic time complexities of several algorithms related to Megrelishvili protocol. The analysis are carried out for the private keys computations and public exchange of values, public key constructions, as well as an elementary exhaustive search attack algorithm. We show that the complexities of these algorithms are higher than the complexities of elementary algorithms involved in the conventional Diffie - Hellman protocol (DHP) or its variant on elliptic curves (ECDHP). This condition also implies that Megrelishvili protocol is more secure than DHP and ECDHP against exhaustive search attack.
Transposition cipher is a class of hystorical encryption algorithms that rearrange positions in plaintext based on some fixed permutation which is its secret key. In this research Differential Evolution was used to attack the transposition cipher, which is a permutation of integer problem. Despite the fact that Differential Evolution mostly used for problem with real numbers; this paper shows that Differential Evolution could be used to correctly decrypt ciphertext that has up to permutation length of 9, but started to have half of incorrect answers in 10 simulations done to permutation length of 10.