mercredi 28 décembre 2011

libLLL

Hello world!

For my first post, I want to share a small library that I developed during my spare time : libLLL !

The first idea of this library was initially to solve the knapsack problem of the SecurIMAG's challenge 5 ( Easy for Santa Claus and his helpers by Mirak ). I didn't find an implementation in Python of the LLL algorithm ( Arjen Lenstra, Hendrik Lenstra and László Lovász ). Usually I use PARI/GP and the "qflll" function to reduce my lattices, but this time I wanted to integrate the lattice reduction in my Python scripts to automate the whole.

I'm not a pure mathematician, so I will not go into the theory to explain in detail what is formally a lattice and to prove the LLL algorithm. In this post I just propose an implementation of the LLL algorithm in Python and explain how to use it to break the Merkle Hellman cryptosystem. If you are interested by the theory I encourage you to buy the book "The LLL Algorithm : Survey and Applications" by Phong Q.Nguyen and Brigitte Vallée.


In one hand I will explain the Merkle Hellman knapsack cryptosystem, in second hand I will explain how to use liblll to break the Merkle Hellman knapsack cryptosystem and finally I will show how to use libLLL to break the "Easy for Santa Claus and his helpers" challenge.