I have been studying papers on various ways to crack the knapsack cryptosystem, unfortunately the mathematics in these papers involves lattices and LLL which is over my head.

The paper "New Attacks for Knapsack Based Cryptosystems" may have a Sage example but I can't view the paper.

http://www.math.ucsd.edu/~crypto/Projects/JenniferBakker/Math187/index.html#Anchor-Cryptographi-62216 has an example but I can't seem to follow it.

I tried writing my own python code based on pseudocode in one paper but it seems to require a loop of 2**256 and neither I nor the atoms in the universe plan on living that long...

I was wondering if anyone could help me with this. Example sage code would be perfect, source code in any language would work as well.


  • $\begingroup$ The title is a literature recommendation but the body of the question is not. Seth, perhaps you could edit the title to better reflect the body? It's a pity the paper is behind a paywall. Edit I edited the title for you. If you feel that I've made a mistake or that the new title doesn't represent the question as you intended, feel free to roll back. $\endgroup$ – rath Apr 10 '14 at 0:10
  • $\begingroup$ Try M = ...; M.LLL(); or M.BKZ() $\endgroup$ – xagawa Apr 10 '14 at 13:31
  • $\begingroup$ That works for me. Anyway, I got my hands on that paper and it has absolutely no sage code in it, despite what the abstract claims. Thank God I didn't blow $50 buying that. I should have known better than to think an academic paper would have any practical value... So I think that link contains exactly the math I need, I just don't know enough about Sage to know how to type it in. $\endgroup$ – Seth Apr 10 '14 at 13:49
  • $\begingroup$ xagawa I didn't see your post when I replied earlier. How do I set up M like in that link I posted? $\endgroup$ – Seth Apr 10 '14 at 15:00
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because this seems to be rather a programming question (How do I implement the given algorithms?) and may be asked at StackOverflow. $\endgroup$ – SEJPM Jun 23 '15 at 19:39