Elliptic Curve Calculator UI (now part of Armory)

[etotheipi]

All over the D&TD forum, there has been talk about creative things you can do with private and public keys, to emulate multi-signature transactions, or create shared secrets.  While these things are all theoretically possible, it takes programming experience and familiarity with an ECDSA library to actually execute them.  Not anymore!.  I have just recently integrated an ECDSA calculator into Armory, and anyone can use it, even with low-RAM computers by running Armory with the --noblockchain option.  Using this interface you can:

• Multiply private keys together
• Scalar "multiply" elliptic curve points (public keys)
• Add elliptic curve points together
• Compute addresses from public keys
• Compute public keys from private keys
• Create and verify signature blocks to send through email
• Import addresses created with the calculator into your wallet
• Do all of the above with arbitrary keys, not necessarily in any wallet!

You can download Windows binaries, or find instructions for building on Linux on the Armory webpage.

If you find this useful/interesting/amazing, please consider donating to my crowdfunding campaign, to help me continue to work on Armory (donate with credit card or BTC)!  All donations of $10 or more come with my hour-long cryptography seminar titled Understanding Cryptography:  Using Boring Math for Something Useful.  It includes a brief introduction to elliptic curves.





So, what is this calculator useful for?
Here are lots of great uses for this calculator.  Here are two specific examples:

(1)Emulated 2-of-2 multisig  Note:  this is only for the case that one party will be redeeming the full amount of the encumbered funds:  there is no trust-free way to split the funds with this method (which makes it useful for Casascius+OtherParty physical bitcoins).

• Each party produces a new address (which should not be in their wallet [explained later])
• From the wallet properties dialog, or the "Keys" tab in the calculator, fetch public keys and exchange with the other party.
• Fetch your own private key for the public key you just sent
• Use the middle entry in the calculator dialog, to multiply the other person's public key (enter x,y pair) by your private key
• Both parties get the same answer!  This is because party A has private key a and public key a*G and party B has private key b and public key b*G.  Both parties then end up producing a*b*G which is a new public key.  However, neither party can calculate a*b (which is the private key for the public key both parties calculated).
• Calculate the address for the public key, and fund it with the amount of money agreed upon.

This is called an "Elliptic-Curve Diffie-Hellman" exchange (ECDH).  It is usually for creating a shared secret with your public keys (such as an encryption key).  In this case, it lets you produce an address that only someone with both private keys can access.  At the end of this process, one person must send the other person their private key, so that they can calculate the shared private key and redeem the funds!  This is why the private key you generate should not be part of any wallet, because it will eventually be shared and you never want to share a private key in one of your wallets!  

This could be used by Casascius and another party:  Casascius and other party execute the process above, and fund the address with 1000 BTC (for a 1000 BTC gold bar).  Casascius gets his hand on the gold bar, and puts his tamper-proof private key on it.  He sends it to the other party, and they put their tamper-proof private key sticker on the other side.  Now, the user with the gold bar is the only person that will ever see both private keys (once he peels them off) and thus, the only person that can ever spend them!  Just plug one into the 'a' field of the calculator and the other one into the 'b' field of the calculator  (if Casascius wanted to do this, I would add a simpler, reduced interface for multiplying private keys, but it is technically do-able as-is).


(2)Send Signed Messages  

Remember when MtGox got hacked, and they had to retroactively verify every account's identity?  This could've been soooo much easier:

"Dear user:  We need to verify the identity of account 198483202.   The first time this account was funded, the address 1Qkj3F3qZjkPdkj389 was used to send BTC.  Please provide your name and email address, in a message signed by address 1Qkj3F3qZjkPdkj389."

This works because the account must've been originally funded by an address owned by the user.  If this message signing interface existed, it would've given MtGox a very easy way to identify most users.  In case the user doesn't have the address anymore, they can just email MtGox and ask for alternative identity verification (which turned out to be the default).  

Also consider the online casino situation.  You dump 200 BTC into this anonymous online casino.  Now, 3 weeks later, someone attempts to gamble with the money and/or cashout.  How does the casino know that you are authorized to do these things?  Well, all they care about is that the person requesting the cashout is the same person who originally funded the account.  To be absolutely safe, they could've collected your identity and provided you a login, but that would dramatically reduce the anonymity of the system.   Instead, the casino only records the first address ever used to fund your account, and that is your "username"!  The user signs a message saying "I would like to withdraw 100 BTC to the following address: ..."  Or it could be used as a way to "sign in" to your account.  In all cases, the user never had to identify themselves, and the only piece of relevant information: that the same user who funded the account is requesting something:  is easy to verify with a signed message!

[1714026906]

1714026906

[1714026906]

1714026906

[1714026906]

1714026906

[cypherdoc]

All over the D&TD forum, there has been talk about creative things you can do with private and public keys, to emulate multi-signature transactions, or create shared secrets.  While these things are all theoretically possible, it takes programming experience and familiarity with an ECDSA library to actually execute them.  Not anymore!.  I have just recently integrated an ECDSA calculator into Armory, and anyone can use it, even with low-RAM computers by running Armory with the --noblockchain option.  Using this interface you can:

• Multiply private keys together
• Scalar "multiply" elliptic curve points (public keys)
• Add elliptic curve points together
• Compute addresses from public keys
• Compute public keys from private keys
• Create and verify signature blocks to send through email
• Import addresses created with the calculator into your wallet
• Do all of the above with arbitrary keys, not necessarily in any wallet!

You can download Windows binaries, or find instructions for building on Linux on the Armory webpage.

If you find this useful/interesting/amazing, please consider donating to my crowdfunding campaign, to help me continue to work on Armory (donate with credit card or BTC)!  All donations of $10 or more come with my hour-long cryptography seminar titled Understanding Cryptography:  Using Boring Math for Something Useful.  It includes a brief introduction to elliptic curves.





So, what is this calculator useful for?
Here are lots of great uses for this calculator.  Here are two specific examples:

(1)Emulated 2-of-2 multisig  Note:  this is only for the case that one party will be redeeming the full amount of the encumbered funds:  there is no trust-free way to split the funds with this method (which makes it useful for Casascius+OtherParty physical bitcoins).

• Each party produces a new address (which should not be in their wallet [explained later])
• From the wallet properties dialog, or the "Keys" tab in the calculator, fetch public keys and exchange with the other party.
• Fetch your own private key for the public key you just sent
• Use the middle entry in the calculator dialog, to multiply the other person's public key (enter x,y pair) by your private key
• Both parties get the same answer!  This is because party A has private key a and public key a*G and party B has private key b and public key b*G.  Both parties then end up producing a*b*G which is a new public key.  However, neither party can calculate a*b (which is the private key for the public key both parties calculated).
• Calculate the address for the public key, and fund it with the amount of money agreed upon.

This is called an "Elliptic-Curve Diffie-Hellman" exchange (ECDH).  It is usually for creating a shared secret with your public keys (such as an encryption key).  In this case, it lets you produce an address that only someone with both private keys can access.  At the end of this process, one person must send the other person their private key, so that they can calculate the shared private key and redeem the funds!  This is why the private key you generate should not be part of any wallet, because it will eventually be shared and you never want to share a private key in one of your wallets!  

This could be used by Casascius and another party:  Casascius and other party execute the process above, and fund the address with 1000 BTC (for a 1000 BTC gold bar).  Casascius gets his hand on the gold bar, and puts his tamper-proof private key on it.  He sends it to the other party, and they put their tamper-proof private key sticker on the other side.  Now, the user with the gold bar is the only person that will ever see both private keys (once he peels them off) and thus, the only person that can ever spend them!  Just plug one into the 'a' field of the calculator and the other one into the 'b' field of the calculator  (if Casascius wanted to do this, I would add a simpler, reduced interface for multiplying private keys, but it is technically do-able as-is).


(2)Send Signed Messages  

Remember when MtGox got hacked, and they had to retroactively verify every account's identity?  This could've been soooo much easier:

"Dear user:  We need to verify the identity of account 198483202.   The first time this account was funded, the address 1Qkj3F3qZjkPdkj389 was used to send BTC.  Please provide your name and email address, in a message signed by address 1Qkj3F3qZjkPdkj389."

This works because the account must've been originally funded by an address owned by the user.  If this message signing interface existed, it would've given MtGox a very easy way to identify most users.  In case the user doesn't have the address anymore, they can just email MtGox and ask for alternative identity verification (which turned out to be the default).  

Also consider the online casino situation.  You dump 200 BTC into this anonymous online casino.  Now, 3 weeks later, someone attempts to gamble with the money and/or cashout.  How does the casino know that you are authorized to do these things?  Well, all they care about is that the person requesting the cashout is the same person who originally funded the account.  To be absolutely safe, they could've collected your identity and provided you a login, but that would dramatically reduce the anonymity of the system.   Instead, the casino only records the first address ever used to fund your account, and that is your "username"!  The user signs a message saying "I would like to withdraw 100 BTC to the following address: ..."  Or it could be used as a way to "sign in" to your account.  In all cases, the user never had to identify themselves, and the only piece of relevant information: that the same user who funded the account is requesting something:  is easy to verify with a signed message!

you talk about this in your slideshow seminar.  these tools are extraordinary!  keep it up.

[Red Emerald]

Is any of this accessible from the command line?

I think this could be great for generating vanity addresses for other people.

[etotheipi]

Is any of this accessible from the command line? I want to experiment with it and then modify vanitygen to do the job of generating the second private key.  Then I could generate vanity addresses for other people and they wouldn't have to worry about me having access to their funds.

The following python code will give you access to this:

Code:

from armoryengine import *

intA  = hex_to_binary('abcd1234abcd1234abcd1234abcd1234abcd1234abcd1234abcd1234abcd1234')
intB  = hex_to_binary('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee')
intCx = hex_to_binary('abababababababababababababababababababababababababababababababab')
intCy = hex_to_binary('de7dde7dde7dde7dde7dde7dde7dde7dde7dde7dde7dde7dde7dde7dde7dde7d')
intDx = hex_to_binary('6666666666666666666666666666666666666666666666666666666666666666')
intDy = hex_to_binary('abc123abc123abc123abc123abc123abc123abc123abc123abc123abc123abc1')

A_times_B = CryptoECDSA().ECMultiplyScalars(intA, intB)
A_times_C = CryptoECDSA().ECMultiplyPoint(intA, intCx, intCy)
C_plus_D  = CryptoECDSA().ECAddPoints(intCx, intCy, intDx, intDy)


print 'a*b     =', binary_to_hex(A_times_B)
print '(a*C)_x =', binary_to_hex(A_times_C[:32])
print '(a*C)_y =', binary_to_hex(A_times_C[32:])
print '(C+D)_x =', binary_to_hex(C_plus_D[:32])
print '(C+D)_y =', binary_to_hex(C_plus_D[32:])

The output of the above script is:

Code:

a*b     = 1a779cdad61f5f00ad22b4cb2d967a53678423055c08b3a4d43da39a49a080e6
(a*C)_x = 0f9ddccd4a2c5be720b99b9a6e32291ce7333a97a61282f2f2c72400d6af6d2d
(a*C)_y = 260991fe8b15f849a7139dca2ce1b7231d60178feb257ab9dee959084d52379d
(C+D)_x = ade6b9f3995f5d6a6b9ec4d8b73bd0d284744468c4a5e3be2306537e31077bcb
(C+D)_y = ded5ac1195fc3e6239659169ccf3384d70d6e1fb03ffb9840d090fff2d4f459a

Pretty simple, eh?  

P.S. - there's also an "ECInverse" function, but I haven't tested it.  Use at your own risk.

[Red Emerald]

<3

I need to install OpenOffice and then I'll watch my reward

[etotheipi]

<3

I need to install OpenOffice and then I'll watch my reward

I sent you the powerpoint version, too, didn't I?

Since you liked the previous example so much, let's get a little more advanced:  use python + armoryengine to create and verify signatures.
Note:  These functions all take "SecureBinaryData" objects, which are memory-locked, auto-destructing binary data objects.  These are not cast implicitly by python/SWIG, so it's a little more fiddling to get it right.  But that's why this is the "advanced" examples   (btw, the security of SecureBinaryData objects is probably diluted by accessing them via python, but there's no reason not to implement them correctly in C++, which may be re-used in other C++ applications later)

Code:

from armoryengine import *

# Note, all the following operations use SecureBinaryData objects which must be cast
# using .toBinStr() or .toHexStr(), or constructed SecureBinaryData(binData)
newPriv = CryptoECDSA().GenerateNewPrivateKey()
newPub  = CryptoECDSA().ComputePublicKey(newPriv)

print 'PrivKey: ', binary_to_hex(newPriv.toBinStr())
print 'PubKey_x:', binary_to_hex(newPub.toBinStr()[1:32])
print 'PubKey_y:', binary_to_hex(newPub.toBinStr()[33:])
print 'PubKey Valid? ', CryptoECDSA().VerifyPublicKeyValid(newPub)
print ''

msg = SecureBinaryData('Beware the buffoon hiding in the corner!')
sig = CryptoECDSA().SignData(msg, newPriv)
print 'Msg:  ', msg.toBinStr()
print 'Sig_r:', sig.toHexStr()[:64]  # 64 because sig is already in hex, not binary
print 'Sig_s:', sig.toHexStr()[64:]  # 64 because sig is already in hex, not binary
print 'Verified?', CryptoECDSA().VerifyData(msg, sig, newPub)

This produces the following output:

Code:

PrivKey:  11b40d463341aa7da3f1abf35893a94a4516a16a3aa7b83ded3a36dcfb0884ef
PubKey_x: ec5acc6ec078e8c1860222a6c9152d437607ab5f99fd36ed4a364db0435f61
PubKey_y: 859858c3bf78719b390f3d8b39b78acd303ee12537fba3a5ea78e216ab8349a3
PubKey Valid?  True

Msg:   Beware the buffoon hiding in the corner!
Sig_r: cc3dc787e7a5797274d41b48161ddac6956dbf15325cb44152bc8a5827de344c
Sig_s: 4f9c1443fbcddac98f03cef017497367a994164052488f571fd49af4796e173a
Verified? True

[Etlase2]

Isn't it possible to compute the public key from a signature? I don't know if this is useful client-side but who knows.

[etotheipi]

Isn't it possible to compute the public key from a signature? I don't know if this is useful client-side but who knows.

Yes.  It's called "key recovery."   But you need to add an extra couple bits to the signature (I think).  I haven't implemented this in Armory yet, but I will, along with compressed public keys.

Sub.

Uh... what?

[finway]

Sub.

Uh... what?
[/quote]

-scribe 

[istar]

Very cool work!

I really hope you get the crowdfunding completed!

I sent some coins earlier, gone send some more.

[etotheipi]

Very cool work!

I really hope you get the crowdfunding completed!

I sent some coins earlier, gone send some more.

How could I forget?!  You can also simulate a 1-of-N transaction with this calculator, and without requiring anyone to give up their private keys!

Two parties create addresses and exchange public keys.  They do the ECDH to create a new public key as described before.  Except this will not be used as a public key:  it turns out that they are the only two people that can calculate this elliptic curve point:  which is now a shared secret.  They can then hash the key to come up with a new private key that both of them can calculate.  They then fund the associated address.  

Then, they are the only two people that know the private key, and thus either of them can spend the money however they want.  This is effectively 1-of-2, though a little unsafe since you are both operating with the same private key.  You could do 1-of-N but it's a little more complicated.

I'm sure even more stuff is possible!   And I'm sure there's lots of discussion on the forums about it, but I just haven't looked around enough yet!


EDIT: If real multi-sig wasn't just around the corner, I could implement 1-of-2 deterministic wallets:   you make your own wallet and exchange watching-only wallets.  From this, you can both calculate an infinite sequence of private keys, just like a regular deterministic wallet: except that the second party can access it to.

But I think this is moot, now.  With Multi-sig right around the corner... putting in effort to enable this would not be worth, especially because the community is more interested in 2-of-2 and 2-of-3, not 1-of-2.

[cypherdoc]

you know, the capabilities of this wallet are mind boggling to even those of us who've been around for a while and especially those of us who don't have the theoretical background for these elliptical curves.

once you get the basic security and functionality bugs out it would help to point us to tutorials as to how to better understand whats going on and how best we could use it.

your seminars have been a good start.

[Mike Hearn]

If you can implement a true elliptic curve threshold signature system, that would be very impressive. It allows t-of-n signatures with the result being a regular ECDSA compatible signature. There are also algorithms that allow for dealer-free secret sharing, that is, N participants create shares in a key that allows them to group sign a message, but nobody ever has the ability to sign entirely by themselves. Kind of a more scalable CHECKMULTISIG.

Myself and justmoon have explored this topic a little, but the algorithms published in the literature are extremely complicated.

[cypherdoc]

If you can implement a true elliptic curve threshold signature system, that would be very impressive. It allows t-of-n signatures with the result being a regular ECDSA compatible signature. There are also algorithms that allow for dealer-free secret sharing, that is, N participants create shares in a key that allows them to group sign a message, but nobody ever has the ability to sign entirely by themselves. Kind of a more scalable CHECKMULTISIG.

Myself and justmoon have explored this topic a little, but the algorithms published in the literature are extremely complicated.

as i recall eto's implementation is an m-of-n whereas you recommend a t-of-n.  could you explain the difference other than you imply its not a true elliptic curve threshold sig system?  more random?

[etotheipi]

If you can implement a true elliptic curve threshold signature system, that would be very impressive. It allows t-of-n signatures with the result being a regular ECDSA compatible signature. There are also algorithms that allow for dealer-free secret sharing, that is, N participants create shares in a key that allows them to group sign a message, but nobody ever has the ability to sign entirely by themselves. Kind of a more scalable CHECKMULTISIG.

Myself and justmoon have explored this topic a little, but the algorithms published in the literature are extremely complicated.

as i recall eto's implementation is an m-of-n whereas you recommend a t-of-n.  could you explain the difference other than you imply its not a true elliptic curve threshold sig system?  more random?

To summarize everything I have talked about above:  I could theoretically implement:

• 1-of-2 transactions in a very pleasant, straightforward way
• 1-of-N transactions, but it would require manually circulating a single packet for everyone to cumulatively sign before you can even compute the 1-of-N address
• 2-of-2 transactions: but only for the case where the distribution is entirely up to one party, and the other party doesn't mind giving up the private key
• N-of-N transactions (3-of-3, 4-of-4, etc):  but it has the same creation complexity of the 1-of-N above, and the spend-complexity of the 2-of-2 above (requiring all parties except one to send their private keys to one party who gets full control over the coins)

Until Mike Hearn mentioned something, I was not aware that thresholding schemes even existed for ECDSA (like 2-of-3 txs).  It seems that this problem would be a lot easier with RSA (because signing&verification operations are much cleaner, simpler and commutative).  But key lengths are 10-20x the size, and obviously BTC doesn't use RSA...

I think it's all moot with real multi-sig around the corner.  It's a fun mathematical exercise, but I think that's all it is, since it would probably take me longer to implement these ideas, than it will take before real multi-sig is enabled on the network.

[Mike Hearn]

CHECKMULTISIG has the same effect as threshold ECDSA but it doesn't scale as well. That's the primary reason to research it, having a few hundred participants in a group signature with CHECKMULTISIG would probably blow the tx size limits, or at least take a hefty fee.

See the PDF here for an introduction to this topic:

www.twisc.ntust.edu.tw/twisc/Media/download.asp?medi_id=168

[etotheipi]

CHECKMULTISIG has the same effect as threshold ECDSA but it doesn't scale as well. That's the primary reason to research it, having a few hundred participants in a group signature with CHECKMULTISIG would probably blow the tx size limits, or at least take a hefty fee.

See the PDF here for an introduction to this topic:

www.twisc.ntust.edu.tw/twisc/Media/download.asp?medi_id=168

You are right, it's fairly complicated.  I spent about 20 minutes looking at it, and got the gist of it:  it looks like each party is producing and sharing lots of polynomials with all the other participants, in such a way that some common information can be recovered later on... But I'm going to need a lot more than 20 minutes to fully absorb it. 

When they say information is exchanged over a secure channel, I assume that something like ECDH is used to establish an encryption key, or simply using ECIES to establish a secure channel...?  Either way, it looks like it would require a lot of work to get 100 different participants to engage in this setup, requiring each participant to contact each other participant (which is what it looks like from the statement that participant Pi sends fi(xj) to participant Pj). 

Beyond the large "social" overhead of execution, my biggest concern is that these papers seem very theoretical, without any evidence that the complexity is actually secure.  I totally agree with you about the OP_CHECKMULTISIG not scaling well, but I'm not sure that a few theoretical papers can be trusted to the level of NIST-approved ECDSA operations, which I believe is necessary for any money system.  I'm sure you're familiar with all the things that can go wrong with asymmetric encryptions if you don't pay attention:  such as picking prime numbers, p & q for RSA such that (p-1) and (q-1) don't have large prime factors.  Or reusing "random" numbers in ECDSA signatures.  I remember in my Crypto class learning all sorts of abstract no-nos for use in cryptography.

Even though OP_CHECKMULTISIG doesn't scale well, I still feel like 99% of the usability is there (as part of P2SH scripts).  I would be interested to learn more about this, though...

[Vitalik Buterin]

What about encrypting messages with public keys using ECIES (http://en.wikipedia.org/wiki/Integrated_Encryption_Scheme)?

[etotheipi]

What about encrypting messages with public keys using ECIES (http://en.wikipedia.org/wiki/Integrated_Encryption_Scheme)?

Haven't done that yet and wasn't really planning to.  Though, it wouldn't take terribly long, gotta spend some time to figure out how to get the functionality out of crypto++ and add it to the interface.  So far, you are the first person to recommend it!  If others were interested, I could do it.   

But I feel like the signature operations were much more important... both for pseudo-multisig (key combining/splitting), as well as sending verifiable messages to other parties -- such as sending a mailing address for purchases.  Also, so services can start accounts based on your funding addresses, and then you can manage your account using signed messages from those addresses, without ever having to set up a login or give out personal information (I'm envisioning online gambling as a prime use-case for this).