Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: casascius on November 29, 2011, 12:55:49 AM

Title: Elliptic curve math question
Post by: casascius on November 29, 2011, 12:55:49 AM

As you guys know, I make Casascius Physical Bitcoins.

I had an idea that maybe you math wizards could either validate or debunk.

First of all, when I create a physical bitcoin, one must trust that I am not keeping the private key.

I am wondering if EC math allows for a bitcoin address to be constructed from two parties using EC addition. If it worked, it would allow physical bitcoins (or bills or whatever) that had two private key components, so both actors would have to collude to perform a scam. Basically they could be more trustworthy.

So basically here is what I am asking. Suppose I create an EC private key S1, and give the public key (X and Y) to the second party.

Some second party takes X and Y, and does EC addition to add some secret S2, that he independently generates, to X and Y, to create a new point (X1 and Y1).

We then compute a Bitcoin address from X1 and Y1.

My hope is that both secrets S1 and S2 would be needed to derive the actual private key needed to spend the funds. Given that, both me and the other party would create a physical token that would contain keys from both of us.

Would this work?

Title: Re: Elliptic curve math question
Post by: ByteCoin on November 29, 2011, 01:46:54 AM

Quote from: casascius on November 29, 2011, 12:55:49 AM

My hope is that both secrets S1 and S2 would be needed to derive the actual private key needed to spend the funds. Given that, both me and the other party would create a physical token that would contain keys from both of us.

Would this work?

Yes that works fine except instead of point addition, use point multiplication.

S1 and S2 are random numbers about the same size of the group order. Send the second party the coordinates of S1*G where G is the agreed "generator" point. The final public key is S2*(S1*G) and the private key is (S1 * S2) modulo the curve order.

ByteCoin

Title: Re: Elliptic curve math question
Post by: cbeast on November 29, 2011, 02:15:15 AM

Quote from: casascius on November 29, 2011, 12:55:49 AM

As you guys know, I make Casascius Physical Bitcoins.

Yes you did. They are lovely collectables and a proof of concept toward trading with Bitcoin offline. I'm not sure how math can solve a problem of trust except for the purchaser. If we can't trust the artist, then it takes away from the intrinsic value of the art.

Maybe I don't understand the problem, but if you want to take away our trust of you, then just have the purchaser send you a public key and an encrypted private key.

Title: Re: Elliptic curve math question
Post by: casascius on November 29, 2011, 02:41:24 AM

Quote from: cbeast on November 29, 2011, 02:15:15 AM

Maybe I don't understand the problem, but if you want to take away our trust of you, then just have the purchaser send you a public key and an encrypted private key.

I don't think it's a matter of taking away trust, I just feel I can offer a better product if it permits its buyer to put more "trust in numbers" and require less trust in the manufacturer.

For example, we've got robkohr on another thread learning the best way to create his own bitcoin bills. How sweet a product he would have, if his bills had two holograms on them, each one coming from a different party. A built-in "check and balance" if you will.

I don't think anyone seriously thinks I will burn them on a 1 BTC coin, especially knowing that I'm charging 1.80 for the coin, and would be drying up a pretty sweet opportunity to sell them at an 80% markup by burning a few people. When I start cranking out 100 BTC gold bars, people start wanting to be a little bit more cautious, and rightfully so, no matter who I am.

On the other hand, if it's possible to produce bars where no single party has the full private key, it's possible to produce higher-denomination bars with better assurance to the buyer that they are the only one with access to their funds. Why not a 1000 BTC bar? It would keep the premium low, and would appeal to the non-technically-oriented buyer. Same thing would go for a paper savings wallet.

Unlike a 1 BTC coin, a bar also has enough surface area to hold multiple hologram stickers and multiple private keys.

I suppose I could just as easily create bars with nonstandard "two party" scripts that require two separate private keys to redeem, it would just add complexity to the redemption process as well as the production process (e.g. I would have to find a reliable miner who would accept these transactions into the block chain). All the better if the magic can just be hidden in the math I suppose.

Title: Re: Elliptic curve math question
Post by: DeathAndTaxes on November 29, 2011, 02:50:09 AM

Quote from: cbeast on November 29, 2011, 02:15:15 AM

Quote from: casascius on November 29, 2011, 12:55:49 AM

As you guys know, I make Casascius Physical Bitcoins.

That wouldn't help then second hand buyers couldn't trust the coin.

The goal would be to have 2 PARTIES that must collude in other to defraud buyers of the coins. That increases trust. Because either one can't defraud buyers without the other.

Title: Re: Elliptic curve math question
Post by: cbeast on November 29, 2011, 03:13:13 AM

Quote from: DeathAndTaxes on November 29, 2011, 02:50:09 AM

2 PARTIES that must collude in other to defraud buyers

That NEVER happens. heh.

Title: Re: Elliptic curve math question
Post by: DeathAndTaxes on November 29, 2011, 03:17:34 AM

Quote from: cbeast on November 29, 2011, 03:13:13 AM

Quote from: DeathAndTaxes on November 29, 2011, 02:50:09 AM

2 PARTIES that must collude in other to defraud buyers

That NEVER happens. heh.

Of course it can happen but it obviously isn't easier than 1 party working by itself to defraud the buyer.

For example say Gavin, casascius, and Mt. Gox each had to collude together to misaproriate funds from the private key. If you trust even 1 of the 3 parties you are ensured that even if the other 2 parties wanted to steal your funds they can't. Now if you don't trust all 3 parties well there is no increased protection but even still it isn't worse than a single party having access to the private key.

If the all of the parties are trustworthy and have something to lose it reduces the likelihood that collusion will happen.

Title: Re: Elliptic curve math question
Post by: fivebells on November 29, 2011, 03:33:43 AM

I believe there's a javascript address generator which you could include inthe ordering process. The webpage would send you only the data necessary to construct the coin, and give the user the full address info.

Obviates the trust issue completely, but inevitably some users would fail to save this data and lose the coins.

Title: Re: Elliptic curve math question
Post by: dree12 on November 29, 2011, 03:53:56 AM

Quote from: fivebells on November 29, 2011, 03:33:43 AM

The issue is that then the coins are no longer reusable and become average tokens.

Title: Re: Elliptic curve math question
Post by: fivebells on November 29, 2011, 09:47:54 AM

Sorry, I don't follow. Can you elaborate, please?

Edit: Oh, do you mean the coin has no resale value because the purchaser is not supposed to know what's under the hologram sticker? I guess that's a concern. Still, if we're talking about 1000BTC transactions, I wouldn't be trusting the integrity of the transaction to the integrity of a sticker anyway.

Title: Re: Elliptic curve math question
Post by: Mike Hearn on November 29, 2011, 10:11:41 AM

This sounds a lot like threshold cryptography, which is extensively studied. For example see this paper (https://docs.google.com/viewer?a=v&q=cache:-6Mi_6Eh8f4J:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.67.9913%26rep%3Drep1%26type%3Dpdf+&hl=en&gl=us&pid=bl&srcid=ADGEESgVj41EbpOZ3Gz-1ieBali84ojcn5AAVJoFG0TkNrRF0PkWg04Nxd9UYmIiVBH0NYo1tKfE-n-Dj_A7v1wIymEt5ICIqn_PUmExhpwhkyXB_U_zjeIs_ji6-7MPxibILVBDL1YL&sig=AHIEtbTQ8hsXTfqSKIbUII7Gj64azo_A1A) which covers threshold ECDSA, ie, can a group of players sign a message such that if some players become unresponsive they are kicked out - you need a "threshold of players" hence the name.

If you look at that paper, the part that's relevant is the "ECVSS without a dealer" section. Some older threshold DSA schemes required the key to be created and split by a trusted dealer. Newer schemes can do without that. So you'd adopt the verifiable secret sharing scheme but ignore the threshold signing.

Title: Re: Elliptic curve math question
Post by: BTCurious on November 29, 2011, 10:34:11 AM

Yes, it is possible. Either with ByteCoin's suggestion:

Quote from: ByteCoin on November 29, 2011, 01:46:54 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.)

Quote from: DeathAndTaxes on November 29, 2011, 02:50:09 AM

Quote from: cbeast on November 29, 2011, 02:15:15 AM

Maybe I don't understand the problem, but if you want to take away our trust of you, then just have the purchaser send you a public key and an encrypted private key.

That wouldn't help then second hand buyers couldn't trust the coin.

Actually, they could, if the hologram is intact. Since under the hologram S2 is stored, the first buyer can't have redeemed the coins unless the hologram is broken. (Assuming safe holograms here.)
You, as a second hand buyer, of course have to trust the first buyer to give you the correct S1. But since the knowledge of S1 an sich is useless to the first buyer, there is no gain for them in scamming you. Unless they don't like you.

Quote from: Mike Hearn on November 29, 2011, 10:11:41 AM

The "simple" case discussed up till now where all the keys involved need to be known is rather trivial, and is not threshold signing. That said, threshold signing may be useful, since invariably one of the parties is going to lose his key, and you don't want the money to be gone then.

Title: Re: Elliptic curve math question
Post by: casascius on November 29, 2011, 02:13:21 PM

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.

Title: Re: Elliptic curve math question
Post by: BTCurious on November 29, 2011, 02:18:41 PM

Yes, this would work. You have to make sure the other party knows which public key goes with which gold bar though, so make sure your communication is clear on that.

For the record: Either of you can load the bitcoins onto the address. If you (casascius) want to do it, the other party needs to tell you the address(es).

Title: Re: Elliptic curve math question
Post by: DeathAndTaxes on November 29, 2011, 02:45:10 PM

Quote from: casascius on November 29, 2011, 02:13:21 PM

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.

Title: Re: Elliptic curve math question
Post by: casascius on November 29, 2011, 02:51:45 PM

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.

Title: Re: Elliptic curve math question
Post by: ByteCoin on November 29, 2011, 06:37:46 PM

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

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, 02:51:45 PM

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"

Title: Re: Elliptic curve math question
Post by: casascius on November 29, 2011, 06:52:02 PM

Quote from: ByteCoin on November 29, 2011, 06: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.

Title: Re: Elliptic curve math question
Post by: jothan on November 29, 2011, 06:57:51 PM

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.

Title: Re: Elliptic curve math question
Post by: BTCurious on November 29, 2011, 07:56:54 PM

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

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

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, 06: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.

Title: Re: Elliptic curve math question
Post by: jothan on November 29, 2011, 11:16:52 PM

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

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.

Title: Re: Elliptic curve math question
Post by: BTCurious on November 29, 2011, 11:27:12 PM

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, 11: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.

Title: Re: Elliptic curve math question
Post by: jothan on November 30, 2011, 12:28:29 AM

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

Quote from: jothan on November 29, 2011, 11: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.

Title: Re: Elliptic curve math question
Post by: casascius on November 30, 2011, 12:34:33 AM

Quote from: jothan on November 30, 2011, 12:28:29 AM

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.

Title: Re: Elliptic curve math question
Post by: SgtSpike on November 30, 2011, 12:38:00 AM

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.

Title: Re: Elliptic curve math question
Post by: BTCurious on November 30, 2011, 12:54:11 AM

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

Quote from: casascius on November 30, 2011, 12:34:33 AM

Quote from: jothan on November 30, 2011, 12:28:29 AM

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

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 30, 2011, 12:38:00 AM

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 30, 2011, 12:38:00 AM

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

Title: Re: Elliptic curve math question
Post by: casascius on November 30, 2011, 12:54:17 AM

Quote from: SgtSpike on November 30, 2011, 12:38:00 AM

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.

Title: Re: Elliptic curve math question
Post by: BurtW on November 30, 2011, 01:41:39 AM

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

Title: Re: Elliptic curve math question
Post by: netrin on November 30, 2011, 03:35:30 AM

Quote from: bwagner on November 30, 2011, 01:41:39 AM

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.

Title: Re: Elliptic curve math question
Post by: jothan on November 30, 2011, 03:49:54 AM

Quote from: netrin on November 30, 2011, 03:35:30 AM

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.

Title: Re: Elliptic curve math question
Post by: netrin on November 30, 2011, 03:56:23 AM

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.

Title: Re: Elliptic curve math question
Post by: BurtW on November 30, 2011, 04:02:02 AM

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?

Title: Re: Elliptic curve math question
Post by: casascius on November 30, 2011, 04:03:45 AM

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.

Title: Re: Elliptic curve math question
Post by: netrin on November 30, 2011, 04:08:02 AM

From another thread:

Quote from: netrin on November 30, 2011, 03:29:11 AM

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

Quote from: bwagner on November 30, 2011, 04:02:02 AM

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?

Title: Re: Elliptic curve math question
Post by: casascius on November 30, 2011, 04:09:28 AM

Quote from: netrin on November 30, 2011, 04:08:02 AM

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.

Title: Re: Elliptic curve math question
Post by: jothan on November 30, 2011, 04:09:36 AM

Quote from: bwagner on November 30, 2011, 04:02:02 AM

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.

Title: Re: Elliptic curve math question
Post by: jothan on November 30, 2011, 04:13:58 AM

Quote from: casascius on November 30, 2011, 04:09:28 AM

Quote from: netrin on November 30, 2011, 04:08:02 AM

Quote from: bwagner on November 30, 2011, 04:02:02 AM

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.

Title: Re: Elliptic curve math question
Post by: BurtW on November 30, 2011, 04:27:47 AM

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

Title: Re: Elliptic curve math question
Post by: netrin on November 30, 2011, 04:33:43 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 D-H until I could draw them out on paper. This seems like the "Hello World" of cryptography, which is rarely available.

Title: Re: Elliptic curve math question
Post by: BurtW on November 30, 2011, 04:47:35 AM

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

Title: Re: Elliptic curve math question
Post by: jothan on November 30, 2011, 04:50:37 AM

Quote from: netrin on November 30, 2011, 04:33:43 AM

It's not really math that you want to do by hand. Quite tedious. The operations on points are only useful if the point lies on the curve, picking a random x and y won't do. All numbers are integers, points are a pair of integers (x, y).

To give you an idea of the math, here are my functions to add a point to itself or to another point:

Quote

def double(self, p):
assert p.y != 0
mo = self.curve.mo

l = mo.div(mo.add2(mo.mul(3, mo.pow2(p.x)), self.curve.a), mo.mul(2, p.y))

x3 = mo.sub(mo.pow2(l), mo.mul(2, p.x))
y3 = mo.sub(mo.mul(l, mo.sub(p.x, x3)), p.y)

return Point(x3, y3)

def add(self, p1, p2):
if p1 is None:
return p2
if p2 is None:
return p1

if p1 == p2:
return self.double(p1)

if p1.x == p2.x and (p1.y != p2.y or p1.y == 0):
return None

mo = self.curve.mo

l = mo.div(mo.sub(p2.y, p1.y), mo.sub(p2.x, p1.x))
x3 = mo.sub(mo.sub(mo.pow2(l), p1.x), p2.x)
y3 = mo.sub(mo.mul(l, mo.sub(p1.x, x3)), p1.y)

return Point(x3, y3)

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.

Title: Re: Elliptic curve math question
Post by: BurtW on November 30, 2011, 04:57:40 AM

Quote from: netrin on November 30, 2011, 04:33:43 AM

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!

Title: Re: Elliptic curve math question
Post by: casascius on November 30, 2011, 05:19:13 AM

Quote from: bwagner on November 30, 2011, 04:27:47 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.

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

Title: Re: Elliptic curve math question
Post by: btc_artist on 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.

Title: Re: Elliptic curve math question
Post by: netrin on November 30, 2011, 05:49:55 AM

Quote from: jothan on November 30, 2011, 04:50:37 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(x-X)-y (all ops modulo mo)

Title: Re: Elliptic curve math question
Post by: BurtW on 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/31-example-of-an-elliptic-curve-group-over-fp

Title: Re: Elliptic curve math question
Post by: BTCurious on 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/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

Title: Re: Elliptic curve math question
Post by: DeathAndTaxes on November 30, 2011, 01:42:28 PM

Quote from: BTCurious on November 30, 2011, 09:42:16 AM

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)

Title: Re: Elliptic curve math question
Post by: etotheipi on 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.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

Title: Re: Elliptic curve math question
Post by: BurtW on November 30, 2011, 02:41:04 PM

Quote from: DeathAndTaxes on November 30, 2011, 01:42:28 PM

Quote from: BTCurious on November 30, 2011, 09:42:16 AM

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

Title: Re: Elliptic curve math question
Post by: BurtW on 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:

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.

Title: Re: Elliptic curve math question
Post by: BurtW on 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?

Title: Re: Elliptic curve math question
Post by: DeathAndTaxes on November 30, 2011, 03:34:39 PM

Quote from: bwagner on 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:

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

Title: Re: Elliptic curve math question
Post by: BurtW on 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 (https://bitcointalk.org/index.php?topic=29416.0)

Title: Re: Elliptic curve math question
Post by: BTCurious on November 30, 2011, 04:06:27 PM

Quote from: DeathAndTaxes on November 30, 2011, 01:42:28 PM

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.

Title: Re: Elliptic curve math question
Post by: BurtW on 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!

Title: Re: Elliptic curve math question
Post by: btc_artist on November 30, 2011, 04:30:35 PM

Quote from: casascius on November 30, 2011, 04:03:45 AM

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

Anyone know of a library like BouncyCastle for PHP?

Title: Re: Elliptic curve math question
Post by: BurtW on November 30, 2011, 09:53:28 PM

Quote from: DeathAndTaxes on November 30, 2011, 09:33:59 PM

Quote from: bwagner on November 30, 2011, 09:15:54 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 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.

Title: Re: Elliptic curve math question
Post by: BurtW on November 30, 2011, 09:54:05 PM

Quote from: bwagner on November 30, 2011, 09:48:03 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.

Title: Re: Elliptic curve math question
Post by: Red Emerald on November 30, 2011, 10:25:04 PM

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

Title: Re: Elliptic curve math question
Post by: mndrix on December 01, 2011, 12:50:38 AM

The above discussion suggests a technique for two-party escrow without transaction scripts.

Bob wants to sell Alice goods for Bitcoin payment.
Alice generates key pair (a,A) and sends A to Bob.
Bob generates key pair (b,B) and sends B to Alice.
Alice sends payment to the address corresponding to A+B. At this point, neither Alice nor Bob can spend the funds.
Bob verifies payment was sent to address A+B and ships the goods to Alice.

If Alice receives the goods as expected, she sends 'a' to Bob. He uses the private key a+b to sweep funds to his own address. If Alice never receives the goods, she withholds a and the funds are permanently lost. If Bob wants to refund the payment, he sends 'b' to Alice and she uses the private key a+b to sweep funds to her own address.

If the transaction goes well and all messages are public, third parties can verify that Alice fulfilled her part of the deal. This could form an part of a p2p exchange with partially-provable reputations.

Title: Re: Elliptic curve math question
Post by: DeathAndTaxes on December 01, 2011, 05:33:08 AM

mndrix I like it. Clever use of partial keys.

Title: Re: Elliptic curve math question
Post by: BTCurious on December 01, 2011, 07:09:04 AM

Yeah, that would work pretty well, and can actually be done right now.
With the new changes (BIP0011) it will also be possible to include a 3rd party, who can give the coins to either A or B in a dispute.

Quote from: mndrix on December 01, 2011, 12:50:38 AM

partially-provable reputations

When coin-picking is implemented in most wallets, reputations can be proven fully, by sending from address X, where address X is well-known as being a reliable trader. Alternatively, during negotiations, one can just sign a message with his well known address' key, and the counterparty can verify that that's actually this guy. This can be done right now with 0.5 I think.

Title: Re: Elliptic curve math question
Post by: mndrix on December 01, 2011, 05:22:41 PM

Quote from: mndrix on December 01, 2011, 12:50:38 AM

partially-provable reputations.

I originally meant that observers have no way to verify that Bob sent the goods. However, I realized last night that Alice publishing 'a' implies that she received the goods and therefore that Bob sent them. If Bob's goods happened to be reversible, such as a PayPal payment, he could chargeback later, so I suppose it's still only partially provable in that case.

As BTCurious mentions, a signature mechanism is necessary to make sure the Alice and Bob in the transaction you watched are the same Alice and Bob you think they are.

Title: Re: Elliptic curve math question
Post by: Red Emerald on December 01, 2011, 05:55:13 PM

Quote from: mndrix on December 01, 2011, 12:50:38 AM

The above discussion suggests a technique for two-party escrow without transaction scripts.

Bob wants to sell Alice goods for Bitcoin payment.
Alice generates key pair (a,A) and sends A to Bob.
Bob generates key pair (b,B) and sends B to Alice.
Alice sends payment to the address corresponding to A+B. At this point, neither Alice nor Bob can spend the funds.
Bob verifies payment was sent to address A+B and ships the goods to Alice.

I like it! Reading stuff like this makes me want to delve deep into EC math, but I just don't have the time.

The only problem is if Alice receives the payment and doesn't transmit a, then Alice has the goods and Bob has no funds. Alice doesn't have the funds either, at least. I guess if you want that level of assurance, you can use scripts.

Title: Re: Elliptic curve math question
Post by: DeathAndTaxes on December 01, 2011, 06:11:10 PM

Quote from: Red Emerald on December 01, 2011, 05:55:13 PM

The only problem is if Alice receives the payment and doesn't transmit a, then Alice has the goods and Bob has no funds. Alice doesn't have the funds either, at least. I guess if you want that level of assurance, you can use scripts.

And damaged rep and others can verify she hasn't paid. There is no way to ensure a thief can't kill a payment without a human third party arbitrator. Still I think that is somewhat unlikely. Alice has the goods she gains nothing by witholding payment however she risks damaging her rep so it is a net loss to withhold payment. If you are that concerned about that event then a true escrow w/ arbitrator is the only secure method but even that isn't a guarantee the human making the decision could either side against you or could be in collusion w/ Alice. :-\

Title: Re: Elliptic curve math question
Post by: PrintCoins on December 01, 2011, 11:00:12 PM

Can anyone write up a simple python module for handling this?

I am guessing it would have two methods:
def combinePublic(pubA, pubB):
//Person A creates a public address and private key. He gives the public address (pubA) to Person B
//Person B creates a public address (pubB) and private key
do some magic and return pubC

def combinePriv(privA, privB):
//do basically the same with private keys (this should create the priv key for pubC)
do some magic and return privC

It might be something that can all be done with one method. I am willing to admit I am way out of my depth though.

It would be great if Mike and I could basically co-sign each other's money this way. It would add to the cost, but the user would have little doubt that either of us have the private key. The double hologram would also mean that both would need to replicated to produce a useful counterfeit.

Title: Re: Elliptic curve math question
Post by: BurtW on December 01, 2011, 11:12:25 PM

Mike knows exactly how to do this - he did it in the example above to prove the concept.

So you two should get together!

Title: Re: Elliptic curve math question
Post by: casascius on December 01, 2011, 11:17:42 PM

Quote from: robkohr on December 01, 2011, 11:00:12 PM

It would be great if Mike and I could basically co-sign each other's money this way. It would add to the cost, but the user would have little doubt that either of us have the private key. The double hologram would also mean that both would need to replicated to produce a useful counterfeit.

Rob, have you called or e-mailed the hologram guys yet? Each of my last two orders took 5-6 weeks. I would be willing to co-sign.

I am asking them to quote me on some rectangular holograms that would be perfect for bills. Regardless of what I do, you could probably do them as well.

By the way, they of course aren't the only provider of holograms in town. But the hologram adhesive (that shows honeycombs if you sneeze on it wrong) from these guys is so good, I don't dare go anywhere else. Many of the other samples I have played with are too easy to peel off intact.

Title: Re: Elliptic curve math question
Post by: PrintCoins on December 02, 2011, 12:19:34 AM

Quote from: casascius on December 01, 2011, 11:17:42 PM

Quote from: robkohr on December 01, 2011, 11:00:12 PM

Yep, and I can see why you charge the price you do for your coins. The holograms are more expensive than the metal by far. Since I have to do a double sided my bills may out cost you coins. I might have to consider some super adhesive cheap alternative backing to prevent scanning through the reverse side of the bill. Otherwise I might just have to switch to coins or plastic.

Edit : Maybe Gorilla Tape. It would be a pain to work with though. I can see my wife coming into the garage while I am working and me being on the floor with Ron Paul bills stuck all over me.

Title: Re: Elliptic curve math question
Post by: casascius on December 02, 2011, 01:03:32 AM

Holo's are cheap if you order a ton of them, it's the setup that costs so much.

Title: Re: Elliptic curve math question
Post by: netrin on December 02, 2011, 01:40:29 AM

Hey guys, thanks for all the input, particularly the http://www.certicom.com links. I intend to come up with a bunch of baby-step examples, perhaps over the weekend, that hopefully my mother could follow.

I once studied abstract algebra, so this isn't totally foreign to me, but I'd prefer to read (python) code rather than latek math notation, if anyone wants to donate some code to the cause.

Title: Re: Elliptic curve math question
Post by: netrin on December 02, 2011, 01:48:27 AM

BTW, I had said earlier that I wouldn't trust this system, because then I'd have two entities who I'd have to trust not to screw up. However, this additive stuff should make it at least possible to verify each private/public pair - who screwed up. Out of curiosity, is it possible to combine many more pairs?

(privA + privB) + ... + (privY + privZ) --> (pubA + pubB) + ... + (pubY + pubZ)

And does doing so weaken the key strength? Is each component (A,B,C...Z) easier to crack than the additive result, or do they all contain just as many bits and are just as seemingly random?

Title: Re: Elliptic curve math question
Post by: DeathAndTaxes on December 02, 2011, 02:35:28 AM

Quote from: netrin on December 02, 2011, 01:48:27 AM

Each private key can contains as many bits as the unified private key. The entropy of each private key depends on the method used by the creator. Even if one key is weaker due to flawed implementation it is still stronger than a single key because you will need all the sub-keys to construct the unified private key.

Title: Re: Elliptic curve math question
Post by: BurtW on December 02, 2011, 02:44:24 AM

Just to answer your specific question about multiple key pairs. You can add together as many public keys as you want to and the corresponding private key will be the sum of all the private keys. I (and some others) are trying to come up with a way to use this property in a little side project we are working on. In our project, depending on how popular it gets, we may be adding together hundreds or even thousands of public keys and the private key would then be the sum of all the corresponding hundreds (or thousands) of private keys.

Title: Re: Elliptic curve math question
Post by: netrin on December 02, 2011, 03:36:46 AM

Was anything secret that might be easier to compute with multiple public addresses, for example this 'G' value that is common among all key calculations?

* or was the G (base point) necessarily public anyway?

Title: Re: Elliptic curve math question
Post by: BurtW on December 02, 2011, 03:46:21 AM

G is a public published value.

In compressed form it is:

G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

and in uncompressed form it is:

G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Each private key is secret but even if you have all but one of them you cannot calculate the last one you need to get to the final public key.

Title: Re: Elliptic curve math question
Post by: casascius on December 02, 2011, 05:48:29 AM

Quote from: bwagner on December 02, 2011, 03:46:21 AM

G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Bitcoin only uses the uncompressed form. It's worth pointing out that this number is actually a structure, because it represents a "point", not just a scalar value.

A "point" has an X and Y coordinate. The first byte, 04, means this uncompressed format, and can be considered a constant. The next 32 bytes are X, and the next 32 bytes are Y.

Constant = 04
X = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Y = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Title: Re: Elliptic curve math question
Post by: ByteCoin on December 02, 2011, 06:35:27 AM

Quote from: casascius on December 02, 2011, 05:48:29 AM

X = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Y = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

so in decimal

x=55066263022277343669578718895168534326250603453777594175500187360389116729240
y=32670510020758816978083085130507043184471273380659243275938904335757337482424
p=115792089237316195423570985008687907853269984665640564039457584007908834671663

y^2 = x^3 + 7 - p * 1442042049659660869506300006036683750029629333882594701370927246876626245108435 922902327776681700708714008192087431130951749952236093997894375239788520937

The equation of the curve is y^2=x^3+7 mod p

ByteCoin

Title: Re: Elliptic curve math question
Post by: BurtW on December 02, 2011, 06:58:18 AM

What I think would be interesting is to verify:

y^2 mod p = ( x^3 + 7 ) mod p for G:

1) Calculate y^2 mod p, get answer

2) Calculate ( x^3 + 7 ) mod p, get answer

I believe that answer from 1) should equal answer from 2)

Title: Re: Elliptic curve math question
Post by: Meni Rosenfeld on December 02, 2011, 07:28:42 AM

Quote from: bwagner on December 02, 2011, 06:58:18 AM

Yeah, this pans out.

Code:

y^2 = 1067362225016502275772194909503713869376985974142797512091458491530306631211206623652669436957676354343630306950631573032330832513385319878364322508915776
y^2 mod p       = 32748224938747404814623910738487752935528512903530129802856995983256684603122
x^3 + 7 = 166977061698153803977729810299616665720111080589888563362701662779994291659333477169534477572723704285154275133397811778652651956291844366636068483203593094558427352525126936769086968791554813695916119291254705683450242657305024007
(x^3 + 7) mod p = 32748224938747404814623910738487752935528512903530129802856995983256684603122

Title: Re: Elliptic curve math question
Post by: Red Emerald on December 02, 2011, 07:34:07 AM

You guys are making my head hurt. It sounds cool though

Title: Re: Elliptic curve math question
Post by: BurtW on December 02, 2011, 07:35:04 AM

See, math can be fun :D

Title: Re: Elliptic curve math question
Post by: PrintCoins on December 02, 2011, 06:55:37 PM

Current Bounty On Javascript Code For This:

RobKohr - 2BTC

Edit: It must be complete and easy to use. Must be able to do the public key combination as well as the private key combination (for end users).

Title: Re: Elliptic curve math question
Post by: casascius on December 02, 2011, 07:29:39 PM

Quote from: robkohr on December 02, 2011, 06:55:37 PM

What RobKohr wants, I think, is a version of Bitaddress.org that also gives him access to the 65 public key bytes (0x04 + x[32] + y[32]), potentially in place of the Bitcoin address, potentially on the QR code as well. Am I right Rob?

In other words, just a checkbox that exposes ECKey.PubKey in hex (if I recall correctly), rather than going on to compute the full bitcoin address.

Title: Re: Elliptic curve math question
Post by: Mike Hearn on December 04, 2011, 05:52:39 PM

I think you guys should seriously review the literature on this before (re)inventing more EC math. I'm not saying your workings are incorrect, just that there is already a lot of research into what you can do with ECC and a citation is more useful than a reinvention.

I for one would be hesitant to implement any cryptographic technique that wasn't published in the relevant journals. Cryptography, especially this type, is subtle and subject to unintuitive failure modes. A paper published via the usual mechanisms carries a lot more weight than a forum post. This is also one reason why using scripts can be more attractive than other techniques - it's less efficient but much easier to convince yourself of its correctness.

For example, see: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1562272

Title: Re: Elliptic curve math question
Post by: casascius on December 04, 2011, 06:37:00 PM

Quote from: Mike Hearn on December 04, 2011, 05:52:39 PM

I agree with you, though I will point out that the purpose of the math in question is to come up with a methodology that reduces the possibility that one person - the person who manufactured a physical bitcoin (me, for example), would be able to steal it by keeping the private key. In other words, reducing the risk profile from "can be stolen by one person" down to "can be stolen only by collusion by two (or more) specific parties".

Sure, there may be some theoretical exploit that causes this scheme to fail, but if only one person in the whole world is in a position to exploit it (me), and finding the exploit requires very rare expertise found only among mathematicians (definitely not me), it's probably not a big deal. A random attacker has nothing to work with - no private keys, no public keys - because all of these keys are going into a physical object. At best, he can attack an object he has or had in his possession. For every person who can attack the object mathematically, there's probably 1000 who can attack it physically, or can counterfeit it... that is to say, I think the community, in a sense, is already prepared for the possibility that they might one day hear they need to be cautious in some way about receiving physical coins from strangers.

Though I won't turn down the citation if someone can provide one (I cannot). I would not be opposed to more formal and rigorous analysis of the math, especially for the benefit of the bitcoin community at a future time when there are numerous producers of physical bitcoins, not just me.

Title: Re: Elliptic curve math question
Post by: BurtW on December 04, 2011, 10:04:05 PM

Quote from: Mike Hearn on December 04, 2011, 05:52:39 PM

Could you please read post #32 on this thread and see if you can see anything missing there - besides a citation, which I am working on. I think the proof is almost self evident. Since the two key system proposed is a natural group theory extension of the already accepted one key system it can only be broken to the extent the one key system can be broken.

Title: Re: Elliptic curve math question
Post by: mndrix on December 05, 2011, 05:07:11 PM

Quote from: Mike Hearn on December 04, 2011, 05:52:39 PM

That's sound advice. I've not been able to find relevant citations. I'd actually be a bit surprised if anyone has studied techniques for multiple parties to agree on a private key that none of them can use. Is there a standard name for such protocols? As I understand it, neither verifiable secret sharing nor threshold signatures are what we want.

Title: Re: Elliptic curve math question
Post by: BurtW on December 05, 2011, 05:14:11 PM

I have also not been able to find a citation for this exact thing (yet) I think mainly because it is such a basic fundamental algebraic concept. I expect no one is going to get a PHD (and therefore have published a paper) from such a simple concept.

Title: Re: Elliptic curve math question
Post by: PrintCoins on December 05, 2011, 07:54:59 PM

Quote from: casascius on December 02, 2011, 07:29:39 PM

Quote from: robkohr on December 02, 2011, 06:55:37 PM

I am not sure I understood your interpretation of my question.

Given Priv1, and Pub1, from me, and let say Priv2 and Pub2 from you, a function would be:
function makeCombinedPublicKey(Pub1, Pub2){... return Pub3}

and there would be
function makeCombinedPrivateKey(Priv1, Priv2){... return Priv3}
This would be for the consumer to use to get after removing protective seals on both private keys. Priv3 would be the private key for Pub3.

The generation of Pub1, Priv1, Pub2, Priv2 could be provided by some other utility such as bitaddress, and could be independent from this pair of functions. Though if it was bundled up in a nice little module that included a function like:
function generateKeyPair(optional_seed){return [private, public]}
that would be a good inclusion.

I could see using this in the pdf printing script I created and adding something where the script will just print the additional keys on the bill (perhaps being smart enough to use a scan of an uncut sheet to extract the public keys for input and then printing to that sheet).

Title: Re: Elliptic curve math question
Post by: BurtW on December 05, 2011, 08:32:49 PM

What Mike is getting at is that if you go to bitaddress.org today you get a private key and a public key address.

Currently there is no way to get the actual public key printed out at that web site.

In order to do the operation (public key 3) = (public key 1) + (public key 2) we need the actual public keys not the public key addresses.

The public key address (called the Bitcoin address on the paper wallets from bitaddress.org) is a number that is calculated from the public key. But you cannot calculate the public key from the public key address.

Also since public keys are very long compared to even public key addresses we would need the public key in a QR form so we don't have to type in the whole thing. Here is an example public key to show you what I mean:

Code:

G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

This also shows you why we use public key addresses instead of public keys because they are so much shorter than the actual public keys.

Title: Re: Elliptic curve math question
Post by: PrintCoins on December 05, 2011, 09:52:21 PM

Quote from: bwagner on December 05, 2011, 08:32:49 PM

Code:

G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

This also shows you why we use public key addresses instead of public keys because they are so much shorter than the actual public keys.

I believe you have just enlightened me to another layer of bitcoin-y-ness. So there is a think called the public key address which is not the same as the public address. And it is not something that is easily reversible to?

Ok, now it is time for me to actually read the initial paper. It is obvious I am more clueless than I should be.

Title: Re: Elliptic curve math question
Post by: btc_artist on December 05, 2011, 09:55:26 PM

https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses This explains how the bitcoin address is created from the public key.

Title: Re: Elliptic curve math question
Post by: BurtW on December 05, 2011, 10:16:56 PM

Quote

I believe you have just enlightened me to another layer of bitcoin-y-ness. So there is a thingk called the public key address which is not the same as the public key ~~address~~. And it is not something that is easily reversible to?

Right, and it designed to be impossible to go directly from the public key address back to the original public key (the public key address is a fancy sha256 hash of the public key - see the above mentioned paper for the details).

Title: Re: Elliptic curve math question
Post by: marcus_of_augustus on December 07, 2011, 12:50:23 PM

hmmmmm.

Title: Re: Elliptic curve math question
Post by: etotheipi on December 07, 2011, 02:33:26 PM

Finally had some time to look at this, and I'm not impressed with the talk of point-addition: as ByteCoin suggested, there is not a "robust" way to use point addition to secure anything. Point addition on a given curve (where everyone knows the parameters, like secp256k1) is easily invertible. Point subtraction is only slightly slower than point addition.

Additionally, it is very unwise to rely on any method that requires keeping public keys secret. This goes against the grain of cryptography, and creates a headache for those of us client developers that justifiably leave public keys unencrypted in wallets. You can argue that some special CONOPS (concept of operations) designed for this application will help, but it's just not good cryptography. Don't do it.

Going back to casascius' original idea: you CAN use Diffie-Hellman shared-secret techniques to SECURELY create a shared key. If Alice has (a, a*G) and Bob has (b, b*G), then by publicly broadcasting their public keys, Alice and Bob can both compute the elliptic curve point (a*b*G) and no one else can. This gives us two options (in general):

(1) (A and B) Alice and Bob create the point (a*b*G) from each others' public keys, and use the result as a new public key. They calculate the address hash and put it in the TxOut field of a transaction. Then when the money needs to be spent, Alice or Bob can send the other one their private key, and then the combined private key can be computed and used to sign the inputs. This is perfect for casascius application, but not many other applications (see below).

(2) (A or B) Alice and Bob create the public key as above, and then use the x component (or combination of x and y components) to derive a new private key. This private key can be converted to public-key/address that can be included on a transaction, and then Alice or Bob can sign for that transaction. This isn't relevant for casascius' application, but it is cryptographically secure, and has plenty of other useful applications.

The problem with (1), in general, is that it's a terrible idea to create a crypto process that relies on exchange of private keys. While a wallet/app will attempt to use a different private key for every transaction, there's a possibility that things go wrong -- someone else sends that private key money, a bug in their client (or someone manipulates their client) to reuse private keys, multiple clients using the same wallet don't realize the key has been used, etc. And a problem like this would go unnoticed by the user until someone has already exploited it. This is in the same vein as requiring public keys to be kept private -- private keys should never have to be made public.

Except for casascius' application: his CONOPS already involves exchanging private keys and his software is specialized to do this correctly. For general multi-signature protocols over the internet with untrusted parties (1) should never be used. (2) could be used cryptographically-responsibly to replace 1-of-2 multi-sig transaction types, but that's for some other application.

P.S. -- I am very interested in ways that an (A and B) transaction could be created using "responsible" cryptography, but so far no one has suggested a way. Such as a way for Alice to only compute the combined private key with her own private key and Bob's signature (or vice versa)...

Title: Re: Elliptic curve math question
Post by: BurtW on December 07, 2011, 03:21:33 PM

Quote from: etotheipi on December 07, 2011, 02:33:26 PM

Point addition on a given curve (where everyone knows the parameters, like secp256k1) is easily invertible. Point subtraction is only slightly slower than point addition.

Agree.

Quote

Additionally, it is very unwise to rely on any method that requires keeping public keys secret.

Agree. However, there is nothing in the proposed two key system that requires that any public key be kept secret. All three public keys a*G, b*G and (a+b)*G are, at all times, publicly available keys. Knowing all three public keys give you no new information. Anyone can use point addition or point subtraction to calculate any one of the three from the other two but that is pointless (grin) since all three are public keys anyway.

Quote

Going back to casascius' original idea: you CAN use Diffie-Hellman shared-secret techniques to SECURELY create a shared key. If Alice has (a, a*G) and Bob has (b, b*G), then by publicly broadcasting their public keys, Alice and Bob can both compute the elliptic curve point (a*b*G) and no one else can.

Agreed. This would work. And you have just created a shared key that only Alice and Bob can know, yes. But since this shared key is going to be a public key why does it need to be a shared secret?

Quote

(1) (A and B) Alice and Bob create the point (a*b*G) from each others' public keys, and use the result as a new public key. They calculate the address hash and put it in the TxOut field of a transaction. Then when the money needs to be spent, Alice or Bob can send the other one their private key, and then the combined private key can be computed and used to sign the inputs. This is perfect for casascius application, but not many other applications (see below).

Agreed. This would work. However the proposed point addition system will also work just as well.

Quote

(2) (A or B) Alice and Bob create the public key as above, and then use the x component (or combination of x and y components) to derive a new private key. This private key can be converted to public-key/address that can be included on a transaction, and then Alice or Bob can sign for that transaction. This isn't relevant for casascius' application, but it is cryptographically secure, and has plenty of other useful applications.

True.

Quote

The problem with (1), in general, is that it's a terrible idea to create a crypto process that relies on exchange of private keys. While a wallet/app will attempt to use a different private key for every transaction, there's a possibility that things go wrong -- someone else sends that private key money, a bug in their client (or someone manipulates their client) to reuse private keys, multiple clients using the same wallet don't realize the key has been used, etc. And a problem like this would go unnoticed by the user until someone has already exploited it.

Agree with the general statement. However what is being discussed here assumes the key pair is going to be used one time for a specific purpose.

Quote

This is in the same vein as requiring public keys to be kept private -- private keys should never have to be made public.

There is nothing in the proposed point addition scenario that requires any of the points (pubic keys) to be held as secrets. Where did you get that idea?

Quote

Except for casascius' application: his CONOPS already involves exchanging private keys and his software is specialized to do this correctly. For general multi-signature protocols over the internet with untrusted parties (1) should never be used. (2) could be used cryptographically-responsibly to replace 1-of-2 multi-sig transaction types, but that's for some other application.

I agree that your proposal would also work for the coin application. But since your only objection to the proposed point addition method is based on the incorrect assumption that it requires that one or more of the public keys be kept secret do you now agree that the proposed point addition system will also work?

Quote

P.S. -- I am very interested in ways that an (A and B) transaction could be created using "responsible" cryptography, but so far no one has suggested a way. Such as a way for Alice to only compute the combined private key with her own private key and Bob's signature (or vice versa)...

Me too.

Title: Re: Elliptic curve math question
Post by: mndrix on December 07, 2011, 03:36:24 PM

Quote from: etotheipi on December 07, 2011, 02:33:26 PM

The problem with (1), in general, is that it's a terrible idea to create a crypto process that relies on exchange of private keys.

Quote

there's a possibility that things go wrong -- someone else sends that private key money, a bug in their client (or someone manipulates their client) to reuse private keys, multiple clients using the same wallet don't realize the key has been used, etc.

All cryptographic protocols can be ruined by things going wrong. A bad Bitcoin implementation might accidentally broadcast private keys on IRC. That doesn't mean the Bitcoin protocol is flawed.

Title: Re: Elliptic curve math question
Post by: BurtW on December 07, 2011, 03:56:04 PM

In summary there are two possible ways this can be done. In both systems you need both private keys to spend the money. In one system you would add the two private keys together to get the private key needed to spend/transfer the funds, in the second system you would muliply the two keys together in order to get the final private key needed to spend the funds. I believe either system will work and that the addition is slightly easier.

Title: Re: Elliptic curve math question
Post by: etotheipi on December 07, 2011, 05:49:15 PM

Quote from: bwagner on December 07, 2011, 03:21:33 PM

That's embarassing, I rushed through the thread and totally misunderstood the proposed solution. My apologies.

You're right it doesn't require keeping public keys secret, but it doesn't change my objection to it. As Mike Hearn suggested, it's a mistake to not use "established" techniques for any cryptographic protocol. Is point addition an established technique for a secure system (I'm not familiar with it, but maybe it is)? Just because an insecurity isn't obvious doesn't mean it's not there. There's all sorts of creative math that has been used to break crypto schemes, and the only way to "be sure" is to use established techniques.

And the fact is there is already an established scheme: which is using point multiplication as described multiple times before. Diffie-Hellman shared-secret techniques have been established as secure, and if you have ECC-math module on your system, you can use it just as easily. There's no reason to risk using point-addition when there's a widely-accepted alternative that gets you the same thing. (In fact, the point multiplication adds a little bit of extra anonymity, since the tx with point addition can be identified with anyone having both public keys. The multiplication tx can only be identified by someone with one of the private keys.)

Quote from: mndrix on December 07, 2011, 03:36:24 PM

Publishing private keys or other secrets after a transaction is a standard part of some sound cryptographic protocols. For example, Off-the-record messaging protocol publishes secret MAC keys as soon as those keys have expired (allowing deniable authentication). Similarly, a Bitcoin contract for trading across chains publishes a secret to finalize the transaction.
...
All cryptographic protocols can be ruined by things going wrong. A bad Bitcoin implementation might accidentally broadcast private keys on IRC. That doesn't mean the Bitcoin protocol is flawed.

The examples you speak of are protocols where your keys are expected to be revealed at the end of the exchange. But, up to this point in Bitcoin, people reuse private keys all the time with the assumption they remain private. Removing that assumption changes the security model for application developers and users. As an app developer, I don't want to have to deal with simultaneously maintaining a set of private keys are okay to reuse, and a set of keys that are a guaranteed fail if I re-use them. Sure, it can be done, but it's extra complexity in security-sensitive software.

Title: Re: Elliptic curve math question
Post by: BurtW on December 07, 2011, 05:59:50 PM

After thinking about it a bit there is a pretty big difference between the two systems when extrapolated to 3 or more parties.

The point addition system can be done in parallel.

Assume five parties all publish their public keys to each other (and the world). These five public keys are a*G, b*G, c*G, d*G and e*G where a, b, c, d, and e are the five private keys.
Now all five parties immediately have eveything they need to calculate the shared public key = a*G + b*G + c*G + d*G + e*G = (a + b + c + d + e)*G

In the other proposed system the calculation of the shared public key cannot be done in parallel, each party must calculate the next point from the previous point

Code:

A sends a*G to B         B calculates b*a*G
B sends b*a*G to C       C calculates c*b*a*G
C sends c*b*a*G to D     D calculates d*c*b*a*G
D sends d*c*b*a*G to E   E calculates e*d*c*b*a*G

This is perfect for where this is what you want: for each party to have to send the result of their calculation on to the next party and for the final party to be the only one to know the final public key. However for our use case we do not need or want this.

I am still looking for a citation regarding the use of point addition. Will let you know when I find it.

Title: Re: Elliptic curve math question
Post by: BurtW on December 07, 2011, 06:09:34 PM

Quote

As an app developer, I don't want to have to deal with simultaneously maintaining a set of private keys are okay to reuse, and a set of keys that are a guaranteed fail if I re-use them. Sure, it can be done, but it's extra complexity in security-sensitive software

Mt. Gox already does this. If you import a private key into your Mt. Gox account they immediately move all BTC from it and will never re-use it. However, they do have a nice sweep feature. If you turn it on then they will automatically sweep any coins sent to that address off it into your account. So if the private key has been or ever is compromised and someone is foolish enough to send it BTC then they get automatically claimed.

I have imported many private keys into my Mt. Gox account - especially every publicly available private key found on this forum and on the wiki - in the hopes that someone will send it some coins on a whim, then they will be mine all mine <insert maniacal laughter here>

Title: Re: Elliptic curve math question
Post by: Meni Rosenfeld on December 07, 2011, 06:17:40 PM

Quote from: etotheipi on December 07, 2011, 05:49:15 PM

Is point addition an established technique for a secure system (I'm not familiar with it, but maybe it is)? Just because an insecurity isn't obvious doesn't mean it's not there.

It seems trivial to prove that if ECDSA is secure then so is the addition scheme (though of course this has to be vetted by someone who is actually experienced with these things): Suppose that given A and (A+B)*G we can deduce A+B. Now let's say we have some arbitrary public key C*G. Generate a random A. C = A + (C-A) so by assumption we can find C.

Quote from: etotheipi on December 07, 2011, 05:49:15 PM

And the fact is there is already an established scheme

There is an established scheme for an application which is not identical to this. There's no reason we shouldn't make use of known primitives to create new applications. Again, I agree that the uninitiated could miss something even when the recombination seems trivial - so we should ask someone about it, but not wait for someone to write a paper about such trivialities.

Quote from: etotheipi on December 07, 2011, 02:33:26 PM

This is in the works (assuming you meant "compute the combined signature").

Title: Re: Elliptic curve math question
Post by: BurtW on December 07, 2011, 06:42:28 PM

Quote

This is basically what I was thinking and was going to write up basically the same proof but then thought - well that would just be bwagner again saying that I think it is secure which I have already done numerous times.

What we need is a known "expert" to say it.

Title: Re: Elliptic curve math question
Post by: etotheipi on December 07, 2011, 07:34:02 PM

I suppose I could've gotten out pencil and paper and done exactly what you did, instead of ranting about it. Your proof looks valid, using a typical proving method: if this was insecure, so would ECDSA, so it must be at least as secure as other ECDSA operations.

But I still don't know why you wouldn't use the DHSS method, since it is established, and you don't need convince someone "I'm pretty sure this proof is correct." Anyone can look up DHSS and see that it is an accepted method for doing what you are trying to do. It's no harder to apply than point addition and even has a little bit of extra anonymity.

-Eto

Title: Re: Elliptic curve math question
Post by: pc on December 07, 2011, 08:14:24 PM

I think the question is the reversibility of EC addition. And I know almost nothing about EC crypto, so perhaps the terms are what's confusing me, but if Alice and Bob each have a private key (PrivA and PrivB), tell each other their public key (PubA and PubB, and they create a combined public key (PubA+PubB) and send coins to it, is it possible for Bob to subtract Alice's public key from Bob's to get the difference, and then apply that some difference to his private key to get Alice's private key and take the coins without Alice's consent? (PrivA=(PrivB-(PubB-PubA)) or something?)

It seems that all of EC crypto is based on many of these operations being irreversible, so I guess I'm just asking if the point addition being talked about fits in that category.

Title: Re: Elliptic curve math question
Post by: BurtW on December 07, 2011, 08:23:49 PM

Quote

is it possible for Bob to subtract Alice's public key from Bob's to get the difference, and then apply that some difference to his private key to get Alice's private key and take the coins without Alice's consent? (PrivA=(PrivB-(PubB-PubA)) or something?)

No. You cannot mix public key addition/subtraction and private key addition/subtraction, they are two totally different things. Public key addition is the defined addition operation on the eliptical group - it is a fairly complex operation and unlike regular addition. You are adding two points from the elliptical group to get a third point. Private key addition is the simple modulo addition defined for the finite field. Apples and oranges.

Title: Re: Elliptic curve math question
Post by: mndrix on December 08, 2011, 12:00:28 AM

Quote from: etotheipi on December 07, 2011, 07:34:02 PM

But I still don't know why you wouldn't use the DHSS method...

For casascius' original question, I agree that Diffie-Hellman is the best solution. However, some of the other protocols described above need onlookers to calculate the same public key as Alice and Bob without knowing either party's private key. As far as I can tell, DH won't work for those protocols, but EC addition will.

Title: Re: Elliptic curve math question
Post by: BurtW on December 08, 2011, 08:05:52 AM

After much thought I agree that we should abandon the point addition system and use the serial point creation system instead. Here is why:

This is the proposed point addition system as used by Mike, who is assumed to be trustworthy
The customer creates public key C and private key c where C = c*G
Mike creates public key M and private key m where M = m*G
The customer sends public key C to Mike and Mike creates the final public key F = C + M = c*G + m*G = (c + m)*G
Mike transfers the BTC to the key pair F = (c + m)*G and ships the product to the customer along with the public key M and the private key m (under the hologram)
The customer can verify that C + M = F and also verify that the BTC are stored on F, all is well.
When the time comes the customer can claim the BTC using c + m

But what about Mike’s evil twin brother Ekim?
Again, the customer creates public key C and private key c where C = c*G
Ekim creates public key E and private key e where E = e*G
The customer sends public key C to Ekim but instead of creating the correct public key F = C + E, Ekim instead creates a pseudo public key P where C + P = E, in other words P = E - C
Ekim now transfers the BTC to the key pair he created E = e*G and ships the product to the customer along with the fake public key P and nothing under the hologram
Since the pseudo public key P was created as P = E – C the customer will be able to verify that C + P = E and also be able to verify that the BTC are stored on E, so the customer thinks that all is well!
When the time comes the customer looks under the hologram and discovers there is no key (or a bogus key) and they have been ripped off. Ekim can move the BTC from E at any time since he knows e.

Now let’s try the same scenario using the serial point creation system
The customer creates public key C and private key c where C = c*G
Mike creates public key M and private key m where M = m*G
The customer sends public key C to Mike and Mike creates the final public key F = m*C = m*c*G
Mike transfers the BTC to the key pair F = m*c*G and ships the product to the customer along with the public key M and the private key m (under the hologram)
The customer can verify that F = c*M = c*m*G and also verify that the BTC are stored on F, all is well.
When the time comes the customer can claim the BTC using c*m

But what about Mike’s evil twin brother Ekim?
Again, the customer creates public key C and private key c where C = c*G
Ekim creates public key E and private key e where E = e*G
The customer sends public key C to Ekim. Now in order to pull the same scam Ekim would want to be able to pass off his personal key pair E = e*G as the final keys and load the BTC on to E for later recovery.
In order to do that he needs to have the pseudo public key necessary to fool the customer.
The customer is going to attempt to verify the pseudo key P by calculating E = c*P
But there is no way that Ekim can calculate P because Ekim does not know c.

Ekim will have to turn over a new leaf and be more like his brother Mike.

EDIT: Note that this is not a cryptographic weakness in the point addition method - it is a fraud vector that does not exist in the point "multiplication" system.

Title: Re: Elliptic curve math question
Post by: Meni Rosenfeld on December 08, 2011, 08:32:27 AM

Quote from: bwagner on December 08, 2011, 08:05:52 AM

This is the proposed point addition system as used by Mike, who is assumed to be trustworthy
The customer creates public key C and private key c where C = c*G
Mike creates public key M and private key m where M = m*G
The customer sends public key C to Mike and Mike creates the final public key F = C + M = c*G + m*G = (c + m)*G
Mike transfers the BTC to the key pair F = (c + m)*G and ships the product to the customer along with the public key M and the private key m (under the hologram)
The customer can verify that C + M = F and also verify that the BTC are stored on F, all is well.
When the time comes the customer can claim the BTC using c + m

I don't think that's the proposal. I thought the point with casascius coins is that you can pay with them, with the active ingredient being that the private key is hidden but with Mike's seal that it is valid. If redeeming a coin requires the private key of the customer who originally ordered the coin, he can't pay with it to another party.

My interpretation of the proposal is: Mike generates a key m and has a business partner who generates a key b. The partner creates a "mini-coin" with b hidden and B exposed, so that b can only be found if the minicoin is evidently opened. Mike embeds the minicoin in his own coin with m hidden and M+B exposed. To redeem the coin it needs to be opened completely to expose m and b and thus m+b. This way, the bitcoins can only be stolen if either:

1. Mike and the partner collude, which is assumed to be unlikely, or
2. Mike opens minicoins before embedding them and scrapes b, which can be detected by sampling Mike's coins and verifying that the minicoin is intact.

Note that sampling needs to be done anyway to verify that coins indeed contain the promised private key. Mike will also need to sample the minicoins of his partner before he commits to embedding them in a coin sealed by himself.

This can be extended to multiple partners each submitting their own minicoin, all of them being embedded in a single coin by Mike.

Title: Re: Elliptic curve math question
Post by: BurtW on December 08, 2011, 08:39:48 AM

Yes, there are two proposals floating around. In one scenario the customer generates a key pair so the customer is certain that they, and only they, have half the puzzle. The other proposal is for Mike to do half and some other trusted entity to do the other half and the customer does nothing until redemption time. Both are being discussed and I think both are valid use cases.

The fraud vector outlined above applies to both use cases and the use of the serial key creation sytem instead of the point addition system eliminates this fraud vector in both use cases.

Title: Re: Elliptic curve math question
Post by: etotheipi on December 08, 2011, 02:08:06 PM

Wow, nice work bwagner! It sounds like the flaw has to do with the fact that point addition is easily invertible, allowing someone to "invert" your public key before using it. They would have to have your private key (or solve a discrete log problem) in order to do the same thing in DHSS.

Title: Re: Elliptic curve math question
Post by: BurtW on December 08, 2011, 02:25:52 PM

Yes, and I have to admit that my thought process was inspired by the following question so some of the credit goes to pc for asking the "stupid" question. I answered the question but it got me to thinking...

Quote from: pc on December 07, 2011, 08:14:24 PM

Title: Re: Elliptic curve math question
Post by: casascius on December 08, 2011, 05:11:48 PM

I don't have any significant efforts invested into addition that cannot be easily switched to multiplication, so this should not be a problem with respect to my coins.

I expect that to create two-part physical bitcoins, I would simply take private key circles out of my secure repurposed Nutella jar, use the series 1 hologram which covers it entirely, calculate the composite bitcoin address, and laser the resulting address on the outside of the hologram. That's time consuming, but not unreasonable for the gold coin since there won't be that many of them.

Title: Re: Elliptic curve math question
Post by: BurtW on December 08, 2011, 06:24:11 PM

EDIT: I guess this is an answer to a question that disappeared while I was answering it! O well I will leave it here for anyone who has the same question.

The argument is subtle. First we are not talkikng about Mike, we are talking about Ekim - and he is out to rip off the customer (being Mike's evil twin brother).

On purpose he is funding the key E (which he totally controls with the private key e). He is planning to take the BTC back at a later time.

The plan is to lie and tell the customer that his key E is the final combined key.

To do this he calculates P = E - C and lies and tells the customer that P is his public part of the two part key chain being used to secure the BTC. Liar - he does not even know the private key for P (and can't)!

So everything is set up. Ekim ships the item to the customer claiming that P is his public key and claims to have put the corresponding private key p under the hologram. He has not since he does not even know p. He also lies and says that E is the final combined key.

The customer gets the item and the two public keys P and E. The customer is sophisticated and careful so they check everything out.

First they check to make sure the BTC they ordered are on the combined key. He looks in the block chain for key E and yes the BTC are there.

Next he wants to make sure that the public keys add up so he calculated C + P and yes it does equal E!

So the customer is happy and thinks everything is ok - but it is not. Ekim controls the BTC and the customer has no way to get the BTC.

Title: Re: Elliptic curve math question
Post by: casascius on December 08, 2011, 07:10:07 PM

I deleted it because I realized I had misunderstood.

You are right.

Title: Re: Elliptic curve math question
Post by: mndrix on December 08, 2011, 07:21:07 PM

Quote from: bwagner on December 08, 2011, 08:05:52 AM

But what about Mike’s evil twin brother Ekim?
Again, the customer creates public key C and private key c where C = c*G
Ekim creates public key E and private key e where E = e*G
The customer sends public key C to Ekim but instead of creating the correct public key F = C + E, Ekim instead creates a pseudo public key P where C + P = E, in other words P = E - C
Ekim now transfers the BTC to the key pair he created E = e*G and ships the product to the customer along with the fake public key P and nothing under the hologram
Since the pseudo public key P was created as P = E – C the customer will be able to verify that C + P = E and also be able to verify that the BTC are stored on E, so the customer thinks that all is well!
When the time comes the customer looks under the hologram and discovers there is no key (or a bogus key) and they have been ripped off. Ekim can move the BTC from E at any time since he knows e.

Academic observation: In this scenario, the customer is safe if Ekim commits to E before C is revealed (by publishing a hash of E, for example).

Title: Re: Elliptic curve math question
Post by: BurtW on December 08, 2011, 07:52:59 PM

I did think of this and thought of it this way: If both parites send their public keys to each other at the start of the protocol and they "cross in the mail" then the system is secure because there is now agreement on which two keys are to be added together to create the final public key.

I guess there may be a way to ensure this "crossing in the mail" but what if Ekim is very clever and so on...

Title: Re: Elliptic curve math question
Post by: casascius on December 08, 2011, 08:15:44 PM

Quote from: bwagner on December 08, 2011, 07:52:59 PM

They can cross in the mail by the two sending each other the hashes of their pre-generated public keys, sharing them only after both have confirmed receipt of the hashes.

Title: Re: Elliptic curve math question
Post by: mndrix on December 08, 2011, 11:37:17 PM

Quote from: casascius on December 08, 2011, 08:15:44 PM

They can cross in the mail by the two sending each other the hashes of their pre-generated public keys, sharing them only after both have confirmed receipt of the hashes.

Yup. A slight optimization allows the first party that receives a public key hash to immediately respond with his own public key, without awaiting confirmation. Because publishing a public key is contingent on receiving a hash, it can be viewed as confirmation and commitment in one.

Title: Re: Elliptic curve math question
Post by: ByteCoin on December 09, 2011, 02:51:20 AM

The recently explained security flaw resulting from adding public key points to derive a common public key is the one I had in mind in my original post (https://bitcointalk.org/index.php?topic=53177.msg634403#msg634403).

A number of forum members seemed to have convinced themselves of the security of the scheme and I hope that this episode encourages people to be less confident and more cautious about "novel" cryptographic constructions.

I believe it's possible to recover the security of the scheme without resorting to a two-round system in which the hashes are published and then the public keys revealed. This is achieved as follows:

1) The participants publish the hashes (or equivalently addresses) of public keys for which signatures have been seen in the block chain.
2) The software scans the signatures in the block chain for the relevant public keys and the combined public key is formed by addition.

This scheme is secure against the attack outlined (in a somewhat garbled fashion) in this post (https://bitcointalk.org/index.php?topic=53177.msg643887#msg643887) because Ekim is unable to create signatures with the key he broadcasts (P in the post's terminology).

ByteCoin

Title: Re: Elliptic curve math question
Post by: Meni Rosenfeld on December 09, 2011, 05:31:36 AM

Quote from: ByteCoin on December 09, 2011, 02:51:20 AM

This isn't a problem with generating a public key from adding two other public keys, but rather with some specific applications. I for one thought we were talking about making casascius coins - if they're not manufactured according to spec all bets are off, which is why they need to be sampled anyway, which would detect attacks like the one described.

(I don't disagree with your main point though.)

Title: Re: Elliptic curve math question
Post by: casascius on December 09, 2011, 07:20:23 AM

Just thinking about the attack vector, realizing that E and C could be reversed. A customer could use the same scheme to acquire an intact Casascius coin with no funds, if I were to offer to have done a two-key coin, and had acquiesced to a request to provide my intended public key first. Having that happen would be non-amusing, so, I suppose I am appreciative to have been made aware of it before ever having produced any.

I suppose that if I offer a two-party key scheme, I might do well not only to use multiplication, but to insist on a mutual commitment of public keys via exchanging hashes first, so that neither party has the opportunity to base their public key on the one they received.

Title: Re: Elliptic curve math question
Post by: etotheipi on December 09, 2011, 08:41:34 PM

Quote from: casascius on December 09, 2011, 07:20:23 AM

I suppose that if I offer a two-party key scheme, I might do well not only to use multiplication, but to insist on a mutual commitment of public keys via exchanging hashes first, so that neither party has the opportunity to base their public key on the one they received.

It doesn't hurt, but I'm not sure how much it helps. The multiplication scheme (DHSS) is used all the time with with pre-published, persistent identities/keys on the internet, all the time. I think the point here, was, that DHSS is established and you can feel comfortable using it in the ways prescribed by NIST, etc (which doesn't recommend any precautions with respect to public key exchange). If someone was smart enough to find a mathematical hole in DHSS based on public key exchange, then they're smart enough to realize that there are much more profitable targets to be exploited around the globe than a $3,000 casascius gold bar...

Title: Re: Elliptic curve math question
Post by: casascius on January 02, 2012, 09:15:44 PM

OK, so random question... how do you multiply a point by a point?

I understand multiplying a point by a scalar value... but I have no concept of multiplying two points together, neither does BouncyCastle offer any function in its "point" class that multiplies the point by another point.

What am I misunderstanding? Thanks in advance.

Title: Re: Elliptic curve math question
Post by: BurtW on January 02, 2012, 09:18:02 PM

There is no defined multiply operation on the eliptical curve group (hence group).

Why are you trying to muliply points?

Title: Re: Elliptic curve math question
Post by: etotheipi on January 02, 2012, 09:23:27 PM

You can add points together--that is the core operations of ECC math. Scalar multiplication is just an extension of that. If you have point P, then 5*P is just P+P+P+P+P. There is no such thing as point-to-point mulitplication.

Title: Re: Elliptic curve math question
Post by: BurtW on January 02, 2012, 09:29:45 PM

Mike,

The two party scheme I think you are working on should be:

Code:

A has private key a and sends public key a*G to B [scalar mult]
B has private key b and calculates new public key b*(a*G) from public key a*G [scalar mult]

Ending private key is b*a (simple modulo multiplication)
  But not known to either A or B, only knowable by someone once they have both a and b
Ending public key is b*a*G

Title: Re: Elliptic curve math question
Post by: casascius on January 02, 2012, 09:35:00 PM

Quote from: bwagner on January 02, 2012, 09:29:45 PM

Mike,

The two party scheme I think you are working on should be:

Code:

A has private key a and sends public key a*G to B [scalar mult]
B has private key b and calculates new public key b*(a*G) from public key a*G [scalar mult]

Ending private key is b*a (simple modulo multiplication)
  But not known to either A or B, only knowable by someone once they have both a and b
Ending public key is b*a*G

This makes sense, and is what I was looking for. Thanks!

I wanted to experimentally create a service where I am "B" and mail out stickers to stick on paper wallets produced by (or printed from website) A. My sticker would have a second private key and the combined Bitcoin address.

Or perhaps even better, where I am "A", and someone uses a website to print their paper wallet "B", and sticks my stickers on their page. (That way, I'm not responsible for calculating the final Bitcoin address, which would be a potential scam vector.)

Title: Re: Elliptic curve math question
Post by: casascius on January 02, 2012, 09:44:07 PM

So here's how that might work.

I sell a "half paper wallet" on my website.
Each half paper wallet has 7 QR coded private keys, they are individual stickers. Each sticker has a short ID code (maybe 8 characters) that ensures they place the right sticker on the right place on their final paper wallet. The ID code is based on the hash of the pubkey, but isn't a bitcoin address (to avoid confusion).
The product also shows a URL, example, casascius.com/pw/9F281BCA398D.txt. There is one URL per sheet sold. This text file contains the pubkeys for all the privkeys on the page.
A service, conceptually similar to BitAddress.org, will http get that file (or offer a place to paste it, if network access is disallowed), and use the pubkeys to construct the paper wallet. Each address on the paper wallet will have a spot to place my stickers. It will recompute the same ID numbers from the pubkeys, so the user can assure themselves they are putting their stickers in the right place

The end result? Pretty much bulletproof paper wallet. Nobody can steal the funds! Not even if I decide to be a crook, or if they produce their paper wallet on a filthy rooted pwned machine.

Title: Re: Elliptic curve math question
Post by: koin on January 05, 2012, 09:36:46 PM

Quote from: casascius on January 02, 2012, 09:44:07 PM

This text file contains the pubkeys for all the privkeys on the page.

to make sure that i understand this better, please clarify this. re-running the bitaddress-like service against the same text file will create different bitcoin addresses, right? i.e., the output of the bitaddress-like service is non-deterministic?

Title: Re: Elliptic curve math question
Post by: pc on January 09, 2012, 02:07:17 AM

Quote from: casascius on January 02, 2012, 09:44:07 PM

The end result? Pretty much bulletproof paper wallet. Nobody can steal the funds! Not even if I decide to be a crook, or if they produce their paper wallet on a filthy rooted pwned machine.

Well, if it's really filthy rooted pwned, with an attack that is aware of bitcoins and how this system/site works, the malware could just replace the real pubkeys/addresses on the paper wallet that's being generated so that instead of corresponding to the combo of private keys, just corresponds to a private key the attacker controls. It'll stop a generic packet or key logger or the like, but if you really can't trust your computation device, then I don't see how you can trust that your output is right.

Title: Re: Elliptic curve math question
Post by: pointbiz on January 11, 2012, 04:06:54 AM

Quote from: pc on January 09, 2012, 02:07:17 AM

Quote from: casascius on January 02, 2012, 09:44:07 PM

The end result? Pretty much bulletproof paper wallet. Nobody can steal the funds! Not even if I decide to be a crook, or if they produce their paper wallet on a filthy rooted pwned machine.

We are discussing degrees of security or probability of encountering an attack. The easier an attack is the more likely it will occur.

Sorry... in other words Casascius is "raising the stakes".

To be properly paranoid you could take the list of public keys from Casascius along with the private keys you generated on the pwned machine using the bitaddress-like service and re-run them through the bitaddress-like service on a different computer to double check the calculation of the combined bitcoin address.

I think this novel idea can significantly increase the security of paper wallets against malware, especially once bitcoin goes mainstream.