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

Question

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

журнал₄₅(201) = 1.39316393

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

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

Answer 1

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

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

Значения «журнала» 45^{эксплуат} % 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;

Например, с этой настройкой журнал₄₅(131) = log[131] = 63 и 45³⁸ = exp[38] = 59.

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

Answer 2

Таким образом, у вас есть значение байта (от 0 до 255), и вы хотите получить базу Log 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%.

Answer 3

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

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

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

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

Answer 4

Это не на самом деле ответ, но часть пользователей, просматривающих этот вопрос, вероятно, будет взаимосвязана при преобразовании 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 initialy.