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: <1666@umn-cs.UUCP> Date: Fri, 19-Jun-87 14:51:09 EDT Article-I.D.: umn-cs.1666 Posted: Fri Jun 19 14:51:09 1987 Date-Received: Sat, 20-Jun-87 10:07:01 EDT References: <1241@crash.CTS.COM> <1661@umn-cs.UUCP> <1253@crash.CTS.COM> Distribution: na Organization: University of Minnesota, Minneapolis Lines: 57 Summary: How knapsack works 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.