Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!umnd-cs!umn-cs!tjacob
From: tjacob@umn-cs.UUCP
Newsgroups: sci.crypt
Subject: Re: Published Key/Knappsack Encryption
Message-ID: <1661@umn-cs.UUCP>
Date: Wed, 17-Jun-87 15:53:50 EDT
Article-I.D.: umn-cs.1661
Posted: Wed Jun 17 15:53:50 1987
Date-Received: Fri, 19-Jun-87 05:39:23 EDT
References: <1241@crash.CTS.COM>
Distribution: na
Organization: University of Minnesota, Minneapolis
Lines: 14
Summary: Re: Knapsack and its breaking


	The knapsack problem is based on finding a unique pattern
of weights that equals the total. Therefore, the decoding key must
be very simple to apply. The first, and most common, key is a super-
increasing sum, that is, each new element in the key is greater than
the sum of all the previous elements. Very trivial to solve. Anyways,
Ernest Brickell, working at Sandia Nat'l Labs, proved that every knapsack
problem is breakable in finite, REALISTIC, time. ie. you're not going
to spend 10 years cracking the key as that's where the security really
lies anyway. ( Who's going to worry about using a breakable key if it's
going to take the guy 10 billion years to break it ?? Not me.. ) If you
want the references, I can go look them up sometime as Brickell's  no
longer at Sandia. ( Other keys looked at are multiplicative and matrix
based - still not much more secure then the increasing sum one. )