¿Cómo calculo los logaritmos en la criptografía?

Question

Estoy tratando de realizar funciones no lineales en bytes para implementar Safer+. El algoritmo requiere calcular el logaritmo base-45 en bytes, y no entiendo cómo hacerlo.

Iniciar sesión₄₅(201) = 1.39316393

Cuando asigno esto a un byte, el valor se trunca a 1, y no puedo recuperar el resultado exacto.

¿Cómo se supone que debo manejar esto?

Answer 1

La criptografía a menudo usa Prime Fields, En este caso, GF (257). Crear una tabla de exponenciación Eso se ve así:

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

Los valores de "registro" son 45^Exp % 257. Necesitará una biblioteca aritmética de precisión arbitraria con un modPow función (eleva un número a una potencia, modulo algún valor) para construir esta tabla. Puede ver que el valor para "EXP" 128 es un caso especial, ya que normalmente el logaritmo de cero está indefinido.

Calcule el logaritmo de un número encontrando el TI en la columna "Log"; El valor en la columna "Exp" de esa fila es el logaritmo.

Aquí hay un boceto de la inicialización:

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;

Con esta configuración, por ejemplo, registro₄₅(131) = log[131] = 63 y 45³⁸ = exp[38] = 59.

(Nunca he escrito C#; solo supongo que el BigInteger documentación; Es probable que haya errores con los tipos de datos).

Answer 2

Entonces, ¿tiene un valor de byte (de 0 a 255), y desea obtener la base de registro 45 y almacenarlo en otro byte? Como otros han dicho, vas a perder algo de precisión al hacer eso. Sin embargo, tu pueden haz mejor que solo lanzar el double resultar en un byte.

La base de registro 45 de 255 es aproximadamente 1.455675. Puede almacenarlo en un byte, con cierta pérdida de precisión, multiplicándolo por un factor constante. ¿Qué factor constante? Podrías usar 100, lo que te daría un valor de 145, pero estás perdiendo casi la mitad del rango de un byte. Dado que el valor más grande que desea representar es 1.455675, puede usar un multiplicador constante de 255/log45(255), o alrededor de 175.176.

¿Qué tan bien funciona? Vamos a ver ...

        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);

Bajo .NET 4 en mi máquina, eso me da un error máximo de 2.1419%y un error promedio de 1.0501%.

Puede reducir el error promedio redondeando el resultado de Math.Pow. Eso es:

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

Eso reduce el error promedio a 0.9300%, pero aumenta el error máximo a 3.8462%.

Answer 3

Mostrarnos el código podría ayudar, pero sospecho que su problema proviene de almacenar el resultado.

Si desea almacenar un número no inteligente, no desea ponerlo en un byte, ya que eso lo truncará (como está viendo). En su lugar, almacene el resultado en un doble o algo más apropiado:

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

Debo agregar que no estoy seguro de qué es más seguro+, por lo que esta respuesta puede no ser útil, pero espero que deba señalarlo en la dirección correcta.

Answer 4

Esta no es realmente una respuesta, pero una fracción de los usuarios que vean esta pregunta probablemente se inyectará en la conversión de un double Escriba a un byte[] escribe. Lo que se podría hacer es simplemente:

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

y

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

esto usa el BitConverter clase que creo que existe en .NET inicialmente.