Algoritme LLL dan Aplikasinya dalam Pembongkaran Sistemkripto Knapsack Merkle-Hellman

Abstract

LLL algorithm is an algorithm that can be used to determine an approximation of the shortest vector in a lattice. Size reduction algorithm is an important step of LLL algorithm. The LLL algorithm can be applied in many elds. This paper shows how LLL algorithm can be used in breaking one of the famous cryptosystem, namely the Merkle-Hellman knapsack cryptosystem. Merkle-Hellman knapsack cryptosystem is an asymmetric cryptosystem using the subset sum problem as the support of security. Subset sum problem can be transformed into the problem of determining shortest vector in a lattice, so that LLL algorithm can also be used to solve the subset sum problem. Since the subset sum problem can be easily solved by applying LLL algorithm, then the Merkle-Hellman knapsack cryptosystem can also be easily be destructed.