c# - 如何计算密码学中的对数？

Question

我正在尝试对字节执行非线性函数以实现 SAFER+。该算法需要计算以字节为底的 45 对数，我不明白该怎么做。

日志₄₅ (201) = 1.39316393

当我将它分配给一个字节时，该值被截断为 1，我无法恢复确切的结果。

我该怎么处理这个？

Answer 1

密码学经常使用素数域，在本例中为 GF(257)。创建一个如下所示的幂表：

经验 | 日志
----+----
  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 ₄₅ (131) = log[131]= 63 和 45 ³⁸ = exp[38]= 59。

（我从未编写过 C#；我只是从BigInteger文档中猜测；数据类型可能存在错误。）

Answer 2

所以你有一个字节值（从 0 到 255），你想获取日志基数 45，并将其存储在另一个字节中？正如其他人所说，这样做会失去一些准确性。但是，您可以做得更好，而不仅仅是将double结果转换为byte.

255 的以 45 为底的对数约为 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);

我应该补充一点，我不确定 SAFER+ 是什么，所以这个答案可能没有帮助，但希望它能为您指明正确的方向。

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 中的类。