An Attacking Method for Multiplicative Knapsack Type Public Key Cryptosystem Based on Finite Field

Kaoru KUROSAWA; Toshiya ITOH; Hiroo SHIGETA; Shigeo TSUJII

An Attacking Method for Multiplicative Knapsack Type Public Key Cryptosystem Based on Finite Field

Kaoru KUROSAWA, Toshiya ITOH, Hiroo SHIGETA, Shigeo TSUJII

Full Text Views

13

Share
Cite this

Summary :

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 (p^h) 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.

Publication: IEICE TRANSACTIONS on transactions Vol.E70-E No.1 pp.37-41

Publication Date: 1987/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Information and Communication Theory

Authors

Kaoru KUROSAWA
Toshiya ITOH
Hiroo SHIGETA
Shigeo TSUJII

Keyword

Cite this

Copy

Kaoru KUROSAWA, Toshiya ITOH, Hiroo SHIGETA, Shigeo TSUJII, "An Attacking Method for Multiplicative Knapsack Type Public Key Cryptosystem Based on Finite Field" in IEICE TRANSACTIONS on transactions, vol. E70-E, no. 1, pp. 37-41, January 1987, doi: .
Abstract: 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 (p^h) 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.
URL: https://globals.ieice.org/en_transactions/transactions/10.1587/e70-e_1_37/_p

Copy

@ARTICLE{e70-e_1_37,
author={Kaoru KUROSAWA, Toshiya ITOH, Hiroo SHIGETA, Shigeo TSUJII, },
journal={IEICE TRANSACTIONS on transactions},
title={An Attacking Method for Multiplicative Knapsack Type Public Key Cryptosystem Based on Finite Field},
year={1987},
volume={E70-E},
number={1},
pages={37-41},
abstract={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 (p^h) 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.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - An Attacking Method for Multiplicative Knapsack Type Public Key Cryptosystem Based on Finite Field
T2 - IEICE TRANSACTIONS on transactions
SP - 37
EP - 41
AU - Kaoru KUROSAWA
AU - Toshiya ITOH
AU - Hiroo SHIGETA
AU - Shigeo TSUJII
PY - 1987
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E70-E
IS - 1
JA - IEICE TRANSACTIONS on transactions
Y1 - January 1987
AB - 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 (p^h) 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.
ER -