Compressed keys, Y from X

[jackjack]

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

[Zeilap]

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;
    }
}; 

[jackjack]

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:

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

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

[Zeilap]

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:

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

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"

[jackjack]

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

[jackjack]

Yep, that works, thanks a lot!

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

[Zeilap]

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

[piotr_n]

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?

[jackjack]

02 if Y is even, 03 if odd

[piotr_n]

02 if Y is even, 03 if odd

thanks

[kjj]

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

[piotr_n]

I prefer 2+Y.Bit(0)

[piotr_n]

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

[jackjack]

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

[piotr_n]

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

[jackjack]

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

[piotr_n]

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.

[jackjack]

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 )

[piotr_n]

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.

[piotr_n]

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