🚀 go-pugleaf

	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.