On the Security of the Improved Knapsack Cryptosystem

Hatsukazu TANAKA

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A    No.10    pp.2184-2185
Publication Date: 1998/10/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Information Theory and Its Applications)
Category: Coded Modulation/Security
public-key cryptosystem,  knapsack problem,  choice of encryption keys,  continued fraction,  LLL algorithm,  

Full Text: PDF(153.4KB)>>
Buy this Article

We discuss the security of the improved knapsack cryptosystem that Kobayashi and Kimura have proposed. Two attacking methods for their cryptosystem are proposed; one is the method for obtaining secret keys from public keys by using the continued fraction, and the other is for decrypting the ciphertext without knowing secret keys. We show that their cryptosystem is not secure against these attacks.