Как вычислить логарифмы в криптографии? - PullRequest
Новая
       42

Как вычислить логарифмы в криптографии?

0 голосов
/ 02 декабря 2011

Я пытаюсь выполнять нелинейные функции в байтах для реализации SAFER +.Алгоритм требует вычисления логарифма base-45 в байтах, и я не понимаю, как это сделать.

log 45 (201) = 1.39316393

Когда я назначаюэто до байта, значение усекается до 1, и я не могу восстановить точный результат.

Как мне справиться с этим?

Ответы [ 4 ]

4 голосов
/ 02 декабря 2011

В криптографии часто используются простые поля, в данном случае GF (257). Создайте таблицу возведения в степень , которая выглядит следующим образом: 

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

Значения «log»: 45 exp % 257. Вам понадобится арифметическая библиотека произвольной точности с функцией modPow (возведите число в степень, по модулю некоторое значение), чтобы построить это Таблица. Вы можете видеть, что значение для «exp» 128 является особым случаем, поскольку обычно логарифм нуля не определен.

Вычислить логарифм числа, найдя его в столбце «log»; значение в столбце "exp" этой строки является логарифмом.

Вот эскиз инициализации: 

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;

При такой настройке, например, log 45 (131) = log[131] = 63 и 45 38 = exp[38] = 59.

(я никогда не писал C #; я просто догадываюсь из документации BigInteger; вероятно, есть ошибки с типами данных.)

1 голос
/ 02 декабря 2011

Итак, у вас есть значение байта (от 0 до 255), и вы хотите получить базу 45 журналов и сохранить ее в другом байте? Как уже говорили другие, вы потеряете некоторую точность в этом. Тем не менее, вы можете добиться большего успеха, чем просто приведение результата double к byte.

База 45 из 255 составляет приблизительно 1,455675. Вы можете сохранить это в байте с некоторой потерей точности, умножив его на постоянный коэффициент. Какой постоянный фактор? Вы можете использовать 100, что даст вам значение 145, но вы теряете почти половину диапазона байта. Поскольку наибольшее значение, которое вы хотите представить, равно 1.455675, вы можете использовать постоянный множитель 255/log45(255) или около 175,176.

Насколько хорошо это работает? Посмотрим ... 

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

В .NET 4 на моей машине это дает мне максимальную ошибку 2,1419% и среднюю ошибку 1,0501%.

Вы можете уменьшить среднюю ошибку, округлив результат с Math.Pow. То есть: 

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

Это уменьшает среднюю ошибку до 0,9300%, но увеличивает максимальную ошибку до 3,8462%.

0 голосов
/ 01 апреля 2014

На самом деле это не ответ, но часть пользователей, просматривающих этот вопрос, вероятно, будет заинтересована в преобразовании типа double в тип byte[]. Что можно сделать, это просто: 

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

и 

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

здесь используется класс BitConverter, который, как я полагаю, существует в .NET.

0 голосов
/ 02 декабря 2011

Показ кода может помочь, но я подозреваю, что ваша проблема связана с сохранением результата.

Если вы хотите сохранить нецелое число, вы не хотите помещать его в байт, так как этообрезать его (как вы видите).Вместо этого сохраните результат в двойном числе или что-то более подходящее: 

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

Я должен добавить, что я не уверен, что такое SAFER +, поэтому этот ответ может оказаться бесполезным, но, надеюсь, он должен указать вам правильное направление.

...