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 .
- 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.
In future posts, I’ll show how this cryptosystem can be quickly implemented in Sage, Axiom, and Maxima.