THE CRYPTANALYSIS OF A PUBLIC-KEY IMPLEMENTATION OF FINITE-GROUP MAPPINGS

Minghua Qu and Vanstone [2] have proposed a public-key cryptosystem (F GM) which is based on factorizations of a binary vector space (i.e., t ransversal logarithmic signatures of an elementary abelian 2-group). I n this paper a generalized (basis-independent) decryption algorithm is given, which shows that there are many equivalent private keys, and a method of efficiently obtaining such an equivalent private key is giv en. The FGM cryptosystem is thus rendered insecure. Although the FGM c ryptosystem is defined in terms of linear algebra, the attack given he re is essentially group-theoretic in nature. Thus this attack throws d oubt on any cryptosystem which relies on the security of transversal l ogarithmic signatures.