Abstract: A new key recovery attack against Wang et al.’s cryptosystem which was built using random knapsacks was proposed in this paper.We found out that it is not a real random knapsack public key cryptosystem.Actually,a special super increasing knapsack is unobviously used in their scheme.By substituting the special super increasing knapsack with normal super increasing knapsack and hiding the normal super increasing knapsack into a random knapsack,we proposed an improved knapsack public key cryptosystem based on Chinese reminder theorem.Our scheme revises the shortage of the Wang et al.’s scheme and can resist the lattice basis reduction algorithm attack and low-density attack,as well as Shamir attack.

Key words: Random knapsack,Knapsack public key cryptosystem,Chinese reminder theorem,Lattice basis reduction algorithm