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

Question

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

log₄₅(201) = 1.39316393

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

我该怎么处理这个事情？

Answer 1

密码学经常使用 素数域，在本例中为 GF(257)。 <一href="http://books.google.com/books?id=_g-fDjmi1xAC&pg=PA60&lpg=PA60&dq=field%2045%20257%20safer%2b&source=bl&ots=pxx5Qxhvx3& ;sig=Js7MaBkdiyeLdCOeMXBcAIsXVUU&hl=en&ei=yyvZTrX5A5TciQL1uPC7Bg&sa=X&oi=book_result&ct=结果&resnum=1&ved=0CBwQ6AEwAA" rel="nofollow">创建一个指数表，如下所示：

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₄₅(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);

使用了我相信.NET 中最初存在的 BitConverter 类。