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.
Merkle Hellman knapsack cryptosystem
The Merkle/Hellman knapsack cryptosystem is an asymetric cryptosystem.
Examples of knapsack :
An easy one :
a = [37, 98, 23, 29 ]
t = 127
with this example it's easy to see that x = [0, 1, 0, 1 ]
because 98 + 29 = 127
A more complicated one :
a = [964266105338945, 6749864515101946, 964264861986975, 13499727318176232, 17356789956975810,3857053002628327, 12535438500695219, 10606879723866753, 10606828405887831, 16392324024362666, 13499318722439347, 7713307812454905, 6748217527825207, 6746569486347068, 8671806553725916, 2879615947706164, 18294696345811439, 6697131932913639, 15322796985338016, 753333165640954, 16934930158297044, 10727464396496856, 8919464717468072, 12053330796850461]
t = 85665597416613316
With a such knapsack, it's more complicated to guess the solution. You have to use a computer!
The first idea to break this knapsack is to try all the combinations until the sum is equal to 85665597416613316. If you do a naive brute force algorithm, you will make about 2^24 computations ( easy with a personal computer ). You can also speed up the computation using "dynamic programming".
Fortunately, the knapsack problem can be modelized using lattices!
LLL algorithm / Lattices
The knapsack problem can be solved using the LLL algorithm, consider a knapsack problem :
For our previous easy example , the lattice modeling this problem is this one :
By construction , v is a short vector of L, thus we can hope to find it using LLL algorithm ( see Shortest Vector Problem and Closest Vector Problem of the LLL book for more information ).
libLLL implements the LLL algorithm, so we can find this shortest vector! It's not an easy task to find a not buggy pseudocode LLL algorithm on Internet.
The pseucode used for the implementation :
Break a = [37, 98, 23, 29] , t = 127 :
Thus the solution is [0, 1, 0, 1], let's try with the more complicated example :) :
Break the complicated example :
a = [964266105338945, 6749864515101946, 964264861986975, 13499727318176232, 17356789956975810,3857053002628327, 12535438500695219, 10606879723866753, 10606828405887831, 16392324024362666, 13499318722439347, 7713307812454905, 6748217527825207, 6746569486347068, 8671806553725916, 2879615947706164, 18294696345811439, 6697131932913639, 15322796985338016, 753333165640954, 16934930158297044, 10727464396496856, 8919464717468072, 12053330796850461]
t = 85665597416613316
Thus the solution is [0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0] :) !
Easy for santa claus and his helpers
The parameters of the challenge :
a = [964266105338945, 6749864515101946, 964264861986975, 13499727318176232, 17356789956975810, 3857053002628327, 12535438500695219, 10606879723866753, 10606828405887831, 16392324024362666, 13499318722439347, 7713307812454905, 6748217527825207, 6746569486347068, 8671806553725916, 2879615947706164, 18294696345811439, 6697131932913639, 15322796985338016, 753333165640954, 16934930158297044, 10727464396496856, 8919464717468072, 12053330796850461]
t[] = [85665597416613316, 68924182376697138, 93855260302436631, 67069112787809230, 67823425594155918, 96038092151406072, 88581012026674643, 87131275443855194, 92447984720405935, 78684146336120268, 52303820625741832, 85294112192719803, 48802767159478973, 93706609509995531, 143147771785836836, 79544023096864593, 118984178180084169, 66881447736363380, 83048004789685724]
So to uncipher the ciphertext we just have to break the knapsack problem for each t[i]. Doing that we can obtain the binary of the plaintext !
Conclusion
Now you can easily break knapsack problem and reduce lattices in python using libLLL ! I do not guarantee that there is no bug in the LLL algorithm but this one "seems" to work, if you find bugs/problems you can send me emails at kutioo [.at.] gmail [.dot.] com. libLLL is GPL v3, so you can be part of the project. The repository is here : libLLL. All the examples in this article are available on the git repository ! I'm beginner in python, thus if you find "optimizations" to speed up the reduction algorithm don't hesitate !
greetz : Mirak and PEV
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.
Merkle Hellman knapsack cryptosystem
The Merkle/Hellman knapsack cryptosystem is an asymetric cryptosystem.
Examples of knapsack :An easy one :
a = [37, 98, 23, 29 ]
t = 127
with this example it's easy to see that x = [0, 1, 0, 1 ]
because 98 + 29 = 127
A more complicated one :
a = [964266105338945, 6749864515101946, 964264861986975, 13499727318176232, 17356789956975810,3857053002628327, 12535438500695219, 10606879723866753, 10606828405887831, 16392324024362666, 13499318722439347, 7713307812454905, 6748217527825207, 6746569486347068, 8671806553725916, 2879615947706164, 18294696345811439, 6697131932913639, 15322796985338016, 753333165640954, 16934930158297044, 10727464396496856, 8919464717468072, 12053330796850461]
t = 85665597416613316
With a such knapsack, it's more complicated to guess the solution. You have to use a computer!
The first idea to break this knapsack is to try all the combinations until the sum is equal to 85665597416613316. If you do a naive brute force algorithm, you will make about 2^24 computations ( easy with a personal computer ). You can also speed up the computation using "dynamic programming".
Fortunately, the knapsack problem can be modelized using lattices!
LLL algorithm / Lattices
The knapsack problem can be solved using the LLL algorithm, consider a knapsack problem :
libLLL implements the LLL algorithm, so we can find this shortest vector! It's not an easy task to find a not buggy pseudocode LLL algorithm on Internet.
The pseucode used for the implementation :
Break a = [37, 98, 23, 29] , t = 127 :
Thus the solution is [0, 1, 0, 1], let's try with the more complicated example :) :
Break the complicated example :
a = [964266105338945, 6749864515101946, 964264861986975, 13499727318176232, 17356789956975810,3857053002628327, 12535438500695219, 10606879723866753, 10606828405887831, 16392324024362666, 13499318722439347, 7713307812454905, 6748217527825207, 6746569486347068, 8671806553725916, 2879615947706164, 18294696345811439, 6697131932913639, 15322796985338016, 753333165640954, 16934930158297044, 10727464396496856, 8919464717468072, 12053330796850461]
t = 85665597416613316
Thus the solution is [0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0] :) !
Easy for santa claus and his helpers
The parameters of the challenge :
a = [964266105338945, 6749864515101946, 964264861986975, 13499727318176232, 17356789956975810, 3857053002628327, 12535438500695219, 10606879723866753, 10606828405887831, 16392324024362666, 13499318722439347, 7713307812454905, 6748217527825207, 6746569486347068, 8671806553725916, 2879615947706164, 18294696345811439, 6697131932913639, 15322796985338016, 753333165640954, 16934930158297044, 10727464396496856, 8919464717468072, 12053330796850461]
t[] = [85665597416613316, 68924182376697138, 93855260302436631, 67069112787809230, 67823425594155918, 96038092151406072, 88581012026674643, 87131275443855194, 92447984720405935, 78684146336120268, 52303820625741832, 85294112192719803, 48802767159478973, 93706609509995531, 143147771785836836, 79544023096864593, 118984178180084169, 66881447736363380, 83048004789685724]
So to uncipher the ciphertext we just have to break the knapsack problem for each t[i]. Doing that we can obtain the binary of the plaintext !
Conclusion
Now you can easily break knapsack problem and reduce lattices in python using libLLL ! I do not guarantee that there is no bug in the LLL algorithm but this one "seems" to work, if you find bugs/problems you can send me emails at kutioo [.at.] gmail [.dot.] com. libLLL is GPL v3, so you can be part of the project. The repository is here : libLLL. All the examples in this article are available on the git repository ! I'm beginner in python, thus if you find "optimizations" to speed up the reduction algorithm don't hesitate !
greetz : Mirak and PEV
thank you boy
RépondreSupprimerthank you boy
RépondreSupprimer