Improving the security of the Knapsack Cryptosystem by using Legendre Symbol

Abstract

In this paper, we present a new cryptosystem based on combining the Knapsack cryptosystem with the Legendre symbol. This combination provides the Knapsack cryptosystem with the feature of using two different super-increasing sequences to generating the keys. The results show that the proposed cryptosystem is secure against the LLL algorithm and Shamir’s attacks because it uses two different public keys instead of only one key as in the standard cryptosystem. Moreover, the comparison of the proposed cryptosystem with the standard cryptosystem confirms that using the Legendre symbol increases the decryption time in the proposed cryptosystem. The higher decryption time with the use of two different private keys increases the required time to break the cryptosystem if any possible attacks might exist that can be applied. Therefore, the proposed cryptosystem is more secure and highly effective.