To find square root mod p when p%4 = 3 (prime of secp256k1 curve is like that) you can compute x(p+1)/4 (mod p) instead.
I'm trying to grok my head around this.
We have y^2 = x^3 + 7 so before I wrote this topic I had the idea that the next statement took the 4th root of Right Hand Side (power by p+1 is equivalent to just 1, and I had the belief that coord^((p+1)/2) was equivalent to taking the square root - since we clearly cannot raise by the fractional power 1/2, but (p+1)/2 is equivalent to that).
In other words, (y^2)^((p+1)/4) would've been sqrt(y) not y. It's like in algebra how you apply the first sqrt and then you have (y)^((p+1)/2).
But apparently the p+1 is to ensure that modulus is zero, i.e. (p+1) % 4 = 0, and then the division by 4 is done. So how is dividing this shifted prime by 4 equivalent to a square root?
Is it because we are now taking the modular power by a whole number? Then why 4 specifically and not some other number?
0 or 1 is subtracted from the recid not the square root.
No look, bitcoinsig.js that is used in the "brainwallet.github.io" sites has this in the verificaiton algo:
function verify_message(signature, message, addrtype) {
try {
var sig = Crypto.util.base64ToBytes(signature);
} catch(err) {
return false;
}
if (sig.length != 65)
return false;
// extract r,s from signature
var r = BigInteger.fromByteArrayUnsigned(sig.slice(1,1+32));
var s = BigInteger.fromByteArrayUnsigned(sig.slice(33,33+32));
// get recid
var compressed = false;
var nV = sig[0];
if (nV < 27 || nV >= 35)
return false;
if (nV >= 31) {
compressed = true;
nV -= 4;
}
var recid = BigInteger.valueOf(nV - 27);
var ecparams = getSECCurveByName("secp256k1");
var curve = ecparams.getCurve();
var a = curve.getA().toBigInteger();
var b = curve.getB().toBigInteger();
var p = curve.getQ();
var G = ecparams.getG();
var order = ecparams.getN();
var x = r.add(order.multiply(recid.divide(BigInteger.valueOf(2))));
var alpha = x.multiply(x).multiply(x).add(a.multiply(x)).add(b).mod(p);
var beta = alpha.modPow(p.add(BigInteger.ONE).divide(BigInteger.valueOf(4)), p);
// It's subtracting recID from Y here, i.e. it is effectively subtracting 0 or 1 from it (ignoring the higher bit) - NotATether
var y = beta.subtract(recid).isEven() ? beta : p.subtract(beta);
var R = new ECPointFp(curve, curve.fromBigInteger(x), curve.fromBigInteger(y));
var e = BigInteger.fromByteArrayUnsigned(msg_digest(message));
var minus_e = e.negate().mod(order);
var inv_r = r.modInverse(order);
var Q = (R.multiply(s).add(G.multiply(minus_e))).multiply(inv_r);
var public_key = Q.getEncoded(compressed);
var addr = new Bitcoin.Address(Bitcoin.Util.sha256ripe160(public_key));
addr.version = addrtype ? addrtype : 0;
return addr.toString();
}
