Issues with programming, Bitcoin, Private Keys, and Public Keys

[dalydir]

your code
while (b != 0)

the rosetta code
while (a > 1)

your while loop will terminate for very different reasons.
The keys you got right you must have gotten lucky with
now mind telling me what the heck your doing?

calculating the modular multiplicative inverse, how does that make bitcoin?

I thought bitcoin took a big ulgy number and computed it's sha1.
if the sha1 was less then some other ulgy number called the merkle root then the mining program would say yea!

You're right, but when I use the (a > 1) it doesn't produce even a single correct x or y coordinate. 

I'm not "mak[ing] bitcoin".  This is a small program that is supposed to calculate the x and y coordinates from one's private key.  these x and y coordinates are basically your "public key".

[jonald_fyookball]

Public keys are generated from the private key using ECDSA and secp256k1.

You have 3 options:

1. Simply use an ECDSA library (easiest)
2. Take a look an existing library and try to reimplement it. ( a bit harder)
3.  Code ECDSA from scratch (hardest).

If you want to go the hard way, start here:
http://en.m.wikipedia.org/wiki/Elliptic_Curve_DSA

And you'll need the curve bitcoin uses (secp256k1)
https://en.bitcoin.it/wiki/Secp256k1

[dalydir]

Public keys are generated from the private key using ECDSA and secp256k1.

You have 3 options:

1. Simply use an ECDSA library (easiest)
2. Take a look an existing library and try to reimplement it. ( a bit harder)
3.  Code ECDSA from scratch (hardest).

If you want to go the hard way, start here:
http://en.m.wikipedia.org/wiki/Elliptic_Curve_DSA

And you'll need the curve bitcoin uses (secp256k1)
https://en.bitcoin.it/wiki/Secp256k1

The only thing that appears to be incorrect in my application (as it stands) is the multiplicative inverse.  I've coded the majority of the rest of the ECDSA algorithm as I currently intend to implement it.  If you know of an ECDSA library in which all I have to do is give it the private key, and it'll kick back the public key, please let me know and give me a simple example of that. 

Like:

publickey = prvtkeytopublickey ( <insert private key> )

If you know of one that simple I would be very grateful if you could identify that for me.  I can even do these equations on sagemath.com but C++'s coding just doesn't work with the ECDSA equations as smoothly as one would hope.

[jonald_fyookball]

http://www.cryptopp.com/

[dalydir]

http://www.cryptopp.com/

Which header file is for ECDSA secp256k1 (bitcoin's algorithm) and what's the command for converting the given private key into a public key?

[jonald_fyookball]

http://www.cryptopp.com/

Which header file is for ECDSA secp256k1 (bitcoin's algorithm) and what's the command for converting the given private key into a public key?

I don't know because I've never used that library.

It feels like you should be researching yourself
and digging in a bit deeper...otherwise, whats
the point of this project?  I thought you wanted
to learn how to write bitcoin related code.

As a developer, sometimes you have to research
things.

Did you download the code library?
Did you go to the ECDSA section?
Have you reviewed the files, classes, and functions?
Is there any documentation?
Are there examples?
Are there likely candidates for which file or command to use?

[dalydir]

http://www.cryptopp.com/

Which header file is for ECDSA secp256k1 (bitcoin's algorithm) and what's the command for converting the given private key into a public key?

I don't know because I've never used that library.

It feels like you should be researching yourself
and digging in a bit deeper...otherwise, whats
the point of this project?  I thought you wanted
to learn how to write bitcoin related code.

As a developer, sometimes you have to research
things.

Did you download the code library?
Did you go to the ECDSA section?
Have you reviewed the files, classes, and functions?
Is there any documentation?
Are there examples?
Are there likely candidates for which file or command to use?

Just to quote myself:

If you know of an ECDSA library in which all I have to do is give it the private key, and it'll kick back the public key, please let me know and give me a simple example of that.

Your response:

http://www.cryptopp.com/

along with

I don't know because I've never used that library.

So you don't know if that library is actually the answer.  Yes, I did read through it and couldn't find anything for ECDSA. 

You, and others, are insisting I should use <insert library, who's existence is not yet confirmed, here> that will resolve the matter quickly and easily, because you believe it obviously exists.  Then you suggest I use one that, as far as you know, will do nothing for me and be substantially more difficult to even figure out than just fixing the equations I've already presented.

Many of you seem to be behaving as theoreticists regarding this matter because you don't actually know the answer to the question.  I do appreciate you having a desire to help me but you're just pointing in different directions in the off chance that the solution is "that way" when you yourself don't even know if the solution is "that way", as you have not even confirmed it yourself.

Did you download the code library?

Yes I did, and it wasn't the first time I've downloaded that particular library, but I simply guessed I had perhaps overlooked something when you recommended it.

Did you go to the ECDSA section?

Yes, and no.  There was no apparent "ECDSA" section I could find.

Have you reviewed the files, classes, and functions?

To the extent that I am capable of doing, yeah, I did.

Is there any documentation?

Yes, there was, but not much.  What was there that I did understand did not appear to be sufficient to explain and or do even just the multiplicative inverse, let alone simply private key to public key.

Are there examples?

Yes, but not examples for what I've been trying to do.

Are there likely candidates for which file or command to use?

A few distantly caught my attention, but as I read through them they weren't what I was looking for.

I thought you wanted to learn how to write bitcoin related code.

Some, but the only thing I'm seeking help at this time with is converting a private key into a public key utilizing C++.

It feels like you should be researching yourself and digging in a bit deeper

I've gone as far as it seems I can go at this time, that's why I came to this forum to seek help.  To see if maybe someone could look at my code and go "oh, yeah man, look at that, you have that one equation wrong, here, go to this coliru page where I've corrected that single line".  Or if someone was going to reference a library for me they'd simply say "yeah, use abcdefg.h and type int512_t = privatekey_to_public_key_function( <private key> ) ".  I don't expect anyone to do a buttload of research for me, nor am I asking anyone to.  Just that if anyone has any insight and realizes whats going on, I'd really appreciate the help.

[jonald_fyookball]

I took a look at cryptpop... Actually there is extensive documenation
in the manual section of the website...although, I will admit that
it is quite an abstract library and would be time consuming.

Here's a much more user friendly one in C:

http://jonasfj.dk/blog/2007/12/simpleecdsa-a-simple-implementation-of-ecdsa-in-c/

go into the test.c file, and you will see the example of how
they do it.  Hope that helps.

-Jonald

Code:

bool test_key_generation(FILE* out)
{
	//First notice
	fprintf(out, "\n--- Test public key generation ---\n");

	//Setting up domain parameters
	domain_parameters curve = domain_parameters_init();
	domain_parameters_load_curve(curve, secp160r1);

	//Public key
	point Q = point_init();
	point Q_check = point_init();

	//Private key
	mpz_t d;mpz_init(d);

	//Load key from GEC test vectors
	mpz_set_str(d, "971761939728640320549601132085879836204587084162", 10);

	//Load correct result from GEC test vectors
	point_set_str(Q_check, "466448783855397898016055842232266600516272889280", "1110706324081757720403272427311003102474457754220", 10);

	//Generate public key
	signature_generate_key(Q, d, curve);

[jonald_fyookball]

here's another resource you might find useful:

https://github.com/wobine/blackboard101/blob/master/EllipticCurvesPart5-TheMagic-SigningAndVerifying.py
https://www.youtube.com/watch?v=U2bw_N6kQL8

[dalydir]

Thank you for all that jonald.  I'm still going through it all.  Either way, I think I'm going to make some progress from all this stuff here.  Its all further confirming that its all about the multiplicative inverse.

[amaclin]

Like:
publickey = prvtkeytopublickey ( <insert private key> )

Quick and dirty example with openssl

Code:

#include <QCoreApplication>
#include <QByteArray>

#include <stdio.h>

#include <openssl/ec.h>
#include <openssl/evp.h>
#include <openssl/ecdsa.h>
#include <openssl/bn.h>

static EC_KEY* EC_KEY_regenerate_key ( const quint8* priv )
{
  static EC_KEY* eckey = EC_KEY_new_by_curve_name ( NID_secp256k1 );
  static const EC_GROUP* group = EC_KEY_get0_group ( eckey );
  BIGNUM* privkey = BN_bin2bn ( priv, 32, BN_new ( ) );
  BN_CTX* ctx = BN_CTX_new ( );
  EC_POINT* pubkey = EC_POINT_new ( group );
  EC_POINT_mul ( group, pubkey, privkey, 0, 0, ctx );
  EC_KEY_set_private_key ( eckey, privkey );
  EC_KEY_set_public_key ( eckey, pubkey );
  EC_POINT_free ( pubkey );
  BN_CTX_free ( ctx );
  BN_clear_free ( privkey );
  return eckey;
}
//--------------------------------------------------------------
static const char* getPublicKey ( char* buf, const quint8* priv )
{
  quint8 pubkey [65];
  quint8* pbegin = pubkey;
  i2o_ECPublicKey ( EC_KEY_regenerate_key ( priv ), &pbegin );
  memcpy ( buf, pubkey + 1, 64 ); // without 0x04 prefix
  return (const char*)buf;
}
//--------------------------------------------------------------
static const QByteArray getPublicKeyClassic ( const quint8* priv )
{
  char buf [65];
  getPublicKey ( buf + 1, priv );
  buf [0] = 0x04;
  return QByteArray ( buf, 65 );
}
//--------------------------------------------------------------
static const QByteArray getPublicKeyCompressed ( const quint8* priv )
{
  char buf [65];
  getPublicKey ( buf + 1, priv );
  buf [0] = 0x02 + ( buf [64] & 1 );
  return QByteArray ( buf, 33 );
}
//--------------------------------------------------------------
int main ( int argc, char* argv [] )
{
  QCoreApplication a ( argc, argv );
  // correct horse battery staple
  const QByteArray priv ( QByteArray::fromHex ( "c4bbcb1fbec99d65bf59d85c8cb62ee2db963f0fe106f483d9afa73bd4e39a8a" ) );
  printf ( "classic=%s\n", getPublicKeyClassic ( (const quint8*)priv.constData ( ) ).toHex ( ).constData ( ) );
  printf ( "compressed=%s\n", getPublicKeyCompressed ( (const quint8*)priv.constData ( ) ).toHex ( ).constData ( ) );
  return a.exec ( );
}

Output is

Code:

classic=0478d430274f8c5ec1321338151e9f27f4c676a008bdf8638d07c0b6be9ab35c71a1518063243acd4dfe96b66e3f2ec8013c8e072cd09b3834a19f81f659cc3455
compressed=0378d430274f8c5ec1321338151e9f27f4c676a008bdf8638d07c0b6be9ab35c71

You can check that result is correct on brainwallet.org ( use "correct horse battery staple" as passphrase )

[dalydir]

I've gone through all the info everyone has provided.  That which I can make sense of doesn't work (even when cutting and pasting).

I'm starting to wonder, how much Bitcoin should I be offering for someone to just tweak this code so that (to verify the function of the equations) it produces the first 10 bitcoin addresses' public x,y coordinates? 

I've gone through so many ways of trying to achieve my results and none have succeeded.  my Coliru link in the first post is still the basis and I can't seem to locate anything, that, when applied, produces the desired results.

[jonald_fyookball]

I've gone through all the info everyone has provided.  That which I can make sense of doesn't work (even when cutting and pasting).

I'm starting to wonder, how much Bitcoin should I be offering for someone to just tweak this code so that (to verify the function of the equations) it produces the first 10 bitcoin addresses' public x,y coordinates?  

I've gone through so many ways of trying to achieve my results and none have succeeded.  my Coliru link in the first post is still the basis and I can't seem to locate anything, that, when applied, produces the desired results.

What 10 addresses do you speak of?  What is the starting point here?
Do you have the public keys, the private keys?  What data do you have
to begin with?

I ran the python code provided above, and it does produce the public
key from the private key using the elliptic curve math.

But I don't think you can produce the x,y coordinates from just
a bitcoin address, as that is a hash of the public key... so, what
are we talking about here?

[dalydir]

My program is just set to take the first and second Private Keys and public keys and using that data to do "point addition" to produce public keys for private keys 3 through 10.

Private Key "1" has a public x,y key of:
55066263022277343669578718895168534326250603453777594175500187360389116729240
32670510020758816978083085130507043184471273380659243275938904335757337482424

Private Key "2" has a public x,y key of:
89565891926547004231252920425935692360644145829622209833684329913297188986597
12158399299693830322967808612713398636155367887041628176798871954788371653930

If you were to use any bitcoin website or program which takes a private key, and gives you a public key, hash, and address, putting "1" in will get you the first x,y coordintes I showed, and putting in a "2" will produce the second set.  

I do intend to use this programming beyond the first 10 addresses, but if I can't get it to work for the first 10 addresses, it won't work for any other address.

http://coliru.stacked-crooked.com/a/74648b16c2692525


And which python code are you referring to?  One I ran gave me the first 1 or two addresses correctly, but not others, and it was all in floating point number format, I need the full x,y coordinates, not "5.50662630222773x10^11" type stuff.

[jonald_fyookball]

My program is just set to take the first and second Private Keys and public keys and using that data to do "point addition" to produce public keys for private keys 3 through 10.

Private Key "1" has a public x,y key of:
55066263022277343669578718895168534326250603453777594175500187360389116729240
32670510020758816978083085130507043184471273380659243275938904335757337482424

Private Key "2" has a public x,y key of:
89565891926547004231252920425935692360644145829622209833684329913297188986597
12158399299693830322967808612713398636155367887041628176798871954788371653930

If you were to use any bitcoin website or program which takes a private key, and gives you a public key, hash, and address, putting "1" in will get you the first x,y coordintes I showed, and putting in a "2" will produce the second set.  

I do intend to use this programming beyond the first 10 addresses, but if I can't get it to work for the first 10 addresses, it won't work for any other address.

http://coliru.stacked-crooked.com/a/74648b16c2692525


And which python code are you referring to?  One I ran gave me the first 1 or two addresses correctly, but not others, and it was all in floating point number format, I need the full x,y coordinates, not "5.50662630222773x10^11" type stuff.

The one I just posted...the only one in this thread.

Here is it again.
https://github.com/wobine/blackboard101/blob/master/EllipticCurvesPart5-TheMagic-SigningAndVerifying.py

Just change the privkey variable to 1 , and you get the data you posted...change it to 2, you also get that
other set of numbers you posted...so the output is as you expected.
 
Now how much Bitcoin do I get ?  Whatever you give me will go to Dob & Noella.

[dalydir]

My program is just set to take the first and second Private Keys and public keys and using that data to do "point addition" to produce public keys for private keys 3 through 10.

Private Key "1" has a public x,y key of:
55066263022277343669578718895168534326250603453777594175500187360389116729240
32670510020758816978083085130507043184471273380659243275938904335757337482424

Private Key "2" has a public x,y key of:
89565891926547004231252920425935692360644145829622209833684329913297188986597
12158399299693830322967808612713398636155367887041628176798871954788371653930

If you were to use any bitcoin website or program which takes a private key, and gives you a public key, hash, and address, putting "1" in will get you the first x,y coordintes I showed, and putting in a "2" will produce the second set.  

I do intend to use this programming beyond the first 10 addresses, but if I can't get it to work for the first 10 addresses, it won't work for any other address.

http://coliru.stacked-crooked.com/a/74648b16c2692525


And which python code are you referring to?  One I ran gave me the first 1 or two addresses correctly, but not others, and it was all in floating point number format, I need the full x,y coordinates, not "5.50662630222773x10^11" type stuff.

The one I just posted...the only one in this thread.

Here is it again.
https://github.com/wobine/blackboard101/blob/master/EllipticCurvesPart5-TheMagic-SigningAndVerifying.py

Just change the privkey variable to 1 , and you get the data you posted...change it to 2, you also get that
other set of numbers you posted...so the output is as you expected.
 
Now how much Bitcoin do I get ?  Whatever you give me will go to Dob & Noella.

Set it to 3.  It doesn't work.  Or take any random private key and place it there, it doesn't work either.

This is, of course, AFTER one mods the python code to be python 3.0 compatible....

[jonald_fyookball]

3 gives me this :  how do you know its wrong?

 
04 11271166043971060605674865917392967310211497734153940854463061355520977588812
1 25583027980570883691656905877401976406448868254816295069919888960541586679410
 

[christianlundkvist]

If anyone can make sense of:

def inverse(x, p):
"""
Calculate the modular inverse of x ( mod p )
the modular inverse is a number such that:
(inverse(x, p) * x) % p == 1
you could think of this as: 1/x
"""
inv1 = 1
inv2 = 0
while p != 1 and p!=0:
inv1, inv2 = inv2, inv1 - inv2 * (x / p)
x, p = p, x % p
 
return inv2

Which is in Python, it would solve my dilemma.  The commas don't make sense to me (IE: "How can a comma work with the equal sign").  That seems to be the part of my program which doesn't function correctly.  Yes, my code has that as well; that's the only part of my code I don't understand piece for piece (as I had to copy and paste that part).  All I'm really trying to do is to get this code to work.  This code should just spit out the public key for addresses represented by the number 4 through the number 10.

The algorithm above for the modular inverse is the Extended Euclidean Algorithm, basically the algorithm will spit out an integer a with the property that a*x + b*p = 1 for some number b.

As for the commas in python, in general a,b = c,d means that a=c and b=d, and you can also do things like swapping the values of a and b by using a,b = b,a.

In our case

Code:

inv1, inv2 = inv2, inv1 - inv2 * (x / p)
x, p = p, x % p

can be written more explicitly as

Code:

temp = inv2
inv2 = inv1 - inv2 * (x / p)
inv1 = temp

temp = p
p = x % p
x = temp

When you test the code, you can check if the value a returned by your function satisfies (a*x) % p == 1.

[dalydir]

3 gives me this :  how do you know its wrong?

 
04 11271166043971060605674865917392967310211497734153940854463061355520977588812
1 25583027980570883691656905877401976406448868254816295069919888960541586679410
 

Who knows, you may have a different version of Python installed on your computer whereby it works differently than on mine.  I have python 3 installed so I had to modify the code to keep it from erroring out first.

These are the first 5 bitcoin addresses, represented by the number 1 through 5.  The x01 is just a reference to which address and the two following numbers are the x,y coordinates.

x01
55066263022277343669578718895168534326250603453777594175500187360389116729240
32670510020758816978083085130507043184471273380659243275938904335757337482424


x02
89565891926547004231252920425935692360644145829622209833684329913297188986597
12158399299693830322967808612713398636155367887041628176798871954788371653930

x03
112711660439710606056748659173929673102114977341539408544630613555209775888121
25583027980570883691656905877401976406448868254816295069919888960541586679410

x04
103388573995635080359749164254216598308788835304023601477803095234286494993683
37057141145242123013015316630864329550140216928701153669873286428255828810018

x05
21505829891763648114329055987619236494102133314575206970830385799158076338148
98003708678762621233683240503080860129026887322874138805529884920309963580118


When I say I had to modify the code it was just for the "print" command, not the equations itself.  But typing in 3 as the private key gives me "5.506626302227735e+76 3.267051002075881e+76", because what you showed you got for that address did appear to be correct, which is awesome.  My only guess is you have a different version of python installed.

Christianlundkvist, Thanks for putting it like that, I may be able to work with that too (hopefully that'll identify why my code isn't working properly after address 3

[dalydir]

If anyone can make sense of:

def inverse(x, p):
"""
Calculate the modular inverse of x ( mod p )
the modular inverse is a number such that:
(inverse(x, p) * x) % p == 1
you could think of this as: 1/x
"""
inv1 = 1
inv2 = 0
while p != 1 and p!=0:
inv1, inv2 = inv2, inv1 - inv2 * (x / p)
x, p = p, x % p
 
return inv2

Which is in Python, it would solve my dilemma.  The commas don't make sense to me (IE: "How can a comma work with the equal sign").  That seems to be the part of my program which doesn't function correctly.  Yes, my code has that as well; that's the only part of my code I don't understand piece for piece (as I had to copy and paste that part).  All I'm really trying to do is to get this code to work.  This code should just spit out the public key for addresses represented by the number 4 through the number 10.

The algorithm above for the modular inverse is the Extended Euclidean Algorithm, basically the algorithm will spit out an integer a with the property that a*x + b*p = 1 for some number b.

As for the commas in python, in general a,b = c,d means that a=c and b=d, and you can also do things like swapping the values of a and b by using a,b = b,a.

In our case

Code:

inv1, inv2 = inv2, inv1 - inv2 * (x / p)
x, p = p, x % p

can be written more explicitly as

Code:

temp = inv2
inv2 = inv1 - inv2 * (x / p)
inv1 = temp

temp = p
p = x % p
x = temp

When you test the code, you can check if the value a returned by your function satisfies (a*x) % p == 1.

Just realized, the problem isn't that I'm getting a solution to the problem, its getting the wrong solution....I think.  The whole result keeps giving me negative y coordinates for the public key, which, mathematically, may make sense, but its not a valid public key in it of itself.  When I add "p", or the mod number to it to provide me with a positive number, it gives me a valid y coordinate, but the wrong y coordinate for the given private key.