The Chor-Rivest cryptosystem

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.

  1. Choose a prime p and integer h, and create a finite field GF(p^h)=mathbb{Z}_p[x]/f(x) where f(x) is a polynomial of degree h which is irreducible over the field mathbb{Z}/pmathbb{Z}.  Let g(x) be a primitive element in the field.
  2. For each iinmathbb{Z}/pmathbb{Z} compute the discrete logarithms a_i=log_{g(x)}(x+i).
  3. Choose a random integer d with 0le dle p^h-2.
  4. Compute c_i=(a_i+d)mod{p^h-1} for all 0le ile p-1.
  5. Then your public key is ([c_0,c_1,ldots,c_{p-1}],p,h) and your private key is [f(x),g(x),d].

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

C=sum_{i=0}^{p-1}m_ic_ipmod{p^h-1}.

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

For decryption, the following steps are used:

  1. Compute r=(C-hd)bmod(p^h-1).
  2. Compute u(x)=g(x)^rpmod{f(x)}
  3. Compute s(x)=u(x)+f(x).
  4. Factor s(x) into linear factors

    s(x)=prod_{j=1}^h(x+t_j)

    where each t_jinmathbb{Z}/pmathbb{Z}. The values of the t_j in the factorization are the positions of the 1’s in the message.

To see that this works, first notice that u(x)=g(x)^{C-hd}pmod{f(x)}. Then

u(x)=g(x)^{(sum_{i=0}^{p-1}m_ic_i)-hd}pmod{f(x)}.

Replacing c_i with its definition using a_i produces

u(x)=g(x)^{(sum_{i=0}^{p-1}m_i(a_i+d))-hd}pmod{f(x)}.

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

u(x)=g(x)^{(sum_{i=0}^{p-1}m_ia_i)}pmod{f(x)}.

Writing the left hand side as a product of powers produces

u(x)=prod_{i=0}^{p-1}[g(x)^{a_i}]^{m_i}pmod{f(x)}.

Since by definition we have g(x)^{a_i}=x+i this last equation can be written as

u(x)=prod_{i=0}^{p-1}(x+i)^{m_i}pmod{f(x)}.

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

s(x)=u(x)+f(x)=prod_{i=0}^{p-1}(x+i)^{m_i}

and since the m_i 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.

Leave a Reply

Your email address will not be published. Required fields are marked *