jothan


November 30, 2011, 04:50:37 AM 

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 DH 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: 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)
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.

Bitcoin: the only currency you can store directly into your brain.
What this planet needs is a good 0.0005 BTC US nickel.







Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.



BurtW
Legendary
Offline
Activity: 1946
All paid signature campaigns should be banned.


November 30, 2011, 04:57:40 AM 

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 DH 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!

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



casascius
Mike Caldwell
VIP
Legendary
Offline
Activity: 1358
The Casascius 1oz 10BTC Silver Round (w/ Gold B)


November 30, 2011, 05:19:13 AM 

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. // 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: 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

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable. I never believe them. If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins. I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion. Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice. Don't keep coins online. Use paper or hardware wallets instead.



btc_artist


November 30, 2011, 05:35:38 AM 

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.

BTC: 1CDCLDBHbAzHyYUkk1wYHPYmrtDZNhk8zf LTC: LMS7SqZJnqzxo76iDSEua33WCyYZdjaQoE



netrin


November 30, 2011, 05:49:55 AM 

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(xX)y (all ops modulo mo)




BurtW
Legendary
Offline
Activity: 1946
All paid signature campaigns should be banned.


November 30, 2011, 06:08:41 AM 

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/31exampleofanellipticcurvegroupoverfp

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



BTCurious


November 30, 2011, 09:42:16 AM 

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/10introductionnetrin: 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 diffiehellman 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 diffiehellman 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




DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


November 30, 2011, 01:42:28 PM 

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/10introductionnetrin: 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 diffiehellman 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 diffiehellman 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%93HellmanThe question is what allows you to assert. ECC(private key 1 + private key 2) = (public key 1 + public key 2) We know these are true: ECC(private key 1) = public key 1 ECC(private key 2) = public key 2 But do we know (as in some whitepaper, mathematical proof, etc) that: ECC(private key 1 + private key 2) = (public key 1 + public key 2)




etotheipi


November 30, 2011, 02:28:32 PM 

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://bitcointalk.org/index.php?topic=23241.0The 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 privatekey exponents, and publickey 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




BurtW
Legendary
Offline
Activity: 1946
All paid signature campaigns should be banned.


November 30, 2011, 02:41:04 PM 

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/10introductionnetrin: 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 diffiehellman 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 diffiehellman 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%93HellmanThe question is what allows you to assert. ECC(private key 1 + private key 2) = (public key 1 + public key 2) We know these are true: ECC(private key 1) = public key 1 ECC(private key 2) = public key 2 But do we know (as in some whitepaper, mathematical proof, etc) that: ECC(private key 1 + private key 2) = (public key 1 + public key 2) Could you please go throught this tutorial  it does not take that long  and then see if you can see it: http://www.certicom.com/index.php/10introduction

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



BurtW
Legendary
Offline
Activity: 1946
All paid signature campaigns should be banned.


November 30, 2011, 02:44:21 PM 

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: 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 counterintuitive but it is true and it works. Don't know what else to say.

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



BurtW
Legendary
Offline
Activity: 1946
All paid signature campaigns should be banned.


November 30, 2011, 03:27:08 PM 

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?

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


November 30, 2011, 03:34:39 PM 

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: 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 counterintuitive 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 postorigination counterfeit risk but all currency carries that risk (just ask the Secret Service).




BurtW
Legendary
Offline
Activity: 1946
All paid signature campaigns should be banned.


November 30, 2011, 03:46:45 PM 

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://bitcointalk.org/index.php?topic=29416.0

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



BTCurious


November 30, 2011, 04:06:27 PM 

The question is what allows you to assert.
ECC(private key 1 + private key 2) = (public key 1 + public key 2)
We know these are true: ECC(private key 1) = public key 1 ECC(private key 2) = public key 2
But do we know (as in some whitepaper, mathematical proof, etc) that: ECC(private key 1 + private key 2) = (public key 1 + public key 2) I know you don't have this question anymore, but I would like to mention the standards document for EC cryptography: http://www.secg.org/collateral/sec1_final.pdfIt is written very understandably for a standards document. All the mathematical basics are in chapter 2. Ignore all paragraphs about F2m, bitcoin doesn't use that.




BurtW
Legendary
Offline
Activity: 1946
All paid signature campaigns should be banned.


November 30, 2011, 04:23:15 PM 

I can't believe that with all my yammerings all over this board that I have just now only cracked 200 posts. This makes me really appreciate the hard work and dedication of people like DeathAndTaxes who are over 2000!

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



btc_artist


November 30, 2011, 04:30:35 PM 

Here is some sample code I tried (C# using BouncyCastle). Math works as advertised.
Anyone know of a library like BouncyCastle for PHP?

BTC: 1CDCLDBHbAzHyYUkk1wYHPYmrtDZNhk8zf LTC: LMS7SqZJnqzxo76iDSEua33WCyYZdjaQoE



BurtW
Legendary
Offline
Activity: 1946
All paid signature campaigns should be banned.


November 30, 2011, 09:53:28 PM 

Here is my explaination from another thread:
1) Make the bar or paper bill with spots for two holograms and a final public key address 2) First party gets the item 3) Put the first private key in mini private key format under the first hologram 4) Put the firstbits of the public key address on the outside of the first hologram 5) Ship the item along with the actual public key to the second party 6) Second party puts the second hologram on the item 7) Second private key in mini private key format under the second hologram 8. Firstbits of the second public key address on the outside of the hologram 9) NOW the second party verifies the public key shipped with the item with the public key address on the first hologram 10) then adds the two public keys together, creating the final public key 11) From the final public key calculate the final public key address 12) This final public key adddress is etched/printed on the item. 13) The BTC funds are transmitted to the final public key address The bolded steps are incorrect. There is no address for the two partial keys. There is also no reason to record the two partial public keys because they can't be looked up. You can't get a firstbits of a nonexistent address. Remove/change steps 4, 8, 9 and it is a good summary. In the redeeming section for section 4 I would indicate you have multiple options a) use a website which supports dual private keys b) use a standalone client designed for loading dual private keys c) use a simple nonnetworked application which generates the single key from the dual private keys and use it anywhere a single private key can be used. As for what to put print on the hologram a) nothing b) some serial number which could be used to lookup the partial public key (not very useful) c) the combined public key (i.e. step 10). This would require some precoordination between two parties. A is the easiest. B isn't too tough but doesn't provide much value. C is the best but may requires some precoordination.

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



BurtW
Legendary
Offline
Activity: 1946
All paid signature campaigns should be banned.


November 30, 2011, 09:54:05 PM 

Sounds good. You are right about not being able to look up firstbits on a nonfunded account (what was I thinking?). That is why we have peer review, right?
1) Make the item with spots for two holograms and a final public key address 2) First party gets the item 3) Put the first private key in mini private key format under the first hologram 4) Ship the item along with the actual public key to the second party 5) Second party puts the second hologram on the item 6) Second private key in mini private key format under the second hologram 7) then adds the two public keys together, creating the final public key 9) From the final public key calculate the final public key address 10) This final public key adddress is etched/printed on the item somewhere, possibly on the hologram 11) The BTC funds are transmitted to the final public key address
At this point no one could possibly know the private key since it has never even been calculated.
To redeem:
1) Pull off both stickers 2) Get the two private keys 3) At a web site that supports the two key option, enter both private keys (Mt Gox, StrongCoin, etc. could be talked into supporting this option) 4) The web sites that support this option would then simply add the two private keys together 5) You now have the private key for the combined public key address etched/printed on the item 6) Redeem the BTC from the item
The other redemption options mentioned above are also possible.

Our family was terrorized by Homeland Security. Read all about it here: http://www.jmwagner.com/ and http://www.burtw.com/ Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!



Red Emerald


November 30, 2011, 10:25:04 PM 

This is interesting. Anything that reduces the amount of trust required is good IMO.




