aboutsummaryrefslogtreecommitdiffstats
path: root/public/js/modsqrt.js
diff options
context:
space:
mode:
authorAdam Soltys <[email protected]>2015-11-28 23:57:34 -0800
committerAdam Soltys <[email protected]>2015-11-30 21:10:59 -0800
commit41f8c6831bb91c0b0be1219b1566e59e48673465 (patch)
tree39626cf1a8fe7b8d73f750ccaf433bfa8c425d6b /public/js/modsqrt.js
parentf2bff842cbe16c18923b905f70ed168096648727 (diff)
downloadcoinos-server-41f8c6831bb91c0b0be1219b1566e59e48673465.tar.gz
coinos-server-41f8c6831bb91c0b0be1219b1566e59e48673465.zip
Use bower, grunt and browserify instead of connect-assets
Diffstat (limited to 'public/js/modsqrt.js')
-rw-r--r--public/js/modsqrt.js139
1 files changed, 0 insertions, 139 deletions
diff --git a/public/js/modsqrt.js b/public/js/modsqrt.js
deleted file mode 100644
index f58223ba..00000000
--- a/public/js/modsqrt.js
+++ /dev/null
@@ -1,139 +0,0 @@
-
-/*
- * 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');
-
-});