Elliptic curve math question

[jothan]

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.

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.

[BurtW]

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.

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!

[casascius]

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 

[btc_artist]

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.

[netrin]

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)

[BurtW]

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

[BTCurious]

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

[DeathAndTaxes]

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

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)

[etotheipi]

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.0

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

[BurtW]

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

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)

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/10-introduction

[BurtW]

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:

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.

[BurtW]

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?

[DeathAndTaxes]

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:

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

[BurtW]

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

[BTCurious]

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.pdf
It 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]

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!

[btc_artist]

Here is some sample code I tried (C# using BouncyCastle).  Math works as advertised.

Anyone know of a library like BouncyCastle for PHP?

[BurtW]

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 non-existent 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 non-networked 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 pre-coordination 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 pre-coordination.

[BurtW]

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.

[Red Emerald]

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