Cryptanalysis of a knapsack cryptosystem
University of New Brunswick
Knapsack cryptosystems are classified as public key cryptosystems. This kind of cryptosystem uses two different keys for the encryption and decryption process. This feature offers strong security for these cryptosystems because the decryption key cannot be derived from the encryption key. Since the Merkle-Hellman knapsack cryptosystem, the first proposed version of knapsack cryptosystems, many knapsack cryptosystems have been suggested. Unfortunately, most knapsack cryptosystems that have been introduced so far are not secure against cryptanalysis attacks. These cryptanalytic attacks find weaknesses in the designs of the knapsack cipher. There are two cryptanalysis systems mentioned in this thesis. These are the Shamir Merkle-Hellman knapsack attack and the Basis Reduction Algorithm (called the LLL algorithm). Accordingly, the main goal of this thesis is to implement Visual Basic programs with these two knapsack cryptanalytic attacks. These Visual Basic programs are for testing many versions of knapsack cryptosystems including a newly invented knapsack system. The result of the testing shows that the knapsack cryptosystems are indeed weak, especially against the Reduced Basis Algorithm. This result does not appear to hold for all cases such as the new knapsack system suggested and the Super-Pascal knapsack cryptosystem.