我一直在需要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。因为我需要在需要第一个（正确）答案的系统上工作，所以这是一个实际的阻止因素。我在这里真的很茫然，我衷心希望有人知道我在做错什么。
欢呼声
（将其发布为答案，因为它不适合评论，但使其成为社区Wiki）：
C＃和Java版本之间的差异发生在calc内部。当我像这样分离出中间值时：
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"));
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));
这些给了我这个输出：
B == 23B61801145A9CB06ADF77493042D166E793B946D1B07B46070E3986A6F036BE
k == 3
g == 7
x == 09F015DB40A59403E42FBD568AF5774A0A0488A62
N == 0894B645E89E1535BBDAD5B8B290650530801B18EBFBF5E8FAB3C82872A3E9BB7
-------
p == 46FF4F26CC2AB0EA82B849044AC68D6CC772C8232086C890C0FBC5DE13BA3111
m == 0D4FDED74648012BF8828DB0CE053A84656585869619459B242F3519A3B2E9333
value == F4EB82A8CAFDA89F0E2B69C3C4FEF2920913B60DD701C2193C41AE7EC6BC1A38B
B == 23b61801145a9cb06adf77493042d166e793b946d1b07b46070e3986a6f036be
k == 3
g == 7
x == 9f015db40a59403e42fbd568af5774a0a0488a62
N == 894b645e89e1535bbdad5b8b290650530801b18ebfbf5e8fab3c82872a3e9bb7
-------
p == 46ff4f26cc2ab0ea82b849044ac68d6cc772c8232086c890c0fbc5de13ba3111
m == d4fded74648012bf8828db0ce053a84656585869619459b242f3519a3b2e9333
d == -b147d5735025760f1d4963c3b010d6df6ec49f228fe3de6c3be51813943e5c75
所以在B - m和not ModPow调用中发生了一些奇怪的事情。
让我们通过序列化d = B - m值将这种情况减少到BigInteger（我确认它们已经正确序列化了：]
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") )
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相同的值吗？
Python也同意答案应该是218bc3ce2641eff5f4bb95a2db931ca62a933c6ba40d3f6e2ad5d5f7d41f0e0a
并且问题似乎不是十六进制解析（即使解析值的十进制版本也相同）。
[我认为您对这种C＃实现中的大整数中的bug不太可能有正确的看法，但是在我看来，这实际上是一个令人震撼的证据（即使我必须说我是不是C＃程序员，只玩了一点）。
我认为您应该提交错误报告。
编辑
问题在于如何处理负红利的模运算，将代码更改为
var val = (B - k * BigInteger.ModPow(g, x, N) + N*1000000) % N;
产生预期的结果。