1-1hit |
Kaoru KUROSAWA Toshiya ITOH Hiroo SHIGETA Shigeo TSUJII
In 1978, Merkle and Hellman published two kinds of knapsack type public key cryptosystems, one of which was super-increasing type and the other was multiplicative type. However, the former was broken by Shamir in 1982 and latter was broken by Odlyzko in 1984. Recently, Chor and Rivest proposed a new multiplicative knapsack type cryptosystem based on arithmetic in GF (ph) which cannot be broken by the Odlyzko attack. This paper shows the new cryptosystem is broken if the public knapsack vector has three elements whose values are close to one another or if the primitive polynomial is known. We also present that not only the original secret-key also many other ones can decipher the cryptosystem.