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
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
(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 and look like innocuous integers, appearances can be deceiving:
sage: parent(A) <type 'int'> 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/C^A 100000000000000000000
It works out, as we’d expect. I don’t know, however, any of the following:
- Is this system secure: that is, are discrete logarithms intractable in the nim-field?
- Are there fast methods for multiplication and inversion in the nim-field?
- Is this system likely to be any more efficient than using the prime field ?
- 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.