Previous [1] [2] [3] [4] [5] [6] [7] 8

Journal of Inforamtion Science and Engineering, Vol.8 No.4, pp.633-640 (December 1992)
Cryptanalysis of Public-Key Cryptosystem
Using the Pascal Triangle*

Chi Sung Laih
Department of Electrical Engineering
National Cheng Kung University
Tainan, Taiwan, Republic of China

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.