Hey Mike, you could even make coins with a sticker on each side. One from you and one from the insurance company. Put the final public key address on the second sticker with no public key address on the first one (so no one gets confused). That would be pretty cool. Logistical issues sure, but very cool.
This thread and others like it is why I LOVE Bitcoins!
BTW: this property can be extended to any number of "cosigners". Three stickers, four stickers, etc.
etotheipi - Welcome to the party! I clicked on one of the links in your signature and all I can say is WOW. Everyone, if you liked this thread you will probably like his thread at https://bitcointalksearch.org/topic/on-the-wire-byte-map-opchecksig-diagram-knowledge-donation-29416
Topic: Elliptic curve math question - page 5. (Read 14045 times)
Also, I think I have presented the simplest possible proof I can think of in post #32 and Mike presented proof by example in post #33. He wrote the code and did exactly what we are saying will work - and it worked.
He took two actual private keys.
Added them together and then computed the public key.
He also took the two public keys and added them together and he got the same public key. See:
It may be counter-intuitive but it is true and it works. Don't know what else to say.
He took two actual private keys.
Added them together and then computed the public key.
He also took the two public keys and added them together and he got the same public key. See:
Code:
Private key 1 is B2 55 38 35 39 4D 34 8C 85 54 BB EB 14 02 29 91 D4 89 E4 EF 4A F7 20 51 D3 59 5F 8C 23 E1 BC B9
Private key 2 is E2 DC 50 E3 79 E0 EC F8 2D C0 5E 6D A5 08 89 CC 8A 4C CA C2 3F 40 76 76 CD 15 3C 49 C9 AB AB 41
Bitcoin address of summing public keys: 12mMm5FypacB3rcehrBpqaNqwYvF9PSjjE
Bitcoin address of summing private keys: 12mMm5FypacB3rcehrBpqaNqwYvF9PSjjE
Combined private key: 95 31 89 18 B3 2E 21 84 B3 15 1A 58 B9 0A B3 5F A4 27 D2 CA DA EE F6 8C E0 9C 3D 49 1D 57 26 B9
It may be counter-intuitive but it is true and it works. Don't know what else to say.
Thanks. That summary and the references back to #32 & #33 finally made it click.
All I can say is ECC has some pretty "cool" mathematical properties. This opens up the door for a lot of interesting things. For example hypothetically someday an insurance company could underwrite physical coins/notes to insure against the originator fraud. Managing that risk would be tough and would likely result in high premiums BUT if they were one of the partial key holders they would have a much higher confidence in the ability to manage risk and thus write a policy.
Someday you could possibly buy insured physical bitcoins/notes. The originator risk could be eliminated via insurance premium.
Granted you would still have the risk of a post-origination counterfeit risk but all currency carries that risk (just ask the Secret Service).
Maybe one more thing:
Do you see/believe that for integers A, a, B, b, and G if A = a x G and B = b x G then
Z = A + B
= (a x G) + (b x G)
= (a + b) x (G)
where + is integer addition and x is integer multiplication?
Hopefully you know this to be true for integers, right? So now can you prove it?
Well it turns out this is also true for any finite field, for example the boolean field where A, a, B, b, G and Z can only be a 0 or a 1 and + is the boolean OR operation and x is the boolean AND operation.
You could prove this to yourself by trying every single possible combination of values for A, a, B, b, G where they can be either 0 or a 1.
Then the beauty of group theory is that if it is true for one finite field it is true for all finite fields.
The case in point is slightly different in that a and b come from a finite field and Z, A, B and G come from a finite (elliptical) group.
But asking for proof is like when I asked you for proof above. Do you see what I mean?
Do you see/believe that for integers A, a, B, b, and G if A = a x G and B = b x G then
Z = A + B
= (a x G) + (b x G)
= (a + b) x (G)
where + is integer addition and x is integer multiplication?
Hopefully you know this to be true for integers, right? So now can you prove it?
Well it turns out this is also true for any finite field, for example the boolean field where A, a, B, b, G and Z can only be a 0 or a 1 and + is the boolean OR operation and x is the boolean AND operation.
You could prove this to yourself by trying every single possible combination of values for A, a, B, b, G where they can be either 0 or a 1.
Then the beauty of group theory is that if it is true for one finite field it is true for all finite fields.
The case in point is slightly different in that a and b come from a finite field and Z, A, B and G come from a finite (elliptical) group.
But asking for proof is like when I asked you for proof above. Do you see what I mean?
Also, I think I have presented the simplest possible proof I can think of in post #32 and Mike presented proof by example in post #33. He wrote the code and did exactly what we are saying will work - and it worked.
He took two actual private keys. Added them together and then computed the public key.
He also took the two public keys and added them together and he got the same public key. See:
It may be counter-intuitive but it is true and it works. Don't know what else to say.
He took two actual private keys. Added them together and then computed the public key.
He also took the two public keys and added them together and he got the same public key. See:
Code:
Private key 1 is B2 55 38 35 39 4D 34 8C 85 54 BB EB 14 02 29 91 D4 89 E4 EF 4A F7 20 51 D3 59 5F 8C 23 E1 BC B9
Private key 2 is E2 DC 50 E3 79 E0 EC F8 2D C0 5E 6D A5 08 89 CC 8A 4C CA C2 3F 40 76 76 CD 15 3C 49 C9 AB AB 41
Bitcoin address of summing public keys: 12mMm5FypacB3rcehrBpqaNqwYvF9PSjjE
Bitcoin address of summing private keys: 12mMm5FypacB3rcehrBpqaNqwYvF9PSjjE
Combined private key: 95 31 89 18 B3 2E 21 84 B3 15 1A 58 B9 0A B3 5F A4 27 D2 CA DA EE F6 8C E0 9C 3D 49 1D 57 26 B9
It may be counter-intuitive but it is true and it works. Don't know what else to say.
I would love to get involved in this discussion, since I am actually a mathematician. But, I am desperately short on time at the moment. Until then, take note of this post:
https://bitcointalksearch.org/topic/solved-python-secp256k1-23241
The post is in Russian, but the code works, and it was the base for all my ECC operations in PyBtcEngine (in my signature). Definitely works. And if you plug that page through a translator, it is clear that Lis is releasing the code into the public domain.
In PyBtcEngine, you can see how I wrapped his code to tie it into Bitcoin itself (starting at line 844, all the createFromPrivateKey, createFromPublicKey, etc). Mostly just keeping track of private-key exponents, and public-key coords all as integers, then plugging them into his code.
In the future I plan to write a primer on asymmetric encryption. But, that is in the future...
-Eto
https://bitcointalksearch.org/topic/solved-python-secp256k1-23241
The post is in Russian, but the code works, and it was the base for all my ECC operations in PyBtcEngine (in my signature). Definitely works. And if you plug that page through a translator, it is clear that Lis is releasing the code into the public domain.
In PyBtcEngine, you can see how I wrapped his code to tie it into Bitcoin itself (starting at line 844, all the createFromPrivateKey, createFromPublicKey, etc). Mostly just keeping track of private-key exponents, and public-key coords all as integers, then plugging them into his code.
In the future I plan to write a primer on asymmetric encryption. But, that is in the future...
-Eto
Bwagner: I was just going to post that! That page is part of a very good introduction to the EC math. The start of that intro is here: http://www.certicom.com/index.php/10-introduction
netrin: An analogy with "baby numbers" would go somewhat like this. I have to abstract some cryptography properties though.
Person A comes up with a number, say 13, and calls this private key 1. He then calculates the public key, which is (for example) "accb". This public key has the property that it can be easily calculated from the private key, but it also has the property that if you only know "accb", then there is no way to find out the private key was 13, unless you bruteforce all numbers by calculating the public key to all of them.
Person B comes up with a number, say 41, and calls this private key 2. He then calculates the public key, which is (for example) "bbbb".
Person A gets the public key from Person B, and adds it to his own: "accb" + "bbbb" = "cddd"
Person B gets the public key from Person A, and adds it to his own: "bbbb" + "accb" = "cddd"
Now they both have the public key "cddd", so they can send money to that public key. To retrieve the money, however, you need to have the private key.
The private key to "cddd" is 13 + 41 = 54. But no one knows this!
That's roughly how you create a private key that no one knows.
I would like to note that this is NOT diffie-hellman secret generation, as far as I know! Neither party knows the private key here, and in fact, any attacker listening to the network could know the private key too. This doesn't matter too much though, since the private key is what you need to get the money. EC diffie-hellman looks similar but is slightly different. In fact it's more like what ByteCoin described early on in the thread. In order not to confuse the thread/topic, I'll just link to the wikipedia page: http://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman
netrin: An analogy with "baby numbers" would go somewhat like this. I have to abstract some cryptography properties though.
Person A comes up with a number, say 13, and calls this private key 1. He then calculates the public key, which is (for example) "accb". This public key has the property that it can be easily calculated from the private key, but it also has the property that if you only know "accb", then there is no way to find out the private key was 13, unless you bruteforce all numbers by calculating the public key to all of them.
Person B comes up with a number, say 41, and calls this private key 2. He then calculates the public key, which is (for example) "bbbb".
Person A gets the public key from Person B, and adds it to his own: "accb" + "bbbb" = "cddd"
Person B gets the public key from Person A, and adds it to his own: "bbbb" + "accb" = "cddd"
Now they both have the public key "cddd", so they can send money to that public key. To retrieve the money, however, you need to have the private key.
The private key to "cddd" is 13 + 41 = 54. But no one knows this!
That's roughly how you create a private key that no one knows.
I would like to note that this is NOT diffie-hellman secret generation, as far as I know! Neither party knows the private key here, and in fact, any attacker listening to the network could know the private key too. This doesn't matter too much though, since the private key is what you need to get the money. EC diffie-hellman looks similar but is slightly different. In fact it's more like what ByteCoin described early on in the thread. In order not to confuse the thread/topic, I'll just link to the wikipedia page: http://en.wikipedia.org/wiki/Elliptic_curve_Diffie%E2%80%93Hellman
netrin,
You will be very happy to see this. It is an elliptical group F23 with all 23 of the points calculated and graphed. You can add them to your hearts desire using the defined addition formulas:
http://www.certicom.com/index.php/31-example-of-an-elliptic-curve-group-over-fp
You will be very happy to see this. It is an elliptical group F23 with all 23 of the points calculated and graphed. You can add them to your hearts desire using the defined addition formulas:
http://www.certicom.com/index.php/31-example-of-an-elliptic-curve-group-over-fp
It's not really math that you want to do by hand. Quite tedious. ... All operations have to be done modulo the order of the field. Quite tedious by hand. I can post my whole code somewhere if you want it.
You may be surprised by what mathematical tedium I will endure.
In fact, only by doing RSA did I understand how to simplify the very large modulo exponents quickly and without running out of memory. I'd appreciate seeing the python code, if you don't mind (PM). So far, doesn't look too bad. double:
L = ( 3(x^2) + a) / 2y
X = L^2 - 2x
Y = L(x-X)-y (all ops modulo mo)
I don't purport to know how the math works, but this is a *very* interesting discussion that will hopefully result in some new innovations with bitcoin.
Check it out, where if his output is correct, he multiplied the two private keys together instead of adding them together:
Unfortunately, I think that was a mistake I made.
My program said that I "multiplied", and that's what I thought I did, but looking at the code, I added them.
Code:
// Combine the two private keys together.
Org.BouncyCastle.Math.BigInteger privsum = priv1.D.Add(priv2.D).Mod(ps.N);
If I change the Add to a Multiply, it stops working.
The output SHOULD be:
The output:
Code:
Private key 1 is B2 55 38 35 39 4D 34 8C 85 54 BB EB 14 02 29 91 D4 89 E4 EF 4A F7 20 51 D3 59 5F 8C 23 E1 BC B9
Private key 2 is E2 DC 50 E3 79 E0 EC F8 2D C0 5E 6D A5 08 89 CC 8A 4C CA C2 3F 40 76 76 CD 15 3C 49 C9 AB AB 41
Bitcoin address of summing public keys: 12mMm5FypacB3rcehrBpqaNqwYvF9PSjjE
Bitcoin address of summing private keys: 12mMm5FypacB3rcehrBpqaNqwYvF9PSjjE
Combined private key: 95 31 89 18 B3 2E 21 84 B3 15 1A 58 B9 0A B3 5F A4 27 D2 CA DA EE F6 8C E0 9C 3D 49 1D 57 26 B9
Google's not too helpful either. Going through some material I'm still at step one:
y^2 = x^3 + ax + b
x=4
a=5
b=20
y=11
Are x and y integers, real, or complex?
I didn't understand RSA nor D-H until I could draw them out on paper. This seems like the "Hello World" of cryptography, which is rarely available.
y^2 = x^3 + ax + b
x=4
a=5
b=20
y=11
Are x and y integers, real, or complex?
I didn't understand RSA nor D-H until I could draw them out on paper. This seems like the "Hello World" of cryptography, which is rarely available.
To answer your question if you want to take a stab at it you would need to select a prime number p for your field and then since for Bitcoins a=0 and b=7 your elliptical group generator equation would be:
y^2 mod p = ( x^3 + b ) mod p
As stated above very tedious by hand. If you pick a small prime like say 13 then there will be only 13 points that will satisfy this equation and those 13 points will form your elliptical group. Then you would need to learn how to add two of the points together - not trivial but you can look it up or I can give you the equations EDIT: Just read the previous post which includes what you need to add points so I don't have to look it up!
Google's not too helpful either. Going through some material I'm still at step one:
y^2 = x^3 + ax + b
x=4
a=5
b=20
y=11
Are x and y integers, real, or complex?
I didn't understand RSA nor D-H until I could draw them out on paper. This seems like the "Hello World" of cryptography, which is rarely available.
y^2 = x^3 + ax + b
x=4
a=5
b=20
y=11
Are x and y integers, real, or complex?
I didn't understand RSA nor D-H until I could draw them out on paper. This seems like the "Hello World" of cryptography, which is rarely available.
It's not really math that you want to do by hand. Quite tedious. The operations on points are only useful if the point lies on the curve, picking a random x and y won't do. All numbers are integers, points are a pair of integers (x, y).
To give you an idea of the math, here are my functions to add a point to itself or to another point:
Quote
def double(self, p):
assert p.y != 0
mo = self.curve.mo
l = mo.div(mo.add2(mo.mul(3, mo.pow2(p.x)), self.curve.a), mo.mul(2, p.y))
x3 = mo.sub(mo.pow2(l), mo.mul(2, p.x))
y3 = mo.sub(mo.mul(l, mo.sub(p.x, x3)), p.y)
return Point(x3, y3)
def add(self, p1, p2):
if p1 is None:
return p2
if p2 is None:
return p1
if p1 == p2:
return self.double(p1)
if p1.x == p2.x and (p1.y != p2.y or p1.y == 0):
return None
mo = self.curve.mo
l = mo.div(mo.sub(p2.y, p1.y), mo.sub(p2.x, p1.x))
x3 = mo.sub(mo.sub(mo.pow2(l), p1.x), p2.x)
y3 = mo.sub(mo.mul(l, mo.sub(p1.x, x3)), p1.y)
return Point(x3, y3)
assert p.y != 0
mo = self.curve.mo
l = mo.div(mo.add2(mo.mul(3, mo.pow2(p.x)), self.curve.a), mo.mul(2, p.y))
x3 = mo.sub(mo.pow2(l), mo.mul(2, p.x))
y3 = mo.sub(mo.mul(l, mo.sub(p.x, x3)), p.y)
return Point(x3, y3)
def add(self, p1, p2):
if p1 is None:
return p2
if p2 is None:
return p1
if p1 == p2:
return self.double(p1)
if p1.x == p2.x and (p1.y != p2.y or p1.y == 0):
return None
mo = self.curve.mo
l = mo.div(mo.sub(p2.y, p1.y), mo.sub(p2.x, p1.x))
x3 = mo.sub(mo.sub(mo.pow2(l), p1.x), p2.x)
y3 = mo.sub(mo.mul(l, mo.sub(p1.x, x3)), p1.y)
return Point(x3, y3)
All operations have to be done modulo the order of the field. Quite tedious by hand. I can post my whole code somewhere if you want it.
Bitcoins uses a specific ECC called secp256k1 you can Google that but to make your life easier the parameters used by the Bitcoin ECC are on page 15 of this document: http://www.secg.org/collateral/sec2_final.pdf
2.7.1 Recommended Parameters secp256k1
The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p;a;b;G;n;h) where the finite field Fp is defined by:
p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
The curve E: y^2 = x^3+ax+b over Fp is defined by:
a = 0
b = 7
The base point G in compressed form is:
G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
and in uncompressed form is:
G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
Finally the order n of G and the cofactor are:
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h = 01
2.7.1 Recommended Parameters secp256k1
The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p;a;b;G;n;h) where the finite field Fp is defined by:
p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
The curve E: y^2 = x^3+ax+b over Fp is defined by:
a = 0
b = 7
The base point G in compressed form is:
G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
and in uncompressed form is:
G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
Finally the order n of G and the cofactor are:
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h = 01
Google's not too helpful either. Going through some material I'm still at step one:
y^2 = x^3 + ax + b
x=4
a=5
b=20
y=11
Are x and y integers, real, or complex?
I didn't understand RSA nor D-H until I could draw them out on paper. This seems like the "Hello World" of cryptography, which is rarely available.
y^2 = x^3 + ax + b
x=4
a=5
b=20
y=11
Are x and y integers, real, or complex?
I didn't understand RSA nor D-H until I could draw them out on paper. This seems like the "Hello World" of cryptography, which is rarely available.
Edit: late nite, tired, stupid math mistake found, total BS deleted.
But you do bring up a good point. Even though you no longer have to worry about the private key ever even having been calculated anywhere by anyone, you do have to trust two entities to properly put the two key pairs on to the item and at least one entity to have properly added the two public keys together.
Please, I insist, can you come up with an example using small baby numbers?
I am not sure how to do that. The elliptic curve digital signature algorithm requires the use of some pre-defined constants, none of which are baby numbers.
Right, one would have to generate real small curve parameters, and openssl does not seem to be able to generate those. My python ECC prototype does not implement curve generation.
The math is correct. If p = the private key, P = the public key and G = the base point of the EC crypto system then P = p(G) where p(G) is the scalar multiplication of p selected from the finite field used to generate the elliptical group with the base point G from the group.
So for any two key pairs: P0/p0 and P1/p1
P0 = p0(G)
P1 = p1(G)
P0 + P1 = p0(G) + p1(G) = (p0 + p1)(G)
So you can take two public keys and apply the defined elliptical group addition and the resulting public key will have the corresponding private key which it the simple modulus addition of the two private keys.
So for any two key pairs: P0/p0 and P1/p1
P0 = p0(G)
P1 = p1(G)
P0 + P1 = p0(G) + p1(G) = (p0 + p1)(G)
So you can take two public keys and apply the defined elliptical group addition and the resulting public key will have the corresponding private key which it the simple modulus addition of the two private keys.
That should work, I had completely forgotten you could add two points together, I only remembered about scalar multiplication. A light bulb popped up when I remembered point doubling was the basis of the whole thing.
The two parties could generate a signature to each other to prove that they possess the secret part or use any secure channel.
Please, I insist, can you come up with an example using small baby numbers?
I am not sure how to do that. The elliptic curve digital signature algorithm requires the use of some pre-defined constants, none of which are baby numbers.
Also, I am not actually doing the math, I am using a library for it. But maybe I can add the following helpful information if you're following my example.
G is a constant that is already defined. It is a "point" (think of graphing), so G is actually a container for two numbers, it has an X and a Y component. I don't have to care what G is, and its X and Y are both some huge numbers I don't need to look at. (both numbers are between 2254 and 2256).
Multiplying a "point" by a "number" yields another "point". To get the public key, I take my private key (which is a number), and multiply them by G (which is a point), resulting in another "point". The multiplying is actually a complicated operation that I know nothing about, all I know is that I put in a "point" and a "number", and out comes a "point".
I can add two "points" together, and out comes another "point". It is not as simple as X=X1+X2 and Y=Y1+Y2, but rather, it is some sort of math I can just forget about and consider to be complete magic. All I care is that I can add two "points" together, and get another "point".
Multiplying two private keys together is easy, they are just regular numbers. But a private key isn't allowed to be bigger than the number N (another constant defined by elliptic curve, but this is a regular number slightly smaller than 2256, not a point), so if the result is bigger than N, I need to divide the result by N and keep only the remainder, so the result remains under N. (that's why I am doing Mod() in my code).
None of the examples given by anyone here assumes an understanding of the details of the magic math of how this point multiplication and point addition work. I don't understand it, and probably don't need to. But all of the examples DO assume an understanding that "point times number gives a point", and "point plus point equals another point". So when someone writes G * N1, it is assumed you know that G is a point, N1 is a regular number, and that the result of that multiplication is a point.
Jump to: