How do I compute logarithms in cryptography?

Question

I am trying to perform non-linear functions on bytes to implement SAFER+. The algorithm requires computing base-45 logarithm on bytes, and I don't understand how to do it.

log₄₅(201) = 1.39316393

When I assign this to a byte, the value is truncated to 1, and I can't recover the exact result.

How am I supposed to handle this?

Answer 1

Cryptography often uses prime fields, in this case, GF(257). Create an exponentiation table that looks like this:

exp | log
----+----
  0 |   1
  1 |  45
  2 | 226
  3 | 147
... | ...
128 |   0
... | ...
255 |  40
---------

The "log" values are 45^exp % 257. You'll need an arbitrary precision arithmetic library with a modPow function (raise a number to a power, modulo some value) to build this table. You can see that the value for "exp" 128 is a special case, since normally the logarithm of zero is undefined.

Compute the logarithm of a number by finding the it in the "log" column; the value in the "exp" column of that row is the logarithm.

Here's a sketch of the initialization:

BigInteger V45 = new BigInteger(45);
BigInteger V257 = new BigInteger(257);
byte[] exp = new byte[256];
for (int idx = 0; idx < 256; ++idx)
  exp[idx] = BigInteger.ModPow(V45, new BigInteger(idx), V257) % 256;
byte[] log = new byte[256];
for (int idx = 0; idx < 256; ++idx)
  log[exp[idx]] = idx;

With this setup, for example, log₄₅(131) = log[131] = 63, and 45³⁸ = exp[38] = 59.

(I've never written C#; I'm just guessing from the BigInteger documentation; there are likely to be errors with the data types.)

Answer 2

Showing us the code might help but I suspect your problem comes from storing the result.

If you want to store a non-integer number you don't want to put it into a byte since that will truncate it (as you are seeing). Instead store the result in a double or something more appropriate:

double result = math.log(154,45);

I should add that I'm not sure what SAFER+ is so this answer may not be helpful but hopefully it should point you in the right direction.

Answer 3

So you have a byte value (from 0 to 255), and you want to get the log base 45, and store it in another byte? As others have said, you're going to lose some accuracy in doing that. However, you can do better than just casting the double result to a byte.

The log base 45 of 255 is approximately 1.455675. You can store that in a byte, with some loss of accuracy, by multiplying it by a constant factor. What constant factor? You could use 100, which would give you a value of 145, but you're losing almost half the range of a byte. Since the largest value you want to represent is 1.455675, you can use a constant multiplier of 255/log45(255), or about 175.176.

How well does this work? Let's see ...

        var mult = 255.0 / Math.Log(255, 45);
        Console.WriteLine("Scaling factor is {0}", mult);
        double errMax = double.MinValue;
        double errMin = double.MaxValue;
        double errTot = 0;
        for (int i = 1; i < 256; ++i)
        {
            // Get the log of the number you want
            var l = Math.Log(i, 45);

            // Convert to byte
            var b = (byte)(l * mult);

            // Now go back the other way.
            var a = Math.Pow(45, (double)b / mult);

            var err = (double)(i - a) / i;
            errTot += err;
            errMax = Math.Max(errMax, err);
            errMin = Math.Min(errMin, err);
            Console.WriteLine("{0,3:N0}, {1,3:N0}, {2}, {3:P4}", i, b, a, err);
        }
        Console.WriteLine("max error = {0:P4}", errMax);
        Console.WriteLine("min error = {0:P4}", errMin);
        Console.WriteLine("avg error = {0:P4}", errTot / 255);

Under .NET 4 on my machine, that gives me a maximum error of 2.1419%, and an average error of 1.0501%.

You can reduce the average error by rounding the result from Math.Pow. That is:

var a = Math.Round(Math.Pow(45, (double)b / mult));

That reduces the average error to 0.9300%, but increases the maximum error to 3.8462%.

Answer 4

This is not really an answer, but a fraction of the users viewing this question will probably be interrested in the conversion of a double type to a byte[] type. What could be done is simply:

double theDouble = 78.24435;
byte[] theResult = BitConverter.GetBytes(theDouble);

and

byte[] theByteArray = new byte[]{0, 4, 2, 3}; //for example
double theCorrespondingDouble = BitConverter.ToDouble(theByteArray);

this uses the BitConverter class which I believe exists in .NET initialy.