# 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 is a finite group generated by of order , then Alice chooses as her private key any number and publishes as her public key. For security, we assume that the discrete logarithm problem is intractably difficult in ; that is, given and , there is no easy way to find . Messages are converted to elements of the group. If is one such message, Bob sends it to Alice by first creating a random "message key" , and computing

as the ciphertext.

Alice decrypts the ciphertext by computing . This works because

.

For the nim-field, choose a proper subfield of order consisting of all integers less than . Consider the cyclic group and suppose 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 , encoding a message as a group element will be very easy, and decoding a group element to a message likewise. For example, treating as a binary file with length less than , its bits can be interpreted as the base 2 digits of an integer less than .

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

equal one.

As an example, choose so that . 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
```

Now to create private and public keys:

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

Note that although and 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 ?
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.