JISE


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


Journal of Information Science and Engineering, Vol. 8 No. 4, pp. 633-640


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

  Retrieve PDF document (JISE_199204_08.pdf)