An Elgamal type cryptosystem using the nim-field

Following on from my last post about Conway’s nimbers, here’s how to perform an Elgamal style encryption and decryption. Recall that if G is a finite group generated by g of order n, then Alice chooses as her private key any number A<n and publishes B=g^A as her public key. For security, we assume that the discrete logarithm problem is intractably difficult in G; that is, given g and B, there is no easy way to find A. Messages are converted to elements of the group. If min G is one such message, Bob sends it to Alice by first creating a random "message key" k<n, and computing

C=[C_0,C_1]=[g^k,B^km]

as the ciphertext.

Alice decrypts the ciphertext by computing C_1(C_0^A)^{-1}. This works because

C_0^A=(g^k)^A=(g^A)^k=B^k.

For the nim-field, choose a proper subfield F of order N = 2^{2^n} consisting of all integers less than N. Consider the cyclic group Fbackslash{0} and suppose a is a generator. Then all the above operations carry across. The nice thing here is that as group elements are all non-zero integers less than N, encoding a message m as a group element will be very easy, and decoding a group element to a message likewise. For example, treating m as a binary file with length less than 2^n, its bits can be interpreted as the base 2 digits of an integer less than N.

Finding a generator a can be done by trial and error. We start by noting that as all integers less than 2^{2^{n-1}} form a proper nim-subfield, any generator a of Fbackslash{0} must be at least as great as 2^{2^{n-1}}. Assume that N-1 can be fully factored, and that its prime factors are p_i. Then a is a generator if none of the values

a^{(N-1)/p_i}

equal one.

As an example, choose n=6 so that N=2^{2^6}=18446744073709551616. This is a small number as far as secure cryptosystems go, but will suffice for a demonstration:

sage: load nimbers.py
sage: from nimbers import NimberField
sage: F = NimberField()
sage: n = 6
sage: N = 2^(2^6)
sage: ps = [p for p,e in factor(N-1)]
sage: ps
  [3, 5, 17, 257, 641, 65537, 6700417]

Now to find a generator:

sage: while true:
....:    a = F(randint(2^(2^5),N))
....:    if [a^((N-1)/p) for p in ps].count(1)==0:
....:        print a
....:        break
....:
10797286954115293541

(Your number may differ.)

Now to create private and public keys:

sage: A = randint(1,N);A
  2836502683176700913
sage: B = a^A; B
  18427739260935308684

Note that although A and B look like innocuous integers, appearances can be deceiving:

sage: parent(A)
  &lt;type 'int'&gt;
sage: parent(B)
  NimberField

Now choose a message and encrypt it:

sage: m=10^20
sage: k=randint(1,N);k
  4367144432619252418
sage: C = [a^k,B^k*m]
sage: C
  [12922178036391740664, 212996673669914038023930158560151735676]

Decryption can be done in one line:

sage: C[1]/C[0]^A
  100000000000000000000

It works out, as we’d expect. I don’t know, however, any of the following:

  1. Is this system secure: that is, are discrete logarithms intractable in the nim-field?
  2. Are there fast methods for multiplication and inversion in the nim-field?
  3. Is this system likely to be any more efficient than using the prime field mathbb{Z}_p?
  4. Are there cryptosystems which are particularly suited to using the nim-field?

As far as I know, nobody has investigated the nim-field from the algorithmic, computational or cryptographic viewpoint.

Leave a Reply

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