Comment puis-je calculer des logarithmes en cryptographie?

Question

Je suis en train d'exécuter des fonctions non-linéaires sur les octets à mettre en œuvre SAFER +. L'algorithme de calcul nécessite logarithme en base 45 sur les octets, et je ne comprends pas comment le faire.

log ₄₅ (201) = 1,39316393

Quand j'attribue à un octet, la valeur est tronquée à 1, et je ne peux pas récupérer le résultat exact.

Comment suis-je censé gérer cela?

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

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 3

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 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.