Cryptanalysis of a public key system based on Diophantine equations

C.H. Lin, C.C. Chang and R.C.T. Lee proposed a new public key cipher system whose security was intended to rest on the fact that solving certain kinds of Diophantine equations is difficult. We show that their cipher system can be broken in polynomial time without solving any Diophantine equations. Our method readily gives an explicit bound on the number of bit operations needed to recover any message from its corresponding ciphertext. The cryptanalysis is carried out by solving certain linear congruences derived from the ciphertext and the public key.