50

How do I, in extreme specificity, convert a given private bitcoin key into a public bitcoin key (Talk to me like I'm 5 and I have to do this step by step or the evil witch will cook me alive in her oven). NOT where can I find a program that will do this, but if I were to do it myself, what would I do?

Private Key:

18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725

supposedly results in the public key:

0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6

Others have asked how to get private to public, I haven't seen a really specific answer, just more general direction, but no answers explain all the variables. I understand this is rather complex and if a given individual thinks its too much work to answer, I totally respect that. Note: I do not care for the Bitcoin Address, just interested in Privatekey to Publickey and the specifics of how.

Variables such as the "a" and "b" in the ECDSA Curve Algorithm are already designated by Bitcoin (according to https://en.bitcoin.it/wiki/Secp256k1). the "base point" aka "G" is also specified on that page. the "private exponent" or "k", I have yet to find. Some of these variables are supposedly "random" which appears to be false as every generator that you can put a private key into seems to always spit out the same public key...so.... all the variables are either already preset or are derived from the private key.

Thanks for any help on this. I've been trying to research and understand this for days, but it seems sometimes I don't understand the terms and or notations, but I think I've gotten past that and now am just missing parts of the equation.

EDIT ADD:
This is the previous stated private key in Decimal:

11253563012059685825953619222107823549092147699031672238385790369351542642469

This is the previous stated public key (x and y values) in decimal:

36422191471907241029883925342251831624200921388586025344128047678873736520530
20277110887056303803699431755396003735040374760118964734768299847012543114150

All I want to know is how to go from that private key to the public key. Supposedly it is a simple equation that doesn't involve bit shifting or xor etc. It may include "point multiplication" (which I don't see how you can multiply a point defined as having both an x and a y). No one seems to understand the intricacies of this. Do you guys suggest I actually offer some fraction of a bitcoin to whoever explains it clearly?

3

5 Answers 5

46

I'll try answering this again in a different way, using small numbers to keep it readable.

  1. convert the private key to binary representation, so decimal number 105, which is 0x69 in hex, becomes 01101001.

  2. calculate this list of points, by repeatedly doubling the Generator point G:

    1*G
    2*G = G+G
    4*G = 2*G + 2*G
    8*G = 4*G + 4*G
    16*G = 8*G + 8*G
    32*G = 16*G + 16*G
    64*G = 32*G + 32*G
    
  3. write the bits of the private key next to this list like this:

    privkey    pointlist
       1          1*G
       0          2*G
       0          4*G
       1          8*G
       0         16*G
       1         32*G
       1         64*G
    
  4. now start adding only those points which hava a 1 written next to them.

        9*G = 1*G + 8*G
       41*G = (9+32)*G = 9*G + 32*G
      105*G = (41+64)*G = 41*G + 64*G
    
  5. now you have calculated the public key for privatekey 105 by using only point doubling and point adding operations.

The actual value will be:

(0xf219ea5d6b54701c1c14de5b557eb42a8d13f3abbcd08affcc2a5e6b049b8d63,
 0x4cb95957e83d40b0f73af4544cccf6b1f4b08d3c07b27fb8d8c2962a400766d1)

The public key will then be in one of two formats:

  • full, this is a 65 byte number, starting with a byte 0x04
  • compressed, this is a shorter form, 33 bytes, starting with either 0x02 or 0x03.

The full public key is 0x04, followed by 32 bytes of the x-coordinate, followed by 32 bytes of the y-coordinate.

The compressed public key is 0x02 or 0x03 depending on whether the y-coordinate is an even or odd number, followed by 32 bytes of the x-coordinate.

Then some more notes on your question:

  • Some older texts used to refer to scalar point multiplication, as exponentiation, that is why sometimes the private key is referred to the private exponent.

  • the parameters of the curve were chosen randomly once. meaning that the designers of the secp256k1 curve tried to unsuccessfully convey that there is no specific structure to this curve. Meaning that the NSA could or could not have put a mathematical backdoor in the curve parameters.

  • when using this curve and generating your public key, -you- have to choose your private key randomly, in a way that it is impossible for anyone to guess it.

  • the generateor G is a specific point on the elliptic curve, defined in the secp256k1 curve.

6
  • 4
    Wow, bravo! For the first time, I actually understand what's going on underneath the hood of code I have written and read. It's no longer just ecdsa.SigningKey.from_string(s.decode('hex'), curve=ecdsa.SECP256k1).verifying_key Thank you! Please post a bitcoin address! (Edit: found it on your linked web site)
    – Eric S
    Aug 6, 2014 at 8:37
  • 1
    One thing: you may want to explicitly indicate that the "NSA-proof" parameters of the curve specifically refer to G in your explanation, so that number is explained (in essence, G is just a large prime number that has certain properties wrt elliptical curves).
    – Eric S
    Aug 6, 2014 at 8:58
  • 1
    Thanks for the BTC :) Two comments: G is a curve point, not a prime number. And, whether this curve is NSA-proof is point of discussion, see the link i added. Aug 6, 2014 at 10:30
  • 1
    Yeah, I know a bit about the controversy -- that's why I put "NSA-proof" in quotes. Regarding G, I'm now curious about what exactly this is, so I asked a follow-up question here: bitcoin.stackexchange.com/questions/29904/…
    – Eric S
    Aug 7, 2014 at 16:51
  • 1
    So whats the actual public key for 105? and is G random?
    – Sam Healey
    Nov 27, 2017 at 10:33
6

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;
    }
}
7
  • 1
    I think I may almost have it.... So, we multiply the "generator256" by the "secret" and the "secret" is simply the private key. But I've lost what happens in "CurveFp curve256 = new CurveFp(p,a,b);. What occurs to those numbers to equal the "curve256" and then what happens to that to create "generator256"?Then, how is pubkeypoint broken up to give you the x and y value?does the multiplication of the gnerator256 and secret simply result in a number where the first half is the x point and the second half is the y point on the graph? (btw, I think a lot of the code doesn't apply, am i right?)
    – Mine
    May 2, 2014 at 1:05
  • When you do new CurveFp(p,a,b), the numbers are simply stored. You can think of a curve as a pairing of three numbers. Similarly, a Point is simply a pairing of a Curve and two numbers. All of these numbers are needed in order to multiply a Point by a number, which is what happens in generator256 * secret. The result of this (very complicated) multiplication is a Point; its X and Y, concatenated together, are the public key. And I think the (C#) code does all apply; you can step through the C# in a debugger with VS Express to see.
    – Tim S.
    May 2, 2014 at 11:52
  • Oh crud. If all the C# code applies then perhaps it really is too complex for someone to explain it all to me. When reading it it looked like the additional calculations were for the bitcoin address or the signature rather than just the public key (as I have no need or care for the signature or address right now since I think it will only serve to further confuse me). I see you reference those things (signature and address). I'm only looking to find how to convert the Private key to Public key and what variables are needed etc. No address, no signature, nothing more.
    – Mine
    May 2, 2014 at 21:53
  • Yep, I'm afraid the C# really is just the private to public, no signing or address involved. If you're looking to understand it, without necessarily being able to compute it practically, you can break it down into its mathematical components and research them: elliptic curves, working modulo a number (p), InverseMod, etc. Reading code is good for, "I don't care why or how it works, just make it work". That sort of research would be better for understanding the algorithms involved.
    – Tim S.
    May 2, 2014 at 22:18
  • I understand what you mean. My concern is that I can read code and get the idea of whats going on, but I don't always understand the full specifics or follow it right. if I have a 30% chance of failing to understand each line of code, after reading 30 lines of equations of code I have a significant chance of being so far off base its not even funny. I have been researching it but even those explanations I don't entirely follow as they seem to switch variables. They say "k", then in other equations they don't say specifically HOW they got a value for "k" or they might call it something else.
    – Mine
    May 3, 2014 at 5:05
4

I took Tim S's answer and stripped out more stuff until it fitted on a single page for me:

https://gist.github.com/dooglus/3b1fcbc2449063a1c3f7f1003ca26447

#! /usr/bin/env python

class Point(object):
    def __init__(self, _x, _y, _order = None): self.x, self.y, self.order = _x, _y, _order

    def calc(self, top, bottom, other_x):
        l = (top * inverse_mod(bottom)) % p
        x3 = (l * l - self.x - other_x) % p
        return Point(x3, (l * (self.x - x3) - self.y) % p)

    def double(self):
        if self == INFINITY: return INFINITY
        return self.calc(3 * self.x * self.x, 2 * self.y, self.x)

    def __add__(self, other):
        if other == INFINITY: return self
        if self == INFINITY: return other
        if self.x == other.x:
            if (self.y + other.y) % p == 0: return INFINITY
            return self.double()
        return self.calc(other.y - self.y, other.x - self.x, other.x)

    def __mul__(self, e):
        if self.order: e %= self.order
        if e == 0 or self == INFINITY: return INFINITY
        result, q = INFINITY, self
        while e:
            if e&1: result += q
            e, q = e >> 1, q.double()
        return result

    def __str__(self):
        if self == INFINITY: return "infinity"
        return "04 %x %x" % (self.x, self.y)

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

p, INFINITY = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2FL, Point(None, None) # secp256k1
g = Point(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798L, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L,
          0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141L)
secret =  0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725L
print '  privkey:    %x\n   pubkey: %s' % (secret, g * secret)

Produces this output:

  privkey:    18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725
   pubkey: 04 50863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352 2cd470243453a299fa9e77237716103abc11a1df38855ed6f2ee187e9c582ba6

I can almost understand how it works now. :)

The description of point multiplication on Wikipedia was helpful in understanding where the l values are coming from. l stands for 'lambda'.

0
4

The public key is a point (x, y) on the secp256k1 curve which can be computed by multiplying the base point G with the secret key sk. Here is a self-contained concise python function, which does this:

def sk_to_pk(sk):
    """
    Derive the public key of a secret key on the secp256k1 curve.

    Args:
        sk: An integer representing the secret key (also known as secret
          exponent).

    Returns:
        A coordinate (x, y) on the curve repesenting the public key
          for the given secret key.

    Raises:
        ValueError: The secret key is not in the valid range [1,N-1].
    """
    # base point (generator)
    G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
         0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

    # field prime
    P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

    # order
    N = (1 << 256) - 0x14551231950B75FC4402DA1732FC9BEBF

    # check if the key is valid
    if not(0 < sk < N):
        msg = "{} is not a valid key (not in range [1, {}])"
        raise ValueError(msg.format(hex(sk), hex(N-1)))

    # addition operation on the elliptic curve
    # see: https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition
    # note that the coordinates need to be given modulo P and that division is
    # done by computing the multiplicative inverse, which can be done with
    # x^-1 = x^(P-2) mod P using fermat's little theorem (the pow function of
    # python can do this efficiently even for very large P)
    def add(p, q):
        px, py = p
        qx, qy = q
        if p == q:
            lam = (3 * px * px) * pow(2 * py, P - 2, P)
        else:
            lam = (qy - py) * pow(qx - px, P - 2, P)
        rx = lam**2 - px - qx
        ry = lam * (px - rx) - py
        return rx % P, ry % P

    # compute G * sk with repeated addition
    # by using the binary representation of sk this can be done in 256
    # iterations (double-and-add)
    ret = None
    for i in xrange(256):
        if sk & (1 << i):
            if ret is None:
                ret = G
            else:
                ret = add(ret, G)
        G = add(G, G)

    return ret

The required parameteres (G, P and N) can be found in the specification: http://www.secg.org/sec2-v2.pdf#page=13. Note that this implementation aims for clarity. It is not efficient at all and probably also not safe against side channel timing attacks. An attacker could use the execution time of a call to this function to derive information about the secret key.

3

I was hoping for an answer like this, and didn't see it, so here's mine:

An elliptic curve ("EC") is a function in which the square of the y coordinate is equal to a third degree polynomial of the x coordinate.

  1. An interesting property of elliptic curves is that any two points on an EC will define a line that also hits the curve at one more place. The "sum" of the first two points is defined as the mirror image (over the X axis) of that place, so after finding the intersection, just negate the Y coordinate, and you have the point that is the "sum" of the other two.
  2. To add a point to itself, you use a line that is tangent to the EC. It, too, will intersect the curve somewhere. (You can see why this works if you imagine the two points you're adding getting closer and closer together on the curve.)
  3. You have to add the "generation point" ("G") to itself a number of times equal to the number represented by the private key to find the point that gives you the public key.
  4. If you do the algebra, you find that the equations for identifying the point on the curve that intersects with the line (either tangent to a point you're doubling, or passing through two points you're adding) are the ones implemented in the python script in another answer.**
  5. To add the point G to itself [private-key] times, you can turn it into a binary number. You can double the point G using the tangent line and intersection as described above to get 2G (a new point), and then again for 4G, 8G, etc, all new points. So now each bit position in your (binary) private key is associated with a point.
  6. Start with the least significant bit (LSB)'s associated point as your result. For each other bit (to the left of the LSB) in your private key that is 1 (skip the zeroes), calculate the "sum" point as described in step 1 using that bit's associated point from step 5 and your current result. Repeat this until you've done all the bits in your private key. Addition is associative, so you can do them in any order you want.
  7. Imagine that this curve is graphed in its infinite fullness on an infinitely large transparent plane. Now imagine that the plane is chopped up into squares so that each square is p units on a side, and then all the squares are stacked on top of each other. Thus, all the points with coordinates larger in magnitude than p are laying on top of a point for which both coordinates are less than p. That's the modulo function at work. In all the math you do in the other 5 steps, when you get an answer that is larger than p, find the answer modulo p.
  8. You end up with a result that is a point. I guess you concatenate the X and Y coordinates and that is your public key, but I'm not so sure about this last step.

This is how I understand ECC, and it may be inaccurate. I would very much appreciate any corrections or questions so that I can hone this description. Given the other answers here already, I thought this one might help a lot of people.

**It would be neat to see the algebra that shows how to get the tangent of the EC (for doublings) and also for the calculation of the point of intersection between a line defined by two other points and the curve itself.

1
  • This is a great answer. The only thing missing in IMO is about how the "point at infinity" is treated as a special point.
    – Anoop
    Mar 1, 2021 at 9:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.