Re: NSA releases newly declassified crypto docs

I remember reading an article in Scientific American where the author
noted that since the knapsack problem was *proven* to be NP-complete,
people shouldn't be relying on such a relatively insecure system as
RSA.

At the time, I thought that was nonsense, since the knapsack
cryptosystem depended on disguising an easy, superincreasing, knapsack
as a difficult one, and there was no proof the disguise wasn't a
weakness.

Of course, soon after, just that weakness *was* used to crack that
cipher. Attempts have been made to improve the disguise, such as
iterated knapsacks, but it hasn't really helped.

John Savard

.