Elliptic curve math question - page 6.

netrin

sr. member

Activity: 322

Merit: 251

FirstBits: 168Bc

From another thread:

Quote from: netrin on November 29, 2011, 10:29:11 PM

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

Quote from: BurtW on November 29, 2011, 11:02:02 PM

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

vip

Activity: 1386

Merit: 1140

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

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.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

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?

netrin

sr. member

Activity: 322

Merit: 251

FirstBits: 168Bc

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.

jothan

full member

Activity: 184

Merit: 100

Feel the coffee, be the coffee.

Quote from: netrin on November 29, 2011, 10:35:30 PM

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

sr. member

Activity: 322

Merit: 251

FirstBits: 168Bc

Quote from: BurtW on November 29, 2011, 08:41:39 PM

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.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

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

casascius

vip

Activity: 1386

Merit: 1140

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

Quote from: SgtSpike on November 29, 2011, 07:38:00 PM

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.

BTCurious

hero member

Activity: 714

Merit: 504

^SEM img of Si wafer edge, scanned 2012-3-12.

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

Quote from: casascius on November 29, 2011, 07:34:33 PM

Quote from: jothan on November 29, 2011, 07:28:29 PM

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

Quote from: SgtSpike on November 29, 2011, 07:38:00 PM

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.

Quote from: SgtSpike on November 29, 2011, 07:38:00 PM

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

SgtSpike

legendary

Activity: 1400

Merit: 1005

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.

casascius

vip

Activity: 1386

Merit: 1140

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

Quote from: jothan on November 29, 2011, 07:28:29 PM

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.

jothan

full member

Activity: 184

Merit: 100

Feel the coffee, be the coffee.

Quote from: BTCurious on November 29, 2011, 06:27:12 PM

Quote from: jothan on November 29, 2011, 06:16:52 PM

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.

BTCurious

hero member

Activity: 714

Merit: 504

^SEM img of Si wafer edge, scanned 2012-3-12.

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.

Quote from: jothan on November 29, 2011, 06:16:52 PM

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

full member

Activity: 184

Merit: 100

Feel the coffee, be the coffee.

Quote from: jothan on November 29, 2011, 01:57:51 PM

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.

BTCurious

hero member

Activity: 714

Merit: 504

^SEM img of Si wafer edge, scanned 2012-3-12.

Quote from: ByteCoin on November 29, 2011, 01:37:46 PM

Quote from: BTCurious on November 29, 2011, 05:34:11 AM

Or with point addition (slightly different, but the security is the same):
The first party generates S1*G, and sends the X and Y to the second party. The second party adds to this point the point S2*G.
This means the public key is now S1*G + S2 * G = (S1+S2)*G, and the private key is (S1+S2). (Of course, everything modulo the curve order.)

This suffers from a security flaw that my scheme does not have. Whether it's exploitable depends on the details of the implementation.
Can anyone else see a problem with the above?

Could you maybe tell what the flaw is?.. Because as far as I know, there isn't one.
Note: Your way of phrasing your comment makes it sound like you're lecturing. Maybe this wasn't intended.

Quote from: jothan on November 29, 2011, 01:57:51 PM

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.

jothan

full member

Activity: 184

Merit: 100

Feel the coffee, be the coffee.

If the private keys are k1 and k2, and the base point is BP and the resulting public key is PK then:

PK = (BP * k1) *k2

With intermediate public keys:

PK1 = BP * k1
PK = PK1 * k2

Where * represents point multiplication.

Edit: in theory, the private key PK = k1 * k2 (mod n), (where * is scalar multiplication) but my ECC math is a bit rusty.

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.

I almost added ECC cryto to GnuTLS, I had a full python prototype, but someone beat me to it.

casascius

vip

Activity: 1386

Merit: 1140

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

Quote from: ByteCoin on November 29, 2011, 01:37:46 PM

This suffers from a security flaw that my scheme does not have. Whether it's exploitable depends on the details of the implementation.
Can anyone else see a problem with the above?

I would be eager to understand the flaw you say you see. I do not understand the math well enough to be qualified to see the flaw, I have to take someone's word for it.

ByteCoin

sr. member

Activity: 416

Merit: 277

Quote from: BTCurious on November 29, 2011, 05:34:11 AM

Or with point addition (slightly different, but the security is the same):
The first party generates S1*G, and sends the X and Y to the second party. The second party adds to this point the point S2*G.
This means the public key is now S1*G + S2 * G = (S1+S2)*G, and the private key is (S1+S2). (Of course, everything modulo the curve order.)

This suffers from a security flaw that my scheme does not have. Whether it's exploitable depends on the details of the implementation.
Can anyone else see a problem with the above?

ByteCoin

PS

Quote from: casascius on November 29, 2011, 09:51:45 AM

If this is all true, then it has big unrealized implications for ways wallets can be secured, far stronger than wallet encryption.

I think you're a bit hasty with the "unrealized"

casascius

vip

Activity: 1386

Merit: 1140

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

If this is all true, then it has big unrealized implications for ways wallets can be secured, far stronger than wallet encryption.

Imagine a web wallet service which created and managed s1 and which signed your transactions after verifying them via SMS. (s1 would be mailed to you encrypted, or on a CD-R, as a failsafe)

Imagine a paper wallet printer which took s1*G and printed you a 100% safe paper wallet because you generated s1*G from a passphrase (s1=sha256(passphrase)) using an app on your smartphone.

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: casascius on November 29, 2011, 09:13:21 AM

I was thinking of having S1 and S2 both on the physical piece.

Example, I make a high-denomination bar with two receptacles for keys. I load it with S1, and then ship the whole batch over to (e.g.) BitBills or MtGox and they use their own custom hologram and load it with S2. I would never bother with this for 1 BTC, just for 100BTC+.

A scam would require collusion between me and Bitbills/MtGox, so short of that, nobody but the person peeling the sticker can redeem the funds.

There is still the possibility that an exploit could be found against the sticker itself, but someone who acquired the bar directly from me or the other party wouldn't have to worry about that. Such a vulnerability would only benefit someone who bought a bar, did the exploit, and passed it off in an in-person transaction.

I like it in theory. One potential risk is Q/A. If either you or the countersigner "screw up" the funds are lost. One way to partially safeguard against that is extensive testing and possibly random audits by a 3rd party (someone you pay to randomly buy coins and verify them). You are also linking your rep to the actions of the countersigner. Their screw up is your screw up.

Still I could see a lot of potential counter-signers. If a large escrow service w/ significant reputation and assets ever rose up in the community their entire business is trust/rep. They would have a lot to lose by colluding. The same thing with any of the larger exchanges. Someone who sells high value products (like real gold bullion). Essentially anyone who is in the "trust business" and the public believes has a lot to lose by colluding.

Hopefully w/ automation the process could be streamlined and it be used for smaller denominations. Maybe I am just silly but I would love to see a 10 BTC note featuring dual keys on security paper, protected by independent custom engraved holograms. It is all about volume. If demand is 10x higher maybe someday volume would support that.

Topic: Elliptic curve math question - page 6. (Read 14040 times)