Print Page - Compressed keys, Y from X

Title: Compressed keys, Y from X
Post by: jackjack on April 01, 2013, 12:56:54 AM

Hi,
I'd like to know if there is a formula to calculate the two possible values of Y from X
I use a library that needs them, and I don't really want to modify it

Title: Re: Compressed keys, Y from X
Post by: Zeilap on April 01, 2013, 01:12:55 AM

Quote from: jackjack on April 01, 2013, 12:56:54 AM

Hi,
I'd like to know if there is a formula to calculate the two possible values of Y from X
I use a library that needs them, and I don't really want to modify it

Actually it's very simple.

y² = x³+ ax² + b
so we need to perform square root to recover y from x. And it turns out that
sqrt(a) = a^(q+1)/4

Now you just have to pick either the positive or negative solution. If the y that you calculated is even, and the first byte of the key is even, then use this value, otherwise, use the negative value which is q-y.

EDIT: relevant code I wrote as a patch for bitaddress.org

Code:

	
ec.CurveFp.prototype.decompressPoint = function(yOdd, X) {
    if(this.q.mod(BigInteger.valueOf(4)).equals(BigInteger.valueOf(3))) {
        // y^2 = x^3 + ax^2 + b, so we need to perform sqrt to recover y
        var ySquared = X.multiply(X.square().add(this.a)).add(this.b);

        // sqrt(a) = a^((q+1)/4) if q = 3 mod 4
        var Y = ySquared.x.modPow(this.q.add(BigInteger.ONE).divide(BigInteger.valueOf(4)), this.q);

        if(Y.testBit(0) !== yOdd) {
            Y = this.q.subtract(Y);
        }

        return new ec.PointFp(this, X, this.fromBigInteger(Y));
    }
    else {
        // only implement sqrt for q = 3 mod 4
        return null;
    }
};

// for now, work with hex strings because they're easier in JS
ec.CurveFp.prototype.decodePointHex = function (s) {
    switch (parseInt(s.substr(0, 2), 16)) { // first byte
    case 0:
        return this.infinity;
    case 2:
        return this.decompressPoint(false, this.fromBigInteger(new BigInteger(s.substr(2), 16)));
    case 3:
        return this.decompressPoint(true, this.fromBigInteger(new BigInteger(s.substr(2), 16)));
    case 4:
    case 6:
    case 7:
        var len = (s.length - 2) / 2;
        var xHex = s.substr(2, len);
        var yHex = s.substr(len + 2, len);

        return new ec.PointFp(this,
                              this.fromBigInteger(new BigInteger(xHex, 16)),
                              this.fromBigInteger(new BigInteger(yHex, 16)));

    default: // unsupported
        return null;
    }
};

Title: Re: Compressed keys, Y from X
Post by: jackjack on April 01, 2013, 02:06:38 AM

Thanks, that helps a lot!
I still have a problem though, the equation doesn't match my data (I wanted to check on an example first)
Let's take that example:

Quote

secret: 0123456789012345678901234567890123456789012345678901234567890123
public key: 046655feed4d214c261e0a6b554395596f1f1476a77d999560e5a8df9b8a1a3515217e88dd05e93 8efdd71b2cce322bf01da96cd42087b236e8f5043157a9c068e
->
X: 6655feed4d214c261e0a6b554395596f1f1476a77d999560e5a8df9b8a1a3515
Y: 217e88dd05e938efdd71b2cce322bf01da96cd42087b236e8f5043157a9c068e

I get:
y²=7f65351d4485d7656f60f8a4e5c802cc5ba6a1eae5d0e94b63357ab43d18b53e
x³=368e518c43bee254854b3c43aa9893e65a3d19282468bae274e93e5cb93d0946
Whereas I should have y² = x³ + 7 (secp256k1)

Title: Re: Compressed keys, Y from X
Post by: Zeilap on April 01, 2013, 02:52:53 AM

Quote from: jackjack on April 01, 2013, 02:06:38 AM

Thanks, that helps a lot!
I still have a problem though, the equation doesn't match my data (I wanted to check on an example first)
Let's take that example:

Quote

I get:
y²=7f65351d4485d7656f60f8a4e5c802cc5ba6a1eae5d0e94b63357ab43d18b53e
x³=368e518c43bee254854b3c43aa9893e65a3d19282468bae274e93e5cb93d0946
Whereas I should have y² = x³ + 7 (secp256k1)

I don't get these values for x³ and y². I get
x³ = ec4081ea3487eadbad1ec86b4fca367185932b0a435c30a4b570b5535e37b17c
y² = ec4081ea3487eadbad1ec86b4fca367185932b0a435c30a4b570b5535e37b183

If you load up bitaddress.org and then use 'Web console' in Firefox or 'Javascript console' in Chrome you can try it out like this

Code:

> var curve = EllipticCurve.getSECCurveByName('secp256k1').getCurve()
> var key = new Bitcoin.ECKey(new BigInteger('0123456789012345678901234567890123456789012345678901234567890123',16))
> key.getPubKeyHex()
"046655FEED4D214C261E0A6B554395596F1F1476A77D999560E5A8DF9B8A1A3515217E88DD05E938EFDD71B2CCE322BF01DA96CD42087B236E8F5043157A9C068E"
> x = new BigInteger(key.getPubKeyHex().substr(2,64), 16)
> x.toString(16)
"6655feed4d214c261e0a6b554395596f1f1476a77d999560e5a8df9b8a1a3515"
> y = new BigInteger(key.getPubKeyHex().substr(66), 16)
> y.toString(16)
"217e88dd05e938efdd71b2cce322bf01da96cd42087b236e8f5043157a9c068e"
> x.modPow(BigInteger.valueOf(3), curve.q).toString(16)
"ec4081ea3487eadbad1ec86b4fca367185932b0a435c30a4b570b5535e37b17c"
> y.modPow(BigInteger.valueOf(2), curve.q).toString(16)
"ec4081ea3487eadbad1ec86b4fca367185932b0a435c30a4b570b5535e37b183"

Title: Re: Compressed keys, Y from X
Post by: jackjack on April 01, 2013, 12:41:17 PM

Wow I can't even use correctly my library...
I'll look at that to get it sorted and hopefully report the success soon

Title: Re: Compressed keys, Y from X
Post by: jackjack on April 01, 2013, 01:48:31 PM

Yep, that works, thanks a lot!

EDIT:
I still have a question: how do you know that sqrt(a) = a^(q+1)/4 ?

Title: Re: Compressed keys, Y from X
Post by: Zeilap on April 01, 2013, 08:26:57 PM

Quote from: jackjack on April 01, 2013, 01:48:31 PM

Yep, that works, thanks a lot!

EDIT:
I still have a question: how do you know that sqrt(a) = a^(q+1)/4 ?

Here's a sketch of why:
Fermat's little theorem (https://en.wikipedia.org/wiki/Fermat%27s_little_theorem) tells us that a^q-1 = 1 (mod q), so by rearranging,
a^q-1 - 1 = 0 (mod q)
which we can factorise into
(a^(q-1)/2 - 1)(a^(q-1)/2 + 1) = 0 (mod q)

These factors multiply to zero, so one of the factors must itself be zero. In particular, we must have a^(q-1)/2 = -1 or +1 (mod q). Each case actually corresponds to whether the square root exists or not (1 for exists, -1 for doesn't exist).

Now, let's say a = x², so that sqrt(a) = x. Then,
a^(q+1)/4 = x^(q+1)/2 = x^{(q-1)/2 + 1} = x * x^(q-1)/2 = +x or -x (mod q)

There's a little more work to show that the square root is unique, which is not true in general, for instance
3*3 = 1 (mod 8 ) and
1*1 = 1 (mod 8 )
So in this case, 1 has multiple square roots modulo 8. However for our q, they are unique.

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 01, 2013, 06:15:04 PM

Sorry for maybe a stupid question, but I have a need to make a reverse operation; compress a key.

So, how do I decide whether to set 02 or 03 in front of the X?

Title: Re: Compressed keys, Y from X
Post by: jackjack on May 01, 2013, 09:49:20 PM

02 if Y is even, 03 if odd

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 02, 2013, 08:23:16 AM

Quote from: jackjack on May 01, 2013, 09:49:20 PM

02 if Y is even, 03 if odd

thanks

Title: Re: Compressed keys, Y from X
Post by: kjj on May 02, 2013, 12:24:56 PM

You can also think of it as 0x02+mod(Y,2)

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 02, 2013, 02:10:47 PM

I prefer 2+Y.Bit(0) :P

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 11, 2013, 01:30:49 PM

I have a slightly different question, but since there are some real math experts in this topic already, please let me ask it in here.

I need to write a function that recovers a public key from ECDSA signature.
It's the algorithm described in section 4.6.1 of the SEC1 spec (http://www.secg.org/index.php?action=secg,docs_secg) - it seems simple, but I guess I am just too stupid to get it :)

Let's say that we have a signature of:

Code:

R = E1D48751A24F0DB604C86A4706D2113FF869808522E8AF4A04F253F03EA87EF1
S = 669E60CFAD73A7FFD63054DBA4D0DB88C628633EE90FCF0D620FF40DE91C3296

The 1st byte of this signature is 0x1F, but I don't think it matters at this stage. Actually it does a bit, since it says that bit(0) of Y is 0.

So, the operation I need to do first, is the equivalent of openssl's ec_GFp_simple_set_compressed_coordinates().
It takes X and the parity of Y, and returns some point R - right?
From what I see the actual result, for the example inputs, should be:

Code:

Rx : 7E677C42747BBDEF47AFAA51001D55A82D8C2B643EF74D6E014F64DCFD31BBA0
Ry : 0D1081A16E20A8839D892ACC384529CA4547D007B58559483991C3EB77DC71BC

Could anyone please tell me how to calculate this R, preferably with some example, in python or whatever..?
I was trying to reverse engineer how openssl does it, but analyzing that code has not got me too far, so far... :)

Also, if you could please explain me what is an "octet string" and how is it different from a big integer expressed as MSB encoded string of bytes?

Title: Re: Compressed keys, Y from X
Post by: jackjack on May 11, 2013, 01:38:43 PM

I'm about to release a code for signing in Armory
If I understood correctly, it should solve your problem

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 11, 2013, 01:39:52 PM

Quote from: jackjack on May 11, 2013, 01:38:43 PM

I'm about to release a code for signing in Armory
If I understood correctly, it should solve your problem

OK - I'll be looking forward for it..
Cheers

Title: Re: Compressed keys, Y from X
Post by: jackjack on May 11, 2013, 02:05:58 PM

In the mean time, could you post the message and address that give this signature?
It seems odd because Rx = r + {0;1}*q and this doesn't correspond to your example at all (first bits should be the same as q=0xffffffffffffffff...)

For exemple, signing 'bitcoin' with private key '\x01'*32 gives

Code:

Flag: 1c -> uncompressed key and Rx=r+0*q
r:    b6392b8e0250550a0a068e8ba68891d555a34eb48fe6266ae042b3c689265586
s:    b220ecbbe88b379812fbc920afcb15a4bd17a73f7555a5fea92b3b4c6a187523

So Rx=b6392b8e0250550a0a068e8ba68891d555a34eb48fe6266ae042b3c689265586

It's from the top of my head, I'll post the code when I have access to my dev computer

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 11, 2013, 03:27:42 PM

May it be because it is a signature from a testnet address?

Code:

bitcoind -testnet verifymessage mqMmY5Uc6AgWoemdbRsvkpTes5hF6p5d8w "H+HUh1GiTw22BMhqRwbSET/4aYCFIuivSgTyU/A+qH7xZp5gz61zp//WMFTbpNDbiMYoYz7pD88NYg/0DekcMpY=" test
true

And this was a compressed key.

Also I was giving the intermediate R - not the Q, that comes at the end.
How to calc the Q - this was supposed to be my next question, because is seems to be even more screwed up :)

And then, at the very end, they take the X and Y from the Q (that is already called a "public key"):

Code:

Q.X: 6130AE7913286EC4D8296AEB7361420C259CD11478FB24FEDA77F81E256059AA
Q.Y: B3A6E7A704FCC0A59AC40BD364336A629483453CF39BB060F92354434B44F636

.. and turn it into an actual bitcoin public key, where:

Code:

X: 05eb0c4f42ecf74ab8789f2855ef33cad6ac0ec1ba6b7179578cb9f218e7793d

So how much more crazy could it be? :)

I spent about 6 hours today trying to figure it out, before finally deciding to seek some help on the forum.

Title: Re: Compressed keys, Y from X
Post by: jackjack on May 11, 2013, 03:43:11 PM

I'm finishing the code, it's coming in the following hours
Here's what I get for your test:

Code:

fb:    1b
recid: 0
r:     e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
s:     669e60cfad73a7ffd63054dba4d0db88c628633ee90fcf0d620ff40de91c3296
Rx:    e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
Ry:    8f875bbc497b680cfe288eeda4bfb1da78af6703afdfaaf580e9e656ad62531c

As for Q:
Q = inv_r * ( R*s + G*minus_e )

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 11, 2013, 03:48:47 PM

Quote from: jackjack on May 11, 2013, 03:43:11 PM

I'm finishing the code, it's coming in the following hours
Here's what I get for your test:

Code:

fb:    1b
recid: 0
r:     e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
s:     669e60cfad73a7ffd63054dba4d0db88c628633ee90fcf0d620ff40de91c3296
Rx:    e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
Ry:    8f875bbc497b680cfe288eeda4bfb1da78af6703afdfaaf580e9e656ad62531c

Yeah - that was actually my first guess, that the "Rx" should be the same as the "r", while Ry should be calculated in the same way as we calc Y from 02||X, for a compressed public key.
But after I put some debugs into bitcoin's key.cpp, it seems that the EC_POINT_set_compressed_coordinates_GFp that is called from there returns completely different X.

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 11, 2013, 04:03:01 PM

At some point (in ec_GFp_simple_set_compressed_coordinates function) I do have:

Code:

x:    e1d48751a24f0db604c86a4706d2113ff869808522e8af4a04f253f03ea87ef1
y:    8f875bbc497b680cfe288eeda4bfb1da78af6703afdfaaf580e9e656ad62531c

... but then, the function calls EC_POINT_set_affine_coordinates_GFp to "assign" these x,y values into the R - and after this the R's, x and y are:

Code:

Rx : 7E677C42747BBDEF47AFAA51001D55A82D8C2B643EF74D6E014F64DCFD31BBA0
Ry : 0D1081A16E20A8839D892ACC384529CA4547D007B58559483991C3EB77DC71BC

Title: Re: Compressed keys, Y from X
Post by: jackjack on May 11, 2013, 06:03:05 PM

I don't get where those values come from...

See https://github.com/jackjack-jj/jasvet/blob/master/jasvet.py
Line 361

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 11, 2013, 06:26:43 PM

Quote from: jackjack on May 11, 2013, 06:03:05 PM

I don't get where those values come from...

See https://github.com/jackjack-jj/jasvet/blob/master/jasvet.py
Line 361

Thanks! I will have a look..

I was hoping that it would actually be less complicated than what I see in bitcoind+openssl :)

Title: Re: Compressed keys, Y from X
Post by: jackjack on May 11, 2013, 07:29:30 PM

I don't find that as complicated as in bitcoin-qt
Your specific problem is only between lines 361->412. I even left the print's so you can uncomment them to see the values

Just delete everything after line 530 and put this

Code:

verifySignature('mqMmY5Uc6AgWoemdbRsvkpTes5hF6p5d8w','H+HUh1GiTw22BMhqRwbSET/4aYCFIuivSgTyU/A+qH7xZp5gz61zp//WMFTbpNDbiMYoYz7pD88NYg/0DekcMpY=','test')

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 11, 2013, 07:31:06 PM

Indeed, it looks cool and simple - and it works!

But can you please tell me what the "R*s" (in line 406) actually does?
I mean, you have (decimals):

Code:

Rx = 102145896445573563625240447116654222837109247557536823325858067433615090286321
Ry = 64919894836278270547560110097107560214300342546989031110129938591497073087260
s = 46415740558353013011708862292271156479711188487571029354677187424581448381078

... and R*s gives you a point having:

Code:

x = 112793881772482502863430761842017408792441979840968192252645857563994847441261
y = 47321320458075246750488099844078925876574705494449064910511016586200529015312

So how do I multiply a point by a number to get such a result? I mean, not using python..

Title: Re: Compressed keys, Y from X
Post by: jackjack on May 11, 2013, 07:37:15 PM

It's the ECC multiplication
You can look at lines 216->237 for algorithm

To understand:
http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa.pdf
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/Elliptic_curve
etc...

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 11, 2013, 07:39:09 PM

Quote from: jackjack on May 11, 2013, 07:37:15 PM

OK - thanks a lot, man!
That's all I needed to know.

Title: Re: Compressed keys, Y from X
Post by: piotr_n on May 11, 2013, 08:15:58 PM

And so it worked in my language as well. :)
https://github.com/piotrnar/gocoin/blob/master/tools/versigmsg.go

Thanks again, @jackjack!

Title: Re: Compressed keys, Y from X
Post by: jackjack on May 11, 2013, 10:11:19 PM

I'm glad that helped!

Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: jackjack on April 01, 2013, 12:56:54 AM