Elliptic curve math question

[jothan]

I do not think there is a way to do a "symmetric" or "simultaneous" way to do this. So Alice has to generate a normal key pair, and Bob needs to generate a key pair, using the key Alice provided as a base point.

Assuming the addition way of generating a joint key is secure (which it is, as far as I know), then you can do this symmetrically. Both generate a private key, calculate the public key, and then send the public key to each other. The public keys added are the total public key.
[/quote]

That is effectively the elliptic curve diffie-hellman key exchange. Not sure about the final addition. I would take the x coordinate of the final "public" key as a private key.

[1714026396]

1714026396

[1714026396]

1714026396

[BTCurious]

If you add Pub1 and Pub2 together, you get Pubsum. If you have Pubsum, you can get Pub1 by doing Pubsum - Pub2, or Pub2 by doing Pubsum - Pub1.

Neither of this gives you Priv1 or Priv2.

In the end, both parties have Pub1, Pub2, and Pubsum. Party one also has Priv1, whereas party two has Priv2. Neither has Privsum, because to calculate that you need Priv1 and Priv2. You can't get it from Pubsum, that's the entire concept of EC cryptography.

The math is rather simple, really. I very strongly doubt that I overlooked something.

I would take the x coordinate of the final "public" key as a private key.

What? That makes no sense. Then both parties know the private key, which makes this whole thing pointless.

[jothan]

I would take the x coordinate of the final "public" key as a private key.

What? That makes no sense. Then both parties know the private key, which makes this whole thing pointless.

They would only exchange the public part when they want to know the private value, but since they have nothing else to exchange, they could not really commit to a shared value (any party could change his keypair). I am indeed not a cryptographer. Forget that suggestion.

An option that does not rely on ECC is an all-or-nothing package.

https://secure.wikimedia.org/wikipedia/en/wiki/All-or-nothing_transform

The secret could not be revealed unless both parties use their share together.

My understanding of the problem is as follows:

• 1. Both parties have to somehow agree on a shared secret.
• 2. A single party should not be able to determine the secret using information available only to it.
• 3. The secret value must be used when manufacturing the coin.

To accomplish these goals, the following procedure could be used:

• 1. Generate the private value (randomly, could have a salt contributed by each party).
• 2. Mint the coin.
• 3. Wrap the secret in an all-or-nothing package and give a share to each party. Along with the share, give each party a hash of the secret, so they can make sure later on it is the secret they agreed on.
• 4. Make sure the original secret is destroyed.
• 5. Each party cannot reveal information about the key with their share alone.

Steps 1 through 3 would be conducted conjointly.

[casascius]

What? That makes no sense. Then both parties know the private key, which makes this whole thing pointless.

He's talking about a diffie hellman key exchange.  In a diffie hellman key exchange, for example, you're trying to come up with a shared secret to secure an SSL connection, so in effect you're trying to get both sides to agree on a shared private key without an eavesdropper being able to figure out that key, even if they can intercept the whole exchange.  It's not related to Bitcoin or digital signatures, it just happens to have strikingly similar math.

[SgtSpike]

Just, make sure it's still simple for the end user to redeem them.  That's the key.  If I had to set up a python script in order to combine the two pieces of paper and get the final private key that has the coins, it would upset me.

Also, I really have no idea how this would work.  If neither of the entities involved ever sees the private key, how would you know what address to send the bitcoins to?  Serious question, this is just beyond me and my knowledge, but I'd like to learn more.

[BTCurious]

Note: I'll try to use public point instead of public key to avoid confusion.

What? That makes no sense. Then both parties know the private key, which makes this whole thing pointless.

He's talking about a diffie hellman key exchange.  In a diffie hellman key exchange, for example, you're trying to come up with a shared secret to secure an SSL connection, so in effect you're trying to get both sides to agree on a shared private key without an eavesdropper being able to figure out that key, even if they can intercept the whole exchange.  It's not related to Bitcoin or digital signatures, it just happens to have strikingly similar math.

Ah, okay. Then still you shouldn't take the X of the summed public point as a shared secret, since that can be calculated from the whole exchange (just add the public points going back and forth).

Just, make sure it's still simple for the end user to redeem them.  That's the key.  If I had to set up a python script in order to combine the two pieces of paper and get the final private key that has the coins, it would upset me.

That's a good point. What could maybe be done is both parties generating half of the private key. In effect party one generates Priv1, being 00000000000004389tnsreaip49 or something, and puts only the last part under the hologram, while the other party generates tnsuyraarstnhe189000000000000000000 and puts only the first part under there.
The user can then simply concatenate the parts. (This assumes Addition shared key, as I described. With multiplication it's harder.)
Note however that this is highly non-standard. The creators need to take the base 58 encoding into account when splitting the key into two. There would be no checksum (although the other proposals don't have a checksum either). Also, the security is halved: one of the parties would only have to bruteforce half of the length of the private key of the other party. This is still sufficient for quite some time.

Also, I really have no idea how this would work.  If neither of the entities involved ever sees the private key, how would you know what address to send the bitcoins to?  Serious question, this is just beyond me and my knowledge, but I'd like to learn more.

Basically, both sides make a mailbox with a lock and key. They keep the key to the mailbox hidden. Then they come together, and mathemagically merge the mailbox, so now there is one merged mailbox with 2 locks. You need both keys to open it.
Sorry for the horrible analogy, it's 2AM and I can't think of a better one. The key is obviously the private key. The mailbox is the public point, which is easily translated into a bitcoin address. You can't find out what the key is if you have only the mailbox.

You need the private key to "use" the money from a bitcoin address. For the "merged mailbox" address, you need both keys to use the money. But the second party doesn't have the first party's key, nor the other way around.

Then they tape the key to the mailbox under a holographic sticker.

Sorry, I'll go to sleep now

[casascius]

Just, make sure it's still simple for the end user to redeem them.  That's the key.  If I had to set up a python script in order to combine the two pieces of paper and get the final private key that has the coins, it would upset me.

Also, I really have no idea how this would work.  If neither of the entities involved ever sees the private key, how would you know what address to send the bitcoins to?  Serious question, this is just beyond me and my knowledge, but I'd like to learn more.

Ideally the user would simply need to enter two pieces of information instead of one.

Instead of entering a concealed private key, they'd enter a private key and a passphrase, printed in plain sight.

The bitcoin address is computed from the public key, not the private key, so getting the address should be easy.

[BurtW]

Seems pretty simple to me:

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

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

[netrin]

1) 2) 3) 4) 5) 6) 7) 8 ) 9) Two entities generate separate holograms and keys.

10) then adds the two public keys together, creating the final public key

...

Uh what? And where is the private key from which this added public key was generated?

Could someone show a mathematical proof of concept using 8 or fewer bit keys. I don't believe it is possible to generate a secret (an unknown) between two parties, then derive a public key from that which is unknown.

[jothan]

Uh what? And where is the private key from which this added public key was generated?

Could someone show a mathematical proof of concept using 8 or fewer bit keys. I don't believe it is possible to generate a secret between two parties, then derive a public key from that which is unknown.

Right, the secret has to be computed in order to derive information from it (the public key). So unless there is some ECC voodoo, I think you are perfectly right. Otherwise, both stakeholders have to "meet" to generate the key without seeing it and issuing key shares.

Public-key cryptography enables wonderful things like proving you possess a private key without revealing it, but I do not know if what we are trying to do breaks information theory.

[netrin]

I'd love to see a proof that it can be done (example) or a formal proof that it's impossible. I would have assumed Diffie-Hellman was impossible too before I studied it. Cryptography never ceases to amaze me. And if you clowns can pull this off, I'll eat my underwear.

[BurtW]

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.

Do you like ketchup/catsup (spelling looks funny) on you underwear?

This is not voodoo it is fairly simple finite field math and group theory.  Check the algebra above.  Do you see any mistakes?

[casascius]

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

The code:

Code:

            ECKeyPairGenerator gen = new ECKeyPairGenerator();
            var secureRandom = new SecureRandom();
            var ps = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");
            var ecParams = new ECDomainParameters(ps.Curve, ps.G, ps.N, ps.H);
            var keyGenParam = new ECKeyGenerationParameters(ecParams, secureRandom);
            gen.Init(keyGenParam);

            // Generate private key #1.

            AsymmetricCipherKeyPair kp1 = gen.GenerateKeyPair();

            ECPrivateKeyParameters priv1 = (ECPrivateKeyParameters)kp1.Private;

            byte[] hexpriv1 = priv1.D.ToByteArrayUnsigned();

            Debug.WriteLine("Private key 1 is " + Bitcoin.ByteArrayToString(hexpriv1));
            
            // Get the public key for #1 (multiplying it by constant G defined by secp256k1).
            ECPoint pub1 = ps.G.Multiply(priv1.D);

            // Generate private key #2.

            AsymmetricCipherKeyPair kp2 = gen.GenerateKeyPair();

            ECPrivateKeyParameters priv2 = (ECPrivateKeyParameters)kp2.Private;

            byte[] hexpriv2 = priv2.D.ToByteArrayUnsigned();

            Debug.WriteLine("Private key 2 is " + Bitcoin.ByteArrayToString(hexpriv2));

            // Get the public key for #2.
            ECPoint pub2 = ps.G.Multiply(priv2.D);

            // Add the two public keys together.

            ECPoint pubsum = pub1.Add(pub2);

            // Turn that into a Bitcoin address.
            byte[] pubbytes = Bitcoin.PubKeyToByteArray(pubsum);
            string pubhashsum = Bitcoin.PubHexToPubHash(pubbytes);
            string pubaddr = Bitcoin.PubHashToAddress(pubhashsum, "Bitcoin");
            Debug.WriteLine("Bitcoin address of summing public keys: " + pubaddr);

            // Combine the two private keys together.
            Org.BouncyCastle.Math.BigInteger privsum = priv1.D.Add(priv2.D).Mod(ps.N);
            
            // Turn the combined privkey into a pubkey...
            ECPoint pub12 = ps.G.Multiply(privsum);
            
            // ... then a Bitcoin address.
            pubbytes = Bitcoin.PubKeyToByteArray(pub12);
            pubhashsum = Bitcoin.PubHexToPubHash(pubbytes);
            pubaddr = Bitcoin.PubHashToAddress(pubhashsum, "Bitcoin");
            Debug.WriteLine("Bitcoin address of multiplying private keys: " + pubaddr);
            Debug.WriteLine("Combined private key: " + Bitcoin.ByteArrayToString(privsum.ToByteArrayUnsigned()));

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 multiplying 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 

* EDIT: my output says I am "multiplying private keys", but turns out I am actually adding them.

[netrin]

From another thread:

No. Then I wouldn't know [which entity] screwed me. At least I know where Mike C (Casc..us) lives.

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?

[casascius]

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 2²⁵⁴ and 2²⁵⁶).

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 2²⁵⁶, 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.

[jothan]

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.

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.

[jothan]

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.

[BurtW]

Edit:  late nite, tired, stupid math mistake found, total BS deleted.

[netrin]

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.

[BurtW]

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