Как вычислить логарифмы в криптографии?
-
27-10-2019 - |
Вопрос
Я пытаюсь выполнять нелинейные функции на байтах, чтобы реализовать SAFER+. Алгоритм требует вычислительного логарифма Base-45 на байтах, и я не понимаю, как это сделать.
журнал45(201) = 1.39316393
Когда я назначаю это байту, значение усекается до 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;
Например, с этой настройкой журнал45(131) = log[131]
= 63 и 4538 = exp[38]
= 59.
(Я никогда не писал C#; я просто угадываю от BigInteger
документация; Скорее всего, будут ошибки с типами данных.)
Другие советы
Таким образом, у вас есть значение байта (от 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%.
Показывая нам, что код может помочь, но я подозреваю, что ваша проблема возникает в хранении результата.
Если вы хотите сохранить неинтемерный номер, вы не хотите помещать его в байт, так как это усеет его (как вы видите). Вместо этого храните результат в двойном или что -то более подходящем:
double result = math.log(154,45);
Я должен добавить, что я не уверен, что такое безопаснее+, поэтому этот ответ может быть не полезным, но, надеюсь, он должен указать вам в правильном направлении.
Это не на самом деле ответ, но часть пользователей, просматривающих этот вопрос, вероятно, будет взаимосвязана при преобразовании 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.