Elliptic curve math question

[Meni Rosenfeld]

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)

Yeah, this pans out.

Code:

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

[1713957743]

1713957743

[1713957743]

1713957743

[1713957743]

1713957743

[1713957743]

1713957743

[Red Emerald]

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

[BurtW]

See, math can be fun 

[PrintCoins]

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

[casascius]

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

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.

[Mike Hearn]

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

[casascius]

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

[BurtW]

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

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.

[mndrix]

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.

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.

[BurtW]

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.

[PrintCoins]

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

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.

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

[BurtW]

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.

[PrintCoins]

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.

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.

[btc_artist]

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

[BurtW]

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

[marcus_of_augustus]

hmmmmm.

[etotheipi]

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

[BurtW]

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.  

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.

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?

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

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

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.

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?  

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?

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.

[mndrix]

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.

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.

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.

[BurtW]

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.