Topic: private to public question. (Read 727 times)

http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

Multiplication is repeated addition.  The pubkey is G * privkey.  The catch is that privkey is huge, so doing simple addition privkey times would take forever.

The algorithm you see here is an optimized exponential multiplication.

Ignore OpenSSL.  That way lays madness...

I started by looking at openssl.  I cannot find where this is done in C in their area.  The executable puts out a pem file that looks like this:

Private-Key: (256 bit)
priv:
    00:f8:ed:69:2e:36:41:73:c9:17:bf:c6:16:ce:cd:
    6a:af:49:11:1e:a8:d2:00:47:6f:c2:25:62:85:50:
    80:9b:a0
pub:
    04:9e:54:ce:31:52:2d:fc:18:a4:7a:f6:2e:b4:34:
    f8:70:69:e6:d9:2c:ac:1f:7c:d2:8f:98:ac:0c:ac:
    7f:69:ec:06:bf:e6:d5:b4:cd:af:4e:8c:2f:a5:59:
    63:d0:38:56:e6:17:fb:38:2e:e4:e3:75:ee:ca:5b:
    e3:0c:44:03:3d
ASN1 OID: secp256k1
-----BEGIN PUBLIC KEY-----
MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEnlTOMVIt/BikevYutDT4cGnm2SysH3zS
j5isDKx/aewGv+bVtM2vTowvpVlj0DhW5hf7OC7k43XuylvjDEQDPQ==
-----END PUBLIC KEY-----


Being that it is a loop I am sure it is not doing the double then add.  That would take too long I think.  There is just no real documentation on the different libraries on how this is done in layman's terms.  Great on the x only with two possible y values.  Is there any way of getting a break down in English as a step by step on the whole process.  I have been looking every where and have found a number of books on all of this and it simply does not exist.

The privkey_to_pubkey() function appears to handle several different types of inputs, and provides corresponding output types.  I'm not a python guy, but the cases in the switch seem to be:  regular number, uncompressed hex, compressed hex, uncompressed binary string, compressed binary string, WIF.

Pubkeys can be compressed simply by throwing away the Y value and including a flag indicating which of the two possible values is right.  This compressed form has a different hash from the uncompressed form, and thus a different address, so a portable private key needs to indicate which of the two possible addresses is the right one.  This is done by including a flag that can be detected simply by noting the extra byte, or two extra hex characters.

base10_multiply() just does point multiplication in a very direct way.  It is a loop, though it may not look like it.  If it is still confusing, you need to learn about EC math to make it clearer.

P.S.  There is no factoring.

Great.  The point math and log factoring is unto itself.  I am good with this.  I am sure when the code simply calculates from a private key to a public point.  it is not doing the complete factoring work.  I was only seeing if there are some python people out there that can explain the code so that as this should work one can read it. Basically putting what the main function is doing in normal math rather than learning python complete.  I am sure that this can be done as someone has compatible code that works with the blockchain relative to open ssl.

I don't think you're going to find a simpler one-stop-shop implementation of curve arithmetic than vbuterin's code.


I can't tell if you're referring to http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication or if you're confusing point-multiplication with `*` in `6 * 2 = 12`.

`base10_multiply` is recursively applying the `base10_add` function. It's all pretty much laid out there for you, although it helps to know that `inv` is an inverse mod function.

If you're having difficulty understanding the math, then it probably means you need to zoom out and get a higher level understanding of elliptic curves and some dependent nodes along that talent tree. If you're using Mathematica, then surely there are examples of curve math out there already described for you in the semantics of Mathematica so you don't have to translate Python.

I found this python code from pybitcoin tools.  In the main:

def base10_multiply(a,n):
  if isinf(a) or n == 0: return (0,0)
  if n == 1: return a
  if n < 0 or n >= N: return base10_multiply(a,n%N)
  if (n%2) == 0: return base10_double(base10_multiply(a,n/2))
  if (n%2) == 1: return base10_add(base10_double(base10_multiply(a,n/2)),a)


def privkey_to_pubkey(privkey):
  if isinstance(privkey,(int,long)):
      return base10_multiply(G,privkey)
  if len(privkey) == 64:
      return point_to_hex(base10_multiply(G,decode(privkey,16)))
  elif len(privkey) == 66:
      return compress(base10_multiply(G,decode(privkey[:-2],16)),'hex')
  elif len(privkey) == 32:
      return point_to_hex(base10_multiply(G,decode(privkey,16)))
  elif len(privkey) == 33:
      return compress(base10_multiply(G,decode(privkey[:-1],16)),'bin')
  else:
      return privkey_to_pubkey(b58check_to_hex(privkey))

  If one uses base ten like the numbers used at the top of the main area.  I am having issues checking this as to how it works.  It looks like it is a simple gx times private key Mod P to get the public x part.  Then do this for Y.  This does not work in a program like mathematica for checking it.

  Does anyone know the regular math involved for taking the private key in base ten and using the parameters from the main starting area to generate the public x,y?  Also the fips big endian thing is a real pain.  Thanks.