BigInteger 中的 .NET 错误？

Question

我一直在处理一个需要 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;

产生了预期的结果。

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

Answer 2

信息

让我们看一下 calc 方法：

当我们比较 C# val.ToString("X") 和 Java val.toString(16) 中的十六进制输出值时，我们将得到不同的输出：

C#:   F4EB82A8CAFDA89F0E2B69C3C4FEF2920913B60DD701C2193C41AE7EC6BC1A38B
Java: -b147d5735025760f1d4963c3b010d6df6ec49f228fe3de6c3be51813943e5c75

但是当我们在 C# val.ToString() 和 Java val.toString(10) 中使用十进制输出值时，我们将得到相同的输出：

C#:   -80186293521643543106092742417459818853945355375849134884320433064971933211765
Java: -80186293521643543106092742417459818853945355375849134884320433064971933211765

此答案基于您无法比较的比较（十六进制输出）。

（将此作为答案发布，因为它不适合评论，但将其设为社区维基）：

C# 和 Java 版本之间的差异发生在 calc 中。当我像这样分离出中间值时：

CSharp

BigInteger B = BigInteger.Parse("023B61801145A9CB06ADF77493042D166E793B946D1B07B46070E3986A6F036BE", NumberStyles.AllowHexSpecifier);
BigInteger k = BigInteger.Parse("3", NumberStyles.AllowHexSpecifier);
BigInteger g = BigInteger.Parse("7", NumberStyles.AllowHexSpecifier);
BigInteger x = BigInteger.Parse("09F015DB40A59403E42FBD568AF5774A0A0488A62", NumberStyles.AllowHexSpecifier);
BigInteger N = BigInteger.Parse("0894B645E89E1535BBDAD5B8B290650530801B18EBFBF5E8FAB3C82872A3E9BB7", NumberStyles.AllowHexSpecifier);

Console.WriteLine( "B == " + B.ToString("X") );
Console.WriteLine( "k == " + k.ToString("X") );
Console.WriteLine( "g == " + g.ToString("X") );
Console.WriteLine( "x == " + x.ToString("X") );
Console.WriteLine( "N == " + N.ToString("X") );

Console.WriteLine( "-------" );

BigInteger p = BigInteger.ModPow(g, x, N);
Console.WriteLine( "p == " + p.ToString("X") );

BigInteger m = k * p;
Console.WriteLine( "m == " + m.ToString("X") );

BigInteger d = B - m;
Console.WriteLine("d == " + d.ToString("X"));

Java

BigInteger B = new BigInteger("023B61801145A9CB06ADF77493042D166E793B946D1B07B46070E3986A6F036BE", 16);
BigInteger k = new BigInteger("3", 16);
BigInteger g = new BigInteger("7", 16);
BigInteger x = new BigInteger("09F015DB40A59403E42FBD568AF5774A0A0488A62", 16);
BigInteger N = new BigInteger("0894B645E89E1535BBDAD5B8B290650530801B18EBFBF5E8FAB3C82872A3E9BB7", 16);

System.out.println("B == " + B.toString(16));
System.out.println("k == " + k.toString(16));
System.out.println("g == " + g.toString(16));
System.out.println("x == " + x.toString(16));
System.out.println("N == " + N.toString(16));

System.out.println("-------");

BigInteger p = g.modPow(x, N);
System.out.println("p == " + p.toString(16));

BigInteger m = k.multiply(p);
System.out.println("m == " + m.toString(16));

BigInteger d = B.subtract(m);
System.out.println("d == " + d.toString(16));

这些给了我这个输出：

CSharp:

B == 23B61801145A9CB06ADF77493042D166E793B946D1B07B46070E3986A6F036BE
k == 3
g == 7
x == 09F015DB40A59403E42FBD568AF5774A0A0488A62
N == 0894B645E89E1535BBDAD5B8B290650530801B18EBFBF5E8FAB3C82872A3E9BB7
-------
p == 46FF4F26CC2AB0EA82B849044AC68D6CC772C8232086C890C0FBC5DE13BA3111
m == 0D4FDED74648012BF8828DB0CE053A84656585869619459B242F3519A3B2E9333
value == F4EB82A8CAFDA89F0E2B69C3C4FEF2920913B60DD701C2193C41AE7EC6BC1A38B

Java:

B == 23b61801145a9cb06adf77493042d166e793b946d1b07b46070e3986a6f036be                                                                                                 
k == 3                                                                                                                                                                
g == 7                                                                                                                                                                
x == 9f015db40a59403e42fbd568af5774a0a0488a62                                                                                                                         
N == 894b645e89e1535bbdad5b8b290650530801b18ebfbf5e8fab3c82872a3e9bb7                                                                                                 
-------                                                                                                                                                               
p == 46ff4f26cc2ab0ea82b849044ac68d6cc772c8232086c890c0fbc5de13ba3111                                                                                                 
m == d4fded74648012bf8828db0ce053a84656585869619459b242f3519a3b2e9333                                                                                                 
d == -b147d5735025760f1d4963c3b010d6df6ec49f228fe3de6c3be51813943e5c75

所以在 B - m 和 中发生了一些奇怪的事情，而不是 ModPow 调用。

第 2 部分

让我们通过序列化 BigInteger 值（我确认它们被正确序列化）将这种情况减少到 d = B - m：

CSharp

BigInteger B = BigInteger.Parse("023B61801145A9CB06ADF77493042D166E793B946D1B07B46070E3986A6F036BE", NumberStyles.AllowHexSpecifier);
Console.WriteLine( "B == " + B.ToString("X") )

BigInteger m = new BigInteger( new Byte[] { 51, 147, 46, 59, 154, 81, 243, 66, 178, 89, 148, 97, 105, 88, 88, 86, 70, 168, 83, 224, 12, 219, 40, 136, 191, 18, 128, 100, 116, 237, 253, 212, 0 } );
Console.WriteLine( "m == " + m.ToString("X") )

BigInteger d = B - m;
Console.WriteLine( "d == " + d.ToString("X") )

Java:

BigInteger B = new BigInteger("023B61801145A9CB06ADF77493042D166E793B946D1B07B46070E3986A6F036BE", 16);
BigInteger m = new BigInteger( new byte[] { 0, -44, -3, -19, 116, 100, -128, 18, -65, -120, 40, -37, 12, -32, 83, -88, 70, 86, 88, 88, 105, 97, -108, 89, -78, 66, -13, 81, -102, 59, 46, -109, 51 } );

System.out.println("B == " + B.toString(16));
System.out.println("m == " + m.toString(16));

BigInteger d = B.subtract(m);
System.out.println("d == " + d.toString(16));

这表明 C# 和 Java 对 B 和 m 的值相同，对 d 的值不同：

// C#:
B == 23B61801145A9CB06ADF77493042D166E793B946D1B07B46070E3986A6F036BE
m == 0D4FDED74648012BF8828DB0CE053A84656585869619459B242F3519A3B2E9333
d == F4EB82A8CAFDA89F0E2B69C3C4FEF2920913B60DD701C2193C41AE7EC6BC1A38B

// Java:
B == 23b61801145a9cb06adf77493042d166e793b946d1b07b46070e3986a6f036be                                                                                
m == d4fded74648012bf8828db0ce053a84656585869619459b242f3519a3b2e9333                                                                                
d == -b147d5735025760f1d4963c3b010d6df6ec49f228fe3de6c3be51813943e5c75

问题是 - F4EB82A8CAFDA89F0E2B69C3C4FEF2920913B60DD701C2193C41AE7EC6BC1A38B 代表与 -b147d5735025760f1d4963c3b010d6df6ec49f228fe3de6c3be51813943e5c75 相同的值吗？

BigInteger 中的 .NET 错误？

.NET bug in BigInteger?

c#

.net

biginteger

信息

CSharp

Java

CSharp:

Java:

第 2 部分

CSharp

Java: