Security of the cryptosystems based on ergodic matrices

Abstract

The security of the public-key cryptosystems based on ergodicmatrices over finite field was analysed.According to the public key,a system of linear equations for the forged secret key bits is obtained by inverse matrix elimination method.It is proved that the computational TEME problem is solvablein polynomial time and the ciphertext of the PZZ1 cryptosystem can be decrypted by the forged secret key.In some case the SEME problem can be reduced to discrete logarithm problem in polynomial time.If the key parameters are chosen improperly,then PZZ2 cryptosystem is based on discrete logarithm problem instead of NP hard problem.

Keywords

• ergodic matrix;public-key cryptography;computational complexity;finite field;algorithm