I'm working on a program that converts a Bitcoin private key to a public key. I've done a lot of searching and looked at a lot of documentation and code. And I've tested the following C# code presented here: https://bitcoin.stackexchange.com/questions/25024/how-do-you-get-a-bitcoin-public-key-from-a-private-key It converts some private keys to public keys correctly, but it doesn't convert some private keys to public keys correctly. For example, consider the following private key: b5639dccd31e3694e53e4d2cfea652dc0ab4be5183fdfc6017eb09b1def82970
The public key is exactly as follows: 04cbadea7f70bb1c885773e3727699773febe8ced1ec1ee73ea952409e6a77b4483a1eb131d0a9e0e3588a88cfbb8a0c74136967e97c297939f2e1b75b3d4bc757
But the program generates the key as follows: It produces 0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 which is wrong but for the following private key 22c355eaf7cf3822520e6e02b1fc996d7c2cd8376451599101a64f8d5ddc4634 it generates the following public key which is correct is 048a4ea6d6db213b32f6c5e48f041481539303ce755dad8e0e042ca012c234f30d36c1f5348a8bdeed856af5948c645cce1eb86813c467bd5e89a8386311be4420
Apparently all parts of the code are correct but I don't know what exactly is the problem. Can anyone help me with this?
Answer
This is the code:
class CalcPub
{
public static void Main()
{
var p = BigInteger.Parse("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", NumberStyles.HexNumber);
var b = (BigInteger)7;
var a = BigInteger.Zero;
var Gx = BigInteger.Parse("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", NumberStyles.HexNumber);
var Gy = BigInteger.Parse("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", NumberStyles.HexNumber);
CurveFp curve256 = new CurveFp(p, a, b);
Point generator256 = new Point(curve256, Gx, Gy);
var secret = BigInteger.Parse("18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725", NumberStyles.HexNumber);
Console.WriteLine("secret {0}", secret.ToString("X"));
var pubkeyPoint = generator256 * secret;
Console.WriteLine("pubkey {0}{1}", pubkeyPoint.X.ToString("X"), pubkeyPoint.Y.ToString("X"));
}
}
class Point
{
public static readonly Point INFINITY = new Point(null, default(BigInteger), default(BigInteger));
public CurveFp Curve { get; private set; }
public BigInteger X { get; private set; }
public BigInteger Y { get; private set; }
public Point(CurveFp curve, BigInteger x, BigInteger y)
{
this.Curve = curve;
this.X = x;
this.Y = y;
}
public Point Double()
{
if (this == INFINITY)
return INFINITY;
BigInteger p = this.Curve.p;
BigInteger a = this.Curve.a;
BigInteger l = ((3 * this.X * this.X + a) * InverseMod(2 * this.Y, p)) % p;
BigInteger x3 = (l * l - 2 * this.X) % p;
BigInteger y3 = (l * (this.X - x3) - this.Y) % p;
return new Point(this.Curve, x3, y3);
}
public override string ToString()
{
if (this == INFINITY)
return "infinity";
return string.Format("({0},{1})", this.X, this.Y);
}
public static Point operator +(Point left, Point right)
{
if (right == INFINITY)
return left;
if (left == INFINITY)
return right;
if (left.X == right.X)
{
if ((left.Y + right.Y) % left.Curve.p == 0)
return INFINITY;
else
return left.Double();
}
var p = left.Curve.p;
var l = ((right.Y - left.Y) * InverseMod(right.X - left.X, p)) % p;
var x3 = (l * l - left.X - right.X) % p;
var y3 = (l * (left.X - x3) - left.Y) % p;
return new Point(left.Curve, x3, y3);
}
public static Point operator *(Point left, BigInteger right)
{
var e = right;
if (e == 0 || left == INFINITY)
return INFINITY;
var e3 = 3 * e;
var negativeLeft = new Point(left.Curve, left.X, -left.Y);
var i = LeftmostBit(e3) / 2;
var result = left;
while (i > 1)
{
result = result.Double();
if ((e3 & i) != 0 && (e & i) == 0)
result += left;
if ((e3 & i) == 0 && (e & i) != 0)
result += negativeLeft;
i /= 2;
}
return result;
}
private static BigInteger LeftmostBit(BigInteger x)
{
BigInteger result = 1;
while (result <= x)
result = 2 * result;
return result / 2;
}
private static BigInteger InverseMod(BigInteger a, BigInteger m)
{
while (a < 0) a += m;
if (a < 0 || m <= a)
a = a % m;
BigInteger c = a;
BigInteger d = m;
BigInteger uc = 1;
BigInteger vc = 0;
BigInteger ud = 0;
BigInteger vd = 1;
while (c != 0)
{
BigInteger r;
//q, c, d = divmod( d, c ) + ( c, );
var q = BigInteger.DivRem(d, c, out r);
d = c;
c = r;
//uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc;
var uct = uc;
var vct = vc;
var udt = ud;
var vdt = vd;
uc = udt - q * uct;
vc = vdt - q * vct;
ud = uct;
vd = vct;
}
if (ud > 0) return ud;
else return ud + m;
}
}
class CurveFp
{
public BigInteger p { get; private set; }
public BigInteger a { get; private set; }
public BigInteger b { get; private set; }
public CurveFp(BigInteger p, BigInteger a, BigInteger b)
{
this.p = p;
this.a = a;
this.b = b;
}
}
