c# - BigInteger 中的 .NET 错误？

Question

这个问题在这里已经有了答案:





C# BigInteger.ModPow bug?

(1 个回答)


去年关闭。




我一直在研究一个需要 BigIntegers 的 .NET 项目，我注意到框架的实现提供了似乎不正确的结果。经过数小时试图找出我做错了什么，我决定用 Java 和 C++(使用 OpenSSL)测试我的算法，并且在这两种语言中我都得到了预期的结果。

现在我很自然地想知道我做错了什么(因为地球上没有办法，这是一个以前没有注意到的错误)，我希望有人能帮助我!

这是简化的 C# 代码:

using System;
using System.Numerics;
using System.Globalization;

public class Program
{
    public static void Main()
    {
        var B = BigInteger.Parse("023B61801145A9CB06ADF77493042D166E793B946D1B07B46070E3986A6F036BE", NumberStyles.AllowHexSpecifier);
        var k = BigInteger.Parse("3", NumberStyles.AllowHexSpecifier);
        var x = BigInteger.Parse("09F015DB40A59403E42FBD568AF5774A0A0488A62", NumberStyles.AllowHexSpecifier);
        var g = BigInteger.Parse("7", NumberStyles.AllowHexSpecifier);
        var N = BigInteger.Parse("0894B645E89E1535BBDAD5B8B290650530801B18EBFBF5E8FAB3C82872A3E9BB7", NumberStyles.AllowHexSpecifier);
        var u = BigInteger.Parse("0AC06F615645BEA9B3D6D887C30D28D71B079B598", NumberStyles.AllowHexSpecifier);
        var a = BigInteger.Parse("0D4515CA7747787F1DDA9962ACE81E8412D9D20D06251696ACD74735F1F3B9875", NumberStyles.AllowHexSpecifier);

        var S = calc(B, k, x, g, N, u, a);
        Console.WriteLine(S.ToString("X"));
    }

    static BigInteger calc(BigInteger B, BigInteger k, BigInteger x, BigInteger g, BigInteger N, BigInteger u, BigInteger a)
    {
        var val = B - k * BigInteger.ModPow(g, x, N);
        var exponent = a + u * x;
        return BigInteger.ModPow(val, exponent, N);
    }
}

你可以在这里执行: https://dotnetfiddle.net/qXXiBk

Java中的相同代码:

import java.math.BigInteger;

public class Main
{
  public static void main(String[] args)
  {
    BigInteger B = new BigInteger("023B61801145A9CB06ADF77493042D166E793B946D1B07B46070E3986A6F036BE", 16);
    BigInteger k = new BigInteger("3", 16);
    BigInteger x = new BigInteger("09F015DB40A59403E42FBD568AF5774A0A0488A62", 16);
    BigInteger g = new BigInteger("7", 16);
    BigInteger N = new BigInteger("0894B645E89E1535BBDAD5B8B290650530801B18EBFBF5E8FAB3C82872A3E9BB7", 16);
    BigInteger u = new BigInteger("0AC06F615645BEA9B3D6D887C30D28D71B079B598", 16);
    BigInteger a = new BigInteger("0D4515CA7747787F1DDA9962ACE81E8412D9D20D06251696ACD74735F1F3B9875", 16);

    BigInteger S = calc(B, k, x, g, N, u, a);
    System.out.println(S.toString(16));
  }

  private static BigInteger calc(BigInteger B, BigInteger k, BigInteger x, BigInteger g, BigInteger N, BigInteger u, BigInteger a)
  {
    BigInteger value = B.subtract(k.multiply(g.modPow(x, N)));
    BigInteger exponent = a.add(u.multiply(x));

    return value.modPow(exponent, N);
  }
}

你可以在这里执行: https://www.onlinegdb.com/BJXxMiO28

最后是一个使用 OpenSSL 的快速而肮脏的 C++ 实现:

#include <iostream>

 #include <openssl/bn.h>

 class BigInteger
 {
     public:
        BigInteger(char const* hexString, BN_CTX *ctx)
            : bn_{BN_new()}
            , ctx_{ctx}
        {
            BN_hex2bn(&bn_, hexString);
        }

        ~BigInteger()
        {
            BN_free(bn_);
        }

        BigInteger ModPow(BigInteger const& exponent, BigInteger const& modulo) const
        {
            BigInteger ret{"0", ctx_};
             BN_mod_exp(ret.bn_, bn_, exponent.bn_, modulo.bn_, ctx_);
             return ret;
        }

        BigInteger Subtract(BigInteger const& rhs) const
        {
            BigInteger ret{"0", ctx_};
            BN_sub(ret.bn_, bn_, rhs.bn_);
             return ret;
        }

        BigInteger Multiply(BigInteger const& rhs) const
        {
            BigInteger ret{"0", ctx_};
            BN_mul(ret.bn_, bn_, rhs.bn_, ctx_);
             return ret;
        }

        BigInteger Add(BigInteger const& rhs) const
        {
            BigInteger ret{"0", ctx_};
            BN_add(ret.bn_, bn_, rhs.bn_);
             return ret;
        }

        std::string ToString() const
        {
            return BN_bn2hex(bn_);
        }

     private:
     BIGNUM* bn_;
     BN_CTX *ctx_;
 };

BigInteger calc(BigInteger const& B, BigInteger const& k, BigInteger const& x, BigInteger const& g, BigInteger const& N, BigInteger const& u, BigInteger const& a)
{
    BigInteger value = B.Subtract(k.Multiply(g.ModPow(x, N)));
    BigInteger exponent = a.Add(u.Multiply(x));

    return value.ModPow(exponent, N);
}

int main()
{
     BN_CTX *ctx = BN_CTX_new();

    BigInteger B{"023B61801145A9CB06ADF77493042D166E793B946D1B07B46070E3986A6F036BE", ctx};
    BigInteger k{"3", ctx};
    BigInteger x{"09F015DB40A59403E42FBD568AF5774A0A0488A62", ctx};
    BigInteger g{"7", ctx};
    BigInteger N{"0894B645E89E1535BBDAD5B8B290650530801B18EBFBF5E8FAB3C82872A3E9BB7", ctx};
    BigInteger u{"0AC06F615645BEA9B3D6D887C30D28D71B079B598", ctx};
    BigInteger a{"0D4515CA7747787F1DDA9962ACE81E8412D9D20D06251696ACD74735F1F3B9875", ctx};

    auto S = calc(B, k, x, g, N, u, a);

    std::cout << S.ToString();
    BN_CTX_free(ctx);
}

你可以在这里执行: https://godbolt.org/z/PtNGdQ

同样，C++ 和 Java 都同意这个答案 218BC3CE2641EFF5F4BB95A2DB931CA62A933C6BA40D3F6E2AD5D5F7D41F0E0A只有 C# 说它是 98405F6F9C609C9A370E3A17B28CCC5322918ADCE44DE0DE7F995370A9E07253 .这是一个真正的表演障碍，因为我需要在需要第一个(正确)答案的系统上工作。我在这里真的很茫然，我真诚地希望有人知道我做错了什么。

干杯

Answer 1

Python 也同意答案应该是 218bc3ce2641eff5f4bb95a2db931ca62a933c6ba40d3f6e2ad5d5f7d41f0e0a
并且问题似乎不是十六进制解析(即使解析值的十进制版本结果是相同的)。

我认为你有正确的态度，认为它不可能是 C# 实现中的大整数中的一个错误，但这实际上在我看来是一个令人震惊的证据(即使我必须说我不是一个C# 程序员，只玩了一点)。

我认为您应该提交错误报告。

编辑

正如 Rufo 爵士在评论中正确指出的那样，问题在于如何在 C# 中处理模运算以获得负红利，将代码更改为

var val = (B - k * BigInteger.ModPow(g, x, N) + N*k) % N;

产生预期的结果。

我会说仍然是一个错误，但是一个设计错误并且不会被修复。