In 1989, Cooper et al. proposed a new knapsack public-key cryptosystem based on the structure of a Pascal triangle called a "Super-Pascal triangle". The main difference between this new structure and most of the knapsack sequences is that the Super-Pascal triangle is two-dimensional and has very high density while most of the knapsack sequences are one-dimensional and have low density. In this paper, we will show that there exist many superincreasing sequences in the structures of the Pascal triangle and Super-Pascal triangle. Since the public keys in the system are transformed by the Super-Pascal triangle based on the modular multiplications, Shamir's attack on the basic Merkle-Hellman knapsack can be used to find the transformed keys and, thus, break this system.

Keywords: cryptanalysis, public key cryptosystems, knapsack problems and pascal triangle

Received June 19, 1992; revised February 12, 1993.
Communicated by Jun S. Huang.
^*This work was supported by the National Science Council, Republic of China, under Contract NSC80-0404-E006-12.