I've been working on a .NET project where I need BigIntegers and I've noticed that the framework's implementation delivers what appears to be incorrect results. After hours of trying to find what I'm doing wrong I decided to test my algorithm in Java and C++ (using OpenSSL) and shockingly in both languages I get the expected results.
Now I'm naturally wondering what I'm doing wrong (since there is no way on earth this is a bug that hasn't been noticed before) and I hope someone can help me!
This is the reduced C# code:
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);
}
}
You can execute it here: https://dotnetfiddle.net/qXXiBk
Same code in 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);
}
}
You can execute it here: https://www.onlinegdb.com/BJXxMiO28
And finally a quick and dirty C++ implementation using OpenSSL:
#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);
}
You can execute it here: https://godbolt.org/z/PtNGdQ
Again, both C++ and Java agree on the answer beeing 218BC3CE2641EFF5F4BB95A2DB931CA62A933C6BA40D3F6E2AD5D5F7D41F0E0A and only C# says it's 98405F6F9C609C9A370E3A17B28CCC5322918ADCE44DE0DE7F995370A9E07253. This is an actual show-stopper since I need to work on systems that require the first (correct) answer. I'm really at a loss here and I sincerely hope that somebody knows what I'm doing wrong.
Cheers