jkimble@crash.UUCP (06/17/87)
I've been doing some research for another paper on encryption. Anyway,
while reading up on various "published key" methods, I came across a
few articles about "Knappsack Encryption." The article state
the program is of the published key nature, but was found to be a little
too easy to crack.
I've hacked a program that has been able to work out a few of the
keys through a brutal front-line attack, but obviously would not be
very effective in the real dog-eat-dog, live on the razor's edge world
of encryption.
Has anyone ever used or seen this method of encryption? Is it still around?
Was it good? Was it really as easy as the magazine made it sound?
----ALSO:
I've finally returned from vacation and typed that bibliography of
encryption sources and references. As soon as I can, I will upload it
here and distribute it.
--Jim Kimble
San Diego State University
Varsity Football, Wide Receiver
"I've always wanted to work in a delicatessen just so some woman would
come up to me and ask for a little tongue."
UUCP: {akgua, hplabs!hp-sdd, sdcsvax, nosc}!crash!jkimble
ARPA: crash!jkimble@nosc
INET: jkimble@crash.CTS.COMtjacob@umn-cs.UUCP (06/17/87)
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. )
jkimble@crash.CTS.COM (Jim Kimble) (06/19/87)
From reading a few short articles (and then reading a few long articles :-),
that it took nothing more then using the special set of numers:
1,2,3,6,12,24,48...
Not those numbers, but the idea of adding the previous numbers up to
determine the key.
and all this time I thought *I* was doing something wrong.
Now to see if my prof doesn't know how it works :-)
--Jim Kimble
"If Gary Hart really is guilty of sexual misconduct, then he *should*
drop out of the presidential race -- and get into TV evangelism where
he belongs."
UUCP: {akgua, hplabs!hp-sdd, sdcsvax, nosc}!crash!jkimble
ARPA: crash!jkimble@nosc
INET: jkimble@crash.CTS.COMtjacob@umn-cs.UUCP (06/19/87)
The knapsack public-key encryption works as follows: The receiver of the secret message picks a decryption key. This is usually an increasing sum ( ie. each element is greater then the sum of all the previous elements ) Take as an example the key ( 1, 2, 4, 8, 16 ). The receiver must also pick a modulus N, and a number P such that N and P are relatively prime and have no common factors. The secrect key is know hidden by multiplying each element by P and taking the result modulus N. For a simple example, let P = 10 and N = 100. Therefore, after one iteration, the key looks like ( 1 * 10 mod 100, 2 * 10 mod 100, ... ) = ( 10, 20, 40, 80, 60 ). As you can see, this is nolonger an increasing sum. If this is repeated several times with realistic numbers ( ie. > 120 digits, prime, etc. ) it was thought to hide the decoding key. To send a message, the sender breaks up the text into blocks of M bits, where M is the number of elements in the key. In our case, M = 5. For each bit in the block that is a '1', the corresponding element in the key is added to a sum. This sum mod N is now the encoded message to be sent. To see how this works, take the letters A..Z and give them values of 0-25. ( ie. A = 0, B = 1, ... ). To encode 'HI', take H = 00111 and encode it as 0 * 10 + 0 * 20 + 1 * 40 + 1 * 80 + 1 * 60 = 180 mod 100 = 80 and as I = 01000 = 0 * 10 + 1 * 20 + 0 * 40 + 0 * 80 + 0 * 60 = 20 mod 100 = 20. We therefore transmit 80 20 to the receiver. To decode the message, we use the property of inversion. This means that there is an inverse P' for our secret P such that P * P' mod N = 1. ( See the Euclidean Algorithm for how to do this. ) What this allows us to do, is take the received value ( 80 and 20 ), multiply by P' and take the result mod N as many times as we did to hide the secret key. When we are finished, we have a result that can quickly be decoded with the secret key. To decode, we simply compare each element in the key, starting at the highest or last element. If that element is less than the sum we're comparing to, it must be part of the sum as all the other elements combined can't add up to this element. ( Remember, that's how we defined our sequence in the first place. ) We now how the bits of the original message and can reassemble them back to their character representations. Not to be one that likes raining on parties, I should mention again that the knapsack system is easily broken. If you want to use a secure system, you should look into the RSA ( Rivest-Shamir-Adleman ) which uses exponentation to do th encoding. Hope this poor explanation helps explain how the knapsack system works. - Joseph Thomas ( using Tom's login ) - jpt@uc.msc.umn.edu -or- jpt@umn-rei-uc.arpa or reply to this account via uucp.