protocol – How do you get a Bitcoin Public Key from a Private Key


Here’s a self-contained Python script that does the conversion. You can check its work by comparing to entering your private key as the “Secret Exponent” at Brainwallet. I took the script from this Bitcointalk thread and stripped out unnecessary stuff (like the code to use the public key to sign a message and verify that signature).

Converting the Python to instructions for a human is left as an exercise to the reader (although I’d argue that in a scenario like this Python code, with appropriate documentation, is just fine as instructions to a human). Note that it’s entirely possible to compute this with pen and paper, but it could take a while, and you’re likely to make a mistake, due to having to deal with such enormous numbers.

Also note that there are no individual operations here that are much more complicated than you’d learn in primary/elementary school. There’s basic comparisons < > ==, arithmetic + - *, division where you care about the quotient /, remainder %, or both divmod, and bitwise AND (&, which is pretty easy if you work in hex; or can be replicated with arithmetic).

I don’t think a (non-genius) 5 year old could actually do it (sorry, the evil witch wins this round), but I think an average adult with enough patience could learn the math needed in nearly no time (with the Python script as a..well..script, to follow). Actually calculating even one public key without the aid of electronic computing devices could take a very long time, however (at a guess: years).

#! /usr/bin/env python
# python 2.x

class CurveFp( object ):
  def __init__( self, p, a, b ):
    self.__p = p
    self.__a = a
    self.__b = b

  def p( self ):
    return self.__p

  def a( self ):
    return self.__a

  def b( self ):
    return self.__b

  def contains_point( self, x, y ):
    return ( y * y - ( x * x * x + self.__a * x + self.__b ) ) % self.__p == 0

class Point( object ):
  def __init__( self, curve, x, y, order = None ):
    self.__curve = curve
    self.__x = x
    self.__y = y
    self.__order = order
    if self.__curve: assert self.__curve.contains_point( x, y )
    if order: assert self * order == INFINITY

  def __add__( self, other ):
    if other == INFINITY: return self
    if self == INFINITY: return other
    assert self.__curve == other.__curve
    if self.__x == other.__x:
      if ( self.__y + other.__y ) % self.__curve.p() == 0:
        return INFINITY
      else:
        return self.double()

    p = self.__curve.p()
    l = ( ( other.__y - self.__y ) * 
          inverse_mod( other.__x - self.__x, p ) ) % p
    x3 = ( l * l - self.__x - other.__x ) % p
    y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
    return Point( self.__curve, x3, y3 )

  def __mul__( self, other ):
    def leftmost_bit( x ):
      assert x > 0
      result = 1L
      while result <= x: result = 2 * result
      return result / 2

    e = other
    if self.__order: e = e % self.__order
    if e == 0: return INFINITY
    if self == INFINITY: return INFINITY
    assert e > 0
    e3 = 3 * e
    negative_self = Point( self.__curve, self.__x, -self.__y, self.__order )
    i = leftmost_bit( e3 ) / 2
    result = self
    while i > 1:
      result = result.double()
      if ( e3 & i ) != 0 and ( e & i ) == 0: result = result + self
      if ( e3 & i ) == 0 and ( e & i ) != 0: result = result + negative_self
      i = i / 2
    return result

  def __rmul__( self, other ):
    return self * other

  def __str__( self ):
    if self == INFINITY: return "infinity"
    return "(%d,%d)" % ( self.__x, self.__y )

  def double( self ):
    if self == INFINITY:
      return INFINITY

    p = self.__curve.p()
    a = self.__curve.a()
    l = ( ( 3 * self.__x * self.__x + a ) * 
          inverse_mod( 2 * self.__y, p ) ) % p
    x3 = ( l * l - 2 * self.__x ) % p
    y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
    return Point( self.__curve, x3, y3 )

  def x( self ):
    return self.__x

  def y( self ):
    return self.__y

  def curve( self ):
    return self.__curve

  def order( self ):
    return self.__order

INFINITY = Point( None, None, None )

def inverse_mod( a, m ):
  if a < 0 or m <= a: a = a % m
  c, d = a, m
  uc, vc, ud, vd = 1, 0, 0, 1
  while c != 0:
    q, c, d = divmod( d, c ) + ( c, )
    uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc
  assert d == 1
  if ud > 0: return ud
  else: return ud + m

# secp256k1
_p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2FL
_r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141L
_b = 0x0000000000000000000000000000000000000000000000000000000000000007L
_a = 0x0000000000000000000000000000000000000000000000000000000000000000L
_Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798L
_Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L

class Public_key( object ):
  def __init__( self, generator, point ):
    self.curve = generator.curve()
    self.generator = generator
    self.point = point
    n = generator.order()
    if not n:
      raise RuntimeError, "Generator point must have order."
    if not n * point == INFINITY:
      raise RuntimeError, "Generator point order is bad."
    if point.x() < 0 or n <= point.x() or point.y() < 0 or n <= point.y():
      raise RuntimeError, "Generator point has x or y out of range."

curve_256 = CurveFp( _p, _a, _b )
generator_256 = Point( curve_256, _Gx, _Gy, _r )
g = generator_256

if __name__ == "__main__":
  print '======================================================================='
  ### set privkey
  # wiki
  #secret = 0xE9873D79C6D87DC0FB6A5778633389F4453213303DA61F20BD67FC233AA33262L
  # question
  secret = 0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725L

  ### print privkey
  print 'secret', hex(secret)
  ### generate pubkey
  pubkey = Public_key( g, g * secret )
  ### print pubkey
  print 'pubkey', hex(pubkey.point.x()), hex(pubkey.point.y())
  print '======================================================================='

See also an even-more-stripped-down version written in C#.

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;
    }
}