Knapsack / subset-sum solver (Merkle-Hellman break)

Subset-sum is NP-hard, and that is exactly why somebody built a public-key cryptosystem on it. Merkle-Hellman, 1978, was the first published alternative to RSA. It was broken by Shamir in 1982 and comprehensively by lattice reduction shortly after, and it is now a CTF fixture rather than a cipher - which is a good thing to be, because it is the cleanest introduction to LLL there is.

The trapdoor, and why it leaks

Start with a superincreasing sequence: each weight larger than the sum of everything before it, say 2, 5, 11, 23, 47. Subset-sum on that is trivial - walk down from the top and take every weight that still fits, because if it fits it must be in, there being not enough smaller weights to cover it. That is the private key.

To get a public key, scramble it: pick a modulus m larger than the total and a multiplier w coprime to it, and publish b_i = w * a_i mod m. The sequence no longer looks superincreasing, so nobody can solve it greedily - but the key holder multiplies a ciphertext by w inverse mod m and is back on the easy sequence. Encryption is one bit per weight: add up the public weights where the message bit is 1.

Density is the number that decides everything

For n weights whose largest is under 2^k, the density is d = n/k. It measures how crowded the instance is: at low density there is essentially one subset that hits the target, at high density there are many. Lagarias and Odlyzko showed in 1985 that d < 0.6463 instances fall to a single LLL reduction; Coster, Joux, LaMacchia, Odlyzko, Schnorr and Stern pushed that to d < 0.9408 in 1992 by centring the lattice. A real Merkle-Hellman key has density near 0.5, because the modulus has to exceed the sum of a superincreasing sequence and so is about twice as many bits as there are weights. The cryptosystem's own parameter requirements put it inside the attack.

How the lattice does it

Build a basis whose rows are an identity block alongside a column holding N*b_i, and add a final row carrying -N*s. Any integer combination corresponds to a choice of coefficients; if those coefficients are a valid solution, the weighted column cancels to zero and what is left is a vector of 0s and 1s - short. Anything that fails the sum constraint pays N in that column, so as long as N exceeds the length of the solution vector, the solution is the shortest thing in the lattice. LLL finds short vectors. That is the whole attack.

The CJLOSS refinement is one line of difference: put a 1 in every identity column of the last row, so the solution vector reads (2x_i - 1) and its entries are +-1 rather than 0/1. Its norm is then sqrt(n) regardless of how many bits are set, instead of growing with the weight of the message. Half the norm is what buys the jump from 0.6463 to 0.9408.

What to try, in order

• Check for superincreasing first. Plenty of challenges hand over the private sequence directly, or a public key whose scrambling was accidentally the identity. Greedy solves it instantly and the answer is provably unique.
• Look at the density. Under 0.9408, the lattice should work; the solver reports the number next to the weights so you know which outcome to expect before you run it.
• If you have m and w, use them. Mapping the target through w inverse mod m and solving the easy sequence is exact and instant - no reduction, no luck.
• Small instances need no theory at all. Under about thirty weights, meet-in-the-middle enumerates 2^(n/2) half-sums and finds the answer whatever the density is.

One thing this solver will not do is return an answer it has not checked. Every candidate coming out of the lattice is re-summed against the target before it is shown, so a decoded vector that does not actually solve the instance is discarded rather than reported. The failure mode here is "no answer", never a wrong one.