Research On Cryptanalysis Of Cryptosystems Based On Matrix

Advances in quantum computers threaten to break the currently used public key cryptosystems on commutative algebraic structures such as RSA,ECC,and EIGa-mal.This is because of Shor’s quantum algorithms for solving the DLP and integer factoring,the known public-key systems will be insecure when quantum computers become practical.Thus,the public key cryptosystems which have the potential to re-sist quantum computational are widely concerned.Now the public key cryptosystems which have the potential to resist known quantum algorithms attacks are mainly in-clude:lattice-based cryptography,MQ-based cryptography,Hash-based cryptography and Code-based cryptography.Because the matrix calculation is very efficient,this advantage makes it highly efficient in matrix-based cryptosystems.Another advantage of matrix-based cryptosystems is that it has the potential to resist known quantum al-gorithms attacks.Aiming at lattice-based cryptography,MQ-based cryptography and Code-based cryptography,in which we research matrix-based cryptography is a current issue of concern.There is an ongoing search for other platforms where the Diffie-Hellman or similar key exchange could be carried out more efficiently,in particular with public/private keys of smaller size.Kahrobaei et al.presented a brand new key exchange protocol based on extension of a(semi)group by automorphisms and described some practical instances of this general idea.They also proposed a non-commutative semigroup of matrices over a Galois field as platform and matrices over group rings as platform re-spectively.Aiming at the HKKS key agreement protocol over the platform-an extension of a semigroup of matrices over a Galois field,we show that the particular instance of the protocol suggested in their paper can be broken via four different attack methods such as a structural attack,a linearization equations attack,an overdefined systems of multivariate polynomial equations attack and a discrete logarithm method attack and that,they require polynomial time complexity to achieve the shared secret key from associated public-key respectively.In this thesis,we conduct a detailed analysis on the attack methods and showed corresponding algorithmic description and efficien-cy analysis.At the same time,we also present that the HKKS protocol over matrix group rings is vulnerable to a structural attack,a linearization equations attack and an overdefined systems of multivariate polynomial equations attack and that,they also only require polynomial time complexity respectively.Compared with a linear alge-bra attack proposed at ACNS 2014,the structural attack has the same computational complexity while the structural attack gives a polynomial time deterministic algorithm and computational complexity of the linearization equations attack is the smallest.In addition,we provide some improved suggestions on the HKKS protocol.The smart cards and the other examples of public key cryptosystems application can be considered.Among them are the mobile phones for the secret mobile com-munications.It is desirable to avoid the arithmetical operations with large integers in such a computational power restricted devices since they require a special co-processors.Sakalauskas et al.presented an asymmetric cipher avoiding the arithmetical operations with large integers.We show that the scheme is insecure against a linear algebra attack.Using the linear algebra attack,we can obtain the equivalent keys from an associated public key with significant probability in a reasonable time.We then analyze the basic rationale for the linear algebra attack.Finally,we propose an improved scheme that remedies the weakness of Raulynaitis’s scheme.To resist known quantum algorithm attacks,several nonabelian algebraic structures mounted upon the stage of modern cryptography,for example,cryptosystems based on PSD or IEFs.For these type cryptography,we carry on cryptanalysis and proposed several attack methods.Experimental results,corresponding algorithmic description and efficiency analysis show that our methods requires the lowest polynomial complexity O(nω+1)to break those cryptosystems.