Breaking the knapsack algorithm involves finding the values k and m such that m*a((i) (mod k) forms a superincreasing set (s(i)), where a(i) is the public set of weights. In the graph y = m*a1(mod k), a(i) is the slope of the function, and discontinuities fall on the values: m = ( (k/a(1)), (2k/a(1)) ... ((a(1)-1)k/a(1))).
m*a(1) (mod k) or y is less than 2(-n+1)*k, where n is the number of weights in the knapsack, because each element in the superincreasing sack must be at least twice the previous. Therefore, m must fall on the interval ((pk/a(1)), (pk/a(1) + (2(-n+1)k/a(1))).
where p equals {1 .. (a(1) -1)}. Dividing the set by k leads to the ratio m/k falling on the interval ((p/a(1)),((p/a(1)) + (1/(a(1)*2(n-1))))
meaning the ratio falls on on of the intervals defined by the discontinuities on the graph y=m*a(1) (mod k).
This procedure works with the second weight a(2), where the ratio m/k can have the values on the interval ((q/a(2)),((q/a(2)) + (1/(a(2)*2(n-2))))
where q = {1...a(2)-1}. Both the first and second intervals must contain m/k, and therefore the possible interval on which m/k may fall is limited to the intersection of the above mentioned.
Increasing the number of weights decreases further the interval, and thus with as few as 4 weights (m,k) may be determined by trial and error.
Sources: Applied Cryptography by Bruce Schneier |
