Cryptanalysis of a Public Key Cryptosystem Based on the Matrix Combinatorial Problem

摘要

In this paper, we present a cryptanalysis of a public key cryptosystem based on the matrix combinatorial problem proposed by Wang and Hu (2010). Using lattice-based methods finding small integer solutions of modular linear equations, we recover the secret key of this cryptosystem for a certain range of parameters. In experiments, for the suggested parameters by Wang and Hu, the secret key can be recovered in seconds.%Straipsnyje pasiūlyta viešojo rakto šifravimo sistema, grįsta matricų kombinatoriniu uždaviniu, kurią nagrinéjo Wang ir kt. Naudojant gardelinius metodus, apskaičiuojami modulinių tiesinių. lygčių mažiausieji sveikieji sprendiniai ir surandamas šios šifravimo sistemos slaptasis raktas. Wang'o ir kt. pasiūlytiems parametrams slaptasis raktas apskaičiuojamas per kelias sekundes.