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?
Topic: Compressed keys, Y from X - page 2. (Read 3136 times)
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:EDIT:
I still have a question: how do you know that sqrt(a) = a(q+1)/4 ?
Fermat's little theorem tells us that aq-1 = 1 (mod q), so by rearranging,
aq-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 = x2, 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.
Yep, that works, thanks a lot!
EDIT:
I still have a question: how do you know that sqrt(a) = a(q+1)/4 ?
EDIT:
I still have a question: how do you know that sqrt(a) = a(q+1)/4 ?
Wow I can't even use correctly my library...
I'll look at that to get it sorted and hopefully report the success soon
I'll look at that to get it sorted and hopefully report the success soon
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:
I get:
y2=7f65351d4485d7656f60f8a4e5c802cc5ba6a1eae5d0e94b63357ab43d18b53e
x3=368e518c43bee254854b3c43aa9893e65a3d19282468bae274e93e5cb93d0946
Whereas I should have y2 = x3 + 7 (secp256k1)
I don't get these values for x3 and y2. I getI 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
public key: 046655feed4d214c261e0a6b554395596f1f1476a77d999560e5a8df9b8a1a3515217e88dd05e93 8efdd71b2cce322bf01da96cd42087b236e8f5043157a9c068e
->
X: 6655feed4d214c261e0a6b554395596f1f1476a77d999560e5a8df9b8a1a3515
Y: 217e88dd05e938efdd71b2cce322bf01da96cd42087b236e8f5043157a9c068e
I get:
y2=7f65351d4485d7656f60f8a4e5c802cc5ba6a1eae5d0e94b63357ab43d18b53e
x3=368e518c43bee254854b3c43aa9893e65a3d19282468bae274e93e5cb93d0946
Whereas I should have y2 = x3 + 7 (secp256k1)
x3 = ec4081ea3487eadbad1ec86b4fca367185932b0a435c30a4b570b5535e37b17c
y2 = 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"
> 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"
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:
I get:
y2=7f65351d4485d7656f60f8a4e5c802cc5ba6a1eae5d0e94b63357ab43d18b53e
x3=368e518c43bee254854b3c43aa9893e65a3d19282468bae274e93e5cb93d0946
Whereas I should have y2 = x3 + 7 (secp256k1)
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
public key: 046655feed4d214c261e0a6b554395596f1f1476a77d999560e5a8df9b8a1a3515217e88dd05e93 8efdd71b2cce322bf01da96cd42087b236e8f5043157a9c068e
->
X: 6655feed4d214c261e0a6b554395596f1f1476a77d999560e5a8df9b8a1a3515
Y: 217e88dd05e938efdd71b2cce322bf01da96cd42087b236e8f5043157a9c068e
I get:
y2=7f65351d4485d7656f60f8a4e5c802cc5ba6a1eae5d0e94b63357ab43d18b53e
x3=368e518c43bee254854b3c43aa9893e65a3d19282468bae274e93e5cb93d0946
Whereas I should have y2 = x3 + 7 (secp256k1)
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. 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
y2 = x3+ ax2 + 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;
}
};
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
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
Jump to: