This is a public key knapsack system which (like all knapsack systems) has been broken. However, it took longer to break than most, and is a very elegant use of finite fields. I like to use it for two things: as a nice example of finite fields in practice for students, and as a test for a computer algebra system. All CAS’s can do calculus and some algebra, but not all of them are equal when it comes to abstract algebra.

Anyway, here is a simplified version of this cryptosystem. (The full version includes a permutation, which I’ve left out as it has nothing to do with the finite field computations).

First, the setup.

- Choose a prime and integer , and create a finite field where is a polynomial of degree which is irreducible over the field . Let be a primitive element in the field.
- For each compute the discrete logarithms .
- Choose a random integer with .
- Compute for all .
- Then your public key is and your private key is .

Messages are binary strings of length with exactly ones. (It is easy to represent numbers in this format.) Encryption is obtained by

.

Note that this is a standard knapsack-style encryption. The difficulty, as with any knapsack, is to determine which of the values were used to create the sum.

For decryption, the following steps are used:

- Compute .
- Compute
- Compute .
- Factor into linear factors
where each . The values of the in the factorization are the positions of the 1’s in the message.

To see that this works, first notice that . Then

.

Replacing with its definition using produces

.

Since exactly of the values are 1, this can be rewritten as

.

Writing the left hand side as a product of powers produces

.

Since by definition we have this last equation can be written as

.

Finally, since both sides of this equation are monic polynomials, and are equal modulo , it follows that

and since the values are either zero or one, we end up with a polynomial which can be factored into the terms we need.

For further discussion, see the Handbook of Applied Cryptography, chapter 8.

In future posts, I’ll show how this cryptosystem can be quickly implemented in Sage, Axiom, and Maxima.