140 lines
4.8 KiB
JavaScript
140 lines
4.8 KiB
JavaScript
|
|
/*
|
|
* ModSqrt borrowed and translated from http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/
|
|
*/
|
|
function LegendreSymbol(a, p) {
|
|
var r = a.modPow(p.subtract(BigInteger.ONE).divide(new BigInteger("2")), p);
|
|
if( r.equals(p.subtract(BigInteger.ONE)) ) return new BigInteger("-1");
|
|
return r;
|
|
}
|
|
|
|
/* return `ret' such that ret^2 = this (mod p) */
|
|
function bnModSqrt(p) {
|
|
var TWO = new BigInteger("2");
|
|
var NEG_ONE = new BigInteger("-1");
|
|
|
|
if( !(LegendreSymbol(this, p).equals(BigInteger.ONE)) )
|
|
return BigInteger.ZERO;
|
|
|
|
if( this.equals(BigInteger.ZERO) )
|
|
return BigInteger.ZERO;
|
|
|
|
if( p.equals(TWO) )
|
|
return p;
|
|
|
|
if( p.mod(new BigInteger("4")).equals(new BigInteger("3")) )
|
|
return this.modPow(p.add(BigInteger.ONE).divide(new BigInteger("4")), p);
|
|
|
|
var s = p.subtract(BigInteger.ONE);
|
|
var e = 0;
|
|
|
|
while( s.mod(TWO).equals(BigInteger.ZERO) ) {
|
|
s = s.divide(TWO);
|
|
e += 1;
|
|
}
|
|
|
|
// find some legendre symbol n|p = -1
|
|
var n = TWO;
|
|
while( !LegendreSymbol(n, p).equals(NEG_ONE) ) {
|
|
n = n.add(BigInteger.ONE);
|
|
}
|
|
|
|
console.log("LegendreSymbol found: " + n);
|
|
|
|
/*
|
|
* Here be dragons!
|
|
* Read the paper "Square roots from 1; 24, 51,
|
|
* 10 to Dan Shanks" by Ezra Brown for more
|
|
* information
|
|
*
|
|
* x is a guess of the square root that gets better
|
|
* with each iteration.
|
|
* b is the "fudge factor" - by how much we're off
|
|
* with the guess. The invariant x^2 = ab (mod p)
|
|
* is maintained throughout the loop.
|
|
* g is used for successive powers of n to update
|
|
* both a and b
|
|
* r is the exponent - decreases with each update
|
|
*/
|
|
var x = this.modPow(s.add(BigInteger.ONE).divide(TWO), p);
|
|
var b = this.modPow(s, p);
|
|
var g = n.modPow(s, p);
|
|
var r = e;
|
|
var q = BigInteger.ZERO.clone();
|
|
|
|
while(true) {
|
|
var t = b.clone();
|
|
var m = 0;
|
|
|
|
for( ; m < r; m += 1 ) {
|
|
if(t.equals(BigInteger.ONE))
|
|
break;
|
|
t = t.modPow(TWO, p);
|
|
}
|
|
|
|
if( m == 0 )
|
|
return x;
|
|
|
|
q.fromInt(r - m - 1);
|
|
|
|
var gs = g.modPow(TWO.pow(q), p);
|
|
g = gs.multiply(gs).mod(p);
|
|
x = x.multiply(gs).mod(p);
|
|
b = b.multiply(g).mod(p);
|
|
r = m;
|
|
}
|
|
}
|
|
|
|
BigInteger.prototype.modSqrt = bnModSqrt;
|
|
|
|
$(document).ready( function() {
|
|
return; // Comment out to run tests
|
|
|
|
var ecparams = getSECCurveByName("secp256k1");
|
|
console.log(ecparams);
|
|
|
|
var test_modsqrt = function(compressed_key_str, check_y_str) {
|
|
var key_bytes = Crypto.util.hexToBytes(compressed_key_str);
|
|
console.log(key_bytes);
|
|
|
|
var y_bit = u8(key_bytes.slice(0, 1)) & 0x01;
|
|
var x = BigInteger.ZERO.clone();
|
|
x.fromString(Crypto.util.bytesToHex(key_bytes.slice(1, 33)), 16);
|
|
console.log('x = ' + Crypto.util.bytesToHex(x.toByteArrayUnsigned()));
|
|
|
|
var curve = ecparams.getCurve();
|
|
var a = curve.getA().toBigInteger();
|
|
var b = curve.getB().toBigInteger();
|
|
var p = curve.getQ();
|
|
|
|
var tmp = x.multiply(x).multiply(x).add(a.multiply(x)).add(b).mod(p);
|
|
console.log('tmp = ' + Crypto.util.bytesToHex(tmp.toByteArrayUnsigned()));
|
|
|
|
var y = tmp.modSqrt(p);
|
|
|
|
if( (y[0] & 0x01) != y_bit ) {
|
|
y = y.multiply(new BigInteger("-1")).mod(p);
|
|
}
|
|
|
|
console.log('y = ' + Crypto.util.bytesToHex(y.toByteArrayUnsigned()));
|
|
|
|
var check_y = BigInteger.ZERO.clone();
|
|
check_y.fromString(check_y_str, 16);
|
|
|
|
if( !y.equals(check_y) ) {
|
|
alert("Error in modSqrt");
|
|
}
|
|
}
|
|
|
|
// ECDSA private key (random number / secret exponent) = 863abb33f3e3305a78f56285c5aa42bcf85c2cdef2cface9346c65233da4e3e1
|
|
// ECDSA public key (uncompressed) = 04aeb681df5ac19e449a872b9e9347f1db5a0394d2ec5caf2a9c143f86e232b0d9eb0124240d225ed0ccfb2dfa9ad05d1e5e0c7941ee5c518b398145f202cb1d13
|
|
// ECDSA public key (compressed) = 03aeb681df5ac19e449a872b9e9347f1db5a0394d2ec5caf2a9c143f86e232b0d9
|
|
test_modsqrt('03aeb681df5ac19e449a872b9e9347f1db5a0394d2ec5caf2a9c143f86e232b0d9', 'eb0124240d225ed0ccfb2dfa9ad05d1e5e0c7941ee5c518b398145f202cb1d13');
|
|
|
|
// ECDSA private key (random number / secret exponent) = 7a26b3657dfa753a6a32962fde76e2d8202b3eaa1603270119ce4156472c4d20
|
|
// ECDSA public key (uncompressed) = 042ba95457d7274368a191d43cc379e357ba577d7a24262ae375cca78a2224f3f011a0fed69a15c28dea6f433255dc765403794c562a444015b996f7ac234141d8
|
|
// ECDSA public key (compressed) = 022ba95457d7274368a191d43cc379e357ba577d7a24262ae375cca78a2224f3f0
|
|
test_modsqrt('022ba95457d7274368a191d43cc379e357ba577d7a24262ae375cca78a2224f3f0', '11a0fed69a15c28dea6f433255dc765403794c562a444015b996f7ac234141d8');
|
|
|
|
});
|