Compressed private keys: how to get Y from X

[casascius]

I am wondering if anyone would be willing to give me the quick tl;dr for how to get an elliptic curve point's Y given X.  Or in other words get the uncompressed version of a compressed point.

My understanding is that for every X, there's two possible Y's, and they differ in some trivial way (such as one is odd and one is even), and which to use is denoted by the byte that comes in front of X.  Further, I understand that the equation y^2=x^3+ax+b is involved, but am not clear how to wrap my head around that and the finite field arithmetic, and my main objective is to upgrade my Casascius Bitcoin Address Utility to support compressed keys.

I'm using BouncyCastle.  Would someone be so kind as to point me in the right direction or offer the code snippet that does this?  Perhaps this functionality (or some primitive it's based upon) is built into BouncyCastle and I just don't know it.  For example, I'm able to find things like this http://www.item.ntnu.no/europki08/presentations/europki08-brumley.pdf but would prefer to use tested code instead of reinventing the wheel.  Thanks in advance.

Edit: I think I'm probably warm with BouncyCastle's decodePoint

[casascius]

OK, I was able to figure this all out.  My utility as tested seems to handle compressed private keys just fine, and produces identical results to BitAddress.org's screens that do the same thing.

Now, I went to BitAddress.org to use the "Vanity Wallet" screen as a test reference, expecting this screen does EC multiplication.

Seems to me I'm wrong and that it actually does EC addition - something I thought we decided was vulnerable.  I guess it's not vulnerable if the vanity generator has to cough up the private key, but still, I'm surprised we're doing EC addition when implementing EC multiplication is just as simple (assuming it's all a library call anyway).

[casascius]

I just published my work on my Casascius Bitcoin Address Utility to fully support compressed private keys.  This new version features a key combiner, which can combine two keys via EC-multiplication and EC-addition.

Feel free to test it.  I'll call it Alpha, because most of the classes have been totally refactored and not thoroughly tested (but the results were correct for the cases I tested)

https://casascius.com/btcaddress-alpha.zip (Windows, binary with C# source - Visual Studio 2010)

[nibor]

Seems to me I'm wrong and that it actually does EC addition - something I thought we decided was vulnerable. 

Yes bitaddress.org does addition. This is because that is what vanitygen.exe -P does.

Why do you say addition is more vulnerable? I can not think of any reason for that.

[casascius]

The vulnerability is related to the fact that point addition can be reversed and point multiplication cannot.  Exploiting it involves passing a specially crafted public key generated through "point subtraction"- and may not affect vanitygen because of the fact that a private key is passed to the buyer immediately.

[casascius]

It occurs to me why addition might be used in vanitygen... point addition is the way vanitygen achieves acceleration past simply brute-forcing random private keys.  If I think about it, it occurs to me that if vanitygen had to use multiplication, it would suffer a major performance cost.  If the security risk inherent in addition doesn't apply because the buyer of the vanitygen service gets his private key immediately (something an attacker wouldn't be able to provide), then it's clear that addition is the right solution.

I have written my utility so it can do both addition and multiplication.

[etotheipi]

Not sure it matters anymore, but I did program an ECDSA calculator into Armory, under "Tools->EC Calculator".  You can multiply scalars mod N (where N is the modulus of the secp256k1 curve), point-addition, and scalar-point multiplication.  It works for doing shared keys like you talk about it your thread on 2-factor physical coins:  you can start Armory in offline mode, create a new wallet, create two addresses, copy&paste the private and public keys, then plug them into the calculator using scalar-point multiplication and verify that A*B' == A'*B.  Then calculate A*B and A*B*G to see that you get what you expect.